1//  Copyright (c) 2019 Couchbase, Inc.
2//  Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file
3//  except in compliance with the License. You may obtain a copy of the License at
4//    http://www.apache.org/licenses/LICENSE-2.0
5//  Unless required by applicable law or agreed to in writing, software distributed under the
6//  License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
7//  either express or implied. See the License for the specific language governing permissions
8//  and limitations under the License.
9
10package flex
11
12import (
13	"github.com/couchbase/query/expression"
14	"github.com/couchbase/query/value"
15)
16
17/*
18  - 1st version can start by only supporting the default type mapping,
19    ensuring that no other type mappings are defined.
20  - 2nd version can also handle another case when default type mapping
21    is disabled, and there is only 1 single explicit type mapping,
22    with no disabled type mappings.
23  - 3rd version can also handle another case when default type mapping
24    is disabled, and there are only explicit type mappings,
25    with no disabled type mappings.
26  - 4th version can also handle another case when default type mapping
27    is disabled, and there are only explicit type mappings,
28    with no disabled type mappings.
29  - 5th version can also handle another case when default type mapping
30    exists and is enabled,
31    along with explicit type mappings (perhaps some disabled).
32
33disabled type mapping is similar to a non-dynamic type mapping with no
34properties/fields defined -- nothing is in the index.
35
36  - there's perhaps another variable in the matrix
37    where dynamic indexing is either enabled/disabled.
38
39in summary, when there's no dynamic indexing...
40                  versions:
41                            1      2      3      4      5
42 - default mapping        : y                           y
43 - 1 type mapping         :        1-only
44 - N type mappings        :               y      y      y
45 - disabled type mappings :                      y      y
46
47dynamic indexing needs to check that all the analyzers are the same
48across all mappings for a certain FieldPath, otherwise don't
49expose the dynamic indexing.
50- extra careful case is when some child FieldPath has inconsistent
51  settings than some parental FieldPath.
52- easy approach is all dynamic indexing must be the same, so no
53  inconsistencies.
54
55related, property/field usage has to also be the same across all mappings,
56otherwise don't expose the property/field.
57
58the main case...
59
60need to check the WHERE clause for all type mappings
61    (ex: type="beer"), because if you don't, there can be false negatives.
62    - example: FTS index has type mapping where type="beer", but the N1QL is
63      looking for WHERE name="coors"
64      - beware the false negative since the FTS index will
65        only have entries for beer docs and (importantly) will be missing
66        entries for brewery docs whose brewery name is "coors".
67    - to have no false negatives, the query has to look like
68      WHERE type="beer" AND name="coors"
69      otherwise n1fty should return not-sargable.
70    - this should be done carefully on a per-conjunction level, a'la...
71      ((type = "beer" AND
72        beer_name = "coors" AND
73        sargable-exprs-with-beer-only-fields AND
74        any-other-fields-are-considered-filterable) OR
75       (type = "brewery" AND
76        brewery_name = coors" AND
77        sargable-exprs-with-brewery-only-fields AND
78        any-other-fields-are-considered-filterable)).
79    - default type mapping need a more complex 'negative' type discriminator, like...
80      ((type != "beer" AND type != "brewery") AND
81       sargable-exprs-with-[non-beer/non-brewery]-fields AND
82       any-other-fields-are-considered-filterable).
83    - what if user references brewery fields (or other non-beer fields)
84      in the beer-centric subtree?
85      - ANS: those can be treated as filterable due to the conjunction,
86             and even though n1fty might be returning additional
87             false positives, it's logically correct.
88  - an approach is to have a sequence of condition-to-FlexIndex pairings.
89    - the doc type field can be checked as part of the conditions.
90    - the doc type may be based on docId regexp or prefix delimiter.
91
92// type=BEER
93//   IndexedFields += "type"=>"string".
94//   SupportedExprs += "eq"=>"type"=>"string"=>"ValueMust == BEER".
95//     adds to fieldTracks but not to flexBuild (Effect: "FlexBuild:n").
96//       ==> if only type field is in the query, then flexBuild will be empty,
97//           leading (hopefully) to empty SearchResult.
98//   will return not-sargable on any other usage of "type" field (via CheckFieldsUsed/IndexedFields).
99//
100// type=WINERY (disabled)
101//   IndexedFields += "type"=>"string".
102//   SupportedExprs += "eq"=>"type"=>"string"=>"ValueMust == WINERY"
103//     ==> not-sargable (via: Effect: "not-sargable"), same as #AAA above.
104//
105// or, just using the type field in any way should be not-sargable instead of filterable.
106//
107// type=<DEFAULT>
108//   IndexedFields += "type"=>"string".
109//   SupportedExprs += "NEQ"=>"type"=>"string"=>["BEER", "WINERY"].
110//     adds to fieldTracks but not to flexBuild (Effect: "FlexBuild:n").
111//       ==> if only type field is in the query, then flexBuild will be empty.
112//   will return not-sargable on any other usage of "type" field (via CheckFieldsUsed/IndexedFields).
113
114/*
115	// TODO: DocType might be specified via an id-regexp or prefix
116	// delimiter, but here we only handle the type-field approach.
117	CondFieldPath []string // Ex: ["type"], or empty when disabled.
118
119	// The Cond might represent a simple condition like `type="BEER"`
120	// or a complex negative check (e.g., !beer && !brewery) when the
121	// default mapping is used along with >=1 explicit type mappings.
122	// Might be empty on a disabled type mapping.
123	CondFlexIndexes []*CondFlexIndex // Ex: [{type=BEER, &FlexIndex{}}].
124
125// A negative list of non-matches for handling default mapping (!beer
126// && !brewery) can be represented by the cfi.Cond.
127//
128// issue: Need to return not-sargable if any other type is referenced?
129// ANS: - This is naturally taken care of during CheckFieldsUsed when
130//        there's no dynamic indexing.
131//      - Under dynamic indexing, need to add a SupportedExpr of
132//        "Effect: not-sargable" to capture that "type" field is
133//        never dynamically indexed?
134
135TODO: what if the type mapping also explicitly indexes the type field, too?
136      - and, what if that explicit type field has a different analyzer?
137*/
138
139// -------------------------------------------------------------------------
140
141// Associates a condition check to a FlexIndex, used for type mappings.
142type CondFlexIndex struct {
143	Cond      CondFunc
144	FlexIndex *FlexIndex // Ex: the type mapping when type=BEER.
145}
146
147// A slice of conditional flex indexes.
148type CondFlexIndexes []*CondFlexIndex
149
150// Returns true when the expressions match the condition check, also
151// returns an array of the requested "types" (obtained from query).
152type CondFunc func(ids Identifiers, es expression.Expressions) (
153	bool, []string, error)
154
155// Returns a CondFunc that represents checking a field for value equality.
156func MakeCondFuncEqVals(fieldPath []string, vals value.Values) CondFunc {
157	return func(ids Identifiers, es expression.Expressions) (
158		bool, []string, error) {
159		for _, e := range es {
160			if f, ok := e.(*expression.Eq); ok {
161				matches, c := MatchEqFieldPathToConstant(ids, fieldPath, f)
162				if matches {
163					for _, v := range vals {
164						if c.Value().Equals(v).Truth() {
165							return true, []string{v.Actual().(string)}, nil
166						}
167					}
168				}
169			} else if f, ok := e.(*expression.Or); ok {
170				// Collect all children of this Or expression, and check if
171				// every one of them are represented in the type vals.
172				exprs := collectDisjunctExprs(f, nil)
173				var eligible bool
174				var requestedTypes []string
175			OUTER:
176				for _, ee := range exprs {
177					if ff, ok := ee.(*expression.Eq); ok {
178						matches, c := MatchEqFieldPathToConstant(ids, fieldPath, ff)
179						if matches {
180							for _, v := range vals {
181								if c.Value().Equals(v).Truth() {
182									eligible = true
183									requestedTypes = append(requestedTypes, v.Actual().(string))
184									continue OUTER
185								}
186							}
187						}
188					}
189					eligible = false
190					break
191				}
192				if eligible {
193					return true, requestedTypes, nil
194				}
195			}
196		}
197
198		return false, nil, nil
199	}
200}
201
202// Returns a CondFunc that represents checking a field is not equal to
203// any of the given vals.
204func MakeCondFuncNeqVals(fieldPath []string, vals []string) CondFunc {
205	return func(ids Identifiers, es expression.Expressions) (
206		bool, []string, error) {
207		if len(vals) <= 0 {
208			return true, nil, nil // Empty vals means CondFunc always matches.
209		}
210
211		m := map[value.Value]struct{}{}
212		for _, v := range vals {
213			m[value.NewValue(v)] = struct{}{}
214		}
215
216		for _, e := range es {
217			n, ok := e.(*expression.Not)
218			if !ok {
219				continue
220			}
221
222			f, ok := n.Operand().(*expression.Eq)
223			if !ok {
224				continue
225			}
226
227			matches, c := MatchEqFieldPathToConstant(ids, fieldPath, f)
228			if matches {
229				delete(m, c.Value())
230			}
231		}
232
233		return len(m) <= 0, nil, nil
234	}
235}
236
237// -------------------------------------------------------------------------
238
239func MatchEqFieldPathToConstant(ids Identifiers, fieldPath []string,
240	f *expression.Eq) (bool, *expression.Constant) {
241	m := func(first, second expression.Expression) (bool, *expression.Constant) {
242		suffix, ok := ExpressionFieldPathSuffix(ids, first, fieldPath, nil)
243		if ok && len(suffix) <= 0 {
244			if c, ok := second.(*expression.Constant); ok {
245				return true, c
246			}
247		}
248
249		return false, nil
250	}
251
252	matches, c := m(f.First(), f.Second()) // Check pattern a.foo = c.
253	if matches {
254		return matches, c
255	}
256
257	return m(f.Second(), f.First()) // Commute to check c = a.foo.
258}
259
260// -------------------------------------------------------------------------
261
262func (s CondFlexIndexes) Sargable(
263	ids Identifiers, e expression.Expression, eFTs FieldTypes) (
264	rFieldTracks FieldTracks, rNeedsFiltering bool, rFB *FlexBuild, err error) {
265	o, ok := e.(*expression.Or)
266	if !ok {
267		o = expression.NewOr(e)
268	}
269
270	// OR-of-AND's means all the OR's children must match a flex index.
271	for _, oChild := range o.Children() {
272		cFI, requestedTypes, err := s.FindFlexIndex(ids, oChild)
273		if err != nil || cFI == nil {
274			return nil, false, nil, err
275		}
276
277		cFieldTracks, cNeedsFiltering, cFB, err := cFI.Sargable(ids, oChild, requestedTypes, eFTs)
278		if err != nil {
279			return nil, false, nil, err
280		}
281
282		if cFB == nil {
283			// If flex build is not available, it is safe to treat the expression as
284			// not-sargable. This can be in any of these situations:
285			// - an expression is treated as "not-sargable"
286			// - as expression is "FlexBuild:n" ("type"/cond expr)
287			// - expression doesn't hold a constant/parmeter
288			return nil, false, nil, nil
289		}
290
291		// Add the recursion's result to our composite results.
292		for cFieldTrack, n := range cFieldTracks {
293			if rFieldTracks == nil {
294				rFieldTracks = FieldTracks{}
295			}
296			rFieldTracks[cFieldTrack] += n
297		}
298
299		rNeedsFiltering = rNeedsFiltering || cNeedsFiltering
300
301		if rFB == nil {
302			rFB = &FlexBuild{Kind: "disjunct"}
303		}
304		rFB.Children = append(rFB.Children, cFB)
305
306		if len(cFieldTracks) > 0 {
307			continue // Expression sargable.
308		}
309
310		return nil, false, nil, nil // Expression not-sargable.
311	}
312
313	if rFB != nil && len(rFB.Children) == 1 { // Optimize OR-of-1-expr.
314		return rFieldTracks, rNeedsFiltering, rFB.Children[0], nil
315	}
316
317	// All expressions in the OR were sargable.
318	return rFieldTracks, rNeedsFiltering, rFB, nil
319}
320
321// Find the first FlexIndex whose Cond matches the given AND expression.
322func (s CondFlexIndexes) FindFlexIndex(ids Identifiers, e expression.Expression) (
323	rv *FlexIndex, requestedTypes []string, err error) {
324	children := collectConjunctExprs(e, nil)
325
326	for _, cfi := range s {
327		matches, reqTypes, err := cfi.Cond(ids, children)
328		if err != nil {
329			return nil, nil, err
330		}
331
332		if matches {
333			if rv != nil {
334				return nil, nil, nil // >1 matches, so not a match.
335			}
336
337			rv = cfi.FlexIndex
338			requestedTypes = reqTypes
339		}
340	}
341
342	return rv, requestedTypes, nil // Might return nil.
343}
344
345// -------------------------------------------------------------------------
346
347func collectConjunctExprs(ex expression.Expression,
348	children expression.Expressions) expression.Expressions {
349	if children == nil {
350		children = make(expression.Expressions, 0, 2)
351	}
352
353	if exAnd, ok := ex.(*expression.And); ok {
354		for _, child := range exAnd.Children() {
355			children = collectConjunctExprs(child, children)
356		}
357	} else {
358		children = append(children, ex)
359	}
360
361	return children
362}
363
364func collectDisjunctExprs(ex expression.Expression,
365	children expression.Expressions) expression.Expressions {
366	if children == nil {
367		children = make(expression.Expressions, 0, 2)
368	}
369
370	if exOr, ok := ex.(*expression.Or); ok {
371		for _, child := range exOr.Children() {
372			children = collectDisjunctExprs(child, children)
373		}
374	} else {
375		children = append(children, ex)
376	}
377
378	return children
379}
380