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.process;
25  
26  import java.util.Comparator;
27  import org.modeshape.graph.Location;
28  import org.modeshape.graph.property.Path;
29  import org.modeshape.graph.property.ValueComparators;
30  import org.modeshape.graph.query.QueryContext;
31  import org.modeshape.graph.query.QueryResults.Columns;
32  import org.modeshape.graph.query.model.ChildNodeJoinCondition;
33  import org.modeshape.graph.query.model.DescendantNodeJoinCondition;
34  import org.modeshape.graph.query.model.EquiJoinCondition;
35  import org.modeshape.graph.query.model.JoinCondition;
36  import org.modeshape.graph.query.model.JoinType;
37  import org.modeshape.graph.query.model.SameNodeJoinCondition;
38  import org.modeshape.graph.query.model.SelectorName;
39  import org.modeshape.graph.query.model.TypeSystem;
40  import org.modeshape.graph.query.model.TypeSystem.TypeFactory;
41  import org.modeshape.graph.query.validate.Schemata;
42  
43  /**
44   * 
45   */
46  public abstract class JoinComponent extends ProcessingComponent {
47  
48      protected static final Comparator<Location> LOCATION_COMPARATOR = Location.comparator();
49  
50      private final ProcessingComponent left;
51      private final ProcessingComponent right;
52      private final JoinCondition condition;
53      private final JoinType joinType;
54  
55      protected JoinComponent( QueryContext context,
56                               ProcessingComponent left,
57                               ProcessingComponent right,
58                               JoinCondition condition,
59                               JoinType joinType ) {
60          super(context, left.getColumns().joinWith(right.getColumns()));
61          this.left = left;
62          this.right = right;
63          this.joinType = joinType;
64          this.condition = condition;
65          assert this.left != null;
66          assert this.right != null;
67          assert this.joinType != null;
68      }
69  
70      /**
71       * Get the type of join this processor represents.
72       * 
73       * @return the join type; never null
74       */
75      public final JoinType getJoinType() {
76          return joinType;
77      }
78  
79      /**
80       * Get the join condition.
81       * 
82       * @return the join condition; never null
83       */
84      public final JoinCondition getJoinCondition() {
85          return condition;
86      }
87  
88      /**
89       * Get the processing component that serves as the left side of the join.
90       * 
91       * @return the left-side processing component; never null
92       */
93      protected final ProcessingComponent left() {
94          return left;
95      }
96  
97      /**
98       * Get the processing component that serves as the right side of the join.
99       * 
100      * @return the right-side processing component; never null
101      */
102     protected final ProcessingComponent right() {
103         return right;
104     }
105 
106     /**
107      * Get the columns definition for the results from the left side of the join.
108      * 
109      * @return the left-side columns that feed this join; never null
110      */
111     protected final Columns leftColunns() {
112         return left.getColumns();
113     }
114 
115     /**
116      * Get the columns definition for the results from the right side of the join.
117      * 
118      * @return the right-side columns that feed this join; never null
119      */
120     protected final Columns rightColumns() {
121         return right.getColumns();
122     }
123 
124     /**
125      * Create a {@link TupleMerger} implementation that will combine a tuple fitting the left columns with a tuple fitting the
126      * right columns. This merger will properly place all of the values, locations, and scores such that the tuples always have
127      * this arrangement:
128      * 
129      * <pre>
130      *    [ <i>v1</i>, <i>v2</i>, ..., <i>vM</i>, <i>loc1</i>, <i>loc2</i>, ..., <i>locN</i>, <i>s1</i>, <i>s2</i>, ..., <i>sN</i> ]
131      * </pre>
132      * 
133      * where <i>M</i> is the number of values in the tuple, and <i>N</i> is the number of sources in the tuple.
134      * <p>
135      * Note that this merger does not actually reduce or combine values. That is done with a particular {@link JoinComponent}
136      * subclass.
137      * </p>
138      * 
139      * @param joinColumns the Columns specification for the joined/merged tuples; may not be null
140      * @param leftColumns the Columns specification for the tuple on the left side of the join; may not be null
141      * @param rightColumns the Columns specification for the tuple on the right side of the join; may not be null
142      * @return the merger implementation that will combine tuples from the left and right to form the merged tuples; never null
143      */
144     protected static TupleMerger createMerger( Columns joinColumns,
145                                                Columns leftColumns,
146                                                Columns rightColumns ) {
147         final int joinTupleSize = joinColumns.getTupleSize();
148         final int joinColumnCount = joinColumns.getColumnCount();
149         final int joinLocationCount = joinColumns.getLocationCount();
150         final int leftColumnCount = leftColumns.getColumnCount();
151         final int leftLocationCount = leftColumns.getLocationCount();
152         final int leftTupleSize = leftColumns.getTupleSize();
153         final int rightColumnCount = rightColumns.getColumnCount();
154         final int rightLocationCount = rightColumns.getLocationCount();
155         final int rightTupleSize = rightColumns.getTupleSize();
156         final int startLeftLocations = joinColumnCount;
157         final int startRightLocations = startLeftLocations + leftLocationCount;
158 
159         // The left and right selectors should NOT overlap ...
160         assert joinLocationCount == leftLocationCount + rightLocationCount;
161 
162         // Create different implementations depending upon the options, since this save us from having to make
163         // these decisions while doing the merges...
164         if (joinColumns.hasFullTextSearchScores()) {
165             final int leftScoreCount = leftTupleSize - leftColumnCount - leftLocationCount;
166             final int rightScoreCount = rightTupleSize - rightColumnCount - rightLocationCount;
167             final int startLeftScores = startRightLocations + rightLocationCount;
168             final int startRightScores = startLeftScores + leftScoreCount;
169             final int leftScoreIndex = leftTupleSize - leftScoreCount;
170             final int rightScoreIndex = rightTupleSize - rightScoreCount;
171 
172             return new TupleMerger() {
173                 /**
174                  * {@inheritDoc}
175                  * 
176                  * @see org.modeshape.graph.query.process.JoinComponent.TupleMerger#merge(java.lang.Object[], java.lang.Object[])
177                  */
178                 public Object[] merge( Object[] leftTuple,
179                                        Object[] rightTuple ) {
180                     Object[] result = new Object[joinTupleSize]; // initialized to null
181                     // If the tuple arrays are null, then we don't need to copy because the arrays are
182                     // initialized to null values.
183                     if (leftTuple != null) {
184                         // Copy the left tuple values ...
185                         System.arraycopy(leftTuple, 0, result, 0, leftColumnCount);
186                         // Copy the left tuple locations ...
187                         System.arraycopy(leftTuple, leftColumnCount, result, startLeftLocations, leftLocationCount);
188                         // Copy the left tuple scores ...
189                         System.arraycopy(leftTuple, leftScoreIndex, result, startLeftScores, leftScoreCount);
190                     }
191                     if (rightTuple != null) {
192                         // Copy the right tuple values ...
193                         System.arraycopy(rightTuple, 0, result, leftColumnCount, rightColumnCount);
194                         // Copy the right tuple locations ...
195                         System.arraycopy(rightTuple, rightColumnCount, result, startRightLocations, rightLocationCount);
196                         // Copy the right tuple scores ...
197                         System.arraycopy(rightTuple, rightScoreIndex, result, startRightScores, rightScoreCount);
198                     }
199                     return result;
200                 }
201             };
202         }
203         // There are no full-text search scores ...
204         return new TupleMerger() {
205             /**
206              * {@inheritDoc}
207              * 
208              * @see org.modeshape.graph.query.process.JoinComponent.TupleMerger#merge(java.lang.Object[], java.lang.Object[])
209              */
210             public Object[] merge( Object[] leftTuple,
211                                    Object[] rightTuple ) {
212                 Object[] result = new Object[joinTupleSize]; // initialized to null
213                 // If the tuple arrays are null, then we don't need to copy because the arrays are
214                 // initialized to null values.
215                 if (leftTuple != null) {
216                     // Copy the left tuple values ...
217                     System.arraycopy(leftTuple, 0, result, 0, leftColumnCount);
218                     System.arraycopy(leftTuple, leftColumnCount, result, startLeftLocations, leftLocationCount);
219                 }
220                 if (rightTuple != null) {
221                     // Copy the right tuple values ...
222                     System.arraycopy(rightTuple, 0, result, leftColumnCount, rightColumnCount);
223                     System.arraycopy(rightTuple, rightColumnCount, result, startRightLocations, rightLocationCount);
224                 }
225                 return result;
226             }
227         };
228     }
229 
230     /**
231      * A component that will merge the supplied tuple on the left side of a join with the supplied tuple on the right side of the
232      * join, to produce a single tuple with all components from the left and right tuples.
233      */
234     protected static interface TupleMerger {
235         Object[] merge( Object[] leftTuple,
236                         Object[] rightTuple );
237     }
238 
239     /**
240      * Interface defining the value of a tuple that is used in the join condition.
241      */
242     protected static interface ValueSelector {
243         /**
244          * Obtain the value that is to be used in the join condition.
245          * 
246          * @param tuple the tuple
247          * @return the value that should be used
248          */
249         Object evaluate( Object[] tuple );
250     }
251 
252     /**
253      * Create a {@link ValueSelector} that obtains the value required to use the supplied join condition.
254      * 
255      * @param source the source component; may not be null
256      * @param condition the join condition; may not be null
257      * @return the value selector; never null
258      */
259     protected static ValueSelector valueSelectorFor( ProcessingComponent source,
260                                                      JoinCondition condition ) {
261         if (condition instanceof ChildNodeJoinCondition) {
262             ChildNodeJoinCondition joinCondition = (ChildNodeJoinCondition)condition;
263             String childSelectorName = joinCondition.childSelectorName().name();
264             if (source.getColumns().hasSelector(childSelectorName)) {
265                 return selectPath(source, childSelectorName);
266             }
267             String parentSelectorName = joinCondition.parentSelectorName().name();
268             return selectPath(source, parentSelectorName);
269         } else if (condition instanceof SameNodeJoinCondition) {
270             SameNodeJoinCondition joinCondition = (SameNodeJoinCondition)condition;
271             String selector1Name = joinCondition.selector1Name().name();
272             if (source.getColumns().hasSelector(selector1Name)) {
273                 return selectPath(source, selector1Name);
274             }
275             String selector2Name = joinCondition.selector2Name().name();
276             return selectPath(source, selector2Name);
277         } else if (condition instanceof DescendantNodeJoinCondition) {
278             DescendantNodeJoinCondition joinCondition = (DescendantNodeJoinCondition)condition;
279             String ancestorSelectorName = joinCondition.ancestorSelectorName().name();
280             if (source.getColumns().hasSelector(ancestorSelectorName)) {
281                 return selectPath(source, ancestorSelectorName);
282             }
283             String descendantSelectorName = joinCondition.descendantSelectorName().name();
284             return selectPath(source, descendantSelectorName);
285         } else if (condition instanceof EquiJoinCondition) {
286             EquiJoinCondition joinCondition = (EquiJoinCondition)condition;
287             SelectorName selector1Name = joinCondition.selector1Name();
288             String propName1 = joinCondition.property1Name();
289             if (source.getColumns().hasSelector(selector1Name.name())) {
290                 return selectValue(source, selector1Name, propName1);
291             }
292             SelectorName selector2Name = joinCondition.selector2Name();
293             String propName2 = joinCondition.property2Name();
294             return selectValue(source, selector2Name, propName2);
295         }
296         throw new IllegalArgumentException();
297     }
298 
299     private static ValueSelector selectPath( ProcessingComponent component,
300                                              String selectorName ) {
301         final int index = component.getColumns().getLocationIndex(selectorName);
302         return new ValueSelector() {
303             public Object evaluate( Object[] tuple ) {
304                 return tuple[index]; // Location
305             }
306         };
307     }
308 
309     private static ValueSelector selectValue( ProcessingComponent component,
310                                               SelectorName selectorName,
311                                               String propertyName ) {
312         final int index = component.getColumns().getColumnIndexForProperty(selectorName.name(), propertyName);
313         return new ValueSelector() {
314             public Object evaluate( Object[] tuple ) {
315                 return tuple[index];
316             }
317         };
318     }
319 
320     /**
321      * Interface defining the value of a tuple that is used in the join condition.
322      */
323     protected static interface Joinable {
324         /**
325          * Obtain the value that is to be used in the join condition.
326          * 
327          * @param leftValue the value from the left tuple; never null
328          * @param rightValue the value from the right tuple; never null
329          * @return true if the tuples are to be joined
330          */
331         boolean evaluate( Object leftValue,
332                           Object rightValue );
333     }
334 
335     /**
336      * Create a {@link ValueSelector} that obtains the value required to use the supplied join condition.
337      * 
338      * @param left the left source component; may not be null
339      * @param right the left source component; may not be null
340      * @param condition the join condition; may not be null
341      * @return the value selector; never null
342      */
343     protected static Joinable joinableFor( ProcessingComponent left,
344                                            ProcessingComponent right,
345                                            JoinCondition condition ) {
346         if (condition instanceof SameNodeJoinCondition) {
347             return new Joinable() {
348                 public boolean evaluate( Object locationA,
349                                          Object locationB ) {
350                     Location location1 = (Location)locationA;
351                     Location location2 = (Location)locationB;
352                     return location1.isSame(location2);
353                 }
354             };
355         } else if (condition instanceof EquiJoinCondition) {
356             return new Joinable() {
357                 public boolean evaluate( Object leftValue,
358                                          Object rightValue ) {
359                     return leftValue.equals(rightValue);
360                 }
361             };
362         } else if (condition instanceof ChildNodeJoinCondition) {
363             ChildNodeJoinCondition joinCondition = (ChildNodeJoinCondition)condition;
364             String childSelectorName = joinCondition.childSelectorName().name();
365             if (left.getColumns().hasSelector(childSelectorName)) {
366                 // The child is on the left ...
367                 return new Joinable() {
368                     public boolean evaluate( Object childLocation,
369                                              Object parentLocation ) {
370                         Path childPath = ((Location)childLocation).getPath();
371                         Path parentPath = ((Location)parentLocation).getPath();
372                         return childPath.getParent().isSameAs(parentPath);
373                     }
374                 };
375             }
376             // The child is on the right ...
377             return new Joinable() {
378                 public boolean evaluate( Object parentLocation,
379                                          Object childLocation ) {
380                     Path childPath = ((Location)childLocation).getPath();
381                     Path parentPath = ((Location)parentLocation).getPath();
382                     return childPath.getParent().isSameAs(parentPath);
383                 }
384             };
385         } else if (condition instanceof DescendantNodeJoinCondition) {
386             DescendantNodeJoinCondition joinCondition = (DescendantNodeJoinCondition)condition;
387             String ancestorSelectorName = joinCondition.ancestorSelectorName().name();
388             if (left.getColumns().hasSelector(ancestorSelectorName)) {
389                 // The ancestor is on the left ...
390                 return new Joinable() {
391                     public boolean evaluate( Object ancestorLocation,
392                                              Object descendantLocation ) {
393                         Path ancestorPath = ((Location)ancestorLocation).getPath();
394                         Path descendantPath = ((Location)descendantLocation).getPath();
395                         return ancestorPath.isAncestorOf(descendantPath);
396                     }
397                 };
398             }
399             // The ancestor is on the right ...
400             return new Joinable() {
401                 public boolean evaluate( Object descendantLocation,
402                                          Object ancestorLocation ) {
403                     Path ancestorPath = ((Location)ancestorLocation).getPath();
404                     Path descendantPath = ((Location)descendantLocation).getPath();
405                     return ancestorPath.isAncestorOf(descendantPath);
406                 }
407             };
408         }
409         throw new IllegalArgumentException();
410     }
411 
412     /**
413      * Create a {@link Comparable} that can be used to compare the values required to evaluate the supplied join condition.
414      * 
415      * @param context the context in which this query is being evaluated; may not be null
416      * @param left the left source component; may not be null
417      * @param right the left source component; may not be null
418      * @param condition the join condition; may not be null
419      * @return the comparator; never null
420      */
421     @SuppressWarnings( "unchecked" )
422     protected static Comparator<Object> comparatorFor( QueryContext context,
423                                                        ProcessingComponent left,
424                                                        ProcessingComponent right,
425                                                        JoinCondition condition ) {
426         final Comparator<Path> pathComparator = ValueComparators.PATH_COMPARATOR;
427         if (condition instanceof SameNodeJoinCondition) {
428             return new Comparator<Object>() {
429                 public int compare( Object location1,
430                                     Object location2 ) {
431                     Path path1 = ((Location)location1).getPath();
432                     Path path2 = ((Location)location2).getPath();
433                     return pathComparator.compare(path1, path2);
434                 }
435             };
436         }
437         if (condition instanceof ChildNodeJoinCondition) {
438             ChildNodeJoinCondition joinCondition = (ChildNodeJoinCondition)condition;
439             String childSelectorName = joinCondition.childSelectorName().name();
440             if (left.getColumns().hasSelector(childSelectorName)) {
441                 // The child is on the left ...
442                 return new Comparator<Object>() {
443                     public int compare( Object childLocation,
444                                         Object parentLocation ) {
445                         Path childPath = ((Location)childLocation).getPath();
446                         Path parentPath = ((Location)parentLocation).getPath();
447                         if (childPath.isRoot()) return parentPath.isRoot() ? 0 : -1;
448                         Path parentOfChild = childPath.getParent();
449                         return pathComparator.compare(parentPath, parentOfChild);
450                     }
451                 };
452             }
453             // The child is on the right ...
454             return new Comparator<Object>() {
455                 public int compare( Object parentLocation,
456                                     Object childLocation ) {
457                     Path childPath = ((Location)childLocation).getPath();
458                     Path parentPath = ((Location)parentLocation).getPath();
459                     if (childPath.isRoot()) return parentPath.isRoot() ? 0 : -1;
460                     Path parentOfChild = childPath.getParent();
461                     return pathComparator.compare(parentPath, parentOfChild);
462                 }
463             };
464         }
465         if (condition instanceof EquiJoinCondition) {
466             EquiJoinCondition joinCondition = (EquiJoinCondition)condition;
467             SelectorName leftSelectorName = joinCondition.selector1Name();
468             SelectorName rightSelectorName = joinCondition.selector2Name();
469             String leftPropertyName = joinCondition.property1Name();
470             String rightPropertyName = joinCondition.property2Name();
471 
472             Schemata schemata = context.getSchemata();
473             Schemata.Table leftTable = schemata.getTable(leftSelectorName);
474             Schemata.Column leftColumn = leftTable.getColumn(leftPropertyName);
475             String leftType = leftColumn.getPropertyType();
476 
477             Schemata.Table rightTable = schemata.getTable(rightSelectorName);
478             Schemata.Column rightColumn = rightTable.getColumn(rightPropertyName);
479             String rightType = rightColumn.getPropertyType();
480 
481             TypeSystem typeSystem = context.getTypeSystem();
482             if (leftType.equals(rightType)) {
483                 TypeFactory<?> typeFactory = typeSystem.getTypeFactory(leftType);
484                 if (typeFactory != null) {
485                     return (Comparator<Object>)typeFactory.getComparator();
486                 }
487             }
488             return typeSystem.getDefaultComparator();
489         }
490         throw new IllegalArgumentException();
491     }
492 }