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