LPInterpreter


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