impl/memory: Implement Queries

impl/memory/datastore_query_test.go

Index: impl/memory/datastore_query_test.go
diff --git a/impl/memory/datastore_query_test.go b/impl/memory/datastore_query_test.go
index 55cb0e547a7f10ecf0c2181355c65975448e5838..1805a32ed010499e8f7b82b83cda253e0658b094 100644
--- a/impl/memory/datastore_query_test.go
+++ b/impl/memory/datastore_query_test.go
@@ -9,6 +9,8 @@ import (
 	"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"
 )
@@ -26,12 +28,29 @@ func TestDatastoreQueries(t *testing.T) {
 		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)
 		})
 
@@ -42,142 +61,308 @@ func TestDatastoreQueries(t *testing.T) {
 			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")
+type queryTest struct {
+	// name is the name of the test case
+	name string
 
-			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")
-			})
+	// q is the input query
+	q dsS.Query
 
-			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")
-				}
-			})
-			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 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)
 				}
-				_, 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() {
+
+		})
 	})
 }