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..ccf466407d35ae10d1c475b7eb5ff5ed73b784cf 100644
--- a/impl/memory/datastore_query_test.go
+++ b/impl/memory/datastore_query_test.go
@@ -5,10 +5,14 @@
 package memory
 
 import (
+	"bytes"
 	"math"
 	"testing"
 
 	dsS "github.com/luci/gae/service/datastore"
+	"github.com/luci/gae/service/datastore/serialize"
+	"github.com/luci/luci-go/common/cmpbin"
+	. "github.com/luci/luci-go/common/testing/assertions"
 	. "github.com/smartystreets/goconvey/convey"
 	"golang.org/x/net/context"
 )
@@ -26,12 +30,32 @@ 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(2),
+				serialize.ToBytes(dsS.IndexColumn{Property: "farnsworth"}),
+				serialize.ToBytes(dsS.IndexColumn{Property: "__key__"}),
+				serialize.ToBytes(prop(200)),
+				serialize.ToBytes(prop(ds.NewKey("Foo", "id", 0, nil)))))
+
+			So(start.String(), ShouldEqual,
+				`gYAAZzFdTeeb3d9zOxsAAF-v221Xy32_AIGHyIkAAUc32-AGabMAAA==`)
+
+			end := queryCursor(bjoin(
+				mkNum(2),
+				serialize.ToBytes(dsS.IndexColumn{Property: "farnsworth"}),
+				serialize.ToBytes(dsS.IndexColumn{Property: "__key__"}),
+				serialize.ToBytes(prop(3000)),
+				serialize.ToBytes(prop(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).reduce("", false)
+			So(rq, ShouldNotBeNil)
 			So(err, ShouldBeNil)
 		})
 
@@ -42,142 +66,349 @@ 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)
+				So(qi.err, ShouldBeNil)
+				rq, err := qi.reduce("", false)
 				So(err, ShouldBeNil)
-				So(qi.order, ShouldResemble, []dsS.IndexColumn{{Property: "wat"}})
+				So(rq.suffixFormat, ShouldResemble, []dsS.IndexColumn{
+					{Property: "wat"}, {Property: "__key__"}})
 			})
 
 			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).reduce("", 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
+}
+
+type sillyCursor string
+
+func (s sillyCursor) String() string { return string(s) }
+
+func curs(pairs ...interface{}) queryCursor {
+	if len(pairs)%2 != 0 {
+		panic("curs() takes only even pairs")
+	}
+	pre := &bytes.Buffer{}
+	cmpbin.WriteUint(pre, uint64(len(pairs)/2))
+	post := serialize.Invertible(&bytes.Buffer{})
+	for i := 0; i < len(pairs); i += 2 {
+		k, v := pairs[i].(string), pairs[i+1]
+
+		col := dsS.IndexColumn{Property: k}
+
+		post.SetInvert(false)
+		if k[0] == '-' {
+			post.SetInvert(false)
+			col.Property = k[1:]
+			col.Direction = dsS.DESCENDING
+		}
+		serialize.WriteIndexColumn(pre, col)
+		serialize.WriteProperty(post, serialize.WithoutContext, prop(v))
+	}
+	return queryCursor(bjoin(pre.Bytes(), post.Bytes()))
+}
+
+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(curs("Foo", 100)),
+		"invalid cursor", 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(
+			curs("Foo", 100, "__key__", key("something", 1)),
+		),
+		"start cursor is invalid", nil},
+
+	{"bad cursors (doesn't include all orders)",
+		nq().Order("Luci").Order("Charliene").Start(
+			curs("Luci", 100, "__key__", key("something", 1)),
+		),
+		"start cursor is invalid", nil},
+
+	{"cursor set multiple times",
+		nq().Order("Luci").End(
+			curs("Luci", 100, "__key__", key("something", 1)),
+		).End(
+			curs("Luci", 100, "__key__", key("something", 1)),
+		),
+		"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",
+		nq("").Filter("face <", 25.3),
+		"kindless queries can only filter on __key__", nil},
+
+	{"kindless with non-__key__ orders",
+		nq("").Order("face"),
+		"invalid order for kindless query", nil},
+
+	{"kindless with descending-__key__ order",
+		nq("").Order("-__key__"),
+		"invalid order for kindless query", nil},
+
+	{"bad namespace",
+		nq("something", "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",
+		nq("", "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},
+
+	{"Filtering on a reserved property is forbidden",
+		nq().Filter("__special__ >=", 10),
+		"filter on reserved property",
+		nil},
+
+	{"oob key filters with ancestor (highside)",
+		nq().Ancestor(key("Hello", 10)).Filter("__key__ <", key("Hello", 9)),
+		"__key__ inequality",
+		nil},
+
+	{"oob key filters with ancestor (lowside)",
+		nq().Ancestor(key("Hello", 10)).Filter("__key__ >", key("Hello", 11)),
+		"__key__ inequality",
+		nil},
+
+	{"in-bound key filters with ancestor OK",
+		nq().Ancestor(key("Hello", 10)).Filter("__key__ <", key("Something", "hi", key("Hello", 10))),
+		nil,
+		nil},
+
+	{"projection elements get filled in",
+		nq().Project("Foo", "Bar").Order("-Bar"),
+		nil,
+		nq().Project("Foo", "Bar").Order("-Bar").Order("Foo")},
+
+	{"cursors get smooshed into the inquality range",
+		(nq().Filter("Foo >", 3).Filter("Foo <", 10).
+			Start(curs("Foo", 2, "__key__", key("Something", 1))).
+			End(curs("Foo", 20, "__key__", key("Something", 20)))),
+		nil,
+		nq().Filter("Foo >", 3).Filter("Foo <", 10)},
+
+	{"cursors could cause the whole query to be useless",
+		(nq().Filter("Foo >", 3).Filter("Foo <", 10).
+			Start(curs("Foo", 200, "__key__", key("Something", 1))).
+			End(curs("Foo", 1, "__key__", key("Something", 20)))),
+		errQueryDone,
+		nil},
+
+	{"query without anything is fine",
+		nq(),
+		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 TestQueries(t *testing.T) {
+	t.Parallel()
+
+	Convey("queries have tons of condition checking", t, func() {
+		for _, tc := range queryTests {
+			Convey(tc.name, func() {
+				rq, err := tc.q.(*queryImpl).reduce("ns", false)
+				So(err, ShouldErrLike, tc.err)
+
+				if tc.equivalentQuery != nil {
+					rq2, err := tc.equivalentQuery.(*queryImpl).reduce("ns", false)
+					So(err, ShouldBeNil)
+					So(rq, ShouldResemble, rq2)
 				}
-				_, 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).reduce("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).reduce("ns", false)
+			So(err, ShouldErrLike, "query is too large")
+		})
 	})
 }