lpinterpreter.java

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

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

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

import java.util.*;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * Bytecode interpeter engine for the LP version of the backward
 * chaining rule system. An instance of this is forked off for each
 * parallel query.
 * 
 * @author <a href="mailto:[e-mail]">Dave Reynolds</a>
 * @version $Revision: 1.14 $ on $Date: 2007/01/02 11:48:41 $
 */
public class LPInterpreter {

    //  =======================================================================
    //  Variables

    /** The engine which is using this interpreter */
    protected LPBRuleEngine engine;

    /** The execution context that should be notified of suspended branches */
    protected LPInterpreterContext iContext;
    
    /** True if the engine has terminated */
    protected boolean isComplete = false;

    /** The set of temporary variables (Ti) in use by this interpreter */
    protected Node[] tVars = new Node[RuleClauseCode.MAX_TEMPORARY_VARS];

    /** The set of argument variables (Ai) in use by this interpreter */
    protected Node[] argVars = new Node[RuleClauseCode.MAX_ARGUMENT_VARS];
        
    /** The set of "permanent" variables (Yi) in use by this interpreter */
    protected Node[] pVars = null;

    /** The current environment frame */
    protected EnvironmentFrame envFrame;

    /** The current choice point frame */
    protected FrameObject cpFrame;
    
    /** The trail of variable bindings that have to be unwound on backtrack */
    protected ArrayList trail = new ArrayList();

    /** The execution context description to be passed to builtins */
    protected RuleContext context;
        
    /** Trick to allow the very top level triple lookup to return results with reduced store turnover */
    protected TopLevelTripleMatchFrame topTMFrame;
    
    /** Original set up goal, only used for debugging */
    protected TriplePattern goal;
        
    static Log logger = LogFactory.getLog(LPInterpreter.class);

    //  =======================================================================
    //  Constructors

    /**
     * Constructor used to construct top level calls.
     * @param engine the engine which is calling this interpreter
     * @param goal the query to be satisfied
     */
    public LPInterpreter(LPBRuleEngine engine, TriplePattern goal) {
        this(engine, goal, engine.getRuleStore().codeFor(goal), true);
    }


    /**
     * Constructor.
     * @param engine the engine which is calling this interpreter
     * @param goal the query to be satisfied
     * @param isTop true if this is a top level call from the outside iterator, false means it is an
     * internal generator call which means we don't need to insert an tabled call
     */
    public LPInterpreter(LPBRuleEngine engine, TriplePattern goal, boolean isTop) {
        this(engine, goal, engine.getRuleStore().codeFor(goal), isTop);
    }
    
    /**
     * Constructor.
     * @param engine the engine which is calling this interpreter
     * @param goal the query to be satisfied
     * @param clauses the set of code blocks needed to implement this goal
     * @param isTop true if this is a top level call from the outside iterator, false means it is an
     * internal generator call which means we don't need to insert an tabled call
     */
    public LPInterpreter(LPBRuleEngine engine, TriplePattern goal, List clauses, boolean isTop) {
        this.engine = engine;
        this.goal = goal;       // Used for debug only
        
        // Construct dummy top environemnt which is a call into the clauses for this goal
        if (engine.getDerivationLogging()) {
            envFrame = new EnvironmentFrameWithDerivation(RuleClauseCode.returnCodeBlock);
        } else {
            envFrame = new EnvironmentFrame(RuleClauseCode.returnCodeBlock);
        }
        envFrame.allocate(RuleClauseCode.MAX_PERMANENT_VARS);
        HashMap mappedVars = new HashMap();
        envFrame.pVars[0] = argVars[0] = standardize(goal.getSubject(), mappedVars);
        envFrame.pVars[1] = argVars[1] = standardize(goal.getPredicate(), mappedVars);
        envFrame.pVars[2] = argVars[2] = standardize(goal.getObject(), mappedVars);
        if (engine.getDerivationLogging()) {
            ((EnvironmentFrameWithDerivation)envFrame).initDerivationRecord(argVars);
        }
        
        if (clauses != null && clauses.size() > 0) {
            if (isTop && engine.getRuleStore().isTabled(goal)) {
                setupTabledCall(0, 0);
//                setupClauseCall(0, 0, clauses);
            } else {
                setupClauseCall(0, 0, clauses, goal.isGround());
            }
        }
        
//        TripleMatchFrame tmFrame = new TripleMatchFrame(this);
        topTMFrame = new TopLevelTripleMatchFrame(this, goal);
        topTMFrame.linkTo(cpFrame);
        topTMFrame.setContinuation(0, 0);
        cpFrame = topTMFrame;
    }

    /**
     * Called by top level interpeter to set to execution context for this interpeter to be
     * top level instead of an internal generator.
     */
    public void setTopInterpreter(LPInterpreterContext context) {
        iContext = context;
        FrameObject topChoice = topTMFrame.getLink();
        if (topChoice instanceof ConsumerChoicePointFrame) {
            ((ConsumerChoicePointFrame)topChoice).context = context;
        }
    }
    
    //  =======================================================================
    //  Control methods

    /**
     * Stop the current work. This is called if the top level results iterator has
     * either finished or the calling application has had enough. 
     */
    public void close() {
        synchronized (engine) {
            isComplete = true;
            engine.detach(this);
            if (cpFrame != null) cpFrame.close();
        }
    }
    
    /**
     * Start the interpreter running with the given context.
     */
    public void setState(LPInterpreterState state) {
        if (state instanceof ConsumerChoicePointFrame) {
            restoreState((ConsumerChoicePointFrame) state);
        } else {
            iContext = (LPInterpreterContext) state;
        }
    }
    /**
     * Return the next result from this engine, no further initialization.
     * Should be called from within an appropriately synchronized block.
     * @param context the generator choice point or top level iterator which 
     * is requesting this result and might have preserved state to restore
     * @return either a StateFlag or  a result Triple
     */
    public Object next() {
        boolean traceOn = engine.isTraceOn();
        
//        System.out.println("next() on interpeter for goal " + goal); 
        StateFlag answer = run();
//        System.out.println("end next() on interpeter for goal " + goal);
        
        if (answer == StateFlag.FAIL || answer == StateFlag.SUSPEND) {
            return answer;
        } else if (answer == StateFlag.SATISFIED) {
            if (traceOn) logger.info("RETURN: " + topTMFrame.lastMatch);
            return topTMFrame.lastMatch;
        } else {
            Triple t = new Triple(deref(pVars[0]), deref(pVars[1]), derefPossFunctor(pVars[2]));
            if (traceOn) logger.info("RETURN: " + t);
            return t;
        }
    }
    
    /**
     * Preserve the current interpreter state in the given 
     * @return
     */
    /**
     * Return the engine which owns this interpreter.
     */
    public LPBRuleEngine getEngine() {
        return engine;
    }
    
    /**
     * Return the current choice point frame that can be used to restart the
     * interpter at this point.
     */
    public FrameObject getChoiceFrame() {
        return cpFrame;
    }
    
    /**
     * Return the context in which this interpreter is running, that is
     * either the Generator for a tabled goal or a top level iterator.
     */
    public LPInterpreterContext getContext() {
        return iContext;
    }
    
    //  =======================================================================
    //  Engine implementation  
 
    /**
     * Restore the current choice point and restart execution of the LP code
     * until either find a successful branch (in which case exit with StateFlag.ACTIVE
     * and variables bound to the correct results) or exhaust all choice points (in
     * which case exit with StateFlag.FAIL and no bound results). In future tabled
     * version could also exit with StateFlag.SUSPEND in cases whether the intepreter
     * needs to suspend to await tabled results from a parallel proof tree.
     */
    protected StateFlag run() {
        int pc = 0;     // Program code counter
        int ac = 0;     // Program arg code counter
        RuleClauseCode clause = null;       // The clause being executed
        ChoicePointFrame choice = null;
        byte[] code;
        Object[] args;
        boolean traceOn = engine.isTraceOn();
        boolean recordDerivations = engine.getDerivationLogging();
        
        main: while (cpFrame != null) {
            // restore choice point
            if (cpFrame instanceof ChoicePointFrame) {
                choice = (ChoicePointFrame)cpFrame;
                if (!choice.hasNext()) {
                    // No more choices left in this choice point
                    cpFrame = choice.getLink();
                    if (traceOn) logger.info("FAIL in clause " + choice.envFrame.clause + " choices exhausted");
                    continue main;
                }
                
                clause = (RuleClauseCode)choice.nextClause();
                // Create an execution environment for the new choice of clause
                if (recordDerivations) {
                    envFrame = new EnvironmentFrameWithDerivation(clause);
                } else {
                    envFrame = new EnvironmentFrame(clause);
                }
                envFrame.linkTo(choice.envFrame);
                envFrame.cpc = choice.cpc;
                envFrame.cac = choice.cac;
                
                // Restore the choice point state
                System.arraycopy(choice.argVars, 0, argVars, 0, RuleClauseCode.MAX_ARGUMENT_VARS);
                int trailMark = choice.trailIndex;
                if (trailMark < trail.size()) {
                    unwindTrail(trailMark);
                }
                pc = ac = 0;
                if (recordDerivations) {
                    ((EnvironmentFrameWithDerivation)envFrame).initDerivationRecord(argVars);
                }
                
                if (traceOn) logger.info("ENTER " + clause + " : " + getArgTrace());
                
                // then fall through into the recreated execution context for the new call
                
            } else if (cpFrame instanceof TripleMatchFrame) {