001: /******************************************************************
002: * File: LPBRuleEngine.java
003: * Created by: Dave Reynolds
004: * Created on: 21-Jul-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: LPBRuleEngine.java,v 1.13 2008/01/02 12:06:16 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import com.hp.hpl.jena.graph.*;
012: import com.hp.hpl.jena.reasoner.*;
013: import com.hp.hpl.jena.reasoner.rulesys.*;
014: import com.hp.hpl.jena.util.iterator.*;
015:
016: import org.apache.commons.logging.Log;
017: import org.apache.commons.logging.LogFactory;
018: import java.util.*;
019:
020: /**
021: * LP version of the core backward chaining engine. For each parent inference
022: * graph (whether pure backward or hybrid) there should be one LPBRuleEngine
023: * instance. The shared instance holds any common result caching, rule store
024: * and global state data. However, all the processing is done by instances
025: * of the LPInterpreter - one per query.
026: *
027: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
028: * @version $Revision: 1.13 $ on $Date: 2008/01/02 12:06:16 $
029: */
030: public class LPBRuleEngine {
031:
032: // =======================================================================
033: // variables
034:
035: /** Store which holds the raw and compiled rules */
036: protected LPRuleStore ruleStore;
037:
038: /** The parent inference graph to which this engine is attached */
039: protected BackwardRuleInfGraphI infGraph;
040:
041: /** True if debug information should be written out */
042: protected boolean traceOn = false;
043:
044: /** Set to true to flag that derivations should be logged */
045: protected boolean recordDerivations;
046:
047: /** List of engine instances which are still processing queries */
048: protected List activeInterpreters = new ArrayList();
049:
050: /** Table mapping tabled goals to generators for those goals.
051: * This is here so that partial goal state can be shared across multiple queries. */
052: protected HashMap tabledGoals = new HashMap();
053:
054: /** Set of generators waiting to be run */
055: protected LinkedList agenda = new LinkedList();
056: // protected List agenda = new ArrayList();
057: // protected Collection agenda = new HashSet();
058:
059: /** Optional profile of number of time each rule is entered, set to non-null to profile */
060: protected HashMap profile;
061:
062: /** The number of generator cycles to wait before running a completion check.
063: * If set to 0 then checks will be done in the generator each time. */
064: public static final int CYCLES_BETWEEN_COMPLETION_CHECK = 3;
065:
066: static Log logger = LogFactory.getLog(LPBRuleEngine.class);
067:
068: // =======================================================================
069: // Constructors
070:
071: /**
072: * Constructor.
073: * @param infGraph the parent inference graph which is using this engine
074: * @param rules the indexed set of rules to process
075: */
076: public LPBRuleEngine(BackwardRuleInfGraphI infGraph,
077: LPRuleStore rules) {
078: this .infGraph = infGraph;
079: ruleStore = rules;
080: }
081:
082: /**
083: * Constructor. Creates an empty engine to which rules must be added.
084: * @param infGraph the parent inference graph which is using this engine
085: */
086: public LPBRuleEngine(BackwardRuleInfGraphI infGraph) {
087: this .infGraph = infGraph;
088: ruleStore = new LPRuleStore();
089: }
090:
091: // =======================================================================
092: // Control methods
093:
094: /**
095: * Start a new interpreter running to answer a query.
096: * @param goal the query to be processed
097: * @return a closable iterator over the query results
098: */
099: public synchronized ExtendedIterator find(TriplePattern goal) {
100: LPInterpreter interpreter = new LPInterpreter(this , goal);
101: activeInterpreters.add(interpreter);
102: return WrappedIterator
103: .create(new LPTopGoalIterator(interpreter));
104: }
105:
106: /**
107: * Clear all tabled results.
108: */
109: public synchronized void reset() {
110: checkSafeToUpdate();
111: tabledGoals = new HashMap();
112: agenda.clear();
113: }
114:
115: /**
116: * Add a single rule to the store.
117: * N.B. This will invalidate current partial results and the engine
118: * should be reset() before future queries.
119: */
120: public synchronized void addRule(Rule rule) {
121: checkSafeToUpdate();
122: if (rule.headLength() > 1) {
123: throw new ReasonerException(
124: "Backward rules only allowed one head clause");
125: }
126: ruleStore.addRule(rule);
127: }
128:
129: /**
130: * Remove a single rule from the store.
131: * N.B. This will invalidate current partial results and the engine
132: * should be reset() before future queries.
133: */
134: public synchronized void deleteRule(Rule rule) {
135: checkSafeToUpdate();
136: ruleStore.deleteRule(rule);
137: }
138:
139: /**
140: * Return an ordered list of all registered rules.
141: */
142: public synchronized List getAllRules() {
143: checkSafeToUpdate();
144: return ruleStore.getAllRules();
145: }
146:
147: /**
148: * Delete all the rules.
149: */
150: public synchronized void deleteAllRules() {
151: checkSafeToUpdate();
152: ruleStore.deleteAllRules();
153: }
154:
155: /**
156: * Stop the current work. Forcibly stop all current query instances over this engine.
157: */
158: public synchronized void halt() {
159: ArrayList copy = new ArrayList(activeInterpreters);
160: // Copy because closing the LPInterpreter will detach it from this engine which affects activeInterpreters
161: for (Iterator i = copy.iterator(); i.hasNext();) {
162: ((LPInterpreter) i.next()).close();
163: }
164: }
165:
166: /**
167: * Set the state of the trace flag. If set to true then rule firings
168: * are logged out to the Log at "INFO" level.
169: */
170: public void setTraceOn(boolean state) {
171: traceOn = state;
172: }
173:
174: /**
175: * Return true if traces of rule firings should be logged.
176: */
177: public boolean isTraceOn() {
178: return traceOn;
179: }
180:
181: /**
182: * Set to true to enable derivation caching
183: */
184: public void setDerivationLogging(boolean recordDerivations) {
185: this .recordDerivations = recordDerivations;
186: }
187:
188: /**
189: * Return true in derivations should be logged.
190: */
191: public boolean getDerivationLogging() {
192: return recordDerivations;
193: }
194:
195: /** Return the rule store associated with the inference graph */
196: public LPRuleStore getRuleStore() {
197: return ruleStore;
198: }
199:
200: /** Return the parent infernce graph associated with this engine */
201: public BackwardRuleInfGraphI getInfGraph() {
202: return infGraph;
203: }
204:
205: /** Detatch the given engine from the list of active engines for this inf graph */
206: public synchronized void detach(LPInterpreter engine) {
207: activeInterpreters.remove(engine);
208: }
209:
210: /**
211: * Check that there are no currently processing queries.
212: * Could throw an exception here but often this can be caused by simply leaving
213: * an unclosed iterator. So instead we try to close the iterators and assume the
214: * rest of the context will be reset by the add call.
215: *
216: * <p>Should be called from within a synchronized block.
217: */
218: public void checkSafeToUpdate() {
219: if (!activeInterpreters.isEmpty()) {
220: ArrayList toClose = new ArrayList();
221: for (Iterator i = activeInterpreters.iterator(); i
222: .hasNext();) {
223: LPInterpreter interpreter = (LPInterpreter) i.next();
224: if (interpreter.getContext() instanceof LPTopGoalIterator) {
225: toClose.add(interpreter.getContext());
226: }
227: }
228: for (Iterator i = toClose.iterator(); i.hasNext();) {
229: ((LPTopGoalIterator) i.next()).close();
230: }
231: }
232: }
233:
234: // =======================================================================
235: // Interface for tabled operations
236:
237: /**
238: * Register an RDF predicate as one whose presence in a goal should force
239: * the goal to be tabled.
240: */
241: public synchronized void tablePredicate(Node predicate) {
242: ruleStore.tablePredicate(predicate);
243: }
244:
245: /**
246: * Return a generator for the given goal (assumes that the caller knows that
247: * the goal should be tabled).
248: * @param goal the goal whose results are to be generated
249: * @param clauses the precomputed set of code blocks used to implement the goal
250: */
251: public synchronized Generator generatorFor(TriplePattern goal,
252: List clauses) {
253: Generator generator = (Generator) tabledGoals.get(goal);
254: if (generator == null) {
255: LPInterpreter interpreter = new LPInterpreter(this , goal,
256: clauses, false);
257: activeInterpreters.add(interpreter);
258: generator = new Generator(interpreter, goal);
259: schedule(generator);
260: tabledGoals.put(goal, generator);
261: }
262: return generator;
263: }
264:
265: /**
266: * Return a generator for the given goal (assumes that the caller knows that
267: * the goal should be tabled).
268: * @param goal the goal whose results are to be generated
269: */
270: public synchronized Generator generatorFor(TriplePattern goal) {
271: Generator generator = (Generator) tabledGoals.get(goal);
272: if (generator == null) {
273: LPInterpreter interpreter = new LPInterpreter(this , goal,
274: false);
275: activeInterpreters.add(interpreter);
276: generator = new Generator(interpreter, goal);
277: schedule(generator);
278: tabledGoals.put(goal, generator);
279: }
280: return generator;
281: }
282:
283: /**
284: * Register that a generator or specific generator state (Consumer choice point)
285: * is now ready to run.
286: */
287: public void schedule(LPAgendaEntry state) {
288: agenda.add(state);
289: }
290:
291: /**
292: * Run the scheduled generators until the given generator is ready to run.
293: */
294: public synchronized void pump(LPInterpreterContext gen) {
295: // System.out.println("Pump agenda on engine " + this + ", size = " + agenda.size());
296: Collection batch = null;
297: if (CYCLES_BETWEEN_COMPLETION_CHECK > 0) {
298: batch = new ArrayList(CYCLES_BETWEEN_COMPLETION_CHECK);
299: }
300: int count = 0;
301: while (!gen.isReady()) {
302: if (agenda.isEmpty()) {
303: // System.out.println("Cycled " + this + ", " + count);
304: return;
305: }
306: // Iterator ai = agenda.iterator();
307: // LPAgendaEntry next = (LPAgendaEntry) ai.next();
308: // ai.remove();
309: int chosen = agenda.size() - 1;
310: LPAgendaEntry next = (LPAgendaEntry) agenda.get(chosen);
311: agenda.remove(chosen);
312: // System.out.println(" pumping entry " + next);
313: next.pump();
314: count++;
315: if (CYCLES_BETWEEN_COMPLETION_CHECK > 0) {
316: batch.add(next.getGenerator());
317: if (count % CYCLES_BETWEEN_COMPLETION_CHECK == 0) {
318: Generator.checkForCompletions(batch);
319: batch.clear();
320: }
321: }
322: }
323: if (CYCLES_BETWEEN_COMPLETION_CHECK > 0 && !batch.isEmpty()) {
324: Generator.checkForCompletions(batch);
325: }
326:
327: // System.out.println("Cycled " + this + ", " + count);
328: }
329:
330: /**
331: * Check all known interpeter contexts to see if any are complete.
332: */
333: public void checkForCompletions() {
334: ArrayList contexts = new ArrayList(activeInterpreters.size());
335: for (Iterator i = activeInterpreters.iterator(); i.hasNext();) {
336: LPInterpreter interpreter = (LPInterpreter) i.next();
337: if (interpreter.getContext() instanceof Generator) {
338: contexts.add(interpreter.getContext());
339: }
340: }
341: Generator.checkForCompletions(contexts);
342: }
343:
344: // =======================================================================
345: // Profiling support
346:
347: /**
348: * Record a rule invocation in the profile count.
349: */
350: public void incrementProfile(RuleClauseCode clause) {
351: if (profile != null) {
352: String index = clause.toString();
353: Count count = (Count) profile.get(index);
354: if (count == null) {
355: profile.put(index, new Count(clause).inc());
356: } else {
357: count.inc();
358: }
359: }
360: }
361:
362: /**
363: * Reset the profile.
364: * @param enable it true then profiling will continue with a new empty profile table,
365: * if false profiling will stop all current data lost.
366: */
367: public void resetProfile(boolean enable) {
368: profile = enable ? new HashMap() : null;
369: }
370:
371: /**
372: * Print a profile of rules used since the last reset.
373: */
374: public void printProfile() {
375: if (profile == null) {
376: System.out.println("No profile collected");
377: } else {
378: ArrayList counts = new ArrayList();
379: counts.addAll(profile.values());
380: Collections.sort(counts);
381: System.out.println("LP engine rule profile");
382: for (Iterator i = counts.iterator(); i.hasNext();) {
383: System.out.println(i.next());
384: }
385: }
386: }
387:
388: /**
389: * Record count of number of rule invocations, used in profile structure only.
390: */
391: static class Count implements Comparable {
392: protected int count = 0;
393: protected RuleClauseCode clause;
394:
395: /** Constructor */
396: public Count(RuleClauseCode clause) {
397: this .clause = clause;
398: }
399:
400: /** return the count value */
401: public int getCount() {
402: return count;
403: }
404:
405: /** increment the count value, return the count object */
406: public Count inc() {
407: count++;
408: return this ;
409: }
410:
411: /** Ordering */
412: public int compareTo(Object other) {
413: Count otherCount = (Count) other;
414: return (count < otherCount.count) ? -1
415: : ((count == otherCount.count) ? 0 : +1);
416: }
417:
418: /** Printable form */
419: public String toString() {
420: return " " + count + "\t - " + clause;
421: }
422:
423: }
424: }
425:
426: /*
427: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
428: All rights reserved.
429:
430: Redistribution and use in source and binary forms, with or without
431: modification, are permitted provided that the following conditions
432: are met:
433:
434: 1. Redistributions of source code must retain the above copyright
435: notice, this list of conditions and the following disclaimer.
436:
437: 2. Redistributions in binary form must reproduce the above copyright
438: notice, this list of conditions and the following disclaimer in the
439: documentation and/or other materials provided with the distribution.
440:
441: 3. The name of the author may not be used to endorse or promote products
442: derived from this software without specific prior written permission.
443:
444: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
445: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
446: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
447: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
448: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
449: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
450: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
451: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
452: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
453: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
454: */
|