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/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: %v", expr, err)
   256		}
   257		if err := sq.Constraint.checkValid(); err != nil {
   258			return nil, fmt.Errorf("Internal error: parseExpression(%q) returned invalid constraint: %v", 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: %v", 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					if len(res.Blobs) == q.Limit {
  1053						return false
  1054					}
  1055					return true
  1056				}
  1057				if q.Around == meta.Ref {
  1058					foundAround = true
  1059					if len(res.Blobs)*2 > q.Limit {
  1060						// If we've already collected more than half of the Limit when Around is found,
  1061						// we ditch the surplus from the beginning of the slice of results.
  1062						// If Limit is even, and the number of results before and after Around
  1063						// are both greater than half the limit, then there will be one more result before
  1064						// than after.
  1065						discard := len(res.Blobs) - q.Limit/2 - 1
  1066						if discard < 0 {
  1067							discard = 0
  1068						}
  1069						res.Blobs = res.Blobs[discard:]
  1070					}
  1071					if len(res.Blobs) == q.Limit {
  1072						return false
  1073					}
  1074					return true
  1075				}
  1076				if len(res.Blobs) == q.Limit {
  1077					n := copy(res.Blobs, res.Blobs[len(res.Blobs)/2:])
  1078					res.Blobs = res.Blobs[:n]
  1079				}
  1080			}
  1081			return true
  1082		})
  1083		if enumErr != nil {
  1084			return nil, enumErr
  1085		}
  1086		if wantAround && !foundAround {
  1087			// results are ignored if Around was not found
  1088			res.Blobs = nil
  1089		}
  1090		if !cands.sorted {
  1091			switch q.Sort {
  1092			// TODO(mpl): maybe someday we'll want both a sort, and then the MapSort
  1093			// selection, as MapSort is technically not really a sort. In which case, MapSort
  1094			// should probably become e.g. another field of SearchQuery.
  1095			case UnspecifiedSort, Unsorted, MapSort:
  1096				// Nothing to do.
  1097			case BlobRefAsc:
  1098				sort.Sort(sortSearchResultBlobs{res.Blobs, func(a, b *SearchResultBlob) bool {
  1099					return a.Blob.Less(b.Blob)
  1100				}})
  1101			case CreatedDesc, CreatedAsc:
  1102				if corpus == nil {
  1103					return nil, errors.New("TODO: Sorting without a corpus unsupported")
  1104				}
  1105				if !q.Constraint.onlyMatchesPermanode() {
  1106					return nil, errors.New("can only sort by ctime when all results are permanodes")
  1107				}
  1108				var err error
  1109				sort.Sort(sortSearchResultBlobs{res.Blobs, func(a, b *SearchResultBlob) bool {
  1110					if err != nil {
  1111						return false
  1112					}
  1113					ta, ok := corpus.PermanodeAnyTime(a.Blob)
  1114					if !ok {
  1115						err = fmt.Errorf("no ctime or modtime found for %v", a.Blob)
  1116						return false
  1117					}
  1118					tb, ok := corpus.PermanodeAnyTime(b.Blob)
  1119					if !ok {
  1120						err = fmt.Errorf("no ctime or modtime found for %v", b.Blob)
  1121						return false
  1122					}
  1123					if q.Sort == CreatedAsc {
  1124						return ta.Before(tb)
  1125					}
  1126					return tb.Before(ta)
  1127				}})
  1128				if err != nil {
  1129					return nil, err
  1130				}
  1131			// TODO(mpl): LastModifiedDesc, LastModifiedAsc
  1132			default:
  1133				return nil, errors.New("TODO: unsupported sort+query combination.")
  1134			}
  1135			if q.Sort != MapSort {
  1136				if q.Limit > 0 && len(res.Blobs) > q.Limit {
  1137					if wantAround {
  1138						aroundPos := sort.Search(len(res.Blobs), func(i int) bool {
  1139							return res.Blobs[i].Blob.String() >= q.Around.String()
  1140						})
  1141						// If we got this far, we know q.Around is in the results, so this below should
  1142						// never happen
  1143						if aroundPos == len(res.Blobs) || res.Blobs[aroundPos].Blob != q.Around {
  1144							panic("q.Around blobRef should be in the results")
  1145						}
  1146						lowerBound := aroundPos - q.Limit/2
  1147						if lowerBound < 0 {
  1148							lowerBound = 0
  1149						}
  1150						upperBound := lowerBound + q.Limit
  1151						if upperBound > len(res.Blobs) {
  1152							upperBound = len(res.Blobs)
  1153						}
  1154						res.Blobs = res.Blobs[lowerBound:upperBound]
  1155					} else {
  1156						res.Blobs = res.Blobs[:q.Limit]
  1157					}
  1158				}
  1159			}
  1160		}
  1161		if corpus != nil {
  1162			if !wantAround {
  1163				q.setResultContinue(corpus, res)
  1164			}
  1165		}
  1166	
  1167		// Populate s.res.LocationArea
  1168		{
  1169			var la camtypes.LocationBounds
  1170			for _, v := range res.Blobs {
  1171				br := v.Blob
  1172				loc, ok := s.loc[br]
  1173				if !ok {
  1174					continue
  1175				}
  1176				la = la.Expand(loc)
  1177			}
  1178			if la != (camtypes.LocationBounds{}) {
  1179				s.res.LocationArea = &la
  1180			}
  1181		}
  1182	
  1183		if q.Sort == MapSort {
  1184			bestByLocation(s.res, s.loc, q.Limit)
  1185		}
  1186	
  1187		if q.Describe != nil {
  1188			q.Describe.BlobRef = blob.Ref{} // zero this out, if caller set it
  1189			blobs := make([]blob.Ref, 0, len(res.Blobs))
  1190			for _, srb := range res.Blobs {
  1191				blobs = append(blobs, srb.Blob)
  1192			}
  1193			q.Describe.BlobRefs = blobs
  1194			t0 := time.Now()
  1195			res, err := s.h.DescribeLocked(ctx, q.Describe)
  1196			if debugQuerySpeed {
  1197				log.Printf("Describe of %d blobs = %v", len(blobs), time.Since(t0))
  1198			}
  1199			if err != nil {
  1200				return nil, err
  1201			}
  1202			s.res.Describe = res
  1203		}
  1204	
  1205		return s.res, nil
  1206	}
  1207	
  1208	// mapCell is which cell of an NxN cell grid of a map a point is in.
  1209	// The numbering is arbitrary but dense, starting with 0.
  1210	type mapCell int
  1211	
  1212	// mapGrids contains 1 or 2 mapGrids, depending on whether the search
  1213	// area cross the dateline.
  1214	type mapGrids []*mapGrid
  1215	
  1216	func (gs mapGrids) cellOf(loc camtypes.Location) mapCell {
  1217		for i, g := range gs {
  1218			cell, ok := g.cellOf(loc)
  1219			if ok {
  1220				return cell + mapCell(i*g.dim*g.dim)
  1221			}
  1222		}
  1223		return 0 // shouldn't happen, unless loc is malformed, in which case this is fine.
  1224	}
  1225	
  1226	func newMapGrids(area camtypes.LocationBounds, dim int) mapGrids {
  1227		if !area.SpansDateLine() {
  1228			return mapGrids{newMapGrid(area, dim)}
  1229		}
  1230		return mapGrids{
  1231			newMapGrid(camtypes.LocationBounds{
  1232				North: area.North,
  1233				South: area.South,
  1234				West:  area.West,
  1235				East:  180,
  1236			}, dim),
  1237			newMapGrid(camtypes.LocationBounds{
  1238				North: area.North,
  1239				South: area.South,
  1240				West:  -180,
  1241				East:  area.East,
  1242			}, dim),
  1243		}
  1244	}
  1245	
  1246	type mapGrid struct {
  1247		dim        int // grid is dim*dim cells
  1248		area       camtypes.LocationBounds
  1249		cellWidth  float64
  1250		cellHeight float64
  1251	}
  1252	
  1253	// newMapGrid returns a grid matcher over an area. The area must not
  1254	// span the date line. The mapGrid maps locations to a grid of (dim *
  1255	// dim) cells.
  1256	func newMapGrid(area camtypes.LocationBounds, dim int) *mapGrid {
  1257		if area.SpansDateLine() {
  1258			panic("invalid use of newMapGrid: must be called with bounds not overlapping date line")
  1259		}
  1260		return &mapGrid{
  1261			dim:        dim,
  1262			area:       area,
  1263			cellWidth:  area.Width() / float64(dim),
  1264			cellHeight: (area.North - area.South) / float64(dim),
  1265		}
  1266	}
  1267	
  1268	func (g *mapGrid) cellOf(loc camtypes.Location) (c mapCell, ok bool) {
  1269		if loc.Latitude > g.area.North || loc.Latitude < g.area.South ||
  1270			loc.Longitude < g.area.West || loc.Longitude > g.area.East {
  1271			return
  1272		}
  1273		x := int((loc.Longitude - g.area.West) / g.cellWidth)
  1274		y := int((g.area.North - loc.Latitude) / g.cellHeight)
  1275		if x >= g.dim {
  1276			x = g.dim - 1
  1277		}
  1278		if y >= g.dim {
  1279			y = g.dim - 1
  1280		}
  1281		return mapCell(y*g.dim + x), true
  1282	}
  1283	
  1284	// bestByLocation conditionally modifies res.Blobs if the number of blobs
  1285	// is greater than limit. If so, it modifies res.Blobs so only `limit`
  1286	// blobs remain, selecting those such that the results are evenly spread
  1287	// over the result's map area.
  1288	//
  1289	// The algorithm is the following:
  1290	// 1) We know the size and position of the relevant area because
  1291	// res.LocationArea was built during blob matching
  1292	// 2) We divide the area in a grid of ~sqrt(limit) lines and columns, which is
  1293	// represented by a map[camtypes.LocationBounds][]blob.Ref
  1294	// 3) For each described blobRef we place it in the cell matching its location.
  1295	// Each cell is bounded by limit though.
  1296	// 4) We compute the max number of nodes per cell:
  1297	// N = (number of non empty cells) / limit
  1298	// 5) for each cell, append to the set of selected nodes the first N nodes of
  1299	// the cell.
  1300	func bestByLocation(res *SearchResult, locm map[blob.Ref]camtypes.Location, limit int) {
  1301		// Calculate res.LocationArea.
  1302		if len(res.Blobs) <= limit {
  1303			return
  1304		}
  1305	
  1306		if res.LocationArea == nil {
  1307			// No even one result node with a location was found.
  1308			return
  1309		}
  1310	
  1311		// Divide location area in a grid of (dim * dim) map cells,
  1312		// such that (dim * dim) is approximately the given limit,
  1313		// then track which search results are in which cell.
  1314		cellOccupants := make(map[mapCell][]blob.Ref)
  1315		dim := int(math.Round(math.Sqrt(float64(limit))))
  1316		if dim < 3 {
  1317			dim = 3
  1318		} else if dim > 100 {
  1319			dim = 100
  1320		}
  1321		grids := newMapGrids(*res.LocationArea, dim)
  1322	
  1323		resBlob := map[blob.Ref]*SearchResultBlob{}
  1324		for _, srb := range res.Blobs {
  1325			br := srb.Blob
  1326			loc, ok := locm[br]
  1327			if !ok {
  1328				continue
  1329			}
  1330			cellKey := grids.cellOf(loc)
  1331			occupants := cellOccupants[cellKey]
  1332			if len(occupants) >= limit {
  1333				// no sense in filling a cell to more than our overall limit
  1334				continue
  1335			}
  1336			cellOccupants[cellKey] = append(occupants, br)
  1337			resBlob[br] = srb
  1338		}
  1339	
  1340		var nodesKept []*SearchResultBlob
  1341		for {
  1342			for cellKey, occupants := range cellOccupants {
  1343				nodesKept = append(nodesKept, resBlob[occupants[0]])
  1344				if len(nodesKept) == limit {
  1345					res.Blobs = nodesKept
  1346					return
  1347				}
  1348				if len(occupants) == 1 {
  1349					delete(cellOccupants, cellKey)
  1350				} else {
  1351					cellOccupants[cellKey] = occupants[1:]
  1352				}
  1353			}
  1354	
  1355		}
  1356	}
  1357	
  1358	// setResultContinue sets res.Continue if q is suitable for having a continue token.
  1359	// The corpus is locked for reads.
  1360	func (q *SearchQuery) setResultContinue(corpus *index.Corpus, res *SearchResult) {
  1361		if !q.Constraint.onlyMatchesPermanode() {
  1362			return
  1363		}
  1364		var pnTimeFunc func(blob.Ref) (t time.Time, ok bool)
  1365		switch q.Sort {
  1366		case LastModifiedDesc:
  1367			pnTimeFunc = corpus.PermanodeModtime
  1368		case CreatedDesc:
  1369			pnTimeFunc = corpus.PermanodeAnyTime
  1370		default:
  1371			return
  1372		}
  1373	
  1374		if q.Limit <= 0 || len(res.Blobs) != q.Limit {
  1375			return
  1376		}
  1377		lastpn := res.Blobs[len(res.Blobs)-1].Blob
  1378		t, ok := pnTimeFunc(lastpn)
  1379		if !ok {
  1380			return
  1381		}
  1382		res.Continue = fmt.Sprintf("pn:%d:%v", t.UnixNano(), lastpn)
  1383	}
  1384	
  1385	type matchFn func(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error)
  1386	
  1387	func alwaysMatch(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error) {
  1388		return true, nil
  1389	}
  1390	
  1391	func neverMatch(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error) {
  1392		return false, nil
  1393	}
  1394	
  1395	func anyCamliType(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1396		return bm.CamliType != "", nil
  1397	}
  1398	
  1399	// Test hooks.
  1400	var (
  1401		candSourceHook     func(string)
  1402		expandLocationHook bool
  1403	)
  1404	
  1405	type candidateSource struct {
  1406		name   string
  1407		sorted bool
  1408	
  1409		// sends sends to the channel and must close it, regardless of error
  1410		// or interruption from context.Done().
  1411		send func(context.Context, *search, func(camtypes.BlobMeta) bool) error
  1412	}
  1413	
  1414	func (q *SearchQuery) pickCandidateSource(s *search) (src candidateSource) {
  1415		c := q.Constraint
  1416		corpus := s.h.corpus
  1417		if corpus != nil {
  1418			if c.onlyMatchesPermanode() {
  1419				src.sorted = true
  1420				switch q.Sort {
  1421				case LastModifiedDesc:
  1422					src.name = "corpus_permanode_lastmod"
  1423					src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1424						corpus.EnumeratePermanodesLastModified(fn)
  1425						return nil
  1426					}
  1427					return
  1428				case CreatedDesc:
  1429					src.name = "corpus_permanode_created"
  1430					src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1431						corpus.EnumeratePermanodesCreated(fn, true)
  1432						return nil
  1433					}
  1434					return
  1435				default:
  1436					src.sorted = false
  1437					if typs := c.matchesPermanodeTypes(); len(typs) != 0 {
  1438						src.name = "corpus_permanode_types"
  1439						src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1440							corpus.EnumeratePermanodesByNodeTypes(fn, typs)
  1441							return nil
  1442						}
  1443						return
  1444					}
  1445				}
  1446			}
  1447			if br := c.matchesAtMostOneBlob(); br.Valid() {
  1448				src.name = "one_blob"
  1449				src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1450					corpus.EnumerateSingleBlob(fn, br)
  1451					return nil
  1452				}
  1453				return
  1454			}
  1455			// fastpath for files
  1456			if c.matchesFileByWholeRef() {
  1457				src.name = "corpus_file_meta"
  1458				src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1459					corpus.EnumerateCamliBlobs(schema.TypeFile, fn)
  1460					return nil
  1461				}
  1462				return
  1463			}
  1464			if c.AnyCamliType || c.CamliType != "" {
  1465				camType := c.CamliType // empty means all
  1466				src.name = "corpus_blob_meta"
  1467				src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1468					corpus.EnumerateCamliBlobs(camType, fn)
  1469					return nil
  1470				}
  1471				return
  1472			}
  1473		}
  1474		src.name = "index_blob_meta"
  1475		src.send = func(ctx context.Context, s *search, fn func(camtypes.BlobMeta) bool) error {
  1476			return s.h.index.EnumerateBlobMeta(ctx, fn)
  1477		}
  1478		return
  1479	}
  1480	
  1481	type allMustMatch []matchFn
  1482	
  1483	func (fns allMustMatch) blobMatches(ctx context.Context, s *search, br blob.Ref, blobMeta camtypes.BlobMeta) (bool, error) {
  1484		for _, condFn := range fns {
  1485			match, err := condFn(ctx, s, br, blobMeta)
  1486			if !match || err != nil {
  1487				return match, err
  1488			}
  1489		}
  1490		return true, nil
  1491	}
  1492	
  1493	func (c *Constraint) matcher() func(ctx context.Context, s *search, br blob.Ref, blobMeta camtypes.BlobMeta) (bool, error) {
  1494		c.matcherOnce.Do(c.initMatcherFn)
  1495		return c.matcherFn
  1496	}
  1497	
  1498	func (c *Constraint) initMatcherFn() {
  1499		c.matcherFn = c.genMatcher()
  1500	}
  1501	
  1502	func (c *Constraint) genMatcher() matchFn {
  1503		var ncond int
  1504		var cond matchFn
  1505		var conds []matchFn
  1506		addCond := func(fn matchFn) {
  1507			ncond++
  1508			if ncond == 1 {
  1509				cond = fn
  1510				return
  1511			} else if ncond == 2 {
  1512				conds = append(conds, cond)
  1513			}
  1514			conds = append(conds, fn)
  1515		}
  1516		if c.Logical != nil {
  1517			addCond(c.Logical.matcher())
  1518		}
  1519		if c.Anything {
  1520			addCond(alwaysMatch)
  1521		}
  1522		if c.CamliType != "" {
  1523			addCond(func(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1524				return bm.CamliType == c.CamliType, nil
  1525			})
  1526		}
  1527		if c.AnyCamliType {
  1528			addCond(anyCamliType)
  1529		}
  1530		if c.Permanode != nil {
  1531			addCond(c.Permanode.blobMatches)
  1532		}
  1533		// TODO: ClaimConstraint
  1534		if c.File != nil {
  1535			addCond(c.File.blobMatches)
  1536		}
  1537		if c.Dir != nil {
  1538			addCond(c.Dir.blobMatches)
  1539		}
  1540		if bs := c.BlobSize; bs != nil {
  1541			addCond(func(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1542				return bs.intMatches(int64(bm.Size)), nil
  1543			})
  1544		}
  1545		if pfx := c.BlobRefPrefix; pfx != "" {
  1546			addCond(func(ctx context.Context, s *search, br blob.Ref, meta camtypes.BlobMeta) (bool, error) {
  1547				return br.HasPrefix(pfx), nil
  1548			})
  1549		}
  1550		switch ncond {
  1551		case 0:
  1552			return neverMatch
  1553		case 1:
  1554			return cond
  1555		default:
  1556			return allMustMatch(conds).blobMatches
  1557		}
  1558	}
  1559	
  1560	func (c *LogicalConstraint) checkValid() error {
  1561		if c == nil {
  1562			return nil
  1563		}
  1564		if c.A == nil {
  1565			return errors.New("In LogicalConstraint, need to set A")
  1566		}
  1567		if err := c.A.checkValid(); err != nil {
  1568			return err
  1569		}
  1570		switch c.Op {
  1571		case "and", "xor", "or":
  1572			if c.B == nil {
  1573				return errors.New("In LogicalConstraint, need both A and B set")
  1574			}
  1575			if err := c.B.checkValid(); err != nil {
  1576				return err
  1577			}
  1578		case "not":
  1579		default:
  1580			return fmt.Errorf("In LogicalConstraint, unknown operation %q", c.Op)
  1581		}
  1582		return nil
  1583	}
  1584	
  1585	func (c *LogicalConstraint) matcher() matchFn {
  1586		amatches := c.A.matcher()
  1587		var bmatches matchFn
  1588		if c.Op != "not" {
  1589			bmatches = c.B.matcher()
  1590		}
  1591		return func(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  1592	
  1593			// Note: not using multiple goroutines here, because
  1594			// so far the *search type assumes it's
  1595			// single-threaded. (e.g. the .ss scratch type).
  1596			// Also, not using multiple goroutines means we can
  1597			// short-circuit when Op == "and" and av is false.
  1598	
  1599			av, err := amatches(ctx, s, br, bm)
  1600			if err != nil {
  1601				return false, err
  1602			}
  1603			switch c.Op {
  1604			case "not":
  1605				return !av, nil
  1606			case "and":
  1607				if !av {
  1608					// Short-circuit.
  1609					return false, nil
  1610				}
  1611			case "or":
  1612				if av {
  1613					// Short-circuit.
  1614					return true, nil
  1615				}
  1616			}
  1617	
  1618			bv, err := bmatches(ctx, s, br, bm)
  1619			if err != nil {
  1620				return false, err
  1621			}
  1622	
  1623			switch c.Op {
  1624			case "and", "or":
  1625				return bv, nil
  1626			case "xor":
  1627				return av != bv, nil
  1628			}
  1629			panic("unreachable")
  1630		}
  1631	}
  1632	
  1633	func (c *PermanodeConstraint) checkValid() error {
  1634		if c == nil {
  1635			return nil
  1636		}
  1637		if c.Attr != "" {
  1638			if c.NumValue == nil && !c.hasValueConstraint() {
  1639				return errors.New("PermanodeConstraint with Attr requires also setting NumValue or a value-matching constraint")
  1640			}
  1641			if nv := c.NumValue; nv != nil {
  1642				if nv.ZeroMin {
  1643					return errors.New("NumValue with ZeroMin makes no sense; matches everything")
  1644				}
  1645				if nv.ZeroMax && c.hasValueConstraint() {
  1646					return errors.New("NumValue with ZeroMax makes no sense in conjunction with a value-matching constraint; matches nothing")
  1647				}
  1648				if nv.Min < 0 || nv.Max < 0 {
  1649					return errors.New("NumValue with negative Min or Max makes no sense")
  1650				}
  1651			}
  1652		}
  1653		if rc := c.Relation; rc != nil {
  1654			if err := rc.checkValid(); err != nil {
  1655				return err
  1656			}
  1657		}
  1658		if pcc := c.Continue; pcc != nil {
  1659			if err := pcc.checkValid(); err != nil {
  1660				return err
  1661			}
  1662		}
  1663		return nil
  1664	}
  1665	
  1666	var numPermanodeFields = reflect.TypeOf(PermanodeConstraint{}).NumField()
  1667	
  1668	// hasValueConstraint returns true if one or more constraints that check an attribute's value are set.
  1669	func (c *PermanodeConstraint) hasValueConstraint() bool {
  1670		// If a field has been added or removed, update this after adding the new field to the return statement if necessary.
  1671		const expectedFields = 15
  1672		if numPermanodeFields != expectedFields {
  1673			panic(fmt.Sprintf("PermanodeConstraint field count changed (now %v rather than %v)", numPermanodeFields, expectedFields))
  1674		}
  1675		return c.Value != "" ||
  1676			c.ValueMatches != nil ||
  1677			c.ValueMatchesInt != nil ||
  1678			c.ValueMatchesFloat != nil ||
  1679			c.ValueInSet != nil
  1680	}
  1681	
  1682	func (c *PermanodeConstraint) blobMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (ok bool, err error) {
  1683		if bm.CamliType != schema.TypePermanode {
  1684			return false, nil
  1685		}
  1686		corpus := s.h.corpus
  1687	
  1688		var dp *DescribedPermanode
  1689		if corpus == nil {
  1690			dr, err := s.h.DescribeLocked(ctx, &DescribeRequest{BlobRef: br})
  1691			if err != nil {
  1692				return false, err
  1693			}
  1694			db := dr.Meta[br.String()]
  1695			if db == nil || db.Permanode == nil {
  1696				return false, nil
  1697			}
  1698			dp = db.Permanode
  1699		}
  1700	
  1701		if c.Attr != "" {
  1702			if !c.At.IsZero() && corpus == nil {
  1703				panic("PermanodeConstraint.At not supported without an in-memory corpus")
  1704			}
  1705			var vals []string
  1706			if corpus == nil {
  1707				vals = dp.Attr[c.Attr]
  1708			} else {
  1709				s.ss = corpus.AppendPermanodeAttrValues(
  1710					s.ss[:0], br, c.Attr, c.At, s.h.owner.KeyID())
  1711				vals = s.ss
  1712			}
  1713			ok, err := c.permanodeMatchesAttrVals(ctx, s, vals)
  1714			if !ok || err != nil {
  1715				return false, err
  1716			}
  1717		}
  1718	
  1719		if c.SkipHidden && corpus != nil {
  1720			defVis := corpus.PermanodeAttrValue(br, "camliDefVis", c.At, s.h.owner.KeyID())
  1721			if defVis == "hide" {
  1722				return false, nil
  1723			}
  1724			nodeType := corpus.PermanodeAttrValue(br, "camliNodeType", c.At, s.h.owner.KeyID())
  1725			if nodeType == "foursquare.com:venue" {
  1726				// TODO: temporary. remove this, or change
  1727				// when/where (time) we show these.  But these
  1728				// are flooding my results and I'm about to
  1729				// demo this.
  1730				return false, nil
  1731			}
  1732		}
  1733	
  1734		if c.ModTime != nil {
  1735			if corpus != nil {
  1736				mt, ok := corpus.PermanodeModtime(br)
  1737				if !ok || !c.ModTime.timeMatches(mt) {
  1738					return false, nil
  1739				}
  1740			} else if !c.ModTime.timeMatches(dp.ModTime) {
  1741				return false, nil
  1742			}
  1743		}
  1744	
  1745		if c.Time != nil {
  1746			if corpus != nil {
  1747				t, ok := corpus.PermanodeAnyTime(br)
  1748				if !ok || !c.Time.timeMatches(t) {
  1749					return false, nil
  1750				}
  1751			} else {
  1752				panic("TODO: not yet supported")
  1753			}
  1754		}
  1755	
  1756		if rc := c.Relation; rc != nil {
  1757			ok, err := rc.match(ctx, s, br, c.At)
  1758			if !ok || err != nil {
  1759				return ok, err
  1760			}
  1761		}
  1762	
  1763		if c.Location != nil || s.q.Sort == MapSort {
  1764			l, err := s.h.lh.PermanodeLocation(ctx, br, c.At, s.h.owner)
  1765			if c.Location != nil {
  1766				if err != nil {
  1767					if err != os.ErrNotExist {
  1768						log.Printf("PermanodeLocation(ref %s): %v", br, err)
  1769					}
  1770					return false, nil
  1771				}
  1772				if !c.Location.matchesLatLong(l.Latitude, l.Longitude) {
  1773					return false, nil
  1774				}
  1775			}
  1776			if err == nil {
  1777				s.loc[br] = l
  1778			}
  1779		}
  1780	
  1781		if cc := c.Continue; cc != nil {
  1782			if corpus == nil {
  1783				// Requires an in-memory index for infinite
  1784				// scroll. At least for now.
  1785				return false, nil
  1786			}
  1787			var pnTime time.Time
  1788			var ok bool
  1789			switch {
  1790			case !cc.LastMod.IsZero():
  1791				pnTime, ok = corpus.PermanodeModtime(br)
  1792				if !ok || pnTime.After(cc.LastMod) {
  1793					return false, nil
  1794				}
  1795			case !cc.LastCreated.IsZero():
  1796				pnTime, ok = corpus.PermanodeAnyTime(br)
  1797				if !ok || pnTime.After(cc.LastCreated) {
  1798					return false, nil
  1799				}
  1800			default:
  1801				panic("Continue constraint without a LastMod or a LastCreated")
  1802			}
  1803			// Blobs are sorted by modtime, and then by
  1804			// blobref, and then reversed overall.  From
  1805			// top of page, imagining this scenario, where
  1806			// the user requested a page size Limit of 4:
  1807			//     mod5, sha1-25
  1808			//     mod4, sha1-72
  1809			//     mod3, sha1-cc
  1810			//     mod3, sha1-bb <--- last seen item, continue = "pn:mod3:sha1-bb"
  1811			//     mod3, sha1-aa  <-- and we want this one next.
  1812			// In the case above, we'll see all of cc, bb, and cc for mod3.
  1813			if (pnTime.Equal(cc.LastMod) || pnTime.Equal(cc.LastCreated)) && !br.Less(cc.Last) {
  1814				return false, nil
  1815			}
  1816		}
  1817		return true, nil
  1818	}
  1819	
  1820	// permanodeMatchesAttrVals checks that the values in vals - all of them, if c.ValueAll is set -
  1821	// match the values for c.Attr.
  1822	// vals are the current permanode values of c.Attr.
  1823	func (c *PermanodeConstraint) permanodeMatchesAttrVals(ctx context.Context, s *search, vals []string) (bool, error) {
  1824		if c.NumValue != nil && !c.NumValue.intMatches(int64(len(vals))) {
  1825			return false, nil
  1826		}
  1827		if c.hasValueConstraint() {
  1828			nmatch := 0
  1829			for _, val := range vals {
  1830				match, err := c.permanodeMatchesAttrVal(ctx, s, val)
  1831				if err != nil {
  1832					return false, err
  1833				}
  1834				if match {
  1835					nmatch++
  1836				}
  1837			}
  1838			if nmatch == 0 {
  1839				return false, nil
  1840			}
  1841			if c.ValueAll {
  1842				return nmatch == len(vals), nil
  1843			}
  1844		}
  1845		return true, nil
  1846	}
  1847	
  1848	func (c *PermanodeConstraint) permanodeMatchesAttrVal(ctx context.Context, s *search, val string) (bool, error) {
  1849		if c.Value != "" && c.Value != val {
  1850			return false, nil
  1851		}
  1852		if c.ValueMatches != nil && !c.ValueMatches.stringMatches(val) {
  1853			return false, nil
  1854		}
  1855		if c.ValueMatchesInt != nil {
  1856			if i, err := strconv.ParseInt(val, 10, 64); err != nil || !c.ValueMatchesInt.intMatches(i) {
  1857				return false, nil
  1858			}
  1859		}
  1860		if c.ValueMatchesFloat != nil {
  1861			if f, err := strconv.ParseFloat(val, 64); err != nil || !c.ValueMatchesFloat.floatMatches(f) {
  1862				return false, nil
  1863			}
  1864		}
  1865		if subc := c.ValueInSet; subc != nil {
  1866			br, ok := blob.Parse(val) // TODO: use corpus's parse, or keep this as blob.Ref in corpus attr
  1867			if !ok {
  1868				return false, nil
  1869			}
  1870			meta, err := s.blobMeta(ctx, br)
  1871			if err == os.ErrNotExist {
  1872				return false, nil
  1873			}
  1874			if err != nil {
  1875				return false, err
  1876			}
  1877			return subc.matcher()(ctx, s, br, meta)
  1878		}
  1879		return true, nil
  1880	}
  1881	
  1882	func (c *FileConstraint) checkValid() error {
  1883		return nil
  1884	}
  1885	
  1886	func (c *FileConstraint) blobMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (ok bool, err error) {
  1887		if bm.CamliType != "file" {
  1888			return false, nil
  1889		}
  1890		fi, err := s.fileInfo(ctx, br)
  1891		if err == os.ErrNotExist {
  1892			return false, nil
  1893		}
  1894		if err != nil {
  1895			return false, err
  1896		}
  1897		if fs := c.FileSize; fs != nil && !fs.intMatches(fi.Size) {
  1898			return false, nil
  1899		}
  1900		if c.IsImage && !strings.HasPrefix(fi.MIMEType, "image/") {
  1901			return false, nil
  1902		}
  1903		if sc := c.FileName; sc != nil && !sc.stringMatches(fi.FileName) {
  1904			return false, nil
  1905		}
  1906		if sc := c.MIMEType; sc != nil && !sc.stringMatches(fi.MIMEType) {
  1907			return false, nil
  1908		}
  1909		if tc := c.Time; tc != nil {
  1910			if fi.Time == nil || !tc.timeMatches(fi.Time.Time()) {
  1911				return false, nil
  1912			}
  1913		}
  1914		if tc := c.ModTime; tc != nil {
  1915			if fi.ModTime == nil || !tc.timeMatches(fi.ModTime.Time()) {
  1916				return false, nil
  1917			}
  1918		}
  1919		if pc := c.ParentDir; pc != nil {
  1920			parents, err := s.parentDirs(ctx, br)
  1921			if err == os.ErrNotExist {
  1922				return false, nil
  1923			}
  1924			if err != nil {
  1925				return false, err
  1926			}
  1927			matches := false
  1928			for parent, _ := range parents {
  1929				meta, err := s.blobMeta(ctx, parent)
  1930				if err != nil {
  1931					if os.IsNotExist(err) {
  1932						continue
  1933					}
  1934					return false, err
  1935				}
  1936				ok, err := pc.blobMatches(ctx, s, parent, meta)
  1937				if err != nil {
  1938					return false, err
  1939				}
  1940				if ok {
  1941					matches = true
  1942					break
  1943				}
  1944			}
  1945			if !matches {
  1946				return false, nil
  1947			}
  1948		}
  1949		corpus := s.h.corpus
  1950		if c.WholeRef.Valid() {
  1951			if corpus == nil {
  1952				return false, nil
  1953			}
  1954			wholeRef, ok := corpus.GetWholeRef(ctx, br)
  1955			if !ok || wholeRef != c.WholeRef {
  1956				return false, nil
  1957			}
  1958		}
  1959		var width, height int64
  1960		if c.Width != nil || c.Height != nil || c.WHRatio != nil {
  1961			if corpus == nil {
  1962				return false, nil
  1963			}
  1964			imageInfo, err := corpus.GetImageInfo(ctx, br)
  1965			if err != nil {
  1966				if os.IsNotExist(err) {
  1967					return false, nil
  1968				}
  1969				return false, err
  1970			}
  1971			width = int64(imageInfo.Width)
  1972			height = int64(imageInfo.Height)
  1973		}
  1974		if c.Width != nil && !c.Width.intMatches(width) {
  1975			return false, nil
  1976		}
  1977		if c.Height != nil && !c.Height.intMatches(height) {
  1978			return false, nil
  1979		}
  1980		if c.WHRatio != nil && !c.WHRatio.floatMatches(float64(width)/float64(height)) {
  1981			return false, nil
  1982		}
  1983		if c.Location != nil {
  1984			if corpus == nil {
  1985				return false, nil
  1986			}
  1987			lat, long, found := corpus.FileLatLong(br)
  1988			if !found || !c.Location.matchesLatLong(lat, long) {
  1989				return false, nil
  1990			}
  1991			// If location was successfully matched, add the
  1992			// location to the global location area of results so
  1993			// a sort-by-map doesn't need to look it up again
  1994			// later.
  1995			s.loc[br] = camtypes.Location{
  1996				Latitude:  lat,
  1997				Longitude: long,
  1998			}
  1999		} else if s.q.Sort == MapSort {
  2000			if lat, long, found := corpus.FileLatLong(br); found {
  2001				s.loc[br] = camtypes.Location{
  2002					Latitude:  lat,
  2003					Longitude: long,
  2004				}
  2005			}
  2006		}
  2007		// this makes sure, in conjunction with TestQueryFileLocation, that we only
  2008		// expand the location iff the location matched AND the whole constraint matched as
  2009		// well.
  2010		if expandLocationHook {
  2011			return false, nil
  2012		}
  2013		if mt := c.MediaTag; mt != nil {
  2014			if corpus == nil {
  2015				return false, nil
  2016			}
  2017			var tagValue string
  2018			if mediaTags, err := corpus.GetMediaTags(ctx, br); err == nil && mt.Tag != "" {
  2019				tagValue = mediaTags[mt.Tag]
  2020			}
  2021			if mt.Int != nil {
  2022				if i, err := strconv.ParseInt(tagValue, 10, 64); err != nil || !mt.Int.intMatches(i) {
  2023					return false, nil
  2024				}
  2025			}
  2026			if mt.String != nil && !mt.String.stringMatches(tagValue) {
  2027				return false, nil
  2028			}
  2029		}
  2030		// TODO: EXIF timeconstraint
  2031		return true, nil
  2032	}
  2033	
  2034	func (c *TimeConstraint) timeMatches(t time.Time) bool {
  2035		if t.IsZero() {
  2036			return false
  2037		}
  2038		if !c.Before.IsAnyZero() {
  2039			if !t.Before(time.Time(c.Before)) {
  2040				return false
  2041			}
  2042		}
  2043		after := time.Time(c.After)
  2044		if after.IsZero() && c.InLast > 0 {
  2045			after = time.Now().Add(-c.InLast)
  2046		}
  2047		if !after.IsZero() {
  2048			if !(t.Equal(after) || t.After(after)) { // after is >=
  2049				return false
  2050			}
  2051		}
  2052		return true
  2053	}
  2054	
  2055	func (c *DirConstraint) checkValid() error {
  2056		if c == nil {
  2057			return nil
  2058		}
  2059		if c.Contains != nil && c.RecursiveContains != nil {
  2060			return errors.New("Contains and RecursiveContains in a DirConstraint are mutually exclusive")
  2061		}
  2062		return nil
  2063	}
  2064	
  2065	func (c *Constraint) isFileOrDirConstraint() bool {
  2066		if l := c.Logical; l != nil {
  2067			if l.Op == "not" {
  2068				return l.A.isFileOrDirConstraint() // l.B is nil
  2069			}
  2070			return l.A.isFileOrDirConstraint() && l.B.isFileOrDirConstraint()
  2071		}
  2072		return c.File != nil || c.Dir != nil
  2073	}
  2074	
  2075	func (c *Constraint) fileOrDirOrLogicalMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  2076		if cf := c.File; cf != nil {
  2077			return cf.blobMatches(ctx, s, br, bm)
  2078		}
  2079		if cd := c.Dir; cd != nil {
  2080			return cd.blobMatches(ctx, s, br, bm)
  2081		}
  2082		if l := c.Logical; l != nil {
  2083			return l.matcher()(ctx, s, br, bm)
  2084		}
  2085		return false, nil
  2086	}
  2087	
  2088	func (c *DirConstraint) blobMatches(ctx context.Context, s *search, br blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  2089		if bm.CamliType != schema.TypeDirectory {
  2090			return false, nil
  2091		}
  2092		// TODO(mpl): I've added c.BlobRefPrefix, so that c.ParentDir can be directly
  2093		// matched against a blobRef (instead of e.g. a filename), but I could instead make
  2094		// ParentDir be a *Constraint, and logically enforce that it has to "be equivalent"
  2095		// to a ParentDir matching or a BlobRefPrefix matching. I think this here below is
  2096		// simpler, but not sure it's best in the long run.
  2097		if pfx := c.BlobRefPrefix; pfx != "" {
  2098			if !br.HasPrefix(pfx) {
  2099				return false, nil
  2100			}
  2101		}
  2102		fi, err := s.fileInfo(ctx, br)
  2103		if err == os.ErrNotExist {
  2104			return false, nil
  2105		}
  2106		if err != nil {
  2107			return false, err
  2108		}
  2109		if sc := c.FileName; sc != nil && !sc.stringMatches(fi.FileName) {
  2110			return false, nil
  2111		}
  2112		if pc := c.ParentDir; pc != nil {
  2113			parents, err := s.parentDirs(ctx, br)
  2114			if err == os.ErrNotExist {
  2115				return false, nil
  2116			}
  2117			if err != nil {
  2118				return false, err
  2119			}
  2120			isMatch, err := pc.hasMatchingParent(ctx, s, parents)
  2121			if err != nil {
  2122				return false, err
  2123			}
  2124			if !isMatch {
  2125				return false, nil
  2126			}
  2127		}
  2128	
  2129		// All constraints not pertaining to children must happen above
  2130		// this point.
  2131		children, err := s.dirChildren(ctx, br)
  2132		if err != nil && err != os.ErrNotExist {
  2133			return false, err
  2134		}
  2135		if fc := c.TopFileCount; fc != nil && !fc.intMatches(int64(len(children))) {
  2136			return false, nil
  2137		}
  2138		cc := c.Contains
  2139		recursive := false
  2140		if cc == nil {
  2141			if crc := c.RecursiveContains; crc != nil {
  2142				recursive = true
  2143				// RecursiveContains implies Contains
  2144				cc = crc
  2145			}
  2146		}
  2147		// First test on the direct children
  2148		containsMatch := false
  2149		if cc != nil {
  2150			// Allow directly specifying the fileRef
  2151			if cc.BlobRefPrefix != "" {
  2152				containsMatch, err = c.hasMatchingChild(ctx, s, children, func(ctx context.Context, s *search, child blob.Ref, bm camtypes.BlobMeta) (bool, error) {
  2153					return child.HasPrefix(cc.BlobRefPrefix), nil
  2154				})
  2155			} else {
  2156				if !cc.isFileOrDirConstraint() {
  2157					return false, errors.New("[Recursive]Contains constraint should have a *FileConstraint, or a *DirConstraint, or a *LogicalConstraint combination of the aforementioned.")
  2158				}
  2159				containsMatch, err = c.hasMatchingChild(ctx, s, children, cc.fileOrDirOrLogicalMatches)
  2160			}
  2161			if err != nil {
  2162				return false, err
  2163			}
  2164			if !containsMatch && !recursive {
  2165				return false, nil
  2166			}
  2167		}
  2168		// Then if needed recurse on the next generation descendants.
  2169		if !containsMatch && recursive {
  2170			match, err := c.hasMatchingChild(ctx, s, children, c.blobMatches)
  2171			if err != nil {
  2172				return false, err
  2173			}
  2174			if !match {
  2175				return false, nil
  2176			}
  2177		}
  2178	
  2179		// TODO: implement FileCount and FileSize.
  2180	
  2181		return true, nil
  2182	}
  2183	
  2184	// hasMatchingParent checks all parents against c and returns true as soon as one of
  2185	// them matches, or returns false if none of them is a match.
  2186	func (c *DirConstraint) hasMatchingParent(ctx context.Context, s *search, parents map[blob.Ref]struct{}) (bool, error) {
  2187		for parent := range parents {
  2188			meta, err := s.blobMeta(ctx, parent)
  2189			if err != nil {
  2190				if os.IsNotExist(err) {
  2191					continue
  2192				}
  2193				return false, err
  2194			}
  2195			ok, err := c.blobMatches(ctx, s, parent, meta)
  2196			if err != nil {
  2197				return false, err
  2198			}
  2199			if ok {
  2200				return true, nil
  2201			}
  2202		}
  2203		return false, nil
  2204	}
  2205	
  2206	// hasMatchingChild runs matcher against each child and returns true as soon as
  2207	// there is a match, of false if none of them is a match.
  2208	func (c *DirConstraint) hasMatchingChild(ctx context.Context, s *search, children map[blob.Ref]struct{},
  2209		matcher func(context.Context, *search, blob.Ref, camtypes.BlobMeta) (bool, error)) (bool, error) {
  2210		// TODO(mpl): See if we're guaranteed to be CPU-bound (i.e. all resources are in
  2211		// corpus), and if not, add some concurrency to spread costly index lookups.
  2212		for child, _ := range children {
  2213			meta, err := s.blobMeta(ctx, child)
  2214			if err != nil {
  2215				if os.IsNotExist(err) {
  2216					continue
  2217				}
  2218				return false, err
  2219			}
  2220			ok, err := matcher(ctx, s, child, meta)
  2221			if err != nil {
  2222				return false, err
  2223			}
  2224			if ok {
  2225				return true, nil
  2226			}
  2227		}
  2228		return false, nil
  2229	}
  2230	
  2231	type sortSearchResultBlobs struct {
  2232		s    []*SearchResultBlob
  2233		less func(a, b *SearchResultBlob) bool
  2234	}
  2235	
  2236	func (ss sortSearchResultBlobs) Len() int           { return len(ss.s) }
  2237	func (ss sortSearchResultBlobs) Swap(i, j int)      { ss.s[i], ss.s[j] = ss.s[j], ss.s[i] }
  2238	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.