001: /******************************************************************
002: * File: Agenda.java
003: * Created by: Dave Reynolds
004: * Created on: 11-May-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: BRuleEngine.java,v 1.8 2008/01/02 12:09:45 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl.oldCode;
010:
011: import com.hp.hpl.jena.reasoner.rulesys.*;
012: import com.hp.hpl.jena.reasoner.rulesys.impl.BindingVector;
013: import com.hp.hpl.jena.reasoner.rulesys.impl.RuleStore;
014: import com.hp.hpl.jena.reasoner.rulesys.impl.StateFlag;
015: import com.hp.hpl.jena.reasoner.*;
016: import com.hp.hpl.jena.util.PrintUtil;
017: import com.hp.hpl.jena.graph.*;
018:
019: import org.apache.commons.logging.Log;
020: import org.apache.commons.logging.LogFactory;
021:
022: import java.util.*;
023:
024: /**
025: * Part of the backward chaining rule interpreter. Maintains an agenda containing
026: * an ordered list of RuleStates awaiting processing (each RuleState
027: * represents the tip of a partially expanded search tree).
028: * <p>
029: * This object does the top level scheduling of rule processing. By default
030: * it batches up several results from the top rule in the agenda before
031: * switching to expand other trees. The size of this batch is adjustable.
032: * </p>
033: *
034: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
035: * @version $Revision: 1.8 $ on $Date: 2008/01/02 12:09:45 $
036: */
037: public class BRuleEngine {
038:
039: // =======================================================================
040: // Variables
041:
042: /** a list of active RuleStates to be processed */
043: protected LinkedList agenda = new LinkedList();
044:
045: // /** the RuleState currently being procssed */
046: // protected RuleState current;
047:
048: /** The table of all goals */
049: protected GoalTable goalTable;
050:
051: /** The inference graph which is using this engine - used for calling builtins */
052: protected BackwardRuleInfGraphI infGraph;
053:
054: /** Indexed version of the rule set */
055: protected RuleStore ruleStore;
056:
057: /** True if debug information should be written out */
058: protected boolean traceOn = false;
059:
060: /** Set to true to flag that derivations should be logged */
061: protected boolean recordDerivations;
062:
063: /** performance stats - number of rules fired */
064: protected long nRulesFired = 0;
065:
066: /** The size of the result batch permitted before a rule should
067: * reschedule itself lower on the agenda */
068: protected int batchSize = 100000;
069:
070: static Log logger = LogFactory.getLog(BRuleEngine.class);
071:
072: // =======================================================================
073: // Constructors
074:
075: /**
076: * Constructor.
077: * @param infGraph the parent inference graph which is using this engine
078: * @param rules the indexed set of rules to process
079: */
080: public BRuleEngine(BackwardRuleInfGraphI infGraph, RuleStore rules) {
081: this .infGraph = infGraph;
082: goalTable = new GoalTable(this );
083: ruleStore = rules;
084: }
085:
086: /**
087: * Constructor. Creates an empty engine to which rules must be added.
088: * @param infGraph the parent inference graph which is using this engine
089: */
090: public BRuleEngine(BackwardRuleInfGraphI infGraph) {
091: this .infGraph = infGraph;
092: goalTable = new GoalTable(this );
093: ruleStore = new RuleStore();
094: }
095:
096: // =======================================================================
097: // Control methods
098:
099: /**
100: * Clear all tabled results.
101: */
102: public synchronized void reset() {
103: agenda.clear();
104: goalTable.reset();
105: }
106:
107: /**
108: * Add a single rule to the store.
109: * N.B. This will invalidate current partial results and the engine
110: * should be reset() before future queries.
111: */
112: public void addRule(Rule rule) {
113: // System.out.println("Adding rule: " + rule);
114: ruleStore.addRule(rule);
115: }
116:
117: /**
118: * Remove a single rule from the store.
119: * N.B. This will invalidate current partial results and the engine
120: * should be reset() before future queries.
121: */
122: public void deleteRule(Rule rule) {
123: ruleStore.deleteRule(rule);
124: }
125:
126: /**
127: * Return an ordered list of all registered rules.
128: */
129: public List getAllRules() {
130: return ruleStore.getAllRules();
131: }
132:
133: /**
134: * Delete all the rules.
135: */
136: public void deleteAllRules() {
137: ruleStore.deleteAllRules();
138: }
139:
140: /**
141: * Stop the current work. This is called if the top level results iterator has
142: * either finished or the calling application has had enough. We leave any completed
143: * results in the GoalTable but clear out the agenda and all non-compelted results.
144: */
145: public synchronized void halt() {
146: // Clear agenda
147: for (Iterator i = agenda.iterator(); i.hasNext();) {
148: RuleState item = (RuleState) i.next();
149: // don't call item.close(), that would update the ref count and set a completion flag
150: if (item.goalState != null)
151: item.goalState.close();
152: }
153: agenda.clear();
154: // Clear the goal table
155: goalTable.removePartialGoals();
156: }
157:
158: /**
159: * Find the set of memoized solutions for the given goal
160: * and return a GoalState that can traverse all the solutions.
161: *
162: * @param goal the goal to be solved
163: * @return a GoalState which can iterate over all of the goal solutions
164: */
165: public synchronized GoalState findGoal(TriplePattern goal) {
166: return goalTable.findGoal(goal);
167: }
168:
169: /**
170: * Set the state of the trace flag. If set to true then rule firings
171: * are logged out to the Log at "INFO" level.
172: */
173: public void setTraceOn(boolean state) {
174: traceOn = state;
175: }
176:
177: /**
178: * Return true if traces of rule firings should be logged.
179: */
180: public boolean isTraceOn() {
181: return traceOn;
182: }
183:
184: /**
185: * Return the number of rules fired since this rule engine instance
186: * was created and initialized
187: */
188: public long getNRulesFired() {
189: return nRulesFired;
190: }
191:
192: /**
193: * Set to true to enable derivation caching
194: */
195: public void setDerivationLogging(boolean recordDerivations) {
196: this .recordDerivations = recordDerivations;
197: }
198:
199: /**
200: * Dump an a summary of the goal table state to stdout.
201: * Just debugging, do not use for real.
202: */
203: public void dump() {
204: goalTable.dump();
205: }
206:
207: // =======================================================================
208: // Engine implementation
209:
210: /**
211: * Append a new rule node to the end of the agenda.
212: */
213: public synchronized void appendToAgenda(RuleState rs) {
214: if (!rs.isScheduled) {
215: if (traceOn) {
216: // logger.debug("append to agenda: " + rs);
217: }
218: agenda.add(rs);
219: rs.isScheduled = true;
220: }
221: }
222:
223: /**
224: * Prepend a new rule node to the head of the agenda.
225: */
226: public synchronized void prependToAgenda(RuleState rs) {
227: if (!rs.isScheduled) {
228: if (traceOn) {
229: // logger.debug("prepend to agenda: " + rs);
230: }
231: agenda.add(0, rs);
232: rs.isScheduled = true;
233: }
234: }
235:
236: /**
237: * Get next agenda item. May do heuristic selection of next item to process.
238: */
239: public RuleState nextAgendaItem() {
240: RuleState next = (RuleState) agenda.removeFirst();
241: next.isScheduled = false;
242: return next;
243:
244: // // This wasn't any good
245: // RuleState next = null;
246: // for (Iterator i = agenda.iterator(); i.hasNext(); ) {
247: // RuleState item = (RuleState)i.next();
248: // if (item.couldProcess()) {
249: // next = item;
250: // break;
251: // }
252: // }
253: // if (next != null) {
254: // agenda.remove(next);
255: // } else {
256: // next = (RuleState)agenda.removeFirst();
257: // }
258: // next.isScheduled = false;
259: // return next;
260: //
261: // // This was even worse
262: // int maxPending = -1;
263: // RuleState best = null;
264: // int bestIndex = 0;
265: // int limit = Math.min(10, agenda.size());
266: // for (int i = 0; i < limit; i++) {
267: // RuleState rs = (RuleState)agenda.get(i);
268: // GoalState gs = rs.goalState;
269: // if (gs != null && gs.results.started) {
270: // int pending = gs.results.numResults() - gs.solutionPointer;
271: // if (pending > maxPending) {
272: // maxPending = pending;
273: // best = rs;
274: // bestIndex = i;
275: // }
276: // }
277: // }
278: // if (best == null) return (RuleState)agenda.removeFirst();
279: // agenda.remove(bestIndex);
280: // best.isScheduled = false;
281: // return best;
282: }
283:
284: /**
285: * Return a list of rules that match the given goal entry
286: */
287: public List rulesFor(TriplePattern goal) {
288: return ruleStore.rulesFor(goal);
289: }
290:
291: /**
292: * Return the rule infernce graph that owns this engine.
293: */
294: public BackwardRuleInfGraphI getInfGraph() {
295: return infGraph;
296: }
297:
298: /**
299: * Process a call to a builtin predicate
300: * @param clause the Functor representing the call
301: * @param env the BindingEnvironment for this call
302: * @param rule the rule which is invoking this call
303: * @return true if the predicate succeeds
304: */
305: public boolean processBuiltin(ClauseEntry clause, Rule rule,
306: BindingEnvironment env) {
307: return infGraph.processBuiltin(clause, rule, env);
308: }
309:
310: /**
311: * The main processing loop. Continues processing agenda items until either
312: * a new solution to the top goal has been found or the agenda is empty and
313: * so no more solutions are available.
314: *
315: * @param topGoalState the top level GoalState whose values are being sought
316: * @return null if all processing is complete and no more solutions are
317: * available, otherwise returns the next result available for the topGoal.
318: */
319: public synchronized Triple next(GoalState topGoalState) {
320: GoalResults topGoal = topGoalState.getGoalResultsEntry();
321: int numResults = 0;
322: BindingVector env = null;
323: RuleState current = null;
324: RuleState continuation = null;
325: try {
326: while (true) {
327: // System.gc();
328: boolean foundResult = false;
329: RuleState delayedRSClose = null;
330: if (current == null) {
331: // Move to the next agenda item
332: // (if empty then an exception is thrown and caught later)
333: current = nextAgendaItem();
334: numResults = 0;
335: if (traceOn) {
336: logger.debug("Waken: " + current);
337: }
338: }
339: Object result = current.next();
340: if (result == StateFlag.FAIL) {
341: // backtrack, if we fall off the root of this tree then
342: // current will end up as null in which case the loop with
343: // shift to the next agenda item
344: if (traceOn) {
345: logger.debug("Failed");
346: }
347: delayedRSClose = current;
348: current = current.prev;
349: } else if (result == StateFlag.SUSPEND) {
350: // Can do no more with this goal
351: if (traceOn) {
352: logger.debug("Suspend: " + current);
353: }
354: GoalResults waitingFor = current.goalState.results;
355: waitingFor.addDependent(current);
356: current = current.prev;
357: } else if (result == StateFlag.SATISFIED) {
358: // The rule had no clauses left to check, so return answers
359: foundResult = true;
360: env = current.env;
361: delayedRSClose = current;
362: continuation = current.prev;
363: } else { // We have a result so continue extending this search tree depth first
364: env = current.newEnvironment((Triple) result);
365: if (env == null) {
366: // failed a functor match - so loop back to look for more results
367: // Might be better to reschedule onto the end of the agenda?
368: continue;
369: }
370: Rule rule = current.ruleInstance.rule;
371: boolean foundGoal = false;
372: int maxClause = rule.bodyLength();
373: int clauseIndex = current.nextClauseIndex();
374: while (clauseIndex < maxClause && !foundGoal) {
375: ClauseEntry clause = rule
376: .getBodyElement(clauseIndex++);
377: if (clause instanceof TriplePattern) {
378: // found next subgoal to try
379: // Push current state onto stack
380: TriplePattern subgoal = env
381: .partInstantiate((TriplePattern) clause);
382: if (!subgoal.isLegal()) {
383: // branch has failed
384: delayedRSClose = current;
385: current = current.prev;
386: } else {
387: current = new RuleState(current,
388: subgoal, clauseIndex, env);
389: }
390: foundGoal = true;
391: } else {
392: if (!infGraph.processBuiltin(clause, rule,
393: env)) {
394: // This branch has failed
395: delayedRSClose = current;
396: current = current.prev;
397: foundGoal = true;
398: }
399: }
400: }
401: if (!foundGoal) {
402: // If we get to here then this branch has completed and we have a result
403: foundResult = true;
404: continuation = current;
405: }
406: }
407: if (foundResult) {
408: // If we get to here then this branch has completed and we have a result
409: GoalResults resultDest = current.ruleInstance.generator;
410: Triple finalResult = current.getResult(env);
411: if (traceOn) {
412: logger.debug("Result: "
413: + PrintUtil.print(finalResult) + " <- "
414: + current + ", newenv=" + env);
415: }
416: boolean newresult = resultDest
417: .addResult(finalResult);
418: if (delayedRSClose != null) {
419: delayedRSClose.close();
420: }
421: numResults++;
422: current = continuation;
423: nRulesFired++;
424: if (newresult && recordDerivations) {
425: Rule rule = current.ruleInstance.rule;
426: List matchList = new ArrayList(rule
427: .bodyLength());
428: for (int i = 0; i < rule.bodyLength(); i++) {
429: Object clause = rule.getBodyElement(i);
430: if (clause instanceof TriplePattern) {
431: matchList
432: .add(env
433: .instantiate((TriplePattern) clause));
434: }
435: }
436:
437: RuleDerivation derivation = new RuleDerivation(
438: rule, finalResult, matchList, infGraph);
439: infGraph.logDerivation(finalResult, derivation);
440: }
441: if (newresult && resultDest == topGoal) {
442: // Found a top level goal result so return it now
443: if (current != null)
444: prependToAgenda(current);
445: return finalResult;
446: } else if (numResults > batchSize) {
447: // push the current state lower down agenda and try another
448: if (current != null)
449: appendToAgenda(current);
450: current = null;
451: }
452: } else {
453: if (delayedRSClose != null) {
454: delayedRSClose.close();
455: }
456: }
457: }
458: } catch (NoSuchElementException e) {
459: // No more agenda items can be processed, so the topGoal is as satisfied as it can be
460: if (traceOn) {
461: logger.debug("Completed all");
462: }
463: goalTable.setAllComplete();
464: return null;
465: }
466: }
467: }
468:
469: /*
470: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
471: All rights reserved.
472:
473: Redistribution and use in source and binary forms, with or without
474: modification, are permitted provided that the following conditions
475: are met:
476:
477: 1. Redistributions of source code must retain the above copyright
478: notice, this list of conditions and the following disclaimer.
479:
480: 2. Redistributions in binary form must reproduce the above copyright
481: notice, this list of conditions and the following disclaimer in the
482: documentation and/or other materials provided with the distribution.
483:
484: 3. The name of the author may not be used to endorse or promote products
485: derived from this software without specific prior written permission.
486:
487: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
488: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
489: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
490: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
491: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
492: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
493: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
494: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
495: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
496: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
497: */
|