KickJava   Java API By Example, From Geeks To Geeks.

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


1 /******************************************************************
2  * File: RuleCode.java
3  * Created by: Dave Reynolds
4  * Created on: 18-Jul-2003
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: RuleClauseCode.java,v 1.8 2005/02/21 12:17:59 andy_seaborne Exp $
9  *****************************************************************/

10 package com.hp.hpl.jena.reasoner.rulesys.impl;
11
12 import com.hp.hpl.jena.reasoner.TriplePattern;
13 import com.hp.hpl.jena.reasoner.rulesys.*;
14 import com.hp.hpl.jena.graph.*;
15
16 import java.io.PrintStream JavaDoc;
17 import java.util.*;
18
19 /**
20  * Object used to hold the compiled bytecode stream for a single rule clause.
21  * This uses a slightly WAM-like code stream but gluing of the clauses together
22  * into disjunctions is done in the interpreter loop so a complete predicate is
23  * represented as a list of RuleClauseCode objects.
24  *
25  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
26  * @version $Revision: 1.8 $ on $Date: 2005/02/21 12:17:59 $
27  */

28 public class RuleClauseCode {
29     
30 // =======================================================================
31
// Variables
32

33     /** The rule from which is code was derived */
34     protected Rule rule;
35     
36     /** The byte code sequence */
37     protected byte[] code;
38     
39     /** Any Object argements needed by the byte codes */
40     protected Object JavaDoc[] args;
41     
42     /** starting byte code offset for body terms */
43     protected int[] termStart;
44      
45 // =======================================================================
46
// Instruction set constants
47

48     /** fetch constant argument (const, Ai) */
49     public static final byte GET_CONSTANT = 0x1;
50     
51     /** fetch permanent variable argument, first occurance (Yi, Ai) */
52     public static final byte GET_VARIABLE = 0x2;
53     
54     /** fetch permanent variable argument, later occurance (Yi, Ai) */
55     public static final byte UNIFY_VARIABLE = 0x3;
56     
57     /** fetch temporary variable argument (Ti, Ai) */
58     public static final byte GET_TEMP = 0x4;
59     
60     /** fetch temporary variable argument, later occurance (Ti, Ai) */
61     public static final byte UNIFY_TEMP = 0x12;
62     
63     /** put constant value into call parameter (const, Ai) */
64     public static final byte PUT_CONSTANT = 0x5;
65     
66     /** put permanaent variable into call parameter, first occurance (Yi, Ai) */
67     public static final byte PUT_NEW_VARIABLE = 0x6;
68     
69     /** put permanaent variable into call parameter (Yi, Ai) */
70     public static final byte PUT_VARIABLE = 0x7;
71     
72     /** put a dereferenced permanent variable into call parameter ready for BUILTIN call (Yi, Ai) */
73     public static final byte PUT_DEREF_VARIABLE = 0x14;
74     
75     /** put temp variable into call parameter (Ti, Ai) */
76     public static final byte PUT_TEMP = 0x8;
77     
78     /** call a predicate code object (predicateCodeList) */
79     public static final byte CALL_PREDICATE = 0x9;
80     
81     /** deconstruct a functor argument (functor) */
82     public static final byte GET_FUNCTOR = 0xa;
83     
84     /** call a predicate code object with run time indexing (predicateCodeList) */
85     public static final byte CALL_PREDICATE_INDEX = 0x17;
86     
87     /** call a pure triple match (predicate) */
88     public static final byte CALL_TRIPLE_MATCH = 0x11;
89     
90     /** variant on CALL_PREDICATE using the last call optimization, only current used in chain rules */
91     public static final byte LAST_CALL_PREDICATE = 0x13;
92     
93     /** call a table code object () */
94     public static final byte CALL_TABLED = 0x18;
95     
96     /** call a table code object from a wildcard () */
97     public static final byte CALL_WILD_TABLED = 0x19;
98     
99     /** return from a call, proceeed along AND tree */
100     public static final byte PROCEED = 0xb;
101     
102     /** create a functor object from a rule template (templateFunctor) */
103     public static final byte MAKE_FUNCTOR = 0xc;
104     
105     /** call a built-in operation defined by a rule clause (clauseIndex( */
106     public static final byte CALL_BUILTIN = 0xd;
107     
108     /** reset a permanent variable to an unbound variable (Yi) */
109     public static final byte CLEAR_VARIABLE = 0xe;
110     
111     /** reset a temp variable to an unbound variable (Ti) */
112     public static final byte CLEAR_TEMP = 0xf;
113     
114     /** reset an argument to an unbound variable (Ai) */
115     public static final byte CLEAR_ARG = 0x10;
116     
117     /** Allocate a new environment frame */
118     public static final byte ALLOCATE = 0x16;
119     
120     /** Test if an argument is bound (Ai) */
121     public static final byte TEST_BOUND = 0x20;
122     
123     /** Test if an argument is unbound (Ai) */
124     public static final byte TEST_UNBOUND = 0x21;
125     
126     // current next = 0x22
127

128     /** The maximum number of permanent variables allowed in a single rule clause.
129      * Now only relevent for initial holding clause. */

130     public static final int MAX_PERMANENT_VARS = 15;
131     
132     /** The maximum number of argument variables allowed in a single goal
133      * Future refactorings will remove this restriction. */

134     public static final int MAX_ARGUMENT_VARS = 8;
135     
136     /** The maximum number of temporary variables allowed in a single rule clause. */
137     public static final int MAX_TEMPORARY_VARS = 8;
138     
139     /** Dummy code block which just returns */
140     public static RuleClauseCode returnCodeBlock;
141     
142     static {
143         returnCodeBlock = new RuleClauseCode(null);
144         returnCodeBlock.code = new byte[] {PROCEED};
145     }
146 // =======================================================================
147
// Methods and constructors
148

149     /**
150      * Constructor.
151      * @param rule the rule to be compiled
152      */

153     public RuleClauseCode(Rule rule) {
154         this.rule = rule;
155     }
156     
157     /**
158      * Return the byte code vector for this clause.
159      */

160     public byte[] getCode() {
161         return code;
162     }
163     
164     /**
165      * Return the argument vector associated with this clauses' byte codes.
166      */

167     public Object JavaDoc[] getArgs() {
168         return args;
169     }
170     
171     /**
172      * Return the rule from which this code block was compiled.
173      */

174     public Rule getRule() {
175         return rule;
176     }
177     
178     /**
179      * Compile the rule into byte code.
180      * @param ruleStore the store of LP rules through which calls to other predicates
181      * can be resolved.
182      */

183     public void compile(LPRuleStore ruleStore) {
184         CompileState state = new CompileState(rule);
185         
186         // Compile any early binding tests
187
int skip = 0; // state.emitBindingTests();
188

189         // Compile the head operations
190
ClauseEntry head = rule.getHeadElement(0);
191         if (!(head instanceof TriplePattern)) {
192             throw new LPRuleSyntaxException("Heads of backward rules must be triple patterns", rule);
193         }
194         state.emitHead((TriplePattern)head);
195         
196         // Compile the body operations
197
termStart = new int[rule.bodyLength()];
198         for (int i = skip; i < rule.bodyLength(); i++) {
199             termStart[i] = state.p;
200             ClauseEntry entry = rule.getBodyElement(i);
201             if (entry instanceof TriplePattern) {
202                 state.emitBody((TriplePattern)entry, ruleStore);
203             } else if (entry instanceof Functor) {
204                 state.emitBody((Functor)entry);
205             } else {
206                 throw new LPRuleSyntaxException("can't create new bRules in an bRule", rule);
207             }
208         }
209         
210         // Extract the final code
211
code = state.getFinalCode();
212         args = state.getFinalArgs();
213     }
214             
215     /**
216      * Translate a program counter offset to the index of the corresponding
217      * body term (or -1 if a head term or a dummy rule).
218      */

219     public int termIndex(int pc) {
220         if (rule == null) return -1;
221         int term = 0;
222         // Trivial linear search because this is only used for logging which is
223
// horribly expensive anyway.
224
while (term < rule.bodyLength()) {
225             if (pc <= termStart[term]) {
226                 return term - 1;
227             }
228             term++;
229         }
230         return term - 1;
231     }
232     
233     /**
234      * Debug helper - list the code to a stream
235      */

236     public void print(PrintStream JavaDoc out) {
237         if (code == null) {
238             out.println("Code not available");
239         } else {
240             int argi = 0;
241             for (int p = 0; p < code.length; ) {
242                 byte instruction = code[p++];
243                 switch (instruction) {
244                 case GET_CONSTANT:
245                     out.println("GET_CONSTANT " + args[argi++] + ", A" + code[p++]);
246                     break;
247                 case GET_VARIABLE:
248                     out.println("GET_VARIABLE " + "Y" + code[p++] + ", A" + code[p++]);
249                     break;
250                 case UNIFY_VARIABLE:
251                     out.println("UNIFY_VARIABLE " + "Y" + code[p++] + ", A" + code[p++]);
252                     break;
253                 case GET_TEMP:
254                     out.println("GET_TEMP " + "T" + code[p++] + ", A" + code[p++]);
255                     break;
256                 case UNIFY_TEMP:
257                     out.println("UNIFY_TEMP " + "T" + code[p++] + ", A" + code[p++]);
258                     break;
259                 case PUT_CONSTANT:
260                     out.println("PUT_CONSTANT " + args[argi++] + ", A" + code[p++]);
261                     break;
262                 case PUT_NEW_VARIABLE:
263                     out.println("PUT_NEW_VARIABLE " + "Y" + code[p++] + ", A" + code[p++]);
264                     break;
265                 case PUT_TEMP:
266                     out.println("PUT_TEMP " + "T" + code[p++] + ", A" + code[p++]);
267                     break;
268                 case PUT_VARIABLE:
269                     out.println("PUT_VARIABLE " + "Y" + code[p++] + ", A" + code[p++]);
270                     break;
271                 case PUT_DEREF_VARIABLE:
272                     out.println("PUT_DEREF_VARIABLE " + "Y" + code[p++] + ", A" + code[p++]);
273                     break;
274                 case TEST_BOUND:
275                     out.println("TEST_BOUND A" + code[p++]);
276                     break;
277                 case TEST_UNBOUND:
278                     out.println("TEST_UNBOUND A" + code[p++]);
279                     break;
280                 case CALL_PREDICATE:
281                     out.println("CALL_PREDICATE " + args[argi++]);
282                     break;
283                 case CALL_TABLED:
284                     out.println("CALL_TABLED ");
285                     break;
286                 case CALL_WILD_TABLED:
287                     out.println("CALL_WILD_TABLED ");
288                     break;
289                 case CALL_PREDICATE_INDEX:
290                     out.println("CALL_PREDICATE_INDEX " + args[argi++]);
291                     break;
292                 case LAST_CALL_PREDICATE:
293                     out.println("LAST_CALL_PREDICATE " + args[argi++]);
294                     break;
295                 case CALL_TRIPLE_MATCH:
296                         out.println("CALL_TRIPLE_MATCH");
297                         break;
298                 case PROCEED:
299                     out.println("PROCEED");
300                     break;
301                 case MAKE_FUNCTOR:
302                     out.println("MAKE_FUNCTOR " + args[argi++]);
303                     break;
304                 case GET_FUNCTOR:
305                     out.println("GET_FUNCTOR " + args[argi++]);
306                     break;
307                 case CALL_BUILTIN:
308                     out.println("CALL_BUILTIN " + ((Builtin)args[argi++]).getName() + "/" + code[p++]);
309                     break;
310                 case CLEAR_ARG:
311                     out.println("CLEAR_ARG " + "A" + code[p++]);
312                     break;
313                 case ALLOCATE:
314                     out.println("ALLOCATE + " + code[p++]);
315                     break;
316                 default:
317                     out.println("Unused code: " + instruction);
318                     break;
319                 }
320             }
321         }
322     }
323     
324     /**
325      * Print clause as rule for tracing.
326      */

327     public String JavaDoc toString() {
328         if (rule == null) {
329             return "[anon]";
330         } else {
331             return "[" + rule.toShortString() + "]";
332         }
333     }
334     
335     /**
336      * Inner class - compiler state.
337      */

338     static class CompileState {
339         
340         /** The temporary code vector during construction */
341         byte[] code;
342         
343         /** The temporary arg list during construction */
344         ArrayList args;
345         
346         /** The code pointer during construction */
347         int p;
348         
349         /** array of lists of variables in the rule clauses, array index is 0 for head, body starts at 1 */
350         private List[] termVarTable;
351         
352         /** Map from variables to the list of term positions in which it occurs */
353         private Map varOccurrence = new HashMap();
354         
355         /** List of all permanent variables */
356         private List permanentVars = new ArrayList();
357         
358         /** List of all temporary variables */
359         private List tempVars = new ArrayList();
360         
361         /** The total number of var occurrences */
362         int totalOccurrences = 0;
363         
364         /** the set of variables processed so far during the compile phase */
365         Set seen = new HashSet();
366          
367         /** The rule being parsed */
368         Rule rule;
369
370         
371         /**
372          * Constructor.
373          */

374         CompileState(Rule rule) {
375             classifyVariables(rule);
376             this.rule = rule;
377             // Create a scratch area for assembling the code, use a worst-case size estimate
378
code = new byte[10 + totalOccurrences + rule.bodyLength()*10];
379             args = new ArrayList();
380         }
381         
382         /**
383          * Emit the code for any bound/unbound tests add start of body
384          * and return the number of body clauses dealt with.
385          */

386         int emitBindingTests() {
387             int i = 0;
388             while (i < rule.bodyLength()) {
389                 ClauseEntry term = rule.getBodyElement(i);
390                 if (term instanceof Functor) {
391                     Functor f = (Functor)term;
392                     if (f.getArgLength() != 1) break;
393                     int ai = aIndex(f.getArgs()[0]);
394                     if (ai >= 0) {
395                         if (f.getName().equals("bound")) {
396                             code[p++] = TEST_BOUND;
397                             code[p++] = (byte)ai;
398                         } else if (f.getName().equals("unbound")) {
399                             code[p++] = TEST_UNBOUND;
400                             code[p++] = (byte)ai;
401                         } else {
402                             break;
403                         }
404                     }
405                 } else {
406                     break;
407                 }
408                 i++;
409             }
410             return i;
411         }
412         
413         /**
414          * Return the argument index of the given variable.
415          */

416         int aIndex(Node n) {
417             TriplePattern tp = (TriplePattern)rule.getHeadElement(0);
418             if (tp.getSubject() == n) {
419                 return 0;
420             } else if (tp.getPredicate() == n) {
421                 return 1;
422             } else if (tp.getObject() == n) {
423                 return 2;
424             } else {
425                 return -1;
426             }
427         }
428         
429         /**
430          * emit the code for the head clause
431          */

432         void emitHead(TriplePattern head) {
433             if (permanentVars.size() > 0) {
434                 code[p++] = ALLOCATE;
435                 code[p++] = (byte)permanentVars.size();
436             }
437             emitHeadGet(head.getSubject(), 0);
438             emitHeadGet(head.getPredicate(), 1);
439             emitHeadGet(head.getObject(), 2);
440         }
441         
442         /**
443          * Emit a single head get operation
444          * @param node the node to emit
445          * @param argi the argument register to address
446          */

447         void emitHeadGet(Node node, int argi) {
448             if (node instanceof Node_RuleVariable) {
449                 Node_RuleVariable var = (Node_RuleVariable)node;
450                 if (isDummy(var)) {
451                     // Node code required, var not used
452
return;
453                 }
454                 if (isTemp(var)) {
455                     List occurrences = (List)varOccurrence.get(var);
456                     if (occurrences.size() == 2 &&
457                         ((TermIndex)occurrences.get(0)).index <= 2 &&
458                         ((TermIndex)occurrences.get(0)).index ==((TermIndex)occurrences.get(1)).index) {
459                             // No movement code required, var in right place
460
} else {
461                         code[p++] = seen.add(var) ? GET_TEMP : UNIFY_TEMP;
462                         code[p++] = (byte)tempVars.indexOf(var);
463                         code[p++] = (byte)argi;
464                     }
465                 } else {
466                     code[p++] = seen.add(var) ? GET_VARIABLE : UNIFY_VARIABLE;
467                     code[p++] = (byte)permanentVars.indexOf(var);
468                     code[p++] = (byte)argi;
469                 }
470             } else if (Functor.isFunctor(node)) {
471                 Functor f = (Functor)node.getLiteral().getValue();
472                 code[p++] = GET_FUNCTOR;
473                 args.add(f);
474                 Node[] fargs = f.getArgs();
475                 for (int i = 0; i < fargs.length; i++) {
476                     emitHeadGet(fargs[i], i+3);
477                 }
478             } else {
479                 code[p++] = GET_CONSTANT;
480                 code[p++] = (byte)argi;
481                 args.add(node);
482             }
483         }
484         
485         /**
486          * Emit code for a body clause.
487          * @param goal the triple pattern to be called
488          */

489         void emitBody(TriplePattern goal, LPRuleStore store) {
490             int argi = 0;
491             emitBodyPut(goal.getSubject(), 0, false);
492             emitBodyPut(goal.getPredicate(), 1, false);
493             emitBodyPut(goal.getObject(), 2, false);
494             List predicateCode = store.codeFor(goal);
495             if (predicateCode == null || predicateCode.size() == 0) {
496                 code[p++] = CALL_TRIPLE_MATCH;
497             } else {
498 // code[p++] = CALL_TABLED;
499
if (goal.getPredicate().isVariable()) {
500                     // Experimental. Force tabling of any wildcard predicate calls
501
code[p++] = CALL_TABLED;
502                 } else if (store.isTabled(goal)) {
503 // if (store.isTabled(goal)) {
504
code[p++] = goal.getPredicate().isVariable() ? CALL_WILD_TABLED : CALL_TABLED;
505                 } else {
506                     if (permanentVars.size() == 0) {
507                         code[p++] = LAST_CALL_PREDICATE;
508                     } else {
509                         // Normal call, but can it be indexed further?
510
if (store.isIndexedPredicate(goal.getPredicate()) && goal.getObject().isVariable()) {
511                             code[p++] = CALL_PREDICATE_INDEX;
512                         } else {
513                             code[p++] = CALL_PREDICATE;
514                         }
515                     }
516                     args.add(predicateCode);
517                 }
518             }
519         }
520         
521         /**
522          * Emit code a single body put operation.
523          * @param node the node to emit
524          * @param argi the argument register to use
525          * @param deref if true force a dereference of the variable binding at this point for
526          * use in calling builtins
527          */

528         void emitBodyPut(Node node, int argi, boolean deref) {
529             if (argi >= MAX_ARGUMENT_VARS) {
530                 throw new LPRuleSyntaxException("Rule too complex for current implementation\n"
531                             + "Rule clauses are limited to " + MAX_ARGUMENT_VARS + " argument variables\n", rule);
532
533             }
534             if (node instanceof Node_RuleVariable) {
535                 Node_RuleVariable var = (Node_RuleVariable)node;
536                 if (isDummy(var)) {
537                     code[p++] = CLEAR_ARG;
538                     code[p++] = (byte)argi;
539                     return;
540                 }
541                 if (isTemp(var)) {
542                     List occurrences = (List)varOccurrence.get(var);
543                     if (occurrences.size() == 2 &&
544                         ((TermIndex)occurrences.get(0)).index ==((TermIndex)occurrences.get(1)).index) {
545                             // No movement code required, var in right place
546
} else {
547                         code[p++] = PUT_TEMP;
548                         code[p++] = (byte)tempVars.indexOf(var);
549                         code[p++] = (byte)argi;
550                     }
551                 } else {
552                     if (! seen.add(var)) {
553                         code[p++] = (deref ? PUT_DEREF_VARIABLE : PUT_VARIABLE);
554                     } else {
555                         code[p++] = PUT_NEW_VARIABLE;
556                     }
557                     code[p++] = (byte)permanentVars.indexOf(var);
558                     code[p++] = (byte)argi;
559                 }
560             } else if (Functor.isFunctor(node)) {
561                 Functor f = (Functor)node.getLiteral().getValue();
562                 Node[] fargs = f.getArgs();
563                 for (int i = 0; i < fargs.length; i++) {
564                     emitBodyPut(fargs[i], i+3, deref);
565                 }
566                 code[p++] = MAKE_FUNCTOR;
567                 args.add(f);
568             } else {
569                 code[p++] = PUT_CONSTANT;
570                 code[p++] = (byte)argi;
571                 args.add(node);
572             }
573         }
574         
575         /**
576          * Emit code for a call to a built-in predicate (functor).
577          * @param functor the built-in to be invoked.
578          */

579         void emitBody(Functor functor) {
580             Node[] fargs = functor.getArgs();
581             Builtin builtin = functor.getImplementor();
582             if (builtin == null) {
583                 throw new LPRuleSyntaxException("Unknown builtin operation " + functor.getName(), rule);
584             }
585             if (builtin.getArgLength() != 0 && builtin.getArgLength() != fargs.length) {
586                 throw new LPRuleSyntaxException("Wrong number of arguments to functor " + functor.getName()
587                                                   + " expected " + functor.getArgLength(), rule);
588             }
589             for (int i = 0; i < fargs.length; i++) {
590                 Node node = fargs[i];
591                 // We optionally force an eager dereference of variables here.
592
// We used to force this but the current builtin implementations
593
// now robust against it (the do a deref themselves anyway).
594
emitBodyPut(node, i, true);
595             }
596             code[p++] = CALL_BUILTIN;
597             code[p++] = (byte)fargs.length;
598             args.add(builtin);
599         }
600          
601         /**
602          * Complete the byte stream with a PROCEED and return the packed version of the code.
603          * @return the byte code array
604          */

605         byte[] getFinalCode() {
606             code[p++] = PROCEED;
607             byte[] finalCode = new byte[p];
608             System.arraycopy(code, 0, finalCode, 0, p);
609             return finalCode;
610         }
611         
612         /**
613          * Fetch the packed array of argument objects for the byte code.
614          * @return arg array
615          */

616         Object JavaDoc[] getFinalArgs() {
617             return args.toArray();
618         }
619         
620         /**
621          * Classifies the variables now and side effects the
622          * index number of the variables so they lie in two sequences - temp
623          * and permanent separately.
624          */

625         void classifyVariables(Rule rule) {
626             // Build index data structure into var use in each term in the rule
627
termVarTable = new List[rule.bodyLength() + 1];
628             termVarTable[0] = termVars(rule.getHeadElement(0));
629             totalOccurrences += termVarTable[0].size();
630             for (int i = 0; i < rule.bodyLength(); i++) {
631                 termVarTable[i+1] = termVars(rule.getBodyElement(i));
632                 totalOccurrences += termVarTable[i+1].size();
633             }
634             
635             // Build the inverted data structure
636
for (int i = 0; i < rule.bodyLength() + 1; i++ ) {
637                 List varEnts = termVarTable[i];
638                 for (int j = 0; j < varEnts.size(); j++) {
639                     Node n = (Node)varEnts.get(j);
640                     if (n.isVariable()) {
641                         Node_RuleVariable var = (Node_RuleVariable)n;
642                         List occurrences = (List)varOccurrence.get(var);
643                         if (occurrences == null) {
644                             occurrences = new ArrayList();
645                             varOccurrence.put(var, occurrences);
646                         }
647                         occurrences.add(new TermIndex(var, i, j));
648                     }
649                 }
650             }
651             
652             // Classify vars as permanent unless they are just dummies (only used once at all)
653
// or only used head+first body goal (but not if used in a builtin)
654
for (Iterator enti = varOccurrence.values().iterator(); enti.hasNext(); ) {
655                 List occurrences = (List)enti.next();
656                 Node_RuleVariable var = null;
657                 boolean inFirst = false;
658                 boolean inLaterBody = false;
659                 boolean inBuiltin = false;
660                 for (Iterator oi = occurrences.iterator(); oi.hasNext(); ) {
661                     TermIndex occurence = (TermIndex)oi.next();
662                     var = occurence.var;
663                     int termNumber = occurence.termNumber;
664                     if (termNumber == 0) {
665                         inFirst = true;
666                     } else if (termNumber > 1) {
667                         inLaterBody = true;
668                     }
669                     if (termNumber > 0 && rule.getBodyElement(termNumber-1) instanceof Functor) {
670                         inBuiltin = true;
671                     }
672                 }
673                 // Don't think we need to protected builtin's any more, so ignore that test
674
// if (inBuiltin) {
675
// permanentVars.add(var);
676
// } else {
677
if (!isDummy(var)) {
678                         if (inLaterBody || !inFirst) {
679                             permanentVars.add(var);
680                         } else {
681                             tempVars.add(var);
682                         }
683                     }
684 // }
685

686             }
687             
688             if (permanentVars.size() > MAX_PERMANENT_VARS) {
689                 throw new LPRuleSyntaxException("Rule too complex for current implementation\n"
690                             + "Rule clauses are limited to " + MAX_PERMANENT_VARS + " permanent variables\n", rule);
691             }
692             
693             if (tempVars.size() > MAX_TEMPORARY_VARS) {
694                 throw new LPRuleSyntaxException("Rule too complex for current implementation\n"
695                             + "Rule clauses are limited to " + MAX_TEMPORARY_VARS + " temporary variables\n", rule);
696             }
697             
698             // Builtins in the forward system use the var index to modify variable bindings.
699
// At one time I though the LP system might need to emulate this but (a) it doesn't and
700
// (b) renumber vars to make that possible wreaks rule equality which wreaks add/remove in
701
// hybrid rule sets. This code left in but commented out as a reminder to not go down
702
// that path again.
703

704             // Renumber the vars
705
// for (int i = 0; i < permanentVars.size(); i++ ) {
706
// Node_RuleVariable var = (Node_RuleVariable)permanentVars.get(i);
707
// var.setIndex(i);
708
// }
709
// for (int i = 0; i < tempVars.size(); i++ ) {
710
// Node_RuleVariable var = (Node_RuleVariable)tempVars.get(i);
711
// var.setIndex(i);
712
// }
713

714         }
715        
716         /** Return true if the given rule variable is a temp */
717         boolean isTemp(Node_RuleVariable var) {
718             return !isDummy(var) && !permanentVars.contains(var);
719         }
720         
721         /** Return true if the given rule variable is a dummy */
722         boolean isDummy(Node_RuleVariable var) {
723             List occurances = (List)varOccurrence.get(var);
724             if (occurances == null || occurances.size() <= 1) return true;
725             return false;
726         }
727                 
728         /** Return an list of variables or nodes in a ClauseEntry, in flattened order */
729         private List termVars(ClauseEntry term) {
730             List result = new ArrayList();
731             if (term instanceof TriplePattern) {
732                 TriplePattern goal = (TriplePattern)term;
733                 result.add(goal.getSubject());
734                 result.add(goal.getPredicate());
735                 Node obj = goal.getObject();
736                 if (Functor.isFunctor(obj)) {
737                     result.add(obj);
738                     result.addAll(termVars((Functor)obj.getLiteral().getValue()));
739                 } else {
740                     result.add(obj);
741                 }
742             } else if (term instanceof Functor) {
743                 Node[] args = (Node[]) ((Functor)term).getArgs();
744                 for (int i = 0; i < args.length; i++) {
745                     result.add(args[i]);
746                 }
747             }
748             return result;
749         }
750     }
751                 
752     
753     /**
754      * Inner class used to represent the occurance of a variable in a term.
755      * Not an abstract data type, just a structure directly accessed.
756      */

757     static class TermIndex {
758         /** The term number in the rule - 0 for head, body starting from 1 */
759         int termNumber;
760         
761         /** The variable position within the term */
762         int index;
763         
764         /** The variable being indexed */
765         Node_RuleVariable var;
766         
767         /** Constructor */
768         TermIndex(Node_RuleVariable var, int termNumber, int index) {
769             this.var = var;
770             this.termNumber = termNumber;
771             this.index = index;
772         }
773     }
774       
775     /**
776      * Debug support - not unit testing.
777      */

778     public static void main(String JavaDoc[] args) {
779         try {
780             LPRuleStore store = new LPRuleStore();
781             String JavaDoc test1 = "(?a p ?y) <- (?a p2 ?z).";
782             String JavaDoc test2 = "(?a p ?y) <- (?a q2 ?z) (?z q2 ?w).";
783             String JavaDoc test3 = "(?a p ?a) <- (?z r2 ?w) (?z r2 ?w).";
784             String JavaDoc test4 = "(?a p ?a) <- (?z r2 ?w) (?a r2 ?w).";
785             String JavaDoc test5 = "(?a p ?y) <- (?a p ?z), (?z p ?y).";
786             String JavaDoc test6 = "(?x p C3) <- (C1 r ?x).";
787             String JavaDoc test7 = "(?x p ?y) <- (?x r ?y) (?x q ?y).";
788             String JavaDoc test8 = "(?x p ?y) <- (?x p ?z) addOne(?z, ?y).";
789             String JavaDoc test9 = "(?x p ?y) <- (?x p ?z) sum(?z, 2, ?y).";
790             String JavaDoc test10 = "(?x p ?y) <- (?x p ?v), sum(?v 2 ?y).";
791             String JavaDoc test11 = "(b p ?y) <- (a ?y ?v).";
792             String JavaDoc test12 = "(?x p ?y) <- (?x p foo(?z, ?y)).";
793             String JavaDoc test13 = "(?x p foo(?y,?z)) <- (?x q ?y), (?x q ?z).";
794             String JavaDoc test14 = "(?x p ?z) <- (?x e ?z), (?z q ?z).";
795             String JavaDoc test15 = "(?x p ?y ) <- bound(?x), (?x p ?y).";
796             String JavaDoc test16 = "(a p b ) <- unbound(?x).";
797             String JavaDoc test17 = "(?a p ?a) <- (?a q class).";
798             String JavaDoc test18 = "(?a p ?a) <- (?a s ?a).";
799             String JavaDoc test19 = "(?X p ?T) <- (?X rdf:type c), noValue(?X, p), makeInstance(?X, p, ?T).";
800             String JavaDoc test20 = "(a p b ) <- unbound(?x).";
801             String JavaDoc testLong = "(?P p ?C) <- (?P q ?D), (?D r xsd(?B, ?S1, ?L1)),(?P p ?E), notEqual(?D, ?E) " +
802                     "(?E e xsd(?B, ?S2, ?L2)),min(?S1, ?S2, ?S3),min(?L1, ?L2, ?L3), (?C r xsd(?B, ?S3, ?L3)).";
803             String JavaDoc test21 = "(?a p ?y) <- (?x s ?y) (?a p ?x).";
804             String JavaDoc test22 = "(?C p ?D) <- (?C rb:xsdBase ?BC), (?D rb:xsdBase ?BD), notEqual(?BC, ?BD).";
805             store.addRule(Rule.parseRule(test22));
806             System.out.println("Code for p:");
807             List codeList = store.codeFor(Node.createURI("p"));
808             RuleClauseCode code = (RuleClauseCode)codeList.get(0);
809             code.print(System.out);
810         } catch (Exception JavaDoc e) {
811             System.out.println("Problem: " + e);
812             e.printStackTrace();
813         }
814     }
815 }
816
817
818 /*
819     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
820     All rights reserved.
821
822     Redistribution and use in source and binary forms, with or without
823     modification, are permitted provided that the following conditions
824     are met:
825
826     1. Redistributions of source code must retain the above copyright
827        notice, this list of conditions and the following disclaimer.
828
829     2. Redistributions in binary form must reproduce the above copyright
830        notice, this list of conditions and the following disclaimer in the
831        documentation and/or other materials provided with the distribution.
832
833     3. The name of the author may not be used to endorse or promote products
834        derived from this software without specific prior written permission.
835
836     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
837     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
838     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
839     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
840     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
841     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
842     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
843     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
844     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
845     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
846 */
Popular Tags