impl/memory: Implement Queries

impl/memory/datastore_query_test.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 (
         "math"
         "testing"
 
         dsS "github.com/luci/gae/service/datastore"
+        "github.com/luci/gae/service/datastore/serialize"
+        . "github.com/luci/luci-go/common/testing/assertions"
         . "github.com/smartystreets/goconvey/convey"
         "golang.org/x/net/context"
 )
 
 const (
         MaxUint     = ^uint(0)
         MaxInt      = int(MaxUint >> 1)
         IntIs32Bits = int64(MaxInt) < math.MaxInt64
 )
 
 func TestDatastoreQueries(t *testing.T) {
         Convey("Datastore Query suport", t, func() {
                 c := Use(context.Background())
                 ds := dsS.Get(c)
                 So(ds, ShouldNotBeNil)
 
                 Convey("can create good queries", func() {
-                        q := ds.NewQuery("Foo").KeysOnly().Limit(10).Offset(39)
-                        q = q.Start(queryCursor("kosmik")).End(queryCursor("krabs"))
+                        q := ds.NewQuery("Foo").Filter("farnsworth >", 20).KeysOnly().Limit(10).Offset(39)
+
+                        // normally you can only get cursors from inside of the memory
+                        // implementation, so this construction is just for testing.
+                        start := queryCursor(bjoin(
+                                mkNum(1),
+                                serialize.ToBytes(dsS.IndexColumn{Property: "farnsworth"}),
+                                mkNum(200),
+                                serialize.ToBytes(ds.NewKey("Foo", "id", 0, nil))))
+
+                        So(start.String(), ShouldEqual, `gIAAZzFdTeeb3d9zOxsAh8gAAUc32-AGabMAAA==`)
+
+                        end := queryCursor(bjoin(
+                                mkNum(1),
+                                serialize.ToBytes(dsS.IndexColumn{Property: "farnsworth"}),
+                                mkNum(3000),
+                                serialize.ToBytes(ds.NewKey("Foo", "zeta", 0, nil))))
+
+                        q = q.Start(start).End(end)
                         So(q, ShouldNotBeNil)
                         So(q.(*queryImpl).err, ShouldBeNil)
-                        done, err := q.(*queryImpl).valid("", false)
-                        So(done, ShouldBeFalse)
+                        rq, err := q.(*queryImpl).prep("", false)
+                        So(rq, ShouldNotBeNil)
                         So(err, ShouldBeNil)
                 })
 
                 Convey("ensures orders make sense", func() {
                         q := ds.NewQuery("Cool")
                         q = q.Filter("cat =", 19).Filter("bob =", 10).Order("bob").Order("bob")
 
                         Convey("removes dups and equality orders", func() {
                                 q = q.Order("wat")
                                 qi := q.(*queryImpl)
-                                done, err := qi.valid("", false)
-                                So(done, ShouldBeFalse)
+                                rq, err := qi.prep("", false)
                                 So(err, ShouldBeNil)
-                                So(qi.order, ShouldResemble, []dsS.IndexColumn{{Property: "wat"}})
+                                So(rq.suffixFormat, ShouldResemble, []dsS.IndexColumn{{Property: "wat"}})
                         })
 
                         Convey("if we equality-filter on __key__, that's just silly", func() {
-                                q = q.Order("wat")
-                                q := q.Filter("__key__ =", ds.NewKey("Foo", "wat", 0, nil))
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring,
-                                        "query equality filter on __key__ is silly")
+                                q = q.Order("wat").Filter("__key__ =", ds.NewKey("Foo", "wat", 0, nil))
+                                _, err := q.(*queryImpl).prep("", false)
+                                So(err, ShouldErrLike, "query equality filter on __key__ is silly")
                         })
 
                 })
 
-                Convey("inequalities apply immediately", func() {
-                        // NOTE: this is (maybe?) a slight divergence from reality, but it's
-                        // helpful to retain sanity. It's possible that in real-appengine, many
-                        // inequalities count towards the MaxQueryComponents limit (100), where
-                        // in this system we will never have more than 2 (an upper and lower
-                        // bound).
-                })
-
-                Convey("can create bad queries", func() {
-                        q := ds.NewQuery("Foo")
-
-                        Convey("only one inequality", func() {
-                                q = q.Order("bob").Order("wat")
-                                q = q.Filter("bob >", 10).Filter("wat <", 29)
-                                qi := q.(*queryImpl)
-                                _, err := qi.valid("", false)
-                                So(err.Error(), ShouldContainSubstring,
-                                        "inequality filters on multiple properties")
-                        })
-
-                        Convey("bad filter ops", func() {
-                                q := q.Filter("Bob !", "value")
-                                So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "invalid operator \"!\"")
-                        })
-                        Convey("bad filter", func() {
-                                q := q.Filter("Bob", "value")
-                                So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "invalid filter")
-                        })
-                        Convey("bad order", func() {
-                                q := q.Order("+Bob")
-                                So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "invalid order")
-                        })
-                        Convey("empty", func() {
-                                q := q.Order("")
-                                So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "empty order")
-                        })
-                        Convey("OOB limit", func() {
-                                // this is supremely stupid. The SDK uses 'int' which measn we have to
-                                // use it too, but then THEY BOUNDS CHECK IT FOR 32 BITS... *sigh*
-                                if !IntIs32Bits {
-                                        q := q.Limit(MaxInt)
-                                        So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "query limit overflow")
+        })
+}
+
+type queryTest struct {
+        // name is the name of the test case
+        name string
+
+        // q is the input query
+        q dsS.Query
+
+        // err is the error to expect after prepping the query (error, string or nil)
+        err interface{}
+
+        // equivalentQuery is another query which ShouldResemble q. This is useful to
+        // see the effects of redundancy pruning on e.g. filters.
+        equivalentQuery dsS.Query
+}
+
+var nq dsS.Query = &queryImpl{kind: "Foo", ns: "ns"}
+
+type sillyCursor string
+
+func (s sillyCursor) String() string { return string(s) }
+
+var queryTests = []queryTest{
+        {"only one inequality",
+                nq.Order("bob").Order("wat").Filter("bob >", 10).Filter("wat <", 29),
+                "inequality filters on multiple properties", nil},
+
+        {"bad filter ops",
+                nq.Filter("Bob !", "value"),
+                "invalid operator \"!\"", nil},
+
+        {"bad filter",
+                nq.Filter("Bob", "value"),
+                "invalid filter", nil},
+
+        {"bad order",
+                nq.Order("+Bob"),
+                "invalid order", nil},
+
+        {"empty order",
+                nq.Order(""),
+                "empty order", nil},
+
+        {"underflow offset",
+                nq.Offset(-20),
+                "negative query offset", nil},
+
+        {"bad cursors (empty)",
+                nq.Start(queryCursor("")),
+                "invalid cursor", nil},
+
+        {"bad cursors (nil)",
+                nq.Start(queryCursor("")),
+                "invalid cursor", nil},
+
+        {"bad cursors (no key)",
+                nq.End(queryCursor(serialize.ToBytes(dsS.PropertyMap{
+                        "Foo": {prop(100)},
+                }))),
+                "cursor is invalid", nil},
+
+        // TODO(riannucci): exclude cursors which are out-of-bounds with inequality?
+        // I think right now you could have a query for > 10 with a start cursor of 1.
+        {"bad cursors (doesn't include ineq)",
+                nq.Filter("Bob >", 10).Start(queryCursor(serialize.ToBytes(dsS.PropertyMap{
+                        "__key__": {prop(key("something", 1))},
+                        "Foo":     {prop(100)},
+                }))),
+                "cursor is invalid", nil},
+
+        {"bad cursors (doesn't include all orders)",
+                nq.Order("Luci").Order("Charliene").Start(queryCursor(serialize.ToBytes(dsS.PropertyMap{
+                        "__key__": {prop(key("something", 1))},
+                        "Luci":    {prop(100)},
+                }))),
+                "cursor is invalid", nil},
+
+        {"bad cursors (#values != 1)",
+                nq.Order("Luci").End(queryCursor(serialize.ToBytes(dsS.PropertyMap{
+                        "__key__": {prop(key("something", 1))},
+                        "Luci":    {prop(100), prop(101)},
+                }))),
+                "cursor is invalid", nil},
+
+        {"cursor set multiple times",
+                nq.Order("Luci").End(queryCursor(serialize.ToBytes(dsS.PropertyMap{
+                        "__key__": {prop(key("something", 1))},
+                        "Luci":    {prop(100), prop(101)},
+                }))).End(queryCursor(serialize.ToBytes(dsS.PropertyMap{
+                        "__key__": {prop(key("something", 1))},
+                        "Luci":    {prop(100), prop(101)},
+                }))),
+                "multiply defined", nil},
+
+        {"cursor bad type",
+                nq.Order("Luci").End(sillyCursor("I am a banana")),
+                "unknown type", nil},
+
+        {"projecting a keys-only query",
+                nq.Project("hello").KeysOnly(),
+                "cannot project a keysOnly query", nil},
+
+        {"projecting a keys-only query (reverse)",
+                nq.KeysOnly().Project("hello"),
+                "cannot project a keysOnly query", nil},
+
+        {"projecting an empty field",
+                nq.Project("hello", ""),
+                "cannot project on an empty field", nil},
+
+        {"projecting __key__",
+                nq.Project("hello", "__key__"),
+                "cannot project on __key__", nil},
+
+        {"projecting a duplicate",
+                nq.Project("hello", "hello"),
+                "cannot project on the same field twice", nil},
+
+        {"projecting a duplicate (style 2)",
+                nq.Project("hello").Project("hello"),
+                "cannot project on the same field twice", nil},
+
+        {"bad ancestors",
+                nq.Ancestor(key("goop", nil)),
+                dsS.ErrInvalidKey, nil},
+
+        {"nil ancestors",
+                nq.Ancestor(nil),
+                "nil query ancestor", nil},
+
+        {"Bad key filters",
+                nq.Filter("__key__ >", key("goop", nil)),
+                dsS.ErrInvalidKey, nil},
+
+        {"filters for __key__ that aren't keys",
+                nq.Filter("__key__ >", 10),
+                "is not a key", nil},
+
+        {"multiple inequalities",
+                nq.Filter("bob > ", 19).Filter("charlie < ", 20),
+                "inequality filters on multiple properties", nil},
+
+        {"inequality must be first sort order",
+                nq.Filter("bob > ", 19).Order("-charlie"),
+                "first sort order", nil},
+
+        {"inequality must be first sort order (reverse)",
+                nq.Order("-charlie").Filter("bob > ", 19),
+                "first sort order", nil},
+
+        {"equality filter projected field",
+                nq.Project("foo").Filter("foo = ", 10),
+                "cannot project", nil},
+
+        {"equality filter projected field (reverse)",
+                nq.Filter("foo = ", 10).Project("foo"),
+                "cannot project", nil},
+
+        {"kindless with non-__key__ filters",
+                (&queryImpl{ns: "ns"}).Filter("face <", 25.3),
+                "kindless queries can only filter on __key__", nil},
+
+        {"kindless with non-__key__ orders",
+                (&queryImpl{ns: "ns"}).Order("face"),
+                "invalid order for kindless query", nil},
+
+        {"kindless with descending-__key__ order",
+                (&queryImpl{ns: "ns"}).Order("-__key__"),
+                "invalid order for kindless query", nil},
+
+        {"bad namespace",
+                (&queryImpl{kind: "something", ns: "sup"}).Order("__key__"),
+                "Namespace mismatched", nil},
+
+        {"distinct non-projection",
+                nq.Distinct().Filter("marla >", 1),
+                "only makes sense on projection queries", nil},
+
+        {"chained errors return the first",
+                nq.Ancestor(nil).Filter("hello", "wurld").Order(""),
+                "nil query ancestor", nil},
+
+        {"bad ancestor namespace",
+                (&queryImpl{ns: "nerd"}).Ancestor(key("something", "correct")),
+                "bad namespace", nil},
+
+        {"multiple ancestors",
+                nq.Ancestor(key("something", "correct")).Ancestor(key("something", "else")),
+                "more than one ancestor", nil},
+
+        {"filter with illegal type",
+                nq.Filter("something =", complex(1, 2)),
+                "bad type complex", nil},
+
+        {"sort orders used for equality are ignored",
+                nq.Order("a").Order("b").Order("c").Filter("b =", 2),
+                nil,
+                nq.Order("a").Order("c").Filter("b =", 2)},
+
+        {"sort orders used for equality are ignored (reversed)",
+                nq.Filter("b =", 2).Order("a").Order("b").Order("c"),
+                nil,
+                nq.Order("a").Order("c").Filter("b =", 2)},
+
+        {"duplicate orders are ignored",
+                nq.Order("a").Order("a").Order("a"),
+                nil,
+                nq.Order("a")},
+
+        {"overconstrained inequality (>= v <)",
+                nq.Filter("bob >=", 10).Filter("bob <", 10),
+                "done", nil},
+
+        {"overconstrained inequality (> v <)",
+                nq.Filter("bob >", 10).Filter("bob <", 10),
+                "done", nil},
+
+        {"overconstrained inequality (> v <=)",
+                nq.Filter("bob >", 10).Filter("bob <=", 10),
+                "done", nil},
+
+        {"silly inequality (=> v <=)",
+                nq.Filter("bob >=", 10).Filter("bob <=", 10),
+                nil,
+                nil},
+}
+
+func init() {
+        // this is supremely stupid. The SDK uses 'int' which measn we have to
+        // use it too, but then THEY BOUNDS CHECK IT FOR 32 BITS... *sigh*
+        if !IntIs32Bits {
+                queryTests = append(queryTests, []queryTest{
+                        {"OOB limit (32 bit)",
+                                nq.Limit(MaxInt),
+                                "query limit overflow", nil},
+
+                        {"OOB offset (32 bit)",
+                                nq.Offset(MaxInt),
+                                "query offset overflow", nil},
+                }...)
+        }
+}
+
+func TestBadQueries(t *testing.T) {
+        t.Parallel()
+
+        Convey("can create bad queries", t, func() {
+                for _, tc := range queryTests {
+                        Convey(tc.name, func() {
+                                _, err := tc.q.(*queryImpl).prep("ns", false)
+                                So(err, ShouldErrLike, tc.err)
+
+                                if tc.equivalentQuery != nil {
+                                        So(tc.q, ShouldResemble, tc.equivalentQuery)
                                 }
                         })
-                        Convey("underflow offset", func() {
-                                q := q.Offset(-29)
-                                So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "negative query offset")
-                        })
-                        Convey("OOB offset", func() {
-                                if !IntIs32Bits {
-                                        q := q.Offset(MaxInt)
-                                        So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "query offset overflow")
-                                }
-                        })
-                        Convey("Bad cursors", func() {
-                                q := q.Start(queryCursor("")).End(queryCursor(""))
-                                So(q.(*queryImpl).err.Error(), ShouldContainSubstring, "invalid cursor")
-                        })
-                        Convey("Bad ancestors", func() {
-                                q := q.Ancestor(ds.NewKey("Goop", "wat", 10, nil))
-                                So(q, ShouldNotBeNil)
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err, ShouldEqual, dsS.ErrInvalidKey)
-                        })
-                        Convey("nil ancestors", func() {
-                                _, err := q.Ancestor(nil).(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring, "nil query ancestor")
-                        })
-                        Convey("Bad key filters", func() {
-                                q := q.Filter("__key__ >", ds.NewKey("Goop", "wat", 10, nil))
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err, ShouldEqual, dsS.ErrInvalidKey)
-                        })
-                        Convey("non-ancestor queries in a transaction", func() {
-                                _, err := q.(*queryImpl).valid("", true)
-                                So(err.Error(), ShouldContainSubstring, "Only ancestor queries")
-                        })
-                        Convey("absurd numbers of filters are prohibited", func() {
-                                q := q.Ancestor(ds.NewKey("thing", "wat", 0, nil))
-                                for i := 0; i < 100; i++ {
-                                        q = q.Filter("something =", i)
-                                }
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring, "query is too large")
-                        })
-                        Convey("filters for __key__ that aren't keys", func() {
-                                q := q.Filter("__key__ > ", 10)
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring, "is not a key")
-                        })
-                        Convey("multiple inequalities", func() {
-                                q := q.Filter("bob > ", 19).Filter("charlie < ", 20)
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring,
-                                        "inequality filters on multiple properties")
-                        })
-                        Convey("bad sort orders", func() {
-                                q := q.Filter("bob > ", 19).Order("-charlie")
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring, "first sort order")
-                        })
-                        Convey("kindless with non-__key__ filters", func() {
-                                q := ds.NewQuery("").Filter("face <", 25.3)
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring,
-                                        "kindless queries can only filter on __key__")
-                        })
-                        Convey("kindless with non-__key__ orders", func() {
-                                q := ds.NewQuery("").Order("face")
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring,
-                                        "invalid order for kindless query")
-                        })
-                        Convey("kindless with decending-__key__ orders", func() {
-                                q := ds.NewQuery("").Order("-__key__")
-                                _, err := q.(*queryImpl).valid("", false)
-                                So(err.Error(), ShouldContainSubstring,
-                                        "invalid order for kindless query")
-                        })
-                })
-
+                }
+
+                Convey("non-ancestor queries in a transaction", func() {
+                        _, err := nq.(*queryImpl).prep("ns", true)
+                        So(err, ShouldErrLike, "Only ancestor queries")
+                })
+
+                Convey("absurd numbers of filters are prohibited", func() {
+                        q := nq.Ancestor(key("thing", "wat"))
+                        for i := 0; i < 100; i++ {
+                                q = q.Filter("something =", i)
+                        }
+                        //So(q.(*queryImpl).numComponents(), ShouldEqual, 101)
+                        _, err := q.(*queryImpl).prep("ns", false)
+                        So(err, ShouldErrLike, "query is too large")
+                })
         })
 }
+
+func TestQueryPreparation(t *testing.T) {
+        t.Parallel()
+
+        Convey("Test Query.prep", t, func() {
+                Convey("ancestor is serialized", func() {
+                        rq, err := nq.Ancestor(key("hi", 1)).(*queryImpl).prep("ns", false)
+                        So(err, ShouldBeNil)
+                        So(rq.ancestor, ShouldResemble, []byte{0, 1, 0x69, 0x35, 0x40, 1, 0x80, 0x80, 0})
+                })
+
+                Convey("inequality property adjusts start/end", func() {
+
+                })
+        })
+}