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