Add initial Query generation, correctness checking and index generation.

Add initial Query generation, correctness checking and index generation.

The ability to execute a query will come in a following CL.

R=maruel@chromium.org, vadimsh@chromium.org
BUG=

Committed: https://chromium.googlesource.com/infra/infra/+/a58ad0bd769b5e26e6a3abcac1583c83bbd4e8dc

[iannucci, 2015-05-30 23:37:01]

On 2015/05/30 23:35:38, iannucci wrote:

I'll be adding some additional tests (see TODO at bottom of plist_test.go) in a
subsequent patch, but I don't expect it to change the behavior or implementation
much.

[iannucci, 2015-05-31 18:42:58]

tests added

[M-A Ruel, 2015-05-31 23:03:16]

Very lightly reviewed.

lgtm with nits

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
File go/src/infra/gae/libs/wrapper/memory/README.md (right):

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/README.md:91: // increasing version number
(aka "timestamp").
http://googlecloudplatform.blogspot.ca/2015/05/Got-a-second-A-leap-second-tha...

and NTP in general. In swarming, what happens in these cases is slight
reordering of the task priority. In Swarming explicitly doesn't do explicit FIFO
under millisecond level by injecting random bits in the ordering.

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
File go/src/infra/gae/libs/wrapper/memory/binutils.go (right):

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/binutils.go:74: funnybase.WriteUint(buf,
uint64(t.Unix())*1e6+uint64(t.Nanosecond()/1e3))
Why silently strip the resolution to µs?

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
File go/src/infra/gae/libs/wrapper/memory/datastore.go (right):

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/datastore.go:125: rq =
rq.normalize().checkCorrectness(d.ns, false)
return &queryIterImp{q.(*queryImpl).normalize().checkCorrectness(d.ns, false)}

or you fine this too intense?

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
File go/src/infra/gae/libs/wrapper/memory/datastore_query.go (right):

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:38: func (qsb qSort)
WriteBinary(buf *bytes.Buffer) {
s/qsb/q/ ?

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:57: type qIdx struct {
I think it's excessive shortening, qIndex would be clearer.

I'd probably name it compositeIndex, but I'm that crazy.

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:79: func (i *qIdx)
WriteBinary(buf *bytes.Buffer) {
All these funnybase stuff would have been much better to be using protobuf. I
hope you plan to rip this out eventually.

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:141: i.sortby =
make([]qSort, numSorts)
You should protect against large numbers.

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
File go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go (right):

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go:17: wg.Add(2)
Please do it right above the go statements, e.g. move at line 29

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go:58: 
remove

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go:60: wg.Wait()
In theory if you synchronize with channels you don't need the WaitGroup.

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
File go/src/infra/gae/libs/wrapper/memory/gkvlite_utils_test.go (right):

https://codereview.chromium.org/1160253002/diff/60001/go/src/infra/gae/libs/w...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils_test.go:13: // key, old, new
Then use these names. The goal is not to make the code opaque.

[iannucci, 2015-05-31 23:31:34]

PTAL + info

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
File go/src/infra/gae/libs/wrapper/memory/README.md (right):

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/README.md:91: // increasing version number
(aka "timestamp").
Yeah, that's not what I'm referring to at all :). The entity group
metadataversion is a UTC timestamp on appspot.com (go load the entity group
version on any appspot instance and then interpret the number as a unix
timestamp). Presumably, it's synchronized by something other than NTP. I'll let
you guess how.

For our purposes here, it would just be an incrementing number because this
isn't a distributed system.

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
File go/src/infra/gae/libs/wrapper/memory/binutils.go (right):

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/binutils.go:74: funnybase.WriteUint(buf,
uint64(t.Unix())*1e6+uint64(t.Nanosecond()/1e3))
On 2015/05/31 23:03:15, M-A Ruel wrote:
> Why silently strip the resolution to µs?

Oh, you wanted nanosecond precision? Don't use a time.Time and store the fields
yourself :) (go check the SDK implementation if you don't believe me). Timezone
is also silently dropped too.

I'll add a comment.

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
File go/src/infra/gae/libs/wrapper/memory/datastore.go (right):

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/datastore.go:125: rq =
rq.normalize().checkCorrectness(d.ns, false)
On 2015/05/31 23:03:15, M-A Ruel wrote:
> return &queryIterImp{q.(*queryImpl).normalize().checkCorrectness(d.ns, false)}
> 
> or you fine this too intense?

I think I had that originally and it seemed too line-noisey :)

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
File go/src/infra/gae/libs/wrapper/memory/datastore_query.go (right):

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:38: func (qsb qSort)
WriteBinary(buf *bytes.Buffer) {
On 2015/05/31 23:03:15, M-A Ruel wrote:
> s/qsb/q/ ?

er, yeah... these used to have longer names, but I truncated them to make the
tests more readable. Then I introduced shortcut methods, so it doesn't matter
any more :)

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:57: type qIdx struct {
On 2015/05/31 23:03:15, M-A Ruel wrote:
> I think it's excessive shortening, qIndex would be clearer.
> 
> I'd probably name it compositeIndex, but I'm that crazy.

it also encodes non-composite indexes (turns out they're all the same
implementation :)). Renamed to qIndex.

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:79: func (i *qIdx)
WriteBinary(buf *bytes.Buffer) {
On 2015/05/31 23:03:15, M-A Ruel wrote:
> All these funnybase stuff would have been much better to be using protobuf. I
> hope you plan to rip this out eventually.

bzzt, wrong :D

protobufs don't have a stable, sortable encoding (and their integer encoding in
general is non-sortable, unless you use fixed-width everywhere, and even then,
you need tons of extra type-flag fields because the wire-types don't map
correctly to the datastore value types). This shit is here to stay because I
need the data emitted here to be orderable with bytes.Compare.

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/datastore_query.go:141: i.sortby =
make([]qSort, numSorts)
On 2015/05/31 23:03:15, M-A Ruel wrote:
> You should protect against large numbers.

yeah, good catch. I do this for bytes. I'll review all these make()'s

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
File go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go (right):

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go:17: wg.Add(2)
On 2015/05/31 23:03:15, M-A Ruel wrote:
> Please do it right above the go statements, e.g. move at line 29

Done.

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go:58: 
On 2015/05/31 23:03:16, M-A Ruel wrote:
> remove

Done.

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils.go:60: wg.Wait()
On 2015/05/31 23:03:15, M-A Ruel wrote:
> In theory if you synchronize with channels you don't need the WaitGroup.

yeah, but doesn't the WaitGroup use channels anyway? I don't see any reason to
reimplement it...

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
File go/src/infra/gae/libs/wrapper/memory/gkvlite_utils_test.go (right):

https://chromiumcodereview.appspot.com/1160253002/diff/60001/go/src/infra/gae...
go/src/infra/gae/libs/wrapper/memory/gkvlite_utils_test.go:13: // key, old, new
On 2015/05/31 23:03:16, M-A Ruel wrote:
> Then use these names. The goal is not to make the code opaque.

Done.

[iannucci, 2015-05-31 23:44:17]

The CQ bit was checked by iannucci@chromium.org

[iannucci, 2015-05-31 23:44:17]

The patchset sent to the CQ was uploaded after l-g-t-m from maruel@chromium.org
Link to the patchset: https://chromiumcodereview.appspot.com/1160253002/#ps80001
(title: "address comments and stuff")

[commit-bot: I haz the power, 2015-05-31 23:44:29]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1160253002/80001

[iannucci, 2015-05-31 23:44:41]

committing so that I can get a stable base for the query-execution CL. We can do
followups if needed.

[commit-bot: I haz the power, 2015-05-31 23:47:08]

Committed patchset #5 (id:80001) as
https://chromium.googlesource.com/infra/infra/+/a58ad0bd769b5e26e6a3abcac1583...