1 package org.drools.reteoo;
2
3 /*
4 $Id: Builder.java,v 1.23 2002/11/22 03:08:45 bob Exp $
5
6 Copyright 2002 (C) The Werken Company. All Rights Reserved.
7
8 Redistribution and use of this software and associated documentation
9 ("Software"), with or without modification, are permitted provided
10 that the following conditions are met:
11
12 1. Redistributions of source code must retain copyright
13 statements and notices. Redistributions must also contain a
14 copy of this document.
15
16 2. Redistributions in binary form must reproduce the
17 above copyright notice, this list of conditions and the
18 following disclaimer in the documentation and/or other
19 materials provided with the distribution.
20
21 3. The name "drools" must not be used to endorse or promote
22 products derived from this Software without prior written
23 permission of The Werken Company. For written permission,
24 please contact bob@werken.com.
25
26 4. Products derived from this Software may not be called "drools"
27 nor may "drools" appear in their names without prior written
28 permission of The Werken Company. "drools" is a registered
29 trademark of The Werken Company.
30
31 5. Due credit should be given to The Werken Company.
32 (http://drools.werken.com/).
33
34 THIS SOFTWARE IS PROVIDED BY THE WERKEN COMPANY AND CONTRIBUTORS
35 ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
36 NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
37 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
38 THE WERKEN COMPANY OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
39 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
40 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
41 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
42 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
43 STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
44 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
45 OF THE POSSIBILITY OF SUCH DAMAGE.
46
47 */
48
49 import org.drools.RuleIntegrationException;
50 import org.drools.reteoo.impl.ReteImpl;
51 import org.drools.reteoo.impl.ObjectTypeNodeImpl;
52 import org.drools.reteoo.impl.ParameterNodeImpl;
53 import org.drools.reteoo.impl.ConditionNodeImpl;
54 import org.drools.reteoo.impl.JoinNodeImpl;
55 import org.drools.reteoo.impl.ExtractionNodeImpl;
56 import org.drools.reteoo.impl.TerminalNodeImpl;
57 import org.drools.reteoo.impl.TupleSourceImpl;
58 import org.drools.rule.Rule;
59 import org.drools.rule.Declaration;
60 import org.drools.rule.Extraction;
61 import org.drools.spi.ObjectType;
62 import org.drools.spi.Condition;
63
64 import java.util.Set;
65 import java.util.HashSet;
66 import java.util.Iterator;
67
68 /*** Builds the Rete-OO network for a <code>RuleSet</code>.
69 *
70 * @see org.drools.rule.RuleSet
71 *
72 * @author <a href="mailto:bob@eng.werken.com">bob mcwhirter</a>
73 *
74 * @task Make joinForCondition actually be intelligent enough to
75 * build optimal joins. Currently using forgy's original
76 * description of 2-input nodes, which I feel (but don't
77 * know for sure, is sub-optimal.
78 */
79 public class Builder
80 {
81 // ------------------------------------------------------------
82 // Instance members
83 // ------------------------------------------------------------
84
85 /*** Rete network to build against. */
86 private ReteImpl rete;
87
88 /*** Total-ordering priority counter. */
89 private int priorityCounter;
90
91 // ------------------------------------------------------------
92 // Constructors
93 // ------------------------------------------------------------
94
95 /*** Construct a <code>Builder</code> against an existing
96 * <code>Rete</code> network.
97 *
98 * @param rete The network to add to.
99 */
100 public Builder(Rete rete)
101 {
102 this.rete = (ReteImpl) rete;
103 }
104
105 // ------------------------------------------------------------
106 // Instance methods
107 // ------------------------------------------------------------
108
109 /*** Retrieve the <code>Rete</code> this <code>Builder</code>
110 * appends to.
111 *
112 * @return The <code>Rete</code>.
113 */
114 public Rete getRete()
115 {
116 return this.rete;
117 }
118
119 /*** Add a <code>Rule</code> to the network.
120 *
121 * @param rule The rule to add.
122 *
123 * @throws RuleIntegrationException if an error prevents complete
124 * construction of the network for the <code>Rule</code>.
125 */
126 public void addRule(Rule rule) throws RuleIntegrationException
127 {
128 Set factExtracts = new HashSet( rule.getExtractions() );
129 Set conds = new HashSet( rule.getConditions() );
130
131 Set leafNodes = null;
132
133 boolean performedJoin = false;
134 boolean attachedExtract = false;
135 boolean cycleAttachExtract = false;
136 boolean joinedForCondition = false;
137
138 leafNodes = createParameterNodes( rule );
139
140 while ( true )
141 {
142 performedJoin = false;
143 attachedExtract = false;
144 joinedForCondition = false;
145
146 if ( ! conds.isEmpty() )
147 {
148 attachConditions( conds,
149 leafNodes );
150 }
151
152 attachedExtract = attachExtractions( factExtracts,
153 leafNodes );
154
155 performedJoin = createJoinNodes( leafNodes );
156
157 if ( ! performedJoin
158 &&
159 ! attachedExtract
160 &&
161 ! conds.isEmpty())
162 {
163 joinedForCondition = joinForCondition( conds,
164 leafNodes );
165 }
166
167 if ( joinedForCondition )
168 {
169 continue;
170 }
171
172 if ( ( performedJoin
173 ||
174 attachedExtract )
175 &&
176 leafNodes.size() > 1 )
177 {
178 continue;
179 }
180
181 if ( leafNodes.size() > 1 )
182 {
183 joinArbitrary( leafNodes );
184 }
185 else if ( ! attachedExtract )
186 {
187 break;
188 }
189 }
190
191 if ( leafNodes.size() != 1 )
192 {
193 throw new RuleIntegrationException( rule );
194 }
195
196 TupleSource lastNode = (TupleSource) leafNodes.iterator().next();
197
198 TerminalNode terminal = new TerminalNodeImpl( lastNode,
199 rule,
200 ++this.priorityCounter);
201 }
202
203 /*** Create the <code>ParameterNode</code>s for the <code>Rule</code>,
204 * and link into the network.
205 *
206 * @param rule The rule.
207 *
208 * @return A <code>Set</code> of <code>ParameterNodes</code> created
209 * and linked into the network.
210 */
211 protected Set createParameterNodes(Rule rule)
212 {
213 Set leafNodes = new HashSet();
214
215 Set parameterDecls = rule.getParameterDeclarations();
216
217 Iterator declIter = parameterDecls.iterator();
218 Declaration eachDecl = null;
219
220 ObjectType objectType = null;
221 ObjectTypeNodeImpl objectTypeNode = null;
222 ParameterNode paramNode = null;
223
224 while ( declIter.hasNext() )
225 {
226 eachDecl = (Declaration) declIter.next();
227
228 objectType = eachDecl.getObjectType();
229
230 objectTypeNode = ((ReteImpl)getRete()).getOrCreateObjectTypeNode( objectType );
231
232 paramNode = new ParameterNodeImpl( objectTypeNode,
233 eachDecl );
234
235 leafNodes.add( paramNode );
236
237 }
238
239 return leafNodes;
240 }
241
242
243 /*** Create and attach <code>Condition</code>s to the network.
244 *
245 * <p>
246 * It may not be possible to satisfy all filder conditions
247 * on the first pass. This method removes satisfied conditions
248 * from the <code>Condition</code> parameter, and leaves
249 * unsatisfied ones in the <code>Set</code>.
250 * </p>
251 *
252 * @param conds Set of <code>Conditions</code>
253 * to attempt attaching.
254 * @param leafNodes The current attachable leaf nodes
255 * of the network.
256 */
257 protected void attachConditions(Set conds,
258 Set leafNodes)
259 {
260 Iterator condIter = conds.iterator();
261 Condition eachCond = null;
262 TupleSourceImpl tupleSource = null;
263
264 ConditionNode conditionNode = null;
265
266 while ( condIter.hasNext() )
267 {
268 eachCond = (Condition) condIter.next();
269
270 tupleSource = findMatchingTupleSourceForCondition( eachCond,
271 leafNodes );
272
273 if ( tupleSource == null )
274 {
275 continue;
276 }
277
278 condIter.remove();
279
280 conditionNode = new ConditionNodeImpl( tupleSource,
281 eachCond );
282
283 leafNodes.remove( tupleSource );
284 leafNodes.add( conditionNode );
285 }
286 }
287
288 /*** Join two arbitrary leaves in order to satisfy a filter
289 * that currently cannot be applied.
290 *
291 * @param conds The filter conditions remaining.
292 * @param leafNodes Available leaf nodes.
293 *
294 * @return <code>true</code> if a join was possible,
295 * otherwise, <code>false</code>.
296 */
297 protected boolean joinForCondition(Set conds,
298 Set leafNodes)
299 {
300 return joinArbitrary( leafNodes );
301 }
302
303 /*** Join two arbitrary leaves in order to satisfy a filter
304 * that currently cannot be applied.
305 *
306 * @param leafNodes Available leaf nodes.
307 */
308 protected boolean joinArbitrary(Set leafNodes)
309 {
310 Iterator leafIter = leafNodes.iterator();
311
312 TupleSourceImpl left = (TupleSourceImpl) leafIter.next();
313
314 if ( ! leafIter.hasNext() )
315 {
316 return false;
317 }
318
319 leafIter.remove();
320
321 TupleSourceImpl right = (TupleSourceImpl) leafIter.next();
322
323 leafIter.remove();
324
325 JoinNode joinNode = new JoinNodeImpl( left,
326 right );
327
328 leafNodes.add( joinNode );
329
330 return true;
331 }
332
333 /*** Create and attach <code>JoinNode</code>s to the network.
334 *
335 * <p>
336 * It may not be possible to join all <code>leafNodes</code>.
337 * </p>
338 *
339 * <p>
340 * Any <code>leafNodes</code> member that particiates
341 * in a <i>join</i> is removed from the <code>leafNodes</code>
342 * collection, and replaced by the joining <code>JoinNode</code>.
343 * </p>
344 *
345 * @param leafNodes The current attachable leaf nodes of
346 * the network.
347 *
348 * @return <code>true</code> if at least one <code>JoinNode</code>
349 * was created, else <code>false</code>.
350 */
351 protected boolean createJoinNodes(Set leafNodes)
352 {
353 boolean performedJoin = false;
354
355 Object[] leftNodes = leafNodes.toArray();
356 Object[] rightNodes = leafNodes.toArray();
357
358 TupleSourceImpl left = null;
359 TupleSourceImpl right = null;
360
361 JoinNode joinNode = null;
362
363 OUTTER:
364 for ( int i = 0 ; i < leftNodes.length ; ++i )
365 {
366 left = (TupleSourceImpl) leftNodes[i];
367
368 if ( ! leafNodes.contains( left ) )
369 {
370 continue OUTTER;
371 }
372
373 INNER:
374 for ( int j = i + 1; j < rightNodes.length ; ++j )
375 {
376 right = (TupleSourceImpl) rightNodes[j];
377
378 if ( ! leafNodes.contains( right ) )
379 {
380 continue INNER;
381 }
382
383 if ( canBeJoined( left,
384 right ) )
385
386 {
387 joinNode = new JoinNodeImpl( left,
388 right );
389
390 leafNodes.remove( left );
391 leafNodes.remove( right );
392
393 leafNodes.add( joinNode );
394
395 performedJoin = true;
396
397 continue OUTTER;
398 }
399 }
400 }
401
402 return performedJoin;
403 }
404
405 /*** Determine if two <code>TupleSource</code>s can be joined.
406 *
407 * @param left The left tuple source
408 * @param right The right tuple source
409 *
410 * @return <code>true</code> if they can be joined (they share
411 * at least one common member declaration), else
412 * <code>false</code>.
413 */
414 protected boolean canBeJoined(TupleSource left,
415 TupleSource right)
416 {
417 Set leftDecls = left.getTupleDeclarations();
418 Iterator rightDeclIter = right.getTupleDeclarations().iterator();
419
420 while ( rightDeclIter.hasNext() )
421 {
422 if ( leftDecls.contains( rightDeclIter.next() ) )
423 {
424 return true;
425 }
426 }
427
428 return false;
429 }
430
431 /*** Create and attach <code>Extraction</code>s to the network.
432 *
433 * <p>
434 * It may not be possible to satisfy all <code>Extraction</code>,
435 * in which case, unsatisfied conditions will remain in the <code>Set</code>
436 * passed in as <code>Extraction</code>.
437 * </p>
438 *
439 * @param factExtracts Set of <code>Extractions</code> to
440 * attach to the network.
441 * @param leafNodes The current attachable leaf nodes of
442 * the network.
443 *
444 * @return <code>true</code> if fact extractions have been
445 * attached, otherwise <code>false</code>.
446 */
447 protected boolean attachExtractions(Set factExtracts,
448 Set leafNodes)
449 {
450 boolean attached = false;
451 boolean cycleAttached = false;
452
453 do
454 {
455 cycleAttached = false;
456
457 Iterator extractIter = factExtracts.iterator();
458 Extraction eachExtract = null;
459 TupleSourceImpl tupleSource = null;
460
461 ExtractionNode extractNode = null;
462
463 while ( extractIter.hasNext() )
464 {
465 eachExtract = (Extraction) extractIter.next();
466
467 tupleSource = findMatchingTupleSourceForExtraction( eachExtract,
468 leafNodes );
469
470 if ( tupleSource == null )
471 {
472 continue;
473 }
474
475 extractIter.remove();
476
477 extractNode = new ExtractionNodeImpl( tupleSource,
478 eachExtract.getTargetDeclaration(),
479 eachExtract.getExtractor() );
480
481 leafNodes.remove( tupleSource );
482 leafNodes.add( extractNode );
483
484 cycleAttached = true;
485 }
486
487 if ( cycleAttached )
488 {
489 attached = true;
490 }
491 }
492 while ( cycleAttached );
493
494 return attached;
495 }
496
497 /*** Locate a <code>TupleSource</code> suitable for attaching
498 * the <code>Condition</code>.
499 *
500 * @param condition The <code>Condition</code> to attach.
501 * @param sources Candidate <code>TupleSources</code>.
502 *
503 * @return Matching <code>TupleSource</code> if a suitable one
504 * can be found, else <code>null</code>.
505 */
506 protected TupleSourceImpl findMatchingTupleSourceForCondition(Condition condition,
507 Set sources)
508 {
509 Iterator sourceIter = sources.iterator();
510 TupleSourceImpl eachSource = null;
511
512 Set decls = null;
513
514 while ( sourceIter.hasNext() )
515 {
516 eachSource = (TupleSourceImpl) sourceIter.next();
517
518 decls = eachSource.getTupleDeclarations();
519
520 if ( matches( condition,
521 decls ) )
522 {
523 return eachSource;
524 }
525 }
526
527 return null;
528 }
529
530 /*** Locate a <code>TupleSource</code> suitable for attaching
531 * the <code>Extraction</code>.
532 *
533 * @param extract The <code>Extraction</code> to attach.
534 * @param sources Candidate <code>TupleSources</code>.
535 *
536 * @return Matching <code>TupleSource</code> if a suitable one
537 * can be found, else <code>null</code>.
538 */
539 protected TupleSourceImpl findMatchingTupleSourceForExtraction(Extraction extract,
540 Set sources)
541 {
542 Declaration targetDecl = extract.getTargetDeclaration();
543
544 Iterator sourceIter = sources.iterator();
545 TupleSourceImpl eachSource = null;
546
547 Set decls = null;
548
549 while ( sourceIter.hasNext() )
550 {
551 eachSource = (TupleSourceImpl) sourceIter.next();
552
553 decls = eachSource.getTupleDeclarations();
554
555 if ( decls.contains( targetDecl ) )
556 {
557 continue;
558 }
559
560 if ( matches( extract,
561 decls ) )
562 {
563 return eachSource;
564 }
565 }
566
567 return null;
568 }
569
570 /*** Determine if a set of <code>Declarations</code> match those
571 * required by a <code>Condition</code>.
572 *
573 * @param condition The <code>Condition</code>.
574 * @param declarations The set of <code>Declarations</code> to compare against.
575 *
576 * @return <code>true</code> if the set of <code>Declarations</code> is a
577 * super-set of the <code>Declarations</code> required by the
578 * <code>Condition</code>.
579 */
580 protected boolean matches(Condition condition,
581 Set declarations)
582 {
583 return matches( condition.getRequiredTupleMembers(),
584 declarations );
585 }
586
587 /*** Determine if a set of <code>Declarations</code> match those
588 * required by a <code>Extraction</code>.
589 *
590 * @param extract The <code>Extraction</code>.
591 * @param declarations The set of <code>Declarations</code> to compare against.
592 *
593 * @return <code>true</code> if the set of <code>Declarations</code> is a
594 * super-set of the <code>Declarations</code> required by the
595 * <code>Condition</code>.
596 */
597 protected boolean matches(Extraction extract,
598 Set declarations)
599 {
600 return matches( extract.getRequiredTupleMembers(),
601 declarations );
602 }
603
604 /*** Determine if a set of <code>Declarations</code> is a super
605 * set of required <code>Declarations</code>
606 *
607 * @param requiredDecls The required <code>Declarations</code>.
608 * @param declarations The set of <code>Declarations</code> to compare against.
609 *
610 * @return <code>true</code> if the set of <code>Declarations</code> is a
611 * super-set of the <code>Declarations</code> required by the
612 * <code>Condition</code>.
613 */
614 protected boolean matches(Declaration[] requiredDecls,
615 Set declarations)
616 {
617 for ( int i = 0 ; i < requiredDecls.length ; ++i )
618 {
619 if ( ! declarations.contains( requiredDecls[i] ) )
620 {
621 return false;
622 }
623 }
624
625 return true;
626 }
627
628 }
This page was automatically generated by Maven