KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > hp > hpl > jena > reasoner > rulesys > impl > oldCode > BRuleEngine


1 /******************************************************************
2  * File: Agenda.java
3  * Created by: Dave Reynolds
4  * Created on: 11-May-2003
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: BRuleEngine.java,v 1.5 2005/02/21 12:18:02 andy_seaborne Exp $
9  *****************************************************************/
10 package com.hp.hpl.jena.reasoner.rulesys.impl.oldCode;
11
12 import com.hp.hpl.jena.reasoner.rulesys.*;
13 import com.hp.hpl.jena.reasoner.rulesys.impl.BindingVector;
14 import com.hp.hpl.jena.reasoner.rulesys.impl.RuleStore;
15 import com.hp.hpl.jena.reasoner.rulesys.impl.StateFlag;
16 import com.hp.hpl.jena.reasoner.*;
17 import com.hp.hpl.jena.util.PrintUtil;
18 import com.hp.hpl.jena.graph.*;
19
20 import org.apache.commons.logging.Log;
21 import org.apache.commons.logging.LogFactory;
22
23 import java.util.*;
24
25 /**
26  * Part of the backward chaining rule interpreter. Maintains an agenda containing
27  * an ordered list of RuleStates awaiting processing (each RuleState
28  * represents the tip of a partially expanded search tree).
29  * <p>
30  * This object does the top level scheduling of rule processing. By default
31  * it batches up several results from the top rule in the agenda before
32  * switching to expand other trees. The size of this batch is adjustable.
33  * </p>
34  *
35  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
36  * @version $Revision: 1.5 $ on $Date: 2005/02/21 12:18:02 $
37  */
38 public class BRuleEngine {
39     
40 // =======================================================================
41 // Variables
42
43     /** a list of active RuleStates to be processed */
44     protected LinkedList agenda = new LinkedList();
45     
46 // /** the RuleState currently being procssed */
47 // protected RuleState current;
48
49     /** The table of all goals */
50     protected GoalTable goalTable;
51     
52     /** The inference graph which is using this engine - used for calling builtins */
53     protected BackwardRuleInfGraphI infGraph;
54     
55     /** Indexed version of the rule set */
56     protected RuleStore ruleStore;
57     
58     /** True if debug information should be written out */
59     protected boolean traceOn = false;
60     
61     /** Set to true to flag that derivations should be logged */
62     protected boolean recordDerivations;
63     
64     /** performance stats - number of rules fired */
65     protected long nRulesFired = 0;
66     
67     /** The size of the result batch permitted before a rule should
68      * reschedule itself lower on the agenda */
69     protected int batchSize = 100000;
70     
71     static Log logger = LogFactory.getLog(BRuleEngine.class);
72     
73 // =======================================================================
74 // Constructors
75
76     /**
77      * Constructor.
78      * @param infGraph the parent inference graph which is using this engine
79      * @param rules the indexed set of rules to process
80      */
81     public BRuleEngine(BackwardRuleInfGraphI infGraph, RuleStore rules) {
82         this.infGraph = infGraph;
83         goalTable = new GoalTable(this);
84         ruleStore = rules;
85     }
86     
87     /**
88      * Constructor. Creates an empty engine to which rules must be added.
89      * @param infGraph the parent inference graph which is using this engine
90      */
91     public BRuleEngine(BackwardRuleInfGraphI infGraph) {
92         this.infGraph = infGraph;
93         goalTable = new GoalTable(this);
94         ruleStore = new RuleStore();
95     }
96     
97 // =======================================================================
98 // Control methods
99
100     /**
101      * Clear all tabled results.
102      */
103     public synchronized void reset() {
104         agenda.clear();
105         goalTable.reset();
106     }
107     
108     /**
109      * Add a single rule to the store.
110      * N.B. This will invalidate current partial results and the engine
111      * should be reset() before future queries.
112      */
113     public void addRule(Rule rule) {
114 // System.out.println("Adding rule: " + rule);
115 ruleStore.addRule(rule);
116     }
117     
118     /**
119      * Remove a single rule from the store.
120      * N.B. This will invalidate current partial results and the engine
121      * should be reset() before future queries.
122      */
123     public void deleteRule(Rule rule) {
124         ruleStore.deleteRule(rule);
125     }
126     
127     /**
128      * Return an ordered list of all registered rules.
129      */
130     public List getAllRules() {
131         return ruleStore.getAllRules();
132     }
133     
134     /**
135      * Delete all the rules.
136      */
137     public void deleteAllRules() {
138         ruleStore.deleteAllRules();
139     }
140     
141     /**
142      * Stop the current work. This is called if the top level results iterator has
143      * either finished or the calling application has had enough. We leave any completed
144      * results in the GoalTable but clear out the agenda and all non-compelted results.
145      */
146     public synchronized void halt() {
147         // Clear agenda
148 for (Iterator i = agenda.iterator(); i.hasNext(); ) {
149             RuleState item = (RuleState)i.next();
150             // don't call item.close(), that would update the ref count and set a completion flag
151 if (item.goalState != null) 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, BindingEnvironment env) {
306         return infGraph.processBuiltin(clause, rule, env);
307     }
308     
309     /**
310      * The main processing loop. Continues processing agenda items until either
311      * a new solution to the top goal has been found or the agenda is empty and
312      * so no more solutions are available.
313      *
314      * @param topGoalState the top level GoalState whose values are being sought
315      * @return null if all processing is complete and no more solutions are
316      * available, otherwise returns the next result available for the topGoal.
317      */
318     public synchronized Triple next(GoalState topGoalState) {
319         GoalResults topGoal = topGoalState.getGoalResultsEntry();
320         int numResults = 0;
321         BindingVector env = null;
322         RuleState current = null;
323         RuleState continuation = null;
324         try {
325             while(true) {
326 // System.gc();
327 boolean foundResult = false;
328                 RuleState delayedRSClose = null;
329                 if (current == null) {
330                     // Move to the next agenda item
331 // (if empty then an exception is thrown and caught later)
332 current = nextAgendaItem();
333                     numResults = 0;
334                     if (traceOn) {
335                         logger.debug("Waken: " + current);
336                     }
337                 }
338                 Object JavaDoc result = current.next();
339                 if (result == StateFlag.FAIL) {
340                     // backtrack, if we fall off the root of this tree then
341 // current will end up as null in which case the loop with
342 // shift to the next agenda item
343 if (traceOn) {
344                         logger.debug("Failed");
345                     }
346                     delayedRSClose = current;
347                     current = current.prev;
348                 } else if (result == StateFlag.SUSPEND) {
349                     // Can do no more with this goal
350 if (traceOn) {
351                         logger.debug("Suspend: " + current);
352                     }
353                     GoalResults waitingFor = current.goalState.results;
354                     waitingFor.addDependent(current);
355                     current = current.prev;
356                 } else if (result == StateFlag.SATISFIED) {
357                     // The rule had no clauses left to check, so return answers
358 foundResult = true;
359                     env = current.env;
360                     delayedRSClose = current;
361                     continuation = current.prev;
362                 } else { // We have a result so continue extending this search tree depth first
363 env = current.newEnvironment((Triple)result);
364                     if (env == null) {
365                         // failed a functor match - so loop back to look for more results
366 // Might be better to reschedule onto the end of the agenda?
367 continue;
368                     }
369                     Rule rule = current.ruleInstance.rule;
370                     boolean foundGoal = false;
371                     int maxClause = rule.bodyLength();
372                     int clauseIndex = current.nextClauseIndex();
373                     while (clauseIndex < maxClause && !foundGoal) {
374                         ClauseEntry clause = rule.getBodyElement(clauseIndex++);
375                         if (clause instanceof TriplePattern) {
376                             // found next subgoal to try
377 // Push current state onto stack
378 TriplePattern subgoal = env.partInstantiate((TriplePattern)clause);
379                             if (!subgoal.isLegal()) {
380                                 // branch has failed
381 delayedRSClose = current;
382                                 current = current.prev;
383                             } else {
384                                 current = new RuleState(current, subgoal, clauseIndex, env);
385                             }
386                             foundGoal = true;
387                         } else {
388                             if (!infGraph.processBuiltin(clause, rule, env)) {
389                                 // This branch has failed
390 delayedRSClose = current;
391                                 current = current.prev;
392                                 foundGoal = true;
393                             }
394                         }
395                     }
396                     if (!foundGoal) {
397                         // If we get to here then this branch has completed and we have a result
398 foundResult = true;
399                         continuation = current;
400                     }
401                 }
402                 if (foundResult) {
403                     // If we get to here then this branch has completed and we have a result
404 GoalResults resultDest = current.ruleInstance.generator;
405                     Triple finalResult = current.getResult(env);
406                     if (traceOn) {
407                         logger.debug("Result: " + PrintUtil.print(finalResult) + " <- " + current +", newenv=" + env);
408                     }
409                     boolean newresult = resultDest.addResult(finalResult);
410                     if (delayedRSClose != null) {
411                         delayedRSClose.close();
412                     }
413                     numResults++;
414                     current = continuation;
415                     nRulesFired++;
416                     if (newresult && recordDerivations) {
417                         Rule rule = current.ruleInstance.rule;
418                         List matchList = new ArrayList(rule.bodyLength());
419                         for (int i = 0; i < rule.bodyLength(); i++) {
420                             Object JavaDoc clause = rule.getBodyElement(i);
421                             if (clause instanceof TriplePattern) {
422                                 matchList.add(env.instantiate((TriplePattern)clause));
423                             }
424                         }
425
426                         RuleDerivation derivation = new RuleDerivation(rule, finalResult, matchList, infGraph);
427                         infGraph.logDerivation(finalResult, derivation);
428                     }
429                     if (newresult && resultDest == topGoal) {
430                         // Found a top level goal result so return it now
431 if (current != null) prependToAgenda(current);
432                         return finalResult;
433                     } else if (numResults > batchSize) {
434                         // push the current state lower down agenda and try another
435 if (current != null) appendToAgenda(current);
436                         current = null;
437                     }
438                 } else {
439                     if (delayedRSClose != null) {
440                         delayedRSClose.close();
441                     }
442                 }
443             }
444         } catch (NoSuchElementException e) {
445             // No more agenda items can be processed, so the topGoal is as satisfied as it can be
446 if (traceOn) {
447                 logger.debug("Completed all");
448             }
449             goalTable.setAllComplete();
450             return null;
451         }
452     }
453 }
454
455
456
457 /*
458     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
459     All rights reserved.
460
461     Redistribution and use in source and binary forms, with or without
462     modification, are permitted provided that the following conditions
463     are met:
464
465     1. Redistributions of source code must retain the above copyright
466        notice, this list of conditions and the following disclaimer.
467
468     2. Redistributions in binary form must reproduce the above copyright
469        notice, this list of conditions and the following disclaimer in the
470        documentation and/or other materials provided with the distribution.
471
472     3. The name of the author may not be used to endorse or promote products
473        derived from this software without specific prior written permission.
474
475     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
476     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
477     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
478     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
479     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
480     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
481     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
482     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
483     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
484     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
485 */
Popular Tags