View Javadoc

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 }