001: /******************************************************************
002: * File: RETEClauseFilter.java
003: * Created by: Dave Reynolds
004: * Created on: 09-Jun-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: RETEClauseFilter.java,v 1.14 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.graph.*;
012: import com.hp.hpl.jena.reasoner.rulesys.*;
013: import com.hp.hpl.jena.reasoner.*;
014:
015: import java.util.*;
016:
017: /**
018: * Checks a triple against the grounded matches and intra-triple matches
019: * for a single rule clause. If the match passes it creates a binding
020: * environment token and passes it on the the RETE network itself. The checks
021: * and bindings are implemented using a simple byte-coded interpreter.
022: *
023: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
024: * @version $Revision: 1.14 $ on $Date: 2008/01/02 12:06:16 $
025: */
026: public class RETEClauseFilter implements RETESourceNode {
027:
028: /** Contains the set of byte-coded instructions and argument pointers */
029: protected byte[] instructions;
030:
031: /** Contains the object arguments referenced from the instructions array */
032: protected Object[] args;
033:
034: /** The network node to receive any created tokens */
035: protected RETESinkNode continuation;
036:
037: /** Instruction code: Check triple entry (arg1) against literal value (arg2). */
038: public static final byte TESTValue = 0x01;
039:
040: /** Instruction code: Check literal value is a functor of name arg1 */
041: public static final byte TESTFunctorName = 0x02;
042:
043: /** Instruction code: Cross match two triple entries (arg1, arg2) */
044: public static final byte TESTIntraMatch = 0x03;
045:
046: /** Instruction code: Create a result environment of length arg1. */
047: public static final byte CREATEToken = 0x04;
048:
049: /** Instruction code: Bind a node (arg1) to a place in the rules token (arg2). */
050: public static final byte BIND = 0x05;
051:
052: /** Instruction code: Final entry - dispatch to the network. */
053: public static final byte END = 0x06;
054:
055: /** Argument addressing code: triple subject */
056: public static final byte ADDRSubject = 0x10;
057:
058: /** Argument addressing code: triple predicate */
059: public static final byte ADDRPredicate = 0x20;
060:
061: /** Argument addressing code: triple object as a whole */
062: public static final byte ADDRObject = 0x30;
063:
064: /** Argument addressing code: triple object functor node, offset in
065: * low nibble, only usable after a successful TestFunctorName. */
066: public static final byte ADDRFunctorNode = 0x40;
067:
068: /**
069: * Contructor.
070: * @param instructions the set of byte-coded instructions and argument pointers.
071: * @param args the object arguments referenced from the instructions array.
072: */
073: public RETEClauseFilter(byte[] instructions, Object[] args) {
074: this .instructions = instructions;
075: this .args = args;
076: }
077:
078: /**
079: * Create a filter node from a rule clause.
080: * Clause complexity is limited to less than 50 args in a Functor.
081: * @param clause the rule clause
082: * @param envLength the size of binding environment that should be created on successful matches
083: * @param varList a list to which all clause variables will be appended
084: */
085: public static RETEClauseFilter compile(TriplePattern clause,
086: int envLength, List varList) {
087: byte[] instructions = new byte[300];
088: byte[] bindInstructions = new byte[100];
089: ArrayList args = new ArrayList();
090: int pc = 0;
091: int bpc = 0;
092:
093: // Pass 0 - prepare env creation statement
094: bindInstructions[bpc++] = CREATEToken;
095: bindInstructions[bpc++] = (byte) envLength;
096:
097: // Pass 1 - check literal values
098: Node n = clause.getSubject();
099: if (!n.isVariable()) {
100: instructions[pc++] = TESTValue;
101: instructions[pc++] = ADDRSubject;
102: instructions[pc++] = (byte) args.size();
103: args.add(n);
104: } else {
105: bindInstructions[bpc++] = BIND;
106: bindInstructions[bpc++] = ADDRSubject;
107: bindInstructions[bpc++] = (byte) ((Node_RuleVariable) n)
108: .getIndex();
109: varList.add(n);
110: }
111: n = clause.getPredicate();
112: if (!n.isVariable()) {
113: instructions[pc++] = TESTValue;
114: instructions[pc++] = ADDRPredicate;
115: instructions[pc++] = (byte) args.size();
116: args.add(clause.getPredicate());
117: } else {
118: bindInstructions[bpc++] = BIND;
119: bindInstructions[bpc++] = ADDRPredicate;
120: bindInstructions[bpc++] = (byte) ((Node_RuleVariable) n)
121: .getIndex();
122: varList.add(n);
123: }
124: n = clause.getObject();
125: if (!n.isVariable()) {
126: if (Functor.isFunctor(n)) {
127: // Pass 2 - check functor
128: Functor f = (Functor) n.getLiteralValue();
129: instructions[pc++] = TESTFunctorName;
130: instructions[pc++] = (byte) args.size();
131: args.add(f.getName());
132: Node[] fargs = f.getArgs();
133: for (int i = 0; i < fargs.length; i++) {
134: Node fn = fargs[i];
135: byte addr = (byte) (ADDRFunctorNode | (0x0f & i));
136: if (!fn.isVariable()) {
137: instructions[pc++] = TESTValue;
138: instructions[pc++] = addr;
139: instructions[pc++] = (byte) args.size();
140: args.add(fn);
141: } else {
142: bindInstructions[bpc++] = BIND;
143: bindInstructions[bpc++] = addr;
144: bindInstructions[bpc++] = (byte) ((Node_RuleVariable) fn)
145: .getIndex();
146: varList.add(fn);
147: }
148: }
149: } else {
150: instructions[pc++] = TESTValue;
151: instructions[pc++] = ADDRObject;
152: instructions[pc++] = (byte) args.size();
153: args.add(n);
154: }
155: } else {
156: bindInstructions[bpc++] = BIND;
157: bindInstructions[bpc++] = ADDRObject;
158: bindInstructions[bpc++] = (byte) ((Node_RuleVariable) n)
159: .getIndex();
160: varList.add(n);
161: }
162: bindInstructions[bpc++] = END;
163:
164: // Pass 4 - Pack instructions
165: byte[] packed = new byte[pc + bpc];
166: System.arraycopy(instructions, 0, packed, 0, pc);
167: System.arraycopy(bindInstructions, 0, packed, pc, bpc);
168: Object[] packedArgs = args.toArray();
169:
170: return new RETEClauseFilter(packed, packedArgs);
171: }
172:
173: /**
174: * Set the continuation node for this node.
175: */
176: public void setContinuation(RETESinkNode continuation) {
177: this .continuation = continuation;
178: }
179:
180: /**
181: * Insert or remove a triple into the network.
182: * @param triple the triple to process.
183: * @param isAdd true if the triple is being added to the working set.
184: */
185: public void fire(Triple triple, boolean isAdd) {
186:
187: Functor lastFunctor = null; // bound by TESTFunctorName
188: BindingVector env = null; // bound by CREATEToken
189: Node n = null; // Temp workspace
190:
191: for (int pc = 0; pc < instructions.length;) {
192: switch (instructions[pc++]) {
193:
194: case TESTValue:
195: // Check triple entry (arg1) against literal value (arg2)
196: if (!getTripleValue(triple, instructions[pc++],
197: lastFunctor).sameValueAs(
198: args[instructions[pc++]]))
199: return;
200: break;
201:
202: case TESTFunctorName:
203: // Check literal value is a functor of name arg1.
204: // Side effect: leaves a loop variable pointing to functor
205: // for possible later functor argument accesses
206: n = triple.getObject();
207: if (!n.isLiteral())
208: return;
209: if (n.getLiteralDatatype() != Functor.FunctorDatatype.theFunctorDatatype)
210: return;
211: lastFunctor = (Functor) n.getLiteralValue();
212: if (!lastFunctor.getName().equals(
213: args[instructions[pc++]]))
214: return;
215: break;
216:
217: case CREATEToken:
218: // Create a result environment of length arg1
219: env = new BindingVector(new Node[instructions[pc++]]);
220: break;
221:
222: case BIND:
223: // Bind a node (arg1) to a place in the rules token (arg2)
224: n = getTripleValue(triple, instructions[pc++],
225: lastFunctor);
226: if (!env.bind(instructions[pc++], n))
227: return;
228: break;
229:
230: case END:
231: // Success, fire the continuation
232: continuation.fire(env, isAdd);
233: }
234: }
235:
236: }
237:
238: /**
239: * Helperful function. Return the node from the argument triple
240: * corresponding to the byte code address.
241: */
242: private Node getTripleValue(Triple triple, byte address,
243: Functor lastFunctor) {
244: switch (address & 0xf0) {
245: case ADDRSubject:
246: return triple.getSubject();
247: case ADDRPredicate:
248: return triple.getPredicate();
249: case ADDRObject:
250: return triple.getObject();
251: case ADDRFunctorNode:
252: return lastFunctor.getArgs()[address & 0x0f];
253: }
254: return null;
255: }
256:
257: /**
258: * Clone this node in the network.
259: * @param netCopy a map from RETENode to cloned instance
260: * @param context the new context to which the network is being ported
261: */
262: public RETENode clone(Map netCopy, RETERuleContext context) {
263: RETEClauseFilter clone = (RETEClauseFilter) netCopy.get(this );
264: if (clone == null) {
265: clone = new RETEClauseFilter(instructions, args);
266: clone.setContinuation((RETESinkNode) continuation.clone(
267: netCopy, context));
268: netCopy.put(this , clone);
269: }
270: return clone;
271: }
272:
273: }
274:
275: /*
276: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
277: All rights reserved.
278:
279: Redistribution and use in source and binary forms, with or without
280: modification, are permitted provided that the following conditions
281: are met:
282:
283: 1. Redistributions of source code must retain the above copyright
284: notice, this list of conditions and the following disclaimer.
285:
286: 2. Redistributions in binary form must reproduce the above copyright
287: notice, this list of conditions and the following disclaimer in the
288: documentation and/or other materials provided with the distribution.
289:
290: 3. The name of the author may not be used to endorse or promote products
291: derived from this software without specific prior written permission.
292:
293: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
294: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
295: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
296: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
297: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
298: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
299: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
300: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
301: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
302: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
303: */
|