001: /******************************************************************
002: * File: RuleState.java
003: * Created by: Dave Reynolds
004: * Created on: 11-May-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: RuleState.java,v 1.9 2008/01/02 12:09:44 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl.oldCode;
010:
011: import com.hp.hpl.jena.reasoner.rulesys.*;
012: import com.hp.hpl.jena.reasoner.rulesys.impl.BindingVector;
013: import com.hp.hpl.jena.reasoner.rulesys.impl.StateFlag;
014: import com.hp.hpl.jena.reasoner.*;
015: import com.hp.hpl.jena.graph.*;
016:
017: /**
018: * Part of the backward chaining rule interpreter. A RuleState represents
019: * the state of a partially expanded search tree for a single Rule.
020: * The RuleStates are linked back in an OR tree to a root goal which is
021: * being satisfied. Each RuleState shares a pointer to a RuleInstance which
022: * holds references for the rule being processed and the goal which the rule is
023: * satisfying.
024: * <p>
025: * Encapuslation warning: this object is used in the tight inner loop of the engine so we access its
026: * field pointers directly rather than through accessor methods.
027: * </p>
028: *
029: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
030: * @version $Revision: 1.9 $ on $Date: 2008/01/02 12:09:44 $
031: */
032: public class RuleState {
033:
034: /** Reference to a package of information on the rule being processed */
035: protected RuleInstance ruleInstance;
036:
037: /** the parent RuleState for backtracking */
038: protected RuleState prev;
039:
040: /** The binding environment for the rule so far */
041: protected BindingVector env;
042:
043: /** The continuation point for the rule clause being processed */
044: protected GoalState goalState;
045:
046: /** Flag to indicate that rule state is scheduled on the agenda */
047: protected boolean isScheduled = false;
048:
049: /** The clause number in the rule to be processed next. */
050: int clauseIndex;
051:
052: /** binding offset for subject field, -1 if none */
053: int subjectBind;
054:
055: /** binding offset for predicate field, -1 if none */
056: int predicateBind;
057:
058: /** binding offset for object field, -1 if none */
059: int objectBind;
060:
061: /** functor node for object binding */
062: protected Functor functorMatch = null;
063:
064: /**
065: * Normal constructor. Creates a new RuleState as an extension to an existing one.
066: * @param parent the parent RuleState being expanded, can't be null
067: * @param clause the TriplePattern which forms the goal for this state
068: * @param index the index of the clause in the parent rule
069: * @param env the prebound enviornment to use
070: */
071: public RuleState(RuleState parent, TriplePattern clause, int index,
072: BindingVector env) {
073: prev = parent;
074: ruleInstance = parent.ruleInstance;
075: clauseIndex = index;
076: this .env = env;
077: TriplePattern subgoal = env
078: .partInstantiate((TriplePattern) clause);
079: goalState = ruleInstance.engine.findGoal(subgoal);
080: initMapping(subgoal);
081: ruleInstance.generator.incRefCount();
082: }
083:
084: /**
085: * Constructor used when creating the first RuleState for a rule.
086: * The caller is responsible for initializing the mapping.
087: */
088: private RuleState(RuleInstance ruleInstance, BindingVector env,
089: GoalState goalState, int index) {
090: prev = null;
091: this .ruleInstance = ruleInstance;
092: this .env = env;
093: this .goalState = goalState;
094: this .clauseIndex = index;
095: ruleInstance.generator.incRefCount();
096: }
097:
098: /**
099: * Return the next match for this clause (or FAIL or SUSPEND)
100: */
101: Object next() {
102: if (goalState == null) {
103: return StateFlag.SATISFIED;
104: } else {
105: return goalState.next();
106: }
107: }
108:
109: /**
110: * Return a new binding environment based on this one but extended
111: * by the matches resulting from the given triple result for this state.
112: */
113: public BindingVector newEnvironment(Triple result) {
114: BindingVector newenv = new BindingVector(env);
115: if (subjectBind != -1)
116: newenv.bind(subjectBind, result.getSubject());
117: if (predicateBind != -1)
118: newenv.bind(predicateBind, result.getPredicate());
119: if (objectBind != -1)
120: newenv.bind(objectBind, result.getObject());
121: // Functor matches are not precompiled but intepreted
122: if (functorMatch != null) {
123: Node obj = result.getObject();
124: if (Functor.isFunctor(obj)) {
125: Functor objValue = (Functor) obj.getLiteralValue();
126: if (objValue.getName().equals(functorMatch.getName())) {
127: Node[] margs = functorMatch.getArgs();
128: Node[] args = objValue.getArgs();
129: if (margs.length != args.length)
130: return null;
131: for (int i = 0; i < margs.length; i++) {
132: Node match = margs[i];
133: if (match instanceof Node_RuleVariable) {
134: Node val = args[i];
135: if (Functor.isFunctor(val))
136: return null;
137: if (!newenv.bind(match, val))
138: return null;
139: }
140: }
141: } else {
142: return null;
143: }
144: } else {
145: return null;
146: }
147: }
148: return newenv;
149: }
150:
151: /**
152: * Return the final goal result, based on the given binding environment
153: */
154: public Triple getResult(BindingVector newenv) {
155: return newenv.instantiate(ruleInstance.head);
156: }
157:
158: /**
159: * Return true if it seems worth scheduling this RuleState. This will be the case
160: * if the RS can be immediately disposed of due to being complete or if there is a result known already.
161: */
162: public boolean couldProcess() {
163: if (goalState == null)
164: return true;
165: return goalState.couldProcess();
166: }
167:
168: /**
169: * Initialize the mapping pointers that map result values to environment bindings
170: */
171: private void initMapping(TriplePattern goal) {
172: Node n = goal.getSubject();
173: subjectBind = (n instanceof Node_RuleVariable) ? ((Node_RuleVariable) n)
174: .getIndex()
175: : -1;
176: n = goal.getPredicate();
177: predicateBind = (n instanceof Node_RuleVariable) ? ((Node_RuleVariable) n)
178: .getIndex()
179: : -1;
180: n = goal.getObject();
181: objectBind = (n instanceof Node_RuleVariable) ? ((Node_RuleVariable) n)
182: .getIndex()
183: : -1;
184: if (Functor.isFunctor(n))
185: functorMatch = (Functor) n.getLiteralValue();
186: }
187:
188: /**
189: * Return the index of the next body clause to try.
190: * Takes clause reordering into account.
191: */
192: protected int nextClauseIndex() {
193: if (ruleInstance.clausesReordered) {
194: if (clauseIndex == (ruleInstance.secondClause + 1)) {
195: // go back to do first clause
196: return ruleInstance.secondClause - 1;
197: } else if (clauseIndex == ruleInstance.secondClause) {
198: return clauseIndex + 1;
199: }
200: }
201: return clauseIndex;
202: }
203:
204: /**
205: * Close a non-longer needed rule state. This will decrement
206: * the reference count of the goal table entry (this might have been
207: * the last RuleState working on that entry) and will close any
208: * iterators in the goal state.
209: */
210: public void close() {
211: if (goalState != null)
212: goalState.close();
213: ruleInstance.generator.decRefCount();
214: }
215:
216: /**
217: * Create the first RuleState for using a given rule to satisfy a goal.
218: * @param rule the rule being instantiated
219: * @param generator the GoalTable entry that this rule should generate results for
220: * @param engine the parent rule engine
221: * @return the instantiated initial RuleState or null if a guard predicate
222: * fails so the rule is not applicable.
223: */
224: public static RuleState createInitialState(Rule rule,
225: GoalResults generator) {
226: // Axioms are alredy handled by the infGraph so this first guard should be helpful but
227: // in practice it doesn't seem to.
228: // if (rule.bodyLength() == 0) return null;
229: TriplePattern goal = generator.goal;
230: TriplePattern head = (TriplePattern) rule.getHeadElement(0);
231: BindingVector env = BindingVector.unify(goal, head, rule
232: .getNumVars());
233: if (env == null)
234: return null;
235:
236: // Find the first goal clause
237: RuleInstance ri = new RuleInstance(generator, rule, head);
238: int maxClause = rule.bodyLength();
239: int clauseIndex = 0;
240: while (clauseIndex < maxClause) {
241: ClauseEntry clause = rule.getBodyElement(clauseIndex++);
242: if (clause instanceof TriplePattern) {
243: // Check for possible clause reorder ...
244: ClauseEntry secondClause = null;
245: boolean foundSecondClause = false;
246: if (clauseIndex < maxClause) {
247: secondClause = rule.getBodyElement(clauseIndex);
248: if (secondClause instanceof TriplePattern) {
249: foundSecondClause = true;
250: }
251: }
252: if (foundSecondClause) {
253: int score1 = scoreClauseBoundness(
254: (TriplePattern) clause, head, env);
255: int score2 = scoreClauseBoundness(
256: (TriplePattern) secondClause, head, env);
257: if (score2 > score1) {
258: ri.clausesReordered = true;
259: ri.secondClause = clauseIndex;
260: clause = secondClause;
261: clauseIndex++;
262: }
263: }
264: // ... end of clause reorder
265: TriplePattern subgoal = env
266: .partInstantiate((TriplePattern) clause);
267: if (!subgoal.isLegal())
268: return null;
269: GoalState gs = generator.getEngine().findGoal(subgoal);
270: RuleState rs = new RuleState(ri, env, gs, clauseIndex);
271: rs.initMapping(subgoal);
272: return rs;
273: } else {
274: if (!generator.getEngine().processBuiltin(clause, rule,
275: env)) {
276: return null;
277: }
278: }
279: }
280: // If we get to here there are no rule body clause to process
281: return new RuleState(ri, env, null, 0);
282: }
283:
284: /**
285: * Score a clause in terms of groundedness using simple heurisitcs.
286: * For this case we are only considering head variables which occur
287: * in the clause and score on boundedness of these.
288: */
289: private static int scoreClauseBoundness(TriplePattern clause,
290: TriplePattern head, BindingVector env) {
291: return scoreNodeBoundness(clause.getSubject(), head, env)
292: + scoreNodeBoundness(clause.getPredicate(), head, env)
293: + scoreNodeBoundness(clause.getObject(), head, env);
294:
295: }
296:
297: /**
298: * Score a node from a pattern as part of scoreClauseBoundedness.
299: */
300: private static int scoreNodeBoundness(Node n, TriplePattern head,
301: BindingVector env) {
302: if (n.isVariable()) {
303: if (n == head.getSubject() || n == head.getPredicate()
304: || n == head.getObject()) {
305: Node val = env.getBinding(n);
306: if (val == null || val.isVariable())
307: return -5;
308: return 5;
309: } else {
310: return 0;
311: }
312: } else {
313: return 1;
314: }
315: }
316:
317: /**
318: * Printable string
319: */
320: public String toString() {
321: return "RuleState " + ruleInstance.rule.toShortString() + "("
322: + (clauseIndex - 1) + ")"
323: // + ", env=" + env
324: + ", gs=" + goalState;
325: }
326:
327: }
328:
329: /*
330: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
331: All rights reserved.
332:
333: Redistribution and use in source and binary forms, with or without
334: modification, are permitted provided that the following conditions
335: are met:
336:
337: 1. Redistributions of source code must retain the above copyright
338: notice, this list of conditions and the following disclaimer.
339:
340: 2. Redistributions in binary form must reproduce the above copyright
341: notice, this list of conditions and the following disclaimer in the
342: documentation and/or other materials provided with the distribution.
343:
344: 3. The name of the author may not be used to endorse or promote products
345: derived from this software without specific prior written permission.
346:
347: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
348: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
349: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
350: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
351: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
352: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
353: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
354: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
355: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
356: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
357: */
|