001: /******************************************************************
002: * File: LPBRuleEngine.java
003: * Created by: Dave Reynolds
004: * Created on: 21-Jul-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: LPInterpreter.java,v 1.15 2008/01/02 12:06:17 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import com.hp.hpl.jena.graph.*;
012: import com.hp.hpl.jena.reasoner.*;
013: import com.hp.hpl.jena.reasoner.rulesys.*;
014: import com.hp.hpl.jena.util.PrintUtil;
015:
016: import java.util.*;
017: import org.apache.commons.logging.Log;
018: import org.apache.commons.logging.LogFactory;
019:
020: /**
021: * Bytecode interpeter engine for the LP version of the backward
022: * chaining rule system. An instance of this is forked off for each
023: * parallel query.
024: *
025: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
026: * @version $Revision: 1.15 $ on $Date: 2008/01/02 12:06:17 $
027: */
028: public class LPInterpreter {
029:
030: // =======================================================================
031: // Variables
032:
033: /** The engine which is using this interpreter */
034: protected LPBRuleEngine engine;
035:
036: /** The execution context that should be notified of suspended branches */
037: protected LPInterpreterContext iContext;
038:
039: /** True if the engine has terminated */
040: protected boolean isComplete = false;
041:
042: /** The set of temporary variables (Ti) in use by this interpreter */
043: protected Node[] tVars = new Node[RuleClauseCode.MAX_TEMPORARY_VARS];
044:
045: /** The set of argument variables (Ai) in use by this interpreter */
046: protected Node[] argVars = new Node[RuleClauseCode.MAX_ARGUMENT_VARS];
047:
048: /** The set of "permanent" variables (Yi) in use by this interpreter */
049: protected Node[] pVars = null;
050:
051: /** The current environment frame */
052: protected EnvironmentFrame envFrame;
053:
054: /** The current choice point frame */
055: protected FrameObject cpFrame;
056:
057: /** The trail of variable bindings that have to be unwound on backtrack */
058: protected ArrayList trail = new ArrayList();
059:
060: /** The execution context description to be passed to builtins */
061: protected RuleContext context;
062:
063: /** Trick to allow the very top level triple lookup to return results with reduced store turnover */
064: protected TopLevelTripleMatchFrame topTMFrame;
065:
066: /** Original set up goal, only used for debugging */
067: protected TriplePattern goal;
068:
069: static Log logger = LogFactory.getLog(LPInterpreter.class);
070:
071: // =======================================================================
072: // Constructors
073:
074: /**
075: * Constructor used to construct top level calls.
076: * @param engine the engine which is calling this interpreter
077: * @param goal the query to be satisfied
078: */
079: public LPInterpreter(LPBRuleEngine engine, TriplePattern goal) {
080: this (engine, goal, engine.getRuleStore().codeFor(goal), true);
081: }
082:
083: /**
084: * Constructor.
085: * @param engine the engine which is calling this interpreter
086: * @param goal the query to be satisfied
087: * @param isTop true if this is a top level call from the outside iterator, false means it is an
088: * internal generator call which means we don't need to insert an tabled call
089: */
090: public LPInterpreter(LPBRuleEngine engine, TriplePattern goal,
091: boolean isTop) {
092: this (engine, goal, engine.getRuleStore().codeFor(goal), isTop);
093: }
094:
095: /**
096: * Constructor.
097: * @param engine the engine which is calling this interpreter
098: * @param goal the query to be satisfied
099: * @param clauses the set of code blocks needed to implement this goal
100: * @param isTop true if this is a top level call from the outside iterator, false means it is an
101: * internal generator call which means we don't need to insert an tabled call
102: */
103: public LPInterpreter(LPBRuleEngine engine, TriplePattern goal,
104: List clauses, boolean isTop) {
105: this .engine = engine;
106: this .goal = goal; // Used for debug only
107:
108: // Construct dummy top environemnt which is a call into the clauses for this goal
109: if (engine.getDerivationLogging()) {
110: envFrame = new EnvironmentFrameWithDerivation(
111: RuleClauseCode.returnCodeBlock);
112: } else {
113: envFrame = new EnvironmentFrame(
114: RuleClauseCode.returnCodeBlock);
115: }
116: envFrame.allocate(RuleClauseCode.MAX_PERMANENT_VARS);
117: HashMap mappedVars = new HashMap();
118: envFrame.pVars[0] = argVars[0] = standardize(goal.getSubject(),
119: mappedVars);
120: envFrame.pVars[1] = argVars[1] = standardize(goal
121: .getPredicate(), mappedVars);
122: envFrame.pVars[2] = argVars[2] = standardize(goal.getObject(),
123: mappedVars);
124: if (engine.getDerivationLogging()) {
125: ((EnvironmentFrameWithDerivation) envFrame)
126: .initDerivationRecord(argVars);
127: }
128:
129: if (clauses != null && clauses.size() > 0) {
130: if (isTop && engine.getRuleStore().isTabled(goal)) {
131: setupTabledCall(0, 0);
132: // setupClauseCall(0, 0, clauses);
133: } else {
134: setupClauseCall(0, 0, clauses, goal.isGround());
135: }
136: }
137:
138: // TripleMatchFrame tmFrame = new TripleMatchFrame(this);
139: topTMFrame = new TopLevelTripleMatchFrame(this , goal);
140: topTMFrame.linkTo(cpFrame);
141: topTMFrame.setContinuation(0, 0);
142: cpFrame = topTMFrame;
143: }
144:
145: /**
146: * Called by top level interpeter to set to execution context for this interpeter to be
147: * top level instead of an internal generator.
148: */
149: public void setTopInterpreter(LPInterpreterContext context) {
150: iContext = context;
151: FrameObject topChoice = topTMFrame.getLink();
152: if (topChoice instanceof ConsumerChoicePointFrame) {
153: ((ConsumerChoicePointFrame) topChoice).context = context;
154: }
155: }
156:
157: // =======================================================================
158: // Control methods
159:
160: /**
161: * Stop the current work. This is called if the top level results iterator has
162: * either finished or the calling application has had enough.
163: */
164: public void close() {
165: synchronized (engine) {
166: isComplete = true;
167: engine.detach(this );
168: if (cpFrame != null)
169: cpFrame.close();
170: }
171: }
172:
173: /**
174: * Start the interpreter running with the given context.
175: */
176: public void setState(LPInterpreterState state) {
177: if (state instanceof ConsumerChoicePointFrame) {
178: restoreState((ConsumerChoicePointFrame) state);
179: } else {
180: iContext = (LPInterpreterContext) state;
181: }
182: }
183:
184: /**
185: * Return the next result from this engine, no further initialization.
186: * Should be called from within an appropriately synchronized block.
187: * @param context the generator choice point or top level iterator which
188: * is requesting this result and might have preserved state to restore
189: * @return either a StateFlag or a result Triple
190: */
191: public Object next() {
192: boolean traceOn = engine.isTraceOn();
193:
194: // System.out.println("next() on interpeter for goal " + goal);
195: StateFlag answer = run();
196: // System.out.println("end next() on interpeter for goal " + goal);
197:
198: if (answer == StateFlag.FAIL || answer == StateFlag.SUSPEND) {
199: return answer;
200: } else if (answer == StateFlag.SATISFIED) {
201: if (traceOn)
202: logger.info("RETURN: " + topTMFrame.lastMatch);
203: return topTMFrame.lastMatch;
204: } else {
205: Triple t = new Triple(deref(pVars[0]), deref(pVars[1]),
206: derefPossFunctor(pVars[2]));
207: if (traceOn)
208: logger.info("RETURN: " + t);
209: return t;
210: }
211: }
212:
213: /**
214: * Preserve the current interpreter state in the given
215: * @return
216: */
217: /**
218: * Return the engine which owns this interpreter.
219: */
220: public LPBRuleEngine getEngine() {
221: return engine;
222: }
223:
224: /**
225: * Return the current choice point frame that can be used to restart the
226: * interpter at this point.
227: */
228: public FrameObject getChoiceFrame() {
229: return cpFrame;
230: }
231:
232: /**
233: * Return the context in which this interpreter is running, that is
234: * either the Generator for a tabled goal or a top level iterator.
235: */
236: public LPInterpreterContext getContext() {
237: return iContext;
238: }
239:
240: // =======================================================================
241: // Engine implementation
242:
243: /**
244: * Restore the current choice point and restart execution of the LP code
245: * until either find a successful branch (in which case exit with StateFlag.ACTIVE
246: * and variables bound to the correct results) or exhaust all choice points (in
247: * which case exit with StateFlag.FAIL and no bound results). In future tabled
248: * version could also exit with StateFlag.SUSPEND in cases whether the intepreter
249: * needs to suspend to await tabled results from a parallel proof tree.
250: */
251: protected StateFlag run() {
252: int pc = 0; // Program code counter
253: int ac = 0; // Program arg code counter
254: RuleClauseCode clause = null; // The clause being executed
255: ChoicePointFrame choice = null;
256: byte[] code;
257: Object[] args;
258: boolean traceOn = engine.isTraceOn();
259: boolean recordDerivations = engine.getDerivationLogging();
260:
261: main: while (cpFrame != null) {
262: // restore choice point
263: if (cpFrame instanceof ChoicePointFrame) {
264: choice = (ChoicePointFrame) cpFrame;
265: if (!choice.hasNext()) {
266: // No more choices left in this choice point
267: cpFrame = choice.getLink();
268: if (traceOn)
269: logger.info("FAIL in clause "
270: + choice.envFrame.clause
271: + " choices exhausted");
272: continue main;
273: }
274:
275: clause = (RuleClauseCode) choice.nextClause();
276: // Create an execution environment for the new choice of clause
277: if (recordDerivations) {
278: envFrame = new EnvironmentFrameWithDerivation(
279: clause);
280: } else {
281: envFrame = new EnvironmentFrame(clause);
282: }
283: envFrame.linkTo(choice.envFrame);
284: envFrame.cpc = choice.cpc;
285: envFrame.cac = choice.cac;
286:
287: // Restore the choice point state
288: System.arraycopy(choice.argVars, 0, argVars, 0,
289: RuleClauseCode.MAX_ARGUMENT_VARS);
290: int trailMark = choice.trailIndex;
291: if (trailMark < trail.size()) {
292: unwindTrail(trailMark);
293: }
294: pc = ac = 0;
295: if (recordDerivations) {
296: ((EnvironmentFrameWithDerivation) envFrame)
297: .initDerivationRecord(argVars);
298: }
299:
300: if (traceOn)
301: logger.info("ENTER " + clause + " : "
302: + getArgTrace());
303:
304: // then fall through into the recreated execution context for the new call
305:
306: } else if (cpFrame instanceof TripleMatchFrame) {
307: TripleMatchFrame tmFrame = (TripleMatchFrame) cpFrame;
308:
309: // Restore the calling context
310: envFrame = tmFrame.envFrame;
311: clause = envFrame.clause;
312: int trailMark = tmFrame.trailIndex;
313: if (trailMark < trail.size()) {
314: unwindTrail(trailMark);
315: }
316:
317: // Find the next choice result directly
318: if (!tmFrame.nextMatch(this )) {
319: // No more matches
320: cpFrame = cpFrame.getLink();
321: if (traceOn)
322: logger.info("TRIPLE match (" + tmFrame.goal
323: + ") -> FAIL");
324: continue main;
325: }
326: if (traceOn) {
327: logger.info("TRIPLE match (" + tmFrame.goal
328: + ") -> " + getArgTrace());
329: logger.info("RENTER " + clause);
330: }
331:
332: pc = tmFrame.cpc;
333: ac = tmFrame.cac;
334:
335: if (recordDerivations) {
336: if (envFrame instanceof EnvironmentFrameWithDerivation) {
337: ((EnvironmentFrameWithDerivation) envFrame)
338: .noteMatch(tmFrame.goal, pc);
339: }
340: }
341:
342: // then fall through to the execution context in which the the match was called
343:
344: } else if (cpFrame instanceof TopLevelTripleMatchFrame) {
345: TopLevelTripleMatchFrame tmFrame = (TopLevelTripleMatchFrame) cpFrame;
346:
347: // Find the next choice result directly
348: if (!tmFrame.nextMatch(this )) {
349: // No more matches
350: cpFrame = cpFrame.getLink();
351: if (traceOn)
352: logger.info("TRIPLE match (" + tmFrame.goal
353: + ") -> FAIL");
354: continue main;
355: } else {
356: // Match but this is the top level so return the triple directly
357: if (traceOn)
358: logger.info("TRIPLE match (" + tmFrame.goal
359: + ") ->");
360: return StateFlag.SATISFIED;
361: }
362:
363: } else if (cpFrame instanceof ConsumerChoicePointFrame) {
364: ConsumerChoicePointFrame ccp = (ConsumerChoicePointFrame) cpFrame;
365:
366: // Restore the calling context
367: envFrame = ccp.envFrame;
368: clause = envFrame.clause;
369: if (traceOn)
370: logger.info("RESTORE " + clause
371: + ", due to tabled goal "
372: + ccp.generator.goal);
373: int trailMark = ccp.trailIndex;
374: if (trailMark < trail.size()) {
375: unwindTrail(trailMark);
376: }
377:
378: // Find the next choice result directly
379: StateFlag state = ccp.nextMatch(this );
380: if (state == StateFlag.FAIL) {
381: // No more matches
382: cpFrame = cpFrame.getLink();
383: if (traceOn)
384: logger.info("FAIL " + clause);
385: continue main;
386: } else if (state == StateFlag.SUSPEND) {
387: // Require other generators to cycle before resuming this one
388: preserveState(ccp);
389: iContext.notifyBlockedOn(ccp);
390: cpFrame = cpFrame.getLink();
391: if (traceOn)
392: logger.info("SUSPEND " + clause);
393: continue main;
394: }
395:
396: pc = ccp.cpc;
397: ac = ccp.cac;
398:
399: if (recordDerivations) {
400: if (envFrame instanceof EnvironmentFrameWithDerivation) {
401: ((EnvironmentFrameWithDerivation) envFrame)
402: .noteMatch(ccp.goal, pc);
403: }
404: }
405:
406: // then fall through to the execution context in which the the match was called
407:
408: } else {
409: throw new ReasonerException(
410: "Internal error in backward rule system, unrecognized choice point");
411: }
412:
413: engine.incrementProfile(clause);
414:
415: interpreter: while (envFrame != null) {
416:
417: // Start of bytecode intepreter loop
418: // Init the state variables
419: pVars = envFrame.pVars;
420: int yi, ai, ti;
421: Node arg, constant;
422: List predicateCode;
423: TripleMatchFrame tmFrame;
424: code = clause.getCode();
425: args = clause.getArgs();
426:
427: codeloop: while (true) {
428: switch (code[pc++]) {
429: case RuleClauseCode.TEST_BOUND:
430: ai = code[pc++];
431: if (deref(argVars[ai]).isVariable()) {
432: if (traceOn)
433: logger.info("FAIL " + clause);
434: continue main;
435: }
436: break;
437:
438: case RuleClauseCode.TEST_UNBOUND:
439: ai = code[pc++];
440: if (!deref(argVars[ai]).isVariable()) {
441: if (traceOn)
442: logger.info("FAIL " + clause);
443: continue main;
444: }
445: break;
446:
447: case RuleClauseCode.ALLOCATE:
448: int envSize = code[pc++];
449: envFrame.allocate(envSize);
450: pVars = envFrame.pVars;
451: break;
452:
453: case RuleClauseCode.GET_VARIABLE:
454: yi = code[pc++];
455: ai = code[pc++];
456: pVars[yi] = argVars[ai];
457: break;
458:
459: case RuleClauseCode.GET_TEMP:
460: ti = code[pc++];
461: ai = code[pc++];
462: tVars[ti] = argVars[ai];
463: break;
464:
465: case RuleClauseCode.GET_CONSTANT:
466: ai = code[pc++];
467: arg = argVars[ai];
468: if (arg instanceof Node_RuleVariable)
469: arg = ((Node_RuleVariable) arg).deref();
470: constant = (Node) args[ac++];
471: if (arg instanceof Node_RuleVariable) {
472: bind(arg, constant);
473: } else {
474: if (!arg.sameValueAs(constant)) {
475: if (traceOn)
476: logger.info("FAIL " + clause);
477: continue main;
478: }
479: }
480: break;
481:
482: case RuleClauseCode.GET_FUNCTOR:
483: Functor func = (Functor) args[ac++];
484: boolean match = false;
485: Node o = argVars[2];
486: if (o instanceof Node_RuleVariable)
487: o = ((Node_RuleVariable) o).deref();
488: if (Functor.isFunctor(o)) {
489: Functor funcArg = (Functor) o
490: .getLiteralValue();
491: if (funcArg.getName()
492: .equals(func.getName())) {
493: if (funcArg.getArgLength() == func
494: .getArgLength()) {
495: Node[] fargs = funcArg.getArgs();
496: for (int i = 0; i < fargs.length; i++) {
497: argVars[i + 3] = fargs[i];
498: }
499: match = true;
500: }
501: }
502: } else if (o.isVariable()) {
503: // Construct a new functor in place
504: Node[] fargs = new Node[func.getArgLength()];
505: Node[] templateArgs = func.getArgs();
506: for (int i = 0; i < fargs.length; i++) {
507: Node template = templateArgs[i];
508: if (template.isVariable())
509: template = new Node_RuleVariable(
510: null, i + 3);
511: fargs[i] = template;
512: argVars[i + 3] = template;
513: }
514: Node newFunc = Functor.makeFunctorNode(func
515: .getName(), fargs);
516: bind(((Node_RuleVariable) o).deref(),
517: newFunc);
518: match = true;
519: }
520: if (!match) {
521: if (traceOn)
522: logger.info("FAIL " + clause);
523: continue main; // fail to unify functor shape
524: }
525: break;
526:
527: case RuleClauseCode.UNIFY_VARIABLE:
528: yi = code[pc++];
529: ai = code[pc++];
530: if (!unify(argVars[ai], pVars[yi])) {
531: if (traceOn)
532: logger.info("FAIL " + clause);
533: continue main;
534: }
535: break;
536:
537: case RuleClauseCode.UNIFY_TEMP:
538: ti = code[pc++];
539: ai = code[pc++];
540: if (!unify(argVars[ai], tVars[ti])) {
541: if (traceOn)
542: logger.info("FAIL " + clause);
543: continue main;
544: }
545: break;
546:
547: case RuleClauseCode.PUT_NEW_VARIABLE:
548: yi = code[pc++];
549: ai = code[pc++];
550: argVars[ai] = pVars[yi] = new Node_RuleVariable(
551: null, yi);
552: break;
553:
554: case RuleClauseCode.PUT_VARIABLE:
555: yi = code[pc++];
556: ai = code[pc++];
557: argVars[ai] = pVars[yi];
558: break;
559:
560: case RuleClauseCode.PUT_DEREF_VARIABLE:
561: yi = code[pc++];
562: ai = code[pc++];
563: argVars[ai] = deref(pVars[yi]);
564: break;
565:
566: case RuleClauseCode.PUT_TEMP:
567: ti = code[pc++];
568: ai = code[pc++];
569: argVars[ai] = tVars[ti];
570: break;
571:
572: case RuleClauseCode.PUT_CONSTANT:
573: ai = code[pc++];
574: argVars[ai] = (Node) args[ac++];
575: break;
576:
577: case RuleClauseCode.CLEAR_ARG:
578: ai = code[pc++];
579: argVars[ai] = new Node_RuleVariable(null, ai);
580: break;
581:
582: case RuleClauseCode.MAKE_FUNCTOR:
583: Functor f = (Functor) args[ac++];
584: Node[] fargs = new Node[f.getArgLength()];
585: System.arraycopy(argVars, 3, fargs, 0,
586: fargs.length);
587: argVars[2] = Functor.makeFunctorNode(f
588: .getName(), fargs);
589: break;
590:
591: case RuleClauseCode.LAST_CALL_PREDICATE:
592: // TODO: improved implementation of last call case
593: case RuleClauseCode.CALL_PREDICATE:
594: List clauses = (List) args[ac++];
595: // Check if this call is now grounded
596: boolean groundCall = isGrounded(argVars[0])
597: && isGrounded(argVars[1])
598: && isGrounded(argVars[2]);
599: setupClauseCall(pc, ac, clauses, groundCall);
600: setupTripleMatchCall(pc, ac);
601: continue main;
602:
603: case RuleClauseCode.CALL_PREDICATE_INDEX:
604: // This code path is experimental, don't yet know if it has enough
605: // performance benefit to justify the cost of maintaining it.
606: clauses = (List) args[ac++];
607: // Check if we can futher index the clauses
608: if (!argVars[2].isVariable()) {
609: clauses = engine.getRuleStore().codeFor(
610: new TriplePattern(argVars[0],
611: argVars[1], argVars[2]));
612: }
613: setupClauseCall(pc, ac, clauses, false);
614: setupTripleMatchCall(pc, ac);
615: continue main;
616:
617: case RuleClauseCode.CALL_TRIPLE_MATCH:
618: setupTripleMatchCall(pc, ac);
619: continue main;
620:
621: case RuleClauseCode.CALL_TABLED:
622: setupTabledCall(pc, ac);
623: continue main;
624:
625: case RuleClauseCode.CALL_WILD_TABLED:
626: Node predicate = deref(argVars[1]);
627: if (engine.getRuleStore().isTabled(predicate)) {
628: setupTabledCall(pc, ac);
629: } else {
630: // normal call set up
631: clauses = engine.getRuleStore().codeFor(
632: new TriplePattern(argVars[0],
633: predicate, argVars[2]));
634: if (clauses != null)
635: setupClauseCall(pc, ac, clauses, false);
636: setupTripleMatchCall(pc, ac);
637: }
638: continue main;
639:
640: case RuleClauseCode.PROCEED:
641: pc = envFrame.cpc;
642: ac = envFrame.cac;
643: if (traceOn)
644: logger.info("EXIT " + clause);
645: if (choice != null)
646: choice.noteSuccess();
647: if (recordDerivations
648: && envFrame.getRule() != null) {
649: if (envFrame instanceof EnvironmentFrameWithDerivation) {
650: EnvironmentFrameWithDerivation efd = (EnvironmentFrameWithDerivation) envFrame;
651: Triple result = efd.getResult();
652: List matches = efd.getMatchList();
653: BackwardRuleInfGraphI infGraph = engine
654: .getInfGraph();
655: RuleDerivation d = new RuleDerivation(
656: envFrame.getRule(), result,
657: matches, infGraph);
658: infGraph.logDerivation(result, d);
659:
660: // Also want to record this result in the calling frame
661: if (envFrame.link instanceof EnvironmentFrameWithDerivation) {
662: EnvironmentFrameWithDerivation pefd = (EnvironmentFrameWithDerivation) envFrame.link;
663: pefd.noteMatch(new TriplePattern(
664: result), pc);
665: }
666: }
667: }
668: envFrame = (EnvironmentFrame) envFrame.link;
669: if (envFrame != null) {
670: clause = envFrame.clause;
671: }
672: continue interpreter;
673:
674: case RuleClauseCode.CALL_BUILTIN:
675: Builtin builtin = (Builtin) args[ac++];
676: if (context == null) {
677: BBRuleContext bbcontext = new BBRuleContext(
678: engine.getInfGraph());
679: bbcontext.setEnv(new LPBindingEnvironment(
680: this ));
681: context = bbcontext;
682: }
683: context.setRule(clause.getRule());
684: if (!builtin.bodyCall(argVars, code[pc++],
685: context)) {
686: if (traceOn)
687: logger.info("FAIL " + clause
688: + ", due to "
689: + builtin.getName());
690: continue main;
691: }
692: break;
693:
694: default:
695: throw new ReasonerException(
696: "Internal error in backward rule system\nIllegal op code");
697: }
698: }
699: // End of innter code loop
700: }
701: // End of bytecode interpreter loop, gets to here if we complete an AND chain
702: return StateFlag.ACTIVE;
703: }
704: // Gets to here if we have run out of choice point frames
705: return StateFlag.FAIL;
706: }
707:
708: /**
709: * Tracing support - return a format set of triple queries/results.
710: */
711: private String getArgTrace() {
712: StringBuffer temp = new StringBuffer();
713: temp.append(PrintUtil.print(deref(argVars[0])));
714: temp.append(" ");
715: temp.append(PrintUtil.print(deref(argVars[1])));
716: temp.append(" ");
717: temp.append(PrintUtil.print(deref(argVars[2])));
718: return temp.toString();
719: }
720:
721: /**
722: * Set up a triple match choice point as part of a CALL.
723: */
724: private void setupTripleMatchCall(int pc, int ac) {
725: TripleMatchFrame tmFrame = new TripleMatchFrame(this );
726: tmFrame.setContinuation(pc, ac);
727: tmFrame.linkTo(cpFrame);
728: cpFrame = tmFrame;
729: }
730:
731: /**
732: * Set up a clause choice point as part of a CALL.
733: */
734: private void setupClauseCall(int pc, int ac, List clauses,
735: boolean isSingleton) {
736: ChoicePointFrame newChoiceFrame = new ChoicePointFrame(this ,
737: clauses, isSingleton);
738: newChoiceFrame.linkTo(cpFrame);
739: newChoiceFrame.setContinuation(pc, ac);
740: cpFrame = newChoiceFrame;
741: }
742:
743: /**
744: * Set up a tabled choice point as part of a CALL.
745: */
746: private void setupTabledCall(int pc, int ac) {
747: ConsumerChoicePointFrame ccp = new ConsumerChoicePointFrame(
748: this );
749: ccp.linkTo(cpFrame);
750: ccp.setContinuation(pc, ac);
751: cpFrame = ccp;
752: }
753:
754: /**
755: * Preserve the current interpter state in the consumer choice point at the top
756: * of the choice point tree.
757: */
758: public void preserveState(ConsumerChoicePointFrame ccp) {
759: ccp.preserveState(trail);
760: }
761:
762: /**
763: * Restore the interpter state according to the given consumer choice point.
764: */
765: public void restoreState(ConsumerChoicePointFrame ccp) {
766: cpFrame = ccp;
767: ccp.restoreState(this );
768: iContext = ccp.context;
769: }
770:
771: /**
772: * Unify two nodes. Current implementation does not support functors.
773: * @return true if the unifcation succeeds
774: */
775: public boolean unify(Node n1, Node n2) {
776: Node nv1 = n1;
777: if (nv1 instanceof Node_RuleVariable) {
778: nv1 = ((Node_RuleVariable) n1).deref();
779:
780: }
781: Node nv2 = n2;
782: if (nv2 instanceof Node_RuleVariable) {
783: nv2 = ((Node_RuleVariable) n2).deref();
784: }
785: if (nv1 instanceof Node_RuleVariable) {
786: bind(nv1, nv2);
787: return true;
788: } else if (nv2 instanceof Node_RuleVariable) {
789: bind(nv2, nv1);
790: return true;
791: } else {
792: return nv1.sameValueAs(nv2);
793: }
794:
795: }
796:
797: /**
798: * Bind a value to a variable, recording the binding in the trail.
799: * @param var the dereferenced variable to be bound
800: * @param val the value to bind to it
801: */
802: public void bind(Node var, Node val) {
803: ((Node_RuleVariable) var).simpleBind(val);
804: trail.add(var);
805: }
806:
807: /**
808: * Unwind the trail to given low water mark
809: */
810: public void unwindTrail(int mark) {
811: for (int i = trail.size() - 1; i >= mark; i--) {
812: Node_RuleVariable var = (Node_RuleVariable) trail.get(i);
813: var.unbind();
814: trail.remove(i);
815: }
816: }
817:
818: /**
819: * Derefernce a node, following any binding trail.
820: */
821: public static Node deref(Node node) {
822: if (node instanceof Node_RuleVariable) {
823: return ((Node_RuleVariable) node).deref();
824: } else {
825: return node;
826: }
827: }
828:
829: /**
830: * Check if a node values is now grounded
831: */
832: public static boolean isGrounded(Node node) {
833: return !(deref(node) instanceof Node_RuleVariable);
834: }
835:
836: /**
837: * Return a dereferenced copy of a triple.
838: */
839: public static Triple deref(TriplePattern t) {
840: if (t == null)
841: return null;
842: return new Triple(deref(t.getSubject()),
843: deref(t.getPredicate()), deref(t.getObject()));
844: }
845:
846: /**
847: * Derefernce a node which may be a functor node
848: */
849: public static Node derefPossFunctor(Node node) {
850: if (node instanceof Node_RuleVariable) {
851: Node dnode = ((Node_RuleVariable) node).deref();
852: if (dnode.isVariable()) {
853: // Problem with variable in return result "should never happen"
854: throw new ReasonerException(
855: "Internal error in LP reasoner: variable in triple result");
856: }
857: if (Functor.isFunctor(dnode)) {
858: Functor f = (Functor) dnode.getLiteralValue();
859: Node[] fargs = f.getArgs();
860: boolean needCopy = false;
861: for (int i = 0; i < fargs.length; i++) {
862: if (fargs[i].isVariable()) {
863: needCopy = true;
864: break;
865: }
866: }
867: if (needCopy) {
868: Node[] newArgs = new Node[fargs.length];
869: for (int i = 0; i < fargs.length; i++) {
870: newArgs[i] = deref(fargs[i]);
871: }
872: dnode = Functor.makeFunctorNode(f.getName(),
873: newArgs);
874: }
875: return dnode;
876: } else {
877: return dnode;
878: }
879: } else {
880: return node;
881: }
882: }
883:
884: /**
885: * Standardize a node by replacing instances of wildcard ANY by new distinct variables.
886: * This is used in constructing the arguments to a top level call from a goal pattern.
887: * @param node the node to be standardized
888: * @param mappedVars known mappings from input variables to local variables
889: */
890: private Node standardize(Node node, Map mappedVars) {
891: Node dnode = deref(node);
892: if (node == Node.ANY || node == Node_RuleVariable.WILD) {
893: return new Node_RuleVariable(null, 0);
894: } else if (dnode.isVariable()) {
895: Node mnode = (Node) mappedVars.get(dnode);
896: if (mnode == null) {
897: mnode = new Node_RuleVariable(null, 0);
898: mappedVars.put(dnode, mnode);
899: }
900: return mnode;
901: } else {
902: return dnode;
903: }
904: }
905:
906: }
907:
908: /*
909: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
910: All rights reserved.
911:
912: Redistribution and use in source and binary forms, with or without
913: modification, are permitted provided that the following conditions
914: are met:
915:
916: 1. Redistributions of source code must retain the above copyright
917: notice, this list of conditions and the following disclaimer.
918:
919: 2. Redistributions in binary form must reproduce the above copyright
920: notice, this list of conditions and the following disclaimer in the
921: documentation and/or other materials provided with the distribution.
922:
923: 3. The name of the author may not be used to endorse or promote products
924: derived from this software without specific prior written permission.
925:
926: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
927: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
928: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
929: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
930: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
931: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
932: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
933: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
934: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
935: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
936: */
|