reteengine.java

jena2.5.4推理机系统的一种最基本实现 HP实验室出品

/******************************************************************
 * File:        RETEEngine.java
 * Created by:  Dave Reynolds
 * Created on:  09-Jun-2003
 * 
 * (c) Copyright 2003, 2004, 2005, 2006, 2007 Hewlett-Packard Development Company, LP
 * [See end of file]
 * $Id: RETEEngine.java,v 1.29 2007/01/02 11:48:41 andy_seaborne Exp $
 *****************************************************************/
package com.hp.hpl.jena.reasoner.rulesys.impl;

import com.hp.hpl.jena.reasoner.*;
import com.hp.hpl.jena.reasoner.rulesys.*;
import com.hp.hpl.jena.graph.*;
import java.util.*;

import com.hp.hpl.jena.util.OneToManyMap;
import com.hp.hpl.jena.util.PrintUtil;
import com.hp.hpl.jena.util.iterator.ConcatenatedIterator;

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

/**
 * A RETE version of the the forward rule system engine. It neeeds to reference
 * an enclosing ForwardInfGraphI which holds the raw data and deductions.
 * 
 * @author <a href="mailto:[e-mail]">Dave Reynolds</a>
 * @version $Revision: 1.29 $ on $Date: 2007/01/02 11:48:41 $
 */
public class RETEEngine implements FRuleEngineI {
    
    /** The parent InfGraph which is employing this engine instance */
    protected ForwardRuleInfGraphI infGraph;
    
    /** Set of rules being used */
    protected List rules;
    
    /** Map from predicate node to clause processor, Node_ANY is used for wildcard predicates */
    protected OneToManyMap clauseIndex;
    
    /** Queue of newly added triples waiting to be processed */
    protected List addsPending = new ArrayList();
    
    /** Queue of newly deleted triples waiting to be processed */
    protected List deletesPending = new ArrayList();
    
    /** The conflict set of rules waiting to fire */
    protected RETEConflictSet conflictSet;
    
    /** List of predicates used in rules to assist in fast data loading */
    protected HashSet predicatesUsed;
    
    /** Flag, if true then there is a wildcard predicate in the rule set so that selective insert is not useful */
    protected boolean wildcardRule;
     
    /** Set to true to flag that derivations should be logged */
    protected boolean recordDerivations;
    
    /** performance stats - number of rules fired */
    long nRulesFired = 0;
    
    /** True if we have processed the axioms in the rule set */
    boolean processedAxioms = false;
    
    /** True if all the rules are monotonic, so we short circuit the conflict set processing */
    boolean isMonotonic = true;
    
    protected static Log logger = LogFactory.getLog(FRuleEngine.class);
    
//  =======================================================================
//  Constructors

    /**
     * Constructor.
     * @param parent the F or FB infGraph that it using this engine, the parent graph
     * holds the deductions graph and source data.
     * @param rules the rule set to be processed
     */
    public RETEEngine(ForwardRuleInfGraphI parent, List rules) {
        infGraph = parent;
        this.rules = rules;
        // Check if this is a monotonic rule set
        isMonotonic = true;
        for (Iterator i = rules.iterator(); i.hasNext(); ) {
            Rule r = (Rule)i.next();
            if ( ! r.isMonotonic() ) {
                isMonotonic = false;
                break;
            }
        }
    }

    /**
     * Constructor. Build an empty engine to which rules must be added
     * using setRuleStore().
     * @param parent the F or FB infGraph that it using this engine, the parent graph
     * holds the deductions graph and source data.
     */
    public RETEEngine(ForwardRuleInfGraphI parent) {
        infGraph = parent;
    }
    
//  =======================================================================
//  Control methods

    /**
     * Process all available data. This should be called once a deductions graph
     * has be prepared and loaded with any precomputed deductions. It will process
     * the rule axioms and all relevant existing exiting data entries.
     * @param ignoreBrules set to true if rules written in backward notation should be ignored
     * @param inserts the set of triples to be processed, normally this is the
     * raw data graph but may include additional deductions made by preprocessing hooks
     */
    public void init(boolean ignoreBrules, Finder inserts) {
        compile(rules, ignoreBrules);
        findAndProcessAxioms();
        fastInit(inserts);
    }
    
    /**
     * Process all available data. This version expects that all the axioms 
     * have already be preprocessed and the clause index already exists.
     * @param inserts the set of triples to be processed, normally this is the
     * raw data graph but may include additional deductions made by preprocessing hooks
     */
    public void fastInit(Finder inserts) {
        conflictSet = new RETEConflictSet(new RETERuleContext(infGraph, this), isMonotonic);
        // Below is used during testing to ensure that all ruleset work (if less efficiently) if marked as non-monotonic
//        conflictSet = new RETEConflictSet(new RETERuleContext(infGraph, this), false);
        findAndProcessActions();
        if (infGraph.getRawGraph() != null) {
            // Insert the data
            if (wildcardRule) {
                for (Iterator i = inserts.find(new TriplePattern(null, null, null)); i.hasNext(); ) {
                    addTriple((Triple)i.next(), false);
                }
            } else {
                for (Iterator p = predicatesUsed.iterator(); p.hasNext(); ) {
                    Node predicate = (Node)p.next();
                    for (Iterator i = inserts.find(new TriplePattern(null, predicate, null)); i.hasNext(); ) {
                        Triple t = (Triple)i.next();
                        addTriple(t, false);
                    }
                }
            }
        }
        // Run the engine
        runAll();
    }

    /**
     * Add one triple to the data graph, run any rules triggered by
     * the new data item, recursively adding any generated triples.
     */
    public synchronized void add(Triple t) {
        addTriple(t, false);
        runAll();
    }
    
    /**
     * Remove one triple to the data graph.
     * @return true if the effects could be correctly propagated or
     * false if not (in which case the entire engine should be restarted).
     */
    public synchronized boolean delete(Triple t) {
        deleteTriple(t, false);
        runAll();
        return true;
    }
    
    /**
     * Return the number of rules fired since this rule engine instance
     * was created and initialized
     */
    public long getNRulesFired() {
        return nRulesFired;
    }
    
    /**
     * Return true if the internal engine state means that tracing is worthwhile.
     * It will return false during the axiom bootstrap phase.
     */
    public boolean shouldTrace() {
        return true;
//        return processedAxioms;
    }

    /**
     * Set to true to enable derivation caching
     */
    public void setDerivationLogging(boolean recordDerivations) {
        this.recordDerivations = recordDerivations;
    }
    
    /**
     * Access the precomputed internal rule form. Used when precomputing the
     * internal axiom closures.
     */
    public Object getRuleStore() {
        return new RuleStore(clauseIndex, predicatesUsed, wildcardRule, isMonotonic);
    }
    
    /**
     * Set the internal rule from from a precomputed state.
     */
    public void setRuleStore(Object ruleStore) {
        RuleStore rs = (RuleStore)ruleStore;
        predicatesUsed = rs.predicatesUsed;
        wildcardRule = rs.wildcardRule;
        isMonotonic = rs.isMonotonic;
        
        // Clone the RETE network to this engine
        RETERuleContext context = new RETERuleContext(infGraph, this);
        Map netCopy = new HashMap();
        clauseIndex = new OneToManyMap();
        for (Iterator i = rs.clauseIndex.entrySet().iterator(); i.hasNext(); ) {
            Map.Entry entry = (Map.Entry)i.next();
            clauseIndex.put(entry.getKey(), ((RETENode)entry.getValue()).clone(netCopy, context));
        }
    }
    
    /**
     * Add a rule firing request to the conflict set.
     */
    public void requestRuleFiring(Rule rule, BindingEnvironment env, boolean isAdd) {
        conflictSet.add(rule, env, isAdd);
    }
    
//  =======================================================================
//  Compiler support  

    /**
     * Compile a list of rules into the internal rule store representation.
     * @param rules the list of Rule objects
     * @param ignoreBrules set to true if rules written in backward notation should be ignored
     */
    public void compile(List rules, boolean ignoreBrules) {
        clauseIndex = new OneToManyMap();
        predicatesUsed = new HashSet();
        wildcardRule = false;
            
        for (Iterator it = rules.iterator(); it.hasNext(); ) {
            Rule rule = (Rule)it.next();
            if (ignoreBrules && rule.isBackward()) continue;
            
            int numVars = rule.getNumVars();
            boolean[] seenVar = new boolean[numVars];
            RETESourceNode prior = null;
        
            for (int i = 0; i < rule.bodyLength(); i++) {
                Object clause = rule.getBodyElement(i);
                if (clause instanceof TriplePattern) {
                    // Create the filter node for this pattern
                    ArrayList clauseVars = new ArrayList(numVars);
                    RETEClauseFilter clauseNode = RETEClauseFilter.compile((TriplePattern)clause, numVars, clauseVars);
                    Node predicate = ((TriplePattern)clause).getPredicate();
                    if (predicate.isVariable()) {
                        clauseIndex.put(Node.ANY, clauseNode);
                        wildcardRule = true;
                    } else {
                        clauseIndex.put(predicate, clauseNode);
                        if (! wildcardRule) {
                            predicatesUsed.add(predicate);
                        }
                    }
                
                    // Create list of variables which should be cross matched between the earlier clauses and this one
                    ArrayList matchIndices = new ArrayList(numVars);
                    for (Iterator iv = clauseVars.iterator(); iv.hasNext(); ) {
                        int varIndex = ((Node_RuleVariable)iv.next()).getIndex();
                        if (seenVar[varIndex]) matchIndices.add(new Byte((byte)varIndex));
                        seenVar[varIndex] = true;
                    }
                
                    // Build the join node
                    if (prior == null) {
                        // First clause, no joins yet
                        prior = clauseNode;
                    } else {
                        RETEQueue leftQ = new RETEQueue(matchIndices);
                        RETEQueue rightQ = new RETEQueue(matchIndices);
                        leftQ.setSibling(rightQ);
                        rightQ.setSibling(leftQ);
                        clauseNode.setContinuation(rightQ);
                        prior.setContinuation(leftQ);
                        prior = leftQ;
                    }
                }
            }