001: /******************************************************************
002: * File: Generator.java
003: * Created by: Dave Reynolds
004: * Created on: 06-Aug-2003
005: *
006: * (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: Generator.java,v 1.10 2008/01/02 12:06:16 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import java.util.*;
012:
013: import com.hp.hpl.jena.reasoner.TriplePattern;
014:
015: /**
016: * A generator represents a set of memoized results for a single
017: * tabled subgoal. The generator may be complete (in which case it just
018: * contains the complete cached set of results for a goal), ready (not complete
019: * but likely to product more results if called) or blocked (not complete and
020: * awaiting results from a dependent generator).
021: * <p>
022: * Each generator may have multiple associated consumer choice points
023: * representing different choices in satisfying the generator's goal.
024: * </p>
025: *
026: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
027: * @version $Revision: 1.10 $ on $Date: 2008/01/02 12:06:16 $
028: */
029: public class Generator implements LPAgendaEntry, LPInterpreterContext {
030:
031: /** The intepreter instance which generates the results for this goal,
032: * null if the generator is complete */
033: protected LPInterpreter interpreter;
034:
035: /** The ordered set of results available for the goal */
036: protected ArrayList results = new ArrayList();
037:
038: /** A indexed version of the result set, used while the generator is live
039: * to detect duplicate results */
040: protected Set resultSet;
041:
042: /** set to true if the dependent generator has new results ready for us */
043: protected boolean isReady = true;
044:
045: /** set to true if at least one branch has block so an active readiness check is required */
046: protected boolean checkReadyNeeded = false;
047:
048: /** The set of choice points producing results for us to use */
049: protected Set generatingCPs = new HashSet();
050:
051: /** The list of active consumer choice points consuming results from this generator */
052: protected Set consumingCPs = new HashSet();
053:
054: /** Flags whether the generator is live/dead/unknown during completion checking */
055: protected LFlag completionState;
056:
057: /** The goal the generator is satisfying - just used in debugging */
058: protected TriplePattern goal;
059:
060: /** True if this generator can produce at most one answer */
061: protected boolean isSingleton;
062:
063: // /** Distance of generator from top level goal, used in scheduling */
064: // protected int depth = DEFAULT_DEPTH;
065: //
066: // /** Default depth if not known */
067: // public static final int DEFAULT_DEPTH = 100;
068:
069: /**
070: * Constructor.
071: *
072: * @param interpreter an initialized interpreter instance that will answer
073: * results for this generator.
074: */
075: public Generator(LPInterpreter interpreter, TriplePattern goal) {
076: this .interpreter = interpreter;
077: this .goal = goal; // Just used for debugging
078: isSingleton = goal.isGround();
079: if (!isSingleton)
080: resultSet = new HashSet();
081: }
082:
083: /**
084: * Return the number of results available from this context.
085: */
086: public int numResults() {
087: return results.size();
088: }
089:
090: /**
091: * Return true if the generator is ready to be scheduled (i.e. it is not
092: * known to be complete and not known to be waiting for a dependent generator).
093: */
094: public boolean isReady() {
095: if (isComplete())
096: return false;
097: if (checkReadyNeeded) {
098: isReady = false;
099: for (Iterator i = generatingCPs.iterator(); i.hasNext();) {
100: if (((ConsumerChoicePointFrame) i.next()).isReady()) {
101: isReady = true;
102: break;
103: }
104: }
105: checkReadyNeeded = false;
106: return isReady;
107: } else {
108: return isReady;
109: }
110: }
111:
112: /**
113: * Directly set that this generator is ready (because the generator
114: * for one of its generatingCPs has produced new results).
115: */
116: public void setReady(ConsumerChoicePointFrame ccp) {
117: if (!isComplete()) {
118: interpreter.engine.schedule(ccp);
119: isReady = true;
120: checkReadyNeeded = false;
121: }
122: }
123:
124: /**
125: * Return true if the generator is complete.
126: */
127: public boolean isComplete() {
128: return interpreter == null;
129: }
130:
131: // /**
132: // * Return the estimated number of generators between the top level goal and this one.
133: // */
134: // public int getDepth() {
135: // return depth;
136: // }
137:
138: // /**
139: // * Set the depth of this generator, it will not be propagated until
140: // * a further depednents are found.
141: // */
142: // public void setDepth(int d) {
143: // depth = d;
144: // }
145:
146: /**
147: * Signal that this generator is complete, no more results can be created.
148: */
149: public void setComplete() {
150: if (!isComplete()) {
151: interpreter.close();
152: interpreter = null;
153: resultSet = null;
154: isReady = false;
155: completionState = LFlag.DEAD;
156: // Anyone we were generating results for is now finished
157: for (Iterator i = consumingCPs.iterator(); i.hasNext();) {
158: ConsumerChoicePointFrame ccp = (ConsumerChoicePointFrame) i
159: .next();
160: if (!ccp.isReady()) {
161: ccp.setFinished();
162: }
163: }
164: generatingCPs = null;
165: consumingCPs.clear();
166: }
167: }
168:
169: /**
170: * Add a new client choince point to consume results from this generator.
171: */
172: public void addConsumer(ConsumerChoicePointFrame ccp) {
173: consumingCPs.add(ccp);
174: // // Update distance from top goal
175: // int newDepth = ccp.context == null ? 1 : ccp.context.getDepth() + 1;
176: // if (newDepth < depth) depth = newDepth;
177: }
178:
179: /**
180: * Remove a terminated consuming choice point from the state set.
181: */
182: public void removeConsumer(ConsumerChoicePointFrame ccp) {
183: consumingCPs.remove(ccp);
184: // We used to set it complete if there were no consumers left.
185: // However, a generator might be part of one query, incompletely consumed
186: // and then opened again on a different query,
187: // it seems better to omit this. TODO review
188: // if (!isComplete() &&consumingCPs.isEmpty()) {
189: // setComplete();
190: // }
191: }
192:
193: /**
194: * Signal dependents that we have new results.
195: */
196: public void notifyResults() {
197: LPBRuleEngine engine = interpreter.getEngine();
198: for (Iterator i = consumingCPs.iterator(); i.hasNext();) {
199: ConsumerChoicePointFrame cons = (ConsumerChoicePointFrame) i
200: .next();
201: cons.setReady();
202: }
203: }
204:
205: /**
206: * Notify that the interpreter has now blocked on the given choice point.
207: */
208: public void notifyBlockedOn(ConsumerChoicePointFrame ccp) {
209: generatingCPs.add(ccp);
210: checkReadyNeeded = true;
211: }
212:
213: /**
214: * Notify this context that the given choice point has terminated
215: * and can be remove from the wait list.
216: */
217: public void notifyFinished(ConsumerChoicePointFrame ccp) {
218: if (generatingCPs != null) {
219: generatingCPs.remove(ccp);
220: }
221: checkReadyNeeded = true;
222: }
223:
224: /**
225: * Start this generator running for the first time.
226: * Should be called from within an appropriately synchronized block.
227: */
228: public void pump() {
229: pump(this );
230: }
231:
232: /**
233: * Start this generator running from the given previous blocked generating
234: * choice point.
235: * Should be called from within an appropriately synchronized block.
236: */
237: public void pump(LPInterpreterState context) {
238: if (isComplete())
239: return;
240: interpreter.setState(context);
241: int priorNresults = results.size();
242: while (true) {
243: Object result = interpreter.next();
244: if (result == StateFlag.FAIL) {
245: checkReadyNeeded = true;
246: break;
247: } else {
248: // Simple triple result
249: if (isSingleton) {
250: results.add(result);
251: isReady = false;
252: break;
253: } else if (resultSet.add(result)) {
254: results.add(result);
255: }
256: }
257: }
258: if (results.size() > priorNresults) {
259: notifyResults();
260: }
261: // Early termination check, close a singleton as soon as we have the ans
262: if (isSingleton && results.size() == 1) {
263: setComplete();
264: }
265: if (LPBRuleEngine.CYCLES_BETWEEN_COMPLETION_CHECK == 0) {
266: checkForCompletions();
267: }
268: }
269:
270: /**
271: * Return the generator associated with this entry (might be the entry itself)
272: */
273: public Generator getGenerator() {
274: return this ;
275: }
276:
277: /**
278: * Check for deadlocked states where none of the generators we are (indirectly)
279: * dependent on can run.
280: */
281: public void checkForCompletions() {
282: HashSet visited = new HashSet();
283: if (runCompletionCheck(visited) != LFlag.LIVE) {
284: postCompletionCheckScan(visited);
285: }
286: }
287:
288: /**
289: * Check for deadlocked states across a collection of generators which have
290: * been run.
291: */
292: public static void checkForCompletions(Collection completions) {
293: HashSet visited = new HashSet();
294: boolean atLeastOneZombie = false;
295: for (Iterator i = completions.iterator(); i.hasNext();) {
296: Generator g = (Generator) i.next();
297: if (g.runCompletionCheck(visited) != LFlag.LIVE) {
298: atLeastOneZombie = true;
299: }
300: }
301: if (atLeastOneZombie) {
302: postCompletionCheckScan(visited);
303: }
304: }
305:
306: /**
307: * Check whether this generator is live (indirectly dependent on a ready
308: * generator), dead (complete) or in a deadlock loop which might or
309: * might not be live (unknown).
310: */
311: protected LFlag runCompletionCheck(Set visited) {
312: if (isComplete())
313: return LFlag.DEAD;
314: if (!visited.add(this ))
315: return this .completionState;
316: completionState = LFlag.UNKNOWN;
317: if (isReady()) {
318: completionState = LFlag.LIVE;
319: } else {
320: for (Iterator i = generatingCPs.iterator(); i.hasNext();) {
321: ConsumerChoicePointFrame ccp = (ConsumerChoicePointFrame) i
322: .next();
323: if (ccp.isReady()) {
324: completionState = LFlag.LIVE;
325: break;
326: } else if (ccp.generator.runCompletionCheck(visited) == LFlag.LIVE) {
327: completionState = LFlag.LIVE;
328: break;
329: }
330: }
331: }
332: return completionState;
333: }
334:
335: /**
336: * Scan the result of a (set of) completion check(s) to detect which of the
337: * unknowns are actually live and set the remaining (deadlocked) states
338: * to complete.
339: */
340: protected static void postCompletionCheckScan(Set visited) {
341: for (Iterator iv = visited.iterator(); iv.hasNext();) {
342: Generator g = (Generator) iv.next();
343: if (g.completionState == LFlag.LIVE) {
344: for (Iterator i = g.consumingCPs.iterator(); i
345: .hasNext();) {
346: LPInterpreterContext link = ((ConsumerChoicePointFrame) i
347: .next()).getConsumingContext();
348: if (link instanceof Generator) {
349: ((Generator) link).propagateLive(visited);
350: }
351: }
352: }
353: }
354:
355: for (Iterator iv = visited.iterator(); iv.hasNext();) {
356: Generator g = (Generator) iv.next();
357: if (g.completionState != LFlag.LIVE) {
358: g.setComplete();
359: }
360: }
361: return;
362: }
363:
364: /**
365: * Propagate liveness state forward to consuming generators, but only those
366: * within the filter set.
367: */
368: protected void propagateLive(Set filter) {
369: if (completionState != LFlag.LIVE) {
370: completionState = LFlag.LIVE;
371: for (Iterator i = consumingCPs.iterator(); i.hasNext();) {
372: LPInterpreterContext link = ((ConsumerChoicePointFrame) i
373: .next()).getConsumingContext();
374: if (link instanceof Generator) {
375: ((Generator) link).propagateLive(filter);
376: }
377: }
378: }
379: }
380:
381: /**
382: * Inner class used to flag generator states during completeness check.
383: */
384: private static class LFlag {
385:
386: /** Label for printing */
387: private String label;
388:
389: public static final LFlag LIVE = new LFlag("Live");
390: public static final LFlag DEAD = new LFlag("Dead");
391: public static final LFlag UNKNOWN = new LFlag("Unknown");
392:
393: /** Constructor */
394: private LFlag(String label) {
395: this .label = label;
396: }
397:
398: /** Print string */
399: public String toString() {
400: return label;
401: }
402: }
403:
404: }
405:
406: /*
407: (c) Copyright 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
408: All rights reserved.
409:
410: Redistribution and use in source and binary forms, with or without
411: modification, are permitted provided that the following conditions
412: are met:
413:
414: 1. Redistributions of source code must retain the above copyright
415: notice, this list of conditions and the following disclaimer.
416:
417: 2. Redistributions in binary form must reproduce the above copyright
418: notice, this list of conditions and the following disclaimer in the
419: documentation and/or other materials provided with the distribution.
420:
421: 3. The name of the author may not be used to endorse or promote products
422: derived from this software without specific prior written permission.
423:
424: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
425: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
426: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
427: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
428: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
429: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
430: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
431: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
432: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
433: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
434: */
|