1	/*
     2	Copyright 2014 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		"context"
    22		"encoding/json"
    23		"errors"
    24		"fmt"
    25		"log"
    26		"net/http"
    27		"net/url"
    28		"os"
    29		"sort"
    30		"strings"
    31		"sync"
    32		"time"
    33	
    34		"go4.org/syncutil"
    35		"go4.org/types"
    36	
    37		"perkeep.org/internal/httputil"
    38		"perkeep.org/pkg/blob"
    39		"perkeep.org/pkg/schema"
    40		"perkeep.org/pkg/types/camtypes"
    41	)
    42	
    43	func (h *Handler) serveDescribe(rw http.ResponseWriter, req *http.Request) {
    44		defer httputil.RecoverJSON(rw, req)
    45		var dr DescribeRequest
    46		dr.fromHTTP(req)
    47		ctx := context.TODO()
    48	
    49		res, err := h.Describe(ctx, &dr)
    50		if err != nil {
    51			httputil.ServeJSONError(rw, err)
    52			return
    53		}
    54		httputil.ReturnJSON(rw, res)
    55	}
    56	
    57	const verboseDescribe = false
    58	
    59	// Describe returns a response for the given describe request. It acquires RLock
    60	// on the Handler's index.
    61	func (h *Handler) Describe(ctx context.Context, dr *DescribeRequest) (dres *DescribeResponse, err error) {
    62		h.index.RLock()
    63		defer h.index.RUnlock()
    64	
    65		return h.DescribeLocked(ctx, dr)
    66	}
    67	
    68	// DescribeLocked returns a response for the given describe request. It is the
    69	// caller's responsibility to lock the search handler's index.
    70	func (h *Handler) DescribeLocked(ctx context.Context, dr *DescribeRequest) (dres *DescribeResponse, err error) {
    71		if verboseDescribe {
    72			t0 := time.Now()
    73			defer func() {
    74				td := time.Since(t0)
    75				var num int
    76				if dres != nil {
    77					num = len(dres.Meta)
    78				}
    79				log.Printf("Described %d blobs in %v", num, td)
    80			}()
    81		}
    82		h.initDescribeRequest(dr)
    83		if dr.BlobRef.Valid() {
    84			dr.StartDescribe(ctx, dr.BlobRef, dr.depth())
    85		}
    86		for _, br := range dr.BlobRefs {
    87			dr.StartDescribe(ctx, br, dr.depth())
    88		}
    89		if err := dr.expandRules(ctx); err != nil {
    90			return nil, err
    91		}
    92		metaMap, err := dr.metaMap()
    93		if err != nil {
    94			return nil, err
    95		}
    96		return &DescribeResponse{metaMap}, nil
    97	}
    98	
    99	type DescribeRequest struct {
   100		// BlobRefs are the blobs to describe. If length zero, BlobRef
   101		// is used.
   102		BlobRefs []blob.Ref `json:"blobrefs,omitempty"`
   103	
   104		// BlobRef is the blob to describe.
   105		BlobRef blob.Ref `json:"blobref,omitempty"`
   106	
   107		// Depth is the optional traversal depth to describe from the
   108		// root BlobRef. If zero, a default is used.
   109		// Depth is deprecated and will be removed. Use Rules instead.
   110		Depth int `json:"depth,omitempty"`
   111	
   112		// MaxDirChildren is the requested optional limit to the number
   113		// of children that should be fetched when describing a static
   114		// directory. If zero, a default is used.
   115		MaxDirChildren int `json:"maxDirChildren,omitempty"`
   116	
   117		// At specifies the time which we wish to see the state of
   118		// this blob.  If zero (unspecified), all claims will be
   119		// considered, otherwise, any claims after this date will not
   120		// be considered.
   121		At types.Time3339 `json:"at"`
   122	
   123		// Rules specifies a set of rules to instruct how to keep
   124		// expanding the described set. All rules are tested and
   125		// matching rules grow the response set until all rules no
   126		// longer match or internal limits are hit.
   127		Rules []*DescribeRule `json:"rules,omitempty"`
   128	
   129		// Internal details, used while loading.
   130		// Initialized by sh.initDescribeRequest.
   131		sh            *Handler
   132		mu            sync.Mutex // protects following:
   133		m             MetaMap
   134		started       map[blobrefAndDepth]bool // blobref -> true
   135		blobDesLock   map[blob.Ref]*sync.Mutex
   136		errs          map[string]error // blobref -> error
   137		resFromRule   map[*DescribeRule]map[blob.Ref]bool
   138		flatRuleCache []*DescribeRule // flattened once, by flatRules
   139	
   140		wg *sync.WaitGroup // for load requests
   141	}
   142	
   143	// Clone clones a DescribeRequest by JSON marshaling it and then unmarshaling it into a new object
   144	// (which is then also initialized with initDescribeRequest).
   145	func (dr *DescribeRequest) Clone() *DescribeRequest {
   146		marshaled, _ := json.Marshal(dr)
   147		res := new(DescribeRequest)
   148		json.Unmarshal(marshaled, res)
   149		dr.sh.initDescribeRequest(res)
   150		return res
   151	}
   152	
   153	type blobrefAndDepth struct {
   154		br    blob.Ref
   155		depth int
   156	}
   157	
   158	// Requires dr.mu is held
   159	func (dr *DescribeRequest) flatRules() []*DescribeRule {
   160		if dr.flatRuleCache == nil {
   161			dr.flatRuleCache = make([]*DescribeRule, 0)
   162			for _, rule := range dr.Rules {
   163				rule.appendToFlatCache(dr)
   164			}
   165		}
   166		return dr.flatRuleCache
   167	}
   168	
   169	func (r *DescribeRule) appendToFlatCache(dr *DescribeRequest) {
   170		dr.flatRuleCache = append(dr.flatRuleCache, r)
   171		for _, rchild := range r.Rules {
   172			rchild.parentRule = r
   173			rchild.appendToFlatCache(dr)
   174		}
   175	}
   176	
   177	// Requires dr.mu is held.
   178	func (dr *DescribeRequest) foreachResultBlob(fn func(blob.Ref)) {
   179		if dr.BlobRef.Valid() {
   180			fn(dr.BlobRef)
   181		}
   182		for _, br := range dr.BlobRefs {
   183			fn(br)
   184		}
   185		for brStr := range dr.m {
   186			if br, ok := blob.Parse(brStr); ok {
   187				fn(br)
   188			}
   189		}
   190	}
   191	
   192	// Requires dr.mu is held.
   193	func (dr *DescribeRequest) blobInitiallyRequested(br blob.Ref) bool {
   194		if dr.BlobRef.Valid() && dr.BlobRef == br {
   195			return true
   196		}
   197		for _, br1 := range dr.BlobRefs {
   198			if br == br1 {
   199				return true
   200			}
   201		}
   202		return false
   203	}
   204	
   205	type DescribeRule struct {
   206		// All non-zero 'If*' fields in the following set must match
   207		// for the rule to match:
   208	
   209		// IsResultRoot, if true, only matches if the blob was part of
   210		// the original search results, not a blob expanded later.
   211		IfResultRoot bool `json:"ifResultRoot,omitempty"`
   212	
   213		// IfCamliNodeType matches if the "camliNodeType" attribute
   214		// equals this value.
   215		IfCamliNodeType string `json:"ifCamliNodeType,omitempty"`
   216	
   217		// Attrs lists attributes to describe. A special case
   218		// is if the value ends in "*", which matches prefixes
   219		// (e.g. "camliPath:*" or "*").
   220		Attrs []string `json:"attrs,omitempty"`
   221	
   222		// Additional rules to run on the described results of Attrs.
   223		Rules []*DescribeRule `json:"rules,omitempty"`
   224	
   225		parentRule *DescribeRule
   226	}
   227	
   228	// DescribeResponse is the JSON response from $searchRoot/camli/search/describe.
   229	type DescribeResponse struct {
   230		Meta MetaMap `json:"meta"`
   231	}
   232	
   233	// A MetaMap is a map from blobref to a DescribedBlob.
   234	type MetaMap map[string]*DescribedBlob
   235	
   236	type DescribedBlob struct {
   237		Request *DescribeRequest `json:"-"`
   238	
   239		BlobRef   blob.Ref         `json:"blobRef"`
   240		CamliType schema.CamliType `json:"camliType,omitempty"`
   241		Size      int64            `json:"size,"`
   242	
   243		// if camliType "permanode"
   244		Permanode *DescribedPermanode `json:"permanode,omitempty"`
   245	
   246		// if camliType "file"
   247		File *camtypes.FileInfo `json:"file,omitempty"`
   248		// if camliType "directory"
   249		Dir *camtypes.FileInfo `json:"dir,omitempty"`
   250		// if camliType "file", and File.IsImage()
   251		Image *camtypes.ImageInfo `json:"image,omitempty"`
   252		// if camliType "file" and media file
   253		MediaTags map[string]string `json:"mediaTags,omitempty"`
   254	
   255		// if camliType "directory"
   256		DirChildren []blob.Ref `json:"dirChildren,omitempty"`
   257	
   258		// Location specifies the location of the entity referenced
   259		// by the blob.
   260		//
   261		// If camliType is "file", then location comes from the metadata
   262		// (currently Exif) metadata of the file content.
   263		//
   264		// If camliType is "permanode", then location comes
   265		// from one of the following sources:
   266		//  1. Permanode attributes "latitude" and "longitude"
   267		//  2. Referenced permanode attributes (eg. for "foursquare.com:checkin"
   268		//     its "foursquareVenuePermanode")
   269		//  3. Location in permanode camliContent file metadata
   270		// The sources are checked in this order, the location from
   271		// the first source yielding a valid result is returned.
   272		Location *camtypes.Location `json:"location,omitempty"`
   273	
   274		// Stub is set if this is not loaded, but referenced.
   275		Stub bool `json:"-"`
   276	}
   277	
   278	func (m MetaMap) Get(br blob.Ref) *DescribedBlob {
   279		if !br.Valid() {
   280			return nil
   281		}
   282		return m[br.String()]
   283	}
   284	
   285	// URLSuffixPost returns the URL suffix for POST requests.
   286	func (dr *DescribeRequest) URLSuffixPost() string {
   287		return "camli/search/describe"
   288	}
   289	
   290	// URLSuffix returns the URL suffix for GET requests.
   291	// This is deprecated.
   292	func (dr *DescribeRequest) URLSuffix() string {
   293		var buf bytes.Buffer
   294		fmt.Fprintf(&buf, "camli/search/describe?depth=%d&maxdirchildren=%d",
   295			dr.depth(), dr.maxDirChildren())
   296		for _, br := range dr.BlobRefs {
   297			buf.WriteString("&blobref=")
   298			buf.WriteString(br.String())
   299		}
   300		if len(dr.BlobRefs) == 0 && dr.BlobRef.Valid() {
   301			buf.WriteString("&blobref=")
   302			buf.WriteString(dr.BlobRef.String())
   303		}
   304		if !dr.At.IsAnyZero() {
   305			buf.WriteString("&at=")
   306			buf.WriteString(dr.At.String())
   307		}
   308		return buf.String()
   309	}
   310	
   311	// fromHTTP panics with an httputil value on failure
   312	func (dr *DescribeRequest) fromHTTP(req *http.Request) {
   313		switch {
   314		case httputil.IsGet(req):
   315			dr.fromHTTPGet(req)
   316		case req.Method == "POST":
   317			dr.fromHTTPPost(req)
   318		default:
   319			panic("Unsupported method")
   320		}
   321	}
   322	
   323	func (dr *DescribeRequest) fromHTTPPost(req *http.Request) {
   324		err := json.NewDecoder(req.Body).Decode(dr)
   325		if err != nil {
   326			panic(err)
   327		}
   328	}
   329	
   330	func (dr *DescribeRequest) fromHTTPGet(req *http.Request) {
   331		req.ParseForm()
   332		if vv := req.Form["blobref"]; len(vv) > 1 {
   333			for _, brs := range vv {
   334				if br, ok := blob.Parse(brs); ok {
   335					dr.BlobRefs = append(dr.BlobRefs, br)
   336				} else {
   337					panic(httputil.InvalidParameterError("blobref"))
   338				}
   339			}
   340		} else {
   341			dr.BlobRef = httputil.MustGetBlobRef(req, "blobref")
   342		}
   343		dr.Depth = httputil.OptionalInt(req, "depth")
   344		dr.MaxDirChildren = httputil.OptionalInt(req, "maxdirchildren")
   345		dr.At = types.ParseTime3339OrZero(req.FormValue("at"))
   346	}
   347	
   348	// PermanodeFile returns in path the blobref of the described permanode
   349	// and the blobref of its File camliContent.
   350	// If b isn't a permanode, or doesn't have a camliContent that
   351	// is a file blob, ok is false.
   352	func (b *DescribedBlob) PermanodeFile() (path []blob.Ref, fi *camtypes.FileInfo, ok bool) {
   353		if b == nil || b.Permanode == nil {
   354			return
   355		}
   356		if contentRef := b.Permanode.Attr.Get("camliContent"); contentRef != "" {
   357			if cdes := b.Request.DescribedBlobStr(contentRef); cdes != nil && cdes.File != nil {
   358				return []blob.Ref{b.BlobRef, cdes.BlobRef}, cdes.File, true
   359			}
   360		}
   361		return
   362	}
   363	
   364	// PermanodeDir returns in path the blobref of the described permanode
   365	// and the blobref of its Directory camliContent.
   366	// If b isn't a permanode, or doesn't have a camliContent that
   367	// is a directory blob, ok is false.
   368	func (b *DescribedBlob) PermanodeDir() (path []blob.Ref, fi *camtypes.FileInfo, ok bool) {
   369		if b == nil || b.Permanode == nil {
   370			return
   371		}
   372		if contentRef := b.Permanode.Attr.Get("camliContent"); contentRef != "" {
   373			if cdes := b.Request.DescribedBlobStr(contentRef); cdes != nil && cdes.Dir != nil {
   374				return []blob.Ref{b.BlobRef, cdes.BlobRef}, cdes.Dir, true
   375			}
   376		}
   377		return
   378	}
   379	
   380	func (b *DescribedBlob) DomID() string {
   381		if b == nil {
   382			return ""
   383		}
   384		return b.BlobRef.DomID()
   385	}
   386	
   387	func (b *DescribedBlob) Title() string {
   388		if b == nil {
   389			return ""
   390		}
   391		if b.Permanode != nil {
   392			if t := b.Permanode.Attr.Get("title"); t != "" {
   393				return t
   394			}
   395			if contentRef := b.Permanode.Attr.Get("camliContent"); contentRef != "" {
   396				return b.Request.DescribedBlobStr(contentRef).Title()
   397			}
   398		}
   399		if b.File != nil {
   400			return b.File.FileName
   401		}
   402		if b.Dir != nil {
   403			return b.Dir.FileName
   404		}
   405		return ""
   406	}
   407	
   408	func (b *DescribedBlob) Description() string {
   409		if b == nil {
   410			return ""
   411		}
   412		if b.Permanode != nil {
   413			return b.Permanode.Attr.Get("description")
   414		}
   415		return ""
   416	}
   417	
   418	// Members returns all of b's children, as given by b's camliMember and camliPath:*
   419	// attributes. Only the first entry for a given camliPath attribute is used.
   420	func (b *DescribedBlob) Members() []*DescribedBlob {
   421		if b == nil {
   422			return nil
   423		}
   424		m := make([]*DescribedBlob, 0)
   425		if b.Permanode != nil {
   426			for _, bstr := range b.Permanode.Attr["camliMember"] {
   427				if br, ok := blob.Parse(bstr); ok {
   428					m = append(m, b.PeerBlob(br))
   429				}
   430			}
   431			for k, bstrs := range b.Permanode.Attr {
   432				if strings.HasPrefix(k, "camliPath:") && len(bstrs) > 0 {
   433					if br, ok := blob.Parse(bstrs[0]); ok {
   434						m = append(m, b.PeerBlob(br))
   435					}
   436				}
   437			}
   438		}
   439		return m
   440	}
   441	
   442	func (b *DescribedBlob) DirMembers() []*DescribedBlob {
   443		if b == nil || b.Dir == nil || len(b.DirChildren) == 0 {
   444			return nil
   445		}
   446	
   447		m := make([]*DescribedBlob, 0)
   448		for _, br := range b.DirChildren {
   449			m = append(m, b.PeerBlob(br))
   450		}
   451		return m
   452	}
   453	
   454	func (b *DescribedBlob) ContentRef() (br blob.Ref, ok bool) {
   455		if b != nil && b.Permanode != nil {
   456			if cref := b.Permanode.Attr.Get("camliContent"); cref != "" {
   457				return blob.Parse(cref)
   458			}
   459		}
   460		return
   461	}
   462	
   463	// DescribedBlobStr when given a blobref string returns a Description
   464	// or nil.  dr may be nil itself.
   465	func (dr *DescribeRequest) DescribedBlobStr(blobstr string) *DescribedBlob {
   466		if dr == nil {
   467			return nil
   468		}
   469		dr.mu.Lock()
   470		defer dr.mu.Unlock()
   471		return dr.m[blobstr]
   472	}
   473	
   474	// PeerBlob returns a DescribedBlob for the provided blobref.
   475	//
   476	// Unlike DescribedBlobStr, the returned DescribedBlob is never nil.
   477	//
   478	// If the blob was never loaded along with the the receiver (or if the
   479	// receiver is nil), a stub DescribedBlob is returned with its Stub
   480	// field set true.
   481	func (b *DescribedBlob) PeerBlob(br blob.Ref) *DescribedBlob {
   482		if b.Request == nil {
   483			return &DescribedBlob{BlobRef: br, Stub: true}
   484		}
   485		b.Request.mu.Lock()
   486		defer b.Request.mu.Unlock()
   487		return b.peerBlob(br)
   488	}
   489	
   490	// version of PeerBlob when b.Request.mu is already held.
   491	func (b *DescribedBlob) peerBlob(br blob.Ref) *DescribedBlob {
   492		if peer, ok := b.Request.m[br.String()]; ok {
   493			return peer
   494		}
   495		return &DescribedBlob{Request: b.Request, BlobRef: br, Stub: true}
   496	}
   497	
   498	type DescribedPermanode struct {
   499		Attr    url.Values `json:"attr"` // a map[string][]string
   500		ModTime time.Time  `json:"modtime,omitempty"`
   501	}
   502	
   503	// IsContainer returns whether the permanode has either named ("camliPath:"-prefixed) or unnamed
   504	// ("camliMember") member attributes.
   505	func (dp *DescribedPermanode) IsContainer() bool {
   506		if members := dp.Attr["camliMember"]; len(members) > 0 {
   507			return true
   508		}
   509		for k := range dp.Attr {
   510			if strings.HasPrefix(k, "camliPath:") {
   511				return true
   512			}
   513		}
   514		return false
   515	}
   516	
   517	// NewDescribeRequest returns a new DescribeRequest holding the state
   518	// of blobs and their summarized descriptions.  Use DescribeBlob
   519	// one or more times before calling Result.
   520	func (h *Handler) NewDescribeRequest() *DescribeRequest {
   521		dr := new(DescribeRequest)
   522		h.initDescribeRequest(dr)
   523		return dr
   524	}
   525	
   526	func (h *Handler) initDescribeRequest(req *DescribeRequest) {
   527		if req.sh != nil {
   528			panic("already initialized")
   529		}
   530		req.sh = h
   531		req.m = make(MetaMap)
   532		req.errs = make(map[string]error)
   533		req.wg = new(sync.WaitGroup)
   534	}
   535	
   536	type DescribeError map[string]error
   537	
   538	func (de DescribeError) Error() string {
   539		var buf bytes.Buffer
   540		for b, err := range de {
   541			fmt.Fprintf(&buf, "%s: %v; ", b, err)
   542		}
   543		return fmt.Sprintf("Errors (%d) describing blobs: %s", len(de), buf.String())
   544	}
   545	
   546	// Result waits for all outstanding lookups to complete and
   547	// returns the map of blobref (strings) to their described
   548	// results. The returned error is non-nil if any errors
   549	// occurred, and will be of type DescribeError.
   550	func (dr *DescribeRequest) Result() (desmap map[string]*DescribedBlob, err error) {
   551		dr.wg.Wait()
   552		// TODO: set "done" / locked flag, so no more DescribeBlob can
   553		// be called.
   554		if len(dr.errs) > 0 {
   555			return dr.m, DescribeError(dr.errs)
   556		}
   557		return dr.m, nil
   558	}
   559	
   560	func (dr *DescribeRequest) depth() int {
   561		if dr.Depth > 0 {
   562			return dr.Depth
   563		}
   564		return 1
   565	}
   566	
   567	func (dr *DescribeRequest) maxDirChildren() int {
   568		return sanitizeNumResults(dr.MaxDirChildren)
   569	}
   570	
   571	func (dr *DescribeRequest) metaMap() (map[string]*DescribedBlob, error) {
   572		dr.wg.Wait()
   573		dr.mu.Lock()
   574		defer dr.mu.Unlock()
   575		for k, err := range dr.errs {
   576			// TODO: include all?
   577			return nil, fmt.Errorf("error populating %s: %w", k, err)
   578		}
   579		m := make(map[string]*DescribedBlob)
   580		for k, desb := range dr.m {
   581			m[k] = desb
   582		}
   583		return m, nil
   584	}
   585	
   586	func (dr *DescribeRequest) describedBlob(b blob.Ref) *DescribedBlob {
   587		dr.mu.Lock()
   588		defer dr.mu.Unlock()
   589		bs := b.String()
   590		if des, ok := dr.m[bs]; ok {
   591			return des
   592		}
   593		des := &DescribedBlob{Request: dr, BlobRef: b}
   594		dr.m[bs] = des
   595		return des
   596	}
   597	
   598	func (dr *DescribeRequest) DescribeSync(ctx context.Context, br blob.Ref) (*DescribedBlob, error) {
   599		dr.StartDescribe(ctx, br, 1)
   600		res, err := dr.Result()
   601		if err != nil {
   602			return nil, err
   603		}
   604		return res[br.String()], nil
   605	}
   606	
   607	// StartDescribe starts a lookup of br, down to the provided depth.
   608	// It returns immediately. One should call Result to wait for the description to
   609	// be completed.
   610	func (dr *DescribeRequest) StartDescribe(ctx context.Context, br blob.Ref, depth int) {
   611		if depth <= 0 {
   612			return
   613		}
   614		dr.mu.Lock()
   615		defer dr.mu.Unlock()
   616		if dr.blobDesLock == nil {
   617			dr.blobDesLock = make(map[blob.Ref]*sync.Mutex)
   618		}
   619		desBlobMu, ok := dr.blobDesLock[br]
   620		if !ok {
   621			desBlobMu = new(sync.Mutex)
   622			dr.blobDesLock[br] = desBlobMu
   623		}
   624		if dr.started == nil {
   625			dr.started = make(map[blobrefAndDepth]bool)
   626		}
   627		key := blobrefAndDepth{br, depth}
   628		if dr.started[key] {
   629			return
   630		}
   631		dr.started[key] = true
   632		dr.wg.Add(1)
   633		go func() {
   634			defer dr.wg.Done()
   635			desBlobMu.Lock()
   636			defer desBlobMu.Unlock()
   637			dr.doDescribe(ctx, br, depth)
   638		}()
   639	}
   640	
   641	// requires dr.mu be held.
   642	func (r *DescribeRule) newMatches(br blob.Ref, dr *DescribeRequest) (brs []blob.Ref) {
   643		if r.IfResultRoot {
   644			if !dr.blobInitiallyRequested(br) {
   645				return nil
   646			}
   647		}
   648		if r.parentRule != nil {
   649			if _, ok := dr.resFromRule[r.parentRule][br]; !ok {
   650				return nil
   651			}
   652		}
   653		db, ok := dr.m[br.String()]
   654		if !ok || db.Permanode == nil {
   655			return nil
   656		}
   657		if t := r.IfCamliNodeType; t != "" {
   658			gotType := db.Permanode.Attr.Get("camliNodeType")
   659			if gotType != t {
   660				return nil
   661			}
   662		}
   663		for attr, vv := range db.Permanode.Attr {
   664			matches := false
   665			for _, matchAttr := range r.Attrs {
   666				if attr == matchAttr {
   667					matches = true
   668					break
   669				}
   670				if strings.HasSuffix(matchAttr, "*") && strings.HasPrefix(attr, strings.TrimSuffix(matchAttr, "*")) {
   671					matches = true
   672					break
   673				}
   674			}
   675			if !matches {
   676				continue
   677			}
   678			for _, v := range vv {
   679				if br, ok := blob.Parse(v); ok {
   680					brs = append(brs, br)
   681				}
   682			}
   683		}
   684		return brs
   685	}
   686	
   687	// dr.mu just be locked.
   688	func (dr *DescribeRequest) noteResultFromRule(rule *DescribeRule, br blob.Ref) {
   689		if dr.resFromRule == nil {
   690			dr.resFromRule = make(map[*DescribeRule]map[blob.Ref]bool)
   691		}
   692		m, ok := dr.resFromRule[rule]
   693		if !ok {
   694			m = make(map[blob.Ref]bool)
   695			dr.resFromRule[rule] = m
   696		}
   697		m[br] = true
   698	}
   699	
   700	func (dr *DescribeRequest) expandRules(ctx context.Context) error {
   701		loop := true
   702	
   703		for loop {
   704			loop = false
   705			dr.wg.Wait()
   706			dr.mu.Lock()
   707			len0 := len(dr.m)
   708			var new []blob.Ref
   709			for _, rule := range dr.flatRules() {
   710				dr.foreachResultBlob(func(br blob.Ref) {
   711					for _, nbr := range rule.newMatches(br, dr) {
   712						new = append(new, nbr)
   713						dr.noteResultFromRule(rule, nbr)
   714					}
   715				})
   716			}
   717			dr.mu.Unlock()
   718			for _, br := range new {
   719				dr.StartDescribe(ctx, br, 1)
   720			}
   721			dr.wg.Wait()
   722			dr.mu.Lock()
   723			len1 := len(dr.m)
   724			dr.mu.Unlock()
   725			loop = len0 != len1
   726		}
   727		return nil
   728	}
   729	
   730	func (dr *DescribeRequest) addError(br blob.Ref, err error) {
   731		if err == nil {
   732			return
   733		}
   734		dr.mu.Lock()
   735		defer dr.mu.Unlock()
   736		// TODO: append? meh.
   737		dr.errs[br.String()] = err
   738	}
   739	
   740	func (dr *DescribeRequest) doDescribe(ctx context.Context, br blob.Ref, depth int) {
   741		meta, err := dr.sh.index.GetBlobMeta(ctx, br)
   742		if errors.Is(err, os.ErrNotExist) {
   743			return
   744		}
   745		if err != nil {
   746			dr.addError(br, err)
   747			return
   748		}
   749	
   750		// TODO: convert all this in terms of
   751		// DescribedBlob/DescribedPermanode/DescribedFile, not json
   752		// maps.  Then add JSON marhsallers to those types. Add tests.
   753		des := dr.describedBlob(br)
   754		if meta.CamliType != "" {
   755			des.setMIMEType("application/json; camliType=" + string(meta.CamliType))
   756		}
   757		des.Size = int64(meta.Size)
   758	
   759		switch des.CamliType {
   760		case "permanode":
   761			des.Permanode = new(DescribedPermanode)
   762			dr.populatePermanodeFields(ctx, des.Permanode, br, depth)
   763			var at time.Time
   764			if !dr.At.IsAnyZero() {
   765				at = dr.At.Time()
   766			}
   767			if loc, err := dr.sh.lh.PermanodeLocation(ctx, br, at, dr.sh.owner); err == nil {
   768				des.Location = &loc
   769			} else {
   770				if !errors.Is(err, os.ErrNotExist) {
   771					log.Printf("PermanodeLocation(permanode %s): %v", br, err)
   772				}
   773			}
   774		case "file":
   775			fi, err := dr.sh.index.GetFileInfo(ctx, br)
   776			if err != nil {
   777				if os.IsNotExist(err) {
   778					log.Printf("index.GetFileInfo(file %s) failed; index stale?", br)
   779				} else {
   780					dr.addError(br, err)
   781				}
   782				return
   783			}
   784			des.File = &fi
   785			if des.File.IsImage() {
   786				imgInfo, err := dr.sh.index.GetImageInfo(ctx, br)
   787				if err != nil {
   788					if !os.IsNotExist(err) {
   789						dr.addError(br, err)
   790					}
   791				} else {
   792					des.Image = &imgInfo
   793				}
   794			}
   795			if mediaTags, err := dr.sh.index.GetMediaTags(ctx, br); err == nil {
   796				des.MediaTags = mediaTags
   797			}
   798			if loc, err := dr.sh.index.GetFileLocation(ctx, br); err == nil {
   799				des.Location = &loc
   800			} else {
   801				if !errors.Is(err, os.ErrNotExist) {
   802					log.Printf("index.GetFileLocation(file %s): %v", br, err)
   803				}
   804			}
   805		case "directory":
   806			var g syncutil.Group
   807			g.Go(func() (err error) {
   808				fi, err := dr.sh.index.GetFileInfo(ctx, br)
   809				if os.IsNotExist(err) {
   810					log.Printf("index.GetFileInfo(directory %s) failed; index stale?", br)
   811				}
   812				if err == nil {
   813					des.Dir = &fi
   814				}
   815				return
   816			})
   817			g.Go(func() (err error) {
   818				des.DirChildren, err = dr.getDirMembers(ctx, br, depth)
   819				return
   820			})
   821			if err := g.Err(); err != nil {
   822				dr.addError(br, err)
   823			}
   824		}
   825	}
   826	
   827	func (dr *DescribeRequest) populatePermanodeFields(ctx context.Context, pi *DescribedPermanode, pn blob.Ref, depth int) {
   828		pi.Attr = make(url.Values)
   829		attr := pi.Attr
   830	
   831		claims, err := dr.sh.index.AppendClaims(ctx, nil, pn, dr.sh.owner.KeyID(), "")
   832		if err != nil {
   833			log.Printf("Error getting claims of %s: %v", pn.String(), err)
   834			dr.addError(pn, fmt.Errorf("Error getting claims of %s: %w", pn.String(), err))
   835			return
   836		}
   837	
   838		sort.Sort(camtypes.ClaimsByDate(claims))
   839	claimLoop:
   840		for _, cl := range claims {
   841			if !dr.At.IsAnyZero() {
   842				if cl.Date.After(dr.At.Time()) {
   843					continue
   844				}
   845			}
   846			switch cl.Type {
   847			default:
   848				continue
   849			case "del-attribute":
   850				if cl.Value == "" {
   851					delete(attr, cl.Attr)
   852				} else {
   853					sl := attr[cl.Attr]
   854					filtered := make([]string, 0, len(sl))
   855					for _, val := range sl {
   856						if val != cl.Value {
   857							filtered = append(filtered, val)
   858						}
   859					}
   860					attr[cl.Attr] = filtered
   861				}
   862			case "set-attribute":
   863				delete(attr, cl.Attr)
   864				fallthrough
   865			case "add-attribute":
   866				if cl.Value == "" {
   867					continue
   868				}
   869				sl, ok := attr[cl.Attr]
   870				if ok {
   871					for _, exist := range sl {
   872						if exist == cl.Value {
   873							continue claimLoop
   874						}
   875					}
   876				} else {
   877					sl = make([]string, 0, 1)
   878					attr[cl.Attr] = sl
   879				}
   880				attr[cl.Attr] = append(sl, cl.Value)
   881			}
   882			pi.ModTime = cl.Date
   883		}
   884	
   885		// Descend into any references in current attributes.
   886		for key, vals := range attr {
   887			dr.describeRefs(ctx, key, depth)
   888			for _, v := range vals {
   889				dr.describeRefs(ctx, v, depth)
   890			}
   891		}
   892	}
   893	
   894	func (dr *DescribeRequest) getDirMembers(ctx context.Context, br blob.Ref, depth int) ([]blob.Ref, error) {
   895		limit := dr.maxDirChildren()
   896		ch := make(chan blob.Ref)
   897		errch := make(chan error)
   898		go func() {
   899			errch <- dr.sh.index.GetDirMembers(ctx, br, ch, limit)
   900		}()
   901	
   902		var members []blob.Ref
   903		for child := range ch {
   904			dr.StartDescribe(ctx, child, depth)
   905			members = append(members, child)
   906		}
   907		if err := <-errch; err != nil {
   908			return nil, err
   909		}
   910		return members, nil
   911	}
   912	
   913	func (dr *DescribeRequest) describeRefs(ctx context.Context, str string, depth int) {
   914		for _, match := range blobRefPattern.FindAllString(str, -1) {
   915			if ref, ok := blob.ParseKnown(match); ok {
   916				dr.StartDescribe(ctx, ref, depth-1)
   917			}
   918		}
   919	}
   920	
   921	func (b *DescribedBlob) setMIMEType(mime string) {
   922		if strings.HasPrefix(mime, camliTypePrefix) {
   923			b.CamliType = schema.CamliType(strings.TrimPrefix(mime, camliTypePrefix))
   924		}
   925	}