!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: queryexecuter.gs,v 1.13 2008-01-09 22:50:13 stever Exp $
!
! Superclass Hierarchy:
!   QueryExecuter, Array, SequenceableCollection, Collection, Object.
!
!=========================================================================

! class created in idxclasses.topaz

removeallmethods QueryExecuter
removeallclassmethods QueryExecuter

category: 'For Documentation Installation only'
classmethod: QueryExecuter
installDocumentation

| doc txt |
doc := GsClassDocumentation _newForPrivateGsClass: self.

txt := (GsDocText new) details:
''.

doc documentClassWith: txt.

self description: doc.
%

! ------------------- Class methods for QueryExecuter
category: 'Instance Creation'
classmethod: QueryExecuter
on: anNsc

"Create a query executer on the given NSC."

^ super new nsc: anNsc
%

category: 'Testing'
classmethod: QueryExecuter
nilOrderDefinedFor: aClass

"Return whether we have defined that nils have a predetermined order
 when comparing against instances of aClass (that is, we have defined that
 nils are less than any instance of aClass)."

" if it is a basic class (String, Number, etc) "
^ ( RangeEqualityIndex isBasicClass: aClass ) _or:
    " or if the path is unconstrained "
    [ aClass == Object _or:
    [ aClass == nil ] ]
%

! ------------------- Instance methods for QueryExecuter
category: 'Query Detect'
method: QueryExecuter
_boundQueryDetect: anArray

"Argument anArray is a four element Array of Arrays describing a SelectBlock
 in the manner needed to process a query on the receiver:

   1.  Array of the bound variables from the predicate
   2.  Array of the predicate's terms
   3.  Array of the predicate's paths
   4.  Array of Strings of the path names used in the predicate"

| ordering oSize offset tmpStream streamOffset minElements minStream numElements |
" get a description of the operations to invoke on indexes "
self _buildIndexOperationsList: anArray.

self optimize.

" get the order to invoke the operations "
ordering := self _getOperationsOrder.
ordering isEmpty
    ifTrue: [ ^ #_incompletePathTraversal ].

oSize := ordering size.

" if only one predicate, do the detect right away "
oSize == 1
    ifTrue: [ ^ self _executeDetectionAt: (ordering at: 1) ].

minElements := nsc size.
" for each predicate ... "
1 to: oSize do: [ :i |
    offset := ordering at: i.

    " if constant-constant predicate, check to see if it is true "
    (self isConstantConstantAt: offset)
        ifTrue: [
            (self _executeConstantConstantPredicateAt: offset)
                ifFalse: [ ^ #_incompletePathTraversal ]
        ].

    " if the predicate is path-constant with an index present ... "
    ( (self isPathConstantAt: offset) _and:
    [ (self firstOperandAt: offset) isPathEvaluator not _and:
    " cannot get stream if operator is ==, ~=, ~~, or unary "
    [ ( #( 3 6 7 8 ) includesIdentical: (self operatorAt: offset) ) not ] ] )
        ifTrue: [
            " quickly see if any will satisfy the predicate "
            tmpStream := self _executePathConstantStreamSelectionAt: offset.
            tmpStream atEnd
                ifTrue: [ ^ #_incompletePathTraversal ].

            " keep the stream with the minimum number of elements "
            (numElements := tmpStream approxNumElements) < minElements
                ifTrue: [
                    minElements := numElements.
                    minStream := tmpStream.
                    streamOffset := i.
                ]
        ].
].

" if got a stream, only query over its contents "
minStream ~~ nil
    ifTrue: [
        " self nsc: minStream copy makeNsc. "
        " nil out this entry in the operations order "
        ordering at: streamOffset put: nil.
    ].

^ self findFirstThatSatisfiesPredicatesStartingAt: 1
    ordering: ordering
    stream: minStream
%

category: 'Query Reject'
method: QueryExecuter
_boundQueryReject: anArray

"Argument anArray is a four element Array of Arrays describing a SelectBlock
 in the manner needed to process a query on the receiver:

   1.  Array of the bound variables from the predicate
   2.  Array of the predicate's terms
   3.  Array of the predicate's paths
   4.  Array of Strings of the path names used in the predicate"

| origNsc result tmpResult |
origNsc := nsc.
result := origNsc _asIdentityBag -
  (self _boundQuerySelect: anArray) _asIdentityBag.
result _class == origNsc speciesForSelect
  ifFalse: [
    tmpResult := origNsc speciesForSelect new.
    tmpResult addAll: result.
    result := tmpResult
  ].
^ result
%

category: 'Query Select'
method: QueryExecuter
_boundQuerySelect: anArray

"Argument anArray is a four element Array of Arrays describing a SelectBlock
 in the manner needed to process a query on the receiver:

   1.  Array of the bound variables from the predicate
   2.  Array of the predicate's terms
   3.  Array of the predicate's paths
   4.  Array of Strings of the path names used in the predicate"

| ordering partialSet resultSet origNsc offset |
origNsc := nsc.

" get a description of the operations to invoke on indexes "
self _buildIndexOperationsList: anArray.

self optimize.

" get the order to invoke the operations "
ordering := self _getOperationsOrder.
ordering isEmpty
    ifTrue: [ ^ origNsc speciesForSelect new ].

" get a first result "
resultSet := self _executeSelectionAt: (ordering at: 1).
resultSet isEmpty
    ifTrue: [ ^ resultSet ].

nsc := resultSet.

" execute remaining predicates "
2 to: ordering size do: [ :i |

    resultSet size < self bruteThreshold
      ifTrue: [
        resultSet := self findAllThatSatisfyPredicatesStartingAt: i ordering: ordering.
        resultSet _class = origNsc speciesForSelect
          ifFalse:
          [ | tmpResult |
            tmpResult := origNsc speciesForSelect new.
            tmpResult addAll: resultSet.
            resultSet := tmpResult].
        ^resultSet
      ].

    offset := ordering at: i.

    " if the next predicate will be done by brute force,
      use the result set rather than the entire NSC "

    " if it is path-constant or path-path "
    (self isConstantConstantAt: offset)
        ifFalse: [
            " if first operand is not an index "
            (self firstOperandAt: offset) isPathEvaluator
                ifTrue: [ (self firstOperandAt: offset) nsc: resultSet ].

            " if it is path-path and second operand is not an index "
            ( (self isPathPathAt: offset) _and:
            [ (self secondOperandAt: offset) isPathEvaluator ] )
                ifTrue: [ (self secondOperandAt: offset) nsc: resultSet ]
        ].

    partialSet := self _executeSelectionAt: offset.

    " if any intermediate result is empty, exit immediately "
    partialSet isEmpty
        ifTrue: [ ^ partialSet ]
        " otherwise, perform a set intersection "
        ifFalse: [ resultSet := resultSet _asIdentityBag * partialSet _asIdentityBag ].

    nsc := resultSet
].

resultSet _class = origNsc speciesForSelect
    ifFalse:
        [ | tmpResult |
        tmpResult := origNsc speciesForSelect new.
        tmpResult addAll: resultSet.
        resultSet := tmpResult].
                                                                                                   
resultSet == origNsc
    ifTrue: [ ^ resultSet copy ].
                                                                                                   
^ resultSet
%

category: 'Setup'
method: QueryExecuter
_buildPathEvaluatorForPredicateLinks: linksArray
withPaths: pathsArray
startingAt: offset

"Returns a path evaluator (an Array of path names) that match the path names
 described by the linksArray and pathsArray arguments (produced as the result
 of binding a select block)."

|  nextLink pathEvaluator i linkSize |
pathEvaluator := PathEvaluator basicNew.

offset == 0
    ifTrue: [
        pathEvaluator add:  #'' .
        ^ pathEvaluator
    ].

i := offset * 2 - 1.
linkSize := linksArray size.

[ i < linkSize ] whileTrue: [

    nextLink == 0 ifTrue: [ ^ pathEvaluator ].

    nextLink := linksArray at: i.
    pathEvaluator add: (pathsArray at: (linksArray at: i + 1)).

    i := nextLink * 2 - 1.

].
^ pathEvaluator
%

category: 'Setup'
method: QueryExecuter
_determinePredicateType: termsArray startingAt: offset

"Returns an integer indicating the predicate type of the predicate whose entry
 begins at the given offset.  Predicates are classified into four types:

 1.  constant-constant (such as 3 > 2)
 2.  path-constant     (such as 'spouse.age' > 30)
 3.  constant-path     (such as 30 <= 'spouse.age')
 4.  path-path         (such as 'spouse.age' < 'spouse.weight')"

(termsArray at: offset + 4)
    ifTrue: [
        (termsArray at: offset + 1)
            ifTrue: [ " its path-path " ^ 4  ]
            ifFalse: [ " its path-constant " ^ 2 ].
    ]
    ifFalse: [
        (termsArray at: offset + 1)
            ifTrue: [ " its constant-path " ^ 3 ]
            ifFalse: [ " its constant-constant " ^ 1 ]
    ]
%

category: 'Query Support'
method: QueryExecuter
_executeConstantConstantPredicateAt: offset

"Executes the constant-constant type predicate operation that is described at
 the given offset and returns a Boolean."

| searchOp |
searchOp := (self operatorAt: offset) + 1.

" if it is a unary operation "
searchOp == 9
    ifTrue: [ ^ self firstOperandAt: offset ].

^ (self firstOperandAt: offset)
    perform: (self operationSelectors at: searchOp)
    with: (self secondOperandAt: offset)
%

category: 'Query Detect'
method: QueryExecuter
_executeConstantConstantDetectionAt: offset

"Executes the constant-constant type predicate operation that is described at
 the given offset.  If the predicate evaluates to true, returns the first
 object in the 'nsc' instance variable."

( (self _executeConstantConstantPredicateAt: offset) _and: [ nsc isEmpty not ] )
    ifTrue: [ ^ nsc _asIdentityBag _at: 1 ]
    ifFalse: [ ^ #_incompletePathTraversal ]
%

category: 'Query Select'
method: QueryExecuter
_executeConstantConstantSelectionAt: offset

"Executes the constant-constant type predicate operation that is described at
 the given offset.  Returns a NSC that is the result of the query."

(self _executeConstantConstantPredicateAt: offset)
    ifTrue: [ ^ nsc ]
    ifFalse: [ ^ nsc speciesForSelect new ]
%

category: 'Query Detect'
method: QueryExecuter
_executeDetectionAt: offset

"Executes the predicate operation that is described at the given offset.
 Returns the first object in the 'nsc' instance variable that satisfies the
 predicate.  If none is detected, returns the result of evaluating the zero
 argument block."

| predicateType |
predicateType := self at: offset.

" if it is path-constant (constant-paths are transformed to this) "
predicateType == 2
    ifTrue: [ ^ self _executePathConstantDetectionAt: offset ].

" if it is constant-constant "
predicateType == 1
    ifTrue: [ ^ self _executeConstantConstantDetectionAt: offset ].

" if it is path-path "
predicateType == 4
    ifTrue: [ ^ self _executePathPathDetectionAt: offset ].
self _error: #assocErrBadComparison
%

category: 'Query Detect'
method: QueryExecuter
_executePathConstantDetectionAt: offset

"Executes the path-constant type predicate operation that is described at the
 given offset.  Returns the first object in the 'nsc' instance variable that
 satisfies the predicate."

| indexObj evalObj searchOp searchVal constraint |
indexObj := self firstOperandAt: offset.
searchOp := self operatorAt: offset.
searchVal := self secondOperandAt: offset.
evalObj := indexObj asQueryEvaluator.

self _check: indexObj compare: searchOp value: searchVal.

" if it is < or < = "
(searchOp == 0 _or: [ searchOp == 4 ] )
    ifTrue: [
        ^ evalObj
            findFirstValueLessThanKey: searchVal
            andEquals: (searchOp == 4)
    ].
" if it is > or >= "
(searchOp == 1 _or: [ searchOp == 5 ] )
    ifTrue: [
        ^ evalObj
            findFirstValueGreaterThanKey: searchVal
            andEquals: (searchOp == 5)
    ].
" if it is = "
searchOp == 2
    ifTrue: [ ^ evalObj findFirstValueEqualTo: searchVal ].
" if it is ~= "
searchOp == 6
    ifTrue: [ ^ evalObj findFirstValueNotEqualTo: searchVal ].
" if it is == "
searchOp == 3
    ifTrue: [ ^ evalObj findFirstValueIdenticalTo: searchVal ].
" if it is ~~ "
searchOp == 7
    ifTrue: [ ^ evalObj findFirstValueNotIdenticalTo: searchVal ].
" if it is unary "
searchOp == 8
    ifTrue: [
        constraint := indexObj nscRoot
            getLastElementConstraintOnPath: indexObj pathComponentsString.
        ( constraint ~~ nil _and: [ constraint ~~ Boolean ] )
            ifTrue: [ self _error: #rtErrLastConstraintNotBoolean ].
        ^ evalObj findFirstValueIdenticalTo: searchVal
    ].
" if it is a dual predicate "
searchOp == 9
    ifTrue: [
      ^ evalObj  findFirstValueGreaterThan: (searchVal at: 2)
          andEquals: ((searchVal at: 1) == 5)
          andLessThan: (searchVal at: 4)
          andEquals: ((searchVal at: 3) == 4)
    ].

self _error: #assocErrBadComparison
%

category: 'Query Select'
method: QueryExecuter
_executePathConstantSelectionAt: offset

"Executes the path-constant type predicate operation that is described at the
 given offset.  Returns a set that is the result of the query."

| indexObj evalObj searchOp searchVal constraint |
indexObj := self firstOperandAt: offset.
searchOp := self operatorAt: offset.
searchVal := self secondOperandAt: offset.
evalObj := indexObj asQueryEvaluator.

self _check: indexObj compare: searchOp value: searchVal.

" if it is < or < = "
(searchOp == 0 _or: [ searchOp == 4 ] )
    ifTrue: [
        ^ evalObj findAllValuesLessThanKey: searchVal andEquals: (searchOp == 4)
    ].
" if it is > or >= "
(searchOp == 1 _or: [ searchOp == 5 ] )
    ifTrue: [
        ^ evalObj findAllValuesGreaterThanKey: searchVal andEquals: (searchOp == 5)
    ].
" if it is ="
searchOp == 2
    ifTrue: [ ^ evalObj findAllValuesEqualTo: searchVal ].
" if it is ~="
searchOp == 6
    ifTrue: [ ^ evalObj findAllValuesNotEqualTo: searchVal ].
" if it is =="
searchOp == 3
    ifTrue: [ ^ evalObj findAllValuesIdenticalTo: searchVal ].
" if it is ~~"
searchOp == 7
    ifTrue: [ ^ evalObj findAllValuesNotIdenticalTo: searchVal ].
" if it is unary "
searchOp == 8
    ifTrue: [
        constraint := indexObj nscRoot
            getLastElementConstraintOnPath: indexObj pathComponentsString.
        ( constraint ~~ nil _and: [ constraint ~~ Boolean ] )
            ifTrue: [ self _error: #rtErrLastConstraintNotBoolean ].
        ^ evalObj findAllValuesIdenticalTo: searchVal
    ].
" if it is a dual predicate "
searchOp == 9
    ifTrue: [
      ^ evalObj  findAllValuesGreaterThan: (searchVal at: 2)
          andEquals: ((searchVal at: 1) == 5)
          andLessThan: (searchVal at: 4)
          andEquals: ((searchVal at: 3) == 4)
    ].

self _error: #assocErrBadComparison
%

category: 'Query Detect'
method: QueryExecuter
_executePathPathDetectionAt: offset

"Executes the path-path type predicate operation that is described at the given
 offset.  Returns the first object for which the predicate evaluates to true."

| index1 searchOp index2 operator val1 incomplete
val2 obj bag |
index1 := self firstOperandAt: offset.
searchOp := self operatorAt: offset.
index2 := self secondOperandAt: offset.

self _check: index1 compare: searchOp value: index2.

operator := self _operationSelectors at: searchOp + 1.

incomplete := #_incompletePathTraversal.

bag := nsc _asIdentityBag.
index1 isIndexOnRootNsc
    ifTrue: [ " query of the form { :o | o = o.a.b.c } "
       | ivOffsetCache |
       ivOffsetCache := index2 _createIvOffsetCache.
       1 to: bag size do: [ :i |
            (obj := bag _at: i) ~~ nil
                ifTrue: [
                    val2 := index2 _traverseObject: obj cache: ivOffsetCache.
                    ( val2 ~~ incomplete _and:
                    [ obj perform: operator with: val2 ] )
                        ifTrue: [ ^obj ]
                ]
       ]
    ]
    ifFalse: [
        index2 isIndexOnRootNsc
            ifTrue: [ " query of the form { :o | o.a.b.c = o } "
               | ivOffsetCache |
               ivOffsetCache := index1 _createIvOffsetCache.
               1 to: bag size do: [ :i |
                    (obj := bag _at: i) ~~ nil
                        ifTrue: [
                            val1 := index1 _traverseObject: obj cache: ivOffsetCache.
                            ( val1 ~~ incomplete _and:
                            [ val1 perform: operator with: obj ] )
                                ifTrue: [ ^obj ]
                        ]
               ]
            ]
            ifFalse: [ " query of the form { :o | o.a.b.c = o.d.e.f } "
               | ivOffsetCache1 ivOffsetCache2 |
               ivOffsetCache1 := index1 _createIvOffsetCache.
                ivOffsetCache2 := index2 _createIvOffsetCache.
               1 to: bag size do: [ :i |
                    (obj := bag _at: i) ~~ nil
                        ifTrue: [
                            (val1 := index1 _traverseObject: obj cache: ivOffsetCache1) ~~ incomplete
                                ifTrue: [
                                    ( (val2 := index2 _traverseObject: obj cache: ivOffsetCache2) ~~ incomplete _and:
                                    [ val1 perform: operator with: val2 ] )
                                        ifTrue: [ ^obj ]
                                ]
                        ]
               ]
            ]
    ].

^ incomplete
%

category: 'Query Select'
method: QueryExecuter
_executePathPathSelectionAt: offset

"Executes the path-path type predicate operation that is described at the given
 offset.  Returns a set that is the result of the query."

| index1 searchOp index2 index1isSetValued index2isSetValued |
index1 := self firstOperandAt: offset.
searchOp := self operatorAt: offset.
index2 := self secondOperandAt: offset.

self _check: index1 compare: searchOp value: index2.

index1isSetValued := false.
index2isSetValued := false.

( index1isSetValued not _and: [ index2isSetValued not ] )
    ifTrue: [ ^ self _executePathPathNoSetValuedSelectionAt: offset].

self _error: #assocErrBadComparison
%

category: 'Query Select'
method: QueryExecuter
_executeSelectionAt: offset

"Executes the predicate operation that is described at the given offset.
 Returns a set that is the result of the query."

| predicateType |
predicateType := self at: offset.

" if it is path-constant (constant-paths are transformed to this) "
predicateType == 2
    ifTrue: [ ^ self _executePathConstantSelectionAt: offset ].

" if it is constant-constant "
predicateType == 1
    ifTrue: [ ^ self _executeConstantConstantSelectionAt: offset ].

" if it is path-path "
predicateType == 4
    ifTrue: [ ^ self _executePathPathSelectionAt: offset ].

self _error: #assocErrBadComparison
%

category: 'Setup'
method: QueryExecuter
_findIndexMatchingTerms: linksArray
withPaths: pathsArray
startingAt: offset
forOperationType: operationType
predicateType: predicateType

"Returns the index whose path terms match the path names described in linksArray
 at the given offset.  If an existing index is not found, see if linksArray
 describes a sub-path of an existing index.  If so, creates a fake index that
 utilizes the mappings provided by the existing index.  If no index exists, then
 returns the path evaluator that can be used to evaluate the path by brute
 force."

| iList indexObj pathEvaluator theIndexObj isRangeOperation |

pathEvaluator := self
  _buildPathEvaluatorForPredicateLinks: linksArray
  withPaths: pathsArray
  startingAt: offset.

iList := nsc _indexedPaths.
" if there are no indexes or it is path-path, returns the path evaluator "
( iList == nil _or: [ predicateType == 4 ] )
  ifTrue: [ ^ (pathEvaluator initialize nsc: nsc) asMostSpecificType ].

isRangeOperation := self _isRangeEqualityOperation: operationType.

" for each index on the receiver ... "
1 to: iList size by: 2 do: [ :i |
  indexObj := iList at: i.
  (iList at: i + 1) == 1
    ifTrue: [
      " see if the index matches the path "
      (indexObj hasIndexOnPath: pathEvaluator)
        ifTrue: [
          " if range index found for range operation or
          identity index found for identity operation "
          ( ( isRangeOperation _and: [ indexObj isRangeEqualityIndex ] ) _or:
          [ isRangeOperation not _and: [ indexObj isIdentityIndex ] ] )
            ifTrue: [
              ^ indexObj
            ]
            ifFalse: [ theIndexObj := indexObj ]
        ]
    ]
].

" if it is a range operation, no range index was found,
  so it returns the path evaluator "
isRangeOperation
  ifTrue: [ ^ (pathEvaluator initialize nsc: nsc) asMostSpecificType ]
  ifFalse: [
    " otherwise, an index was found, returns it "
    theIndexObj ~~ nil
      ifTrue: [
        ^ theIndexObj
      ]
  ].

" no indexObj had a path that was an exact match, so see if we can build
a fake index utilizing the sub-path of an existing index "
indexObj := IdentityIndex new.
indexObj indexDictionary: nsc _indexDictionary; nscRoot: nsc.
iList _putAllCommonPathTermsForPathArray: pathEvaluator into: indexObj.
indexObj size == pathEvaluator size
  ifTrue: [
    ^ indexObj
  ].

^ (pathEvaluator initialize nsc: nsc) asMostSpecificType
%

category: 'Setup'
method: QueryExecuter
_getOperationsOrder

"Returns an Array that is the order to invoke the operations described in the
 indexOperationsList.  The order is optimized to perform constant-constant
 predicates first, then perform path-constant/constant-path with indexes next,
 then perform identity-based operations second (==, ~~), then perform
 equality-based operations (=, ~=)."

| ordering constList identList equalList otherList indexList |

" if only one predicate, no work to be done "
( self size == 4 _and: [ (self at: 1) ~~ nil ] )
    ifTrue: [ ^ #( 1 ) ].

constList := Array new.
identList := Array new.
equalList := Array new.
otherList := Array new.
indexList := Array new.

1 to: self size by: 4 do: [ :i |
    " entry may be nil due to query optimization "
    (self at: i) ~~ nil
        ifTrue: [
            " if it is constant-constant "
            (self isConstantConstantAt: i)
                ifTrue: [ constList addLast: i ]
                ifFalse: [
                    " if an index exists on the path and it is not path-path "
                    ( (self firstOperandAt: i) isPathEvaluator not _and:
                    [ (self isPathPathAt: i ) not ] )
                        ifTrue: [ indexList addLast: i ]
                        ifFalse: [
                            " if it is an identity operation (== or ~~) "
                            (self _isIdentityOperation: (self operatorAt: i))
                                ifTrue: [ identList addLast: i ]
                                ifFalse: [ " if operation is = or ~= "
                                    (self _isEqualityOperation: (self operatorAt: i))
                                        ifTrue: [ equalList addLast: i ]
                                        ifFalse: [ otherList addLast: i ]
                                ]
                        ]
                ]
        ]
].

ordering := Array new.
1 to: constList size do: [ :i | ordering addLast: (constList at: i) ].
1 to: indexList size do: [ :i | ordering addLast: (indexList at: i) ].
1 to: identList size do: [ :i | ordering addLast: (identList at: i) ].
1 to: equalList size do: [ :i | ordering addLast: (equalList at: i) ].
1 to: otherList size do: [ :i | ordering addLast: (otherList at: i) ].
^ ordering
%

category: 'Testing'
method: QueryExecuter
_isIdentityOperation: searchOp

"Returns true if the given search operation is either == or ~~."

^ searchOp == 3 _or: [ searchOp == 7 ]
%

category: 'Testing'
method: QueryExecuter
_isEqualityOperation: searchOp

"Returns true if the given search operation is either = or ~=."

^ searchOp == 2 _or: [ searchOp == 6 ]
%

category: 'Testing'
method: QueryExecuter
_isRangeEqualityOperation: searchOp

"Returns true if the given search operation is one of < > = <= >= or ~=."

" ^ #(0 1 2 4 5 6) includesIdentical: searchOp "

^ (searchOp ~~ 3) _and: [ searchOp < 7 ]
%

category: 'Query Select'
method: QueryExecuter
_perform: selector over: nsc1 and: nsc2

"Send the given comparison selector to each element in nsc1 with each element
 in nsc2 as an argument.  The first time the comparison selector evaluates to
 true, returns true.  Otherwise, returns false."

nsc1 do: [ :obj1 |
    nsc2 do: [ :obj2 |
        (obj1 perform: selector with: obj2)
            ifTrue: [ ^ true ]
    ]
].
^ false
%

category: 'Testing'
method: QueryExecuter
isConstantConstantAt: offset

"Returns whether the predicate at the given offset is a constant-constant
 type."

^ (self at: offset) == 1
%

category: 'Testing'
method: QueryExecuter
isPathConstantAt: offset

"Returns whether the predicate at the given offset is a path-constant type."

^ (self at: offset) == 2
%

category: 'Testing'
method: QueryExecuter
isPathPathAt: offset

"Returns whether the predicate at the given offset is a path-path type."

^ (self at: offset) == 4
%

category: 'Accessing'
method: QueryExecuter
operatorAt: offset

"Returns the operator number (0-9) for the predicate at the given offset."

^ self at: offset + 2
%

category: 'Accessing'
method: QueryExecuter
firstOperandAt: offset

"Returns the first operand for the predicate at the given offset."

^ self at: offset + 1
%

category: 'Accessing'
method: QueryExecuter
secondOperandAt: offset

"Returns the second operand for the predicate at the given offset."

^ self at: offset + 3
%

category: 'Accessing'
method: QueryExecuter
nsc

"Returns the value of the instance variable 'nsc'."

   ^nsc
%

category: 'Updating'
method: QueryExecuter
nsc: newValue

"Modify the value of the instance variable 'nsc'."

nsc := newValue
%

category: 'Setup'
method: QueryExecuter
_buildIndexOperationsList: anArray

"Builds the indexed part that can be used to invoke operations on indexes
 to return the results of a query.  The Array has the following format:

   1.  predicate type
   2.  first index object (or path evaluator if no index exists)
   3.  search operation type (integer between 0-8)
   4.  value or second index object (depending upon predicate type)"

| varsArray termsArray linksArray pathsArray indexObj indexObj2
firstTermOffset secondTermOffset firstValOffset secondValOffset predicateType |
varsArray := anArray at: 1.
termsArray := anArray at: 2.
linksArray := anArray at: 3.
pathsArray := anArray at: 4.

" for each predicate described in the termArray ... "
1 to: termsArray size by: 7 do: [ :i |
  predicateType := self _determinePredicateType: termsArray startingAt: i.

  predicateType == 2 " path-constant "
    ifTrue: [
      firstTermOffset := termsArray at: i + 6.
      secondValOffset := termsArray at: i + 2
    ]
    ifFalse: [
      predicateType == 3 " constant-path "
        ifTrue: [
          secondTermOffset := termsArray at: i + 3.
          firstValOffset := termsArray at: i + 5
        ]
        ifFalse: [
          predicateType == 4 " path-path "
            ifTrue: [
              firstTermOffset := termsArray at: i + 6.
              secondTermOffset := termsArray at: i + 3
            ]
            ifFalse: [ " constant-constant "
              firstValOffset := termsArray at: i + 5.
              secondValOffset := termsArray at: i + 2
            ]
        ]
    ].

  " if it is path-constant or path-path "
  (predicateType == 2 _or: [ predicateType == 4 ] )
    ifTrue: [ 
      self addLast: predicateType.

      indexObj := self _findIndexMatchingTerms: linksArray
        withPaths: pathsArray
        startingAt: firstTermOffset
        forOperationType: (termsArray at: i)
        predicateType: predicateType.

      predicateType == 4
        ifTrue: [ " if it is path-path "
          indexObj2 := self _findIndexMatchingTerms: linksArray
            withPaths: pathsArray
            startingAt: secondTermOffset
            forOperationType: (termsArray at: i)
            predicateType: predicateType.

            self addLast: indexObj2.
            self addLast: (self _inverseOperatorFor: (termsArray at: i)).
            self addLast: indexObj
        ]
        ifFalse: [ " if it is path-constant "
          self addLast: indexObj.

          " if unary predicate "
          (termsArray at: i) == 8
            ifTrue: [
              " check if last object on the path is a Boolean "
              | constraint |
              constraint := indexObj lastElementClass.
              (constraint ~~ nil _and: [constraint ~~ Boolean])
                ifTrue: [ self _error: #rtErrLastConstraintNotBoolean ].

              " recast predicate to be '= true' "
              self addLast: 2.
              self addLast: true 
            ]
            ifFalse: [
              self addLast: (termsArray at: i).
              self addLast: (varsArray at: secondValOffset)
            ]
        ]
    ]
    ifFalse: [
      " if it is constant-path "
      predicateType == 3
        ifTrue: [ 
          " modify the predicate to be path-constant "
          self addLast: 2.

          indexObj := self _findIndexMatchingTerms: linksArray
            withPaths: pathsArray
            startingAt: secondTermOffset
            forOperationType: (termsArray at: i)
            predicateType: predicateType.

          self addLast: indexObj.
          self addLast: (self _inverseOperatorFor: (termsArray at: i)).
          self addLast: (varsArray at: firstValOffset)
        ]
        ifFalse: [ " it is constant-constant "
          self addLast: predicateType.
          self addLast: (varsArray at: firstValOffset).
          self addLast: (termsArray at: i).
          self addLast: (varsArray at: secondValOffset)
        ]
    ]
]
%

category: 'Query SelectAsStream'
method: QueryExecuter
_boundQuerySelectAsStream: anArray

"Argument anArray is a four element Array of Arrays describing a SelectBlock
 in the manner needed to process a query on the receiver:

   1.  Array of the bound variables from the predicate
   2.  Array of the predicate's terms
   3.  Array of the predicate's paths
   4.  Array of Strings of the path names used in the predicate"
| numPredicates operand1 stream |

" get a description of the operations to invoke on indexes "
self _buildIndexOperationsList: anArray.

(self isPathConstantAt: 1)
    ifFalse: [ ^ self _error: #rtErrBagInvalidPredicateForStreamSelection ].

operand1 := self firstOperandAt: 1.
(operand1 isKindOf: RangeEqualityIndex)
    ifFalse: [ ^ self _error: #rtErrBagNoRangeIndexOnPathExpression ].

" see if there are two predicates on the same path with the same index "
(numPredicates := self numPredicates) == 2
  ifTrue: [
    " must have identical path "
    operand1 ~~ (self firstOperandAt: 5)
      ifTrue: [ ^ self _error: #rtErrBagOnlyOnePredicateAllowed ].
    " see if predicates can be reduced to one "
    self _consolidatePredicatesAt: 1 and: 5.
    " check number of predicates after consolidation "
    self numPredicates > 1
      ifTrue: [ ^ self _error: #rtErrBagOnlyOnePredicateAllowed ].
    " check if query was satisfiable (see if all operands are now nil) "
    (self firstOperandAt: 1) == nil
      ifTrue: [
        stream := operand1 readStreamClass new rangeIndex: operand1.
        ^ stream currentStack: (Array with: 0).
      ]
  ]
  ifFalse: [
    numPredicates > 1
      ifTrue: [ ^ self _error: #rtErrBagOnlyOnePredicateAllowed ].

    (self isPathConstantAt: 1)
        ifFalse: [ ^ self _error: #rtErrBagInvalidPredicateForStreamSelection ].
  ].

^ self _executePathConstantStreamSelectionAt: 1
%

category: 'Query SelectAsStream'
method: QueryExecuter
_executePathConstantStreamSelectionAt: offset

"Execute the path-constant type predicate operation that is described at the
 given offset.  Returns a stream that is the result of the query."

| indexObj evalObj searchOp searchVal |
indexObj := self firstOperandAt: offset.
searchOp := self operatorAt: offset.
searchVal := self secondOperandAt: offset.
evalObj := indexObj asQueryEvaluator.

self _check: indexObj compare: searchOp value: searchVal.

" if it is < or < = "
(searchOp == 0 _or: [ searchOp == 4 ] )
    ifTrue: [
        ^ evalObj _findAllValuesGreaterThan: nil 
                       andEquals: true
                       andLessThan: searchVal 
                       andEquals: (searchOp == 4) 
                       using: BtreeComparisonForCompare
    ].
" if it is > or >= "
(searchOp == 1 _or: [ searchOp == 5 ] )
    ifTrue: [
        ^ evalObj _findAllValuesGreaterThanKey: searchVal andEquals: (searchOp == 5) using: BtreeComparisonForCompare
    ].
" if it is ="
searchOp == 2
    ifTrue: [
        ^ evalObj
            _findAllValuesGreaterThan: searchVal
            andEquals: true
            andLessThan: searchVal
            andEquals: true
            using: BtreeComparisonForCompare
    ].
" if it is a dual predicate "
searchOp == 9
    ifTrue: [
      ^ evalObj  _findAllValuesGreaterThan: (searchVal at: 2)
          andEquals: ((searchVal at: 1) == 5)
          andLessThan: (searchVal at: 4)
          andEquals: ((searchVal at: 3) == 4)
           using: BtreeComparisonForCompare
    ].

^ self _error: #rtErrBagOperationNotSupportedForStreamSelection
%

category: 'Testing'
method: QueryExecuter
_check: indexObj compare: compareOp value: searchVal

"Raise an error if the comparison operation is not valid for the index object
 and the search value."

" check for range operation using an identity index "
( ( self _isRangeEqualityOperation: compareOp ) _and:
[ indexObj isRangeEqualityIndex not ] )
    ifTrue: [ ^ indexObj _errorCannotInvokeRangeOperationOnIdentityIndex ].
%

category: 'Setup'
method: QueryExecuter
_inverseOperatorFor: operator

"Returns the operator number that is the inverse of the given operator number.
 This is used to reverse the operands in a predicate.  For example, the inverse
 of < is >=; the inverse of = is = (no change)."

^ #( 1 0 2 3 5 4 6 7 8 ) at: operator + 1
%

category: 'Query Optimization'
method: QueryExecuter
_checkPathPathAt: i

"Check a path-path predicate to see if the query is satisfiable."

| indexObj operator |
indexObj := self firstOperandAt: i.

" if paths are the same "
(indexObj hasSamePathAs: (self secondOperandAt: i))
  ifTrue: [
    operator := self operatorAt: i.
    " if operator is =, ==, <=, >= predicate will always be true "
    ( operator >= 2 _and: [ operator <= 5 ] )
      ifTrue: [
        " turn predicate into a unary type evaluating to true "
        self at: i put: 1. " constant-constant "
        self at: i + 1 put: true. " value "
        self at: i + 2 put: 8. " unary operation "
        self at: i + 3 put: true. " value "
      ]
      ifFalse: [ " operator is <, >, ~=, or ~~ "
        " if path does not have a set-valued term "
      ]
  ]
%

category: 'Query Optimization'
method: QueryExecuter
_checkSamePathsAt: i

"Perform two checks for the same path:  Check if the predicate at the given
 offset is a path-path predicate with the same path.  Also check if any
 subsequent predicates have the same path as the predicate at the given offset.
 If so, see if the predicates are redundant or if the terms can be
 consolidated."

| predicateList k |
" if path-path "
(self isPathPathAt: i)
    ifTrue: [ self _checkPathPathAt: i ]
    ifFalse: [ " is path-constant "

        " if no more predicates, then we're done "
        i + 4 > self size
            ifTrue: [ ^ self ].

        predicateList := Array new.
        " first check each subsequent predicate for redundant predicates "
        i + 4 to: self size by: 4 do: [ :j |
            " if entry not nil and predicate not constant-constant "
            ( (self at: j) == nil _or: [ (self at: i) == nil _or:
            [ self isConstantConstantAt: j ] ] )
                ifFalse: [
                    " if subsequent predicate has operand with same path "
                    ((self firstOperandAt: i) hasSamePathAs: (self firstOperandAt: j))
                        ifTrue: [ " found predicates with same path "
                            (self _removeRedundantOperatorsAt: i and: j)
                                " if did not remove redundant predicates,
                                  put in list to attempt consolidation "
                                ifFalse: [ predicateList add: j ]
                        ]
                ]
        ].

        " now check for predicates that can be consolidated "
        1 to: predicateList size do: [ :j |
            k := predicateList at: j.
            " if entries not nil "
            ( (self at: i) ~~ nil _and: [ (self at: k) ~~ nil ] ) 
                ifTrue: [ self _consolidatePredicatesAt: i and: k ]
        ].
    ]
%

category: 'Query Optimization'
method: QueryExecuter
_consolidatePredicatesAt: i and: j

"See if the predicates at the give offset can be consolidated (i.e. can be
 satisfied with a single lookup).  If so, modify the first predicate entry in
 the receiver to contain all the information for the consolidated predicates
 and remove the second predicate."

| op1 op2 |

" check if both predicates are path-constant "
( (self isPathConstantAt: i) _and: [ self isPathConstantAt: j ] )
    ifTrue: [
        op1 := self operatorAt: i.
        op2 := self operatorAt: j.

        " if first operator is > or >= and second operator is < or <= "
        ( ( op1 == 1 _or: [ op1 == 5 ] ) _and: [ op2 == 0 _or: [ op2 == 4] ] )
            ifTrue: [
                ( (self secondOperandAt: i) _idxForCompareGreaterThan:  (self secondOperandAt: j) )
                    ifTrue: [ ^ self _unsatisfiableQuery ].

                self at: i + 2 put: 9. " dual predicate operator type "
                self at: i + 3 put:
                    #[ op1, (self secondOperandAt: i), op2, (self secondOperandAt: j) ].

                " remove the second predicate "
                self _removePredicateAt: j
            ].

        " if first operator is < or <= and second operator is > or >= "
        ( ( op1 == 0 _or: [ op1 == 4 ] ) _and: [ op2 == 1 _or: [ op2 == 5] ] )
            ifTrue: [
                ( (self secondOperandAt: i) _idxForCompareLessThan: (self secondOperandAt: j) )
                    ifTrue: [ ^ self _unsatisfiableQuery ].

                self at: i + 2 put: 9. " dual predicate operator type "
                self at: i + 3 put:
                    #[ op2, (self secondOperandAt: j), op1, (self secondOperandAt: i) ].

                " remove the second predicate "
                self _removePredicateAt: j
            ]
    ]
%

category: 'Query Optimization'
method: QueryExecuter
_removeRedundantOperatorsAt: i and: j

"Checks the predicates at the given offsets to see if one of them is redundant.
 If so, puts nil values in the entry of the redundant one and returns true."

| op1 op2 |
op1 := self operatorAt: i.
op2 := self operatorAt: j.

" check if both predicates are path-constant "
( (self isPathConstantAt: i) _and: [ self isPathConstantAt: j ] )
    ifTrue: [
        " if path has a set-valued term, no redundancies are currently removed "
        " NOTE: Redundancies can be removed (they are backwards of the
          removals performed for a singleton path) "

        op1 == op2
            ifTrue: [ " operators are the same "
                ( op1 == 0 _or: [ op1 == 4 ] ) " operator: < or <= "
                    ifTrue: [ " choose smallest value "
                        ( (self secondOperandAt: i) < (self secondOperandAt: j) )
                            ifTrue: [ self _removePredicateAt: j ]
                            ifFalse: [ self _removePredicateAt: i ].
                        ^ true
                    ].

                ( op1 == 1 _or: [ op1 == 5 ] ) " operator: > or >= "
                    ifTrue: [  " choose largest value "
                        ( (self secondOperandAt: i) > (self secondOperandAt: j) )
                            ifTrue: [ self _removePredicateAt: j ]
                            ifFalse: [ self _removePredicateAt: i ].
                        ^ true
                    ].

                op1 == 2 " operator: = "
                    ifTrue: [
                        ( (self secondOperandAt: i) = (self secondOperandAt: j) )
                            ifTrue: [ self _removePredicateAt: j ]
                            ifFalse: [ self _unsatisfiableQuery ].
                        ^ true
                    ].

               op1 == 3 " operator: == "
                    ifTrue: [
                        ( (self secondOperandAt: i) == (self secondOperandAt: j) )
                            ifTrue: [ self _removePredicateAt: j ]
                            ifFalse: [ self _unsatisfiableQuery ].
                        ^ true
                    ].

            ]
            ifFalse: [ " operators are different "
                ( ( op1 == 0 _and: [ op2 == 4 ] ) " op1: < and op2: <= "
                _or: [ op1 == 4 _and: [ op2 == 0 ] ] ) " op1: <= and op2: < "
                    ifTrue: [ " choose smallest value "
                        ( (self secondOperandAt: i) < (self secondOperandAt: j) )
                            ifTrue: [ self _removePredicateAt: j ]
                            ifFalse: [
                                ( (self secondOperandAt: i) > (self secondOperandAt: j) )
                                    ifTrue: [ self _removePredicateAt: i ]
                                    ifFalse: [ " operands are = "
                                        op1 == 0
                                            ifTrue: [ self _removePredicateAt: j ]
                                            ifFalse: [ self _removePredicateAt: i ]
                                    ]
                            ].
                        ^ true
                    ].

                ( ( op1 == 1 _and: [ op2 == 5 ] ) " op1: > and op2: >= "
                _or: [ op1 == 5 _and: [ op2 == 1 ] ] ) " op1: >= and op2: > "
                    ifTrue: [ " choose largest value "
                        ( (self secondOperandAt: i) > (self secondOperandAt: j) )
                            ifTrue: [ self _removePredicateAt: j ]
                            ifFalse: [
                                ( (self secondOperandAt: i) < (self secondOperandAt: j) )
                                    ifTrue: [ self _removePredicateAt: i ]
                                    ifFalse: [ " operands are = "
                                        op1 == 1
                                            ifTrue: [ self _removePredicateAt: j ]
                                            ifFalse: [ self _removePredicateAt: i ]
                                    ]
                            ].
                        ^ true
                    ].

                ( ( op1 == 2 _and: [ op2 == 3 ] ) " op1: = and op2: == "
                _or: [ op1 == 3 _and: [ op2 == 2 ] ] ) " op1: == and op2: = "
                    ifTrue: [
                        ( (self secondOperandAt: i) == (self secondOperandAt: j) )
                            ifTrue: [ self _removePredicateAt: j ]
                            ifFalse: [ self _unsatisfiableQuery ].
                        ^ true
                    ].

                op1 == 2 " op1: = "
                    ifTrue: [
                        op2 == 0 " op2: < "
                            ifTrue: [
                                ( (self secondOperandAt: i) < (self secondOperandAt: j) )
                                    ifTrue: [ self _removePredicateAt: j ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].
                        op2 == 4 " op2: <= "
                            ifTrue: [
                                ( (self secondOperandAt: i) <= (self secondOperandAt: j) )
                                    ifTrue: [ self _removePredicateAt: j ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].
                        op2 == 1 " op2: > "
                            ifTrue: [
                                ( (self secondOperandAt: i) > (self secondOperandAt: j) )
                                    ifTrue: [ self _removePredicateAt: j ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].
                        op2 == 5 " op2: >= "
                            ifTrue: [
                                ( (self secondOperandAt: i) >= (self secondOperandAt: j) )
                                    ifTrue: [ self _removePredicateAt: j ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].

                    ].
                op2 == 2 " op2: = "
                    ifTrue: [
                        op1 == 0 " op1: < "
                            ifTrue: [
                                ( (self secondOperandAt: j) < (self secondOperandAt: i) )
                                    ifTrue: [ self _removePredicateAt: i ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].
                        op1 == 4 " op1: <= "
                            ifTrue: [
                                ( (self secondOperandAt: j) <= (self secondOperandAt: i) )
                                    ifTrue: [ self _removePredicateAt: i ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].
                        op1 == 1 " op1: > "
                            ifTrue: [
                                ( (self secondOperandAt: j) > (self secondOperandAt: i) )
                                    ifTrue: [ self _removePredicateAt: i ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].
                        op1 == 5 " op1: >= "
                            ifTrue: [
                                ( (self secondOperandAt: j) >= (self secondOperandAt: i) )
                                    ifTrue: [ self _removePredicateAt: i ]
                                    ifFalse: [ self _unsatisfiableQuery ].
                                ^ true
                            ].
                    ]
            ]
    ].

" try to eliminate path-constant/path-path predicates with = or == operator "

^ false
%

category: 'Query Optimization'
method: QueryExecuter
_unsatisfiableQuery

"The query has been deemed to be unsatisfiable.  Nil out each predicate entry."

1 to: self size do: [ :i | self at: i put: nil ]
%

category: 'Query Optimization'
method: QueryExecuter
_removePredicateAt: i

"Remove the entry for the predicate at the given offset by putting nil values
 in its slots."

#( nil nil nil nil ) copyFrom: 1 to: 4 into: self startingAt: i
%

category: 'Query Optimization'
method: QueryExecuter
optimize

"Perform query optimizations."

1 to: self size by: 4 do: [ :i |
    " ignore predicate if it is constant-constant or the entry is nil "
    ( (self isConstantConstantAt: i) _or: [ (self at: i) == nil ] )
        ifFalse: [
            self _transformNilQueriesAt: i.
            self _checkSamePathsAt: i.
        ]
]
%

category: 'Accessing'
method: QueryExecuter
numPredicates

"Returns the number of predicates after optimization."

| cnt |
cnt := 0.
1 to: self size by: 4 do: [ :i |
    (self at: i) ~~ nil ifTrue: [ cnt := cnt + 1 ]
].
^ cnt
%

category: 'Accessing'
method: QueryExecuter
operationSelectors

"Returns an Array of comparison operation selectors whose ordering corresponds
 to the operation integer for each predicate entry in the receiver."

^ #( #< #> #= #== #<= #>= #~= #~~)
%

category: 'Query Select'
method: QueryExecuter
_executePathPathNoSetValuedSelectionAt: offset

"Execute the path-path type predicate operation that is described at the given
 offset.  Returns a set that is the result of the query."

| pathEval1 searchOp pathEval2 operator tmpHolder val1 val2 obj bag incomplete |

pathEval1 := self firstOperandAt: offset.
searchOp := self operatorAt: offset.
pathEval2 := self secondOperandAt: offset.

operator := self _operationSelectors at: searchOp + 1.

incomplete := #_incompletePathTraversal.
bag := nsc _asIdentityBag.

tmpHolder := NscBuilder for: nsc speciesForSelect new max: nsc size.

pathEval1 _initTraverseCache.
pathEval2 _initTraverseCache.

pathEval1 isIndexOnRootNsc
    ifTrue: [ " query of the form { :o | o = o.a.b.c } "
       | ivOffsetCache |
       ivOffsetCache := pathEval2 _createIvOffsetCache.
       1 to: bag size do: [ :i |
            (obj := bag _at: i) ~~ nil
                ifTrue: [
                    val2 := pathEval2 _traverseObject: obj cache: ivOffsetCache.
                    ( val2 ~~ incomplete _and:
                    [ obj perform: operator with: val2 ] )
                        ifTrue: [ tmpHolder add: obj ]
                ]
       ]
    ]
    ifFalse: [
        pathEval2 isIndexOnRootNsc
            ifTrue: [ " query of the form { :o | o.a.b.c = o } "
               | ivOffsetCache |
               ivOffsetCache := pathEval1 _createIvOffsetCache.
               1 to: bag size do: [ :i |
                    (obj := bag _at: i) ~~ nil
                        ifTrue: [
                            val1 := pathEval1 _traverseObject: obj cache: ivOffsetCache.
                            ( val1 ~~ incomplete _and:
                            [ val1 perform: operator with: obj ] )
                                ifTrue: [ tmpHolder add: obj ]
                        ]
               ]
            ]
            ifFalse: [ " query of the form { :o | o.a.b.c = o.d.e.f } "
               | ivOffsetCache1 ivOffsetCache2 |
               ivOffsetCache1 := pathEval1 _createIvOffsetCache.
                ivOffsetCache2 := pathEval2 _createIvOffsetCache.
               1 to: bag size do: [ :i |
                    (obj := bag _at: i) ~~ nil
                        ifTrue: [
                            (val1 := pathEval1 _traverseObject: obj cache: ivOffsetCache1) ~~ incomplete
                                ifTrue: [
                                    ( (val2 := pathEval2 _traverseObject: obj cache: ivOffsetCache2) ~~ incomplete _and:
                                    [ val1 perform: operator with: val2 ] )
                                        ifTrue: [ tmpHolder add: obj ]
                                ]
                        ]
               ]
            ]
    ].

^ tmpHolder completeBag
%

category: 'Query Optimization'
method: QueryExecuter
_transformNilQueriesAt: i

"Check if the predicate at the given offset is a path-constant query, with a
 comparison operator of <, <=, >, or >= on a nil value.  If so, either raise
 an error for an invalid query, or transform the query into an = comparison."

| op operand |
" if path-constant on a nil value and last object on the path is a basic class "
( (self isPathConstantAt: i) _and:
[ (self secondOperandAt: i) == nil ] )
  ifTrue: [
    operand := self firstOperandAt: i.
    op := self operatorAt: i.

    "no need to fail when nil is an operand 
        -- we can handle the comparison without errors
        -- special cases here not enforceable without Constraints
     "

    " if operator is = and we have an identity index,
      transform comparison to == "
    ( op == 2 _and: [ operand isIdentityIndex ] )
      ifTrue: [ self at: i + 2 put: 3 ]
  ]
%

category: 'Accessing'
method: QueryExecuter
_operationSelectors

"Returns an Array of comparison operation selectors whose ordering corresponds
 to the operation integer for each predicate entry in the receiver."

^ #( #_idxForCompareLessThan: 
    #_idxForCompareGreaterThan: 
    #_idxForCompareEqualTo:  
    #==
    #_idxForCompareLessThanOrEqualTo: 
    #_idxForCompareGreaterThanOrEqualTo: 
    #_idxForCompareNotEqualTo: 
    #~~
    nil
    #_idxGreaterThanAndLessThanValues:
  )
%

category: 'Query Support'
method: QueryExecuter
evaluatePathConstantPredicates: querySpec for: anObject

"Evaluate all the path-constant predicates defined in querySpec for the given
 object.  Returns true if the object satisfies all the predicates."

1 to: querySpec size by: 3 do: [ :j |
    ((querySpec at: j) traverse:  anObject
        andCompare: (querySpec at: j + 1) 
        with: (querySpec at: j + 2))
        ifFalse: [ ^ false ]
].
^ true
%

category: 'Query Support'
method: QueryExecuter
evaluatePathPathPredicates: querySpec for: anObject

"Evaluate all the path-path predicates defined in querySpec for the given
 object.  Returns true if the object satisfies all the predicates."

1 to: querySpec size by: 3 do: [ :j |
    ( (querySpec at: j) traverse:  anObject
        andCompare: (querySpec at: j + 1) 
        withTraverser: (querySpec at: j + 2) )
        ifFalse: [ ^ false ]
].
^ true
%

category: 'Query Detect'
method: QueryExecuter
findFirstThatSatisfiesPredicatesStartingAt: beginOffset
ordering: ordering
stream: stream

"Returns whether the given object satisfies the predicate described at
 the given offset."

| obj pcQuerySpec ppQuerySpec array offset hasTruePredicate searchOp
secondOperand pathEval |

" build Arrays that hold the specifications of the predicates "
pcQuerySpec := Array new.   " for path-constant predicates "
ppQuerySpec := Array new.   " for path-path predicates "

hasTruePredicate := false.
beginOffset to: ordering size do: [ :j |
  offset := ordering at: j.

  offset ~~ nil
    ifTrue: [
      " if constant-constant predicate, check to see if it is true "
      (self isConstantConstantAt: offset)
        ifTrue: [
          (self _executeConstantConstantPredicateAt: offset)
            ifTrue: [ hasTruePredicate := true ]
            ifFalse: [ ^ #_incompletePathTraversal ]
        ]
        ifFalse: [
          (self isPathConstantAt: offset)
            ifTrue: [ array := pcQuerySpec ]
            ifFalse: [ array := ppQuerySpec ].

          " the first operand (a PathEvaluator) "
          pathEval := (self firstOperandAt: offset) asPathEvaluator.
          pathEval _initTraverseCache.
          array add: pathEval.
          " the comparison selector "

          searchOp := self operatorAt: offset.
          " insert comparison selector "
          array add: (self _operationSelectors at: searchOp + 1).
          secondOperand := self secondOperandAt: offset.
          " if dual predicate, transform argument Array "
          searchOp == 9
            ifTrue: [
              secondOperand :=
                #[ secondOperand at: 2,
                 (secondOperand at: 1) == 5,
                 secondOperand at: 4,
                 (secondOperand at: 3) == 4
                 ]
            ].
          array add: secondOperand.
        ]
    ]
].

ppQuerySpec isEmpty
  ifTrue: [
    pcQuerySpec isEmpty
      ifFalse: [ " only path-constants "
        stream ~~ nil
          ifTrue: [
            [ stream atEnd ] whileFalse: [
              ( (obj := stream next) ~~ nil _and:
              [ self evaluatePathConstantPredicates: pcQuerySpec for: obj ] )
                ifTrue: [ ^ obj ]
            ]
          ]
          ifFalse: [
            nsc do: [ :theObj |
              ( theObj ~~ nil _and:
              [ self evaluatePathConstantPredicates: pcQuerySpec for: theObj ] )
                ifTrue: [ ^ theObj ]
            ]
          ]
      ]
  ]
  ifFalse: [
    pcQuerySpec isEmpty
      ifTrue: [ " only path-paths "
        stream ~~ nil
          ifTrue: [
            [ stream atEnd ] whileFalse: [
              ( (obj := stream next) ~~ nil _and:
              [ self evaluatePathPathPredicates: ppQuerySpec for: obj ] )
                ifTrue: [ ^ obj ]
            ]
          ]
          ifFalse: [
            nsc do: [ :theObj |
              ( theObj ~~ nil _and:
              [ self evaluatePathPathPredicates: ppQuerySpec for: theObj ] )
                ifTrue: [ ^ theObj ]
            ]
          ]
      ]
      ifFalse: [ " both path-constants and path-paths "
        stream ~~ nil
            ifTrue: [
              [ stream atEnd ] whileFalse: [
                ( (obj := stream next) ~~ nil _and:
                [ (self evaluatePathConstantPredicates: pcQuerySpec for: obj) _and:
                [ self evaluatePathPathPredicates: ppQuerySpec for: obj ] ] )
                  ifTrue: [ ^ obj ]
              ]
            ]
            ifFalse: [
              nsc do: [ :theObj |
                ( theObj ~~ nil _and:
                [ (self evaluatePathConstantPredicates: pcQuerySpec for: theObj) _and:
                [ self evaluatePathPathPredicates: ppQuerySpec for: theObj ] ] )
                  ifTrue: [ ^ theObj ]
              ]
            ]
      ]
  ].

^ ( hasTruePredicate _and: [ nsc isEmpty not ] )
  ifTrue: [
    stream ~~ nil
      ifTrue: [ stream next ]
      ifFalse: [ nsc _asIdentityBag _at: 1 ]
  ]
  ifFalse: [ #_incompletePathTraversal ]
%

category: 'Query Select'
method: QueryExecuter
findAllThatSatisfyPredicatesStartingAt: beginOffset ordering: ordering

"Returns an NSC of all objects that satisfy the predicates beginning at the
 given offset."

| pcQuerySpec ppQuerySpec array offset tmpHolder searchOp secondOperand pathEval |

" build Arrays that hold the specifications of the predicates "
pcQuerySpec := Array new.   " for path-constant predicates "
ppQuerySpec := Array new.   " for path-path predicates "
beginOffset to: ordering size do: [ :j |
  offset := ordering at: j.

  offset ~~ nil
    ifTrue: [

      " if constant-constant path, check to see if it is satisfiable "
      (self isConstantConstantAt: offset)
        ifTrue: [
          (self _executeConstantConstantPredicateAt: offset)
            ifFalse: [ ^ nsc speciesForSelect new ]
        ]
        ifFalse: [

          (self isPathConstantAt: offset)
            ifTrue: [ array := pcQuerySpec ]
            ifFalse: [ array := ppQuerySpec ].

          " the first operand (a PathEvaluator) "
          pathEval := (self firstOperandAt: offset) asPathEvaluator.
          pathEval _initTraverseCache.
          array add: pathEval.

          searchOp := self operatorAt: offset.
          " insert comparison selector "
          array add: (self _operationSelectors at: searchOp + 1).
          secondOperand := self secondOperandAt: offset.
          " if dual predicate, transform argument Array "
          searchOp == 9
            ifTrue: [
              secondOperand :=
                #[ secondOperand at: 2,
                 (secondOperand at: 1) == 5,
                 secondOperand at: 4,
                 (secondOperand at: 3) == 4
                 ]
            ].
          array add: secondOperand.
        ]
    ]
].

ppQuerySpec isEmpty
  ifTrue: [
    pcQuerySpec isEmpty
      ifTrue: [ ^ nsc ]
      ifFalse: [ " only path-constants "
        tmpHolder := NscBuilder for: nsc speciesForSelect new max: nsc size.
        nsc do: [ :obj |
          ( obj ~~ nil _and:
          [ self evaluatePathConstantPredicates: pcQuerySpec for: obj] )
            ifTrue: [ tmpHolder add: obj ]
        ]
      ]
  ]
  ifFalse: [
    tmpHolder := NscBuilder for: nsc speciesForSelect new max: nsc size.
    pcQuerySpec isEmpty
      ifTrue: [ " only path-paths "
        nsc do: [ :obj |
          ( obj ~~ nil _and:
          [ self evaluatePathPathPredicates: ppQuerySpec for: obj ] )
            ifTrue: [ tmpHolder add: obj ]
        ]
      ]
      ifFalse: [ " both path-constants and path-paths "
        nsc do: [ :obj |
          ( obj ~~ nil _and:
          [ (self evaluatePathConstantPredicates: pcQuerySpec for: obj) _and:
          [ self evaluatePathPathPredicates: ppQuerySpec for: obj ] ] )
            ifTrue: [ tmpHolder add: obj ]
        ]
      ]
  ].

^  tmpHolder completeBag
%

category: 'Formatting'
method: QueryExecuter
printOn: aStream

"Puts a displayable representation of the receiver on the given stream."

"Copy the implementation from Object so we don't inherit it from Collection."

aStream nextPutAll: self asString
%

category: 'Constants'
method: QueryExecuter
bruteThreshold

""

^ 1000
%
 
