001: /******************************************************************
002: * File: BindingVector.java
003: * Created by: Dave Reynolds
004: * Created on: 28-Apr-03
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: BindingVector.java,v 1.26 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.*;
013: import com.hp.hpl.jena.reasoner.rulesys.*;
014: import com.hp.hpl.jena.util.PrintUtil;
015:
016: import java.util.*;
017:
018: /**
019: * An implementation of a binding environment that maintains
020: * a single array of bound values for the variables in a rule.
021: * Stack management is done externally. This is intended for use in
022: * the Brule system and so also supports variable-variable bindings by
023: * use of reference chains.
024: *
025: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
026: * @version $Revision: 1.26 $ on $Date: 2008/01/02 12:06:16 $
027: */
028: public class BindingVector implements BindingEnvironment {
029:
030: /** The current binding set */
031: protected Node[] environment;
032:
033: /**
034: * Constructor - create an empty binding environment
035: */
036: public BindingVector(int size) {
037: environment = new Node[size];
038: }
039:
040: /**
041: * Constructor - create a binding environment from a vector of bindings
042: */
043: public BindingVector(Node[] env) {
044: environment = env;
045: }
046:
047: /**
048: * Constructor - create a binding environment which is a copy
049: * of the given environment
050: */
051: public BindingVector(BindingVector clone) {
052: Node[] orig = clone.environment;
053: environment = new Node[orig.length];
054: System.arraycopy(orig, 0, environment, 0, orig.length);
055: }
056:
057: /**
058: * Return the current array of bindings. Useful for fast access to
059: * serveral bindings, not useful for doing updates.
060: */
061: public Node[] getEnvironment() {
062: return environment;
063: }
064:
065: /**
066: * If the node is a variable then return the current binding (null if not bound)
067: * otherwise return the node itself.
068: */
069: public Node getBinding(Node node) {
070: if (node instanceof Node_RuleVariable) {
071: Node val = environment[((Node_RuleVariable) node)
072: .getIndex()];
073: if (val instanceof Node_RuleVariable) {
074: return getBinding(val);
075: } else {
076: return val;
077: }
078: } else if (node instanceof Node_ANY) {
079: return null;
080: } else if (Functor.isFunctor(node)) {
081: Functor functor = (Functor) node.getLiteralValue();
082: if (functor.isGround())
083: return node;
084: Node[] args = functor.getArgs();
085: ArrayList boundargs = new ArrayList(args.length);
086: for (int i = 0; i < args.length; i++) {
087: Object binding = getBinding(args[i]);
088: if (binding == null) {
089: // Not sufficently bound to instantiate functor yet
090: return null;
091: }
092: boundargs.add(binding);
093: }
094: Functor newf = new Functor(functor.getName(), boundargs);
095: return Functor.makeFunctorNode(newf);
096: } else {
097: return node;
098: }
099: }
100:
101: /**
102: * Return the most ground version of the node. If the node is not a variable
103: * just return it, if it is a varible bound in this enviroment return the binding,
104: * if it is an unbound variable return the variable.
105: */
106: public Node getGroundVersion(Node node) {
107: Node bind = getBinding(node);
108: if (bind == null) {
109: return node;
110: } else {
111: return bind;
112: }
113: }
114:
115: /**
116: * Bind the ith variable in the current envionment to the given value.
117: * Checks that the new binding is compatible with any current binding.
118: * Handles aliased variables.
119: * @return false if the binding fails
120: */
121: public boolean bind(int i, Node value) {
122: Node node = environment[i];
123: if (node == null) {
124: environment[i] = value;
125: return true;
126: } else if (node instanceof Node_RuleVariable) {
127: environment[i] = value;
128: return bind(((Node_RuleVariable) node).getIndex(), value);
129: } else {
130: return node.sameValueAs(value);
131: }
132: }
133:
134: /**
135: * Bind a variable in the current envionment to the given value.
136: * Checks that the new binding is compatible with any current binding.
137: * @param var a Node_RuleVariable defining the variable to bind
138: * @param value the value to bind
139: * @return false if the binding fails
140: */
141: public boolean bind(Node var, Node value) {
142: if (var instanceof Node_RuleVariable) {
143: return bind(((Node_RuleVariable) var).getIndex(), value);
144: } else {
145: return var.sameValueAs(value);
146: }
147: }
148:
149: /**
150: * Bind the variables in a goal pattern using the binding environment, to
151: * generate a more specialized goal
152: * @param goal the TriplePattern to be instantiated
153: * @return a TriplePattern obtained from the goal by substituting current bindinds
154: */
155: public TriplePattern partInstantiate(TriplePattern goal) {
156: return new TriplePattern(getGroundVersion(goal.getSubject()),
157: getGroundVersion(goal.getPredicate()),
158: getGroundVersion(goal.getObject()));
159: }
160:
161: // Replaced by version below for consistency with stack variant
162: // /**
163: // * Instatiate a goal pattern using the binding environment
164: // * @param goal the TriplePattern to be instantiated
165: // * @return an instantiated Triple
166: // */
167: // public Triple instantiate(TriplePattern goal) {
168: // return new Triple(
169: // getGroundVersion(goal.getSubject()),
170: // getGroundVersion(goal.getPredicate()),
171: // getGroundVersion(goal.getObject())
172: // );
173: // }
174:
175: /**
176: * Instantiate a triple pattern against the current environment.
177: * This version handles unbound varibles by turning them into bNodes.
178: * @param clause the triple pattern to match
179: * @param env the current binding environment
180: * @return a new, instantiated triple
181: */
182: public Triple instantiate(TriplePattern pattern) {
183: Node s = getGroundVersion(pattern.getSubject());
184: if (s.isVariable())
185: s = Node.createAnon();
186: Node p = getGroundVersion(pattern.getPredicate());
187: if (p.isVariable())
188: p = Node.createAnon();
189: Node o = getGroundVersion(pattern.getObject());
190: if (o.isVariable())
191: o = Node.createAnon();
192: return new Triple(s, p, o);
193: }
194:
195: /**
196: * Printable form
197: */
198: public String toString() {
199: StringBuffer buffer = new StringBuffer();
200: for (int i = 0; i < environment.length; i++) {
201: if (environment[i] == null) {
202: buffer.append("-");
203: } else {
204: buffer.append(PrintUtil.print(environment[i]));
205: }
206: buffer.append(" ");
207: }
208: return buffer.toString();
209: }
210:
211: /**
212: * Unify a goal with the head of a rule. This is a poor-man's unification,
213: * we should try swtiching to a more conventional global-variables-with-trail
214: * implementation in the future.
215: * @param goal the goal pattern which it being matched to a rule
216: * @param head the head pattern of the rule which is being instantiated
217: * @param numRuleVars the length of the environment to allocate.
218: * @return An initialized binding environment for the rule variables
219: * or null if the unification fails. If a variable in the environment becomes
220: * aliased to another variable through the unification this is represented
221: * by having its value in the environment be the variable to which it is aliased.
222: */
223: public static BindingVector unify(TriplePattern goal,
224: TriplePattern head, int numRuleVars) {
225: Node[] gEnv = new Node[numRuleVars]; // TODO: check
226: Node[] hEnv = new Node[numRuleVars];
227:
228: if (!unify(goal.getSubject(), head.getSubject(), gEnv, hEnv)) {
229: return null;
230: }
231: if (!unify(goal.getPredicate(), head.getPredicate(), gEnv, hEnv)) {
232: return null;
233: }
234:
235: Node gObj = goal.getObject();
236: Node hObj = head.getObject();
237: if (Functor.isFunctor(gObj)) {
238: Functor gFunctor = (Functor) gObj.getLiteralValue();
239: if (Functor.isFunctor(hObj)) {
240: Functor hFunctor = (Functor) hObj.getLiteralValue();
241: if (!gFunctor.getName().equals(hFunctor.getName())) {
242: return null;
243: }
244: Node[] gArgs = gFunctor.getArgs();
245: Node[] hArgs = hFunctor.getArgs();
246: if (gArgs.length != hArgs.length)
247: return null;
248: for (int i = 0; i < gArgs.length; i++) {
249: if (!unify(gArgs[i], hArgs[i], gEnv, hEnv)) {
250: return null;
251: }
252: }
253: } else if (hObj instanceof Node_RuleVariable) {
254: // temp debug ...
255: // Check the goal functor is fully ground
256: if (gFunctor.isGround(new BindingVector(gEnv))) {
257: if (!unify(gObj, hObj, gEnv, hEnv))
258: return null;
259: }
260: // ... end debug
261: } else {
262: // unifying simple ground object with functor, failure
263: return null;
264: }
265: } else {
266: if (!unify(gObj, hObj, gEnv, hEnv))
267: return null;
268: }
269: // Successful bind if we get here
270: return new BindingVector(hEnv);
271: }
272:
273: /**
274: * Unify a single pair of goal/head nodes. Unification of a head var to
275: * a goal var is recorded using an Integer in the head env to point to a
276: * goal env and storing the head var in the goal env slot.
277: * @return true if they are unifiable, side effects the environments
278: */
279: private static boolean unify(Node gNode, Node hNode, Node[] gEnv,
280: Node[] hEnv) {
281: if (hNode instanceof Node_RuleVariable) {
282: int hIndex = ((Node_RuleVariable) hNode).getIndex();
283: if (gNode instanceof Node_RuleVariable) {
284: // Record variable bind between head and goal to detect aliases
285: int gIndex = ((Node_RuleVariable) gNode).getIndex();
286: if (gIndex < 0)
287: return true;
288: if (gEnv[gIndex] == null) {
289: // First time bind so record link
290: gEnv[gIndex] = hNode;
291: } else {
292: // aliased var so follow trail to alias
293: // but ignore self-aliases
294: Node gVal = gEnv[gIndex];
295: if (hIndex != gIndex
296: || !(gVal instanceof Node_RuleVariable)) {
297: hEnv[hIndex] = gVal;
298: }
299: }
300: } else {
301: Node hVal = hEnv[hIndex];
302: if (hVal == null) {
303: hEnv[hIndex] = gNode;
304: } else {
305: // Already bound
306: if (hVal instanceof Node_RuleVariable) {
307: // Already an aliased variable, so bind both this an the alias
308: hEnv[((Node_RuleVariable) hVal).getIndex()] = gNode;
309: hEnv[hIndex] = gNode;
310: } else {
311: // Already bound to a ground node
312: return hVal.sameValueAs(gNode);
313: }
314: }
315: }
316: return true;
317: } else {
318: if (gNode instanceof Node_RuleVariable) {
319: int gIndex = ((Node_RuleVariable) gNode).getIndex();
320: if (gIndex < 0)
321: return true;
322: Node gVal = gEnv[gIndex];
323: if (gVal == null) {
324: //. No variable alias so just record binding
325: gEnv[gIndex] = hNode;
326: } else if (gVal instanceof Node_RuleVariable) {
327: // Already an alias
328: hEnv[((Node_RuleVariable) gVal).getIndex()] = hNode;
329: gEnv[gIndex] = hNode;
330: } else {
331: return gVal.sameValueAs(hNode);
332: }
333: return true;
334: } else {
335: return hNode.sameValueAs(gNode);
336: }
337: }
338: }
339:
340: /** Equality override */
341: public boolean equals(Object o) {
342: // Pass 1 - just check basic shape
343: if (!(o instanceof BindingVector))
344: return false;
345: Node[] other = ((BindingVector) o).environment;
346: if (environment.length != other.length)
347: return false;
348: for (int i = 0; i < environment.length; i++) {
349: Node n = environment[i];
350: Node no = other[i];
351: if (n == null) {
352: if (no != null)
353: return false;
354: } else {
355: if (!n.sameValueAs(no))
356: return false;
357: }
358: }
359: return true;
360: }
361:
362: /** hash function override */
363: public int hashCode() {
364: int hash = 0;
365: for (int i = 0; i < environment.length; i++) {
366: Node n = environment[i];
367: hash = (hash << 1) ^ (n == null ? 0x537c : n.hashCode());
368: }
369: return hash;
370: }
371:
372: }
373:
374: /*
375: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
376: All rights reserved.
377:
378: Redistribution and use in source and binary forms, with or without
379: modification, are permitted provided that the following conditions
380: are met:
381:
382: 1. Redistributions of source code must retain the above copyright
383: notice, this list of conditions and the following disclaimer.
384:
385: 2. Redistributions in binary form must reproduce the above copyright
386: notice, this list of conditions and the following disclaimer in the
387: documentation and/or other materials provided with the distribution.
388:
389: 3. The name of the author may not be used to endorse or promote products
390: derived from this software without specific prior written permission.
391:
392: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
393: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
394: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
395: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
396: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
397: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
398: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
399: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
400: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
401: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
402: */
|