1 /* 2 * ModeShape (http://www.modeshape.org) 3 * See the COPYRIGHT.txt file distributed with this work for information 4 * regarding copyright ownership. Some portions may be licensed 5 * to Red Hat, Inc. under one or more contributor license agreements. 6 * See the AUTHORS.txt file in the distribution for a full listing of 7 * individual contributors. 8 * 9 * ModeShape is free software. Unless otherwise indicated, all code in ModeShape 10 * is licensed to you under the terms of the GNU Lesser General Public License as 11 * published by the Free Software Foundation; either version 2.1 of 12 * the License, or (at your option) any later version. 13 * 14 * ModeShape is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 * Lesser General Public License for more details. 18 * 19 * You should have received a copy of the GNU Lesser General Public 20 * License along with this software; if not, write to the Free 21 * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 22 * 02110-1301 USA, or see the FSF site: http://www.fsf.org. 23 */ 24 package org.modeshape.graph.query.plan; 25 26 import java.util.ArrayList; 27 import java.util.Collection; 28 import java.util.Collections; 29 import java.util.EnumSet; 30 import java.util.HashMap; 31 import java.util.HashSet; 32 import java.util.Iterator; 33 import java.util.LinkedList; 34 import java.util.List; 35 import java.util.Map; 36 import java.util.Set; 37 import net.jcip.annotations.NotThreadSafe; 38 import org.modeshape.common.util.CheckArg; 39 import org.modeshape.common.util.ObjectUtil; 40 import org.modeshape.graph.query.model.Column; 41 import org.modeshape.graph.query.model.Constraint; 42 import org.modeshape.graph.query.model.JoinCondition; 43 import org.modeshape.graph.query.model.JoinType; 44 import org.modeshape.graph.query.model.Ordering; 45 import org.modeshape.graph.query.model.Readable; 46 import org.modeshape.graph.query.model.SelectorName; 47 import org.modeshape.graph.query.model.Visitable; 48 import org.modeshape.graph.query.model.Visitors; 49 import org.modeshape.graph.query.model.SetQuery.Operation; 50 import org.modeshape.graph.query.validate.Schemata; 51 52 /** 53 * A representation of a single node within a plan tree. 54 */ 55 @NotThreadSafe 56 public final class PlanNode implements Iterable<PlanNode>, Readable, Cloneable, java.io.Serializable { 57 58 private static final long serialVersionUID = 1L; 59 60 /** 61 * An enumeration dictating the type of plan tree nodes. 62 */ 63 public enum Type { 64 65 /** A node that represents an access of the underlying storage. */ 66 ACCESS("Access"), 67 /** A node that defines the removal of duplicate tuples. */ 68 DUP_REMOVE("DupRemoval"), 69 /** A node that defines the join type, join criteria, and join strategy */ 70 JOIN("Join"), 71 /** A node that defines the columns returned from the node. */ 72 PROJECT("Project"), 73 /** A node that selects a filters the tuples by applying a criteria evaluation filter node (WHERE / HAVING) */ 74 SELECT("Select"), 75 /** A node that defines the columns to sort on, the sort direction for each column, and whether to remove duplicates. */ 76 SORT("Sort"), 77 /** A node that defines the 'table' from which the tuples are being obtained */ 78 SOURCE("Source"), 79 /** A node that groups sets of rows into groups (and where aggregation would be performed) */ 80 GROUP("Group"), 81 /** A node that produces no results */ 82 NULL("Null"), 83 /** A node that limits the number of tuples returned */ 84 LIMIT("Limit"), 85 /** A node the performs set operations on two sets of tuples, including UNION */ 86 SET_OPERATION("SetOperation"); 87 88 private static final Map<String, Type> TYPE_BY_SYMBOL; 89 static { 90 Map<String, Type> typesBySymbol = new HashMap<String, Type>(); 91 for (Type type : Type.values()) { 92 typesBySymbol.put(type.getSymbol().toUpperCase(), type); 93 } 94 TYPE_BY_SYMBOL = Collections.unmodifiableMap(typesBySymbol); 95 } 96 97 private final String symbol; 98 99 private Type( String symbol ) { 100 this.symbol = symbol; 101 } 102 103 /** 104 * Get the symbol representation of this node type. 105 * 106 * @return the symbol; never null and never empty 107 */ 108 public String getSymbol() { 109 return symbol; 110 } 111 112 /** 113 * {@inheritDoc} 114 * 115 * @see java.lang.Enum#toString() 116 */ 117 @Override 118 public String toString() { 119 return symbol; 120 } 121 122 /** 123 * Attempt to find the Type given a symbol. The matching is done independent of case. 124 * 125 * @param symbol the symbol 126 * @return the Type having the supplied symbol, or null if there is no Type with the supplied symbol 127 * @throws IllegalArgumentException if the symbol is null 128 */ 129 public static Type forSymbol( String symbol ) { 130 CheckArg.isNotNull(symbol, "symbol"); 131 return TYPE_BY_SYMBOL.get(symbol.toUpperCase().trim()); 132 } 133 } 134 135 /** 136 * An enumeration dictating the type of plan tree nodes. 137 */ 138 public enum Property { 139 /** For SELECT and JOIN nodes, a flag specifying whether the criteria is dependent. Value is a {@link Boolean} object. */ 140 IS_DEPENDENT, 141 142 /** For SELECT nodes, the criteria object that is to be applied. Value is a {@link Constraint} object. */ 143 SELECT_CRITERIA, 144 145 /** For SET_OPERATION nodes, the type of set operation to be performed. Value is a {@link Operation} object. */ 146 SET_OPERATION, 147 /** For SET_OPERATION nodes, whether the 'all' clause is used. Value is a {@link Boolean} object. */ 148 SET_USE_ALL, 149 150 /** For JOIN nodes, the type of join operation. Value is a {@link JoinType} object. */ 151 JOIN_TYPE, 152 /** For JOIN nodes, the type of join algorithm. Value is a {@link JoinAlgorithm} object. */ 153 JOIN_ALGORITHM, 154 /** For JOIN nodes, the join criteria (or join condition). Value is a {@link JoinCondition} object. */ 155 JOIN_CONDITION, 156 /** 157 * For JOIN nodes, additional criteria that have been pushed down to the join. Value is a List of {@link Constraint} 158 * object. 159 */ 160 JOIN_CONSTRAINTS, 161 162 /** For SOURCE nodes, the literal name of the selector. Value is a {@link SelectorName} object. */ 163 SOURCE_NAME, 164 /** For SOURCE nodes, the alias name of the selector. Value is a {@link SelectorName} object. */ 165 SOURCE_ALIAS, 166 /** 167 * For SOURCE nodes, the collection of columns that are available. Value is a Collection of {@link Schemata.Column} 168 * objects. 169 */ 170 SOURCE_COLUMNS, 171 172 /** For PROJECT nodes, the ordered collection of columns being projected. Value is a Collection of {@link Column} objects. */ 173 PROJECT_COLUMNS, 174 175 /** 176 * For GROUP nodes, the ordered collection of columns used to group the result tuples. Value is a Collection of 177 * {@link Column} objects. 178 */ 179 GROUP_COLUMNS, 180 181 /** 182 * For SET_OPERATION nodes, the list of orderings for the results. Value is either a Collection of {@link Ordering} 183 * objects or a collection of {@link SelectorName} objects (if the sorting is being done as an input to a merge-join). 184 */ 185 SORT_ORDER_BY, 186 187 /** For LIMIT nodes, the maximum number of rows to return. Value is an {@link Integer} object. */ 188 LIMIT_COUNT, 189 /** For LIMIT nodes, the offset value. Value is an {@link Integer} object. */ 190 LIMIT_OFFSET, 191 192 /** 193 * For ACESS nodes, this signifies that the node will never return results. Value is a {@link Boolean} object, though the 194 * mere presence of this property signifies that it is no longer needed. 195 */ 196 ACCESS_NO_RESULTS 197 } 198 199 private Type type; 200 private PlanNode parent; 201 private LinkedList<PlanNode> children = new LinkedList<PlanNode>(); 202 private List<PlanNode> childrenView = Collections.unmodifiableList(children); 203 private Map<Property, Object> nodeProperties; 204 205 /** The set of named selectors (e.g., tables) that this node deals with. */ 206 private Set<SelectorName> selectors = new HashSet<SelectorName>(); 207 208 /** 209 * Create a new plan node with the supplied initial type. 210 * 211 * @param type the type of the node; may not be null 212 */ 213 public PlanNode( Type type ) { 214 assert type != null; 215 this.type = type; 216 } 217 218 /** 219 * Create a new plan node with the supplied initial type ad that is a child of the supplied parent. 220 * 221 * @param type the type of the node; may not be null 222 * @param parent the parent node, or null if there is no parent 223 */ 224 public PlanNode( Type type, 225 PlanNode parent ) { 226 assert type != null; 227 this.type = type; 228 if (parent != null) { 229 this.parent = parent; 230 this.parent.children.add(this); 231 } 232 } 233 234 /** 235 * Create a new plan node with the supplied initial type ad that is a child of the supplied parent. 236 * 237 * @param type the type of the node; may not be null 238 * @param selectors the selectors that should be assigned to this node 239 */ 240 public PlanNode( Type type, 241 SelectorName... selectors ) { 242 this(type); 243 for (SelectorName selector : selectors) { 244 addSelector(selector); 245 } 246 } 247 248 /** 249 * Create a new plan node with the supplied initial type ad that is a child of the supplied parent. 250 * 251 * @param type the type of the node; may not be null 252 * @param selectors the selectors that should be assigned to this node 253 */ 254 public PlanNode( Type type, 255 Iterable<SelectorName> selectors ) { 256 this(type); 257 addSelectors(selectors); 258 } 259 260 /** 261 * Create a new plan node with the supplied initial type ad that is a child of the supplied parent. 262 * 263 * @param type the type of the node; may not be null 264 * @param parent the parent node, or null if there is no parent 265 * @param selectors the selectors that should be assigned to this node 266 */ 267 public PlanNode( Type type, 268 PlanNode parent, 269 SelectorName... selectors ) { 270 this(type, parent); 271 for (SelectorName selector : selectors) { 272 addSelector(selector); 273 } 274 } 275 276 /** 277 * Create a new plan node with the supplied initial type ad that is a child of the supplied parent. 278 * 279 * @param type the type of the node; may not be null 280 * @param parent the parent node, or null if there is no parent 281 * @param selectors the selectors that should be assigned to this node 282 */ 283 public PlanNode( Type type, 284 PlanNode parent, 285 Iterable<SelectorName> selectors ) { 286 this(type, parent); 287 addSelectors(selectors); 288 } 289 290 /** 291 * Get the type for this node. 292 * 293 * @return the node type, or null if there is no node type 294 */ 295 public Type getType() { 296 return type; 297 } 298 299 /** 300 * Set the type for this node. 301 * 302 * @param type Sets type to the specified value; may not be null 303 */ 304 public void setType( Type type ) { 305 assert type != null; 306 this.type = type; 307 } 308 309 /** 310 * Return true if this node's type does not match the supplied type 311 * 312 * @param type the type to compare 313 * @return true if this node's type is different than that supplied, or false if they are the same 314 */ 315 public boolean isNot( Type type ) { 316 return this.type != type; 317 } 318 319 /** 320 * Return true if this node's type does not match any of the supplied types 321 * 322 * @param first the type to compare 323 * @param rest the additional types to compare 324 * @return true if this node's type is different than all of those supplied, or false if matches one of the supplied types 325 */ 326 public boolean isNotOneOf( Type first, 327 Type... rest ) { 328 return isNotOneOf(EnumSet.of(first, rest)); 329 } 330 331 /** 332 * Return true if this node's type does not match any of the supplied types 333 * 334 * @param types the types to compare 335 * @return true if this node's type is different than all of those supplied, or false if matches one of the supplied types 336 */ 337 public boolean isNotOneOf( Set<Type> types ) { 338 return !types.contains(type); 339 } 340 341 /** 342 * Return true if this node's type does match the supplied type 343 * 344 * @param type the type to compare 345 * @return true if this node's type is the same as that supplied, or false if the types are different 346 */ 347 public boolean is( Type type ) { 348 return this.type == type; 349 } 350 351 /** 352 * Return true if this node's type matches one of the supplied types 353 * 354 * @param first the type to compare 355 * @param rest the additional types to compare 356 * @return true if this node's type is one of those supplied, or false otherwise 357 */ 358 public boolean isOneOf( Type first, 359 Type... rest ) { 360 return isOneOf(EnumSet.of(first, rest)); 361 } 362 363 /** 364 * Return true if this node's type matches one of the supplied types 365 * 366 * @param types the types to compare 367 * @return true if this node's type is one of those supplied, or false otherwise 368 */ 369 public boolean isOneOf( Set<Type> types ) { 370 return types.contains(type); 371 } 372 373 /** 374 * Determine if the supplied node is an ancestor of this node. 375 * 376 * @param possibleAncestor the node that is to be determined if it is an ancestor 377 * @return true if the supplied node is indeed an ancestor, or false if it is not an ancestor 378 */ 379 public boolean isBelow( PlanNode possibleAncestor ) { 380 PlanNode node = this; 381 while (node != null) { 382 if (node == possibleAncestor) return true; 383 node = node.getParent(); 384 } 385 return false; 386 } 387 388 /** 389 * Determine if the supplied node is a descendant of this node. 390 * 391 * @param possibleDescendant the node that is to be determined if it is a descendant 392 * @return true if the supplied node is indeed an ancestor, or false if it is not an ancestor 393 */ 394 public boolean isAbove( PlanNode possibleDescendant ) { 395 return possibleDescendant != null && possibleDescendant.isBelow(this); 396 } 397 398 /** 399 * Get the parent of this node. 400 * 401 * @return the parent node, or null if this node has no parent 402 */ 403 public PlanNode getParent() { 404 return parent; 405 } 406 407 /** 408 * Set the parent for this node. If this node already has a parent, this method will remove this node from the current parent. 409 * If the supplied parent is not null, then this node will be added to the supplied parent's children. 410 * 411 * @param parent the new parent, or null if this node is to have no parent 412 */ 413 public void setParent( PlanNode parent ) { 414 removeFromParent(); 415 if (parent != null) { 416 this.parent = parent; 417 this.parent.children.add(this); 418 } 419 } 420 421 /** 422 * Insert the supplied node into the plan node tree immediately above this node. If this node has a parent when this method is 423 * called, the new parent essentially takes the place of this node within the list of children of the old parent. This method 424 * does nothing if the supplied new parent is null. 425 * <p> 426 * For example, consider a plan node tree before this method is called: 427 * 428 * <pre> 429 * A 430 * / | \ 431 * / | \ 432 * B C D 433 * </pre> 434 * 435 * Then after this method is called with <code>c.insertAsParent(e)</code>, the resulting plan node tree will be: 436 * 437 * <pre> 438 * A 439 * / | \ 440 * / | \ 441 * B E D 442 * | 443 * | 444 * C 445 * </pre> 446 * 447 * </p> 448 * <p> 449 * Also note that the node on which this method is called ('C' in the example above) will always be added as the 450 * {@link #addLastChild(PlanNode) last child} to the new parent. This allows the new parent to already have children before 451 * this method is called. 452 * </p> 453 * 454 * @param newParent the new parent; method does nothing if this is null 455 */ 456 public void insertAsParent( PlanNode newParent ) { 457 if (newParent == null) return; 458 newParent.removeFromParent(); 459 if (this.parent != null) { 460 this.parent.replaceChild(this, newParent); 461 } 462 newParent.addLastChild(this); 463 } 464 465 /** 466 * Remove this node from its parent, and return the node that used to be the parent of this node. Note that this method 467 * removes the entire subgraph under this node. 468 * 469 * @return the node that was the parent of this node, or null if this node had no parent 470 * @see #extractChild(PlanNode) 471 * @see #extractFromParent() 472 */ 473 public PlanNode removeFromParent() { 474 PlanNode result = this.parent; 475 if (this.parent != null) { 476 // Remove this node from its current parent ... 477 this.parent.children.remove(this); 478 this.parent = null; 479 } 480 return result; 481 } 482 483 /** 484 * Get the unmodifiable list of child nodes. This list will immediately reflect any changes made to the children (via other 485 * methods), but this list cannot be used to add or remove children. 486 * 487 * @return the list of children, which immediately reflects changes but which cannot be modified directly; never null 488 */ 489 public List<PlanNode> getChildren() { 490 return childrenView; 491 } 492 493 /** 494 * {@inheritDoc} 495 * <p> 496 * This iterator is immutable. 497 * </p> 498 * 499 * @see java.lang.Iterable#iterator() 500 */ 501 public Iterator<PlanNode> iterator() { 502 return childrenView.iterator(); 503 } 504 505 /** 506 * Remove all children from this node. All nodes immediately become orphaned. The resulting list will be mutable. 507 * 508 * @return a copy of all the of the children that were removed (and which have no parent); never null 509 */ 510 public List<PlanNode> removeAllChildren() { 511 if (this.children.isEmpty()) { 512 return new ArrayList<PlanNode>(0); 513 } 514 List<PlanNode> copyOfChildren = new ArrayList<PlanNode>(this.children); 515 for (Iterator<PlanNode> childIter = this.children.iterator(); childIter.hasNext();) { 516 PlanNode child = childIter.next(); 517 childIter.remove(); 518 child.parent = null; 519 } 520 return copyOfChildren; 521 } 522 523 /** 524 * Replace the supplied child with another node. If the replacement is already a child of this node, this method effectively 525 * swaps the position of the child and replacement nodes. 526 * 527 * @param child the node that is already a child and that is to be replaced; may not be null and must be a child 528 * @param replacement the node that is to replace the 'child' node; may not be null 529 * @return true if the child was successfully replaced 530 */ 531 public boolean replaceChild( PlanNode child, 532 PlanNode replacement ) { 533 assert child != null; 534 assert replacement != null; 535 if (child.parent == this) { 536 int i = this.children.indexOf(child); 537 if (replacement.parent == this) { 538 // Swapping the positions ... 539 int j = this.children.indexOf(replacement); 540 this.children.set(i, replacement); 541 this.children.set(j, child); 542 return true; 543 } 544 // The replacement is not yet a child ... 545 this.children.set(i, replacement); 546 replacement.removeFromParent(); 547 replacement.parent = this; 548 child.parent = null; 549 return true; 550 } 551 return false; 552 } 553 554 /** 555 * Get the number of child nodes. 556 * 557 * @return the number of children; never negative 558 */ 559 public int getChildCount() { 560 return this.children.size(); 561 } 562 563 /** 564 * Get the first child. 565 * 566 * @return the first child, or null if there are no children 567 */ 568 public PlanNode getFirstChild() { 569 return this.children.isEmpty() ? null : this.children.getFirst(); 570 } 571 572 /** 573 * Get the last child. 574 * 575 * @return the last child, or null if there are no children 576 */ 577 public PlanNode getLastChild() { 578 return this.children.isEmpty() ? null : this.children.getLast(); 579 } 580 581 /** 582 * Get the child at the supplied index. 583 * 584 * @param index the index 585 * @return the child, or null if there are no children 586 * @throws IndexOutOfBoundsException if the index is not valid given the number of children 587 */ 588 public PlanNode getChild( int index ) { 589 return this.children.isEmpty() ? null : this.children.get(index); 590 } 591 592 /** 593 * Add the supplied node to the front of the list of children. 594 * 595 * @param child the node that should be added as the first child; may not be null 596 */ 597 public void addFirstChild( PlanNode child ) { 598 assert child != null; 599 this.children.addFirst(child); 600 child.removeFromParent(); 601 child.parent = this; 602 } 603 604 /** 605 * Add the supplied node to the end of the list of children. 606 * 607 * @param child the node that should be added as the last child; may not be null 608 */ 609 public void addLastChild( PlanNode child ) { 610 assert child != null; 611 this.children.addLast(child); 612 child.removeFromParent(); 613 child.parent = this; 614 } 615 616 /** 617 * Add the supplied nodes at the end of the list of children. 618 * 619 * @param otherChildren the children to add; may not be null 620 */ 621 public void addChildren( Iterable<PlanNode> otherChildren ) { 622 assert otherChildren != null; 623 for (PlanNode planNode : otherChildren) { 624 this.addLastChild(planNode); 625 } 626 } 627 628 /** 629 * Add the supplied nodes at the end of the list of children. 630 * 631 * @param first the first child to add 632 * @param second the second child to add 633 */ 634 public void addChildren( PlanNode first, 635 PlanNode second ) { 636 if (first != null) this.addLastChild(first); 637 if (second != null) this.addLastChild(second); 638 } 639 640 /** 641 * Add the supplied nodes at the end of the list of children. 642 * 643 * @param first the first child to add 644 * @param second the second child to add 645 * @param third the third child to add 646 */ 647 public void addChildren( PlanNode first, 648 PlanNode second, 649 PlanNode third ) { 650 if (first != null) this.addLastChild(first); 651 if (second != null) this.addLastChild(second); 652 if (third != null) this.addLastChild(third); 653 } 654 655 /** 656 * Remove the node from this node. 657 * 658 * @param child the child node; may not be null 659 * @return true if the child was removed from this node, or false if the supplied node was not a child of this node 660 */ 661 public boolean removeChild( PlanNode child ) { 662 boolean result = this.children.remove(child); 663 if (result) { 664 child.parent = null; 665 } 666 return result; 667 } 668 669 /** 670 * Remove the child node from this node, and replace that child with its first child (if there is one). 671 * 672 * @param child the child to be extracted; may not be null and must have at most 1 child 673 * @see #extractFromParent() 674 */ 675 public void extractChild( PlanNode child ) { 676 if (child.getChildCount() == 0) { 677 removeChild(child); 678 } else { 679 PlanNode grandChild = child.getFirstChild(); 680 replaceChild(child, grandChild); 681 } 682 } 683 684 /** 685 * Extract this node from its parent, but replace this node with its child (if there is one). 686 * 687 * @see #extractChild(PlanNode) 688 */ 689 public void extractFromParent() { 690 this.parent.extractChild(this); 691 } 692 693 /** 694 * Get the keys for the property values that are set on this node. 695 * 696 * @return the property keys; never null but possibly empty 697 */ 698 public Set<Property> getPropertyKeys() { 699 return nodeProperties != null ? nodeProperties.keySet() : Collections.<Property>emptySet(); 700 } 701 702 /** 703 * Get the node's value for this supplied property. 704 * 705 * @param propertyId the property identifier 706 * @return the value, or null if there is no property on this node 707 */ 708 public Object getProperty( Property propertyId ) { 709 return nodeProperties != null ? nodeProperties.get(propertyId) : null; 710 } 711 712 /** 713 * Get the node's value for this supplied property, casting the result to the supplied type. 714 * 715 * @param <ValueType> the type of the value expected 716 * @param propertyId the property identifier 717 * @param type the class denoting the type of value expected; may not be null 718 * @return the value, or null if there is no property on this node 719 */ 720 public <ValueType> ValueType getProperty( Property propertyId, 721 Class<ValueType> type ) { 722 return nodeProperties != null ? type.cast(nodeProperties.get(propertyId)) : null; 723 } 724 725 /** 726 * Get the node's value for this supplied property, casting the result to a {@link Collection} of the supplied type. 727 * 728 * @param <ValueType> the type of the value expected 729 * @param propertyId the property identifier 730 * @param type the class denoting the type of value expected; may not be null 731 * @return the value, or null if there is no property on this node 732 */ 733 @SuppressWarnings( "unchecked" ) 734 public <ValueType> Collection<ValueType> getPropertyAsCollection( Property propertyId, 735 Class<ValueType> type ) { 736 if (nodeProperties == null) return null; 737 return (Collection)nodeProperties.get(propertyId); 738 } 739 740 /** 741 * Get the node's value for this supplied property, casting the result to a {@link List} of the supplied type. 742 * 743 * @param <ValueType> the type of the value expected 744 * @param propertyId the property identifier 745 * @param type the class denoting the type of value expected; may not be null 746 * @return the value, or null if there is no property on this node 747 */ 748 @SuppressWarnings( "unchecked" ) 749 public <ValueType> List<ValueType> getPropertyAsList( Property propertyId, 750 Class<ValueType> type ) { 751 if (nodeProperties == null) return null; 752 return (List)nodeProperties.get(propertyId); 753 } 754 755 /** 756 * Set the node's value for the supplied property. 757 * 758 * @param propertyId the property identifier 759 * @param value the value, or null if the property is to be removed 760 * @return the previous value that was overwritten by this call, or null if there was prior value 761 */ 762 public Object setProperty( Property propertyId, 763 Object value ) { 764 if (value == null) { 765 // Removing this property ... 766 return nodeProperties != null ? nodeProperties.remove(propertyId) : null; 767 } 768 // Otherwise, we're adding the property 769 if (nodeProperties == null) nodeProperties = new HashMap<Property, Object>(); 770 return nodeProperties.put(propertyId, value); 771 } 772 773 /** 774 * Remove the node's value for this supplied property. 775 * 776 * @param propertyId the property identifier 777 * @return the value that was removed, or null if there was no property on this node 778 */ 779 public Object removeProperty( Object propertyId ) { 780 return nodeProperties != null ? nodeProperties.remove(propertyId) : null; 781 } 782 783 /** 784 * Indicates if there is a non-null value for the property. 785 * 786 * @param propertyId the property identifier 787 * @return true if this node has a non-null value for that property, or false if the value is null or there is no property 788 */ 789 public boolean hasProperty( Property propertyId ) { 790 return nodeProperties != null && nodeProperties.containsKey(propertyId); 791 } 792 793 /** 794 * Indicates if there is a non-null and non-empty Collection value for the property. 795 * 796 * @param propertyId the property identifier 797 * @return true if this node has value for the supplied property and that value is a non-empty Collection 798 */ 799 public boolean hasCollectionProperty( Property propertyId ) { 800 Object value = getProperty(propertyId); 801 return (value instanceof Collection && !((Collection<?>)value).isEmpty()); 802 } 803 804 /** 805 * Indicates if there is a non-null property value that equates to a <code>true</code> boolean value. 806 * 807 * @param propertyId the property identifier 808 * @return true if this node has value for the supplied property and that value is a boolean value of <code>true</code> 809 */ 810 public boolean hasBooleanProperty( Property propertyId ) { 811 Object value = getProperty(propertyId); 812 return (value instanceof Boolean && ((Boolean)value).booleanValue()); 813 } 814 815 /** 816 * Add a selector to this plan node. This method does nothing if the supplied selector is null. 817 * 818 * @param symbol the symbol of the selector 819 */ 820 public void addSelector( SelectorName symbol ) { 821 if (symbol != null) selectors.add(symbol); 822 } 823 824 /** 825 * Add the selectors to this plan node. This method does nothing for any supplied selector that is null. 826 * 827 * @param first the first symbol to be added 828 * @param second the second symbol to be added 829 */ 830 public void addSelector( SelectorName first, 831 SelectorName second ) { 832 if (first != null) selectors.add(first); 833 if (second != null) selectors.add(second); 834 } 835 836 /** 837 * Add the selectors to this plan node. This method does nothing for any supplied selector that is null. 838 * 839 * @param names the symbols to be added 840 */ 841 public void addSelectors( Iterable<SelectorName> names ) { 842 for (SelectorName name : names) { 843 if (name != null) selectors.add(name); 844 } 845 } 846 847 /** 848 * Get the selectors that are referenced by this plan node. 849 * 850 * @return the names of the selectors; never null but possibly empty 851 */ 852 public Set<SelectorName> getSelectors() { 853 return selectors; 854 } 855 856 /** 857 * Get the path from this node (inclusive) to the supplied descendant node (inclusive) 858 * 859 * @param descendant the descendant; may not be null, and must be a descendant of this node 860 * @return the path from this node to the supplied descendant node; never null 861 */ 862 public LinkedList<PlanNode> getPathTo( PlanNode descendant ) { 863 assert descendant != null; 864 LinkedList<PlanNode> stack = new LinkedList<PlanNode>(); 865 PlanNode node = descendant; 866 while (node != this) { 867 stack.addFirst(node); 868 node = node.getParent(); 869 assert node != null : "The supplied node is not a descendant of this node"; 870 } 871 stack.addFirst(this); 872 return stack; 873 } 874 875 /** 876 * Determine whether this node has an ancestor with the supplied type. 877 * 878 * @param type the type; may not be null 879 * @return true if there is at least one ancestor of the supplied type, or false otherwise 880 */ 881 public boolean hasAncestorOfType( Type type ) { 882 return hasAncestorOfType(EnumSet.of(type)); 883 } 884 885 /** 886 * Determine whether this node has an ancestor with any of the supplied types. 887 * 888 * @param firstType the first type; may not be null 889 * @param additionalTypes the additional types; may not be null 890 * @return true if there is at least one ancestor that has any of the supplied types, or false otherwise 891 */ 892 public boolean hasAncestorOfType( Type firstType, 893 Type... additionalTypes ) { 894 return hasAncestorOfType(EnumSet.of(firstType, additionalTypes)); 895 } 896 897 /** 898 * Determine whether this node has an ancestor with any of the supplied types. 899 * 900 * @param types the types; may not be null 901 * @return true if there is at least one ancestor that has any of the supplied types, or false otherwise 902 */ 903 public boolean hasAncestorOfType( Set<Type> types ) { 904 PlanNode node = this.parent; 905 while (node != null) { 906 if (types.contains(node.getType())) return true; 907 node = node.getParent(); 908 } 909 return false; 910 } 911 912 /** 913 * {@inheritDoc} 914 * 915 * @see java.lang.Object#toString() 916 */ 917 @Override 918 public String toString() { 919 return getString(); 920 } 921 922 /** 923 * {@inheritDoc} 924 * 925 * @see java.lang.Object#equals(java.lang.Object) 926 */ 927 @Override 928 public final boolean equals( Object obj ) { 929 // Quite a few methods rely upon instance/reference equality ... 930 return super.equals(obj); 931 } 932 933 /** 934 * {@inheritDoc} 935 * <p> 936 * This class returns a new clone of the plan tree rooted at this node. However, the top node of the resulting plan tree (that 937 * is, the node returned from this method) has no parent. 938 * </p> 939 * 940 * @see java.lang.Object#clone() 941 */ 942 @Override 943 public PlanNode clone() { 944 return cloneWithoutNewParent(); 945 } 946 947 protected PlanNode cloneWithoutNewParent() { 948 PlanNode result = new PlanNode(this.type, null, this.selectors); 949 if (this.nodeProperties != null && !this.nodeProperties.isEmpty()) { 950 result.nodeProperties = new HashMap<Property, Object>(this.nodeProperties); 951 } 952 // Clone the children ... 953 for (PlanNode child : children) { 954 PlanNode childClone = child.cloneWithoutNewParent(); 955 // The child has no parent, so add the child to the new result ... 956 result.addLastChild(childClone); 957 } 958 return result; 959 } 960 961 /** 962 * Determine whether the supplied plan is equivalent to this plan. 963 * 964 * @param other the other plan to compare with this instance 965 * @return true if the two plans are equivalent, or false otherwise 966 */ 967 public boolean isSameAs( PlanNode other ) { 968 if (other == null) return false; 969 if (this.getType() != other.getType()) return false; 970 if (!ObjectUtil.isEqualWithNulls(this.nodeProperties, other.nodeProperties)) return false; 971 if (!this.getSelectors().equals(other.getSelectors())) return false; 972 if (this.getChildCount() != other.getChildCount()) return false; 973 Iterator<PlanNode> thisChildren = this.getChildren().iterator(); 974 Iterator<PlanNode> thatChildren = other.getChildren().iterator(); 975 while (thisChildren.hasNext() && thatChildren.hasNext()) { 976 if (!thisChildren.next().isSameAs(thatChildren.next())) return false; 977 } 978 return true; 979 } 980 981 /** 982 * {@inheritDoc} 983 * 984 * @see org.modeshape.graph.query.model.Readable#getString() 985 */ 986 public String getString() { 987 StringBuilder sb = new StringBuilder(); 988 getRecursiveString(sb, 0); 989 return sb.toString(); 990 } 991 992 private void getRecursiveString( StringBuilder str, 993 int indentLevel ) { 994 for (int i = 0; i < indentLevel; ++i) { 995 str.append(" "); 996 } 997 getNodeString(str).append('\n'); 998 999 // Recursively add children at one greater tab level 1000 for (PlanNode child : this) { 1001 child.getRecursiveString(str, indentLevel + 1); 1002 } 1003 } 1004 1005 private StringBuilder getNodeString( StringBuilder str ) { 1006 str.append(this.type.getSymbol()); 1007 if (!selectors.isEmpty()) { 1008 str.append(" ["); 1009 boolean first = true; 1010 for (SelectorName symbol : selectors) { 1011 if (first) first = false; 1012 else str.append(','); 1013 str.append(symbol.getName()); 1014 } 1015 str.append(']'); 1016 } 1017 if (nodeProperties != null && !nodeProperties.isEmpty()) { 1018 str.append(" <"); 1019 boolean first = true; 1020 for (Map.Entry<Property, Object> entry : nodeProperties.entrySet()) { 1021 if (first) first = false; 1022 else str.append(", "); 1023 str.append(entry.getKey()).append('='); 1024 Object value = entry.getValue(); 1025 if (value instanceof Visitable) { 1026 str.append(Visitors.readable((Visitable)value)); 1027 } else if (value instanceof Collection) { 1028 boolean firstItem = true; 1029 str.append('['); 1030 for (Object item : (Collection<?>)value) { 1031 if (firstItem) firstItem = false; 1032 else str.append(", "); 1033 if (item instanceof Visitable) { 1034 str.append(Visitors.readable((Visitable)item)); 1035 } else { 1036 str.append(item); 1037 } 1038 } 1039 str.append(']'); 1040 } else { 1041 str.append(value); 1042 } 1043 } 1044 str.append('>'); 1045 } 1046 return str; 1047 } 1048 1049 /** 1050 * Starting at the parent of this node, find the lowest (also closest) ancestor that has the specified type. 1051 * 1052 * @param typeToFind the type of the node to find; may not be null 1053 * @return the node with the specified type, or null if there is no such ancestor 1054 */ 1055 public PlanNode findAncestor( Type typeToFind ) { 1056 return findAncestor(EnumSet.of(typeToFind)); 1057 } 1058 1059 /** 1060 * Starting at the parent of this node, find the lowest (also closest) ancestor that has one of the specified types. 1061 * 1062 * @param firstTypeToFind the first type to find; may not be null 1063 * @param additionalTypesToFind additional types to find; may not be null 1064 * @return the node with the specified type, or null if there is no such ancestor 1065 */ 1066 public PlanNode findAncestor( Type firstTypeToFind, 1067 Type... additionalTypesToFind ) { 1068 return findAncestor(EnumSet.of(firstTypeToFind, additionalTypesToFind)); 1069 } 1070 1071 /** 1072 * Starting at the parent of this node, find the lowest (also closest) ancestor that has one of the specified types. 1073 * 1074 * @param typesToFind the set of types to find; may not be null 1075 * @return the node with one of the specified types, or null if there is no such ancestor 1076 */ 1077 public PlanNode findAncestor( Set<Type> typesToFind ) { 1078 PlanNode node = this; 1079 PlanNode parent = null; 1080 while ((parent = node.getParent()) != null) { 1081 if (typesToFind.contains(parent.getType())) return parent; 1082 node = parent; 1083 } 1084 return null; 1085 } 1086 1087 public static enum Traversal { 1088 LEVEL_ORDER, 1089 PRE_ORDER; 1090 } 1091 1092 /** 1093 * Find all of the nodes that are at or below this node. 1094 * 1095 * @return the collection of nodes that are at or below this node; never null and never empty 1096 */ 1097 public List<PlanNode> findAllAtOrBelow() { 1098 return findAllAtOrBelow(Traversal.PRE_ORDER); 1099 } 1100 1101 /** 1102 * Find all of the nodes that are at or below this node. 1103 * 1104 * @param order the order to traverse; may not be null 1105 * @return the collection of nodes that are at or below this node; never null and never empty 1106 */ 1107 public List<PlanNode> findAllAtOrBelow( Traversal order ) { 1108 assert order != null; 1109 List<PlanNode> results = new LinkedList<PlanNode>(); 1110 LinkedList<PlanNode> queue = new LinkedList<PlanNode>(); 1111 queue.add(this); 1112 while (!queue.isEmpty()) { 1113 PlanNode aNode = queue.poll(); 1114 switch (order) { 1115 case LEVEL_ORDER: 1116 queue.addAll(aNode.getChildren()); 1117 break; 1118 case PRE_ORDER: 1119 queue.addAll(0, aNode.getChildren()); 1120 break; 1121 } 1122 } 1123 return results; 1124 } 1125 1126 /** 1127 * Find all of the nodes of the specified type that are at or below this node. 1128 * 1129 * @param typeToFind the type of node to find; may not be null 1130 * @return the collection of nodes that are at or below this node that all have the supplied type; never null but possibly 1131 * empty 1132 */ 1133 public List<PlanNode> findAllAtOrBelow( Type typeToFind ) { 1134 return findAllAtOrBelow(EnumSet.of(typeToFind)); 1135 } 1136 1137 /** 1138 * Find all of the nodes with one of the specified types that are at or below this node. 1139 * 1140 * @param firstTypeToFind the first type of node to find; may not be null 1141 * @param additionalTypesToFind the additional types of node to find; may not be null 1142 * @return the collection of nodes that are at or below this node that all have one of the supplied types; never null but 1143 * possibly empty 1144 */ 1145 public List<PlanNode> findAllAtOrBelow( Type firstTypeToFind, 1146 Type... additionalTypesToFind ) { 1147 return findAllAtOrBelow(EnumSet.of(firstTypeToFind, additionalTypesToFind)); 1148 } 1149 1150 /** 1151 * Find all of the nodes with one of the specified types that are at or below this node. 1152 * 1153 * @param typesToFind the types of node to find; may not be null 1154 * @return the collection of nodes that are at or below this node that all have one of the supplied types; never null but 1155 * possibly empty 1156 */ 1157 public List<PlanNode> findAllAtOrBelow( Set<Type> typesToFind ) { 1158 return findAllAtOrBelow(Traversal.PRE_ORDER, typesToFind); 1159 } 1160 1161 /** 1162 * Find all of the nodes of the specified type that are at or below this node. 1163 * 1164 * @param order the order to traverse; may not be null 1165 * @param typeToFind the type of node to find; may not be null 1166 * @return the collection of nodes that are at or below this node that all have the supplied type; never null but possibly 1167 * empty 1168 */ 1169 public List<PlanNode> findAllAtOrBelow( Traversal order, 1170 Type typeToFind ) { 1171 return findAllAtOrBelow(order, EnumSet.of(typeToFind)); 1172 } 1173 1174 /** 1175 * Find all of the nodes with one of the specified types that are at or below this node. 1176 * 1177 * @param order the order to traverse; may not be null 1178 * @param firstTypeToFind the first type of node to find; may not be null 1179 * @param additionalTypesToFind the additional types of node to find; may not be null 1180 * @return the collection of nodes that are at or below this node that all have one of the supplied types; never null but 1181 * possibly empty 1182 */ 1183 public List<PlanNode> findAllAtOrBelow( Traversal order, 1184 Type firstTypeToFind, 1185 Type... additionalTypesToFind ) { 1186 return findAllAtOrBelow(order, EnumSet.of(firstTypeToFind, additionalTypesToFind)); 1187 } 1188 1189 /** 1190 * Find all of the nodes with one of the specified types that are at or below this node. 1191 * 1192 * @param order the order to traverse; may not be null 1193 * @param typesToFind the types of node to find; may not be null 1194 * @return the collection of nodes that are at or below this node that all have one of the supplied types; never null but 1195 * possibly empty 1196 */ 1197 public List<PlanNode> findAllAtOrBelow( Traversal order, 1198 Set<Type> typesToFind ) { 1199 assert order != null; 1200 List<PlanNode> results = new LinkedList<PlanNode>(); 1201 LinkedList<PlanNode> queue = new LinkedList<PlanNode>(); 1202 queue.add(this); 1203 while (!queue.isEmpty()) { 1204 PlanNode aNode = queue.poll(); 1205 if (typesToFind.contains(aNode.getType())) { 1206 results.add(aNode); 1207 } 1208 switch (order) { 1209 case LEVEL_ORDER: 1210 queue.addAll(aNode.getChildren()); 1211 break; 1212 case PRE_ORDER: 1213 queue.addAll(0, aNode.getChildren()); 1214 break; 1215 } 1216 } 1217 return results; 1218 } 1219 1220 /** 1221 * Find the first node with the specified type that are at or below this node. 1222 * 1223 * @param typeToFind the type of node to find; may not be null 1224 * @return the first node that is at or below this node that has the supplied type; or null if there is no such node 1225 */ 1226 public PlanNode findAtOrBelow( Type typeToFind ) { 1227 return findAtOrBelow(EnumSet.of(typeToFind)); 1228 } 1229 1230 /** 1231 * Find the first node with one of the specified types that are at or below this node. 1232 * 1233 * @param firstTypeToFind the first type of node to find; may not be null 1234 * @param additionalTypesToFind the additional types of node to find; may not be null 1235 * @return the first node that is at or below this node that has one of the supplied types; or null if there is no such node 1236 */ 1237 public PlanNode findAtOrBelow( Type firstTypeToFind, 1238 Type... additionalTypesToFind ) { 1239 return findAtOrBelow(EnumSet.of(firstTypeToFind, additionalTypesToFind)); 1240 } 1241 1242 /** 1243 * Find the first node with one of the specified types that are at or below this node. 1244 * 1245 * @param typesToFind the types of node to find; may not be null 1246 * @return the first node that is at or below this node that has one of the supplied types; or null if there is no such node 1247 */ 1248 public PlanNode findAtOrBelow( Set<Type> typesToFind ) { 1249 return findAtOrBelow(Traversal.PRE_ORDER, typesToFind); 1250 } 1251 1252 /** 1253 * Find the first node with the specified type that are at or below this node. 1254 * 1255 * @param order the order to traverse; may not be null 1256 * @param typeToFind the type of node to find; may not be null 1257 * @return the first node that is at or below this node that has the supplied type; or null if there is no such node 1258 */ 1259 public PlanNode findAtOrBelow( Traversal order, 1260 Type typeToFind ) { 1261 return findAtOrBelow(order, EnumSet.of(typeToFind)); 1262 } 1263 1264 /** 1265 * Find the first node with one of the specified types that are at or below this node. 1266 * 1267 * @param order the order to traverse; may not be null 1268 * @param firstTypeToFind the first type of node to find; may not be null 1269 * @param additionalTypesToFind the additional types of node to find; may not be null 1270 * @return the first node that is at or below this node that has one of the supplied types; or null if there is no such node 1271 */ 1272 public PlanNode findAtOrBelow( Traversal order, 1273 Type firstTypeToFind, 1274 Type... additionalTypesToFind ) { 1275 return findAtOrBelow(order, EnumSet.of(firstTypeToFind, additionalTypesToFind)); 1276 } 1277 1278 /** 1279 * Find the first node with one of the specified types that are at or below this node. 1280 * 1281 * @param order the order to traverse; may not be null 1282 * @param typesToFind the types of node to find; may not be null 1283 * @return the first node that is at or below this node that has one of the supplied types; or null if there is no such node 1284 */ 1285 public PlanNode findAtOrBelow( Traversal order, 1286 Set<Type> typesToFind ) { 1287 LinkedList<PlanNode> queue = new LinkedList<PlanNode>(); 1288 queue.add(this); 1289 while (!queue.isEmpty()) { 1290 PlanNode aNode = queue.poll(); 1291 if (typesToFind.contains(aNode.getType())) { 1292 return aNode; 1293 } 1294 switch (order) { 1295 case LEVEL_ORDER: 1296 queue.addAll(aNode.getChildren()); 1297 break; 1298 case PRE_ORDER: 1299 queue.addAll(0, aNode.getChildren()); 1300 break; 1301 } 1302 } 1303 return null; 1304 } 1305 1306 }