KickJava   Java API By Example, From Geeks To Geeks.

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


1 /******************************************************************
2  * File: Generator.java
3  * Created by: Dave Reynolds
4  * Created on: 06-Aug-2003
5  *
6  * (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
7  * [See end of file]
8  * $Id: Generator.java,v 1.7 2005/04/12 17:01:41 andy_seaborne Exp $
9  *****************************************************************/
10 package com.hp.hpl.jena.reasoner.rulesys.impl;
11
12 import java.util.*;
13
14 import com.hp.hpl.jena.reasoner.TriplePattern;
15
16 /**
17  * A generator represents a set of memoized results for a single
18  * tabled subgoal. The generator may be complete (in which case it just
19  * contains the complete cached set of results for a goal), ready (not complete
20  * but likely to product more results if called) or blocked (not complete and
21  * awaiting results from a dependent generator).
22  * <p>
23  * Each generator may have multiple associated consumer choice points
24  * representing different choices in satisfying the generator's goal.
25  * </p>
26  *
27  * @author <a HREF="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
28  * @version $Revision: 1.7 $ on $Date: 2005/04/12 17:01:41 $
29  */
30 public class Generator implements LPAgendaEntry, LPInterpreterContext {
31
32     /** The intepreter instance which generates the results for this goal,
33      * null if the generator is complete */
34     protected LPInterpreter interpreter;
35         
36     /** The ordered set of results available for the goal */
37     protected ArrayList results = new ArrayList();
38     
39     /** A indexed version of the result set, used while the generator is live
40      * to detect duplicate results */
41     protected Set resultSet;
42     
43     /** set to true if the dependent generator has new results ready for us */
44     protected boolean isReady = true;
45     
46     /** set to true if at least one branch has block so an active readiness check is required */
47     protected boolean checkReadyNeeded = false;
48     
49     /** The set of choice points producing results for us to use */
50     protected Set generatingCPs = new HashSet();
51     
52     /** The list of active consumer choice points consuming results from this generator */
53     protected Set consumingCPs = new HashSet();
54     
55     /** Flags whether the generator is live/dead/unknown during completion checking */
56     protected LFlag completionState;
57     
58     /** The goal the generator is satisfying - just used in debugging */
59     protected TriplePattern goal;
60     
61     /** True if this generator can produce at most one answer */
62     protected boolean isSingleton;
63     
64 // /** Distance of generator from top level goal, used in scheduling */
65 // protected int depth = DEFAULT_DEPTH;
66 //
67 // /** Default depth if not known */
68 // public static final int DEFAULT_DEPTH = 100;
69
70     /**
71      * Constructor.
72      *
73      * @param interpreter an initialized interpreter instance that will answer
74      * results for this generator.
75      */
76     public Generator(LPInterpreter interpreter, TriplePattern goal) {
77         this.interpreter = interpreter;
78         this.goal = goal; // Just used for debugging
79 isSingleton = goal.isGround();
80         if (!isSingleton) resultSet = new HashSet();
81     }
82     
83     /**
84      * Return the number of results available from this context.
85      */
86     public int numResults() {
87         return results.size();
88     }
89     
90     /**
91      * Return true if the generator is ready to be scheduled (i.e. it is not
92      * known to be complete and not known to be waiting for a dependent generator).
93      */
94     public boolean isReady() {
95         if (isComplete()) return false;
96         if (checkReadyNeeded) {
97             isReady = false;
98             for (Iterator i = generatingCPs.iterator(); i.hasNext(); ) {
99                 if ( ((ConsumerChoicePointFrame)i.next()).isReady() ) {
100                     isReady = true;
101                     break;
102                 }
103             }
104             checkReadyNeeded = false;
105             return isReady;
106         } else {
107             return isReady;
108         }
109     }
110     
111     /**
112      * Directly set that this generator is ready (because the generator
113      * for one of its generatingCPs has produced new results).
114      */
115     public void setReady(ConsumerChoicePointFrame ccp) {
116         if (!isComplete()) {
117             interpreter.engine.schedule(ccp);
118             isReady = true;
119             checkReadyNeeded = false;
120         }
121     }
122     
123     /**
124      * Return true if the generator is complete.
125      */
126     public boolean isComplete() {
127         return interpreter == null;
128     }
129     
130 // /**
131 // * Return the estimated number of generators between the top level goal and this one.
132 // */
133 // public int getDepth() {
134 // return depth;
135 // }
136
137 // /**
138 // * Set the depth of this generator, it will not be propagated until
139 // * a further depednents are found.
140 // */
141 // public void setDepth(int d) {
142 // depth = d;
143 // }
144
145     /**
146      * Signal that this generator is complete, no more results can be created.
147      */
148     public void setComplete() {
149         if (!isComplete()) {
150             interpreter.close();
151             interpreter = null;
152             resultSet = null;
153             isReady = false;
154             completionState = LFlag.DEAD;
155             // Anyone we were generating results for is now finished
156 for (Iterator i = consumingCPs.iterator(); i.hasNext(); ) {
157                 ConsumerChoicePointFrame ccp = (ConsumerChoicePointFrame)i.next();
158                 if ( ! ccp.isReady()) {
159                     ccp.setFinished();
160                 }
161             }
162             generatingCPs = null;
163             consumingCPs.clear();
164         }
165     }
166     
167     /**
168      * Add a new client choince point to consume results from this generator.
169      */
170     public void addConsumer(ConsumerChoicePointFrame ccp) {
171         consumingCPs.add(ccp);
172 // // Update distance from top goal
173 // int newDepth = ccp.context == null ? 1 : ccp.context.getDepth() + 1;
174 // if (newDepth < depth) depth = newDepth;
175 }
176     
177     /**
178      * Remove a terminated consuming choice point from the state set.
179      */
180     public void removeConsumer(ConsumerChoicePointFrame ccp) {
181         consumingCPs.remove(ccp);
182         // We used to set it complete if there were no consumers left.
183 // However, a generator might be part of one query, incompletely consumed
184 // and then opened again on a different query,
185 // it seems better to omit this. TODO review
186 // if (!isComplete() &&consumingCPs.isEmpty()) {
187 // setComplete();
188 // }
189 }
190         
191     /**
192      * Signal dependents that we have new results.
193      */
194     public void notifyResults() {
195         LPBRuleEngine engine = interpreter.getEngine();
196         for (Iterator i = consumingCPs.iterator(); i.hasNext(); ) {
197             ConsumerChoicePointFrame cons = (ConsumerChoicePointFrame)i.next();
198             cons.setReady();
199         }
200     }
201
202     /**
203      * Notify that the interpreter has now blocked on the given choice point.
204      */
205     public void notifyBlockedOn(ConsumerChoicePointFrame ccp) {
206         generatingCPs.add(ccp);
207         checkReadyNeeded = true;
208     }
209     
210     /**
211      * Notify this context that the given choice point has terminated
212      * and can be remove from the wait list.
213      */
214     public void notifyFinished(ConsumerChoicePointFrame ccp) {
215         if (generatingCPs != null) {
216             generatingCPs.remove(ccp);
217         }
218         checkReadyNeeded = true;
219     }
220
221     /**
222      * Start this generator running for the first time.
223      * Should be called from within an appropriately synchronized block.
224      */
225     public void pump() {
226         pump(this);
227     }
228     
229     /**
230      * Start this generator running from the given previous blocked generating
231      * choice point.
232      * Should be called from within an appropriately synchronized block.
233      */
234     public void pump(LPInterpreterState context) {
235         if (isComplete()) return;
236         interpreter.setState(context);
237         int priorNresults = results.size();
238         while (true) {
239             Object JavaDoc result = interpreter.next();
240             if (result == StateFlag.FAIL) {
241                 checkReadyNeeded = true;
242                 break;
243             } else {
244                 // Simple triple result
245 if (isSingleton) {
246                     results.add(result);
247                     isReady = false;
248                     break;
249                 } else if (resultSet.add(result)) {
250                     results.add(result);
251                 }
252             }
253         }
254         if (results.size() > priorNresults) {
255             notifyResults();
256         }
257         // Early termination check, close a singleton as soon as we have the ans
258 if (isSingleton && results.size() == 1) {
259             setComplete();
260         }
261         if (LPBRuleEngine.CYCLES_BETWEEN_COMPLETION_CHECK == 0) {
262             checkForCompletions();
263         }
264     }
265     
266     /**
267      * Return the generator associated with this entry (might be the entry itself)
268      */
269     public Generator getGenerator() {
270         return this;
271     }
272     
273     /**
274      * Check for deadlocked states where none of the generators we are (indirectly)
275      * dependent on can run.
276      */
277     public void checkForCompletions() {
278         HashSet visited = new HashSet();
279         if (runCompletionCheck(visited) != LFlag.LIVE) {
280             postCompletionCheckScan(visited);
281         }
282     }
283     
284     /**
285      * Check for deadlocked states across a collection of generators which have
286      * been run.
287      */
288     public static void checkForCompletions(Collection completions) {
289         HashSet visited = new HashSet();
290         boolean atLeastOneZombie = false;
291         for (Iterator i = completions.iterator(); i.hasNext(); ) {
292             Generator g = (Generator)i.next();
293             if (g.runCompletionCheck(visited) != LFlag.LIVE) {
294                 atLeastOneZombie = true;
295             }
296         }
297         if (atLeastOneZombie) {
298             postCompletionCheckScan(visited);
299         }
300     }
301     
302     /**
303      * Check whether this generator is live (indirectly dependent on a ready
304      * generator), dead (complete) or in a deadlock loop which might or
305      * might not be live (unknown).
306      */
307     protected LFlag runCompletionCheck(Set visited) {
308         if (isComplete()) return LFlag.DEAD;
309         if (! visited.add(this)) return this.completionState;
310         completionState = LFlag.UNKNOWN;
311         if (isReady()) {
312             completionState = LFlag.LIVE;
313         } else {
314             for (Iterator i = generatingCPs.iterator(); i.hasNext(); ) {
315                 ConsumerChoicePointFrame ccp = (ConsumerChoicePointFrame)i.next();
316                 if (ccp.isReady()) {
317                     completionState = LFlag.LIVE;
318                     break;
319                 } else if ( ccp.generator.runCompletionCheck(visited) == LFlag.LIVE) {
320                     completionState = LFlag.LIVE;
321                     break;
322                 }
323             }
324         }
325         return completionState;
326     }
327     
328     /**
329      * Scan the result of a (set of) completion check(s) to detect which of the
330      * unknowns are actually live and set the remaining (deadlocked) states
331      * to complete.
332      */
333     protected static void postCompletionCheckScan(Set visited ) {
334         for (Iterator iv = visited.iterator(); iv.hasNext(); ) {
335             Generator g = (Generator)iv.next();
336             if (g.completionState == LFlag.LIVE) {
337                 for (Iterator i = g.consumingCPs.iterator(); i.hasNext(); ) {
338                     LPInterpreterContext link = ((ConsumerChoicePointFrame)i.next()).getConsumingContext();
339                     if (link instanceof Generator) {
340                         ((Generator)link).propagateLive(visited);
341                     }
342                 }
343             }
344         }
345         
346         for (Iterator iv = visited.iterator(); iv.hasNext(); ) {
347             Generator g = (Generator)iv.next();
348             if (g.completionState != LFlag.LIVE) {
349                 g.setComplete();
350             }
351         }
352         return;
353      }
354     
355     /**
356      * Propagate liveness state forward to consuming generators, but only those
357      * within the filter set.
358      */
359     protected void propagateLive(Set filter) {
360         if (completionState != LFlag.LIVE) {
361             completionState = LFlag.LIVE;
362             for (Iterator i = consumingCPs.iterator(); i.hasNext(); ) {
363                 LPInterpreterContext link = ((ConsumerChoicePointFrame)i.next()).getConsumingContext();
364                 if (link instanceof Generator) {
365                     ((Generator)link).propagateLive(filter);
366                 }
367             }
368         }
369     }
370     
371     /**
372      * Inner class used to flag generator states during completeness check.
373      */
374     private static class LFlag {
375     
376         /** Label for printing */
377         private String JavaDoc label;
378
379         public static final LFlag LIVE = new LFlag("Live");
380         public static final LFlag DEAD = new LFlag("Dead");
381         public static final LFlag UNKNOWN = new LFlag("Unknown");
382     
383         /** Constructor */
384         private LFlag(String JavaDoc label) {
385             this.label = label;
386         }
387     
388         /** Print string */
389         public String JavaDoc toString() {
390             return label;
391         }
392     }
393
394     
395 }
396
397
398 /*
399     (c) Copyright 2003, 2004, 2005 Hewlett-Packard Development Company, LP
400     All rights reserved.
401
402     Redistribution and use in source and binary forms, with or without
403     modification, are permitted provided that the following conditions
404     are met:
405
406     1. Redistributions of source code must retain the above copyright
407        notice, this list of conditions and the following disclaimer.
408
409     2. Redistributions in binary form must reproduce the above copyright
410        notice, this list of conditions and the following disclaimer in the
411        documentation and/or other materials provided with the distribution.
412
413     3. The name of the author may not be used to endorse or promote products
414        derived from this software without specific prior written permission.
415
416     THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
417     IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
418     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
419     IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
420     INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
421     NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
422     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
423     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
424     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
425     THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
426 */
Popular Tags