001: /******************************************************************
002: * File: RETEConflictSet.java
003: * Created by: Dave Reynolds
004: * Created on: 04-Oct-2005
005: *
006: * (c) Copyright 2005, Hewlett-Packard Development Company, LP
007: * [See end of file]
008: * $Id: RETEConflictSet.java,v 1.6 2008/01/02 12:06:17 andy_seaborne Exp $
009: *****************************************************************/package com.hp.hpl.jena.reasoner.rulesys.impl;
010:
011: import java.util.ArrayList;
012: import java.util.Iterator;
013: import java.util.List;
014:
015: import org.apache.commons.logging.Log;
016: import org.apache.commons.logging.LogFactory;
017:
018: import com.hp.hpl.jena.graph.Triple;
019: import com.hp.hpl.jena.reasoner.ReasonerException;
020: import com.hp.hpl.jena.reasoner.TriplePattern;
021: import com.hp.hpl.jena.reasoner.rulesys.BindingEnvironment;
022: import com.hp.hpl.jena.reasoner.rulesys.Builtin;
023: import com.hp.hpl.jena.reasoner.rulesys.ForwardRuleInfGraphI;
024: import com.hp.hpl.jena.reasoner.rulesys.Functor;
025: import com.hp.hpl.jena.reasoner.rulesys.Rule;
026: import com.hp.hpl.jena.reasoner.rulesys.RuleDerivation;
027:
028: /**
029: * Manages a set of ready-to-fire rules. For monotonic rule sets
030: * we simply fire the rules as soon as they are triggered. For non-monotonic
031: * rule sets we stack them up in a conflict set and fire them one-at-a-time,
032: * propagating all changes between times.
033: * <p>
034: * Note, implementation is not thread-safe. Would be easy to make it so but
035: * concurrent adds to InfModel are not supported anyway.
036: *
037: * @author <a href="mailto:der@hplb.hpl.hp.com">Dave Reynolds</a>
038: * @version $Revision: 1.6 $
039: */
040:
041: public class RETEConflictSet {
042: protected static Log logger = LogFactory.getLog(FRuleEngine.class);
043:
044: /** the execution context for this conflict set */
045: protected RETERuleContext gcontext;
046:
047: /** false if the overall rule system contains some non-montotonic rules */
048: protected boolean isMonotonic;
049:
050: /** the list of rule activations left to fire */
051: protected ArrayList conflictSet = new ArrayList();
052:
053: /** count the number of positive entries - optimization hack */
054: protected int nPos = 0;
055:
056: /** count the number of negative entries - optimization hack */
057: protected int nNeg = 0;
058:
059: /** Construct an empty conflict set, noting whether the overall rule system is monotonic or not */
060: public RETEConflictSet(RETERuleContext context, boolean isMonotonic) {
061: this .gcontext = context;
062: this .isMonotonic = isMonotonic;
063: }
064:
065: /**
066: * Record a request for a rule firing. For monotonic rulesets it may be
067: * actioned immediately, otherwise it will be stacked up.
068: */
069: public void add(Rule rule, BindingEnvironment env, boolean isAdd) {
070: if (isMonotonic) {
071: RETERuleContext context = new RETERuleContext(
072: (ForwardRuleInfGraphI) gcontext.getGraph(),
073: gcontext.getEngine());
074: context.setEnv(env);
075: context.setRule(rule);
076: execute(context, isAdd);
077: } else {
078: // Add to the conflict set, compressing +/- pairs
079: boolean done = false;
080: if ((isAdd && nNeg > 0) || (!isAdd && nPos > 0)) {
081: for (Iterator i = conflictSet.iterator(); i.hasNext();) {
082: CSEntry cse = (CSEntry) i.next();
083: if (cse.rule != rule)
084: continue;
085: if (cse.env.equals(env)) {
086: if (isAdd != cse.isAdd) {
087: i.remove();
088: if (cse.isAdd)
089: nPos--;
090: else
091: nNeg--;
092: done = true;
093: } else {
094: // Redundant insert? Probably leave in for side-effect cases like print
095: }
096: }
097: }
098: }
099: if (!done) {
100: conflictSet.add(new CSEntry(rule, env, isAdd));
101: if (isAdd)
102: nPos++;
103: else
104: nNeg++;
105: }
106: }
107: }
108:
109: /**
110: * Return true if there are no more rules awaiting firing.
111: */
112: public boolean isEmpty() {
113: return conflictSet.isEmpty();
114: }
115:
116: /**
117: * Pick on pending rule from the conflict set and fire it.
118: * Return true if there was a rule to fire.
119: */
120: public boolean fireOne() {
121: if (isEmpty())
122: return false;
123: int index = conflictSet.size() - 1;
124: CSEntry cse = (CSEntry) conflictSet.remove(index);
125: if (cse.isAdd)
126: nPos--;
127: else
128: nNeg--;
129: RETERuleContext context = new RETERuleContext(
130: (ForwardRuleInfGraphI) gcontext.getGraph(), gcontext
131: .getEngine());
132: context.setEnv(cse.env);
133: context.setRule(cse.rule);
134: if (context.shouldStillFire()) {
135: execute(context, cse.isAdd);
136: }
137: return true;
138:
139: }
140:
141: /**
142: * Execute a single rule firing.
143: */
144: public static void execute(RETERuleContext context, boolean isAdd) {
145: Rule rule = context.getRule();
146: BindingEnvironment env = context.getEnv();
147: ForwardRuleInfGraphI infGraph = (ForwardRuleInfGraphI) context
148: .getGraph();
149: if (infGraph.shouldTrace()) {
150: logger.info("Fired rule: " + rule.toShortString());
151: }
152: RETEEngine engine = context.getEngine();
153: engine.incRuleCount();
154: List matchList = null;
155: if (infGraph.shouldLogDerivations() && isAdd) {
156: // Create derivation record
157: matchList = new ArrayList(rule.bodyLength());
158: for (int i = 0; i < rule.bodyLength(); i++) {
159: Object clause = rule.getBodyElement(i);
160: if (clause instanceof TriplePattern) {
161: matchList.add(env
162: .instantiate((TriplePattern) clause));
163: }
164: }
165: }
166: for (int i = 0; i < rule.headLength(); i++) {
167: Object hClause = rule.getHeadElement(i);
168: if (hClause instanceof TriplePattern) {
169: Triple t = env.instantiate((TriplePattern) hClause);
170: if (!t.getSubject().isLiteral()) {
171: // Only add the result if it is legal at the RDF level.
172: // E.g. RDFS rules can create assertions about literals
173: // that we can't record in RDF
174: if (isAdd) {
175: if (!context.contains(t)) {
176: engine.addTriple(t, true);
177: if (infGraph.shouldLogDerivations()) {
178: infGraph.logDerivation(t,
179: new RuleDerivation(rule, t,
180: matchList, infGraph));
181: }
182: }
183: } else {
184: if (context.contains(t)) {
185: // Remove the generated triple
186: engine.deleteTriple(t, true);
187: }
188: }
189: }
190: } else if (hClause instanceof Functor && isAdd) {
191: Functor f = (Functor) hClause;
192: Builtin imp = f.getImplementor();
193: if (imp != null) {
194: imp.headAction(f.getBoundArgs(env), f
195: .getArgLength(), context);
196: } else {
197: throw new ReasonerException(
198: "Invoking undefined Functor " + f.getName()
199: + " in " + rule.toShortString());
200: }
201: } else if (hClause instanceof Rule) {
202: Rule r = (Rule) hClause;
203: if (r.isBackward()) {
204: if (isAdd) {
205: infGraph.addBRule(r.instantiate(env));
206: } else {
207: infGraph.deleteBRule(r.instantiate(env));
208: }
209: } else {
210: throw new ReasonerException(
211: "Found non-backward subrule : " + r);
212: }
213: }
214: }
215: }
216:
217: // Inner class representing a conflict set entry
218: private static class CSEntry {
219: protected Rule rule;
220: protected BindingEnvironment env;
221: protected boolean isAdd;
222:
223: CSEntry(Rule rule, BindingEnvironment env, boolean isAdd) {
224: this .rule = rule;
225: this .env = env;
226: this .isAdd = isAdd;
227: }
228: }
229: }
230:
231: /*
232: (c) Copyright 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP
233: All rights reserved.
234:
235: Redistribution and use in source and binary forms, with or without
236: modification, are permitted provided that the following conditions
237: are met:
238:
239: 1. Redistributions of source code must retain the above copyright
240: notice, this list of conditions and the following disclaimer.
241:
242: 2. Redistributions in binary form must reproduce the above copyright
243: notice, this list of conditions and the following disclaimer in the
244: documentation and/or other materials provided with the distribution.
245:
246: 3. The name of the author may not be used to endorse or promote products
247: derived from this software without specific prior written permission.
248:
249: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
250: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
251: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
252: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
253: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
254: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
255: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
256: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
257: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
258: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
259: */
|