Update dependencies

8 files changed, 726 insertions, 0 deletions

diff --git a/vendor/github.com/googleapis/gax-go/CONTRIBUTING.md b/vendor/github.com/googleapis/gax-go/CONTRIBUTING.md
new file mode 100644
index 0000000..2827b7d
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/CONTRIBUTING.md
@@ -0,0 +1,27 @@
+Want to contribute? Great! First, read this page (including the small print at the end).
+
+### Before you contribute
+Before we can use your code, you must sign the
+[Google Individual Contributor License Agreement]
+(https://cla.developers.google.com/about/google-individual)
+(CLA), which you can do online. The CLA is necessary mainly because you own the
+copyright to your changes, even after your contribution becomes part of our
+codebase, so we need your permission to use and distribute your code. We also
+need to be sure of various other things—for instance that you'll tell us if you
+know that your code infringes on other people's patents. You don't have to sign
+the CLA until after you've submitted your code for review and a member has
+approved it, but you must do it before we can put your code into our codebase.
+Before you start working on a larger contribution, you should get in touch with
+us first through the issue tracker with your idea so that we can help out and
+possibly guide you. Coordinating up front makes it much easier to avoid
+frustration later on.
+
+### Code reviews
+All submissions, including submissions by project members, require review. We
+use Github pull requests for this purpose.
+
+### The small print
+Contributions made by corporations are covered by a different agreement than
+the one above, the
+[Software Grant and Corporate Contributor License Agreement]
+(https://cla.developers.google.com/about/google-corporate).
diff --git a/vendor/github.com/googleapis/gax-go/LICENSE b/vendor/github.com/googleapis/gax-go/LICENSE
new file mode 100644
index 0000000..6d16b65
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/LICENSE
@@ -0,0 +1,27 @@
+Copyright 2016, Google Inc.
+All rights reserved.
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+   * Redistributions of source code must retain the above copyright
+notice, this list of conditions and the following disclaimer.
+   * Redistributions in binary form must reproduce the above
+copyright notice, this list of conditions and the following disclaimer
+in the documentation and/or other materials provided with the
+distribution.
+   * Neither the name of Google Inc. nor the names of its
+contributors may be used to endorse or promote products derived from
+this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/vendor/github.com/googleapis/gax-go/README.md b/vendor/github.com/googleapis/gax-go/README.md
new file mode 100644
index 0000000..38ebdcf
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/README.md
@@ -0,0 +1,11 @@
+Google API Extensions for Go
+============================
+
+[![Build Status](https://travis-ci.org/googleapis/gax-go.svg?branch=master)](https://travis-ci.org/googleapis/gax-go)
+[![Code Coverage](https://img.shields.io/codecov/c/github/googleapis/gax-go.svg)](https://codecov.io/github/googleapis/gax-go)
+
+Google API Extensions for Go (gax-go) is a set of modules which aids the
+development of APIs for clients and servers based on `gRPC` and Google API
+conventions.
+
+This project is currently experimental and not supported.
diff --git a/vendor/github.com/googleapis/gax-go/call_option.go b/vendor/github.com/googleapis/gax-go/call_option.go
new file mode 100644
index 0000000..4ba1cdf
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/call_option.go
@@ -0,0 +1,136 @@
+// Copyright 2016, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+package gax
+
+import (
+	"math/rand"
+	"time"
+
+	"google.golang.org/grpc"
+	"google.golang.org/grpc/codes"
+)
+
+// CallOption is an option used by Invoke to control behaviors of RPC calls.
+// CallOption works by modifying relevant fields of CallSettings.
+type CallOption interface {
+	// Resolve applies the option by modifying cs.
+	Resolve(cs *CallSettings)
+}
+
+// Retryer is used by Invoke to determine retry behavior.
+type Retryer interface {
+	// Retry reports whether a request should be retriedand how long to pause before retrying
+	// if the previous attempt returned with err. Invoke never calls Retry with nil error.
+	Retry(err error) (pause time.Duration, shouldRetry bool)
+}
+
+type retryerOption func() Retryer
+
+func (o retryerOption) Resolve(s *CallSettings) {
+	s.Retry = o
+}
+
+// WithRetry sets CallSettings.Retry to fn.
+func WithRetry(fn func() Retryer) CallOption {
+	return retryerOption(fn)
+}
+
+// OnCodes returns a Retryer that retries if and only if
+// the previous attempt returns a GRPC error whose error code is stored in cc.
+// Pause times between retries are specified by bo.
+//
+// bo is only used for its parameters; each Retryer has its own copy.
+func OnCodes(cc []codes.Code, bo Backoff) Retryer {
+	return &boRetryer{
+		backoff: bo,
+		codes:   append([]codes.Code(nil), cc...),
+	}
+}
+
+type boRetryer struct {
+	backoff Backoff
+	codes   []codes.Code
+}
+
+func (r *boRetryer) Retry(err error) (time.Duration, bool) {
+	c := grpc.Code(err)
+	for _, rc := range r.codes {
+		if c == rc {
+			return r.backoff.Pause(), true
+		}
+	}
+	return 0, false
+}
+
+// Backoff implements exponential backoff.
+// The wait time between retries is a random value between 0 and the "retry envelope".
+// The envelope starts at Initial and increases by the factor of Multiplier every retry,
+// but is capped at Max.
+type Backoff struct {
+	// Initial is the initial value of the retry envelope, defaults to 1 second.
+	Initial time.Duration
+
+	// Max is the maximum value of the retry envelope, defaults to 30 seconds.
+	Max time.Duration
+
+	// Multiplier is the factor by which the retry envelope increases.
+	// It should be greater than 1 and defaults to 2.
+	Multiplier float64
+
+	// cur is the current retry envelope
+	cur time.Duration
+}
+
+func (bo *Backoff) Pause() time.Duration {
+	if bo.Initial == 0 {
+		bo.Initial = time.Second
+	}
+	if bo.cur == 0 {
+		bo.cur = bo.Initial
+	}
+	if bo.Max == 0 {
+		bo.Max = 30 * time.Second
+	}
+	if bo.Multiplier < 1 {
+		bo.Multiplier = 2
+	}
+	d := time.Duration(rand.Int63n(int64(bo.cur)))
+	bo.cur = time.Duration(float64(bo.cur) * bo.Multiplier)
+	if bo.cur > bo.Max {
+		bo.cur = bo.Max
+	}
+	return d
+}
+
+type CallSettings struct {
+	// Retry returns a Retryer to be used to control retry logic of a method call.
+	// If Retry is nil or the returned Retryer is nil, the call will not be retried.
+	Retry func() Retryer
+}
diff --git a/vendor/github.com/googleapis/gax-go/gax.go b/vendor/github.com/googleapis/gax-go/gax.go
new file mode 100644
index 0000000..c7e4ce9
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/gax.go
@@ -0,0 +1,32 @@
+// Copyright 2016, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+package gax
+
+const Version = "0.1.0"
diff --git a/vendor/github.com/googleapis/gax-go/invoke.go b/vendor/github.com/googleapis/gax-go/invoke.go
new file mode 100644
index 0000000..d2134e1
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/invoke.go
@@ -0,0 +1,90 @@
+// Copyright 2016, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+package gax
+
+import (
+	"time"
+
+	"golang.org/x/net/context"
+)
+
+// A user defined call stub.
+type APICall func(context.Context) error
+
+// Invoke calls the given APICall,
+// performing retries as specified by opts, if any.
+func Invoke(ctx context.Context, call APICall, opts ...CallOption) error {
+	var settings CallSettings
+	for _, opt := range opts {
+		opt.Resolve(&settings)
+	}
+	return invoke(ctx, call, settings, Sleep)
+}
+
+// Sleep is similar to time.Sleep, but it can be interrupted by ctx.Done() closing.
+// If interrupted, Sleep returns ctx.Err().
+func Sleep(ctx context.Context, d time.Duration) error {
+	t := time.NewTimer(d)
+	select {
+	case <-ctx.Done():
+		t.Stop()
+		return ctx.Err()
+	case <-t.C:
+		return nil
+	}
+}
+
+type sleeper func(ctx context.Context, d time.Duration) error
+
+// invoke implements Invoke, taking an additional sleeper argument for testing.
+func invoke(ctx context.Context, call APICall, settings CallSettings, sp sleeper) error {
+	var retryer Retryer
+	for {
+		err := call(ctx)
+		if err == nil {
+			return nil
+		}
+		if settings.Retry == nil {
+			return err
+		}
+		if retryer == nil {
+			if r := settings.Retry(); r != nil {
+				retryer = r
+			} else {
+				return err
+			}
+		}
+		if d, ok := retryer.Retry(err); !ok {
+			return err
+		} else if err = sp(ctx, d); err != nil {
+			return err
+		}
+	}
+}
diff --git a/vendor/github.com/googleapis/gax-go/path_template.go b/vendor/github.com/googleapis/gax-go/path_template.go
new file mode 100644
index 0000000..41bda94
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/path_template.go
@@ -0,0 +1,176 @@
+// Copyright 2016, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+package gax
+
+import (
+	"errors"
+	"fmt"
+	"strings"
+)
+
+type matcher interface {
+	match([]string) (int, error)
+	String() string
+}
+
+type segment struct {
+	matcher
+	name string
+}
+
+type labelMatcher string
+
+func (ls labelMatcher) match(segments []string) (int, error) {
+	if len(segments) == 0 {
+		return 0, fmt.Errorf("expected %s but no more segments found", ls)
+	}
+	if segments[0] != string(ls) {
+		return 0, fmt.Errorf("expected %s but got %s", ls, segments[0])
+	}
+	return 1, nil
+}
+
+func (ls labelMatcher) String() string {
+	return string(ls)
+}
+
+type wildcardMatcher int
+
+func (wm wildcardMatcher) match(segments []string) (int, error) {
+	if len(segments) == 0 {
+		return 0, errors.New("no more segments found")
+	}
+	return 1, nil
+}
+
+func (wm wildcardMatcher) String() string {
+	return "*"
+}
+
+type pathWildcardMatcher int
+
+func (pwm pathWildcardMatcher) match(segments []string) (int, error) {
+	length := len(segments) - int(pwm)
+	if length <= 0 {
+		return 0, errors.New("not sufficient segments are supplied for path wildcard")
+	}
+	return length, nil
+}
+
+func (pwm pathWildcardMatcher) String() string {
+	return "**"
+}
+
+type ParseError struct {
+	Pos      int
+	Template string
+	Message  string
+}
+
+func (pe ParseError) Error() string {
+	return fmt.Sprintf("at %d of template '%s', %s", pe.Pos, pe.Template, pe.Message)
+}
+
+// PathTemplate manages the template to build and match with paths used
+// by API services. It holds a template and variable names in it, and
+// it can extract matched patterns from a path string or build a path
+// string from a binding.
+//
+// See http.proto in github.com/googleapis/googleapis/ for the details of
+// the template syntax.
+type PathTemplate struct {
+	segments []segment
+}
+
+// NewPathTemplate parses a path template, and returns a PathTemplate
+// instance if successful.
+func NewPathTemplate(template string) (*PathTemplate, error) {
+	return parsePathTemplate(template)
+}
+
+// MustCompilePathTemplate is like NewPathTemplate but panics if the
+// expression cannot be parsed. It simplifies safe initialization of
+// global variables holding compiled regular expressions.
+func MustCompilePathTemplate(template string) *PathTemplate {
+	pt, err := NewPathTemplate(template)
+	if err != nil {
+		panic(err)
+	}
+	return pt
+}
+
+// Match attempts to match the given path with the template, and returns
+// the mapping of the variable name to the matched pattern string.
+func (pt *PathTemplate) Match(path string) (map[string]string, error) {
+	paths := strings.Split(path, "/")
+	values := map[string]string{}
+	for _, segment := range pt.segments {
+		length, err := segment.match(paths)
+		if err != nil {
+			return nil, err
+		}
+		if segment.name != "" {
+			value := strings.Join(paths[:length], "/")
+			if oldValue, ok := values[segment.name]; ok {
+				values[segment.name] = oldValue + "/" + value
+			} else {
+				values[segment.name] = value
+			}
+		}
+		paths = paths[length:]
+	}
+	if len(paths) != 0 {
+		return nil, fmt.Errorf("Trailing path %s remains after the matching", strings.Join(paths, "/"))
+	}
+	return values, nil
+}
+
+// Render creates a path string from its template and the binding from
+// the variable name to the value.
+func (pt *PathTemplate) Render(binding map[string]string) (string, error) {
+	result := make([]string, 0, len(pt.segments))
+	var lastVariableName string
+	for _, segment := range pt.segments {
+		name := segment.name
+		if lastVariableName != "" && name == lastVariableName {
+			continue
+		}
+		lastVariableName = name
+		if name == "" {
+			result = append(result, segment.String())
+		} else if value, ok := binding[name]; ok {
+			result = append(result, value)
+		} else {
+			return "", fmt.Errorf("%s is not found", name)
+		}
+	}
+	built := strings.Join(result, "/")
+	return built, nil
+}
diff --git a/vendor/github.com/googleapis/gax-go/path_template_parser.go b/vendor/github.com/googleapis/gax-go/path_template_parser.go
new file mode 100644
index 0000000..79c8e75
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/path_template_parser.go
@@ -0,0 +1,227 @@
+// Copyright 2016, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+package gax
+
+import (
+	"fmt"
+	"io"
+	"strings"
+)
+
+// This parser follows the syntax of path templates, from
+// https://github.com/googleapis/googleapis/blob/master/google/api/http.proto.
+// The differences are that there is no custom verb, we allow the initial slash
+// to be absent, and that we are not strict as
+// https://tools.ietf.org/html/rfc6570 about the characters in identifiers and
+// literals.
+
+type pathTemplateParser struct {
+	r                *strings.Reader
+	runeCount        int             // the number of the current rune in the original string
+	nextVar          int             // the number to use for the next unnamed variable
+	seenName         map[string]bool // names we've seen already
+	seenPathWildcard bool            // have we seen "**" already?
+}
+
+func parsePathTemplate(template string) (pt *PathTemplate, err error) {
+	p := &pathTemplateParser{
+		r:        strings.NewReader(template),
+		seenName: map[string]bool{},
+	}
+
+	// Handle panics with strings like errors.
+	// See pathTemplateParser.error, below.
+	defer func() {
+		if x := recover(); x != nil {
+			errmsg, ok := x.(errString)
+			if !ok {
+				panic(x)
+			}
+			pt = nil
+			err = ParseError{p.runeCount, template, string(errmsg)}
+		}
+	}()
+
+	segs := p.template()
+	// If there is a path wildcard, set its length. We can't do this
+	// until we know how many segments we've got all together.
+	for i, seg := range segs {
+		if _, ok := seg.matcher.(pathWildcardMatcher); ok {
+			segs[i].matcher = pathWildcardMatcher(len(segs) - i - 1)
+			break
+		}
+	}
+	return &PathTemplate{segments: segs}, nil
+
+}
+
+// Used to indicate errors "thrown" by this parser. We don't use string because
+// many parts of the standard library panic with strings.
+type errString string
+
+// Terminates parsing immediately with an error.
+func (p *pathTemplateParser) error(msg string) {
+	panic(errString(msg))
+}
+
+// Template = [ "/" ] Segments
+func (p *pathTemplateParser) template() []segment {
+	var segs []segment
+	if p.consume('/') {
+		// Initial '/' needs an initial empty matcher.
+		segs = append(segs, segment{matcher: labelMatcher("")})
+	}
+	return append(segs, p.segments("")...)
+}
+
+// Segments = Segment { "/" Segment }
+func (p *pathTemplateParser) segments(name string) []segment {
+	var segs []segment
+	for {
+		subsegs := p.segment(name)
+		segs = append(segs, subsegs...)
+		if !p.consume('/') {
+			break
+		}
+	}
+	return segs
+}
+
+// Segment  = "*" | "**" | LITERAL | Variable
+func (p *pathTemplateParser) segment(name string) []segment {
+	if p.consume('*') {
+		if name == "" {
+			name = fmt.Sprintf("$%d", p.nextVar)
+			p.nextVar++
+		}
+		if p.consume('*') {
+			if p.seenPathWildcard {
+				p.error("multiple '**' disallowed")
+			}
+			p.seenPathWildcard = true
+			// We'll change 0 to the right number at the end.
+			return []segment{{name: name, matcher: pathWildcardMatcher(0)}}
+		}
+		return []segment{{name: name, matcher: wildcardMatcher(0)}}
+	}
+	if p.consume('{') {
+		if name != "" {
+			p.error("recursive named bindings are not allowed")
+		}
+		return p.variable()
+	}
+	return []segment{{name: name, matcher: labelMatcher(p.literal())}}
+}
+
+// Variable = "{" FieldPath [ "=" Segments ] "}"
+// "{" is already consumed.
+func (p *pathTemplateParser) variable() []segment {
+	// Simplification: treat FieldPath as LITERAL, instead of IDENT { '.' IDENT }
+	name := p.literal()
+	if p.seenName[name] {
+		p.error(name + " appears multiple times")
+	}
+	p.seenName[name] = true
+	var segs []segment
+	if p.consume('=') {
+		segs = p.segments(name)
+	} else {
+		// "{var}" is equivalent to "{var=*}"
+		segs = []segment{{name: name, matcher: wildcardMatcher(0)}}
+	}
+	if !p.consume('}') {
+		p.error("expected '}'")
+	}
+	return segs
+}
+
+// A literal is any sequence of characters other than a few special ones.
+// The list of stop characters is not quite the same as in the template RFC.
+func (p *pathTemplateParser) literal() string {
+	lit := p.consumeUntil("/*}{=")
+	if lit == "" {
+		p.error("empty literal")
+	}
+	return lit
+}
+
+// Read runes until EOF or one of the runes in stopRunes is encountered.
+// If the latter, unread the stop rune. Return the accumulated runes as a string.
+func (p *pathTemplateParser) consumeUntil(stopRunes string) string {
+	var runes []rune
+	for {
+		r, ok := p.readRune()
+		if !ok {
+			break
+		}
+		if strings.IndexRune(stopRunes, r) >= 0 {
+			p.unreadRune()
+			break
+		}
+		runes = append(runes, r)
+	}
+	return string(runes)
+}
+
+// If the next rune is r, consume it and return true.
+// Otherwise, leave the input unchanged and return false.
+func (p *pathTemplateParser) consume(r rune) bool {
+	rr, ok := p.readRune()
+	if !ok {
+		return false
+	}
+	if r == rr {
+		return true
+	}
+	p.unreadRune()
+	return false
+}
+
+// Read the next rune from the input. Return it.
+// The second return value is false at EOF.
+func (p *pathTemplateParser) readRune() (rune, bool) {
+	r, _, err := p.r.ReadRune()
+	if err == io.EOF {
+		return r, false
+	}
+	if err != nil {
+		p.error(err.Error())
+	}
+	p.runeCount++
+	return r, true
+}
+
+// Put the last rune that was read back on the input.
+func (p *pathTemplateParser) unreadRune() {
+	if err := p.r.UnreadRune(); err != nil {
+		p.error(err.Error())
+	}
+	p.runeCount--
+}