001: /******************************************************************
002: * File: RuleCode.java
003: * Created by: Dave Reynolds
004: * Created on: 18-Jul-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: RuleClauseCode.java,v 1.12 2008/01/02 12:06:16 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import com.hp.hpl.jena.reasoner.TriplePattern;
012: import com.hp.hpl.jena.reasoner.rulesys.*;
013: import com.hp.hpl.jena.graph.*;
014:
015: import java.io.PrintStream;
016: import java.util.*;
017:
018: /**
019: * Object used to hold the compiled bytecode stream for a single rule clause.
020: * This uses a slightly WAM-like code stream but gluing of the clauses together
021: * into disjunctions is done in the interpreter loop so a complete predicate is
022: * represented as a list of RuleClauseCode objects.
023: *
024: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
025: * @version $Revision: 1.12 $ on $Date: 2008/01/02 12:06:16 $
026: */
027: public class RuleClauseCode {
028:
029: // =======================================================================
030: // Variables
031:
032: /** The rule from which is code was derived */
033: protected Rule rule;
034:
035: /** The byte code sequence */
036: protected byte[] code;
037:
038: /** Any Object argements needed by the byte codes */
039: protected Object[] args;
040:
041: /** starting byte code offset for body terms */
042: protected int[] termStart;
043:
044: // =======================================================================
045: // Instruction set constants
046:
047: /** fetch constant argument (const, Ai) */
048: public static final byte GET_CONSTANT = 0x1;
049:
050: /** fetch permanent variable argument, first occurance (Yi, Ai) */
051: public static final byte GET_VARIABLE = 0x2;
052:
053: /** fetch permanent variable argument, later occurance (Yi, Ai) */
054: public static final byte UNIFY_VARIABLE = 0x3;
055:
056: /** fetch temporary variable argument (Ti, Ai) */
057: public static final byte GET_TEMP = 0x4;
058:
059: /** fetch temporary variable argument, later occurance (Ti, Ai) */
060: public static final byte UNIFY_TEMP = 0x12;
061:
062: /** put constant value into call parameter (const, Ai) */
063: public static final byte PUT_CONSTANT = 0x5;
064:
065: /** put permanaent variable into call parameter, first occurance (Yi, Ai) */
066: public static final byte PUT_NEW_VARIABLE = 0x6;
067:
068: /** put permanaent variable into call parameter (Yi, Ai) */
069: public static final byte PUT_VARIABLE = 0x7;
070:
071: /** put a dereferenced permanent variable into call parameter ready for BUILTIN call (Yi, Ai) */
072: public static final byte PUT_DEREF_VARIABLE = 0x14;
073:
074: /** put temp variable into call parameter (Ti, Ai) */
075: public static final byte PUT_TEMP = 0x8;
076:
077: /** call a predicate code object (predicateCodeList) */
078: public static final byte CALL_PREDICATE = 0x9;
079:
080: /** deconstruct a functor argument (functor) */
081: public static final byte GET_FUNCTOR = 0xa;
082:
083: /** call a predicate code object with run time indexing (predicateCodeList) */
084: public static final byte CALL_PREDICATE_INDEX = 0x17;
085:
086: /** call a pure triple match (predicate) */
087: public static final byte CALL_TRIPLE_MATCH = 0x11;
088:
089: /** variant on CALL_PREDICATE using the last call optimization, only current used in chain rules */
090: public static final byte LAST_CALL_PREDICATE = 0x13;
091:
092: /** call a table code object () */
093: public static final byte CALL_TABLED = 0x18;
094:
095: /** call a table code object from a wildcard () */
096: public static final byte CALL_WILD_TABLED = 0x19;
097:
098: /** return from a call, proceeed along AND tree */
099: public static final byte PROCEED = 0xb;
100:
101: /** create a functor object from a rule template (templateFunctor) */
102: public static final byte MAKE_FUNCTOR = 0xc;
103:
104: /** call a built-in operation defined by a rule clause (clauseIndex( */
105: public static final byte CALL_BUILTIN = 0xd;
106:
107: /** reset a permanent variable to an unbound variable (Yi) */
108: public static final byte CLEAR_VARIABLE = 0xe;
109:
110: /** reset a temp variable to an unbound variable (Ti) */
111: public static final byte CLEAR_TEMP = 0xf;
112:
113: /** reset an argument to an unbound variable (Ai) */
114: public static final byte CLEAR_ARG = 0x10;
115:
116: /** Allocate a new environment frame */
117: public static final byte ALLOCATE = 0x16;
118:
119: /** Test if an argument is bound (Ai) */
120: public static final byte TEST_BOUND = 0x20;
121:
122: /** Test if an argument is unbound (Ai) */
123: public static final byte TEST_UNBOUND = 0x21;
124:
125: // current next = 0x22
126:
127: /** The maximum number of permanent variables allowed in a single rule clause.
128: * Now only relevent for initial holding clause. */
129: public static final int MAX_PERMANENT_VARS = 15;
130:
131: /** The maximum number of argument variables allowed in a single goal
132: * Future refactorings will remove this restriction. */
133: public static final int MAX_ARGUMENT_VARS = 8;
134:
135: /** The maximum number of temporary variables allowed in a single rule clause. */
136: public static final int MAX_TEMPORARY_VARS = 8;
137:
138: /** Dummy code block which just returns */
139: public static RuleClauseCode returnCodeBlock;
140:
141: static {
142: returnCodeBlock = new RuleClauseCode(null);
143: returnCodeBlock.code = new byte[] { PROCEED };
144: }
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[] 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(
193: "Heads of backward rules must be triple patterns",
194: rule);
195: }
196: state.emitHead((TriplePattern) head);
197:
198: // Compile the body operations
199: termStart = new int[rule.bodyLength()];
200: for (int i = skip; i < rule.bodyLength(); i++) {
201: termStart[i] = state.p;
202: ClauseEntry entry = rule.getBodyElement(i);
203: if (entry instanceof TriplePattern) {
204: state.emitBody((TriplePattern) entry, ruleStore);
205: } else if (entry instanceof Functor) {
206: state.emitBody((Functor) entry);
207: } else {
208: throw new LPRuleSyntaxException(
209: "can't create new bRules in an bRule", rule);
210: }
211: }
212:
213: // Extract the final code
214: code = state.getFinalCode();
215: args = state.getFinalArgs();
216: }
217:
218: /**
219: * Translate a program counter offset to the index of the corresponding
220: * body term (or -1 if a head term or a dummy rule).
221: */
222: public int termIndex(int pc) {
223: if (rule == null)
224: return -1;
225: int term = 0;
226: // Trivial linear search because this is only used for logging which is
227: // horribly expensive anyway.
228: while (term < rule.bodyLength()) {
229: if (pc <= termStart[term]) {
230: return term - 1;
231: }
232: term++;
233: }
234: return term - 1;
235: }
236:
237: /**
238: * Debug helper - list the code to a stream
239: */
240: public void print(PrintStream out) {
241: if (code == null) {
242: out.println("Code not available");
243: } else {
244: int argi = 0;
245: for (int p = 0; p < code.length;) {
246: byte instruction = code[p++];
247: switch (instruction) {
248: case GET_CONSTANT:
249: out.println("GET_CONSTANT " + args[argi++] + ", A"
250: + code[p++]);
251: break;
252: case GET_VARIABLE:
253: out.println("GET_VARIABLE " + "Y" + code[p++]
254: + ", A" + code[p++]);
255: break;
256: case UNIFY_VARIABLE:
257: out.println("UNIFY_VARIABLE " + "Y" + code[p++]
258: + ", A" + code[p++]);
259: break;
260: case GET_TEMP:
261: out.println("GET_TEMP " + "T" + code[p++] + ", A"
262: + code[p++]);
263: break;
264: case UNIFY_TEMP:
265: out.println("UNIFY_TEMP " + "T" + code[p++] + ", A"
266: + code[p++]);
267: break;
268: case PUT_CONSTANT:
269: out.println("PUT_CONSTANT " + args[argi++] + ", A"
270: + code[p++]);
271: break;
272: case PUT_NEW_VARIABLE:
273: out.println("PUT_NEW_VARIABLE " + "Y" + code[p++]
274: + ", A" + code[p++]);
275: break;
276: case PUT_TEMP:
277: out.println("PUT_TEMP " + "T" + code[p++] + ", A"
278: + code[p++]);
279: break;
280: case PUT_VARIABLE:
281: out.println("PUT_VARIABLE " + "Y" + code[p++]
282: + ", A" + code[p++]);
283: break;
284: case PUT_DEREF_VARIABLE:
285: out.println("PUT_DEREF_VARIABLE " + "Y" + code[p++]
286: + ", A" + code[p++]);
287: break;
288: case TEST_BOUND:
289: out.println("TEST_BOUND A" + code[p++]);
290: break;
291: case TEST_UNBOUND:
292: out.println("TEST_UNBOUND A" + code[p++]);
293: break;
294: case CALL_PREDICATE:
295: out.println("CALL_PREDICATE " + args[argi++]);
296: break;
297: case CALL_TABLED:
298: out.println("CALL_TABLED ");
299: break;
300: case CALL_WILD_TABLED:
301: out.println("CALL_WILD_TABLED ");
302: break;
303: case CALL_PREDICATE_INDEX:
304: out.println("CALL_PREDICATE_INDEX " + args[argi++]);
305: break;
306: case LAST_CALL_PREDICATE:
307: out.println("LAST_CALL_PREDICATE " + args[argi++]);
308: break;
309: case CALL_TRIPLE_MATCH:
310: out.println("CALL_TRIPLE_MATCH");
311: break;
312: case PROCEED:
313: out.println("PROCEED");
314: break;
315: case MAKE_FUNCTOR:
316: out.println("MAKE_FUNCTOR " + args[argi++]);
317: break;
318: case GET_FUNCTOR:
319: out.println("GET_FUNCTOR " + args[argi++]);
320: break;
321: case CALL_BUILTIN:
322: out.println("CALL_BUILTIN "
323: + ((Builtin) args[argi++]).getName() + "/"
324: + code[p++]);
325: break;
326: case CLEAR_ARG:
327: out.println("CLEAR_ARG " + "A" + code[p++]);
328: break;
329: case ALLOCATE:
330: out.println("ALLOCATE + " + code[p++]);
331: break;
332: default:
333: out.println("Unused code: " + instruction);
334: break;
335: }
336: }
337: }
338: }
339:
340: /**
341: * Print clause as rule for tracing.
342: */
343: public String toString() {
344: if (rule == null) {
345: return "[anon]";
346: } else {
347: return "[" + rule.toShortString() + "]";
348: }
349: }
350:
351: /**
352: * Inner class - compiler state.
353: */
354: static class CompileState {
355:
356: /** The temporary code vector during construction */
357: byte[] code;
358:
359: /** The temporary arg list during construction */
360: ArrayList args;
361:
362: /** The code pointer during construction */
363: int p;
364:
365: /** array of lists of variables in the rule clauses, array index is 0 for head, body starts at 1 */
366: private List[] termVarTable;
367:
368: /** Map from variables to the list of term positions in which it occurs */
369: private Map varOccurrence = new HashMap();
370:
371: /** List of all permanent variables */
372: private List permanentVars = new ArrayList();
373:
374: /** List of all temporary variables */
375: private List tempVars = new ArrayList();
376:
377: /** The total number of var occurrences */
378: int totalOccurrences = 0;
379:
380: /** the set of variables processed so far during the compile phase */
381: Set seen = new HashSet();
382:
383: /** The rule being parsed */
384: Rule rule;
385:
386: /**
387: * Constructor.
388: */
389: CompileState(Rule rule) {
390: classifyVariables(rule);
391: this .rule = rule;
392: // Create a scratch area for assembling the code, use a worst-case size estimate
393: code = new byte[10 + totalOccurrences + rule.bodyLength()
394: * 10];
395: args = new ArrayList();
396: }
397:
398: /**
399: * Emit the code for any bound/unbound tests add start of body
400: * and return the number of body clauses dealt with.
401: */
402: int emitBindingTests() {
403: int i = 0;
404: while (i < rule.bodyLength()) {
405: ClauseEntry term = rule.getBodyElement(i);
406: if (term instanceof Functor) {
407: Functor f = (Functor) term;
408: if (f.getArgLength() != 1)
409: break;
410: int ai = aIndex(f.getArgs()[0]);
411: if (ai >= 0) {
412: if (f.getName().equals("bound")) {
413: code[p++] = TEST_BOUND;
414: code[p++] = (byte) ai;
415: } else if (f.getName().equals("unbound")) {
416: code[p++] = TEST_UNBOUND;
417: code[p++] = (byte) ai;
418: } else {
419: break;
420: }
421: }
422: } else {
423: break;
424: }
425: i++;
426: }
427: return i;
428: }
429:
430: /**
431: * Return the argument index of the given variable.
432: */
433: int aIndex(Node n) {
434: TriplePattern tp = (TriplePattern) rule.getHeadElement(0);
435: if (tp.getSubject() == n) {
436: return 0;
437: } else if (tp.getPredicate() == n) {
438: return 1;
439: } else if (tp.getObject() == n) {
440: return 2;
441: } else {
442: return -1;
443: }
444: }
445:
446: /**
447: * emit the code for the head clause
448: */
449: void emitHead(TriplePattern head) {
450: if (permanentVars.size() > 0) {
451: code[p++] = ALLOCATE;
452: code[p++] = (byte) permanentVars.size();
453: }
454: emitHeadGet(head.getSubject(), 0);
455: emitHeadGet(head.getPredicate(), 1);
456: emitHeadGet(head.getObject(), 2);
457: }
458:
459: /**
460: * Emit a single head get operation
461: * @param node the node to emit
462: * @param argi the argument register to address
463: */
464: void emitHeadGet(Node node, int argi) {
465: if (node instanceof Node_RuleVariable) {
466: Node_RuleVariable var = (Node_RuleVariable) node;
467: if (isDummy(var)) {
468: // Node code required, var not used
469: return;
470: }
471: if (isTemp(var)) {
472: List occurrences = (List) varOccurrence.get(var);
473: if (occurrences.size() == 2
474: && ((TermIndex) occurrences.get(0)).index <= 2
475: && ((TermIndex) occurrences.get(0)).index == ((TermIndex) occurrences
476: .get(1)).index) {
477: // No movement code required, var in right place
478: } else {
479: code[p++] = seen.add(var) ? GET_TEMP
480: : UNIFY_TEMP;
481: code[p++] = (byte) tempVars.indexOf(var);
482: code[p++] = (byte) argi;
483: }
484: } else {
485: code[p++] = seen.add(var) ? GET_VARIABLE
486: : UNIFY_VARIABLE;
487: code[p++] = (byte) permanentVars.indexOf(var);
488: code[p++] = (byte) argi;
489: }
490: } else if (Functor.isFunctor(node)) {
491: Functor f = (Functor) node.getLiteralValue();
492: code[p++] = GET_FUNCTOR;
493: args.add(f);
494: Node[] fargs = f.getArgs();
495: for (int i = 0; i < fargs.length; i++) {
496: emitHeadGet(fargs[i], i + 3);
497: }
498: } else {
499: code[p++] = GET_CONSTANT;
500: code[p++] = (byte) argi;
501: args.add(node);
502: }
503: }
504:
505: /**
506: * Emit code for a body clause.
507: * @param goal the triple pattern to be called
508: */
509: void emitBody(TriplePattern goal, LPRuleStore store) {
510: int argi = 0;
511: emitBodyPut(goal.getSubject(), 0, false);
512: emitBodyPut(goal.getPredicate(), 1, false);
513: emitBodyPut(goal.getObject(), 2, false);
514: List predicateCode = store.codeFor(goal);
515: if (predicateCode == null || predicateCode.size() == 0) {
516: code[p++] = CALL_TRIPLE_MATCH;
517: } else {
518: // code[p++] = CALL_TABLED;
519: if (goal.getPredicate().isVariable()) {
520: // Experimental. Force tabling of any wildcard predicate calls
521: code[p++] = CALL_TABLED;
522: } else if (store.isTabled(goal)) {
523: // if (store.isTabled(goal)) {
524: code[p++] = goal.getPredicate().isVariable() ? CALL_WILD_TABLED
525: : CALL_TABLED;
526: } else {
527: if (permanentVars.size() == 0) {
528: code[p++] = LAST_CALL_PREDICATE;
529: } else {
530: // Normal call, but can it be indexed further?
531: if (store.isIndexedPredicate(goal
532: .getPredicate())
533: && goal.getObject().isVariable()) {
534: code[p++] = CALL_PREDICATE_INDEX;
535: } else {
536: code[p++] = CALL_PREDICATE;
537: }
538: }
539: args.add(predicateCode);
540: }
541: }
542: }
543:
544: /**
545: * Emit code a single body put operation.
546: * @param node the node to emit
547: * @param argi the argument register to use
548: * @param deref if true force a dereference of the variable binding at this point for
549: * use in calling builtins
550: */
551: void emitBodyPut(Node node, int argi, boolean deref) {
552: if (argi >= MAX_ARGUMENT_VARS) {
553: throw new LPRuleSyntaxException(
554: "Rule too complex for current implementation\n"
555: + "Rule clauses are limited to "
556: + MAX_ARGUMENT_VARS
557: + " argument variables\n", rule);
558:
559: }
560: if (node instanceof Node_RuleVariable) {
561: Node_RuleVariable var = (Node_RuleVariable) node;
562: if (isDummy(var)) {
563: code[p++] = CLEAR_ARG;
564: code[p++] = (byte) argi;
565: return;
566: }
567: if (isTemp(var)) {
568: List occurrences = (List) varOccurrence.get(var);
569: if (occurrences.size() == 2
570: && ((TermIndex) occurrences.get(0)).index == ((TermIndex) occurrences
571: .get(1)).index) {
572: // No movement code required, var in right place
573: } else {
574: code[p++] = PUT_TEMP;
575: code[p++] = (byte) tempVars.indexOf(var);
576: code[p++] = (byte) argi;
577: }
578: } else {
579: if (!seen.add(var)) {
580: code[p++] = (deref ? PUT_DEREF_VARIABLE
581: : PUT_VARIABLE);
582: } else {
583: code[p++] = PUT_NEW_VARIABLE;
584: }
585: code[p++] = (byte) permanentVars.indexOf(var);
586: code[p++] = (byte) argi;
587: }
588: } else if (Functor.isFunctor(node)) {
589: Functor f = (Functor) node.getLiteralValue();
590: Node[] fargs = f.getArgs();
591: for (int i = 0; i < fargs.length; i++) {
592: emitBodyPut(fargs[i], i + 3, deref);
593: }
594: code[p++] = MAKE_FUNCTOR;
595: args.add(f);
596: } else {
597: code[p++] = PUT_CONSTANT;
598: code[p++] = (byte) argi;
599: args.add(node);
600: }
601: }
602:
603: /**
604: * Emit code for a call to a built-in predicate (functor).
605: * @param functor the built-in to be invoked.
606: */
607: void emitBody(Functor functor) {
608: Node[] fargs = functor.getArgs();
609: Builtin builtin = functor.getImplementor();
610: if (builtin == null) {
611: throw new LPRuleSyntaxException(
612: "Unknown builtin operation "
613: + functor.getName(), rule);
614: }
615: if (builtin.getArgLength() != 0
616: && builtin.getArgLength() != fargs.length) {
617: throw new LPRuleSyntaxException(
618: "Wrong number of arguments to functor "
619: + functor.getName() + " expected "
620: + functor.getArgLength(), rule);
621: }
622: for (int i = 0; i < fargs.length; i++) {
623: Node node = fargs[i];
624: // We optionally force an eager dereference of variables here.
625: // We used to force this but the current builtin implementations
626: // now robust against it (the do a deref themselves anyway).
627: emitBodyPut(node, i, true);
628: }
629: code[p++] = CALL_BUILTIN;
630: code[p++] = (byte) fargs.length;
631: args.add(builtin);
632: }
633:
634: /**
635: * Complete the byte stream with a PROCEED and return the packed version of the code.
636: * @return the byte code array
637: */
638: byte[] getFinalCode() {
639: code[p++] = PROCEED;
640: byte[] finalCode = new byte[p];
641: System.arraycopy(code, 0, finalCode, 0, p);
642: return finalCode;
643: }
644:
645: /**
646: * Fetch the packed array of argument objects for the byte code.
647: * @return arg array
648: */
649: Object[] getFinalArgs() {
650: return args.toArray();
651: }
652:
653: /**
654: * Classifies the variables now and side effects the
655: * index number of the variables so they lie in two sequences - temp
656: * and permanent separately.
657: */
658: void classifyVariables(Rule rule) {
659: // Build index data structure into var use in each term in the rule
660: termVarTable = new List[rule.bodyLength() + 1];
661: termVarTable[0] = termVars(rule.getHeadElement(0));
662: totalOccurrences += termVarTable[0].size();
663: for (int i = 0; i < rule.bodyLength(); i++) {
664: termVarTable[i + 1] = termVars(rule.getBodyElement(i));
665: totalOccurrences += termVarTable[i + 1].size();
666: }
667:
668: // Build the inverted data structure
669: for (int i = 0; i < rule.bodyLength() + 1; i++) {
670: List varEnts = termVarTable[i];
671: for (int j = 0; j < varEnts.size(); j++) {
672: Node n = (Node) varEnts.get(j);
673: if (n.isVariable()) {
674: Node_RuleVariable var = (Node_RuleVariable) n;
675: List occurrences = (List) varOccurrence
676: .get(var);
677: if (occurrences == null) {
678: occurrences = new ArrayList();
679: varOccurrence.put(var, occurrences);
680: }
681: occurrences.add(new TermIndex(var, i, j));
682: }
683: }
684: }
685:
686: // Classify vars as permanent unless they are just dummies (only used once at all)
687: // or only used head+first body goal (but not if used in a builtin)
688: for (Iterator enti = varOccurrence.values().iterator(); enti
689: .hasNext();) {
690: List occurrences = (List) enti.next();
691: Node_RuleVariable var = null;
692: boolean inFirst = false;
693: boolean inLaterBody = false;
694: boolean inBuiltin = false;
695: for (Iterator oi = occurrences.iterator(); oi.hasNext();) {
696: TermIndex occurence = (TermIndex) oi.next();
697: var = occurence.var;
698: int termNumber = occurence.termNumber;
699: if (termNumber == 0) {
700: inFirst = true;
701: } else if (termNumber > 1) {
702: inLaterBody = true;
703: }
704: if (termNumber > 0
705: && rule.getBodyElement(termNumber - 1) instanceof Functor) {
706: inBuiltin = true;
707: }
708: }
709: // Don't think we need to protected builtin's any more, so ignore that test
710: // if (inBuiltin) {
711: // permanentVars.add(var);
712: // } else {
713: if (!isDummy(var)) {
714: if (inLaterBody || !inFirst) {
715: permanentVars.add(var);
716: } else {
717: tempVars.add(var);
718: }
719: }
720: // }
721:
722: }
723:
724: if (permanentVars.size() > MAX_PERMANENT_VARS) {
725: throw new LPRuleSyntaxException(
726: "Rule too complex for current implementation\n"
727: + "Rule clauses are limited to "
728: + MAX_PERMANENT_VARS
729: + " permanent variables\n", rule);
730: }
731:
732: if (tempVars.size() > MAX_TEMPORARY_VARS) {
733: throw new LPRuleSyntaxException(
734: "Rule too complex for current implementation\n"
735: + "Rule clauses are limited to "
736: + MAX_TEMPORARY_VARS
737: + " temporary variables\n", rule);
738: }
739:
740: // Builtins in the forward system use the var index to modify variable bindings.
741: // At one time I though the LP system might need to emulate this but (a) it doesn't and
742: // (b) renumber vars to make that possible wreaks rule equality which wreaks add/remove in
743: // hybrid rule sets. This code left in but commented out as a reminder to not go down
744: // that path again.
745:
746: // Renumber the vars
747: // for (int i = 0; i < permanentVars.size(); i++ ) {
748: // Node_RuleVariable var = (Node_RuleVariable)permanentVars.get(i);
749: // var.setIndex(i);
750: // }
751: // for (int i = 0; i < tempVars.size(); i++ ) {
752: // Node_RuleVariable var = (Node_RuleVariable)tempVars.get(i);
753: // var.setIndex(i);
754: // }
755:
756: }
757:
758: /** Return true if the given rule variable is a temp */
759: boolean isTemp(Node_RuleVariable var) {
760: return !isDummy(var) && !permanentVars.contains(var);
761: }
762:
763: /** Return true if the given rule variable is a dummy */
764: boolean isDummy(Node_RuleVariable var) {
765: List occurances = (List) varOccurrence.get(var);
766: if (occurances == null || occurances.size() <= 1)
767: return true;
768: return false;
769: }
770:
771: /** Return an list of variables or nodes in a ClauseEntry, in flattened order */
772: private List termVars(ClauseEntry term) {
773: List result = new ArrayList();
774: if (term instanceof TriplePattern) {
775: TriplePattern goal = (TriplePattern) term;
776: result.add(goal.getSubject());
777: result.add(goal.getPredicate());
778: Node obj = goal.getObject();
779: if (Functor.isFunctor(obj)) {
780: result.add(obj);
781: result.addAll(termVars((Functor) obj
782: .getLiteralValue()));
783: } else {
784: result.add(obj);
785: }
786: } else if (term instanceof Functor) {
787: Node[] args = (Node[]) ((Functor) term).getArgs();
788: for (int i = 0; i < args.length; i++) {
789: result.add(args[i]);
790: }
791: }
792: return result;
793: }
794: }
795:
796: /**
797: * Inner class used to represent the occurance of a variable in a term.
798: * Not an abstract data type, just a structure directly accessed.
799: */
800: static class TermIndex {
801: /** The term number in the rule - 0 for head, body starting from 1 */
802: int termNumber;
803:
804: /** The variable position within the term */
805: int index;
806:
807: /** The variable being indexed */
808: Node_RuleVariable var;
809:
810: /** Constructor */
811: TermIndex(Node_RuleVariable var, int termNumber, int index) {
812: this .var = var;
813: this .termNumber = termNumber;
814: this .index = index;
815: }
816: }
817:
818: /**
819: * Debug support - not unit testing.
820: */
821: public static void main(String[] args) {
822: try {
823: LPRuleStore store = new LPRuleStore();
824: String test1 = "(?a p ?y) <- (?a p2 ?z).";
825: String test2 = "(?a p ?y) <- (?a q2 ?z) (?z q2 ?w).";
826: String test3 = "(?a p ?a) <- (?z r2 ?w) (?z r2 ?w).";
827: String test4 = "(?a p ?a) <- (?z r2 ?w) (?a r2 ?w).";
828: String test5 = "(?a p ?y) <- (?a p ?z), (?z p ?y).";
829: String test6 = "(?x p C3) <- (C1 r ?x).";
830: String test7 = "(?x p ?y) <- (?x r ?y) (?x q ?y).";
831: String test8 = "(?x p ?y) <- (?x p ?z) addOne(?z, ?y).";
832: String test9 = "(?x p ?y) <- (?x p ?z) sum(?z, 2, ?y).";
833: String test10 = "(?x p ?y) <- (?x p ?v), sum(?v 2 ?y).";
834: String test11 = "(b p ?y) <- (a ?y ?v).";
835: String test12 = "(?x p ?y) <- (?x p foo(?z, ?y)).";
836: String test13 = "(?x p foo(?y,?z)) <- (?x q ?y), (?x q ?z).";
837: String test14 = "(?x p ?z) <- (?x e ?z), (?z q ?z).";
838: String test15 = "(?x p ?y ) <- bound(?x), (?x p ?y).";
839: String test16 = "(a p b ) <- unbound(?x).";
840: String test17 = "(?a p ?a) <- (?a q class).";
841: String test18 = "(?a p ?a) <- (?a s ?a).";
842: String test19 = "(?X p ?T) <- (?X rdf:type c), noValue(?X, p), makeInstance(?X, p, ?T).";
843: String test20 = "(a p b ) <- unbound(?x).";
844: String testLong = "(?P p ?C) <- (?P q ?D), (?D r xsd(?B, ?S1, ?L1)),(?P p ?E), notEqual(?D, ?E) "
845: + "(?E e xsd(?B, ?S2, ?L2)),min(?S1, ?S2, ?S3),min(?L1, ?L2, ?L3), (?C r xsd(?B, ?S3, ?L3)).";
846: String test21 = "(?a p ?y) <- (?x s ?y) (?a p ?x).";
847: String test22 = "(?C p ?D) <- (?C rb:xsdBase ?BC), (?D rb:xsdBase ?BD), notEqual(?BC, ?BD).";
848: store.addRule(Rule.parseRule(test22));
849: System.out.println("Code for p:");
850: List codeList = store.codeFor(Node.createURI("p"));
851: RuleClauseCode code = (RuleClauseCode) codeList.get(0);
852: code.print(System.out);
853: } catch (Exception e) {
854: System.out.println("Problem: " + e);
855: e.printStackTrace();
856: }
857: }
858: }
859:
860: /*
861: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
862: All rights reserved.
863:
864: Redistribution and use in source and binary forms, with or without
865: modification, are permitted provided that the following conditions
866: are met:
867:
868: 1. Redistributions of source code must retain the above copyright
869: notice, this list of conditions and the following disclaimer.
870:
871: 2. Redistributions in binary form must reproduce the above copyright
872: notice, this list of conditions and the following disclaimer in the
873: documentation and/or other materials provided with the distribution.
874:
875: 3. The name of the author may not be used to endorse or promote products
876: derived from this software without specific prior written permission.
877:
878: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
879: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
880: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
881: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
882: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
883: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
884: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
885: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
886: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
887: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
888: */
|