KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > reasoner > rulesys > impl > oldCode > RuleState


1 /******************************************************************
2  * File: RuleState.java
3  * Created by: Dave Reynolds
4  * Created on: 11-May-2003
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: RuleState.java,v 1.4 2005/02/21 12:18:05 andy_seaborne Exp $
9  *****************************************************************/
10 package com.hp.hpl.jena.reasoner.rulesys.impl.oldCode;
11
12 import com.hp.hpl.jena.reasoner.rulesys.*;
13 import com.hp.hpl.jena.reasoner.rulesys.impl.BindingVector;
14 import com.hp.hpl.jena.reasoner.rulesys.impl.StateFlag;
15 import com.hp.hpl.jena.reasoner.*;
16 import com.hp.hpl.jena.graph.*;
17
18 /**
19  * Part of the backward chaining rule interpreter. A RuleState represents
20  * the state of a partially expanded search tree for a single Rule.
21  * The RuleStates are linked back in an OR tree to a root goal which is
22  * being satisfied. Each RuleState shares a pointer to a RuleInstance which
23  * holds references for the rule being processed and the goal which the rule is
24  * satisfying.
25  * <p>
26  * Encapuslation warning: this object is used in the tight inner loop of the engine so we access its
27  * field pointers directly rather than through accessor methods.
28  * </p>
29  *
30  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
31  * @version $Revision: 1.4 $ on $Date: 2005/02/21 12:18:05 $
32  */
33 public class RuleState {
34
35     /** Reference to a package of information on the rule being processed */
36     protected RuleInstance ruleInstance;
37     
38     /** the parent RuleState for backtracking */
39     protected RuleState prev;
40     
41     /** The binding environment for the rule so far */
42     protected BindingVector env;
43     
44     /** The continuation point for the rule clause being processed */
45     protected GoalState goalState;
46     
47     /** Flag to indicate that rule state is scheduled on the agenda */
48     protected boolean isScheduled = false;
49     
50     /** The clause number in the rule to be processed next. */
51     int clauseIndex;
52     
53     /** binding offset for subject field, -1 if none */
54     int subjectBind;
55     
56     /** binding offset for predicate field, -1 if none */
57     int predicateBind;
58     
59     /** binding offset for object field, -1 if none */
60     int objectBind;
61     
62     /** functor node for object binding */
63     protected Functor functorMatch = null;
64     
65     /**
66      * Normal constructor. Creates a new RuleState as an extension to an existing one.
67      * @param parent the parent RuleState being expanded, can't be null
68      * @param clause the TriplePattern which forms the goal for this state
69      * @param index the index of the clause in the parent rule
70      * @param env the prebound enviornment to use
71      */
72     public RuleState(RuleState parent, TriplePattern clause, int index, BindingVector env) {
73         prev = parent;
74         ruleInstance = parent.ruleInstance;
75         clauseIndex = index;
76         this.env = env;
77         TriplePattern subgoal = env.partInstantiate((TriplePattern)clause);
78         goalState = ruleInstance.engine.findGoal(subgoal);
79         initMapping(subgoal);
80         ruleInstance.generator.incRefCount();
81     }
82     
83     /**
84      * Constructor used when creating the first RuleState for a rule.
85      * The caller is responsible for initializing the mapping.
86      */
87     private RuleState(RuleInstance ruleInstance, BindingVector env, GoalState goalState, int index) {
88         prev = null;
89         this.ruleInstance = ruleInstance;
90         this.env = env;
91         this.goalState = goalState;
92         this.clauseIndex = index;
93         ruleInstance.generator.incRefCount();
94     }
95     
96     /**
97      * Return the next match for this clause (or FAIL or SUSPEND)
98      */
99     Object JavaDoc next() {
100         if (goalState == null) {
101             return StateFlag.SATISFIED;
102         } else {
103             return goalState.next();
104         }
105     }
106     
107     /**
108      * Return a new binding environment based on this one but extended
109      * by the matches resulting from the given triple result for this state.
110      */
111     public BindingVector newEnvironment(Triple result) {
112         BindingVector newenv = new BindingVector(env);
113         if (subjectBind != -1) newenv.bind(subjectBind, result.getSubject());
114         if (predicateBind != -1) newenv.bind(predicateBind, result.getPredicate());
115         if (objectBind != -1) newenv.bind(objectBind, result.getObject());
116         // Functor matches are not precompiled but intepreted
117 if (functorMatch != null) {
118             Node obj = result.getObject();
119             if (Functor.isFunctor(obj)) {
120                 Functor objValue = (Functor)obj.getLiteral().getValue();
121                 if (objValue.getName().equals(functorMatch.getName())) {
122                     Node[] margs = functorMatch.getArgs();
123                     Node[] args = objValue.getArgs();
124                     if (margs.length != args.length) return null;
125                     for (int i = 0; i < margs.length; i++) {
126                         Node match = margs[i];
127                         if (match instanceof Node_RuleVariable) {
128                             Node val = args[i];
129                             if (Functor.isFunctor(val)) return null;
130                             if (!newenv.bind(match, val)) return null;
131                         }
132                     }
133                 } else {
134                     return null;
135                 }
136             } else {
137                 return null;
138             }
139         }
140         return newenv;
141     }
142     
143     /**
144      * Return the final goal result, based on the given binding environment
145      */
146     public Triple getResult(BindingVector newenv) {
147         return newenv.instantiate(ruleInstance.head);
148     }
149     
150     /**
151      * Return true if it seems worth scheduling this RuleState. This will be the case
152      * if the RS can be immediately disposed of due to being complete or if there is a result known already.
153      */
154     public boolean couldProcess() {
155         if (goalState == null) return true;
156         return goalState.couldProcess();
157     }
158     
159     /**
160      * Initialize the mapping pointers that map result values to environment bindings
161      */
162     private void initMapping(TriplePattern goal) {
163         Node n = goal.getSubject();
164         subjectBind = (n instanceof Node_RuleVariable) ? ((Node_RuleVariable)n).getIndex() : -1 ;
165         n = goal.getPredicate();
166         predicateBind = (n instanceof Node_RuleVariable) ? ((Node_RuleVariable)n).getIndex() : -1 ;
167         n = goal.getObject();
168         objectBind = (n instanceof Node_RuleVariable) ? ((Node_RuleVariable)n).getIndex() : -1 ;
169         if (Functor.isFunctor(n)) functorMatch = (Functor)n.getLiteral().getValue();
170     }
171     
172     /**
173      * Return the index of the next body clause to try.
174      * Takes clause reordering into account.
175      */
176     protected int nextClauseIndex() {
177         if (ruleInstance.clausesReordered) {
178             if (clauseIndex == (ruleInstance.secondClause + 1) ) {
179                 // go back to do first clause
180 return ruleInstance.secondClause - 1;
181             } else if (clauseIndex == ruleInstance.secondClause) {
182                 return clauseIndex + 1;
183             }
184         }
185         return clauseIndex;
186     }
187     
188     /**
189      * Close a non-longer needed rule state. This will decrement
190      * the reference count of the goal table entry (this might have been
191      * the last RuleState working on that entry) and will close any
192      * iterators in the goal state.
193      */
194     public void close() {
195         if (goalState != null) goalState.close();
196         ruleInstance.generator.decRefCount();
197     }
198         
199     /**
200      * Create the first RuleState for using a given rule to satisfy a goal.
201      * @param rule the rule being instantiated
202      * @param generator the GoalTable entry that this rule should generate results for
203      * @param engine the parent rule engine
204      * @return the instantiated initial RuleState or null if a guard predicate
205      * fails so the rule is not applicable.
206      */
207     public static RuleState createInitialState(Rule rule, GoalResults generator) {
208         // Axioms are alredy handled by the infGraph so this first guard should be helpful but
209 // in practice it doesn't seem to.
210 // if (rule.bodyLength() == 0) return null;
211 TriplePattern goal = generator.goal;
212         TriplePattern head = (TriplePattern) rule.getHeadElement(0);
213         BindingVector env = BindingVector.unify(goal, head, rule.getNumVars());
214         if (env == null) return null;
215         
216         // Find the first goal clause
217 RuleInstance ri = new RuleInstance(generator, rule, head);
218         int maxClause = rule.bodyLength();
219         int clauseIndex = 0;
220         while (clauseIndex < maxClause) {
221             ClauseEntry clause = rule.getBodyElement(clauseIndex++);
222             if (clause instanceof TriplePattern) {
223                 // Check for possible clause reorder ...
224 ClauseEntry secondClause = null;
225                 boolean foundSecondClause = false;
226                 if (clauseIndex < maxClause) {
227                     secondClause = rule.getBodyElement(clauseIndex);
228                     if (secondClause instanceof TriplePattern) {
229                         foundSecondClause = true;
230                     }
231                 }
232                 if (foundSecondClause) {
233                     int score1 = scoreClauseBoundness((TriplePattern)clause, head, env);
234                     int score2 = scoreClauseBoundness((TriplePattern)secondClause, head, env);
235                     if (score2 > score1) {
236                         ri.clausesReordered = true;
237                         ri.secondClause = clauseIndex;
238                         clause = secondClause;
239                         clauseIndex++;
240                     }
241                 }
242                 // ... end of clause reorder
243 TriplePattern subgoal = env.partInstantiate((TriplePattern)clause);
244                 if (!subgoal.isLegal()) return null;
245                 GoalState gs = generator.getEngine().findGoal(subgoal);
246                 RuleState rs = new RuleState(ri, env, gs, clauseIndex);
247                 rs.initMapping(subgoal);
248                 return rs;
249             } else {
250                 if (!generator.getEngine().processBuiltin(clause, rule, env)) {
251                     return null;
252                 }
253             }
254         }
255         // If we get to here there are no rule body clause to process
256 return new RuleState(ri, env, null, 0);
257     }
258     
259     
260     /**
261      * Score a clause in terms of groundedness using simple heurisitcs.
262      * For this case we are only considering head variables which occur
263      * in the clause and score on boundedness of these.
264      */
265     private static int scoreClauseBoundness(TriplePattern clause,
266                                                TriplePattern head,
267                                                BindingVector env) {
268         return
269                 scoreNodeBoundness(clause.getSubject(), head, env) +
270                 scoreNodeBoundness(clause.getPredicate(), head, env) +
271                 scoreNodeBoundness(clause.getObject(), head, env);
272
273     }
274     
275     /**
276      * Score a node from a pattern as part of scoreClauseBoundedness.
277      */
278     private static int scoreNodeBoundness(Node n, TriplePattern head, BindingVector env) {
279         if (n.isVariable()) {
280             if (n == head.getSubject() || n == head.getPredicate() || n == head.getObject() ) {
281                 Node val = env.getBinding(n);
282                 if (n == null || n.isVariable()) return -5;
283                 return 5;
284             } else {
285                 return 0;
286             }
287         } else {
288             return 1;
289         }
290     }
291     
292     /**
293      * Printable string
294      */
295     public String JavaDoc toString() {
296         return "RuleState "
297                 + ruleInstance.rule.toShortString()
298                 + "("+ (clauseIndex-1) +")"
299 // + ", env=" + env
300 + ", gs=" + goalState;
301     }
302     
303 }
304
305 /*
306     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
307     All rights reserved.
308
309     Redistribution and use in source and binary forms, with or without
310     modification, are permitted provided that the following conditions
311     are met:
312
313     1. Redistributions of source code must retain the above copyright
314        notice, this list of conditions and the following disclaimer.
315
316     2. Redistributions in binary form must reproduce the above copyright
317        notice, this list of conditions and the following disclaimer in the
318        documentation and/or other materials provided with the distribution.
319
320     3. The name of the author may not be used to endorse or promote products
321        derived from this software without specific prior written permission.
322
323     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
324     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
325     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
326     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
327     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
328     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
329     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
330     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
331     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
332     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
333 */
Popular Tags