rule.java

Jena推理机

/******************************************************************
 * File:        Rule.java
 * Created by:  Dave Reynolds
 * Created on:  29-Mar-03
 * 
 * (c) Copyright 2003, 2004, 2005, 2006, 2007 Hewlett-Packard Development Company, LP
 * [See end of file]
 * $Id: Rule.java,v 1.45 2007/01/02 11:50:58 andy_seaborne Exp $
 *****************************************************************/
package com.hp.hpl.jena.reasoner.rulesys;

import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;

import com.hp.hpl.jena.util.FileUtils;
import com.hp.hpl.jena.util.PrintUtil;
import com.hp.hpl.jena.util.Tokenizer;
import com.hp.hpl.jena.graph.*;
import com.hp.hpl.jena.reasoner.*;
import com.hp.hpl.jena.shared.*;
import com.hp.hpl.jena.datatypes.RDFDatatype;
import com.hp.hpl.jena.datatypes.TypeMapper;
import com.hp.hpl.jena.datatypes.xsd.*;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**Representation of a generic inference rule. 
 * <p>
 * This represents the rule specification but most engines will 
 * compile this specification into an abstract machine or processing
 * graph. </p>
 * <p>
 * The rule specification comprises a list of antecendents (body) and a list
 * of consequents (head). If there is more than one consequent then a backchainer
 * should regard this as a shorthand for several rules, all with the
 * same body but with a singleton head. </p>
 * <p>
 * Each element in the head or body can be a TriplePattern, a Functor or a Rule.
 * A TriplePattern is just a triple of Nodes but the Nodes can represent
 * variables, wildcards and embedded functors - as well as constant uri or
 * literal graph nodes. A functor comprises a functor name and a list of 
 * arguments. The arguments are Nodes of any type except functor nodes
 * (there is no functor nesting). The functor name can be mapped into a registered
 * java class that implements its semantics. Functors play three roles -
 * in heads they represent actions (procedural attachement); in bodies they
 * represent builtin predicates; in TriplePatterns they represent embedded
 * structured literals that are used to cache matched subgraphs such as
 * restriction specifications. </p>
 *<p>
 * We include a trivial, recursive descent parser but this is just there
 * to allow rules to be embedded in code. External rule syntax based on N3
 * and RDF could be developed. The embedded syntax supports rules such as:
 * <blockindent>    
 * <code>[ (?C rdf:type *), guard(?C, ?P)  -> (?c rb:restriction some(?P, ?D)) ].</code><br />
 * <code>[ (?s owl:foo ?p) -> [ (?s owl:bar ?a) -> (?s ?p ?a) ] ].</code><br />
 * <code>[name: (?s owl:foo ?p) -> (?s ?p ?a)].</code><br />
 * </blockindent>
 * only built in namespaces are recognized as such, * is a wildcard node, ?c is a variable, 
 * name(node ... node) is a functor, (node node node) is a triple pattern, [..] is an
 * embedded rule, commas are ignore and can be freely used as separators. Functor names
 * may not end in ':'.
 * </p>
 * @author <a href="mailto:[e-mail]">Dave Reynolds</a> * @version $Revision: 1.45 $ on $Date: 2007/01/02 11:50:58 $ 
 */
public class Rule implements ClauseEntry {
    
//=======================================================================
// variables

    /** Rule body */
    protected ClauseEntry[] body;
    
    /** Rule head or set of heads */
    protected ClauseEntry[] head;
    
    /** Optional name for the rule */
    protected String name;
    
    /** The number of distinct variables used in the rule */
    protected int numVars = -1;
    
    /** Flags whether the rule was written as a forward or backward rule */
    protected boolean isBackward = false;
    
    /** Flags whether the rule is monotonic */
    protected boolean isMonotonic = true;
    
    static Log logger = LogFactory.getLog(Rule.class);
    
    /**
     * Constructor
     * @param body a list of TriplePatterns or Functors.
     * @param head a list of TriplePatterns, Functors or rules
     */
    public Rule(List head, List body) {
        this(null, head, body);
    }
    
    /**
     * Constructor
     * @param name a label for rule
     * @param body a list of TriplePatterns or Functors.
     * @param head a list of TriplePatterns, Functors or rules
     */
    public Rule(String name, List head, List body) {
        this(name, 
                (ClauseEntry[]) head.toArray(new ClauseEntry[head.size()]),
                (ClauseEntry[]) body.toArray(new ClauseEntry[body.size()]) );
    }
    
    /**
     * Constructor
     * @param name a label for rule
     * @param body an array of TriplePatterns or Functors.
     * @param head an array of TriplePatterns, Functors or rules
     */
    public Rule(String name, ClauseEntry[] head, ClauseEntry[] body) {
        this.name = name;
        this.head = head;
        this.body = body;
        this.isMonotonic = allMonotonic(head);
    }
    
    // Compute the monotonicity flag
    // Future support for negation would affect this
    private boolean allMonotonic(ClauseEntry[] elts) {
        for (int i = 0; i < elts.length; i++) {
            ClauseEntry elt = elts[i];
            if (elt instanceof Functor) {
                Builtin b = ((Functor)elt).getImplementor();
                if (b != null) {
                    if (! b.isMonotonic() ) return false;
                } else {
                    throw new ReasonerException("Undefined Functor " + ((Functor)elt).getName() +" in " + toShortString());
                }
            }
        }
        return true;
    }
    
//=======================================================================
// accessors

    /**
     * Return the number of body elements
     */
    public int bodyLength() {
        return body.length;
    }
    
    /**
     * Return the n'th body element
     */
    public ClauseEntry getBodyElement(int n) {
        return body[n];
    }
    
    /**
     * return the entire rule body as an array of objects
     */
    public ClauseEntry[] getBody() {
        return body;
    }
        
    
    /**
     * Return the number of head elements
     */
    public int headLength() {
        return head.length;
    }
    
    /**
     * Return the n'th head element
     */
    public ClauseEntry getHeadElement(int n) {
        return head[n];
    }
    
    /**
     * return the entire rule head as an array of objects
     */
    public ClauseEntry[] getHead() {
        return head;
    }
    
    /**
     * Return true if the rule was written as a backward (as opposed to forward) rule.
     */
    public boolean isBackward() {
        return isBackward;
    }
    
    /**
     * Set the rule to be run backwards.
     * @param flag if true the rule should run backwards.
     */
    public void setBackward(boolean flag) {
        isBackward = flag;
    }
    
    /**
     * Get the name for the rule - can be null.
     */
    public String getName() {
        return name;
    }
    
    /**
     * Set the number of distinct variables for this rule.
     * Used internally when cloing rules, not normally required.
     */
    public void setNumVars(int n) {
        numVars = n;
    }
    
    /**
     * Return the number of distinct variables in the rule. Or more precisely, the
     * size of a binding environment needed to represent the rule.
     */
    public int getNumVars() {
        if (numVars == -1) {
            // only have to do this if the rule was generated programatically
            // the parser will have prefilled this in for normal rules
            int max = findVars(body, -1);
            max = findVars(head, max);
            numVars = max + 1;
        }
        return numVars;
    }
    
    /**
     * Find all the variables in a clause array.
     */
    private int findVars(Object[] nodes, int maxIn) {
        int max = maxIn;
        for (int i = 0; i < nodes.length; i++) {
            Object node = nodes[i];
            if (node instanceof TriplePattern) {
                max = findVars((TriplePattern)node, max);
            } else {
                max = findVars((Functor)node, max); 
            }
        }
        return max;
    }
    
    /**
     * Find all the variables in a TriplePattern.
     */
    private int findVars(TriplePattern t, int maxIn) {
        int max = maxIn;
        max = maxVarIndex(t.getSubject(), max);
        max = maxVarIndex(t.getPredicate(), max);
        Node obj = t.getObject();
        if (obj instanceof Node_RuleVariable) {
            max = maxVarIndex(obj, max);
        } else if (Functor.isFunctor(obj)) {
            max = findVars((Functor)obj.getLiteralValue(), max);
        }
        return max;
    }
        
    /**
     * Find all the variables in a Functor.
     */
    private int findVars(Functor f, int maxIn) {
        int max = maxIn;
        Node[] args = f.getArgs();
        for (int i = 0; i < args.length; i++) {
            if (args[i].isVariable()) max = maxVarIndex(args[i], max);
        }
        return max;
    }
    
    /**
     * Return the maximum node index of the variable and the max so far. 
     */
    private int maxVarIndex(Node var, int max) {
        if (var instanceof Node_RuleVariable) {
            int index = ((Node_RuleVariable)var).index;
            if (index > max) return index;            
        }
        return max;
    }
    
    /**
     * Instantiate a rule given a variable binding environment.
     * This will clone any non-bound variables though that is only needed
     * for trail implementations.
     */
    public Rule instantiate(BindingEnvironment env) {
        HashMap vmap = new HashMap();
        return new Rule(name, cloneClauseArray(head, vmap, env), cloneClauseArray(body, vmap, env));
    }
    
    /**
     * Clone a rule, cloning any embedded variables.
     */
    public Rule cloneRule() {
        if (getNumVars() > 0) {
            HashMap vmap = new HashMap();
            return new Rule(name, cloneClauseArray(head, vmap, null), cloneClauseArray(body, vmap, null));
        } else {
            return this;
        }
    }
    
    /**
     * Clone a clause array.
     */
    private ClauseEntry[] cloneClauseArray(ClauseEntry[] clauses, Map vmap, BindingEnvironment env) {
        ClauseEntry[] cClauses = new ClauseEntry[clauses.length];
        for (int i = 0; i < clauses.length; i++ ) {
            cClauses[i] = cloneClause(clauses[i], vmap, env);
        }
        return cClauses;
    }
    
    /**
     * Clone a clause, cloning any embedded variables.
     */
    private ClauseEntry cloneClause(ClauseEntry clause, Map vmap, BindingEnvironment env) {
        if (clause instanceof TriplePattern) {
            TriplePattern tp = (TriplePattern)clause;
            return new TriplePattern (
                            cloneNode(tp.getSubject(), vmap, env),
                            cloneNode(tp.getPredicate(), vmap, env),
                            cloneNode(tp.getObject(), vmap, env)
                        );
        } else {
            return cloneFunctor((Functor)clause, vmap, env);
        }
    }
    
    /**
     * Clone a functor, cloning any embedded variables.
     */
    private Functor cloneFunctor(Functor f, Map vmap, BindingEnvironment env) {
        Node[] args = f.getArgs();
        Node[] cargs = new Node[args.length];
        for (int i = 0; i < args.length; i++) {
            cargs[i] = cloneNode(args[i], vmap, env);
        }
        Functor fn = new Functor(f.getName(), cargs);
        fn.setImplementor(f.getImplementor());
        return fn;
    }
    
    /**
     * Close a single node.
     */
    private Node cloneNode(Node nIn, Map vmap, BindingEnvironment env) {
        Node n = (env == null) ? nIn : env.getGroundVersion(nIn);
        if (n instanceof Node_RuleVariable) {
            Node_RuleVariable nv = (Node_RuleVariable)n;
            Node c = (Node)vmap.get(nv);
            if (c == null) {
                c = ((Node_RuleVariable)n).cloneNode();
                vmap.put(nv, c);
            }
            return c;
        } else if (Functor.isFunctor(n)) {
            Functor f = (Functor)n.getLiteralValue();
            return Functor.makeFunctorNode(cloneFunctor(f, vmap, env));
        } else {
            return n;
        }
    }
    
    /**