1	/*
     2	Copyright 2011 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 schema manipulates Camlistore schema blobs.
    18	//
    19	// A schema blob is a JSON-encoded blob that describes other blobs.
    20	// See documentation in Perkeep's doc/schema/ directory.
    21	package schema // import "perkeep.org/pkg/schema"
    22	
    23	import (
    24		"bytes"
    25		"context"
    26		"crypto/rand"
    27		"encoding/base64"
    28		"encoding/json"
    29		"errors"
    30		"fmt"
    31		"hash"
    32		"io"
    33		"log"
    34		"os"
    35		"regexp"
    36		"strconv"
    37		"strings"
    38		"sync"
    39		"time"
    40		"unicode/utf8"
    41	
    42		"github.com/bradfitz/latlong"
    43		"perkeep.org/internal/pools"
    44		"perkeep.org/pkg/blob"
    45	
    46		"github.com/rwcarlsen/goexif/exif"
    47		"github.com/rwcarlsen/goexif/tiff"
    48		"go4.org/strutil"
    49		"go4.org/types"
    50	)
    51	
    52	func init() {
    53		// Intern common strings as used by schema blobs (camliType values), to reduce
    54		// index memory usage, which uses strutil.StringFromBytes.
    55		strutil.RegisterCommonString(
    56			"bytes",
    57			"claim",
    58			"directory",
    59			"file",
    60			"permanode",
    61			"share",
    62			"static-set",
    63			"symlink",
    64		)
    65	}
    66	
    67	// MaxSchemaBlobSize represents the upper bound for how large
    68	// a schema blob may be.
    69	const MaxSchemaBlobSize = 1 << 20
    70	
    71	var (
    72		ErrNoCamliVersion = errors.New("schema: no camliVersion key in map")
    73	)
    74	
    75	var clockNow = time.Now
    76	
    77	type StatHasher interface {
    78		Lstat(fileName string) (os.FileInfo, error)
    79		Hash(fileName string) (blob.Ref, error)
    80	}
    81	
    82	// File is the interface returned when opening a DirectoryEntry that
    83	// is a regular file.
    84	type File interface {
    85		io.Closer
    86		io.ReaderAt
    87		io.Reader
    88		Size() int64
    89	}
    90	
    91	// Directory is a read-only interface to a "directory" schema blob.
    92	type Directory interface {
    93		// Readdir reads the contents of the directory associated with dr
    94		// and returns an array of up to n DirectoryEntries structures.
    95		// Subsequent calls on the same file will yield further
    96		// DirectoryEntries.
    97		// If n > 0, Readdir returns at most n DirectoryEntry structures. In
    98		// this case, if Readdir returns an empty slice, it will return
    99		// a non-nil error explaining why. At the end of a directory,
   100		// the error is os.EOF.
   101		// If n <= 0, Readdir returns all the DirectoryEntries from the
   102		// directory in a single slice. In this case, if Readdir succeeds
   103		// (reads all the way to the end of the directory), it returns the
   104		// slice and a nil os.Error. If it encounters an error before the
   105		// end of the directory, Readdir returns the DirectoryEntry read
   106		// until that point and a non-nil error.
   107		Readdir(ctx context.Context, n int) ([]DirectoryEntry, error)
   108	}
   109	
   110	type Symlink interface {
   111		// .. TODO
   112	}
   113	
   114	// FIFO is the read-only interface to a "fifo" schema blob.
   115	type FIFO interface {
   116		// .. TODO
   117	}
   118	
   119	// Socket is the read-only interface to a "socket" schema blob.
   120	type Socket interface {
   121		// .. TODO
   122	}
   123	
   124	// DirectoryEntry is a read-only interface to an entry in a (static)
   125	// directory.
   126	type DirectoryEntry interface {
   127		// CamliType returns the schema blob's "camliType" field.
   128		// This may be "file", "directory", "symlink", or other more
   129		// obscure types added in the future.
   130		CamliType() CamliType
   131	
   132		FileName() string
   133		BlobRef() blob.Ref
   134	
   135		File(ctx context.Context) (File, error)           // if camliType is "file"
   136		Directory(ctx context.Context) (Directory, error) // if camliType is "directory"
   137		Symlink() (Symlink, error)                        // if camliType is "symlink"
   138		FIFO() (FIFO, error)                              // if camliType is "fifo"
   139		Socket() (Socket, error)                          // If camliType is "socket"
   140	}
   141	
   142	// dirEntry is the default implementation of DirectoryEntry
   143	type dirEntry struct {
   144		ss      superset
   145		fetcher blob.Fetcher
   146		fr      *FileReader // or nil if not a file
   147		dr      *DirReader  // or nil if not a directory
   148	}
   149	
   150	// A SearchQuery must be of type *search.SearchQuery.
   151	// This type breaks an otherwise-circular dependency.
   152	type SearchQuery interface{}
   153	
   154	func (de *dirEntry) CamliType() CamliType {
   155		return de.ss.Type
   156	}
   157	
   158	func (de *dirEntry) FileName() string {
   159		return de.ss.FileNameString()
   160	}
   161	
   162	func (de *dirEntry) BlobRef() blob.Ref {
   163		return de.ss.BlobRef
   164	}
   165	
   166	func (de *dirEntry) File(ctx context.Context) (File, error) {
   167		if de.fr == nil {
   168			if de.ss.Type != TypeFile {
   169				return nil, fmt.Errorf("DirectoryEntry is camliType %q, not %q", de.ss.Type, TypeFile)
   170			}
   171			fr, err := NewFileReader(ctx, de.fetcher, de.ss.BlobRef)
   172			if err != nil {
   173				return nil, err
   174			}
   175			de.fr = fr
   176		}
   177		return de.fr, nil
   178	}
   179	
   180	func (de *dirEntry) Directory(ctx context.Context) (Directory, error) {
   181		if de.dr == nil {
   182			if de.ss.Type != TypeDirectory {
   183				return nil, fmt.Errorf("DirectoryEntry is camliType %q, not %q", de.ss.Type, TypeDirectory)
   184			}
   185			dr, err := NewDirReader(ctx, de.fetcher, de.ss.BlobRef)
   186			if err != nil {
   187				return nil, err
   188			}
   189			de.dr = dr
   190		}
   191		return de.dr, nil
   192	}
   193	
   194	func (de *dirEntry) Symlink() (Symlink, error) {
   195		return 0, errors.New("TODO: Symlink not implemented")
   196	}
   197	
   198	func (de *dirEntry) FIFO() (FIFO, error) {
   199		return 0, errors.New("TODO: FIFO not implemented")
   200	}
   201	
   202	func (de *dirEntry) Socket() (Socket, error) {
   203		return 0, errors.New("TODO: Socket not implemented")
   204	}
   205	
   206	// newDirectoryEntry takes a superset and returns a DirectoryEntry if
   207	// the Supserset is valid and represents an entry in a directory.  It
   208	// must by of type "file", "directory", "symlink" or "socket".
   209	// TODO: "char", block", probably.  later.
   210	func newDirectoryEntry(fetcher blob.Fetcher, ss *superset) (DirectoryEntry, error) {
   211		if ss == nil {
   212			return nil, errors.New("ss was nil")
   213		}
   214		if !ss.BlobRef.Valid() {
   215			return nil, errors.New("ss.BlobRef was invalid")
   216		}
   217		switch ss.Type {
   218		case TypeFile, TypeDirectory, TypeSymlink, TypeFIFO, TypeSocket:
   219			// Okay
   220		default:
   221			return nil, fmt.Errorf("invalid DirectoryEntry camliType of %q", ss.Type)
   222		}
   223		de := &dirEntry{ss: *ss, fetcher: fetcher} // defensive copy
   224		return de, nil
   225	}
   226	
   227	// NewDirectoryEntryFromBlobRef takes a BlobRef and returns a
   228	//
   229	//	DirectoryEntry if the BlobRef contains a type "file", "directory",
   230	//	"symlink", "fifo" or "socket".
   231	//
   232	// TODO: ""char", "block", probably.  later.
   233	func NewDirectoryEntryFromBlobRef(ctx context.Context, fetcher blob.Fetcher, blobRef blob.Ref) (DirectoryEntry, error) {
   234		ss := new(superset)
   235		err := ss.setFromBlobRef(ctx, fetcher, blobRef)
   236		if err != nil {
   237			return nil, fmt.Errorf("schema/filereader: can't fill superset: %w", err)
   238		}
   239		return newDirectoryEntry(fetcher, ss)
   240	}
   241	
   242	// superset represents the superset of common Perkeep JSON schema
   243	// keys as a convenient json.Unmarshal target.
   244	// TODO(bradfitz): unexport this type. Getting too gross. Move to schema.Blob
   245	type superset struct {
   246		// BlobRef isn't for a particular metadata blob field, but included
   247		// for convenience.
   248		BlobRef blob.Ref
   249	
   250		Version int       `json:"camliVersion"`
   251		Type    CamliType `json:"camliType"`
   252	
   253		Signer blob.Ref `json:"camliSigner"`
   254		Sig    string   `json:"camliSig"`
   255	
   256		ClaimType string         `json:"claimType"`
   257		ClaimDate types.Time3339 `json:"claimDate"`
   258	
   259		Permanode blob.Ref `json:"permaNode"`
   260		Attribute string   `json:"attribute"`
   261		Value     string   `json:"value"`
   262	
   263		// FileName and FileNameBytes represent one of the two
   264		// representations of file names in schema blobs.  They should
   265		// not be accessed directly.  Use the FileNameString accessor
   266		// instead, which also sanitizes malicious values.
   267		FileName      string        `json:"fileName"`
   268		FileNameBytes []interface{} `json:"fileNameBytes"`
   269	
   270		SymlinkTarget      string        `json:"symlinkTarget"`
   271		SymlinkTargetBytes []interface{} `json:"symlinkTargetBytes"`
   272	
   273		UnixPermission string `json:"unixPermission"`
   274		UnixOwnerId    int    `json:"unixOwnerId"`
   275		UnixOwner      string `json:"unixOwner"`
   276		UnixGroupId    int    `json:"unixGroupId"`
   277		UnixGroup      string `json:"unixGroup"`
   278		UnixMtime      string `json:"unixMtime"`
   279		UnixCtime      string `json:"unixCtime"`
   280		UnixAtime      string `json:"unixAtime"`
   281	
   282		// Parts are references to the data chunks of a regular file (or a "bytes" schema blob).
   283		// See doc/schema/bytes.txt and doc/schema/files/file.txt.
   284		Parts []*BytesPart `json:"parts"`
   285	
   286		Entries   blob.Ref   `json:"entries"`   // for directories, a blobref to a static-set
   287		Members   []blob.Ref `json:"members"`   // for static sets (for directory static-sets: blobrefs to child dirs/files)
   288		MergeSets []blob.Ref `json:"mergeSets"` // each is a "sub static-set", that has either Members or MergeSets. For large dirs.
   289	
   290		// Search allows a "share" blob to share an entire search. Contrast with "target".
   291		Search SearchQuery `json:"search"`
   292		// Target is a "share" blob's target (the thing being shared)
   293		// Or it is the object being deleted in a DeleteClaim claim.
   294		Target blob.Ref `json:"target"`
   295		// Transitive is a property of a "share" blob.
   296		Transitive bool `json:"transitive"`
   297		// AuthType is a "share" blob's authentication type that is required.
   298		// Currently (2013-01-02) just "haveref" (if you know the share's blobref,
   299		// you get access: the secret URL model)
   300		AuthType string         `json:"authType"`
   301		Expires  types.Time3339 `json:"expires"` // or zero for no expiration
   302	}
   303	
   304	var errSchemaBlobTooLarge = errors.New("schema blob too large")
   305	
   306	func parseSuperset(r io.Reader) (*superset, error) {
   307		buf := pools.BytesBuffer()
   308		defer pools.PutBuffer(buf)
   309	
   310		n, err := io.CopyN(buf, r, MaxSchemaBlobSize+1)
   311		if err != nil && err != io.EOF {
   312			return nil, err
   313		}
   314		if n > MaxSchemaBlobSize {
   315			return nil, errSchemaBlobTooLarge
   316		}
   317	
   318		ss := new(superset)
   319		if err := json.Unmarshal(buf.Bytes(), ss); err != nil {
   320			return nil, err
   321		}
   322		return ss, nil
   323	}
   324	
   325	// BlobFromReader returns a new Blob from the provided Reader r,
   326	// which should be the body of the provided blobref.
   327	// Note: the hash checksum is not verified.
   328	func BlobFromReader(ref blob.Ref, r io.Reader) (*Blob, error) {
   329		if !ref.Valid() {
   330			return nil, errors.New("schema.BlobFromReader: invalid blobref")
   331		}
   332		var buf bytes.Buffer
   333		tee := io.TeeReader(r, &buf)
   334		ss, err := parseSuperset(tee)
   335		if err != nil {
   336			return nil, fmt.Errorf("error parsing Blob %v: %w", ref, err)
   337		}
   338		return &Blob{ref, buf.String(), ss}, nil
   339	}
   340	
   341	// BytesPart is the type representing one of the "parts" in a "file"
   342	// or "bytes" JSON schema.
   343	//
   344	// See doc/schema/bytes.txt and doc/schema/files/file.txt.
   345	type BytesPart struct {
   346		// Size is the number of bytes that this part contributes to the overall segment.
   347		Size uint64 `json:"size"`
   348	
   349		// At most one of BlobRef or BytesRef must be non-zero
   350		// (Valid), but it's illegal for both.
   351		// If neither are set, this BytesPart represents Size zero bytes.
   352		// BlobRef refers to raw bytes. BytesRef references a "bytes" schema blob.
   353		BlobRef  blob.Ref `json:"blobRef,omitempty"`
   354		BytesRef blob.Ref `json:"bytesRef,omitempty"`
   355	
   356		// Offset optionally specifies the offset into BlobRef to skip
   357		// when reading Size bytes.
   358		Offset uint64 `json:"offset,omitempty"`
   359	}
   360	
   361	// stringFromMixedArray joins a slice of either strings or float64
   362	// values (as retrieved from JSON decoding) into a string.  These are
   363	// used for non-UTF8 filenames in "fileNameBytes" fields.  The strings
   364	// are UTF-8 segments and the float64s (actually uint8 values) are
   365	// byte values.
   366	func stringFromMixedArray(parts []interface{}) string {
   367		var buf bytes.Buffer
   368		for _, part := range parts {
   369			if s, ok := part.(string); ok {
   370				buf.WriteString(s)
   371				continue
   372			}
   373			if num, ok := part.(float64); ok {
   374				buf.WriteByte(byte(num))
   375				continue
   376			}
   377		}
   378		return buf.String()
   379	}
   380	
   381	// mixedArrayFromString is the inverse of stringFromMixedArray. It
   382	// splits a string to a series of either UTF-8 strings and non-UTF-8
   383	// bytes.
   384	func mixedArrayFromString(s string) (parts []interface{}) {
   385		for len(s) > 0 {
   386			if n := utf8StrLen(s); n > 0 {
   387				parts = append(parts, s[:n])
   388				s = s[n:]
   389			} else {
   390				parts = append(parts, s[0])
   391				s = s[1:]
   392			}
   393		}
   394		return parts
   395	}
   396	
   397	// utf8StrLen returns how many prefix bytes of s are valid UTF-8.
   398	func utf8StrLen(s string) int {
   399		for i, r := range s {
   400			for r == utf8.RuneError {
   401				// The RuneError value can be an error
   402				// sentinel value (if it's size 1) or the same
   403				// value encoded properly. Decode it to see if
   404				// it's the 1 byte sentinel value.
   405				_, size := utf8.DecodeRuneInString(s[i:])
   406				if size == 1 {
   407					return i
   408				}
   409			}
   410		}
   411		return len(s)
   412	}
   413	
   414	func (ss *superset) SumPartsSize() (size uint64) {
   415		for _, part := range ss.Parts {
   416			size += uint64(part.Size)
   417		}
   418		return size
   419	}
   420	
   421	func (ss *superset) SymlinkTargetString() string {
   422		if ss.SymlinkTarget != "" {
   423			return ss.SymlinkTarget
   424		}
   425		return stringFromMixedArray(ss.SymlinkTargetBytes)
   426	}
   427	
   428	// FileNameString returns the schema blob's base filename.
   429	//
   430	// If the fileName field of the blob accidentally or maliciously
   431	// contains a slash, this function returns an empty string instead.
   432	func (ss *superset) FileNameString() string {
   433		v := ss.FileName
   434		if v == "" {
   435			v = stringFromMixedArray(ss.FileNameBytes)
   436		}
   437		if v != "" {
   438			if strings.Contains(v, "/") {
   439				// Bogus schema blob; ignore.
   440				return ""
   441			}
   442			if strings.Contains(v, "\\") {
   443				// Bogus schema blob; ignore.
   444				return ""
   445			}
   446		}
   447		return v
   448	}
   449	
   450	func (ss *superset) HasFilename(name string) bool {
   451		return ss.FileNameString() == name
   452	}
   453	
   454	func (b *Blob) FileMode() os.FileMode {
   455		// TODO: move this to a different type, off *Blob
   456		return b.ss.FileMode()
   457	}
   458	
   459	func (ss *superset) FileMode() os.FileMode {
   460		var mode os.FileMode
   461		hasPerm := ss.UnixPermission != ""
   462		if hasPerm {
   463			m64, err := strconv.ParseUint(ss.UnixPermission, 8, 64)
   464			if err == nil {
   465				mode = mode | os.FileMode(m64)
   466			}
   467		}
   468	
   469		// TODO: add other types (block, char, etc)
   470		switch ss.Type {
   471		case TypeDirectory:
   472			mode = mode | os.ModeDir
   473		case TypeFile:
   474			// No extra bit.
   475		case TypeSymlink:
   476			mode = mode | os.ModeSymlink
   477		case TypeFIFO:
   478			mode = mode | os.ModeNamedPipe
   479		case TypeSocket:
   480			mode = mode | os.ModeSocket
   481		}
   482		if !hasPerm {
   483			switch ss.Type {
   484			case TypeDirectory:
   485				mode |= 0755
   486			default:
   487				mode |= 0644
   488			}
   489		}
   490		return mode
   491	}
   492	
   493	// MapUid returns the most appropriate mapping from this file's owner
   494	// to the local machine's owner, trying first a match by name,
   495	// followed by just mapping the number through directly.
   496	func (b *Blob) MapUid() int { return b.ss.MapUid() }
   497	
   498	// MapGid returns the most appropriate mapping from this file's group
   499	// to the local machine's group, trying first a match by name,
   500	// followed by just mapping the number through directly.
   501	func (b *Blob) MapGid() int { return b.ss.MapGid() }
   502	
   503	func (ss *superset) MapUid() int {
   504		if ss.UnixOwner != "" {
   505			uid, ok := getUidFromName(ss.UnixOwner)
   506			if ok {
   507				return uid
   508			}
   509		}
   510		return ss.UnixOwnerId // TODO: will be 0 if unset, which isn't ideal
   511	}
   512	
   513	func (ss *superset) MapGid() int {
   514		if ss.UnixGroup != "" {
   515			gid, ok := getGidFromName(ss.UnixGroup)
   516			if ok {
   517				return gid
   518			}
   519		}
   520		return ss.UnixGroupId // TODO: will be 0 if unset, which isn't ideal
   521	}
   522	
   523	func (ss *superset) ModTime() time.Time {
   524		if ss.UnixMtime == "" {
   525			return time.Time{}
   526		}
   527		t, err := time.Parse(time.RFC3339, ss.UnixMtime)
   528		if err != nil {
   529			return time.Time{}
   530		}
   531		return t
   532	}
   533	
   534	var DefaultStatHasher = &defaultStatHasher{}
   535	
   536	type defaultStatHasher struct{}
   537	
   538	func (d *defaultStatHasher) Lstat(fileName string) (os.FileInfo, error) {
   539		return os.Lstat(fileName)
   540	}
   541	
   542	func (d *defaultStatHasher) Hash(fileName string) (blob.Ref, error) {
   543		h := blob.NewHash()
   544		file, err := os.Open(fileName)
   545		if err != nil {
   546			return blob.Ref{}, err
   547		}
   548		defer file.Close()
   549		_, err = io.Copy(h, file)
   550		if err != nil {
   551			return blob.Ref{}, err
   552		}
   553		return blob.RefFromHash(h), nil
   554	}
   555	
   556	// maximum number of static-set members in a static-set schema. As noted in
   557	// https://github.com/camlistore/camlistore/issues/924 , 33k members result in a
   558	// 1.7MB blob, so 10k members seems reasonable to stay under the MaxSchemaBlobSize (1MB)
   559	// limit. This is not a const, so we can lower it during tests and test the logic
   560	// without having to create thousands of blobs.
   561	var maxStaticSetMembers = 10000
   562	
   563	// NewStaticSet returns the "static-set" schema for a directory. Its members
   564	// should be populated with SetStaticSetMembers.
   565	func NewStaticSet() *Builder {
   566		return base(1, TypeStaticSet)
   567	}
   568	
   569	// SetStaticSetMembers sets the given members as the static-set members of this
   570	// builder. If the members are so numerous that they would not fit on a schema
   571	// blob, they are spread (recursively, if needed) onto sub static-sets. In which
   572	// case, these subsets are set as "mergeSets" of this builder. All the created
   573	// subsets are returned, so the caller can upload them along with the top
   574	// static-set created from this builder.
   575	// SetStaticSetMembers panics if bb isn't a "static-set" claim type.
   576	func (bb *Builder) SetStaticSetMembers(members []blob.Ref) []*Blob {
   577		if bb.Type() != TypeStaticSet {
   578			panic("called SetStaticSetMembers on non static-set")
   579		}
   580	
   581		if len(members) <= maxStaticSetMembers {
   582			ms := make([]string, len(members))
   583			for i := range members {
   584				ms[i] = members[i].String()
   585			}
   586			bb.m["members"] = ms
   587			return nil
   588		}
   589	
   590		// too many members to fit in one static-set, so we spread them in
   591		// several sub static-sets.
   592		subsetsNumber := len(members) / maxStaticSetMembers
   593		var perSubset int
   594		if subsetsNumber < maxStaticSetMembers {
   595			// this means we can fill each subset up to maxStaticSetMembers,
   596			// and stash the rest in one last subset.
   597			perSubset = maxStaticSetMembers
   598		} else {
   599			// otherwise we need to divide the members evenly in
   600			// (maxStaticSetMembers - 1) subsets, and each of these subsets
   601			// will also (recursively) have subsets of its own. There might
   602			// also be a rest in one last subset, as above.
   603			subsetsNumber = maxStaticSetMembers - 1
   604			perSubset = len(members) / subsetsNumber
   605		}
   606		// only the subsets at this level
   607		subsets := make([]*Blob, 0, subsetsNumber)
   608		// subsets at this level, plus all the children subsets.
   609		allSubsets := make([]*Blob, 0, subsetsNumber)
   610		for i := 0; i < subsetsNumber; i++ {
   611			ss := NewStaticSet()
   612			subss := ss.SetStaticSetMembers(members[i*perSubset : (i+1)*perSubset])
   613			subsets = append(subsets, ss.Blob())
   614			allSubsets = append(allSubsets, ss.Blob())
   615			allSubsets = append(allSubsets, subss...)
   616		}
   617	
   618		// Deal with the rest (of the euclidean division)
   619		if perSubset*subsetsNumber < len(members) {
   620			ss := NewStaticSet()
   621			ss.SetStaticSetMembers(members[perSubset*subsetsNumber:])
   622			allSubsets = append(allSubsets, ss.Blob())
   623			subsets = append(subsets, ss.Blob())
   624		}
   625	
   626		mss := make([]string, len(subsets))
   627		for i := range subsets {
   628			mss[i] = subsets[i].BlobRef().String()
   629		}
   630		bb.m["mergeSets"] = mss
   631		return allSubsets
   632	}
   633	
   634	func base(version int, ctype CamliType) *Builder {
   635		return &Builder{map[string]interface{}{
   636			"camliVersion": version,
   637			"camliType":    string(ctype),
   638		}}
   639	}
   640	
   641	// NewUnsignedPermanode returns a new random permanode, not yet signed.
   642	func NewUnsignedPermanode() *Builder {
   643		bb := base(1, TypePermanode)
   644		chars := make([]byte, 20)
   645		_, err := io.ReadFull(rand.Reader, chars)
   646		if err != nil {
   647			panic("error reading random bytes: " + err.Error())
   648		}
   649		bb.m["random"] = base64.StdEncoding.EncodeToString(chars)
   650		return bb
   651	}
   652	
   653	// NewPlannedPermanode returns a permanode with a fixed key.  Like
   654	// NewUnsignedPermanode, this builder is also not yet signed.  Callers of
   655	// NewPlannedPermanode must sign the map with a fixed claimDate and
   656	// GPG date to create consistent JSON encodings of the Map (its
   657	// blobref), between runs.
   658	func NewPlannedPermanode(key string) *Builder {
   659		bb := base(1, TypePermanode)
   660		bb.m["key"] = key
   661		return bb
   662	}
   663	
   664	// NewHashPlannedPermanode returns a planned permanode with the sum
   665	// of the hash, prefixed with "sha1-", as the key.
   666	func NewHashPlannedPermanode(h hash.Hash) *Builder {
   667		return NewPlannedPermanode(blob.RefFromHash(h).String())
   668	}
   669	
   670	// JSON returns the map m encoded as JSON in its
   671	// recommended canonical form. The canonical form is readable with newlines and indentation,
   672	// and always starts with the header bytes:
   673	//
   674	//	{"camliVersion":
   675	func mapJSON(m map[string]interface{}) (string, error) {
   676		version, hasVersion := m["camliVersion"]
   677		if !hasVersion {
   678			return "", ErrNoCamliVersion
   679		}
   680		delete(m, "camliVersion")
   681		jsonBytes, err := json.MarshalIndent(m, "", "  ")
   682		if err != nil {
   683			return "", err
   684		}
   685		m["camliVersion"] = version
   686		var buf bytes.Buffer
   687		fmt.Fprintf(&buf, "{\"camliVersion\": %v,\n", version)
   688		buf.Write(jsonBytes[2:])
   689		return buf.String(), nil
   690	}
   691	
   692	// NewFileMap returns a new builder of a type "file" schema for the provided fileName.
   693	// The chunk parts of the file are not populated.
   694	func NewFileMap(fileName string) *Builder {
   695		return newCommonFilenameMap(fileName).SetType(TypeFile)
   696	}
   697	
   698	// NewDirMap returns a new builder of a type "directory" schema for the provided fileName.
   699	func NewDirMap(fileName string) *Builder {
   700		return newCommonFilenameMap(fileName).SetType(TypeDirectory)
   701	}
   702	
   703	func newCommonFilenameMap(fileName string) *Builder {
   704		bb := base(1, "" /* no type yet */)
   705		if fileName != "" {
   706			bb.SetFileName(fileName)
   707		}
   708		return bb
   709	}
   710	
   711	var populateSchemaStat []func(schemaMap map[string]interface{}, fi os.FileInfo)
   712	
   713	func NewCommonFileMap(fileName string, fi os.FileInfo) *Builder {
   714		bb := newCommonFilenameMap(fileName)
   715		// Common elements (from file-common.txt)
   716		if fi.Mode()&os.ModeSymlink == 0 {
   717			bb.m["unixPermission"] = fmt.Sprintf("0%o", fi.Mode().Perm())
   718		}
   719	
   720		// OS-specific population; defined in schema_posix.go, etc. (not on App Engine)
   721		for _, f := range populateSchemaStat {
   722			f(bb.m, fi)
   723		}
   724	
   725		if mtime := fi.ModTime(); !mtime.IsZero() {
   726			bb.m["unixMtime"] = RFC3339FromTime(mtime)
   727		}
   728		return bb
   729	}
   730	
   731	// PopulateParts sets the "parts" field of the blob with the provided
   732	// parts.  The sum of the sizes of parts must match the provided size
   733	// or an error is returned.  Also, each BytesPart may only contain either
   734	// a BytesPart or a BlobRef, but not both.
   735	func (bb *Builder) PopulateParts(size int64, parts []BytesPart) error {
   736		return populateParts(bb.m, size, parts)
   737	}
   738	
   739	func populateParts(m map[string]interface{}, size int64, parts []BytesPart) error {
   740		sumSize := int64(0)
   741		mparts := make([]map[string]interface{}, len(parts))
   742		for idx, part := range parts {
   743			mpart := make(map[string]interface{})
   744			mparts[idx] = mpart
   745			switch {
   746			case part.BlobRef.Valid() && part.BytesRef.Valid():
   747				return errors.New("schema: part contains both BlobRef and BytesRef")
   748			case part.BlobRef.Valid():
   749				mpart["blobRef"] = part.BlobRef.String()
   750			case part.BytesRef.Valid():
   751				mpart["bytesRef"] = part.BytesRef.String()
   752			default:
   753				return errors.New("schema: part must contain either a BlobRef or BytesRef")
   754			}
   755			mpart["size"] = part.Size
   756			sumSize += int64(part.Size)
   757			if part.Offset != 0 {
   758				mpart["offset"] = part.Offset
   759			}
   760		}
   761		if sumSize != size {
   762			return fmt.Errorf("schema: declared size %d doesn't match sum of parts size %d", size, sumSize)
   763		}
   764		m["parts"] = mparts
   765		return nil
   766	}
   767	
   768	func newBytes() *Builder {
   769		return base(1, TypeBytes)
   770	}
   771	
   772	// CamliType is one of the valid "camliType" fields in a schema blob. See doc/schema.
   773	type CamliType string
   774	
   775	const (
   776		TypeBytes     CamliType = "bytes"
   777		TypeClaim     CamliType = "claim"
   778		TypeDirectory CamliType = "directory"
   779		TypeFIFO      CamliType = "fifo"
   780		TypeFile      CamliType = "file"
   781		TypeInode     CamliType = "inode"
   782		TypeKeep      CamliType = "keep"
   783		TypePermanode CamliType = "permanode"
   784		TypeShare     CamliType = "share"
   785		TypeSocket    CamliType = "socket"
   786		TypeStaticSet CamliType = "static-set"
   787		TypeSymlink   CamliType = "symlink"
   788	)
   789	
   790	// ClaimType is one of the valid "claimType" fields in a "claim" schema blob. See doc/schema/claims/.
   791	type ClaimType string
   792	
   793	const (
   794		SetAttributeClaim ClaimType = "set-attribute"
   795		AddAttributeClaim ClaimType = "add-attribute"
   796		DelAttributeClaim ClaimType = "del-attribute"
   797		ShareClaim        ClaimType = "share"
   798		// DeleteClaim deletes a permanode or another claim.
   799		// A delete claim can itself be deleted, and so on.
   800		DeleteClaim ClaimType = "delete"
   801	)
   802	
   803	// claimParam is used to populate a claim map when building a new claim
   804	type claimParam struct {
   805		claimType ClaimType
   806	
   807		// Params specific to *Attribute claims:
   808		permanode blob.Ref // modified permanode
   809		attribute string   // required
   810		value     string   // optional if Type == DelAttributeClaim
   811	
   812		// Params specific to ShareClaim claims:
   813		authType   string
   814		transitive bool
   815	
   816		// Params specific to ShareClaim and DeleteClaim claims.
   817		target blob.Ref
   818	}
   819	
   820	func newClaim(claims ...*claimParam) *Builder {
   821		bb := base(1, TypeClaim)
   822		bb.SetClaimDate(clockNow())
   823		if len(claims) == 1 {
   824			cp := claims[0]
   825			populateClaimMap(bb.m, cp)
   826			return bb
   827		}
   828		var claimList []interface{}
   829		for _, cp := range claims {
   830			m := map[string]interface{}{}
   831			populateClaimMap(m, cp)
   832			claimList = append(claimList, m)
   833		}
   834		bb.m["claimType"] = "multi"
   835		bb.m["claims"] = claimList
   836		return bb
   837	}
   838	
   839	func populateClaimMap(m map[string]interface{}, cp *claimParam) {
   840		m["claimType"] = string(cp.claimType)
   841		switch cp.claimType {
   842		case ShareClaim:
   843			m["authType"] = cp.authType
   844			m["transitive"] = cp.transitive
   845		case DeleteClaim:
   846			m["target"] = cp.target.String()
   847		default:
   848			m["permaNode"] = cp.permanode.String()
   849			m["attribute"] = cp.attribute
   850			if !(cp.claimType == DelAttributeClaim && cp.value == "") {
   851				m["value"] = cp.value
   852			}
   853		}
   854	}
   855	
   856	// NewShareRef creates a *Builder for a "share" claim.
   857	func NewShareRef(authType string, transitive bool) *Builder {
   858		return newClaim(&claimParam{
   859			claimType:  ShareClaim,
   860			authType:   authType,
   861			transitive: transitive,
   862		})
   863	}
   864	
   865	func NewSetAttributeClaim(permaNode blob.Ref, attr, value string) *Builder {
   866		return newClaim(&claimParam{
   867			permanode: permaNode,
   868			claimType: SetAttributeClaim,
   869			attribute: attr,
   870			value:     value,
   871		})
   872	}
   873	
   874	func NewAddAttributeClaim(permaNode blob.Ref, attr, value string) *Builder {
   875		return newClaim(&claimParam{
   876			permanode: permaNode,
   877			claimType: AddAttributeClaim,
   878			attribute: attr,
   879			value:     value,
   880		})
   881	}
   882	
   883	// NewDelAttributeClaim creates a new claim to remove value from the
   884	// values set for the attribute attr of permaNode. If value is empty then
   885	// all the values for attribute are cleared.
   886	func NewDelAttributeClaim(permaNode blob.Ref, attr, value string) *Builder {
   887		return newClaim(&claimParam{
   888			permanode: permaNode,
   889			claimType: DelAttributeClaim,
   890			attribute: attr,
   891			value:     value,
   892		})
   893	}
   894	
   895	// NewDeleteClaim creates a new claim to delete a target claim or permanode.
   896	func NewDeleteClaim(target blob.Ref) *Builder {
   897		return newClaim(&claimParam{
   898			target:    target,
   899			claimType: DeleteClaim,
   900		})
   901	}
   902	
   903	// ShareHaveRef is the auth type specifying that if you "have the
   904	// reference" (know the blobref to the haveref share blob), then you
   905	// have access to the referenced object from that share blob.
   906	// This is the "send a link to a friend" access model.
   907	const ShareHaveRef = "haveref"
   908	
   909	// UnknownLocation is a magic timezone value used when the actual location
   910	// of a time is unknown. For instance, EXIF files commonly have a time without
   911	// a corresponding location or timezone offset.
   912	var UnknownLocation = time.FixedZone("Unknown", -60) // 1 minute west
   913	
   914	// IsZoneKnown reports whether t is in a known timezone.
   915	// Perkeep uses the magic timezone offset of 1 minute west of UTC
   916	// to mean that the timezone wasn't known.
   917	func IsZoneKnown(t time.Time) bool {
   918		if t.Location() == UnknownLocation {
   919			return false
   920		}
   921		if _, off := t.Zone(); off == -60 {
   922			return false
   923		}
   924		return true
   925	}
   926	
   927	// RFC3339FromTime returns an RFC3339-formatted time.
   928	//
   929	// If the timezone is known, the time will be converted to UTC and
   930	// returned with a "Z" suffix. For unknown zones, the timezone will be
   931	// "-00:01" (1 minute west of UTC).
   932	//
   933	// Fractional seconds are only included if the time has fractional
   934	// seconds.
   935	func RFC3339FromTime(t time.Time) string {
   936		if IsZoneKnown(t) {
   937			t = t.UTC()
   938		}
   939		if t.UnixNano()%1e9 == 0 {
   940			return t.Format(time.RFC3339)
   941		}
   942		return t.Format(time.RFC3339Nano)
   943	}
   944	
   945	var bytesCamliVersion = []byte("camliVersion")
   946	
   947	// LikelySchemaBlob returns quickly whether buf likely contains (or is
   948	// the prefix of) a schema blob.
   949	func LikelySchemaBlob(buf []byte) bool {
   950		if len(buf) == 0 || buf[0] != '{' {
   951			return false
   952		}
   953		return bytes.Contains(buf, bytesCamliVersion)
   954	}
   955	
   956	// findSize checks if v is an *os.File or if it has
   957	// a Size() int64 method, to find its size.
   958	// It returns 0, false otherwise.
   959	func findSize(v interface{}) (size int64, ok bool) {
   960		if fi, ok := v.(*os.File); ok {
   961			v, _ = fi.Stat()
   962		}
   963		if sz, ok := v.(interface {
   964			Size() int64
   965		}); ok {
   966			return sz.Size(), true
   967		}
   968		// For bytes.Reader, strings.Reader, etc:
   969		if li, ok := v.(interface {
   970			Len() int
   971		}); ok {
   972			ln := int64(li.Len()) // unread portion, typically
   973			// If it's also a seeker, remove add any seek offset:
   974			if sk, ok := v.(io.Seeker); ok {
   975				if cur, err := sk.Seek(0, 1); err == nil {
   976					ln += cur
   977				}
   978			}
   979			return ln, true
   980		}
   981		return 0, false
   982	}
   983	
   984	// FileTime returns the best guess of the file's creation time (or modtime).
   985	// If the file doesn't have its own metadata indication the creation time (such as in EXIF),
   986	// FileTime uses the modification time from the file system.
   987	// It there was a valid EXIF but an error while trying to get a date from it,
   988	// it logs the error and tries the other methods.
   989	func FileTime(f io.ReaderAt) (time.Time, error) {
   990		var ct time.Time
   991		defaultTime := func() (time.Time, error) {
   992			if osf, ok := f.(*os.File); ok {
   993				fi, err := osf.Stat()
   994				if err != nil {
   995					return ct, fmt.Errorf("Failed to find a modtime: stat: %w", err)
   996				}
   997				return fi.ModTime(), nil
   998			}
   999			return ct, errors.New("all methods failed to find a creation time or modtime")
  1000		}
  1001	
  1002		size, ok := findSize(f)
  1003		if !ok {
  1004			size = 256 << 10 // enough to get the EXIF
  1005		}
  1006		r := io.NewSectionReader(f, 0, size)
  1007		var tiffErr error
  1008		ex, err := exif.Decode(r)
  1009		if err != nil {
  1010			tiffErr = err
  1011			if exif.IsShortReadTagValueError(err) {
  1012				return ct, io.ErrUnexpectedEOF
  1013			}
  1014			if exif.IsCriticalError(err) || exif.IsExifError(err) {
  1015				return defaultTime()
  1016			}
  1017		}
  1018		ct, err = ex.DateTime()
  1019		if err != nil {
  1020			return defaultTime()
  1021		}
  1022		// If the EXIF file only had local timezone, but it did have
  1023		// GPS, then lookup the timezone and correct the time.
  1024		if ct.Location() == time.Local {
  1025			if exif.IsGPSError(tiffErr) {
  1026				log.Printf("Invalid EXIF GPS data: %v", tiffErr)
  1027				return ct, nil
  1028			}
  1029			if lat, long, err := ex.LatLong(); err == nil {
  1030				if loc := lookupLocation(latlong.LookupZoneName(lat, long)); loc != nil {
  1031					if t, err := exifDateTimeInLocation(ex, loc); err == nil {
  1032						return t, nil
  1033					}
  1034				}
  1035			} else if !exif.IsTagNotPresentError(err) {
  1036				log.Printf("Invalid EXIF GPS data: %v", err)
  1037			}
  1038		}
  1039		return ct, nil
  1040	}
  1041	
  1042	// This is basically a copy of the exif.Exif.DateTime() method, except:
  1043	//   - it takes a *time.Location to assume
  1044	//   - the caller already assumes there's no timezone offset or GPS time
  1045	//     in the EXIF, so any of that code can be ignored.
  1046	func exifDateTimeInLocation(x *exif.Exif, loc *time.Location) (time.Time, error) {
  1047		tag, err := x.Get(exif.DateTimeOriginal)
  1048		if err != nil {
  1049			tag, err = x.Get(exif.DateTime)
  1050			if err != nil {
  1051				return time.Time{}, err
  1052			}
  1053		}
  1054		if tag.Format() != tiff.StringVal {
  1055			return time.Time{}, errors.New("DateTime[Original] not in string format")
  1056		}
  1057		const exifTimeLayout = "2006:01:02 15:04:05"
  1058		dateStr := strings.TrimRight(string(tag.Val), "\x00")
  1059		return time.ParseInLocation(exifTimeLayout, dateStr, loc)
  1060	}
  1061	
  1062	var zoneCache struct {
  1063		sync.RWMutex
  1064		m map[string]*time.Location
  1065	}
  1066	
  1067	func lookupLocation(zone string) *time.Location {
  1068		if zone == "" {
  1069			return nil
  1070		}
  1071		zoneCache.RLock()
  1072		l, ok := zoneCache.m[zone]
  1073		zoneCache.RUnlock()
  1074		if ok {
  1075			return l
  1076		}
  1077		// could use singleflight here, but doesn't really
  1078		// matter if two callers both do this.
  1079		loc, err := time.LoadLocation(zone)
  1080	
  1081		zoneCache.Lock()
  1082		if zoneCache.m == nil {
  1083			zoneCache.m = make(map[string]*time.Location)
  1084		}
  1085		zoneCache.m[zone] = loc // even if nil
  1086		zoneCache.Unlock()
  1087	
  1088		if err != nil {
  1089			log.Printf("failed to lookup timezone %q: %v", zone, err)
  1090			return nil
  1091		}
  1092		return loc
  1093	}
  1094	
  1095	var boringTitlePattern = regexp.MustCompile(`^(?:IMG_|DSC|PANO_|ESR_).*$`)
  1096	
  1097	// IsInterestingTitle returns whether title would be interesting information as
  1098	// a title for a permanode. For example, filenames automatically created by
  1099	// cameras, such as IMG_XXXX.JPG, do not add any interesting value.
  1100	func IsInterestingTitle(title string) bool {
  1101		return !boringTitlePattern.MatchString(title)
  1102	}