gdrive.go

//
// gdrive.go
// Copyright(c)2014-2015 Google, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

// Package gdrive provides a slightly higher-level API for Google Drive
// than is provided by the official Google Drive API Go language bindings.
// In addition to handling transient network errors, rate limit
// errors, and other http miscellania, gdrive also provides functionality
// for limiting bandwidth consumption in both uploads and downloads.
//
// gdrive was written to be independent of the skicka application; issues
// like encryption, mapping Google Drive files to Unix file semantics,
// etc., are intentionally not included here.
package gdrive

import (
	"encoding/gob"
	"errors"
	"fmt"
	"io"
	"io/ioutil"
	"log"
	"net/http"
	"os"
	"path/filepath"
	"runtime"
	"sort"
	"strings"
	"sync"
	"time"

	"github.com/cheggaaa/pb"
	"google.golang.org/api/drive/v2"
	"google.golang.org/api/googleapi"
)

const timeFormat = "2006-01-02T15:04:05.000000000Z07:00"

///////////////////////////////////////////////////////////////////////////

// TODO: The File representation doesn't quite work in the case where
// multiple paths on Drive refer to the same underlying file; for example,
// if we update such a file's modification time on Drive and update the
// local metadata to reflect this (which we don't yet..), then the metadata
// won't reflect the modification time for other paths that point to the
// file.  It may be best to have File be just a Path and a pointer to a new
// FileMetadata struct.

// File represents a file or folder in Google Drive.
type File struct {
	// Path name on Drive. Does not start with a slash.
	Path string
	// Size of the file in bytes.
	FileSize int64
	// Unique id of the file (that persists over file modifications,
	// renamings, etc.) This value is generated by Google Drive when a file
	// is first created.
	Id string
	// MD5 checksum of the file's contents.
	Md5      string
	MimeType string
	// Last time that the file's contents were modified.
	ModTime time.Time
	// Array of Google Drive file ids for the folder or folders that have
	// this file in it.
	ParentIds []string
	// User-defined properties associated with the file.
	Properties []Property
}

// newFile returns a new gdrive.File corresponding to the given Google
// Drive file. The path to the file on Drive should be provided for the
// path parameter.
func newFile(path string, f *drive.File) *File {
	modTime := time.Unix(0, 0)
	if f.ModifiedDate != "" {
		modTime, _ = time.Parse(time.RFC3339Nano, f.ModifiedDate)
	}

	var properties []Property
	for _, p := range f.Properties {
		properties = append(properties, Property{Key: p.Key, Value: p.Value})
	}

	var parentIds []string
	for _, p := range f.Parents {
		parentIds = append(parentIds, p.Id)
	}

	return &File{
		Path:       path,
		FileSize:   f.FileSize,
		Id:         f.Id,
		Md5:        f.Md5Checksum,
		MimeType:   f.MimeType,
		ModTime:    modTime,
		ParentIds:  parentIds,
		Properties: properties,
	}
}

// driveFile returns a new *drive.File that corresponds to the gdrive.File.
func (f *File) driveFile() *drive.File {
	var parents []*drive.ParentReference
	for _, pid := range f.ParentIds {
		parents = append(parents, &drive.ParentReference{Id: pid})
	}

	return &drive.File{
		Title:        filepath.Base(f.Path),
		FileSize:     f.FileSize,
		Id:           f.Id,
		Md5Checksum:  f.Md5,
		MimeType:     f.MimeType,
		ModifiedDate: f.ModTime.UTC().Format(timeFormat),
		Parents:      parents,
		Properties:   convertProplist(f.Properties),
	}
}

// IsFolder returns a boolean indicating whether the given File is a
// folder.
func (f *File) IsFolder() bool {
	return f.MimeType == "application/vnd.google-apps.folder"
}

// IsGoogleAppsFile returns a boolean indicating whether the given File was created
// with Google Docs, Google Sheets, etc.
func (f *File) IsGoogleAppsFile() bool {
	return !f.IsFolder() && strings.HasPrefix(f.MimeType, "application/vnd.google-apps.")
}

// Property represents a user-specified property associated with a Drive
// file.
type Property struct {
	Key, Value string
}

// GetProperty returns the property of the given name associated with the
// given file, if the named property is present.  If the property isn't
// present in the fie, then an empty string and an error are returned.
func (f *File) GetProperty(name string) (string, error) {
	for _, prop := range f.Properties {
		if prop.Key == name {
			return prop.Value, nil
		}
	}
	return "", fmt.Errorf("%s: property not found", name)
}

// Helper declarations to be able to sort an array of File values by
// pathname.
type byPath []*File

func (a byPath) Len() int           { return len(a) }
func (a byPath) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a byPath) Less(i, j int) bool { return a[i].Path < a[j].Path }

///////////////////////////////////////////////////////////////////////////

var ErrNotExist = errors.New("file does not exist")
var ErrMultipleFiles = errors.New("multiple files on Drive")

///////////////////////////////////////////////////////////////////////////
// GDrive

// GDrive encapsulates a session for performing operations with Google
// Drive. It provides a variety of methods for working with files and
// folders stored in Google Drive.
type GDrive struct {
	client *http.Client
	svc    *drive.Service
	debug  func(s string, args ...interface{})
	quiet  bool
	// Mutex that must be held when accessing dirToFiles or pathToFile.
	metadataMutex sync.Mutex
	// mapping from directory names to array of File pointers corresponding
	// to the files in that directory.
	dirToFiles map[string][]*File
	// mapping from path names to File pointers representing files or
	// directories on Drive. Note that multiple files may have the same
	// path on Drive.
	pathToFile map[string][]*File
}

///////////////////////////////////////////////////////////////////////////
// Utility routines

const maxRetries = 6

// There are a number of cases where the Google Drive API returns an error
// code but where it's possible to recover from the error; examples 403/500
// errors when we make too many API calls too quickly and we get a rate
// limit error.  This function takes an error returned by a Drive API call
// and the number of times that we've tried to call the API entrypoint
// already and does its best to handle the error.
//
// If it thinks the error may be transient, it returns nil, and the caller
// should try the call again. For unrecoverable errors (or putatively
// transient ones that don't clear up after multiple tries), it returns the
// error code back and the caller should stop trying.
func (gd *GDrive) tryToHandleDriveAPIError(err error, try int) error {
	gd.debug("tryToHandleDriveAPIError: try %d error %T %+v",
		try, err, err)

	if try == maxRetries {
		return err
	}
	gd.exponentialBackoff(try, nil, err)
	return nil
}

// GetFileById returns the *drive.File corresponding to the string Id
// Google Drive uses to uniquely identify the file. It deals with timeouts
// and transient errors.
func (gd *GDrive) GetFileById(id string) (*drive.File, error) {
	gd.debug("GetFileById: %s", id)
	for try := 0; ; try++ {
		file, err := gd.svc.Files.Get(id).Do()
		if err == nil {
			return file, nil
		} else if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
			return nil, err
		}
	}
}

// runQuery executes the given query with the Google Drive API, calling the
// given callback function with each file that matches the query's
// conditions.
func (gd *GDrive) runQuery(query string, process func(*drive.File)) error {
	gd.debug("Running query: %s", query)

	pageToken := ""
	for try := 0; ; try++ {
		q := gd.svc.Files.List().Q(query)
		if pageToken != "" {
			q = q.PageToken(pageToken)
		}

		r, err := q.Do()
		if err != nil {
			if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
				return err
			}
		} else {
			for _, f := range r.Items {
				process(f)
			}

			pageToken = r.NextPageToken
			if pageToken == "" {
				return nil
			}
		}
	}
}

///////////////////////////////////////////////////////////////////////////
// Public Interface

// New returns a pointer to a new GDrive instance.
//
// The uploadBytesPerSecond and downloadBytesPerSecond parameters can be
// used to specify bandwidth limits if rate-limited uploads or downloads
// are desired.  If zero, bandwidth use is unconstrained.
//
// The debug parameter can be used to provide a callback function to be
// used to log debugging information and all HTTP requrests go over the
// provided http.Client.  Finally, metadata about files stored on
// Drive is cached locally in metadataCacheFilename.
func New(uploadBytesPerSecond, downloadBytesPerSecond int,
	debug func(s string, args ...interface{}), client *http.Client,
	metadataCacheFilename string, quiet bool) (*GDrive, error) {
	gd := &GDrive{
		debug:  debug,
		quiet:  quiet,
		client: client,
	}

	var err error
	if gd.svc, err = drive.New(client); err != nil {
		return nil, err
	}

	launchBandwidthTask(uploadBytesPerSecond, downloadBytesPerSecond)

	err = gd.UpdateMetadataCache(metadataCacheFilename)
	if err != nil {
		return nil, err
	}
	return gd, nil
}

func (gd *GDrive) getMetadataChanges(svc *drive.Service, startChangeId int64,
	changeChan chan<- []*drive.Change, errorChan chan<- error) {
	var about *drive.About
	var err error

	// Get the Drive About information in order to figure out how many
	// changes we need to download to get up to date.
	for try := 0; ; try++ {
		about, err = svc.About.Get().Do()
		if err == nil {
			break
		} else {
			err = gd.tryToHandleDriveAPIError(err, try)
		}
		if err != nil {
			errorChan <- err
			return
		}
	}

	// Don't clutter the output with a progress bar unless it looks like
	// downloading changes may take a while.
	// TODO: consider using timer.AfterFunc to put up the progress bar if
	// we're not done after a few seconds?  It's not clear if this is worth
	// the trouble.
	var bar *pb.ProgressBar
	numChanges := about.LargestChangeId - startChangeId
	if numChanges > 1000 && !gd.quiet {
		bar = pb.New64(numChanges)
		bar.ShowBar = true
		bar.ShowCounters = false
		bar.Output = os.Stderr
		bar.Prefix("Updating metadata cache: ")
		bar.Start()
	}

	pageToken := ""
	try := 0
	// Keep asking Drive for more changes until we get through them all.
	for {
		// Only ask for the fields in the drive.Change structure that we
		// actually to be filled in to save some bandwidth...
		fields := []googleapi.Field{"nextPageToken",
			"items/id", "items/fileId", "items/deleted",
			"items/file/id", "items/file/parents", "items/file/title",
			"items/file/fileSize", "items/file/mimeType", "items/file/properties",
			"items/file/modifiedDate", "items/file/md5Checksum", "items/file/labels"}
		q := svc.Changes.List().MaxResults(1000).IncludeSubscribed(false).Fields(fields...)
		if startChangeId >= 0 {
			q = q.StartChangeId(startChangeId + 1)
		}
		if pageToken != "" {
			q = q.PageToken(pageToken)
		}

		r, err := q.Do()
		if err != nil {
			err = gd.tryToHandleDriveAPIError(err, try)
			if err != nil {
				errorChan <- err
				return
			}
			try++
			continue
		}

		// Success. Reset the try counter in case we had errors leading up
		// to this.
		try = 0

		if len(r.Items) > 0 {
			// Send the changes along to the goroutine that's updating the
			// local cache.
			changeChan <- r.Items

			if bar != nil {
				bar.Set(int(r.Items[len(r.Items)-1].Id - startChangeId))
			}
		}

		pageToken = string(r.NextPageToken)
		if pageToken == "" {
			break
		}
	}
	// Signal that no more changes are coming.
	close(changeChan)

	if bar != nil {
		bar.Finish()
	}

	gd.debug("Done updating metadata from Drive")
}

// saveMetadataCache saves both the current maximum change id as well as
// the mapping from Drive file id's to *drive.File objects into the given
// file.
func (gd *GDrive) saveMetadataCache(filename string, maxChangeId int64,
	m map[string]*File) error {
	// Save the information into a temporary file; when we're done, we'll
	// rename this to the destination filename.  This ensures that the
	// update is atomic and we don't accidentally write a partial file if
	// we're interrupted.
	f, err := ioutil.TempFile("", "skicka.metadata")
	if err != nil {
		return err
	}
	defer os.Remove(f.Name())

	e := gob.NewEncoder(f)

	// First goes the metadata verion number.
	version := 1
	if err := e.Encode(version); err != nil {
		return err
	}
	// Then goes the current change id from Drive.
	if err := e.Encode(maxChangeId); err != nil {
		return err
	}
	// Next goes the serialized map from strings to File structures.
	if err := e.Encode(m); err != nil {
		return err
	}
	// Make sure it has all successfully landed on disk.
	if err := f.Sync(); err != nil {
		return err
	}
	if err := f.Close(); err != nil {
		return err
	}
	// Try to rename the temporary file to the actual cache filename; this
	// ensures that we have an atomic update and don't inadvertently write
	// out a truncated file if there's an error.
	if err = os.Rename(f.Name(), filename); err != nil {
		// The rename may fail, for example if the two files are on
		// different filesystems.
		gd.debug("%s -> %s: rename failed. Trying manual copy.", f.Name(), filename)

		ftmp, err := os.Open(f.Name())
		if err != nil {
			return err
		}
		defer ftmp.Close()

		// Try making a temporary file in the same directory as the
		// eventual destination file.
		flocal, err := ioutil.TempFile(filepath.Dir(filename), ".skicka.metadata")
		if err != nil {
			return err
		}
		// This remove will return an error if the Rename() below
		// succeeds. That's fine.
		defer os.Remove(flocal.Name())

		if _, err := io.Copy(flocal, ftmp); err != nil {
			flocal.Close()
			return err
		} else if err := flocal.Close(); err != nil {
			return err
		}

		// Windows doesn't let us rename one file on top of an existing
		// one. Therefore, when running on Windows, remove the target file
		// first.
		if runtime.GOOS == "windows" {
			_ = os.Remove(filename)
		}

		if err := os.Rename(flocal.Name(), filename); err != nil {
			return err
		}
	}

	gd.debug("Done writing new file cache to disk")
	return nil
}

// UpdateMetadataCache initializes the local cache of metadata about the
// files and folders currently on Google Drive, reading content from
// filename and querying Drive for changes.  If updates are found, the
// local cache in filename is updated.
func (gd *GDrive) UpdateMetadataCache(filename string) error {
	if runtime.GOOS != "windows" {
		// Warn if the metadata cache file is readable by other users.
		if stat, err := os.Stat(filename); err == nil {
			perms := stat.Mode() & ((1 << 6) - 1)
			if perms != 0 {
				fmt.Fprintf(os.Stderr, "skicka: %s: permissions allow group/other "+
					"access. Metadata about your Drive files is accessible by others.",
					filename)
			}
		}
	}

	idToFile, err := gd.getIdToFile(filename)
	if err != nil {
		return err
	}

	gd.metadataMutex.Lock()
	defer gd.metadataMutex.Unlock()

	// Convert the idToFile map to one map from parent folder path to array
	// of Files in the folder and to a second map from path to array of
	// Files at that path.
	gd.dirToFiles = make(map[string][]*File)
	gd.pathToFile = make(map[string][]*File)

	// TODO: store the root file metadata in the cache as well to avoid
	// doing this each time.
	rootDriveFile, err := gd.GetFileById("root")
	if err != nil {
		return err
	}
	rootFile := newFile(".", rootDriveFile)
	gd.pathToFile[rootFile.Path] = append(gd.pathToFile[rootFile.Path], rootFile)
	idToFile[rootDriveFile.Id] = rootFile

	for _, f := range idToFile {
		// Because files in Google Drive may have multiple parent folders
		// (which themselves may have multiple parents), each file may have
		// multiple paths that refer to it.  To find them, we start from the
		// file and walk up through all of its parents, recursively, prepending
		// the parent folder's name to the in-progress path until we hit the
		// root directory.  The path is then added to the paths array.
		var paths []string
		for _, parentId := range f.ParentIds {
			getFilePath(f.Path, parentId, idToFile, &paths)
		}
		for _, p := range paths {
			// Create a new File instance for each path where this file is
			// found. (We don't want to clobber the Path member if there
			// are multiple paths).  See the TODO above the File struct
			// declaration for an issue with this approach, though.
			file := new(File)
			*file = *f
			file.Path = p

			gd.pathToFile[p] = append(gd.pathToFile[p], file)

			dir := filepath.Dir(p)
			gd.dirToFiles[dir] = append(gd.dirToFiles[dir], file)
		}
	}

	return nil
}

// Google Drive associates a unique string id with each file and folder.
// Updates in the changes stream are all in terms of (file id, change).
// Therefore, we serialize the mapping id->gdrive.File to disk and update
// this mapping with updates from Drive.  Only once it is up-to-date do we
// convert this representation to one that is more useful to the operations
// that the gdrive package provides.
func (gd *GDrive) getIdToFile(filename string) (map[string]*File, error) {
	maxChangeId := int64(-1)

	// Channel to carry change records from Drive.  Make sure that a decent
	// number of changes can be buffered up in case reading existing
	// metadata from disk takes a while.  (Otherwise, the goroutine getting
	// changes from Drive may block.)
	changeChan := make(chan []*drive.Change, 32)
	errorChan := make(chan error)

	idToFile := make(map[string]*File)

	f, err := os.Open(filename)
	if err == nil {
		// A metadata cache file exists.
		defer f.Close()
		decoder := gob.NewDecoder(f)

		var version int
		if err := decoder.Decode(&version); err != nil {
			return nil, err
		}
		if version != 1 {
			return nil, fmt.Errorf("metadata file version %d unknown to this version"+
				"of skicka", version)
		}

		if err := decoder.Decode(&maxChangeId); err != nil {
			return nil, err
		}
		gd.debug("Read max change id %d", maxChangeId)

		// As soon as we know the id of the last change in the metadata
		// file, we can kick off the goroutine that starts pulling changes
		// from Google Drive.  This can happen concurrently with reading
		// the cache from disk.
		go gd.getMetadataChanges(gd.svc, maxChangeId, changeChan, errorChan)

		// Read the rest of the metadata.
		if err := decoder.Decode(&idToFile); err != nil {
			return nil, err
		}
		f.Close()
		gd.debug("Done reading file cache from disk")
	} else {
		// No metadata available locally; pull the entire history from Drive.
		go gd.getMetadataChanges(gd.svc, maxChangeId, changeChan, errorChan)
	}

	// Only after the metadata has been read from disk can we start
	// processing updates to it from Drive.
	newMaxChangeId := maxChangeId
outer:
	for {
		select {
		case changes, ok := <-changeChan:
			if !ok {
				break outer
			}

			for _, c := range changes {
				if c.Id < newMaxChangeId {
					panic(fmt.Sprintf("Change id %d less than max %d!", c.Id,
						newMaxChangeId))
				}
				newMaxChangeId = c.Id

				if c.Deleted ||
					(c.File != nil && c.File.Labels != nil && c.File.Labels.Trashed) {
					delete(idToFile, c.FileId)
				} else {
					// For the files in the idToFile map, we overload File.Path
					// to store the file's name for now.
					idToFile[c.File.Id] = newFile(c.File.Title, c.File)
				}
			}
		case err = <-errorChan:
			return nil, err
		}
	}
	gd.debug("File cache has %d items", len(idToFile))

	if newMaxChangeId > maxChangeId {
		gd.debug("Writing updated file cache to disk: maxChangeId now %d",
			newMaxChangeId)
		err := gd.saveMetadataCache(filename, newMaxChangeId, idToFile)
		if err != nil {
			return nil, err
		}
	}

	return idToFile, nil
}

func getFilePath(path string, parentId string, idToFile map[string]*File, paths *[]string) {
	if parentFile, ok := idToFile[parentId]; ok {
		if len(parentFile.ParentIds) == 0 {
			// We're at the root, which doesn't have any parents.
			// Double-check, though.
			if parentFile.Path != "." {
				panic(fmt.Sprintf("no parents for file %+v with WIP path %s "+
					"but parent path isn't \".\"?", parentFile, path))
			}
			*paths = append(*paths, path)
		} else {
			for _, grandParentId := range parentFile.ParentIds {
				newPath := filepath.Join(parentFile.Path, path)
				getFilePath(newPath, grandParentId, idToFile, paths)
			}
		}
	}
	// If one of the parent files doesn't exist in idToFile, then this
	// means that it has been deleted or trashed. In that case, the current
	// file is also deleted/trashed and so we just return without appending
	// it to the paths array.
}

// CheckMetadata downloads the metadata about all of the files currently
// stored on Drive and compares it with the local cache.
func (gd *GDrive) CheckMetadata(filename string, report func(string)) error {
	idToFile, err := gd.getIdToFile(filename)
	if err != nil {
		return err
	}

	// This will almost certainly take a while, so put up a progress bar.
	var bar *pb.ProgressBar
	if !gd.quiet {
		bar = pb.New(len(idToFile))
		bar.ShowBar = true
		bar.ShowCounters = false
		bar.Output = os.Stderr
		bar.Prefix("Checking metadata cache: ")
		bar.Start()
	}

	err = gd.runQuery("trashed=false", func(f *drive.File) {
		if file, ok := idToFile[f.Id]; ok {
			df := newFile(f.Title, f)
			if !filesEqual(df, file) {
				report(fmt.Sprintf("%s: metadata mismatch.\nLocal: %+v\nDrive: %+v",
					file.Path, file, df))
			}
			if bar != nil {
				bar.Increment()
			}
			delete(idToFile, f.Id)
		} else {
			// It'd be preferable to have "sharedWithMe=false" included in
			// the query string above, but the combination of that with
			// "trashed=false" seems to lead to no results being returned.
			if f.Shared == false {
				report(fmt.Sprintf("%s: found on Drive, not in local cache [%+v]",
					f.Title, f))
			}
		}
	})

	for _, f := range idToFile {
		report(fmt.Sprintf("%s: found in local cache, not on Drive [%+v]",
			f.Path, f))
	}

	if bar != nil {
		bar.Finish()
	}
	return nil
}

func filesEqual(fa, fb *File) bool {
	if fa.Path != fb.Path || fa.FileSize != fb.FileSize ||
		fa.Md5 != fb.Md5 || fa.MimeType != fb.MimeType ||
		fa.ModTime != fb.ModTime {
		return false
	}

	if len(fa.ParentIds) != len(fb.ParentIds) {
		return false
	}
	for _, id := range fa.ParentIds {
		found := false
		for _, id2 := range fb.ParentIds {
			if id == id2 {
				found = true
				break
			}
		}
		if !found {
			return false
		}
	}

	if len(fa.Properties) != len(fb.Properties) {
		return false
	}
	for _, p := range fa.Properties {
		found := false
		for _, p2 := range fb.Properties {
			if p == p2 {
				found = true
				break
			}
		}
		if !found {
			return false
		}
	}

	return true
}

// GetFile returns the File corresponding to a file or folder specified by
// the given path starting from the root of the Google Drive filesystem.
// (Note that File is used to represent both files and folders in Google
// Drive.)
func (gd *GDrive) GetFile(path string) (*File, error) {
	files := gd.GetFiles(path)
	if len(files) == 0 {
		return nil, ErrNotExist
	} else if len(files) > 1 {
		return nil, ErrMultipleFiles
	}
	return files[0], nil
}

// Given a path from the user, convert it into the form that's used for
// paths in the dirToFiles and pathToFile maps in GDrive.  Specifically:
// run it through filepath.Clean() to eliminate any clearly redundant junk,
// convert "/" to ".", and remove any leading "/", if the user provided an
// absolute path.
//
// TODO: could we equivalently just do:
//   return filepath.Clean(filepath.Join(".", path))
// ?
func canonicalPath(path string) string {
	path = filepath.Clean(path)
	if path[0] == os.PathSeparator {
		if len(path) > 1 {
			path = path[1:]
		} else {
			path = "."
		}
	}
	return path
}

// GetFiles returns File structures for *all* of the files in Google Drive
// that correspond to the given path. Because Google Drive allows multiple
// files to have the same title (and allows multiple folders of the same
// name), more than one file may be returned
//
// Note: an error is not returned if the file doesn't exist; the caller
// should detect that case by checking for a zero-length returned array.
func (gd *GDrive) GetFiles(path string) []*File {
	gd.metadataMutex.Lock()
	defer gd.metadataMutex.Unlock()
	return gd.pathToFile[canonicalPath(path)]
}

// GetFilesInFolder returns a *File array representing the files in the
// given folder with the given name. The files are sorted by pathname.
func (gd *GDrive) GetFilesInFolder(path string) ([]*File, error) {
	gd.metadataMutex.Lock()
	defer gd.metadataMutex.Unlock()

	if dirFiles, ok := gd.dirToFiles[canonicalPath(path)]; ok {
		sort.Sort(byPath(dirFiles))
		return dirFiles, nil
	}
	return nil, ErrNotExist
}

// PartitionUniquesAndMultiples partitions all of the files by path name
// and then returns an array of File structures for the uniquely-named
// files and a map from path names to arrays of files for cases where more
// than one file has the same pathname.
func PartitionUniquesAndMultiples(files []*File) ([]*File, map[string][]*File) {
	sort.Sort(byPath(files))

	var uniques []*File
	multiples := make(map[string][]*File)
	for i, f := range files {
		// Non-duplicated files are different than their neighbors on both
		// sides (if present).
		if (i == 0 || f.Path != files[i-1].Path) &&
			(i == len(files)-1 || f.Path != files[i+1].Path) {
			uniques = append(uniques, f)
		} else {
			multiples[f.Path] = append(multiples[f.Path], f)
		}
	}

	return uniques, multiples
}

// GetFilesUnderFolder returns an array of File pointers that represents all of the
// files stored in GoogleDrive under the given path.  The 'includeBase'
// parameter indicates whether the file corresponding to the given path's
// folder should be included.
func (gd *GDrive) GetFilesUnderFolder(path string, includeBase bool) ([]*File, error) {
	var files []*File

	// Start by getting the file or files that correspond to the given
	// path.
	pathfiles := gd.GetFiles(path)
	if len(pathfiles) == 0 {
		return files, ErrNotExist
	}

	gd.metadataMutex.Lock()
	defer gd.metadataMutex.Unlock()

	for _, f := range pathfiles {
		if f.IsFolder() {
			if includeBase {
				files = append(files, f)
			}
			gd.getFolderContentsRecursive(f, &files)
		} else {
			files = append(files, f)
		}
	}

	sort.Sort(byPath(files))
	return files, nil
}

func (gd *GDrive) getFolderContentsRecursive(parentFolder *File, files *[]*File) {
	// The mutex for dirToFiles was acquired by GetFilesUnderFolder.
	for _, f := range gd.dirToFiles[parentFolder.Path] {
		*files = append(*files, f)
		if f.IsFolder() {
			gd.getFolderContentsRecursive(f, files)
		}
	}
}

// GetFileContents returns an io.ReadCloser that provides the contents of
// the given File.
func (gd *GDrive) GetFileContents(f *File) (io.ReadCloser, error) {
	// The file download URL expires some hours after it's retrieved, so we
	// can't really cache it.  Re-grab the full *drive.File right before
	// downloading it so that we have a fresh URL.
	driveFile, err := gd.GetFileById(f.Id)
	if err != nil {
		return nil, err
	}

	url := driveFile.DownloadUrl
	if url == "" {
		// Google Docs files can't be downloaded directly via DownloadUrl,
		// but can be exported to another format that can be downloaded.

		// Docs, Sheets, and Slides can be downloaded into .docx, .xls,
		// and .pptx formats, respectively. This may be a bit confusing since
		// they won't have that suffix locally.
		for mt, u := range driveFile.ExportLinks {
			if strings.HasPrefix(mt, "application/vnd.openxmlformats-officedocument") {
				url = u
				break
			}
		}
		// Google Drawings can be downloaded in SVG form.
		if url == "" {
			if u, ok := driveFile.ExportLinks["image/svg+xml"]; ok {
				url = u
			}
		}
		// Otherwise we seem to be out of luck.
		if url == "" {
			return nil, fmt.Errorf("%s: unable to download Google Docs file", f.Path)
		}
	}

	for try := 0; ; try++ {
		request, err := http.NewRequest("GET", url, nil)
		if err != nil {
			return nil, err
		}

		resp, err := gd.client.Do(request)

		switch gd.handleHTTPResponse(resp, err, try) {
		case Success:
			// Rate-limit the download, if required.
			return MakeLimitedDownloadReader(resp.Body), nil
		case Fail:
			return nil, err
		case Retry:
		}
	}
}

// UpdateProperty updates the property with name 'key' to the value 'value'
// in the given file on Google Drive.
func (gd *GDrive) UpdateProperty(f *File, key string, value string) error {
	for _, prop := range f.Properties {
		if prop.Key == key {
			if prop.Value == value {
				// Save the network round-trip and return, since the
				// property already has the desired value.
				return nil
			}
			break
		}
	}

	// Update the file on Drive.
	prop := &drive.Property{Key: key, Value: value}

	for try := 0; ; try++ {
		_, err := gd.svc.Properties.Update(f.Id, key, prop).Do()
		if err == nil {
			// Success.
			return nil
		} else if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
			return err
		}
	}
}

// UpdateModificationTime updates the modification time of the given Google
// Drive file to the given time.
func (gd *GDrive) UpdateModificationTime(f *File, newTime time.Time) error {
	gd.debug("updating modification time of %s to %v", f.Path, newTime)

	if f.ModTime.Equal(newTime) {
		return nil
	}

	for try := 0; ; try++ {
		fp := &drive.File{ModifiedDate: newTime.UTC().Format(timeFormat)}
		_, err := gd.svc.Files.Patch(f.Id, fp).SetModifiedDate(true).Do()
		if err == nil {
			gd.debug("success: updated modification time on %s", f.Path)
			return nil
		} else if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
			return err
		}
	}
}

// AddProperty adds the property with given key and value to the provided
// file and updates the file in Google Drive.
func (gd *GDrive) AddProperty(key, value string, f *File) error {
	prop := &drive.Property{Key: key, Value: value}

	for try := 0; ; try++ {
		_, err := gd.svc.Properties.Insert(f.Id, prop).Do()
		if err == nil {
			return nil
		} else if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
			return fmt.Errorf("unable to create %s property: %v",
				prop.Key, err)
		}
	}
}

// http://stackoverflow.com/questions/18578768/403-rate-limit-on-insert-sometimes-succeeds
// Sometimes when we get a 403 error from Files.Insert().Do(), a file is
// actually created. Delete the file to be sure we don't have duplicate
// files with the same name.
func (gd *GDrive) deleteIncompleteDriveFiles(title string, parentId string) {
	query := fmt.Sprintf("title='%s' and '%s' in parents and trashed=false",
		title, parentId)
	err := gd.runQuery(query, func(f *drive.File) {
		for try := 0; ; try++ {
			err := gd.svc.Files.Delete(f.Id).Do()
			if err == nil {
				break
			} else if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
				log.Fatalf("error deleting 403 Google Drive file "+
					"for %s (ID %s): %v", title, f.Id, err)
			}
		}
	})

	if err != nil {
		gd.debug("unable to run query in deleteIncompleteDriveFiles(); "+
			"ignoring error: %v", err)
		return
	}
}

func convertProplist(p []Property) []*drive.Property {
	var pl []*drive.Property
	for _, prop := range p {
		pl = append(pl, &drive.Property{Key: prop.Key, Value: prop.Value})
	}
	return pl
}

// CreateFile creates an actual file in Google Drive with the given
// filename.  The new file is in the folder given by represented by the
// 'parent' parameter, is initialized to have the given modification time
// and the provided Google Drive file properties.  The returned File value
// represents the file in Drive.
func (gd *GDrive) CreateFile(name string, parent *File,
	modTime time.Time, proplist []Property) (*File, error) {
	return gd.createFileOrFolder(name, parent, modTime, proplist,
		"application/octet-stream")
}

// CreateFolder creates a new folder in Google Drive with given name.
func (gd *GDrive) CreateFolder(name string, parent *File,
	modTime time.Time, proplist []Property) (*File, error) {
	return gd.createFileOrFolder(name, parent, modTime, proplist,
		"application/vnd.google-apps.folder")
}

func (gd *GDrive) createFileOrFolder(name string, parent *File,
	modTime time.Time, proplist []Property, mimeType string) (*File, error) {
	path := canonicalPath(filepath.Join(parent.Path, name))

	gd.metadataMutex.Lock()
	defer gd.metadataMutex.Unlock()

	if _, ok := gd.pathToFile[path]; ok {
		panic(fmt.Sprintf("%s: already exists!", path))
	}

	pr := &drive.ParentReference{Id: parent.Id}
	f := &drive.File{
		Title:        name,
		MimeType:     mimeType,
		ModifiedDate: modTime.UTC().Format(timeFormat),
		Parents:      []*drive.ParentReference{pr},
		Properties:   convertProplist(proplist),
	}
	f, err := gd.insertFile(f)
	if err != nil {
		return nil, err
	}

	// Update the metadata cache to account for the new file.
	file := newFile(canonicalPath(filepath.Join(parent.Path, f.Title)), f)

	// Update the pathToFile map.
	switch len(gd.pathToFile[file.Path]) {
	case 0:
		gd.pathToFile[file.Path] = append(gd.pathToFile[file.Path], file)
	case 1:
		gd.pathToFile[file.Path][0] = file
	default:
		panic("gdrive: creating file/folder when multiple already exist")
	}

	// Also update the parent folder's list of files, either replacing a
	// current instance of a file with this name or adding a new file for
	// this one.
	for i, dirFile := range gd.dirToFiles[parent.Path] {
		if dirFile.Path == file.Path {
			gd.dirToFiles[parent.Path][i] = file
			return file, nil
		}
	}

	gd.dirToFiles[parent.Path] = append(gd.dirToFiles[parent.Path], file)
	return file, nil
}

func (gd *GDrive) insertFile(f *drive.File) (*drive.File, error) {
	for try := 0; ; try++ {
		r, err := gd.svc.Files.Insert(f).Do()
		if err == nil {
			gd.debug("Created new Google Drive file for %s: ID=%s",
				f.Title, r.Id)
			return r, nil
		}
		gd.debug("Error %v trying to create drive file for %s. "+
			"Deleting detrius...", err, f.Title)
		gd.deleteIncompleteDriveFiles(f.Title, f.Parents[0].Id)
		err = gd.tryToHandleDriveAPIError(err, try)
		if err != nil {
			return nil, fmt.Errorf("unable to create drive.File: %v", err)
		}
	}
}

// DeleteFile deletes the given file from Google Drive; note that deletion
// is permanent and un-reversable!  (Consider TrashFile instead.)
func (gd *GDrive) DeleteFile(f *File) error {
	for try := 0; ; try++ {
		err := gd.svc.Files.Delete(f.Id).Do()
		if err == nil {
			return nil
		} else if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
			return fmt.Errorf("%s: unable to delete: %v", f.Path, err)
		}
	}
}

// TrashFile moves the given Google Drive file to the trash; it is not
// immediately deleted permanently.
func (gd *GDrive) TrashFile(f *File) error {
	for try := 0; ; try++ {
		_, err := gd.svc.Files.Trash(f.Id).Do()
		if err == nil {
			return nil
		} else if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
			return fmt.Errorf("%s: unable to trash: %v", f.Path, err)
		}
	}
}

type SpaceUser struct {
	Name string
	Used int64
}

type Usage struct {
	Capacity int64
	Used     int64
	Users    []SpaceUser
}

// GetDriveUsage returns a structure with information about the current
// storage usage on Google Drive.
func (gd *GDrive) GetDriveUsage() (Usage, error) {
	var about *drive.About
	var err error

	for try := 0; ; try++ {
		about, err = gd.svc.About.Get().Do()
		if err == nil {
			break
		}
		if err = gd.tryToHandleDriveAPIError(err, try); err != nil {
			return Usage{}, err
		}
	}

	var users []SpaceUser
	users = append(users, SpaceUser{Name: "Trash", Used: about.QuotaBytesUsedInTrash})
	for _, s := range about.QuotaBytesByService {
		users = append(users, SpaceUser{Name: s.ServiceName, Used: s.BytesUsed})
	}

	return Usage{
		Capacity: about.QuotaBytesTotal,
		Used:     about.QuotaBytesUsedAggregate,
		Users:    users}, nil
}