Add transaction buffer filter.

impl/memory/datastore_query.go

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 package memory
 
 import (
         "bytes"
         "encoding/base64"
         "errors"
@@ skipping 84 matching lines @@
         }
         if p, _, _ := fq.IneqFilterHigh(); p != "" {
                 numComponents++
         }
         for _, v := range fq.EqFilters() {
                 numComponents += v.Len()
         }
         return numComponents
 }
 
-func reduce(fq *ds.FinalizedQuery, ns string, isTxn bool) (*reducedQuery, error) {
-        if err := fq.Valid(globalAppID, ns); err != nil {
-                return nil, err
-        }
-        if isTxn && fq.Ancestor() == nil {
-                return nil, fmt.Errorf("queries within a transaction must include an Ancestor filter")
-        }
-        if num := numComponents(fq); num > MaxQueryComponents {
-                return nil, fmt.Errorf(
-                        "gae/memory: query is too large. may not have more than "+
-                                "%d filters + sort orders + ancestor total: had %d",
-                        MaxQueryComponents, num)
-        }
-
-        ret := &reducedQuery{
-                ns:           ns,
-                kind:         fq.Kind(),
-                suffixFormat: fq.Orders(),
-        }
-
-        eqFilts := fq.EqFilters()
-        ret.eqFilters = make(map[string]stringset.Set, len(eqFilts))
-        for prop, vals := range eqFilts {
-                sVals := stringset.New(len(vals))
-                for _, v := range vals {
-                        sVals.Add(string(serialize.ToBytes(v)))
-                }
-                ret.eqFilters[prop] = sVals
-        }
-
+// GetBinaryBounds gets the binary encoding of the upper and lower bounds of
+// the inequality filter on fq, if any is defined. If a bound does not exist,
+// it is nil.
+//
+// NOTE: if fq specifies a descending sort order for the inequality, the bounds
+// will be inverted, incremented, and fliped.
+func GetBinaryBounds(fq *ds.FinalizedQuery) (lower, upper []byte) {
         // Pick up the start/end range from the inequalities, if any.
         //
         // start and end in the reducedQuery are normalized so that `start >=
         // X < end`. Because of that, we need to tweak the inequality filters
         // contained in the query if they use the > or <= operators.
-        startD := []byte(nil)
-        endD := []byte(nil)
         if ineqProp := fq.IneqFilterProp(); ineqProp != "" {
                 _, startOp, startV := fq.IneqFilterLow()
                 if startOp != "" {
-                        startD = serialize.ToBytes(startV)
+                        lower = serialize.ToBytes(startV)
                         if startOp == ">" {
-                                startD = increment(startD)
+                                lower = increment(lower)
                         }
                 }
 
                 _, endOp, endV := fq.IneqFilterHigh()
                 if endOp != "" {
-                        endD = serialize.ToBytes(endV)
+                        upper = serialize.ToBytes(endV)
                         if endOp == "<=" {
-                                endD = increment(endD)
+                                upper = increment(upper)
                         }
                 }
 
                 // The inequality is specified in natural (ascending) order in the query's
                 // Filter syntax, but the order information may indicate to use a descending
                 // index column for it. If that's the case, then we must invert, swap and
                 // increment the inequality endpoints.
                 //
                 // Invert so that the desired numbers are represented correctly in the index.
                 // Swap so that our iterators still go from >= start to < end.
                 // Increment so that >= and < get correctly bounded (since the iterator is
                 // still using natrual bytes ordering)
-                if ret.suffixFormat[0].Descending {
+                if fq.Orders()[0].Descending {
                         hi, lo := []byte(nil), []byte(nil)
-                        if len(startD) > 0 {
-                                lo = increment(serialize.Invert(startD))
+                        if len(lower) > 0 {
+                                lo = increment(serialize.Invert(lower))
                         }
-                        if len(endD) > 0 {
-                                hi = increment(serialize.Invert(endD))
+                        if len(upper) > 0 {
+                                hi = increment(serialize.Invert(upper))
                         }
-                        endD, startD = lo, hi
+                        upper, lower = lo, hi
                 }
         }
+        return
+}
+
+func reduce(fq *ds.FinalizedQuery, ns string, isTxn bool) (*reducedQuery, error) {
+        if err := fq.Valid(globalAppID, ns); err != nil {
+                return nil, err
+        }
+        if isTxn && fq.Ancestor() == nil {
+                return nil, fmt.Errorf("queries within a transaction must include an Ancestor filter")
+        }
+        if num := numComponents(fq); num > MaxQueryComponents {
+                return nil, fmt.Errorf(
+                        "gae/memory: query is too large. may not have more than "+
+                                "%d filters + sort orders + ancestor total: had %d",
+                        MaxQueryComponents, num)
+        }
+
+        ret := &reducedQuery{
+                ns:           ns,
+                kind:         fq.Kind(),
+                suffixFormat: fq.Orders(),
+        }
+
+        eqFilts := fq.EqFilters()
+        ret.eqFilters = make(map[string]stringset.Set, len(eqFilts))
+        for prop, vals := range eqFilts {
+                sVals := stringset.New(len(vals))
+                for _, v := range vals {
+                        sVals.Add(string(serialize.ToBytes(v)))
+                }
+                ret.eqFilters[prop] = sVals
+        }
+
+        startD, endD := GetBinaryBounds(fq)
 
         // Now we check the start and end cursors.
         //
         // Cursors are composed of a list of IndexColumns at the beginning, followed
         // by the raw bytes to use for the suffix. The cursor is only valid if all of
         // its IndexColumns match our proposed suffixFormat, as calculated above.
         //
         // Cursors are mutually exclusive with the start/end we picked up from the
         // inequality. In a well formed query, they indicate a subset of results
         // bounded by the inequality. Technically if the start cursor is not >= the
@@ skipping 71 matching lines @@
                 // and the new value has overflowed this representation.
                 //
                 // Fortunately, the first byte of a serialized index column entry is a
                 // PropertyType byte, and the only valid values that we'll be incrementing
                 // are never equal to 0xFF, since they have the high bit set (so either they're
                 // 0x8*, or 0x7*, depending on if it's inverted).
                 impossible(fmt.Errorf("incrementing %v would require more sigfigs", bstr))
         }
         return ret
 }