Switch to external stringset implementation.

impl/memory/datastore_index_selection.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 (
         "bytes"
         "fmt"
         "sort"
         "strings"
 
         ds "github.com/luci/gae/service/datastore"
         "github.com/luci/gae/service/datastore/serialize"
+        "github.com/luci/luci-go/common/stringset"
 )
 
 // reducedQuery contains only the pieces of the query necessary to iterate for
 // results.
 //   deduplication is applied externally
 //   projection / keysonly / entity retrieval is done externally
 type reducedQuery struct {
         ns   string
         kind string
 
         // eqFilters indicate the set of all prefix constraints which need to be
         // fulfilled in the composite query. All of these will translate into prefix
         // bytes for SOME index.
-        eqFilters map[string]stringSet
+        eqFilters map[string]stringset.Set
 
         // suffixFormat is the PRECISE listing of the suffix columns that ALL indexes
         //   in the multi query will have.
         //
         // suffixFormat ALWAYS includes the inequality filter (if any) as the 0th
         //   element
         // suffixFormat ALWAYS includes any additional projections (in ascending
         //   order) after all user defined sort orders
         // suffixFormat ALWAYS has __key__ as the last column
         suffixFormat []ds.IndexColumn
@@ skipping 67 matching lines @@
 // maybeAddDefinition possibly adds a new IndexDefinitionSortable to this slice.
 // It's only added if it could be useful in servicing q, otherwise this function
 // is a noop.
 //
 // This returns true iff the proposed index is OK and depletes missingTerms to
 // empty.
 //
 // If the proposed index is PERFECT (e.g. contains enough columns to cover all
 // equality filters, and also has the correct suffix), idxs will be replaced
 // with JUST that index, and this will return true.
-func (idxs *IndexDefinitionSortableSlice) maybeAddDefinition(q *reducedQuery, s *memStore, missingTerms stringSet, id *ds.IndexDefinition) bool {
+func (idxs *IndexDefinitionSortableSlice) maybeAddDefinition(q *reducedQuery, s *memStore, missingTerms stringset.Set, id *ds.IndexDefinition) bool {
         // Kindless queries are handled elsewhere.
         if id.Kind != q.kind {
                 impossible(
                         fmt.Errorf("maybeAddDefinition given index with wrong kind %q v %q", id.Kind, q.kind))
         }
 
         // If we're an ancestor query, and the index is compound, but doesn't include
         // an Ancestor field, it doesn't work. Builtin indexes can be used for
         // ancestor queries (and have !Ancestor), assuming that it's only equality
         // filters (plus inequality on __key__), or a single inequality.
@@ skipping 51 matching lines @@
         coll := s.GetCollection(
                 fmt.Sprintf("idx:%s:%s", q.ns, serialize.ToBytes(*id.PrepForIdxTable())))
 
         // First, see if it's a perfect match. If it is, then our search is over.
         //
         // A perfect match contains ALL the equality filter columns (or more, since
         // we can use residuals to fill in the extras).
         toAdd := IndexDefinitionSortable{coll: coll}
         toAdd.eqFilts = eqFilts
         for _, sb := range toAdd.eqFilts {
-                missingTerms.rm(sb.Property)
+                missingTerms.Del(sb.Property)
         }
 
         perfect := false
         if len(sortBy) == q.numCols {
                 perfect = true
                 for k, num := range numByProp {
-                        if num < len(q.eqFilters[k]) {
+                        if num < q.eqFilters[k].Len() {
                                 perfect = false
                                 break
                         }
                 }
         }
         if perfect {
                 *idxs = IndexDefinitionSortableSlice{toAdd}
         } else {
                 *idxs = append(*idxs, toAdd)
         }
-        return len(missingTerms) == 0
+        return missingTerms.Len() == 0
 }
 
 // getRelevantIndexes retrieves the relevant indexes which could be used to
 // service q. It returns nil if it's not possible to service q with the current
 // indexes.
 func getRelevantIndexes(q *reducedQuery, s *memStore) (IndexDefinitionSortableSlice, error) {
-        missingTerms := stringSet{}
+        missingTerms := stringset.New(len(q.eqFilters))
         for k := range q.eqFilters {
                 if k == "__ancestor__" {
                         // ancestor is not a prefix which can be satisfied by a single index. It
                         // must be satisfied by ALL indexes (and has special logic for this in
                         // the addDefinition logic)
                         continue
                 }
-                missingTerms.add(k)
+                missingTerms.Add(k)
         }
         idxs := IndexDefinitionSortableSlice{}
 
         // First we add builtins
         // add
         //   idx:KIND
         if idxs.maybeAddDefinition(q, s, missingTerms, &ds.IndexDefinition{
                 Kind: q.kind,
         }) {
                 return idxs, nil
         }
 
         // add
         //   idx:KIND:prop
         //   idx:KIND:-prop
-        props := stringSet{}
+        props := stringset.New(len(q.eqFilters) + (len(q.suffixFormat) - len(q.suffixFormat)))

[dnj, 2015/08/31 23:27:26]

A + (B - B)?

[iannucci, 2015/09/10 21:32:19]

Oops. Fixed.

         for prop := range q.eqFilters {
-                props.add(prop)
+                props.Add(prop)
         }
         for _, col := range q.suffixFormat[:len(q.suffixFormat)-1] {
-                props.add(col.Property)
+                props.Add(col.Property)
         }
-        for prop := range props {
+        for _, prop := range props.ToSlice() {
                 if strings.HasPrefix(prop, "__") && strings.HasSuffix(prop, "__") {
                         continue
                 }
                 if idxs.maybeAddDefinition(q, s, missingTerms, &ds.IndexDefinition{
                         Kind: q.kind,
                         SortBy: []ds.IndexColumn{
                                 {Property: prop},
                         },
                 }) {
                         return idxs, nil
@@ skipping 14 matching lines @@
                 Ancestor: q.eqFilters["__ancestor__"] != nil,
                 SortBy:   q.suffixFormat,
         }
         walkCompIdxs(s, suffix, func(def *ds.IndexDefinition) bool {
                 // keep walking until we find a perfect index.
                 return !idxs.maybeAddDefinition(q, s, missingTerms, def)
         })
 
         // this query is impossible to fulfil with the current indexes. Not all the
         // terms (equality + projection) are satisfied.
-        if len(missingTerms) < 0 || len(idxs) == 0 {
+        if missingTerms.Len() < 0 || len(idxs) == 0 {
                 remains := &ds.IndexDefinition{
                         Kind:     q.kind,
                         Ancestor: q.eqFilters["__ancestor__"] != nil,
                 }
-                terms := make([]string, 0, len(missingTerms))
-                for mt := range missingTerms {
-                        terms = append(terms, mt)
-                }
+                terms := missingTerms.ToSlice()
                 if serializationDeterministic {
                         sort.Strings(terms)
                 }
                 for _, term := range terms {
                         remains.SortBy = append(remains.SortBy, ds.IndexColumn{Property: term})
                 }
                 remains.SortBy = append(remains.SortBy, q.suffixFormat...)
                 last := remains.SortBy[len(remains.SortBy)-1]
                 if last.Direction == ds.ASCENDING {
                         // this removes the __key__ column, since it's implicit.
@@ skipping 39 matching lines @@
                 //   Kind/__key__
                 //   Kind/Prop/__key__
                 //   Kind/Prop/-__key__
                 if len(q.suffixFormat) > 2 || q.suffixFormat[len(q.suffixFormat)-1].Property != "__key__" {
                         // This should never happen. One of the previous validators would have
                         // selected a different index. But just in case.
                         impossible(fmt.Errorf("cannot supply an implicit ancestor for %#v", idx))
                 }
 
                 // get the only value out of __ancestor__
-                anc := q.eqFilters["__ancestor__"].getOne()
+                anc, _ := q.eqFilters["__ancestor__"].Peek()
 
                 // Intentionally do NOT update prefixLen. This allows multiIterator to
                 // correctly include the entire key in the shared iterator suffix, instead
                 // of just the remainder.
 
                 // chop the terminal null byte off the q.ancestor key... we can accept
                 // anything which is a descendant or an exact match.  Removing the last byte
                 // from the key (the terminating null) allows this trick to work. Otherwise
                 // it would be a closed range of EXACTLY this key.
                 chopped := []byte(anc[:len(anc)-1])
@@ skipping 73 matching lines @@
 // arbitrary value for filling index prefixes which have more equality fields
 // than are necessary. The value doesn't matter, as long as its an equality
 // constraint in the original query.
 func calculateConstraints(q *reducedQuery) *constraints {
         ret := &constraints{
                 original:        make(map[string][][]byte, len(q.eqFilters)),
                 constraints:     make(map[string][][]byte, len(q.eqFilters)),
                 residualMapping: make(map[string]int),
         }
         for prop, vals := range q.eqFilters {
-                bvals := make([][]byte, 0, len(vals))
-                for val := range vals {
+                bvals := make([][]byte, 0, vals.Len())
+                vals.Iter(func(val string) bool {
                         bvals = append(bvals, []byte(val))
-                }
+                        return true
+                })
                 ret.original[prop] = bvals
                 if prop == "__ancestor__" {
                         // exclude __ancestor__ from the constraints.
                         //
                         // This is because it's handled specially during index proposal and
                         // generation. Ancestor is used by ALL indexes, and so its residual value
                         // in ret.original above will be sufficient.
                         continue
                 }
                 ret.constraints[prop] = bvals
@@ skipping 77 matching lines @@
                 if bestIdx == nil {
                         // something is really wrong here... if relevantIdxs is !nil, then we
                         // should always be able to make progress in this loop.
                         impossible(fmt.Errorf("deadlock: cannot fulfil query?"))
                 }
                 ret = append(ret, generate(q, bestIdx, constraints))
         }
 
         return ret, nil
 }