Home Download Docs Code Community
     1	/*
     2	Copyright 2013 The Perkeep Authors
     3	
     4	Licensed under the Apache License, Version 2.0 (the "License");
     5	you may not use this file except in compliance with the License.
     6	You may obtain a copy of the License at
     7	
     8	     http://www.apache.org/licenses/LICENSE-2.0
     9	
    10	Unless required by applicable law or agreed to in writing, software
    11	distributed under the License is distributed on an "AS IS" BASIS,
    12	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13	See the License for the specific language governing permissions and
    14	limitations under the License.
    15	*/
    16	
    17	package search
    18	
    19	import (
    20		"bytes"
    21		"encoding/json"
    22		"errors"
    23		"fmt"
    24		"io"
    25		"log"
    26		"math"
    27		"net/http"
    28		"os"
    29		"reflect"
    30		"sort"
    31		"strconv"
    32		"strings"
    33		"sync"
    34		"time"
    35	
    36		"perkeep.org/pkg/blob"
    37		"perkeep.org/pkg/index"
    38		"perkeep.org/pkg/types/camtypes"
    39	
    40		"context"
    41	
    42		"go4.org/strutil"
    43		"go4.org/types"
    44	)
    45	
    46	type SortType int
    47	
    48	const (
    49		UnspecifiedSort SortType = iota
    50		Unsorted
    51		LastModifiedDesc
    52		LastModifiedAsc
    53		CreatedDesc
    54		CreatedAsc
    55		BlobRefAsc
    56		// MapSort requests that any limited search results are optimized
    57		// for rendering on a map. If there are fewer matches than the
    58		// requested limit, no results are pruned. When limiting results,
    59		// MapSort prefers results spread around the map before clustering
    60		// items too tightly.
    61		MapSort
    62		maxSortType
    63	)
    64	
    65	var sortName = map[SortType][]byte{
    66		Unsorted:         []byte(`"unsorted"`),
    67		LastModifiedDesc: []byte(`"-mod"`),
    68		LastModifiedAsc:  []byte(`"mod"`),
    69		CreatedDesc:      []byte(`"-created"`),
    70		CreatedAsc:       []byte(`"created"`),
    71		BlobRefAsc:       []byte(`"blobref"`),
    72		MapSort:          []byte(`"map"`),
    73	}
    74	
    75	func (t SortType) MarshalJSON() ([]byte, error) {
    76		v, ok := sortName[t]
    77		if !ok {
    78			panic("unnamed SortType " + strconv.Itoa(int(t)))
    79		}
    80		return v, nil
    81	}
    82	
    83	func (t *SortType) UnmarshalJSON(v []byte) error {
    84		for n, nv := range sortName {
    85			if bytes.Equal(v, nv) {
    86				*t = n
    87				return nil
    88			}
    89		}
    90		return fmt.Errorf("Bogus search sort type %q", v)
    91	}
    92	
    93	type SearchQuery struct {
    94		// Exactly one of Expression or Contraint must be set.
    95		// If an Expression is set, it's compiled to a Constraint.
    96	
    97		// Expression is a textual search query in minimal form,
    98		// e.g. "hawaii before:2008" or "tag:foo" or "foo" or "location:portland"
    99		// See expr.go and expr_test.go for all the operators.
   100		Expression string      `json:"expression,omitempty"`
   101		Constraint *Constraint `json:"constraint,omitempty"`
   102	
   103		// Limit is the maximum number of returned results. A negative value means no
   104		// limit. If unspecified, a default (of 200) will be used.
   105		Limit int `json:"limit,omitempty"`
   106	
   107		// Sort specifies how the results will be sorted. It defaults to CreatedDesc when the
   108		// query is about permanodes only.
   109		Sort SortType `json:"sort,omitempty"`
   110	
   111		// Around specifies that the results, after sorting, should be centered around
   112		// this result. If Around is not found the returned results will be empty.
   113		// If both Continue and Around are set, an error is returned.
   114		Around blob.Ref `json:"around,omitempty"`
   115	
   116		// Continue specifies the opaque token (as returned by a
   117		// SearchResult) for where to continue fetching results when
   118		// the Limit on a previous query was interrupted.
   119		// Continue is only valid for the same query (Expression or Constraint),
   120		// Limit, and Sort values.
   121		// If empty, the top-most query results are returned, as given
   122		// by Limit and Sort.
   123		// Continue is not compatible with the Around option.
   124		Continue string `json:"continue,omitempty"`
   125	
   126		// If Describe is specified, the matched blobs are also described,
   127		// as if the Describe.BlobRefs field was populated.
   128		Describe *DescribeRequest `json:"describe,omitempty"`
   129	}
   130	
   131	func (q *SearchQuery) URLSuffix() string { return "camli/search/query" }
   132	
   133	func (q *SearchQuery) FromHTTP(req *http.Request) error {
   134		dec := json.NewDecoder(io.LimitReader(req.Body, 1<<20))
   135		return dec.Decode(q)
   136	}
   137	
   138	// exprQuery optionally specifies the *SearchQuery prototype that was generated
   139	// by parsing the search expression
   140	func (q *SearchQuery) plannedQuery(expr *SearchQuery) *SearchQuery {
   141		pq := new(SearchQuery)
   142		*pq = *q
   143		if expr != nil {
   144			pq.Constraint = expr.Constraint
   145			if expr.Sort != 0 {
   146				pq.Sort = expr.Sort
   147			}
   148			if expr.Limit != 0 {
   149				pq.Limit = expr.Limit
   150			}
   151		}
   152		if pq.Sort == UnspecifiedSort {
   153			if pq.Constraint.onlyMatchesPermanode() {
   154				pq.Sort = CreatedDesc
   155			}
   156		}
   157		if pq.Limit == 0 {
   158			pq.Limit = 200 // arbitrary
   159		}
   160		if err := pq.addContinueConstraint(); err != nil {
   161			log.Printf("Ignoring continue token: %v", err)
   162		}
   163		pq.Constraint = optimizePlan(pq.Constraint)
   164		return pq
   165	}
   166	
   167	// For permanodes, the continue token is (currently!)
   168	// of form "pn:nnnnnnn:sha1-xxxxx" where "pn" is a
   169	// literal, "nnnnnn" is the UnixNano of the time
   170	// (modified or created) and "sha1-xxxxx" was the item
   171	// seen in the final result set, used as a tie breaker
   172	// if multiple permanodes had the same mod/created
   173	// time. This format is NOT an API promise or standard and
   174	// clients should not rely on it. It may change without notice
   175	func parsePermanodeContinueToken(v string) (t time.Time, br blob.Ref, ok bool) {
   176		if !strings.HasPrefix(v, "pn:") {
   177			return
   178		}
   179		v = v[len("pn:"):]
   180		col := strings.Index(v, ":")
   181		if col < 0 {
   182			return
   183		}
   184		nano, err := strconv.ParseUint(v[:col], 10, 64)
   185		if err != nil {
   186			return
   187		}
   188		t = time.Unix(0, int64(nano))
   189		br, ok = blob.Parse(v[col+1:])
   190		return
   191	}
   192	
   193	// addContinueConstraint conditionally modifies q.Constraint to scroll
   194	// past the results as indicated by q.Continue.
   195	func (q *SearchQuery) addContinueConstraint() error {
   196		cont := q.Continue
   197		if cont == "" {
   198			return nil
   199		}
   200		if q.Constraint.onlyMatchesPermanode() {
   201			tokent, lastbr, ok := parsePermanodeContinueToken(cont)
   202			if !ok {
   203				return errors.New("Unexpected continue token")
   204			}
   205			if q.Sort == LastModifiedDesc || q.Sort == CreatedDesc {
   206				var lastMod, lastCreated time.Time
   207				switch q.Sort {
   208				case LastModifiedDesc:
   209					lastMod = tokent
   210				case CreatedDesc:
   211					lastCreated = tokent
   212				}
   213				baseConstraint := q.Constraint
   214				q.Constraint = &Constraint{
   215					Logical: &LogicalConstraint{
   216						Op: "and",
   217						A: &Constraint{
   218							Permanode: &PermanodeConstraint{
   219								Continue: &PermanodeContinueConstraint{
   220									LastCreated: lastCreated,
   221									LastMod:     lastMod,
   222									Last:        lastbr,
   223								},
   224							},
   225						},
   226						B: baseConstraint,
   227					},
   228				}
   229			}
   230			return nil
   231		}
   232		return errors.New("token not valid for query type")
   233	}
   234	
   235	func (q *SearchQuery) checkValid(ctx context.Context) (sq *SearchQuery, err error) {
   236		if q.Sort >= maxSortType || q.Sort < 0 {
   237			return nil, errors.New("invalid sort type")
   238		}
   239		if q.Continue != "" && q.Around.Valid() {
   240			return nil, errors.New("Continue and Around parameters are mutually exclusive")
   241		}
   242		if q.Sort == MapSort && (q.Continue != "" || q.Around.Valid()) {
   243			return nil, errors.New("Continue or Around parameters are not available with MapSort")
   244		}
   245		if q.Constraint != nil && q.Expression != "" {
   246			return nil, errors.New("Constraint and Expression are mutually exclusive in a search query")
   247		}
   248		if q.Constraint != nil {
   249			return sq, q.Constraint.checkValid()
   250		}
   251		expr := q.Expression
   252		sq, err = parseExpression(ctx, expr)
   253		if err != nil {
   254			return nil, fmt.Errorf("Error parsing search expression %q: %v", expr, err)
   255		}
   256		if err := sq.Constraint.checkValid(); err != nil {
   257			return nil, fmt.Errorf("Internal error: parseExpression(%q) returned invalid constraint: %v", expr, err)
   258		}
   259		return sq, nil
   260	}
   261	
   262	// SearchResult is the result of the Search method for a given SearchQuery.
   263	type SearchResult struct {
   264		Blobs    []*SearchResultBlob `json:"blobs"`
   265		Describe *DescribeResponse   `json:"description"`
   266	
   267		// LocationArea is non-nil if the search result mentioned any location terms. It
   268		// is the bounds of the locations of the matched permanodes, for the permanodes
   269		// with locations.
   270		LocationArea *camtypes.LocationBounds
   271	
   272		// Continue optionally specifies the continuation token to to
   273		// continue fetching results in this result set, if interrupted
   274		// by a Limit.
   275		Continue string `json:"continue,omitempty"`
   276	}
   277	
   278	type SearchResultBlob struct {
   279		Blob blob.Ref `json:"blob"`
   280		// ... file info, permanode info, blob info ... ?
   281	}
   282	
   283	func (r *SearchResultBlob) String() string {
   284		return fmt.Sprintf("[blob: %s]", r.Blob)
   285	}
   286	
   287	// Constraint specifies a blob matching constraint.
   288	// A blob matches if it matches all non-zero fields' predicates.
   289	// A zero constraint matches nothing.
   290	type Constraint struct {
   291		// If Logical is non-nil, all other fields are ignored.
   292		Logical *LogicalConstraint `json:"logical,omitempty"`
   293	
   294		// Anything, if true, matches all blobs.
   295		Anything bool `json:"anything,omitempty"`
   296	
   297		CamliType     string `json:"camliType,omitempty"`    // camliType of the JSON blob
   298		AnyCamliType  bool   `json:"anyCamliType,omitempty"` // if true, any camli JSON blob matches
   299		BlobRefPrefix string `json:"blobRefPrefix,omitempty"`
   300	
   301		File *FileConstraint `json:"file,omitempty"`
   302		Dir  *DirConstraint  `json:"dir,omitempty"`
   303	
   304		Claim    *ClaimConstraint `json:"claim,omitempty"`
   305		BlobSize *IntConstraint   `json:"blobSize,omitempty"`
   306	
   307		Permanode *PermanodeConstraint `json:"permanode,omitempty"`
   308	
   309		matcherOnce sync.Once
   310		matcherFn   matchFn
   311	}
   312	
   313	func (c *Constraint) checkValid() error {
   314		type checker interface {
   315			checkValid() error
   316		}
   317		if c.Claim != nil {
   318			return errors.New("TODO: implement ClaimConstraint")
   319		}
   320		for _, cv := range []checker{
   321			c.Logical,
   322			c.File,
   323			c.Dir,
   324			c.BlobSize,
   325			c.Permanode,
   326		} {
   327			if err := cv.checkValid(); err != nil {
   328				return err
   329			}
   330		}
   331		return nil
   332	}
   333	
   334	// matchesPermanodeTypes returns a set of valid permanode types that a matching
   335	// permanode must have as its "camliNodeType" attribute.
   336	// It returns a zero-length slice if this constraint might include things other
   337	// things.
   338	func (c *Constraint) matchesPermanodeTypes() []string {
   339		if c == nil {
   340			return nil
   341		}
   342		if pc := c.Permanode; pc != nil && pc.Attr == "camliNodeType" && pc.Value != "" {
   343			return []string{pc.Value}
   344		}
   345		if lc := c.Logical; lc != nil {
   346			sa := lc.A.matchesPermanodeTypes()
   347			sb := lc.B.matchesPermanodeTypes()
   348			switch lc.Op {
   349			case "and":
   350				if len(sa) != 0 {
   351					return sa
   352				}
   353				return sb
   354			case "or":
   355				return append(sa, sb...)
   356			}
   357		}
   358		return nil
   359	
   360	}
   361	
   362	// matchesAtMostOneBlob reports whether this constraint matches at most a single blob.
   363	// If so, it returns that blob. Otherwise it returns a zero, invalid blob.Ref.
   364	func (c *Constraint) matchesAtMostOneBlob() blob.Ref {
   365		if c == nil {
   366			return blob.Ref{}
   367		}
   368		if c.BlobRefPrefix != "" {
   369			br, ok := blob.Parse(c.BlobRefPrefix)
   370			if ok {
   371				return br
   372			}
   373		}
   374		if c.Logical != nil && c.Logical.Op == "and" {
   375			if br := c.Logical.A.matchesAtMostOneBlob(); br.Valid() {
   376				return br
   377			}
   378			if br := c.Logical.B.matchesAtMostOneBlob(); br.Valid() {
   379				return br
   380			}
   381		}
   382		return blob.Ref{}
   383	}
   384	
   385	func (c *Constraint) onlyMatchesPermanode() bool {
   386		if c.Permanode != nil || c.CamliType == "permanode" {
   387			return true
   388		}
   389	
   390		if c.Logical != nil && c.Logical.Op == "and" {
   391			if c.Logical.A.onlyMatchesPermanode() || c.Logical.B.onlyMatchesPermanode() {
   392				return true
   393			}
   394		}
   395	
   396		// TODO: There are other cases we can return true here, like:
   397		// Logical:{Op:'or', A:PermanodeConstraint{...}, B:PermanodeConstraint{...}
   398	
   399		return false
   400	}
   401	
   402	func (c *Constraint) matchesFileByWholeRef() bool {
   403		if c.Logical != nil && c.Logical.Op == "and" {
   404			if c.Logical.A.matchesFileByWholeRef() || c.Logical.B.matchesFileByWholeRef() {
   405				return true
   406			}
   407		}
   408		if c.File == nil {
   409			return false
   410		}
   411		return c.File.WholeRef.Valid()
   412	}
   413	
   414	type FileConstraint struct {
   415		// (All non-zero fields must match)
   416	
   417		FileSize *IntConstraint    `json:"fileSize,omitempty"`
   418		FileName *StringConstraint `json:"fileName,omitempty"`
   419		MIMEType *StringConstraint `json:"mimeType,omitempty"`
   420		Time     *TimeConstraint   `json:"time,omitempty"`
   421		ModTime  *TimeConstraint   `json:"modTime,omitempty"`
   422	
   423		// WholeRef if non-zero only matches if the entire checksum of the
   424		// file (the concatenation of all its blobs) is equal to the
   425		// provided blobref. The index may not have every file's digest for
   426		// every known hash algorithm.
   427		WholeRef blob.Ref `json:"wholeRef,omitempty"`
   428	
   429		// ParentDir, if non-nil, constrains the file match based on properties
   430		// of its parent directory.
   431		ParentDir *DirConstraint `json:"parentDir,omitempty"`
   432	
   433		// For images:
   434		IsImage  bool                `json:"isImage,omitempty"`
   435		EXIF     *EXIFConstraint     `json:"exif,omitempty"` // TODO: implement
   436		Width    *IntConstraint      `json:"width,omitempty"`
   437		Height   *IntConstraint      `json:"height,omitempty"`
   438		WHRatio  *FloatConstraint    `json:"widthHeightRation,omitempty"`
   439		Location *LocationConstraint `json:"location,omitempty"`
   440	
   441		// MediaTag is for ID3 (and similar) embedded metadata in files.
   442		MediaTag *MediaTagConstraint `json:"mediaTag,omitempty"`
   443	}
   444	
   445	type MediaTagConstraint struct {
   446		// Tag is the tag to match.
   447		// For ID3, this includes: title, artist, album, genre, musicbrainzalbumid, year, track, disc, mediaref, durationms.
   448		Tag string `json:"tag"`
   449	
   450		String *StringConstraint `json:"string,omitempty"`
   451		Int    *IntConstraint    `json:"int,omitempty"`
   452	}
   453	
   454	// DirConstraint matches static directories.
   455	type DirConstraint struct {
   456		// (All non-zero fields must match)
   457	
   458		FileName      *StringConstraint `json:"fileName,omitempty"`
   459		BlobRefPrefix string            `json:"blobRefPrefix,omitempty"`
   460	
   461		// ParentDir, if non-nil, constrains the directory match based on properties
   462		// of its parent directory.
   463		ParentDir *DirConstraint `json:"parentDir,omitempty"`
   464	
   465		// TODO: implement.
   466		// FileCount *IntConstraint
   467		// FileSize *IntConstraint
   468	
   469		// TopFileCount, if non-nil, constrains the directory match with the directory's
   470		// number of children (non-recursively).
   471		TopFileCount *IntConstraint `json:"topFileCount,omitempty"`
   472	
   473		// RecursiveContains, if non-nil, is like Contains, but applied to all
   474		// the descendants of the directory. It is mutually exclusive with Contains.
   475		RecursiveContains *Constraint `json:"recursiveContains,omitempty"`
   476	
   477		// Contains, if non-nil, constrains the directory match to just those
   478		// directories containing a file matched by Contains. Contains should have a
   479		// BlobPrefix, or a *FileConstraint, or a *DirConstraint, or a *LogicalConstraint
   480		// combination of the aforementioned. It is only applied to the children of the
   481		// directory, in a non-recursive manner. It is mutually exclusive with RecursiveContains.
   482		Contains *Constraint `json:"contains,omitempty"`
   483	}
   484	
   485	// An IntConstraint specifies constraints on an integer.
   486	type IntConstraint struct {
   487		// Min and Max are both optional and inclusive bounds.
   488		// Zero means don't check.
   489		Min     int64 `json:"min,omitempty"`
   490		Max     int64 `json:"max,omitempty"`
   491		ZeroMin bool  `json:"zeroMin,omitempty"` // if true, min is actually zero
   492		ZeroMax bool  `json:"zeroMax,omitempty"` // if true, max is actually zero
   493	}
   494	
   495	func (c *IntConstraint) hasMin() bool { return c.Min != 0 || c.ZeroMin }
   496	func (c *IntConstraint) hasMax() bool { return c.Max != 0 || c.ZeroMax }
   497	
   498	func (c *IntConstraint) checkValid() error {
   499		if c == nil {
   500			return nil
   501		}
   502		if c.ZeroMin && c.Min != 0 {
   503			return errors.New("in IntConstraint, can't set both ZeroMin and Min")
   504		}
   505		if c.ZeroMax && c.Max != 0 {
   506			return errors.New("in IntConstraint, can't set both ZeroMax and Max")
   507		}
   508		if c.hasMax() && c.hasMin() && c.Min > c.Max {
   509			return errors.New("in IntConstraint, min is greater than max")
   510		}
   511		return nil
   512	}
   513	
   514	func (c *IntConstraint) intMatches(v int64) bool {
   515		if c.hasMin() && v < c.Min {
   516			return false
   517		}
   518		if c.hasMax() && v > c.Max {
   519			return false
   520		}
   521		return true
   522	}
   523	
   524	// A FloatConstraint specifies constraints on a float.
   525	type FloatConstraint struct {
   526		// Min and Max are both optional and inclusive bounds.
   527		// Zero means don't check.
   528		Min     float64 `json:"min,omitempty"`
   529		Max     float64 `json:"max,omitempty"`
   530		ZeroMin bool    `json:"zeroMin,omitempty"` // if true, min is actually zero
   531		ZeroMax bool    `json:"zeroMax,omitempty"` // if true, max is actually zero
   532	}
   533	
   534	func (c *FloatConstraint) hasMin() bool { return c.Min != 0 || c.ZeroMin }
   535	func (c *FloatConstraint) hasMax() bool { return c.Max != 0 || c.ZeroMax }
   536	
   537	func (c *FloatConstraint) checkValid() error {
   538		if c == nil {
   539			return nil
   540		}
   541		if c.ZeroMin && c.Min != 0 {
   542			return errors.New("in FloatConstraint, can't set both ZeroMin and Min")
   543		}
   544		if c.ZeroMax && c.Max != 0 {
   545			return errors.New("in FloatConstraint, can't set both ZeroMax and Max")
   546		}
   547		if c.hasMax() && c.hasMin() && c.Min > c.Max {
   548			return errors.New("in FloatConstraint, min is greater than max")
   549		}
   550		return nil
   551	}
   552	
   553	func (c *FloatConstraint) floatMatches(v float64) bool {
   554		if c.hasMin() && v < c.Min {
   555			return false
   556		}
   557		if c.hasMax() && v > c.Max {
   558			return false
   559		}
   560		return true
   561	}
   562	
   563	type EXIFConstraint struct {
   564		// TODO.  need to put this in the index probably.
   565		// Maybe: GPS *LocationConstraint
   566		// ISO, Aperature, Camera Make/Model, etc.
   567	}
   568	
   569	type LocationConstraint struct {
   570		// Any, if true, matches any photo with a known location.
   571		Any bool
   572	
   573		// North, West, East, and South define a region in which a photo
   574		// must be in order to match.
   575		North float64
   576		West  float64
   577		East  float64
   578		South float64
   579	}
   580	
   581	func (c *LocationConstraint) matchesLatLong(lat, long float64) bool {
   582		if c.Any {
   583			return true
   584		}
   585		if !(c.South <= lat && lat <= c.North) {
   586			return false
   587		}
   588		if c.West < c.East {
   589			return c.West <= long && long <= c.East
   590		}
   591		// boundary spanning longitude ±180°
   592		return c.West <= long || long <= c.East
   593	}
   594	
   595	// A StringConstraint specifies constraints on a string.
   596	// All non-zero must match.
   597	type StringConstraint struct {
   598		Empty           bool           `json:"empty,omitempty"` // matches empty string
   599		Equals          string         `json:"equals,omitempty"`
   600		Contains        string         `json:"contains,omitempty"`
   601		HasPrefix       string         `json:"hasPrefix,omitempty"`
   602		HasSuffix       string         `json:"hasSuffix,omitempty"`
   603		ByteLength      *IntConstraint `json:"byteLength,omitempty"` // length in bytes (not chars)
   604		CaseInsensitive bool           `json:"caseInsensitive,omitempty"`
   605	
   606		// TODO: CharLength (assume UTF-8)
   607	}
   608	
   609	// stringCompareFunc contains a function to get a value from a StringConstraint and a second function to compare it
   610	// against the string s that's being matched.
   611	type stringConstraintFunc struct {
   612		v  func(*StringConstraint) string
   613		fn func(s, v string) bool
   614	}
   615	
   616	// Functions to compare fields of a StringConstraint against strings in a case-sensitive manner.
   617	var stringConstraintFuncs = []stringConstraintFunc{
   618		{func(c *StringConstraint) string { return c.Equals }, func(a, b string) bool { return a == b }},
   619		{func(c *StringConstraint) string { return c.Contains }, strings.Contains},
   620		{func(c *StringConstraint) string { return c.HasPrefix }, strings.HasPrefix},
   621		{func(c *StringConstraint) string { return c.HasSuffix }, strings.HasSuffix},
   622	}
   623	
   624	// Functions to compare fields of a StringConstraint against strings in a case-insensitive manner.
   625	var stringConstraintFuncsFold = []stringConstraintFunc{
   626		{func(c *StringConstraint) string { return c.Equals }, strings.EqualFold},
   627		{func(c *StringConstraint) string { return c.Contains }, strutil.ContainsFold},
   628		{func(c *StringConstraint) string { return c.HasPrefix }, strutil.HasPrefixFold},
   629		{func(c *StringConstraint) string { return c.HasSuffix }, strutil.HasSuffixFold},
   630	}
   631	
   632	func (c *StringConstraint) stringMatches(s string) bool {
   633		if c.Empty && len(s) > 0 {
   634			return false
   635		}
   636		if c.ByteLength != nil && !c.ByteLength.intMatches(int64(len(s))) {
   637			return false
   638		}
   639	
   640		funcs := stringConstraintFuncs
   641		if c.CaseInsensitive {
   642			funcs = stringConstraintFuncsFold
   643		}
   644		for _, pair := range funcs {
   645			if v := pair.v(c); v != "" && !pair.fn(s, v) {
   646				return false
   647			}
   648		}
   649		return true
   650	}
   651	
   652	type TimeConstraint struct {
   653		Before types.Time3339 `json:"before"` // <
   654		After  types.Time3339 `json:"after"`  // >=
   655	
   656		// TODO: this won't JSON-marshal/unmarshal well. Make a time.Duration marshal type?
   657		// Likewise with time that supports omitempty?
   658		InLast time.Duration `json:"inLast"` // >=
   659	}
   660	
   661	type ClaimConstraint struct {
   662		SignedBy     string    `json:"signedBy"` // identity
   663		SignedAfter  time.Time `json:"signedAfter"`
   664		SignedBefore time.Time `json:"signedBefore"`
   665	}
   666	
   667	func (c *ClaimConstraint) checkValid() error {
   668		return errors.New("TODO: implement blobMatches and checkValid on ClaimConstraint")
   669	}
   670	
   671	type LogicalConstraint struct {
   672		Op string      `json:"op"` // "and", "or", "xor", "not"
   673		A  *Constraint `json:"a"`
   674		B  *Constraint `json:"b"` // only valid if Op != "not"
   675	}
   676	
   677	// PermanodeConstraint matches permanodes.
   678	type PermanodeConstraint struct {
   679		// At specifies the time at which to pretend we're resolving attributes.
   680		// Attribute claims after this point in time are ignored.
   681		// If zero, the current time is used.
   682		At time.Time `json:"at,omitempty"`
   683	
   684		// ModTime optionally matches on the last modtime of the permanode.
   685		ModTime *TimeConstraint `json:"modTime,omitempty"`
   686	
   687		// Time optionally matches the permanode's time. A Permanode
   688		// may not have a known time. If the permanode does not have a
   689		// known time, one may be guessed if the top-level search
   690		// parameters request so.
   691		Time *TimeConstraint `json:"time,omitempty"`
   692	
   693		// Attr optionally specifies the attribute to match.
   694		// e.g. "camliContent", "camliMember", "tag"
   695		// This is required if any of the items below are used.
   696		Attr string `json:"attr,omitempty"`
   697	
   698		// SkipHidden skips hidden or other boring files.
   699		SkipHidden bool `json:"skipHidden,omitempty"`
   700	
   701		// NumValue optionally tests the number of values this
   702		// permanode has for Attr.
   703		NumValue *IntConstraint `json:"numValue,omitempty"`
   704	
   705		// ValueAll modifies the matching behavior when an attribute
   706		// is multi-valued.  By default, when ValueAll is false, only
   707		// one value of a multi-valued attribute needs to match. If
   708		// ValueAll is true, all attributes must match.
   709		ValueAll bool `json:"valueAllMatch,omitempty"`
   710	
   711		// Value specifies an exact string to match.
   712		// This is a convenience form for the simple case of exact
   713		// equality. The same can be accomplished with ValueMatches.
   714		Value string `json:"value,omitempty"` // if non-zero, absolute match
   715	
   716		// ValueMatches optionally specifies a StringConstraint to
   717		// match the value against.
   718		ValueMatches *StringConstraint `json:"valueMatches,omitempty"`
   719	
   720		// ValueMatchesInt optionally specifies an IntConstraint to match
   721		// the value against. Non-integer values will not match.
   722		ValueMatchesInt *IntConstraint `json:"valueMatchesInt,omitempty"`
   723	
   724		// ValueMatchesFloat optionally specifies a FloatConstraint to match
   725		// the value against. Non-float values will not match.
   726		ValueMatchesFloat *FloatConstraint `json:"valueMatchesFloat,omitempty"`
   727	
   728		// ValueInSet optionally specifies a sub-query which the value
   729		// (which must be a blobref) must be a part of.
   730		ValueInSet *Constraint `json:"valueInSet,omitempty"`
   731	
   732		// Relation optionally specifies a constraint based on relations
   733		// to other permanodes (e.g. camliMember or camliPath sets).
   734		// You can use it to test the properties of a parent, ancestor,
   735		// child, or progeny.
   736		Relation *RelationConstraint `json:"relation,omitempty"`
   737	
   738		// Location optionally restricts matches to permanodes having
   739		// this location. This only affects permanodes with a known
   740		// type to have an lat/long location.
   741		Location *LocationConstraint `json:"location,omitempty"`
   742	
   743		// Continue is for internal use.
   744		Continue *PermanodeContinueConstraint `json:"-"`
   745	
   746		// TODO:
   747		// NumClaims *IntConstraint  // by owner
   748		// Owner  blob.Ref // search for permanodes by an owner
   749	
   750		// Note: When adding a field, update hasValueConstraint.
   751	}
   752	
   753	type PermanodeContinueConstraint struct {
   754		// LastMod if non-zero is the modtime of the last item
   755		// that was seen. One of this or LastCreated will be set.
   756		LastMod time.Time
   757	
   758		// LastCreated if non-zero is the creation time of the last
   759		// item that was seen.
   760		LastCreated time.Time
   761	
   762		// Last is the last blobref that was shown at the time
   763		// given in ModLessEqual or CreateLessEqual.
   764		// This is used as a tie-breaker.
   765		// If the time is equal, permanodes <= this are not matched.
   766		// If the time is past this in the scroll position, then this
   767		// field is ignored.
   768		Last blob.Ref
   769	}
   770	
   771	func (pcc *PermanodeContinueConstraint) checkValid() error {
   772		if pcc.LastMod.IsZero() == pcc.LastCreated.IsZero() {
   773			return errors.New("exactly one of PermanodeContinueConstraint LastMod or LastCreated must be defined")
   774		}
   775		return nil
   776	}
   777	
   778	type RelationConstraint struct {
   779		// Relation must be one of:
   780		//   * "child"
   781		//   * "parent" (immediate parent only)
   782		//   * "progeny" (any level down)
   783		//   * "ancestor" (any level up)
   784		Relation string
   785	
   786		// EdgeType optionally specifies an edge type.
   787		// By default it matches "camliMember" and "camliPath:*".
   788		EdgeType string
   789	
   790		// After finding all the nodes matching the Relation and
   791		// EdgeType, either one or all (depending on whether Any or
   792		// All is set) must then match for the RelationConstraint
   793		// itself to match.
   794		//
   795		// It is an error to set both.
   796		Any, All *Constraint
   797	}
   798	
   799	func (rc *RelationConstraint) checkValid() error {
   800		if rc.Relation != "parent" && rc.Relation != "child" {
   801			return errors.New("only RelationConstraint.Relation of \"parent\" or \"child\" is currently supported")
   802		}
   803		if (rc.Any == nil) == (rc.All == nil) {
   804			return errors.New("exactly one of RelationConstraint Any or All must be defined")
   805		}
   806		return nil
   807	}
   808	
   809	func (rc *RelationConstraint) matchesAttr(attr string) bool {
   810		if rc.EdgeType != "" {
   811			return attr == rc.EdgeType
   812		}
   813		return attr == "camliMember" || strings.HasPrefix(attr, "camliPath:")
   814	}
   815	
   816	// The PermanodeConstraint matching of RelationConstraint.
   817	func (rc *RelationConstraint) match(ctx context.Context, s *search, pn blob.Ref, at time.Time) (ok bool, err error) {
   818		corpus := s.h.corpus
   819		if corpus == nil {
   820			// TODO: care?
   821			return false, errors.New("RelationConstraint requires an in-memory corpus")
   822		}
   823	
   824		var foreachClaim func(pn blob.Ref, at time.Time, f func(cl *camtypes.Claim) bool)
   825		// relationRef returns the relevant blobRef from the claim if cl defines
   826		// the kind of relation we are looking for, (blob.Ref{}, false) otherwise.
   827		var relationRef func(cl *camtypes.Claim) (blob.Ref, bool)
   828		switch rc.Relation {
   829		case "parent":
   830			foreachClaim = corpus.ForeachClaimBack
   831			relationRef = func(cl *camtypes.Claim) (blob.Ref, bool) { return cl.Permanode, true }
   832		case "child":
   833			foreachClaim = corpus.ForeachClaim
   834			relationRef = func(cl *camtypes.Claim) (blob.Ref, bool) { return blob.Parse(cl.Value) }
   835		default:
   836			panic("bogus")
   837		}
   838	
   839		var matcher matchFn
   840		if rc.Any != nil {
   841			matcher = rc.Any.matcher()
   842		} else {
   843			matcher = rc.All.matcher()
   844		}
   845	
   846		var anyGood bool
   847		var anyBad bool
   848		var lastChecked blob.Ref
   849		var permanodesChecked map[blob.Ref]bool // lazily created to optimize for common case of 1 match
   850		foreachClaim(pn, at, func(cl *camtypes.Claim) bool {
   851			if !rc.matchesAttr(cl.Attr) {
   852				return true // skip claim
   853			}
   854			if lastChecked.Valid() {
   855				if permanodesChecked == nil {
   856					permanodesChecked = make(map[blob.Ref]bool)
   857				}
   858				permanodesChecked[lastChecked] = true
   859				lastChecked = blob.Ref{} // back to zero
   860			}
   861			relRef, ok := relationRef(cl)
   862			if !ok {
   863				// The claim does not define the kind of relation we're looking for
   864				// (e.g. it sets a tag vale), so we continue to the next claim.
   865				return true
   866			}
   867			if permanodesChecked[relRef] {
   868				return true // skip checking
   869			}
   870			if !corpus.PermanodeHasAttrValue(cl.Permanode, at, cl.Attr, cl.Value) {
   871				return true // claim once matched permanode, but no longer
   872			}
   873	
   874			var bm camtypes.BlobMeta
   875			bm, err = s.blobMeta(ctx, relRef)
   876			if err != nil {
   877				return false
   878			}
   879			ok, err = matcher(ctx, s, relRef, bm)
   880			if err != nil {
   881				return false
   882			}
   883			if ok {
   884				anyGood = true
   885				if rc.Any != nil {
   886					return false // done. stop searching.
   887				}
   888			} else {
   889				anyBad = true
   890				if rc.All != nil {
   891					return false // fail fast
   892				}
   893			}
   894			lastChecked = relRef
   895			return true
   896		})
   897		if err != nil {
   898			return false, err
   899		}
   900		if rc.All != nil {
   901			return anyGood && !anyBad, nil
   902		}
   903		return anyGood, nil
   904	}
   905	
   906	// search is the state of an in-progress search
   907	type search struct {
   908		h   *Handler
   909		q   *SearchQuery
   910		res *SearchResult
   911	
   912		// ss is a scratch string slice to avoid allocations.
   913		// We assume (at least so far) that only 1 goroutine is used
   914		// for a given search, so anything can use this.
   915		ss []string // scratch
   916	
   917		// loc is a cache of calculated locations.
   918		//
   919		// TODO: if location-of-permanode were cheaper and cached in
   920		// the corpus instead, then we wouldn't need this. And then
   921		// searches would be faster anyway. This is a hack.
   922		loc map[blob.Ref]camtypes.Location
   923	}
   924	
   925	func (s *search) blobMeta(ctx context.Context, br blob.Ref) (camtypes.BlobMeta, error) {
   926		if c := s.h.corpus; c != nil {
   927			return c.GetBlobMeta(ctx, br)
   928		}
   929		return s.h.index.GetBlobMeta(ctx, br)
   930	}
   931	
   932	func (s *search) fileInfo(ctx context.Context, br blob.Ref) (camtypes.FileInfo, error) {
   933		if c := s.h.corpus; c != nil {
   934			return c.GetFileInfo(ctx, br)
   935		}
   936		return s.h.index.GetFileInfo(ctx, br)
   937	}
   938	
   939	func (s *search) dirChildren(ctx context.Context, br blob.Ref) (map[blob.Ref]struct{}, error) {
   940		if c := s.h.corpus; c != nil {
   941			return c.GetDirChildren(ctx, br)
   942		}
   943	
   944		ch := make(chan blob.Ref)
   945		errch := make(chan error)
   946		go func() {
   947			errch <- s.h.index.GetDirMembers(ctx, br, ch, s.q.Limit)
   948		}()
   949		children := make(map[blob.Ref]struct{})
   950		for child := range ch {
   951			children[child] = struct{}{}
   952		}
   953		if err := <-errch; err != nil {
   954			return nil, err
   955		}
   956		return children, nil
   957	}
   958	
   959	func (s *search) parentDirs(ctx context.Context, br blob.Ref) (map[blob.Ref]struct{}, error) {
   960		c := s.h.corpus
   961		if c == nil {
   962			return nil, errors.New("parent directory search not supported without a corpus")
   963		}
   964		return c.GetParentDirs(ctx, br)
   965	}
   966	
   967	// optimizePlan returns an optimized version of c which will hopefully
   968	// execute faster than executing c literally.
   969	func optimizePlan(c *Constraint) *Constraint {
   970		// TODO: what the comment above says.
   971		return c
   972	}
   973	
   974	var debugQuerySpeed, _ = strconv.ParseBool(os.Getenv("CAMLI_DEBUG_QUERY_SPEED"))
   975	
   976	func (h *Handler) Query(ctx context.Context, rawq *SearchQuery) (ret_ *SearchResult, _ error) {
   977		if debugQuerySpeed {
   978			t0 := time.Now()
   979			jq, _ := json.Marshal(rawq)
   980			log.Printf("[search=%p] Start %v, Doing search %s... ", rawq, t0.Format(time.RFC3339), jq)
   981			defer func() {
   982				d := time.Since(t0)
   983				if ret_ != nil {
   984					log.Printf("[search=%p] Start %v + %v = %v results", rawq, t0.Format(time.RFC3339), d, len(ret_.Blobs))
   985				} else {
   986					log.Printf("[search=%p] Start %v + %v = error", rawq, t0.Format(time.RFC3339), d)
   987				}
   988			}()
   989		}
   990		exprResult, err := rawq.checkValid(ctx)
   991		if err != nil {
   992			return nil, fmt.Errorf("Invalid SearchQuery: %v", err)
   993		}
   994		q := rawq.plannedQuery(exprResult)
   995		res := new(SearchResult)
   996		s := &search{
   997			h:   h,
   998			q:   q,
   999			res: res,
  1000			loc: make(map[blob.Ref]camtypes.Location),
  1001		}
  1002	
  1003		h.index.RLock()
  1004		defer h.index.RUnlock()
  1005	
  1006		ctx, cancelSearch := context.WithCancel(context.TODO())
  1007		defer cancelSearch()
  1008	
  1009		corpus := h.corpus
  1010	
  1011		cands := q.pickCandidateSource(s)
  1012		if candSourceHook != nil {
  1013			candSourceHook(cands.name)
  1014		}
  1015		if debugQuerySpeed {
  1016			log.Printf("[search=%p] using candidate source set %q", rawq, cands.name)
  1017		}
  1018	
  1019		wantAround, foundAround := false, false
  1020		if q.Around.Valid() {
  1021			// TODO(mpl): fail somewhere if MapSorted and wantAround at the same time.
  1022			wantAround = true
  1023		}
  1024		blobMatches := q.Constraint.matcher()
  1025	
  1026		var enumErr error
  1027		cands.send(ctx, s, func(meta camtypes.BlobMeta) bool {
  1028			match, err := blobMatches(ctx, s, meta.Ref, meta)
  1029			if err != nil {
  1030				enumErr = err
  1031				return false
  1032			}
  1033			if match {
  1034				res.Blobs = append(res.Blobs, &SearchResultBlob{
  1035					Blob: meta.Ref,
  1036				})
  1037				if q.Sort == MapSort {
  1038					// We need all the matching blobs to apply the MapSort selection afterwards, so
  1039					// we temporarily ignore the limit.
  1040					// TODO(mpl): the above means that we also ignore Continue and Around here. I
  1041					// don't think we need them for the map aspect for now though.
  1042					return true
  1043				}
  1044				if q.Limit <= 0 || !cands.sorted {
  1045					if wantAround && !foundAround && q.Around == meta.Ref {
  1046						foundAround = true
  1047					}
  1048					return true
  1049				}
  1050				if !wantAround || foundAround {
  1051					if len(res.Blobs) == q.Limit {
  1052						return false
  1053					}
  1054					return true
  1055				}
  1056				if q.Around == meta.Ref {
  1057					foundAround = true
  1058					if len(res.Blobs)*2 > q.Limit {
  1059						// If we've already collected more than half of the Limit when Around is found,
  1060						// we ditch the surplus from the beginning of the slice of results.
  1061						// If Limit is even, and the number of results before and after Around
  1062						// are both greater than half the limit, then there will be one more result before
  1063						// than after.
  1064						discard := len(res.Blobs) - q.Limit/2 - 1
  1065						if discard < 0 {
  1066							discard = 0
  1067						}
  1068						res.Blobs = res.Blobs[discard:]
  1069					}
  1070					if len(res.Blobs) == q.Limit {
  1071						return false
  1072					}
  1073					return true
  1074				}
  1075				if len(res.Blobs) == q.Limit {
  1076					n := copy(res.Blobs, res.Blobs[len(res.Blobs)/2:])
  1077					res.Blobs = res.Blobs[:n]
  1078				}
  1079			}
  1080			return true
  1081		})
  1082		if enumErr != nil {
  1083			return nil, enumErr
  1084		}
  1085		if wantAround && !foundAround {
  1086			// results are ignored if Around was not found
  1087			res.Blobs = nil
  1088		}
  1089		if !cands.sorted {
  1090			switch q.Sort {
  1091			// TODO(mpl): maybe someday we'll want both a sort, and then the MapSort
  1092			// selection, as MapSort is technically not really a sort. In which case, MapSort
  1093			// should probably become e.g. another field of SearchQuery.
  1094			case UnspecifiedSort, Unsorted, MapSort:
  1095				// Nothing to do.
  1096			case BlobRefAsc:
  1097				sort.Sort(sortSearchResultBlobs{res.Blobs, func(a, b *SearchResultBlob) bool {
  1098					return a.Blob.Less(b.Blob)
  1099				}})
  1100			case CreatedDesc, CreatedAsc:
  1101				if corpus == nil {
  1102					return nil, errors.New("TODO: Sorting without a corpus unsupported")
  1103				}
  1104				if !q.Constraint.onlyMatchesPermanode() {
  1105					return nil, errors.New("can only sort by ctime when all results are permanodes")
  1106				}
  1107				var err error
  1108				sort.Sort(sortSearchResultBlobs{res.Blobs, func(a, b *SearchResultBlob) bool {
  1109					if err != nil {
  1110						return false
  1111					}
  1112					ta, ok := corpus.PermanodeAnyTime(a.Blob)
  1113					if !ok {
  1114						err = fmt.Errorf("no ctime or modtime found for %v", a.Blob)
  1115						return false
  1116					}
  1117					tb, ok := corpus.PermanodeAnyTime(b.Blob)
  1118					if !ok {
  1119						err = fmt.Errorf("no ctime or modtime found for %v", b.Blob)
  1120						return false
  1121					}
  1122					if q.Sort == CreatedAsc {
  1123						return ta.Before(tb)
  1124					}
  1125					return tb.Before(ta)
  1126				}})
  1127				if err != nil {
  1128					return nil, err
  1129				}
  1130			// TODO(mpl): LastModifiedDesc, LastModifiedAsc
  1131			default:
  1132				return nil, errors.New("TODO: unsupported sort+query combination.")
  1133			}
  1134			if q.Sort != MapSort {
  1135				if q.Limit > 0 && len(res.Blobs) > q.Limit {
  1136					if wantAround {
  1137						aroundPos := sort.Search(len(res.Blobs), func(i int) bool {
  1138							return res.Blobs[i].Blob.String() >= q.Around.String()
  1139						})
  1140						// If we got this far, we know q.Around is in the results, so this below should
  1141						// never happen
  1142						if aroundPos == len(res.Blobs) || res.Blobs[aroundPos].Blob != q.Around {
  1143							panic("q.Around blobRef should be in the results")
  1144						}
  1145						lowerBound := aroundPos - q.Limit/2
  1146						if lowerBound < 0 {
  1147							lowerBound = 0
  1148						}
  1149						upperBound := lowerBound + q.Limit
  1150						if upperBound > len(res.Blobs) {
  1151							upperBound = len(res.Blobs)
  1152						}
  1153						res.Blobs = res.Blobs[lowerBound:upperBound]
  1154					} else {
  1155						res.Blobs = res.Blobs[:q.Limit]
  1156					}
  1157				}
  1158			}
  1159		}
  1160		if corpus != nil {
  1161			if !wantAround {
  1162				q.setResultContinue(corpus, res)
  1163			}
  1164		}
  1165	
  1166		// Populate s.res.LocationArea
  1167		{
  1168			var la camtypes.LocationBounds
  1169			for _, v := range res.Blobs {
  1170				br := v.Blob
  1171				loc, ok := s.loc[br]
  1172				if !ok {
  1173					continue
  1174				}
  1175				la = la.Expand(loc)
  1176			}
  1177			if la != (camtypes.LocationBounds{}) {
  1178				s.res.LocationArea = &la
  1179			}
  1180		}
  1181	
  1182		if q.Sort == MapSort {
  1183			bestByLocation(s.res, s.loc, q.Limit)
  1184		}
  1185	
  1186		if q.Describe != nil {
  1187			q.Describe.BlobRef = blob.Ref{} // zero this out, if caller set it
  1188			blobs := make([]blob.Ref, 0, len(res.Blobs))
  1189			for _, srb := range res.Blobs {
  1190				blobs = append(blobs, srb.Blob)
  1191			}
  1192			q.Describe.BlobRefs = blobs
  1193			t0 := time.Now()
  1194			res, err := s.h.DescribeLocked(ctx, q.Describe)
  1195			if debugQuerySpeed {
  1196				log.Printf("Describe of %d blobs = %v", len(blobs), time.Since(t0))
  1197			}
  1198			if err != nil {
  1199				return nil, err
  1200			}
  1201			s.res.Describe = res
  1202		}
  1203	
  1204		return s.res, nil
  1205	}
  1206	
  1207	// mapCell is which cell of an NxN cell grid of a map a point is in.
  1208	// The numbering is arbitrary but dense, starting with 0.
  1209	type mapCell int
  1210	
  1211	// mapGrids contains 1 or 2 mapGrids, depending on whether the search
  1212	// area cross the dateline.
  1213	type mapGrids []*mapGrid
  1214	
  1215	func (gs mapGrids) cellOf(loc camtypes.Location) mapCell {
  1216		for i, g := range gs {
  1217			cell, ok := g.cellOf(loc)
  1218			if ok {
  1219				return cell + mapCell(i*g.dim*g.dim)
  1220			}
  1221		}
  1222		return 0 // shouldn't happen, unless loc is malformed, in which case this is fine.
  1223	}
  1224	
  1225	func newMapGrids(area camtypes.LocationBounds, dim int) mapGrids {
  1226		if !area.SpansDateLine() {
  1227			return mapGrids{newMapGrid(area, dim)}
  1228		}
  1229		return mapGrids{
  1230			newMapGrid(camtypes.LocationBounds{
  1231				North: area.North,
  1232				South: area.South,
  1233				West:  area.West,
  1234				East:  180,
  1235			}, dim),
  1236			newMapGrid(camtypes.LocationBounds{
  1237				North: area.North,
  1238				South: area.South,
  1239				West:  -180,
  1240				East:  area.East,
  1241			}, dim),
  1242		}
  1243	}
  1244	
  1245	type mapGrid struct {
  1246		dim        int // grid is dim*dim cells
  1247		area       camtypes.LocationBounds
  1248		cellWidth  float64
  1249		cellHeight float64
  1250	}
  1251	
  1252	// newMapGrid returns a grid matcher over an area. The area must not
  1253	// span the date line. The mapGrid maps locations to a grid of (dim *
  1254	// dim) cells.
  1255	func newMapGrid(area camtypes.LocationBounds, dim int) *mapGrid {
  1256		if area.SpansDateLine() {
  1257			panic("invalid use of newMapGrid: must be called with bounds not overlapping date line")
  1258		}
  1259		return &mapGrid{
  1260			dim:        dim,
  1261			area:       area,
  1262			cellWidth:  area.Width() / float64(dim),
  1263			cellHeight: (area.North - area.South) / float64(dim),
  1264		}
  1265	}
  1266	
  1267	func (g *mapGrid) cellOf(loc camtypes.Location) (c mapCell, ok bool) {
  1268		if loc.Latitude > g.area.North || loc.Latitude < g.area.South ||
  1269			loc.Longitude < g.area.West || loc.Longitude > g.area.East {
  1270			return
  1271		}
  1272		x := int((loc.Longitude - g.area.West) / g.cellWidth)
  1273		y := int((g.area.North - loc.Latitude) / g.cellHeight)
  1274		if x >= g.dim {
  1275			x = g.dim - 1
  1276		}
  1277		if y >= g.dim {
  1278			y = g.dim - 1
  1279		}
  1280		return mapCell(y*g.dim + x), true
  1281	}
  1282	
  1283	// bestByLocation conditionally modifies res.Blobs if the number of blobs
  1284	// is greater than limit. If so, it modifies res.Blobs so only `limit`
  1285	// blobs remain, selecting those such that the results are evenly spread
  1286	// over the result's map area.
  1287	//
  1288	// The algorithm is the following:
  1289	// 1) We know the size and position of the relevant area because
  1290	// res.LocationArea was built during blob matching
  1291	// 2) We divide the area in a grid of ~sqrt(limit) lines and columns, which is
  1292	// represented by a map[camtypes.LocationBounds][]blob.Ref
  1293	// 3) For each described blobRef we place it in the cell matching its location.
  1294	// Each cell is bounded by limit though.
  1295	// 4) We compute the max number of nodes per cell:
  1296	// N = (number of non empty cells) / limit
  1297	// 5) for each cell, append to the set of selected nodes the first N nodes of
  1298	// the cell.
  1299	func bestByLocation(res *SearchResult, locm map[blob.Ref]camtypes.Location, limit int) {
  1300		// Calculate res.LocationArea.
  1301		if len(res.Blobs) <= limit {
  1302			return
  1303		}
  1304	
  1305		if res.LocationArea == nil {
  1306			// No even one result node with a location was found.
  1307			return
  1308		}
  1309	
  1310		// Divide location area in a grid of (dim * dim) map cells,
  1311		// such that (dim * dim) is approximately the given limit,
  1312		// then track which search results are in which cell.
  1313		cellOccupants := make(map[mapCell][]blob.Ref)
  1314		dim := int(math.Round(math.Sqrt(float64(limit))))
  1315		if dim < 3 {
  1316			dim = 3
  1317		} else if dim > 100 {
  1318			dim = 100
  1319		}
  1320		grids := newMapGrids(*res.LocationArea, dim)
  1321	
  1322		resBlob := map[blob.Ref]*SearchResultBlob{}
  1323		for _, srb := range res.Blobs {
  1324			br := srb.Blob
  1325			loc, ok := locm[br]
  1326			if !ok {
  1327				continue
  1328			}
  1329			cellKey := grids.cellOf(loc)
  1330			occupants := cellOccupants[cellKey]
  1331			if len(occupants) >= limit {
  1332				// no sense in filling a cell to more than our overall limit
  1333				continue
  1334			}
  1335			cellOccupants[cellKey] = append(occupants, br)
  1336			resBlob[br] = srb
  1337		}
  1338	
  1339		var nodesKept []*SearchResultBlob
  1340		for {
  1341			for cellKey, occupants := range cellOccupants {
  1342				nodesKept = append(nodesKept, resBlob[occupants[0]])
  1343				if len(nodesKept) == limit {
  1344					res.Blobs = nodesKept
  1345					return
  1346				}
  1347				if len(occupants) == 1 {
  1348					delete(cellOccupants, cellKey)
  1349				} else {
  1350					cellOccupants[cellKey] = occupants[1:]
  1351				}
  1352			}
  1353	
  1354		}
  1355	}
  1356	
  1357	// setResultContinue sets res.Continue if q is suitable for having a continue token.
  1358	// The corpus is locked for reads.
  1359	func (q *SearchQuery) setResultContinue(corpus *index.Corpus, res *SearchResult) {
  1360		if !q.Constraint.onlyMatchesPermanode() {
  1361			return
  1362		}
  1363		var pnTimeFunc func(blob.Ref) (t time.Time, ok bool)
  1364		switch q.Sort {
  1365		case LastModifiedDesc:
  1366			pnTimeFunc = corpus.PermanodeModtime
  1367		case CreatedDesc:
  1368			pnTimeFunc = corpus.PermanodeAnyTime
  1369		default:
  1370			return
  1371		}
  1372	
  1373		if q.Limit <= 0 || len(res.Blobs) != q.Limit {
  1374			return
  1375		}
  1376		lastpn := res.Blobs[len(res.Blobs)-1].Blob
  1377		t, ok := pnTimeFunc(lastpn)
  1378		if !ok {
  1379			return
  1380		}
  1381		res.Continue = fmt.Sprintf("pn:%d:%v", t.UnixNano(), lastpn)
  1382	}
  1383	
  1384	type matchFn func(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error)
  1385	
  1386	func alwaysMatch(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error) {
  1387		return true, nil
  1388	}
  1389	
  1390	func neverMatch(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error) {
  1391		return false, nil
  1392	}
  1393	
  1394	func anyCamliType(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1395		return bm.CamliType != "", nil
  1396	}
  1397	
  1398	// Test hooks.
  1399	var (
  1400		candSourceHook     func(string)
  1401		expandLocationHook bool
  1402	)
  1403	
  1404	type candidateSource struct {
  1405		name   string
  1406		sorted bool
  1407	
  1408		// sends sends to the channel and must close it, regardless of error
  1409		// or interruption from context.Done().
  1410		send func(context.Context, *search, func(camtypes.BlobMeta) bool) error
  1411	}
  1412	
  1413	func (q *SearchQuery) pickCandidateSource(s *search) (src candidateSource) {
  1414		c := q.Constraint
  1415		corpus := s.h.corpus
  1416		if corpus != nil {
  1417			if c.onlyMatchesPermanode() {
  1418				src.sorted = true
  1419				switch q.Sort {
  1420				case LastModifiedDesc:
  1421					src.name = "corpus_permanode_lastmod"
  1422					src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1423						corpus.EnumeratePermanodesLastModified(fn)
  1424						return nil
  1425					}
  1426					return
  1427				case CreatedDesc:
  1428					src.name = "corpus_permanode_created"
  1429					src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1430						corpus.EnumeratePermanodesCreated(fn, true)
  1431						return nil
  1432					}
  1433					return
  1434				default:
  1435					src.sorted = false
  1436					if typs := c.matchesPermanodeTypes(); len(typs) != 0 {
  1437						src.name = "corpus_permanode_types"
  1438						src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1439							corpus.EnumeratePermanodesByNodeTypes(fn, typs)
  1440							return nil
  1441						}
  1442						return
  1443					}
  1444				}
  1445			}
  1446			if br := c.matchesAtMostOneBlob(); br.Valid() {
  1447				src.name = "one_blob"
  1448				src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1449					corpus.EnumerateSingleBlob(fn, br)
  1450					return nil
  1451				}
  1452				return
  1453			}
  1454			// fastpath for files
  1455			if c.matchesFileByWholeRef() {
  1456				src.name = "corpus_file_meta"
  1457				src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1458					corpus.EnumerateCamliBlobs("file", fn)
  1459					return nil
  1460				}
  1461				return
  1462			}
  1463			if c.AnyCamliType || c.CamliType != "" {
  1464				camType := c.CamliType // empty means all
  1465				src.name = "corpus_blob_meta"
  1466				src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1467					corpus.EnumerateCamliBlobs(camType, fn)
  1468					return nil
  1469				}
  1470				return
  1471			}
  1472		}
  1473		src.name = "index_blob_meta"
  1474		src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1475			return s.h.index.EnumerateBlobMeta(ctx, fn)
  1476		}
  1477		return
  1478	}
  1479	
  1480	type allMustMatch []matchFn
  1481	
  1482	func (fns allMustMatch) blobMatches(ctx context.Context, s *search, br blob.Ref, blobMeta camtypes.BlobMeta) (bool, error) {
  1483		for _, condFn := range fns {
  1484			match, err := condFn(ctx, s, br, blobMeta)
  1485			if !match || err != nil {
  1486				return match, err
  1487			}
  1488		}
  1489		return true, nil
  1490	}
  1491	
  1492	func (c *Constraint) matcher() func(ctx context.Context, s *search, br blob.Ref, blobMeta camtypes.BlobMeta) (bool, error) {
  1493		c.matcherOnce.Do(c.initMatcherFn)
  1494		return c.matcherFn
  1495	}
  1496	
  1497	func (c *Constraint) initMatcherFn() {
  1498		c.matcherFn = c.genMatcher()
  1499	}
  1500	
  1501	func (c *Constraint) genMatcher() matchFn {
  1502		var ncond int
  1503		var cond matchFn
  1504		var conds []matchFn
  1505		addCond := func(fn matchFn) {
  1506			ncond++
  1507			if ncond == 1 {
  1508				cond = fn
  1509				return
  1510			} else if ncond == 2 {
  1511				conds = append(conds, cond)
  1512			}
  1513			conds = append(conds, fn)
  1514		}
  1515		if c.Logical != nil {
  1516			addCond(c.Logical.matcher())
  1517		}
  1518		if c.Anything {
  1519			addCond(alwaysMatch)
  1520		}
  1521		if c.CamliType != "" {
  1522			addCond(func(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1523				return bm.CamliType == c.CamliType, nil
  1524			})
  1525		}
  1526		if c.AnyCamliType {
  1527			addCond(anyCamliType)
  1528		}
  1529		if c.Permanode != nil {
  1530			addCond(c.Permanode.blobMatches)
  1531		}
  1532		// TODO: ClaimConstraint
  1533		if c.File != nil {
  1534			addCond(c.File.blobMatches)
  1535		}
  1536		if c.Dir != nil {
  1537			addCond(c.Dir.blobMatches)
  1538		}
  1539		if bs := c.BlobSize; bs != nil {
  1540			addCond(func(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1541				return bs.intMatches(int64(bm.Size)), nil
  1542			})
  1543		}
  1544		if pfx := c.BlobRefPrefix; pfx != "" {
  1545			addCond(func(ctx context.Context, s *search, br blob.Ref, meta camtypes.BlobMeta) (bool, error) {
  1546				return br.HasPrefix(pfx), nil
  1547			})
  1548		}
  1549		switch ncond {
  1550		case 0:
  1551			return neverMatch
  1552		case 1:
  1553			return cond
  1554		default:
  1555			return allMustMatch(conds).blobMatches
  1556		}
  1557	}
  1558	
  1559	func (c *LogicalConstraint) checkValid() error {
  1560		if c == nil {
  1561			return nil
  1562		}
  1563		if c.A == nil {
  1564			return errors.New("In LogicalConstraint, need to set A")
  1565		}
  1566		if err := c.A.checkValid(); err != nil {
  1567			return err
  1568		}
  1569		switch c.Op {
  1570		case "and", "xor", "or":
  1571			if c.B == nil {
  1572				return errors.New("In LogicalConstraint, need both A and B set")
  1573			}
  1574			if err := c.B.checkValid(); err != nil {
  1575				return err
  1576			}
  1577		case "not":
  1578		default:
  1579			return fmt.Errorf("In LogicalConstraint, unknown operation %q", c.Op)
  1580		}
  1581		return nil
  1582	}
  1583	
  1584	func (c *LogicalConstraint) matcher() matchFn {
  1585		amatches := c.A.matcher()
  1586		var bmatches matchFn
  1587		if c.Op != "not" {
  1588			bmatches = c.B.matcher()
  1589		}
  1590		return func(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1591	
  1592			// Note: not using multiple goroutines here, because
  1593			// so far the *search type assumes it's
  1594			// single-threaded. (e.g. the .ss scratch type).
  1595			// Also, not using multiple goroutines means we can
  1596			// short-circuit when Op == "and" and av is false.
  1597	
  1598			av, err := amatches(ctx, s, br, bm)
  1599			if err != nil {
  1600				return false, err
  1601			}
  1602			switch c.Op {
  1603			case "not":
  1604				return !av, nil
  1605			case "and":
  1606				if !av {
  1607					// Short-circuit.
  1608					return false, nil
  1609				}
  1610			case "or":
  1611				if av {
  1612					// Short-circuit.
  1613					return true, nil
  1614				}
  1615			}
  1616	
  1617			bv, err := bmatches(ctx, s, br, bm)
  1618			if err != nil {
  1619				return false, err
  1620			}
  1621	
  1622			switch c.Op {
  1623			case "and", "or":
  1624				return bv, nil
  1625			case "xor":
  1626				return av != bv, nil
  1627			}
  1628			panic("unreachable")
  1629		}
  1630	}
  1631	
  1632	func (c *PermanodeConstraint) checkValid() error {
  1633		if c == nil {
  1634			return nil
  1635		}
  1636		if c.Attr != "" {
  1637			if c.NumValue == nil && !c.hasValueConstraint() {
  1638				return errors.New("PermanodeConstraint with Attr requires also setting NumValue or a value-matching constraint")
  1639			}
  1640			if nv := c.NumValue; nv != nil {
  1641				if nv.ZeroMin {
  1642					return errors.New("NumValue with ZeroMin makes no sense; matches everything")
  1643				}
  1644				if nv.ZeroMax && c.hasValueConstraint() {
  1645					return errors.New("NumValue with ZeroMax makes no sense in conjunction with a value-matching constraint; matches nothing")
  1646				}
  1647				if nv.Min < 0 || nv.Max < 0 {
  1648					return errors.New("NumValue with negative Min or Max makes no sense")
  1649				}
  1650			}
  1651		}
  1652		if rc := c.Relation; rc != nil {
  1653			if err := rc.checkValid(); err != nil {
  1654				return err
  1655			}
  1656		}
  1657		if pcc := c.Continue; pcc != nil {
  1658			if err := pcc.checkValid(); err != nil {
  1659				return err
  1660			}
  1661		}
  1662		return nil
  1663	}
  1664	
  1665	var numPermanodeFields = reflect.TypeOf(PermanodeConstraint{}).NumField()
  1666	
  1667	// hasValueConstraint returns true if one or more constraints that check an attribute's value are set.
  1668	func (c *PermanodeConstraint) hasValueConstraint() bool {
  1669		// If a field has been added or removed, update this after adding the new field to the return statement if necessary.
  1670		const expectedFields = 15
  1671		if numPermanodeFields != expectedFields {
  1672			panic(fmt.Sprintf("PermanodeConstraint field count changed (now %v rather than %v)", numPermanodeFields, expectedFields))
  1673		}
  1674		return c.Value != "" ||
  1675			c.ValueMatches != nil ||
  1676			c.ValueMatchesInt != nil ||
  1677			c.ValueMatchesFloat != nil ||
  1678			c.ValueInSet != nil
  1679	}
  1680	
  1681	func (c *PermanodeConstraint) blobMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (ok bool, err error) {
  1682		if bm.CamliType != "permanode" {
  1683			return false, nil
  1684		}
  1685		corpus := s.h.corpus
  1686	
  1687		var dp *DescribedPermanode
  1688		if corpus == nil {
  1689			dr, err := s.h.DescribeLocked(ctx, &DescribeRequest{BlobRef: br})
  1690			if err != nil {
  1691				return false, err
  1692			}
  1693			db := dr.Meta[br.String()]
  1694			if db == nil || db.Permanode == nil {
  1695				return false, nil
  1696			}
  1697			dp = db.Permanode
  1698		}
  1699	
  1700		if c.Attr != "" {
  1701			if !c.At.IsZero() && corpus == nil {
  1702				panic("PermanodeConstraint.At not supported without an in-memory corpus")
  1703			}
  1704			var vals []string
  1705			if corpus == nil {
  1706				vals = dp.Attr[c.Attr]
  1707			} else {
  1708				s.ss = corpus.AppendPermanodeAttrValues(
  1709					s.ss[:0], br, c.Attr, c.At, s.h.owner.KeyID())
  1710				vals = s.ss
  1711			}
  1712			ok, err := c.permanodeMatchesAttrVals(ctx, s, vals)
  1713			if !ok || err != nil {
  1714				return false, err
  1715			}
  1716		}
  1717	
  1718		if c.SkipHidden && corpus != nil {
  1719			defVis := corpus.PermanodeAttrValue(br, "camliDefVis", c.At, s.h.owner.KeyID())
  1720			if defVis == "hide" {
  1721				return false, nil
  1722			}
  1723			nodeType := corpus.PermanodeAttrValue(br, "camliNodeType", c.At, s.h.owner.KeyID())
  1724			if nodeType == "foursquare.com:venue" {
  1725				// TODO: temporary. remove this, or change
  1726				// when/where (time) we show these.  But these
  1727				// are flooding my results and I'm about to
  1728				// demo this.
  1729				return false, nil
  1730			}
  1731		}
  1732	
  1733		if c.ModTime != nil {
  1734			if corpus != nil {
  1735				mt, ok := corpus.PermanodeModtime(br)
  1736				if !ok || !c.ModTime.timeMatches(mt) {
  1737					return false, nil
  1738				}
  1739			} else if !c.ModTime.timeMatches(dp.ModTime) {
  1740				return false, nil
  1741			}
  1742		}
  1743	
  1744		if c.Time != nil {
  1745			if corpus != nil {
  1746				t, ok := corpus.PermanodeAnyTime(br)
  1747				if !ok || !c.Time.timeMatches(t) {
  1748					return false, nil
  1749				}
  1750			} else {
  1751				panic("TODO: not yet supported")
  1752			}
  1753		}
  1754	
  1755		if rc := c.Relation; rc != nil {
  1756			ok, err := rc.match(ctx, s, br, c.At)
  1757			if !ok || err != nil {
  1758				return ok, err
  1759			}
  1760		}
  1761	
  1762		if c.Location != nil || s.q.Sort == MapSort {
  1763			l, err := s.h.lh.PermanodeLocation(ctx, br, c.At, s.h.owner)
  1764			if c.Location != nil {
  1765				if err != nil {
  1766					if err != os.ErrNotExist {
  1767						log.Printf("PermanodeLocation(ref %s): %v", br, err)
  1768					}
  1769					return false, nil
  1770				}
  1771				if !c.Location.matchesLatLong(l.Latitude, l.Longitude) {
  1772					return false, nil
  1773				}
  1774			}
  1775			if err == nil {
  1776				s.loc[br] = l
  1777			}
  1778		}
  1779	
  1780		if cc := c.Continue; cc != nil {
  1781			if corpus == nil {
  1782				// Requires an in-memory index for infinite
  1783				// scroll. At least for now.
  1784				return false, nil
  1785			}
  1786			var pnTime time.Time
  1787			var ok bool
  1788			switch {
  1789			case !cc.LastMod.IsZero():
  1790				pnTime, ok = corpus.PermanodeModtime(br)
  1791				if !ok || pnTime.After(cc.LastMod) {
  1792					return false, nil
  1793				}
  1794			case !cc.LastCreated.IsZero():
  1795				pnTime, ok = corpus.PermanodeAnyTime(br)
  1796				if !ok || pnTime.After(cc.LastCreated) {
  1797					return false, nil
  1798				}
  1799			default:
  1800				panic("Continue constraint without a LastMod or a LastCreated")
  1801			}
  1802			// Blobs are sorted by modtime, and then by
  1803			// blobref, and then reversed overall.  From
  1804			// top of page, imagining this scenario, where
  1805			// the user requested a page size Limit of 4:
  1806			//     mod5, sha1-25
  1807			//     mod4, sha1-72
  1808			//     mod3, sha1-cc
  1809			//     mod3, sha1-bb <--- last seen item, continue = "pn:mod3:sha1-bb"
  1810			//     mod3, sha1-aa  <-- and we want this one next.
  1811			// In the case above, we'll see all of cc, bb, and cc for mod3.
  1812			if (pnTime.Equal(cc.LastMod) || pnTime.Equal(cc.LastCreated)) && !br.Less(cc.Last) {
  1813				return false, nil
  1814			}
  1815		}
  1816		return true, nil
  1817	}
  1818	
  1819	// permanodeMatchesAttrVals checks that the values in vals - all of them, if c.ValueAll is set -
  1820	// match the values for c.Attr.
  1821	// vals are the current permanode values of c.Attr.
  1822	func (c *PermanodeConstraint) permanodeMatchesAttrVals(ctx context.Context, s *search, vals []string) (bool, error) {
  1823		if c.NumValue != nil && !c.NumValue.intMatches(int64(len(vals))) {
  1824			return false, nil
  1825		}
  1826		if c.hasValueConstraint() {
  1827			nmatch := 0
  1828			for _, val := range vals {
  1829				match, err := c.permanodeMatchesAttrVal(ctx, s, val)
  1830				if err != nil {
  1831					return false, err
  1832				}
  1833				if match {
  1834					nmatch++
  1835				}
  1836			}
  1837			if nmatch == 0 {
  1838				return false, nil
  1839			}
  1840			if c.ValueAll {
  1841				return nmatch == len(vals), nil
  1842			}
  1843		}
  1844		return true, nil
  1845	}
  1846	
  1847	func (c *PermanodeConstraint) permanodeMatchesAttrVal(ctx context.Context, s *search, val string) (bool, error) {
  1848		if c.Value != "" && c.Value != val {
  1849			return false, nil
  1850		}
  1851		if c.ValueMatches != nil && !c.ValueMatches.stringMatches(val) {
  1852			return false, nil
  1853		}
  1854		if c.ValueMatchesInt != nil {
  1855			if i, err := strconv.ParseInt(val, 10, 64); err != nil || !c.ValueMatchesInt.intMatches(i) {
  1856				return false, nil
  1857			}
  1858		}
  1859		if c.ValueMatchesFloat != nil {
  1860			if f, err := strconv.ParseFloat(val, 64); err != nil || !c.ValueMatchesFloat.floatMatches(f) {
  1861				return false, nil
  1862			}
  1863		}
  1864		if subc := c.ValueInSet; subc != nil {
  1865			br, ok := blob.Parse(val) // TODO: use corpus's parse, or keep this as blob.Ref in corpus attr
  1866			if !ok {
  1867				return false, nil
  1868			}
  1869			meta, err := s.blobMeta(ctx, br)
  1870			if err == os.ErrNotExist {
  1871				return false, nil
  1872			}
  1873			if err != nil {
  1874				return false, err
  1875			}
  1876			return subc.matcher()(ctx, s, br, meta)
  1877		}
  1878		return true, nil
  1879	}
  1880	
  1881	func (c *FileConstraint) checkValid() error {
  1882		return nil
  1883	}
  1884	
  1885	func (c *FileConstraint) blobMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (ok bool, err error) {
  1886		if bm.CamliType != "file" {
  1887			return false, nil
  1888		}
  1889		fi, err := s.fileInfo(ctx, br)
  1890		if err == os.ErrNotExist {
  1891			return false, nil
  1892		}
  1893		if err != nil {
  1894			return false, err
  1895		}
  1896		if fs := c.FileSize; fs != nil && !fs.intMatches(fi.Size) {
  1897			return false, nil
  1898		}
  1899		if c.IsImage && !strings.HasPrefix(fi.MIMEType, "image/") {
  1900			return false, nil
  1901		}
  1902		if sc := c.FileName; sc != nil && !sc.stringMatches(fi.FileName) {
  1903			return false, nil
  1904		}
  1905		if sc := c.MIMEType; sc != nil && !sc.stringMatches(fi.MIMEType) {
  1906			return false, nil
  1907		}
  1908		if tc := c.Time; tc != nil {
  1909			if fi.Time == nil || !tc.timeMatches(fi.Time.Time()) {
  1910				return false, nil
  1911			}
  1912		}
  1913		if tc := c.ModTime; tc != nil {
  1914			if fi.ModTime == nil || !tc.timeMatches(fi.ModTime.Time()) {
  1915				return false, nil
  1916			}
  1917		}
  1918		if pc := c.ParentDir; pc != nil {
  1919			parents, err := s.parentDirs(ctx, br)
  1920			if err == os.ErrNotExist {
  1921				return false, nil
  1922			}
  1923			if err != nil {
  1924				return false, err
  1925			}
  1926			matches := false
  1927			for parent, _ := range parents {
  1928				meta, err := s.blobMeta(ctx, parent)
  1929				if err != nil {
  1930					if os.IsNotExist(err) {
  1931						continue
  1932					}
  1933					return false, err
  1934				}
  1935				ok, err := pc.blobMatches(ctx, s, parent, meta)
  1936				if err != nil {
  1937					return false, err
  1938				}
  1939				if ok {
  1940					matches = true
  1941					break
  1942				}
  1943			}
  1944			if !matches {
  1945				return false, nil
  1946			}
  1947		}
  1948		corpus := s.h.corpus
  1949		if c.WholeRef.Valid() {
  1950			if corpus == nil {
  1951				return false, nil
  1952			}
  1953			wholeRef, ok := corpus.GetWholeRef(ctx, br)
  1954			if !ok || wholeRef != c.WholeRef {
  1955				return false, nil
  1956			}
  1957		}
  1958		var width, height int64
  1959		if c.Width != nil || c.Height != nil || c.WHRatio != nil {
  1960			if corpus == nil {
  1961				return false, nil
  1962			}
  1963			imageInfo, err := corpus.GetImageInfo(ctx, br)
  1964			if err != nil {
  1965				if os.IsNotExist(err) {
  1966					return false, nil
  1967				}
  1968				return false, err
  1969			}
  1970			width = int64(imageInfo.Width)
  1971			height = int64(imageInfo.Height)
  1972		}
  1973		if c.Width != nil && !c.Width.intMatches(width) {
  1974			return false, nil
  1975		}
  1976		if c.Height != nil && !c.Height.intMatches(height) {
  1977			return false, nil
  1978		}
  1979		if c.WHRatio != nil && !c.WHRatio.floatMatches(float64(width)/float64(height)) {
  1980			return false, nil
  1981		}
  1982		if c.Location != nil {
  1983			if corpus == nil {
  1984				return false, nil
  1985			}
  1986			lat, long, found := corpus.FileLatLong(br)
  1987			if !found || !c.Location.matchesLatLong(lat, long) {
  1988				return false, nil
  1989			}
  1990			// If location was successfully matched, add the
  1991			// location to the global location area of results so
  1992			// a sort-by-map doesn't need to look it up again
  1993			// later.
  1994			s.loc[br] = camtypes.Location{
  1995				Latitude:  lat,
  1996				Longitude: long,
  1997			}
  1998		} else if s.q.Sort == MapSort {
  1999			if lat, long, found := corpus.FileLatLong(br); found {
  2000				s.loc[br] = camtypes.Location{
  2001					Latitude:  lat,
  2002					Longitude: long,
  2003				}
  2004			}
  2005		}
  2006		// this makes sure, in conjunction with TestQueryFileLocation, that we only
  2007		// expand the location iff the location matched AND the whole constraint matched as
  2008		// well.
  2009		if expandLocationHook {
  2010			return false, nil
  2011		}
  2012		if mt := c.MediaTag; mt != nil {
  2013			if corpus == nil {
  2014				return false, nil
  2015			}
  2016			var tagValue string
  2017			if mediaTags, err := corpus.GetMediaTags(ctx, br); err == nil && mt.Tag != "" {
  2018				tagValue = mediaTags[mt.Tag]
  2019			}
  2020			if mt.Int != nil {
  2021				if i, err := strconv.ParseInt(tagValue, 10, 64); err != nil || !mt.Int.intMatches(i) {
  2022					return false, nil
  2023				}
  2024			}
  2025			if mt.String != nil && !mt.String.stringMatches(tagValue) {
  2026				return false, nil
  2027			}
  2028		}
  2029		// TODO: EXIF timeconstraint
  2030		return true, nil
  2031	}
  2032	
  2033	func (c *TimeConstraint) timeMatches(t time.Time) bool {
  2034		if t.IsZero() {
  2035			return false
  2036		}
  2037		if !c.Before.IsAnyZero() {
  2038			if !t.Before(time.Time(c.Before)) {
  2039				return false
  2040			}
  2041		}
  2042		after := time.Time(c.After)
  2043		if after.IsZero() && c.InLast > 0 {
  2044			after = time.Now().Add(-c.InLast)
  2045		}
  2046		if !after.IsZero() {
  2047			if !(t.Equal(after) || t.After(after)) { // after is >=
  2048				return false
  2049			}
  2050		}
  2051		return true
  2052	}
  2053	
  2054	func (c *DirConstraint) checkValid() error {
  2055		if c == nil {
  2056			return nil
  2057		}
  2058		if c.Contains != nil && c.RecursiveContains != nil {
  2059			return errors.New("Contains and RecursiveContains in a DirConstraint are mutually exclusive")
  2060		}
  2061		return nil
  2062	}
  2063	
  2064	func (c *Constraint) isFileOrDirConstraint() bool {
  2065		if l := c.Logical; l != nil {
  2066			if l.Op == "not" {
  2067				return l.A.isFileOrDirConstraint() // l.B is nil
  2068			}
  2069			return l.A.isFileOrDirConstraint() && l.B.isFileOrDirConstraint()
  2070		}
  2071		return c.File != nil || c.Dir != nil
  2072	}
  2073	
  2074	func (c *Constraint) fileOrDirOrLogicalMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  2075		if cf := c.File; cf != nil {
  2076			return cf.blobMatches(ctx, s, br, bm)
  2077		}
  2078		if cd := c.Dir; cd != nil {
  2079			return cd.blobMatches(ctx, s, br, bm)
  2080		}
  2081		if l := c.Logical; l != nil {
  2082			return l.matcher()(ctx, s, br, bm)
  2083		}
  2084		return false, nil
  2085	}
  2086	
  2087	func (c *DirConstraint) blobMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  2088		if bm.CamliType != "directory" {
  2089			return false, nil
  2090		}
  2091		// TODO(mpl): I've added c.BlobRefPrefix, so that c.ParentDir can be directly
  2092		// matched against a blobRef (instead of e.g. a filename), but I could instead make
  2093		// ParentDir be a *Constraint, and logically enforce that it has to "be equivalent"
  2094		// to a ParentDir matching or a BlobRefPrefix matching. I think this here below is
  2095		// simpler, but not sure it's best in the long run.
  2096		if pfx := c.BlobRefPrefix; pfx != "" {
  2097			if !br.HasPrefix(pfx) {
  2098				return false, nil
  2099			}
  2100		}
  2101		fi, err := s.fileInfo(ctx, br)
  2102		if err == os.ErrNotExist {
  2103			return false, nil
  2104		}
  2105		if err != nil {
  2106			return false, err
  2107		}
  2108		if sc := c.FileName; sc != nil && !sc.stringMatches(fi.FileName) {
  2109			return false, nil
  2110		}
  2111		if pc := c.ParentDir; pc != nil {
  2112			parents, err := s.parentDirs(ctx, br)
  2113			if err == os.ErrNotExist {
  2114				return false, nil
  2115			}
  2116			if err != nil {
  2117				return false, err
  2118			}
  2119			isMatch, err := pc.hasMatchingParent(ctx, s, parents)
  2120			if err != nil {
  2121				return false, err
  2122			}
  2123			if !isMatch {
  2124				return false, nil
  2125			}
  2126		}
  2127	
  2128		// All constraints not pertaining to children must happen above
  2129		// this point.
  2130		children, err := s.dirChildren(ctx, br)
  2131		if err != nil && err != os.ErrNotExist {
  2132			return false, err
  2133		}
  2134		if fc := c.TopFileCount; fc != nil && !fc.intMatches(int64(len(children))) {
  2135			return false, nil
  2136		}
  2137		cc := c.Contains
  2138		recursive := false
  2139		if cc == nil {
  2140			if crc := c.RecursiveContains; crc != nil {
  2141				recursive = true
  2142				// RecursiveContains implies Contains
  2143				cc = crc
  2144			}
  2145		}
  2146		// First test on the direct children
  2147		containsMatch := false
  2148		if cc != nil {
  2149			// Allow directly specifying the fileRef
  2150			if cc.BlobRefPrefix != "" {
  2151				containsMatch, err = c.hasMatchingChild(ctx, s, children, func(ctx context.Context, s *search, child blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  2152					return child.HasPrefix(cc.BlobRefPrefix), nil
  2153				})
  2154			} else {
  2155				if !cc.isFileOrDirConstraint() {
  2156					return false, errors.New("[Recursive]Contains constraint should have a *FileConstraint, or a *DirConstraint, or a *LogicalConstraint combination of the aforementioned.")
  2157				}
  2158				containsMatch, err = c.hasMatchingChild(ctx, s, children, cc.fileOrDirOrLogicalMatches)
  2159			}
  2160			if err != nil {
  2161				return false, err
  2162			}
  2163			if !containsMatch && !recursive {
  2164				return false, nil
  2165			}
  2166		}
  2167		// Then if needed recurse on the next generation descendants.
  2168		if !containsMatch && recursive {
  2169			match, err := c.hasMatchingChild(ctx, s, children, c.blobMatches)
  2170			if err != nil {
  2171				return false, err
  2172			}
  2173			if !match {
  2174				return false, nil
  2175			}
  2176		}
  2177	
  2178		// TODO: implement FileCount and FileSize.
  2179	
  2180		return true, nil
  2181	}
  2182	
  2183	// hasMatchingParent checks all parents against c and returns true as soon as one of
  2184	// them matches, or returns false if none of them is a match.
  2185	func (c *DirConstraint) hasMatchingParent(ctx context.Context, s *search, parents map[blob.Ref]struct{}) (bool, error) {
  2186		for parent := range parents {
  2187			meta, err := s.blobMeta(ctx, parent)
  2188			if err != nil {
  2189				if os.IsNotExist(err) {
  2190					continue
  2191				}
  2192				return false, err
  2193			}
  2194			ok, err := c.blobMatches(ctx, s, parent, meta)
  2195			if err != nil {
  2196				return false, err
  2197			}
  2198			if ok {
  2199				return true, nil
  2200			}
  2201		}
  2202		return false, nil
  2203	}
  2204	
  2205	// hasMatchingChild runs matcher against each child and returns true as soon as
  2206	// there is a match, of false if none of them is a match.
  2207	func (c *DirConstraint) hasMatchingChild(ctx context.Context, s *search, children map[blob.Ref]struct{},
  2208		matcher func(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error)) (bool, error) {
  2209		// TODO(mpl): See if we're guaranteed to be CPU-bound (i.e. all resources are in
  2210		// corpus), and if not, add some concurrency to spread costly index lookups.
  2211		for child, _ := range children {
  2212			meta, err := s.blobMeta(ctx, child)
  2213			if err != nil {
  2214				if os.IsNotExist(err) {
  2215					continue
  2216				}
  2217				return false, err
  2218			}
  2219			ok, err := matcher(ctx, s, child, meta)
  2220			if err != nil {
  2221				return false, err
  2222			}
  2223			if ok {
  2224				return true, nil
  2225			}
  2226		}
  2227		return false, nil
  2228	}
  2229	
  2230	type sortSearchResultBlobs struct {
  2231		s    []*SearchResultBlob
  2232		less func(a, b *SearchResultBlob) bool
  2233	}
  2234	
  2235	func (ss sortSearchResultBlobs) Len() int           { return len(ss.s) }
  2236	func (ss sortSearchResultBlobs) Swap(i, j int)      { ss.s[i], ss.s[j] = ss.s[j], ss.s[i] }
  2237	func (ss sortSearchResultBlobs) Less(i, j int) bool { return ss.less(ss.s[i], ss.s[j]) }
Website layout inspired by memcached.
Content by the authors.