Upgrade to 0.12

[github/fretlink/terraform-provider-statuscake.git] / vendor / google.golang.org / appengine / datastore / query.go

// Copyright 2011 Google Inc. All rights reserved.
// Use of this source code is governed by the Apache 2.0
// license that can be found in the LICENSE file.

package datastore

import (
        "encoding/base64"
        "errors"
        "fmt"
        "math"
        "reflect"
        "strings"

        "github.com/golang/protobuf/proto"
        "golang.org/x/net/context"

        "google.golang.org/appengine/internal"
        pb "google.golang.org/appengine/internal/datastore"
)

type operator int

const (
        lessThan operator = iota
        lessEq
        equal
        greaterEq
        greaterThan
)

var operatorToProto = map[operator]*pb.Query_Filter_Operator{
        lessThan:    pb.Query_Filter_LESS_THAN.Enum(),
        lessEq:      pb.Query_Filter_LESS_THAN_OR_EQUAL.Enum(),
        equal:       pb.Query_Filter_EQUAL.Enum(),
        greaterEq:   pb.Query_Filter_GREATER_THAN_OR_EQUAL.Enum(),
        greaterThan: pb.Query_Filter_GREATER_THAN.Enum(),
}

// filter is a conditional filter on query results.
type filter struct {
        FieldName string
        Op        operator
        Value     interface{}
}

type sortDirection int

const (
        ascending sortDirection = iota
        descending
)

var sortDirectionToProto = map[sortDirection]*pb.Query_Order_Direction{
        ascending:  pb.Query_Order_ASCENDING.Enum(),
        descending: pb.Query_Order_DESCENDING.Enum(),
}

// order is a sort order on query results.
type order struct {
        FieldName string
        Direction sortDirection
}

// NewQuery creates a new Query for a specific entity kind.
//
// An empty kind means to return all entities, including entities created and
// managed by other App Engine features, and is called a kindless query.
// Kindless queries cannot include filters or sort orders on property values.
func NewQuery(kind string) *Query {
        return &Query{
                kind:  kind,
                limit: -1,
        }
}

// Query represents a datastore query.
type Query struct {
        kind       string
        ancestor   *Key
        filter     []filter
        order      []order
        projection []string

        distinct bool
        keysOnly bool
        eventual bool
        limit    int32
        offset   int32
        count    int32
        start    *pb.CompiledCursor
        end      *pb.CompiledCursor

        err error
}

func (q *Query) clone() *Query {
        x := *q
        // Copy the contents of the slice-typed fields to a new backing store.
        if len(q.filter) > 0 {
                x.filter = make([]filter, len(q.filter))
                copy(x.filter, q.filter)
        }
        if len(q.order) > 0 {
                x.order = make([]order, len(q.order))
                copy(x.order, q.order)
        }
        return &x
}

// Ancestor returns a derivative query with an ancestor filter.
// The ancestor should not be nil.
func (q *Query) Ancestor(ancestor *Key) *Query {
        q = q.clone()
        if ancestor == nil {
                q.err = errors.New("datastore: nil query ancestor")
                return q
        }
        q.ancestor = ancestor
        return q
}

// EventualConsistency returns a derivative query that returns eventually
// consistent results.
// It only has an effect on ancestor queries.
func (q *Query) EventualConsistency() *Query {
        q = q.clone()
        q.eventual = true
        return q
}

// Filter returns a derivative query with a field-based filter.
// The filterStr argument must be a field name followed by optional space,
// followed by an operator, one of ">", "<", ">=", "<=", or "=".
// Fields are compared against the provided value using the operator.
// Multiple filters are AND'ed together.
func (q *Query) Filter(filterStr string, value interface{}) *Query {
        q = q.clone()
        filterStr = strings.TrimSpace(filterStr)
        if len(filterStr) < 1 {
                q.err = errors.New("datastore: invalid filter: " + filterStr)
                return q
        }
        f := filter{
                FieldName: strings.TrimRight(filterStr, " ><=!"),
                Value:     value,
        }
        switch op := strings.TrimSpace(filterStr[len(f.FieldName):]); op {
        case "<=":
                f.Op = lessEq
        case ">=":
                f.Op = greaterEq
        case "<":
                f.Op = lessThan
        case ">":
                f.Op = greaterThan
        case "=":
                f.Op = equal
        default:
                q.err = fmt.Errorf("datastore: invalid operator %q in filter %q", op, filterStr)
                return q
        }
        q.filter = append(q.filter, f)
        return q
}

// Order returns a derivative query with a field-based sort order. Orders are
// applied in the order they are added. The default order is ascending; to sort
// in descending order prefix the fieldName with a minus sign (-).
func (q *Query) Order(fieldName string) *Query {
        q = q.clone()
        fieldName = strings.TrimSpace(fieldName)
        o := order{
                Direction: ascending,
                FieldName: fieldName,
        }
        if strings.HasPrefix(fieldName, "-") {
                o.Direction = descending
                o.FieldName = strings.TrimSpace(fieldName[1:])
        } else if strings.HasPrefix(fieldName, "+") {
                q.err = fmt.Errorf("datastore: invalid order: %q", fieldName)
                return q
        }
        if len(o.FieldName) == 0 {
                q.err = errors.New("datastore: empty order")
                return q
        }
        q.order = append(q.order, o)
        return q
}

// Project returns a derivative query that yields only the given fields. It
// cannot be used with KeysOnly.
func (q *Query) Project(fieldNames ...string) *Query {
        q = q.clone()
        q.projection = append([]string(nil), fieldNames...)
        return q
}

// Distinct returns a derivative query that yields de-duplicated entities with
// respect to the set of projected fields. It is only used for projection
// queries.
func (q *Query) Distinct() *Query {
        q = q.clone()
        q.distinct = true
        return q
}

// KeysOnly returns a derivative query that yields only keys, not keys and
// entities. It cannot be used with projection queries.
func (q *Query) KeysOnly() *Query {
        q = q.clone()
        q.keysOnly = true
        return q
}

// Limit returns a derivative query that has a limit on the number of results
// returned. A negative value means unlimited.
func (q *Query) Limit(limit int) *Query {
        q = q.clone()
        if limit < math.MinInt32 || limit > math.MaxInt32 {
                q.err = errors.New("datastore: query limit overflow")
                return q
        }
        q.limit = int32(limit)
        return q
}

// Offset returns a derivative query that has an offset of how many keys to
// skip over before returning results. A negative value is invalid.
func (q *Query) Offset(offset int) *Query {
        q = q.clone()
        if offset < 0 {
                q.err = errors.New("datastore: negative query offset")
                return q
        }
        if offset > math.MaxInt32 {
                q.err = errors.New("datastore: query offset overflow")
                return q
        }
        q.offset = int32(offset)
        return q
}

// BatchSize returns a derivative query to fetch the supplied number of results
// at once. This value should be greater than zero, and equal to or less than
// the Limit.
func (q *Query) BatchSize(size int) *Query {
        q = q.clone()
        if size <= 0 || size > math.MaxInt32 {
                q.err = errors.New("datastore: query batch size overflow")
                return q
        }
        q.count = int32(size)
        return q
}

// Start returns a derivative query with the given start point.
func (q *Query) Start(c Cursor) *Query {
        q = q.clone()
        if c.cc == nil {
                q.err = errors.New("datastore: invalid cursor")
                return q
        }
        q.start = c.cc
        return q
}

// End returns a derivative query with the given end point.
func (q *Query) End(c Cursor) *Query {
        q = q.clone()
        if c.cc == nil {
                q.err = errors.New("datastore: invalid cursor")
                return q
        }
        q.end = c.cc
        return q
}

// toProto converts the query to a protocol buffer.
func (q *Query) toProto(dst *pb.Query, appID string) error {
        if len(q.projection) != 0 && q.keysOnly {
                return errors.New("datastore: query cannot both project and be keys-only")
        }
        dst.Reset()
        dst.App = proto.String(appID)
        if q.kind != "" {
                dst.Kind = proto.String(q.kind)
        }
        if q.ancestor != nil {
                dst.Ancestor = keyToProto(appID, q.ancestor)
                if q.eventual {
                        dst.Strong = proto.Bool(false)
                }
        }
        if q.projection != nil {
                dst.PropertyName = q.projection
                if q.distinct {
                        dst.GroupByPropertyName = q.projection
                }
        }
        if q.keysOnly {
                dst.KeysOnly = proto.Bool(true)
                dst.RequirePerfectPlan = proto.Bool(true)
        }
        for _, qf := range q.filter {
                if qf.FieldName == "" {
                        return errors.New("datastore: empty query filter field name")
                }
                p, errStr := valueToProto(appID, qf.FieldName, reflect.ValueOf(qf.Value), false)
                if errStr != "" {
                        return errors.New("datastore: bad query filter value type: " + errStr)
                }
                xf := &pb.Query_Filter{
                        Op:       operatorToProto[qf.Op],
                        Property: []*pb.Property{p},
                }
                if xf.Op == nil {
                        return errors.New("datastore: unknown query filter operator")
                }
                dst.Filter = append(dst.Filter, xf)
        }
        for _, qo := range q.order {
                if qo.FieldName == "" {
                        return errors.New("datastore: empty query order field name")
                }
                xo := &pb.Query_Order{
                        Property:  proto.String(qo.FieldName),
                        Direction: sortDirectionToProto[qo.Direction],
                }
                if xo.Direction == nil {
                        return errors.New("datastore: unknown query order direction")
                }
                dst.Order = append(dst.Order, xo)
        }
        if q.limit >= 0 {
                dst.Limit = proto.Int32(q.limit)
        }
        if q.offset != 0 {
                dst.Offset = proto.Int32(q.offset)
        }
        if q.count != 0 {
                dst.Count = proto.Int32(q.count)
        }
        dst.CompiledCursor = q.start
        dst.EndCompiledCursor = q.end
        dst.Compile = proto.Bool(true)
        return nil
}

// Count returns the number of results for the query.
//
// The running time and number of API calls made by Count scale linearly with
// the sum of the query's offset and limit. Unless the result count is
// expected to be small, it is best to specify a limit; otherwise Count will
// continue until it finishes counting or the provided context expires.
func (q *Query) Count(c context.Context) (int, error) {
        // Check that the query is well-formed.
        if q.err != nil {
                return 0, q.err
        }

        // Run a copy of the query, with keysOnly true (if we're not a projection,
        // since the two are incompatible), and an adjusted offset. We also set the
        // limit to zero, as we don't want any actual entity data, just the number
        // of skipped results.
        newQ := q.clone()
        newQ.keysOnly = len(newQ.projection) == 0
        newQ.limit = 0
        if q.limit < 0 {
                // If the original query was unlimited, set the new query's offset to maximum.
                newQ.offset = math.MaxInt32
        } else {
                newQ.offset = q.offset + q.limit
                if newQ.offset < 0 {
                        // Do the best we can, in the presence of overflow.
                        newQ.offset = math.MaxInt32
                }
        }
        req := &pb.Query{}
        if err := newQ.toProto(req, internal.FullyQualifiedAppID(c)); err != nil {
                return 0, err
        }
        res := &pb.QueryResult{}
        if err := internal.Call(c, "datastore_v3", "RunQuery", req, res); err != nil {
                return 0, err
        }

        // n is the count we will return. For example, suppose that our original
        // query had an offset of 4 and a limit of 2008: the count will be 2008,
        // provided that there are at least 2012 matching entities. However, the
        // RPCs will only skip 1000 results at a time. The RPC sequence is:
        //   call RunQuery with (offset, limit) = (2012, 0)  // 2012 == newQ.offset
        //   response has (skippedResults, moreResults) = (1000, true)
        //   n += 1000  // n == 1000
        //   call Next     with (offset, limit) = (1012, 0)  // 1012 == newQ.offset - n
        //   response has (skippedResults, moreResults) = (1000, true)
        //   n += 1000  // n == 2000
        //   call Next     with (offset, limit) = (12, 0)    // 12 == newQ.offset - n
        //   response has (skippedResults, moreResults) = (12, false)
        //   n += 12    // n == 2012
        //   // exit the loop
        //   n -= 4     // n == 2008
        var n int32
        for {
                // The QueryResult should have no actual entity data, just skipped results.
                if len(res.Result) != 0 {
                        return 0, errors.New("datastore: internal error: Count request returned too much data")
                }
                n += res.GetSkippedResults()
                if !res.GetMoreResults() {
                        break
                }
                if err := callNext(c, res, newQ.offset-n, q.count); err != nil {
                        return 0, err
                }
        }
        n -= q.offset
        if n < 0 {
                // If the offset was greater than the number of matching entities,
                // return 0 instead of negative.
                n = 0
        }
        return int(n), nil
}

// callNext issues a datastore_v3/Next RPC to advance a cursor, such as that
// returned by a query with more results.
func callNext(c context.Context, res *pb.QueryResult, offset, count int32) error {
        if res.Cursor == nil {
                return errors.New("datastore: internal error: server did not return a cursor")
        }
        req := &pb.NextRequest{
                Cursor: res.Cursor,
        }
        if count >= 0 {
                req.Count = proto.Int32(count)
        }
        if offset != 0 {
                req.Offset = proto.Int32(offset)
        }
        if res.CompiledCursor != nil {
                req.Compile = proto.Bool(true)
        }
        res.Reset()
        return internal.Call(c, "datastore_v3", "Next", req, res)
}

// GetAll runs the query in the given context and returns all keys that match
// that query, as well as appending the values to dst.
//
// dst must have type *[]S or *[]*S or *[]P, for some struct type S or some non-
// interface, non-pointer type P such that P or *P implements PropertyLoadSaver.
//
// As a special case, *PropertyList is an invalid type for dst, even though a
// PropertyList is a slice of structs. It is treated as invalid to avoid being
// mistakenly passed when *[]PropertyList was intended.
//
// The keys returned by GetAll will be in a 1-1 correspondence with the entities
// added to dst.
//
// If q is a ``keys-only'' query, GetAll ignores dst and only returns the keys.
//
// The running time and number of API calls made by GetAll scale linearly with
// the sum of the query's offset and limit. Unless the result count is
// expected to be small, it is best to specify a limit; otherwise GetAll will
// continue until it finishes collecting results or the provided context
// expires.
func (q *Query) GetAll(c context.Context, dst interface{}) ([]*Key, error) {
        var (
                dv               reflect.Value
                mat              multiArgType
                elemType         reflect.Type
                errFieldMismatch error
        )
        if !q.keysOnly {
                dv = reflect.ValueOf(dst)
                if dv.Kind() != reflect.Ptr || dv.IsNil() {
                        return nil, ErrInvalidEntityType
                }
                dv = dv.Elem()
                mat, elemType = checkMultiArg(dv)
                if mat == multiArgTypeInvalid || mat == multiArgTypeInterface {
                        return nil, ErrInvalidEntityType
                }
        }

        var keys []*Key
        for t := q.Run(c); ; {
                k, e, err := t.next()
                if err == Done {
                        break
                }
                if err != nil {
                        return keys, err
                }
                if !q.keysOnly {
                        ev := reflect.New(elemType)
                        if elemType.Kind() == reflect.Map {
                                // This is a special case. The zero values of a map type are
                                // not immediately useful; they have to be make'd.
                                //
                                // Funcs and channels are similar, in that a zero value is not useful,
                                // but even a freshly make'd channel isn't useful: there's no fixed
                                // channel buffer size that is always going to be large enough, and
                                // there's no goroutine to drain the other end. Theoretically, these
                                // types could be supported, for example by sniffing for a constructor
                                // method or requiring prior registration, but for now it's not a
                                // frequent enough concern to be worth it. Programmers can work around
                                // it by explicitly using Iterator.Next instead of the Query.GetAll
                                // convenience method.
                                x := reflect.MakeMap(elemType)
                                ev.Elem().Set(x)
                        }
                        if err = loadEntity(ev.Interface(), e); err != nil {
                                if _, ok := err.(*ErrFieldMismatch); ok {
                                        // We continue loading entities even in the face of field mismatch errors.
                                        // If we encounter any other error, that other error is returned. Otherwise,
                                        // an ErrFieldMismatch is returned.
                                        errFieldMismatch = err
                                } else {
                                        return keys, err
                                }
                        }
                        if mat != multiArgTypeStructPtr {
                                ev = ev.Elem()
                        }
                        dv.Set(reflect.Append(dv, ev))
                }
                keys = append(keys, k)
        }
        return keys, errFieldMismatch
}

// Run runs the query in the given context.
func (q *Query) Run(c context.Context) *Iterator {
        if q.err != nil {
                return &Iterator{err: q.err}
        }
        t := &Iterator{
                c:      c,
                limit:  q.limit,
                count:  q.count,
                q:      q,
                prevCC: q.start,
        }
        var req pb.Query
        if err := q.toProto(&req, internal.FullyQualifiedAppID(c)); err != nil {
                t.err = err
                return t
        }
        if err := internal.Call(c, "datastore_v3", "RunQuery", &req, &t.res); err != nil {
                t.err = err
                return t
        }
        offset := q.offset - t.res.GetSkippedResults()
        var count int32
        if t.count > 0 && (t.limit < 0 || t.count < t.limit) {
                count = t.count
        } else {
                count = t.limit
        }
        for offset > 0 && t.res.GetMoreResults() {
                t.prevCC = t.res.CompiledCursor
                if err := callNext(t.c, &t.res, offset, count); err != nil {
                        t.err = err
                        break
                }
                skip := t.res.GetSkippedResults()
                if skip < 0 {
                        t.err = errors.New("datastore: internal error: negative number of skipped_results")
                        break
                }
                offset -= skip
        }
        if offset < 0 {
                t.err = errors.New("datastore: internal error: query offset was overshot")
        }
        return t
}

// Iterator is the result of running a query.
type Iterator struct {
        c   context.Context
        err error
        // res is the result of the most recent RunQuery or Next API call.
        res pb.QueryResult
        // i is how many elements of res.Result we have iterated over.
        i int
        // limit is the limit on the number of results this iterator should return.
        // A negative value means unlimited.
        limit int32
        // count is the number of results this iterator should fetch at once. This
        // should be equal to or greater than zero.
        count int32
        // q is the original query which yielded this iterator.
        q *Query
        // prevCC is the compiled cursor that marks the end of the previous batch
        // of results.
        prevCC *pb.CompiledCursor
}

// Done is returned when a query iteration has completed.
var Done = errors.New("datastore: query has no more results")

// Next returns the key of the next result. When there are no more results,
// Done is returned as the error.
//
// If the query is not keys only and dst is non-nil, it also loads the entity
// stored for that key into the struct pointer or PropertyLoadSaver dst, with
// the same semantics and possible errors as for the Get function.
func (t *Iterator) Next(dst interface{}) (*Key, error) {
        k, e, err := t.next()
        if err != nil {
                return nil, err
        }
        if dst != nil && !t.q.keysOnly {
                err = loadEntity(dst, e)
        }
        return k, err
}

func (t *Iterator) next() (*Key, *pb.EntityProto, error) {
        if t.err != nil {
                return nil, nil, t.err
        }

        // Issue datastore_v3/Next RPCs as necessary.
        for t.i == len(t.res.Result) {
                if !t.res.GetMoreResults() {
                        t.err = Done
                        return nil, nil, t.err
                }
                t.prevCC = t.res.CompiledCursor
                var count int32
                if t.count > 0 && (t.limit < 0 || t.count < t.limit) {
                        count = t.count
                } else {
                        count = t.limit
                }
                if err := callNext(t.c, &t.res, 0, count); err != nil {
                        t.err = err
                        return nil, nil, t.err
                }
                if t.res.GetSkippedResults() != 0 {
                        t.err = errors.New("datastore: internal error: iterator has skipped results")
                        return nil, nil, t.err
                }
                t.i = 0
                if t.limit >= 0 {
                        t.limit -= int32(len(t.res.Result))
                        if t.limit < 0 {
                                t.err = errors.New("datastore: internal error: query returned more results than the limit")
                                return nil, nil, t.err
                        }
                }
        }

        // Extract the key from the t.i'th element of t.res.Result.
        e := t.res.Result[t.i]
        t.i++
        if e.Key == nil {
                return nil, nil, errors.New("datastore: internal error: server did not return a key")
        }
        k, err := protoToKey(e.Key)
        if err != nil || k.Incomplete() {
                return nil, nil, errors.New("datastore: internal error: server returned an invalid key")
        }
        return k, e, nil
}

// Cursor returns a cursor for the iterator's current location.
func (t *Iterator) Cursor() (Cursor, error) {
        if t.err != nil && t.err != Done {
                return Cursor{}, t.err
        }
        // If we are at either end of the current batch of results,
        // return the compiled cursor at that end.
        skipped := t.res.GetSkippedResults()
        if t.i == 0 && skipped == 0 {
                if t.prevCC == nil {
                        // A nil pointer (of type *pb.CompiledCursor) means no constraint:
                        // passing it as the end cursor of a new query means unlimited results
                        // (glossing over the integer limit parameter for now).
                        // A non-nil pointer to an empty pb.CompiledCursor means the start:
                        // passing it as the end cursor of a new query means 0 results.
                        // If prevCC was nil, then the original query had no start cursor, but
                        // Iterator.Cursor should return "the start" instead of unlimited.
                        return Cursor{&zeroCC}, nil
                }
                return Cursor{t.prevCC}, nil
        }
        if t.i == len(t.res.Result) {
                return Cursor{t.res.CompiledCursor}, nil
        }
        // Otherwise, re-run the query offset to this iterator's position, starting from
        // the most recent compiled cursor. This is done on a best-effort basis, as it
        // is racy; if a concurrent process has added or removed entities, then the
        // cursor returned may be inconsistent.
        q := t.q.clone()
        q.start = t.prevCC
        q.offset = skipped + int32(t.i)
        q.limit = 0
        q.keysOnly = len(q.projection) == 0
        t1 := q.Run(t.c)
        _, _, err := t1.next()
        if err != Done {
                if err == nil {
                        err = fmt.Errorf("datastore: internal error: zero-limit query did not have zero results")
                }
                return Cursor{}, err
        }
        return Cursor{t1.res.CompiledCursor}, nil
}

var zeroCC pb.CompiledCursor

// Cursor is an iterator's position. It can be converted to and from an opaque
// string. A cursor can be used from different HTTP requests, but only with a
// query with the same kind, ancestor, filter and order constraints.
type Cursor struct {
        cc *pb.CompiledCursor
}

// String returns a base-64 string representation of a cursor.
func (c Cursor) String() string {
        if c.cc == nil {
                return ""
        }
        b, err := proto.Marshal(c.cc)
        if err != nil {
                // The only way to construct a Cursor with a non-nil cc field is to
                // unmarshal from the byte representation. We panic if the unmarshal
                // succeeds but the marshaling of the unchanged protobuf value fails.
                panic(fmt.Sprintf("datastore: internal error: malformed cursor: %v", err))
        }
        return strings.TrimRight(base64.URLEncoding.EncodeToString(b), "=")
}

// Decode decodes a cursor from its base-64 string representation.
func DecodeCursor(s string) (Cursor, error) {
        if s == "" {
                return Cursor{&zeroCC}, nil
        }
        if n := len(s) % 4; n != 0 {
                s += strings.Repeat("=", 4-n)
        }
        b, err := base64.URLEncoding.DecodeString(s)
        if err != nil {
                return Cursor{}, err
        }
        cc := &pb.CompiledCursor{}
        if err := proto.Unmarshal(b, cc); err != nil {
                return Cursor{}, err
        }
        return Cursor{cc}, nil
}