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.Collections;
27  import java.util.Comparator;
28  import java.util.Iterator;
29  import java.util.LinkedList;
30  import java.util.List;
31  import java.util.Map;
32  import java.util.regex.Pattern;
33  import org.modeshape.graph.Location;
34  import org.modeshape.graph.query.QueryResults.Columns;
35  import org.modeshape.graph.query.model.And;
36  import org.modeshape.graph.query.model.BindVariableName;
37  import org.modeshape.graph.query.model.ChildNode;
38  import org.modeshape.graph.query.model.Comparison;
39  import org.modeshape.graph.query.model.Constraint;
40  import org.modeshape.graph.query.model.DescendantNode;
41  import org.modeshape.graph.query.model.FullTextSearch;
42  import org.modeshape.graph.query.model.Literal;
43  import org.modeshape.graph.query.model.Not;
44  import org.modeshape.graph.query.model.Operator;
45  import org.modeshape.graph.query.model.Or;
46  import org.modeshape.graph.query.model.PropertyExistence;
47  import org.modeshape.graph.query.model.SameNode;
48  import org.modeshape.graph.query.model.SetCriteria;
49  import org.modeshape.graph.query.model.StaticOperand;
50  import org.modeshape.graph.query.model.TypeSystem;
51  import org.modeshape.graph.query.model.TypeSystem.TypeFactory;
52  import org.modeshape.graph.query.validate.Schemata;
53  
54  /**
55   */
56  public class SelectComponent extends DelegatingComponent {
57  
58      private final Constraint constraint;
59      private final ConstraintChecker checker;
60      private final Map<String, Object> variables;
61  
62      /**
63       * Create a SELECT processing component that pass those tuples that satisfy the supplied constraint. Certain constraints
64       * (including {@link FullTextSearch}, {@link SameNode} and {@link PropertyExistence}) are evaluated in a fairly limited
65       * fashion, essentially operating upon the tuple values themselves.
66       * <p>
67       * For example, the {@link SameNode} constraint is satisfied when the selected node has the same path as the constraint's
68       * {@link SameNode#path() path}. And the {@link PropertyExistence} constraint is satisfied when the
69       * {@link PropertyExistence#propertyName() property} is represented in the tuple with a non-null value. Similarly,
70       * {@link FullTextSearch} always evaluates to true. Obviously these implementations will likely not be sufficient for many
71       * purposes. But in cases where these particular constraints are handled in other ways (and thus not expected to be seen by
72       * this processor), this form may be sufficient.
73       * </p>
74       * <p>
75       * For more control over the behavior, use the constructor that takes an {@link Analyzer} implementation (see
76       * {@link #SelectComponent(ProcessingComponent, Constraint, Map, Analyzer)}).
77       * </p>
78       * 
79       * @param delegate the delegate processing component that this component should use to obtain the input tuples; may not be
80       *        null
81       * @param constraint the query constraint; may not be null
82       * @param variables the map of variables keyed by their name (as used in {@link BindVariableName} constraints); may be null
83       */
84      public SelectComponent( ProcessingComponent delegate,
85                              Constraint constraint,
86                              Map<String, Object> variables ) {
87          this(delegate, constraint, variables, null);
88      }
89  
90      /**
91       * Create a SELECT processing component that pass those tuples that satisfy the supplied constraint, using the supplied
92       * {@link Analyzer} for the verification of the more complex/arduous constraints.
93       * 
94       * @param delegate the delegate processing component that this component should use to obtain the input tuples; may not be
95       *        null
96       * @param constraint the query constraint; may not be null
97       * @param variables the map of variables keyed by their name (as used in {@link BindVariableName} constraints); may be null
98       * @param analyzer the analyzer; may be null
99       */
100     public SelectComponent( ProcessingComponent delegate,
101                             Constraint constraint,
102                             Map<String, Object> variables,
103                             Analyzer analyzer ) {
104         super(delegate);
105         this.constraint = constraint;
106         this.variables = variables != null ? variables : Collections.<String, Object>emptyMap();
107         TypeSystem types = delegate.getContext().getTypeSystem();
108         Schemata schemata = delegate.getContext().getSchemata();
109         this.checker = createChecker(types, schemata, delegate.getColumns(), this.constraint, this.variables, analyzer);
110     }
111 
112     /**
113      * {@inheritDoc}
114      * 
115      * @see org.modeshape.graph.query.process.ProcessingComponent#execute()
116      */
117     @Override
118     public List<Object[]> execute() {
119         List<Object[]> tuples = delegate().execute();
120         if (!tuples.isEmpty()) {
121             // Iterate through the tuples, removing any that do not satisfy the constraint ...
122             Iterator<Object[]> iter = tuples.iterator();
123             while (iter.hasNext()) {
124                 if (!checker.satisfiesConstraints(iter.next())) {
125                     iter.remove();
126                 }
127             }
128         }
129         return tuples;
130     }
131 
132     /**
133      * Interface used to determine whether a tuple satisfies all of the constraints applied to the SELECT node.
134      */
135     public static interface ConstraintChecker {
136         /**
137          * Return true if the tuple satisfies all of the constraints.
138          * 
139          * @param tuple the tuple; never null
140          * @return true if the tuple satisifes the constraints, or false otherwise
141          */
142         boolean satisfiesConstraints( Object[] tuple );
143     }
144 
145     /**
146      * Inteface for criteria evaluation operations that cannot be defined efficiently, correctly, or completely using only the
147      * tuple values.
148      * 
149      * @see SelectComponent#SelectComponent(ProcessingComponent, Constraint, Map, Analyzer)
150      */
151     public static interface Analyzer {
152 
153         int length( Object value );
154 
155         /**
156          * Determine whether the node specified by the location is the same node as that supplied by the path. This determines if
157          * the nodes at the supplied location and path are the same node.
158          * 
159          * @param location the location of the node; never null
160          * @param accessibleAtPath the path that the node can be accessed via
161          * @return true if the node given by the {@link Location} is also accessible at the supplied path, or false otherwise
162          */
163         boolean isSameNode( Location location,
164                             String accessibleAtPath );
165 
166         /**
167          * Determine whether the node specified by the location is a descendant of that supplied by the path.
168          * 
169          * @param location the location of the node; never null
170          * @param ancestorPath the path of the ancestor node
171          * @return true if the node given by the {@link Location} is also accessible at the supplied path, or false otherwise
172          */
173         boolean isDescendantOf( Location location,
174                                 String ancestorPath );
175 
176         /**
177          * Determine whether the node at the supplied location has the named property.
178          * 
179          * @param location the location of the node; never null
180          * @param propertyName the name of the property
181          * @return true if the node at the supplied {@link Location} does contain the property, or false if it does not
182          */
183         boolean hasProperty( Location location,
184                              String propertyName );
185 
186         /**
187          * Determine whether the node at the supplied location satisfies the supplied full-text query.
188          * 
189          * @param location the location of the node; never null
190          * @param fullTextQuery the full-text search expression; never null
191          * @return the full-text search score of the node, or 0.0d if the node does not satisfy the full-text query
192          */
193         double hasFullText( Location location,
194                             String fullTextQuery );
195 
196         /**
197          * Determine whether the named property of the node at the supplied location satisfies the supplied full-text query.
198          * 
199          * @param location the location of the node; never null
200          * @param propertyName the name of the property; never null
201          * @param fullTextQuery the full-text search expression; never null
202          * @return the full-text search score of the node, or 0.0d if the node does not satisfy the full-text query
203          */
204         double hasFullText( Location location,
205                             String propertyName,
206                             String fullTextQuery );
207     }
208 
209     /**
210      * Interface defining the {@link Comparison} functionality for a specific {@link Operator}.
211      */
212     protected static interface CompareOperation {
213         /**
214          * Perform the comparison operation.
215          * 
216          * @param tupleValue the value in the tuple
217          * @param criteriaValue the right-hand-side of the comparison
218          * @return true if the comparison criteria is satisfied, or false otherwise
219          */
220         boolean evaluate( Object tupleValue,
221                           Object criteriaValue );
222     }
223 
224     /**
225      * Create the constraint evaluator that is used by the {@link SelectComponent} to evaluate the supplied {@link Constraint
226      * criteria}. For the most correct behavior, specify an {@link Analyzer} implementation.
227      * 
228      * @param types the type system; may not be null
229      * @param schemata the schemata; may not be null
230      * @param columns the definition of the result columns and the tuples; may not be null
231      * @param constraint the criteria that this {@link SelectComponent} is to evaluate
232      * @param variables the variables that are to be substituted for the various {@link BindVariableName} {@link StaticOperand
233      *        operands}; may not be null
234      * @param analyzer the analyzer that should be used to evalulate the operations that cannot be defined efficiently, correctly,
235      *        or completely using only the tuple values; may be null if the tuple values should be used to perform the evaluation
236      *        in perhaps an non-ideal manner
237      * @return the constraint evaluator; never null
238      */
239     protected ConstraintChecker createChecker( final TypeSystem types,
240                                                Schemata schemata,
241                                                Columns columns,
242                                                Constraint constraint,
243                                                Map<String, Object> variables,
244                                                final Analyzer analyzer ) {
245         if (constraint instanceof Or) {
246             Or orConstraint = (Or)constraint;
247             final ConstraintChecker left = createChecker(types, schemata, columns, orConstraint.left(), variables, analyzer);
248             final ConstraintChecker right = createChecker(types, schemata, columns, orConstraint.right(), variables, analyzer);
249             return new ConstraintChecker() {
250                 public boolean satisfiesConstraints( Object[] tuple ) {
251                     return left.satisfiesConstraints(tuple) || right.satisfiesConstraints(tuple);
252                 }
253             };
254         }
255         if (constraint instanceof Not) {
256             Not notConstraint = (Not)constraint;
257             final ConstraintChecker original = createChecker(types,
258                                                              schemata,
259                                                              columns,
260                                                              notConstraint.constraint(),
261                                                              variables,
262                                                              analyzer);
263             return new ConstraintChecker() {
264                 public boolean satisfiesConstraints( Object[] tuple ) {
265                     return !original.satisfiesConstraints(tuple);
266                 }
267             };
268         }
269         if (constraint instanceof And) {
270             And andConstraint = (And)constraint;
271             final ConstraintChecker left = createChecker(types, schemata, columns, andConstraint.left(), variables, analyzer);
272             final ConstraintChecker right = createChecker(types, schemata, columns, andConstraint.right(), variables, analyzer);
273             return new ConstraintChecker() {
274                 public boolean satisfiesConstraints( Object[] tuple ) {
275                     return left.satisfiesConstraints(tuple) && right.satisfiesConstraints(tuple);
276                 }
277             };
278         }
279         if (constraint instanceof ChildNode) {
280             ChildNode childConstraint = (ChildNode)constraint;
281             final int locationIndex = columns.getLocationIndex(childConstraint.selectorName().name());
282             final String parentPath = childConstraint.parentPath();
283             return new ConstraintChecker() {
284                 public boolean satisfiesConstraints( Object[] tuple ) {
285                     Location location = (Location)tuple[locationIndex];
286                     assert location.hasPath();
287                     return location.getPath().getParent().equals(parentPath);
288                 }
289             };
290         }
291         if (constraint instanceof DescendantNode) {
292             DescendantNode descendantNode = (DescendantNode)constraint;
293             final int locationIndex = columns.getLocationIndex(descendantNode.selectorName().name());
294             final String ancestorPath = descendantNode.ancestorPath();
295             return new ConstraintChecker() {
296                 public boolean satisfiesConstraints( Object[] tuple ) {
297                     Location location = (Location)tuple[locationIndex];
298                     assert location.hasPath();
299                     return analyzer.isDescendantOf(location, ancestorPath);
300                 }
301             };
302         }
303         if (constraint instanceof SameNode) {
304             SameNode sameNode = (SameNode)constraint;
305             final int locationIndex = columns.getLocationIndex(sameNode.selectorName().name());
306             final String path = sameNode.path();
307             if (analyzer != null) {
308                 return new ConstraintChecker() {
309                     public boolean satisfiesConstraints( Object[] tuple ) {
310                         Location location = (Location)tuple[locationIndex];
311                         return analyzer.isSameNode(location, path);
312                     }
313                 };
314             }
315             return new ConstraintChecker() {
316                 public boolean satisfiesConstraints( Object[] tuple ) {
317                     Location location = (Location)tuple[locationIndex];
318                     assert location.hasPath();
319                     return location.toString().equals(path);
320                 }
321             };
322         }
323         if (constraint instanceof PropertyExistence) {
324             PropertyExistence propertyExistance = (PropertyExistence)constraint;
325             String selectorName = propertyExistance.selectorName().name();
326             final String propertyName = propertyExistance.propertyName();
327             if (analyzer != null) {
328                 final int locationIndex = columns.getLocationIndex(selectorName);
329                 return new ConstraintChecker() {
330                     public boolean satisfiesConstraints( Object[] tuple ) {
331                         Location location = (Location)tuple[locationIndex];
332                         return analyzer.hasProperty(location, propertyName);
333                     }
334                 };
335             }
336             final int columnIndex = columns.getColumnIndexForProperty(selectorName, propertyName);
337             return new ConstraintChecker() {
338                 public boolean satisfiesConstraints( Object[] tuple ) {
339                     return tuple[columnIndex] != null;
340                 }
341             };
342         }
343         if (constraint instanceof FullTextSearch) {
344             if (analyzer != null) {
345                 FullTextSearch search = (FullTextSearch)constraint;
346                 String selectorName = search.selectorName().name();
347                 final int locationIndex = columns.getLocationIndex(selectorName);
348                 final String expression = search.fullTextSearchExpression();
349                 if (expression == null) {
350                     return new ConstraintChecker() {
351                         public boolean satisfiesConstraints( Object[] tuple ) {
352                             return false;
353                         }
354                     };
355                 }
356                 final String propertyName = search.propertyName(); // may be null
357                 final int scoreIndex = columns.getFullTextSearchScoreIndexFor(selectorName);
358                 assert scoreIndex >= 0 : "Columns do not have room for the search scores";
359                 if (propertyName != null) {
360                     return new ConstraintChecker() {
361                         public boolean satisfiesConstraints( Object[] tuple ) {
362                             Location location = (Location)tuple[locationIndex];
363                             if (location == null) return false;
364                             double score = analyzer.hasFullText(location, propertyName, expression);
365                             // put the score on the correct tuple value ...
366                             Double existing = (Double)tuple[scoreIndex];
367                             if (existing != null) {
368                                 score = Math.max(existing.doubleValue(), score);
369                             }
370                             tuple[scoreIndex] = new Double(score);
371                             return true;
372                         }
373                     };
374                 }
375                 return new ConstraintChecker() {
376                     public boolean satisfiesConstraints( Object[] tuple ) {
377                         Location location = (Location)tuple[locationIndex];
378                         if (location == null) return false;
379                         double score = analyzer.hasFullText(location, expression);
380                         // put the score on the correct tuple value ...
381                         Double existing = (Double)tuple[scoreIndex];
382                         if (existing != null) {
383                             score = Math.max(existing.doubleValue(), score);
384                         }
385                         tuple[scoreIndex] = new Double(score);
386                         return true;
387                     }
388                 };
389             }
390             return new ConstraintChecker() {
391                 public boolean satisfiesConstraints( Object[] tuple ) {
392                     return true;
393                 }
394             };
395         }
396         if (constraint instanceof Comparison) {
397             Comparison comparison = (Comparison)constraint;
398 
399             // Create the correct dynamic operation ...
400             DynamicOperation dynamicOperation = createDynamicOperation(types, schemata, columns, comparison.operand1());
401             Operator operator = comparison.operator();
402             StaticOperand staticOperand = comparison.operand2();
403             return createChecker(types, schemata, columns, dynamicOperation, operator, staticOperand);
404         }
405         if (constraint instanceof SetCriteria) {
406             SetCriteria setCriteria = (SetCriteria)constraint;
407             DynamicOperation dynamicOperation = createDynamicOperation(types, schemata, columns, setCriteria.leftOperand());
408             Operator operator = Operator.EQUAL_TO;
409             final List<ConstraintChecker> checkers = new LinkedList<ConstraintChecker>();
410             for (StaticOperand setValue : setCriteria.rightOperands()) {
411                 ConstraintChecker rightChecker = createChecker(types, schemata, columns, dynamicOperation, operator, setValue);
412                 assert rightChecker != null;
413                 checkers.add(rightChecker);
414             }
415             if (checkers.isEmpty()) {
416                 // Nothing will satisfy these constraints ...
417                 return new ConstraintChecker() {
418                     public boolean satisfiesConstraints( Object[] tuple ) {
419                         return false;
420                     }
421                 };
422             }
423             return new ConstraintChecker() {
424                 public boolean satisfiesConstraints( Object[] tuple ) {
425                     for (ConstraintChecker checker : checkers) {
426                         if (checker.satisfiesConstraints(tuple)) return true;
427                     }
428                     return false;
429                 }
430             };
431         }
432         assert false;
433         return null;
434     }
435 
436     @SuppressWarnings( "unchecked" )
437     protected ConstraintChecker createChecker( final TypeSystem types,
438                                                Schemata schemata,
439                                                Columns columns,
440                                                final DynamicOperation dynamicOperation,
441                                                Operator operator,
442                                                StaticOperand staticOperand ) {
443         final String expectedType = dynamicOperation.getExpectedType();
444 
445         // Determine the literal value ...
446         Object literalValue = null;
447         if (staticOperand instanceof BindVariableName) {
448             BindVariableName bindVariable = (BindVariableName)staticOperand;
449             String variableName = bindVariable.variableName();
450             literalValue = variables.get(variableName); // may be null
451         } else {
452             Literal literal = (Literal)staticOperand;
453             literalValue = literal.value();
454         }
455         // Create the correct comparator ...
456         final TypeFactory<?> typeFactory = types.getTypeFactory(expectedType);
457         assert typeFactory != null;
458         final Comparator<Object> comparator = (Comparator<Object>)typeFactory.getComparator();
459         assert comparator != null;
460         // Create the correct operation ...
461         final TypeFactory<?> literalFactory = types.getTypeFactory(expectedType);
462         final Object rhs = literalFactory.create(literalValue);
463         switch (operator) {
464             case EQUAL_TO:
465                 return new ConstraintChecker() {
466                     public boolean satisfiesConstraints( Object[] tuples ) {
467                         return comparator.compare(dynamicOperation.evaluate(tuples), rhs) == 0;
468                     }
469                 };
470             case GREATER_THAN:
471                 return new ConstraintChecker() {
472                     public boolean satisfiesConstraints( Object[] tuples ) {
473                         return comparator.compare(dynamicOperation.evaluate(tuples), rhs) > 0;
474                     }
475                 };
476             case GREATER_THAN_OR_EQUAL_TO:
477                 return new ConstraintChecker() {
478                     public boolean satisfiesConstraints( Object[] tuples ) {
479                         return comparator.compare(dynamicOperation.evaluate(tuples), rhs) >= 0;
480                     }
481                 };
482             case LESS_THAN:
483                 return new ConstraintChecker() {
484                     public boolean satisfiesConstraints( Object[] tuples ) {
485                         return comparator.compare(dynamicOperation.evaluate(tuples), rhs) < 0;
486                     }
487                 };
488             case LESS_THAN_OR_EQUAL_TO:
489                 return new ConstraintChecker() {
490                     public boolean satisfiesConstraints( Object[] tuples ) {
491                         return comparator.compare(dynamicOperation.evaluate(tuples), rhs) <= 0;
492                     }
493                 };
494             case NOT_EQUAL_TO:
495                 return new ConstraintChecker() {
496                     public boolean satisfiesConstraints( Object[] tuples ) {
497                         return comparator.compare(dynamicOperation.evaluate(tuples), rhs) != 0;
498                     }
499                 };
500             case LIKE:
501                 // Convert the LIKE expression to a regular expression
502                 final Pattern pattern = createRegexFromLikeExpression(types.asString(rhs));
503                 return new ConstraintChecker() {
504                     public boolean satisfiesConstraints( Object[] tuples ) {
505                         Object tupleValue = dynamicOperation.evaluate(tuples);
506                         if (tupleValue == null) return false;
507                         String value = types.asString(tupleValue);
508                         return pattern.matcher(value).matches();
509                     }
510                 };
511         }
512         assert false;
513         return null;
514     }
515 
516     protected static Pattern createRegexFromLikeExpression( String likeExpression ) {
517         return null;
518     }
519 }