View Javadoc
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