bruleengine.java

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

//        // This wasn't any good
//        RuleState next = null;
//        for (Iterator i = agenda.iterator(); i.hasNext(); ) {
//            RuleState item = (RuleState)i.next();
//            if (item.couldProcess()) {
//                next = item;
//                break;
//            }
//        }
//        if (next != null) {
//            agenda.remove(next);
//        } else {
//            next = (RuleState)agenda.removeFirst();
//        }
//        next.isScheduled = false;
//        return next;
//        
//        // This was even worse
//        int maxPending = -1;
//        RuleState best = null;
//        int bestIndex = 0;
//        int limit = Math.min(10, agenda.size());
//        for (int i = 0; i < limit; i++) {
//            RuleState rs = (RuleState)agenda.get(i);
//            GoalState gs = rs.goalState;
//            if (gs != null && gs.results.started) {
//                int pending = gs.results.numResults() - gs.solutionPointer;
//                if (pending > maxPending) {
//                    maxPending = pending;
//                    best = rs;
//                    bestIndex = i;
//                }
//            }
//        }
//        if (best == null) return (RuleState)agenda.removeFirst();
//        agenda.remove(bestIndex);
//        best.isScheduled = false;
//        return best;
    }
    
    /**
     * Return a list of rules that match the given goal entry
     */
    public List rulesFor(TriplePattern goal) {
        return ruleStore.rulesFor(goal);
    }  
    
    /**
     * Return the rule infernce graph that owns this engine.
     */
    public BackwardRuleInfGraphI getInfGraph() {
        return infGraph;  
    }
    
    /**
     * Process a call to a builtin predicate
     * @param clause the Functor representing the call
     * @param env the BindingEnvironment for this call
     * @param rule the rule which is invoking this call
     * @return true if the predicate succeeds
     */
    public boolean processBuiltin(ClauseEntry clause, Rule rule, BindingEnvironment env) {
        return infGraph.processBuiltin(clause, rule, env);
    }
    
    /**
     * The main processing loop. Continues processing agenda items until either
     * a new solution to the top goal has been found or the agenda is empty and
     * so no more solutions are available.
     * 
     * @param topGoalState the top level GoalState whose values are being sought
     * @return null if all processing is complete and no more solutions are
     * available, otherwise returns the next result available for the topGoal.
     */
    public synchronized Triple next(GoalState topGoalState) {
        GoalResults topGoal = topGoalState.getGoalResultsEntry();
        int numResults = 0;
        BindingVector env = null;
        RuleState current = null;
        RuleState continuation = null;
        try {
            while(true) {
//                System.gc();
                boolean foundResult = false;
                RuleState delayedRSClose = null;
                if (current == null) {
                    // Move to the next agenda item
                    // (if empty then an exception is thrown and caught later)
                    current = nextAgendaItem();
                    numResults = 0;
                    if (traceOn) {
                        logger.debug("Waken:   " + current);
                    }
                }
                Object result = current.next();
                if (result == StateFlag.FAIL) {
                    // backtrack, if we fall off the root of this tree then
                    // current will end up as null in which case the loop with
                    // shift to the next agenda item
                    if (traceOn) {
                        logger.debug("Failed");
                    }
                    delayedRSClose = current;
                    current = current.prev;
                } else if (result == StateFlag.SUSPEND) {
                    // Can do no more with this goal
                    if (traceOn) {
                        logger.debug("Suspend: " + current);
                    }
                    GoalResults waitingFor = current.goalState.results;
                    waitingFor.addDependent(current);
                    current = current.prev;
                } else if (result == StateFlag.SATISFIED) {
                    // The rule had no clauses left to check, so return answers
                    foundResult = true;
                    env = current.env;
                    delayedRSClose = current;
                    continuation = current.prev;
                } else {                    // We have a result so continue extending this search tree depth first
                    env = current.newEnvironment((Triple)result);
                    if (env == null) {
                        // failed a functor match - so loop back to look for more results
                        // Might be better to reschedule onto the end of the agenda?
                        continue;
                    }
                    Rule rule = current.ruleInstance.rule;
                    boolean foundGoal = false;
                    int maxClause = rule.bodyLength();
                    int clauseIndex = current.nextClauseIndex();
                    while (clauseIndex < maxClause && !foundGoal) {
                        ClauseEntry clause = rule.getBodyElement(clauseIndex++);
                        if (clause instanceof TriplePattern) {
                            // found next subgoal to try
                            // Push current state onto stack 
                            TriplePattern subgoal = env.partInstantiate((TriplePattern)clause);
                            if (!subgoal.isLegal()) {
                                // branch has failed
                                delayedRSClose = current;
                                current = current.prev;
                            } else {                                
                                current = new RuleState(current, subgoal, clauseIndex, env);
                            }
                            foundGoal = true;
                        } else {
                            if (!infGraph.processBuiltin(clause, rule, env)) {
                                // This branch has failed
                                delayedRSClose = current;
                                current = current.prev;
                                foundGoal = true;
                            }
                        }
                    }
                    if (!foundGoal) {
                        // If we get to here then this branch has completed and we have a result
                        foundResult = true;
                        continuation = current;
                    }
                }
                if (foundResult) {
                    // If we get to here then this branch has completed and we have a result
                    GoalResults resultDest = current.ruleInstance.generator;
                    Triple finalResult = current.getResult(env);
                    if (traceOn) {
                        logger.debug("Result:  " + PrintUtil.print(finalResult) + " <- " + current +", newenv=" + env);
                    }
                    boolean newresult = resultDest.addResult(finalResult);
                    if (delayedRSClose != null) {
                        delayedRSClose.close();
                    }
                    numResults++;
                    current = continuation;
                    nRulesFired++;
                    if (newresult && recordDerivations) {
                        Rule rule = current.ruleInstance.rule;
                        List matchList = new ArrayList(rule.bodyLength());
                        for (int i = 0; i < rule.bodyLength(); i++) {
                            Object clause = rule.getBodyElement(i);
                            if (clause instanceof TriplePattern) {
                                matchList.add(env.instantiate((TriplePattern)clause));
                            } 
                        }

                        RuleDerivation derivation = new RuleDerivation(rule, finalResult, matchList, infGraph);
                        infGraph.logDerivation(finalResult, derivation);
                    }
                    if (newresult && resultDest == topGoal) {
                        // Found a top level goal result so return it now
                        if (current != null) prependToAgenda(current);
                        return finalResult;
                    } else if (numResults > batchSize) {
                        // push the current state lower down agenda and try another
                        if (current != null) appendToAgenda(current);
                        current = null;
                    }
                } else {
                    if (delayedRSClose != null) {
                        delayedRSClose.close();
                    }
                }
            }
        } catch (NoSuchElementException e) {
            // No more agenda items can be processed, so the topGoal is as satisfied as it can be
            if (traceOn) {
                logger.debug("Completed all");
            }
            goalTable.setAllComplete();
            return null;
        }
    }
}



/*
    (c) Copyright 2003, 2004, 2005, 2006, 2007 Hewlett-Packard Development Company, LP
    All rights reserved.

    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions
    are met:

    1. Redistributions of source code must retain the above copyright
       notice, this list of conditions and the following disclaimer.

    2. Redistributions in binary form must reproduce the above copyright
       notice, this list of conditions and the following disclaimer in the
       documentation and/or other materials provided with the distribution.

    3. The name of the author may not be used to endorse or promote products
       derived from this software without specific prior written permission.

    THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/