Merge pull request #226 from google/dvyukov-vendor

vendor: vendor dependencies

15 files changed, 1282 insertions, 0 deletions

diff --git a/vendor/github.com/googleapis/gax-go/.gitignore b/vendor/github.com/googleapis/gax-go/.gitignore
new file mode 100644
index 000000000..289bf1eb7
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/.gitignore
@@ -0,0 +1 @@
+*.cover
diff --git a/vendor/github.com/googleapis/gax-go/.travis.yml b/vendor/github.com/googleapis/gax-go/.travis.yml
new file mode 100644
index 000000000..6db28b6c6
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/.travis.yml
@@ -0,0 +1,15 @@
+sudo: false
+language: go
+go:
+  - 1.6
+  - 1.7
+before_install:
+  - go get golang.org/x/tools/cmd/cover
+  - go get golang.org/x/tools/cmd/goimports
+script:
+  - gofmt -l .
+  - goimports -l .
+  - go tool vet .
+  - go test -coverprofile=coverage.txt -covermode=atomic
+after_success:
+  - bash <(curl -s https://codecov.io/bash)
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 000000000..2827b7d3f
--- /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 000000000..6d16b6578
--- /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 000000000..3cedd5be9
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/README.md
@@ -0,0 +1,24 @@
+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.
+
+Application code will rarely need to use this library directly,
+but the code generated automatically from API definition files can use it
+to simplify code generation and to provide more convenient and idiomatic API surface.
+
+**This project is currently experimental and not supported.**
+
+Go Versions
+===========
+This library requires Go 1.6 or above.
+
+License
+=======
+BSD - please see [LICENSE](https://github.com/googleapis/gax-go/blob/master/LICENSE)
+for more information.
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 000000000..7b621643e
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/call_option.go
@@ -0,0 +1,157 @@
+// 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"
+	"google.golang.org/grpc/status"
+)
+
+// 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) {
+	st, ok := status.FromError(err)
+	if !ok {
+		return 0, false
+	}
+	c := st.Code()
+	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
+	}
+	// Select a duration between zero and the current max. It might seem counterintuitive to
+	// have so much jitter, but https://www.awsarchitectureblog.com/2015/03/backoff.html
+	// argues that that is the best strategy.
+	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 grpcOpt []grpc.CallOption
+
+func (o grpcOpt) Resolve(s *CallSettings) {
+	s.GRPC = o
+}
+
+func WithGRPCOptions(opt ...grpc.CallOption) CallOption {
+	return grpcOpt(append([]grpc.CallOption(nil), opt...))
+}
+
+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
+
+	// CallOptions to be forwarded to GRPC.
+	GRPC []grpc.CallOption
+}
diff --git a/vendor/github.com/googleapis/gax-go/call_option_test.go b/vendor/github.com/googleapis/gax-go/call_option_test.go
new file mode 100644
index 000000000..6f81305ff
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/call_option_test.go
@@ -0,0 +1,88 @@
+// 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 (
+	"testing"
+	"time"
+
+	"google.golang.org/grpc/codes"
+	"google.golang.org/grpc/status"
+)
+
+var _ Retryer = &boRetryer{}
+
+func TestBackofDefault(t *testing.T) {
+	backoff := Backoff{}
+
+	max := []time.Duration{1, 2, 4, 8, 16, 30, 30, 30, 30, 30}
+	for i, m := range max {
+		max[i] = m * time.Second
+	}
+
+	for i, w := range max {
+		if d := backoff.Pause(); d > w {
+			t.Errorf("Backoff duration should be at most %s, got %s", w, d)
+		} else if i < len(max)-1 && backoff.cur != max[i+1] {
+			t.Errorf("current envelope is %s, want %s", backoff.cur, max[i+1])
+		}
+	}
+}
+
+func TestBackoffExponential(t *testing.T) {
+	backoff := Backoff{Initial: 1, Max: 20, Multiplier: 2}
+	want := []time.Duration{1, 2, 4, 8, 16, 20, 20, 20, 20, 20}
+	for _, w := range want {
+		if d := backoff.Pause(); d > w {
+			t.Errorf("Backoff duration should be at most %s, got %s", w, d)
+		}
+	}
+}
+
+func TestOnCodes(t *testing.T) {
+	// Lint errors grpc.Errorf in 1.6. It mistakenly expects the first arg to Errorf to be a string.
+	errf := status.Errorf
+	apiErr := errf(codes.Unavailable, "")
+	tests := []struct {
+		c     []codes.Code
+		retry bool
+	}{
+		{nil, false},
+		{[]codes.Code{codes.DeadlineExceeded}, false},
+		{[]codes.Code{codes.DeadlineExceeded, codes.Unavailable}, true},
+		{[]codes.Code{codes.Unavailable}, true},
+	}
+	for _, tst := range tests {
+		b := OnCodes(tst.c, Backoff{})
+		if _, retry := b.Retry(apiErr); retry != tst.retry {
+			t.Errorf("retriable codes: %v, error: %s, retry: %t, want %t", tst.c, apiErr, retry, tst.retry)
+		}
+	}
+}
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 000000000..5ebedff0d
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/gax.go
@@ -0,0 +1,40 @@
+// 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 contains a set of modules which aid the development of APIs
+// for clients and servers based on gRPC and Google API conventions.
+//
+// Application code will rarely need to use this library directly.
+// However, code generated automatically from API definition files can use it
+// to simplify code generation and to provide more convenient and idiomatic API surfaces.
+//
+// This project is currently experimental and not supported.
+package gax
+
+const Version = "0.1.0"
diff --git a/vendor/github.com/googleapis/gax-go/header.go b/vendor/github.com/googleapis/gax-go/header.go
new file mode 100644
index 000000000..d81455ecc
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/header.go
@@ -0,0 +1,24 @@
+package gax
+
+import "bytes"
+
+// XGoogHeader is for use by the Google Cloud Libraries only.
+//
+// XGoogHeader formats key-value pairs.
+// The resulting string is suitable for x-goog-api-client header.
+func XGoogHeader(keyval ...string) string {
+	if len(keyval) == 0 {
+		return ""
+	}
+	if len(keyval)%2 != 0 {
+		panic("gax.Header: odd argument count")
+	}
+	var buf bytes.Buffer
+	for i := 0; i < len(keyval); i += 2 {
+		buf.WriteByte(' ')
+		buf.WriteString(keyval[i])
+		buf.WriteByte('/')
+		buf.WriteString(keyval[i+1])
+	}
+	return buf.String()[1:]
+}
diff --git a/vendor/github.com/googleapis/gax-go/header_test.go b/vendor/github.com/googleapis/gax-go/header_test.go
new file mode 100644
index 000000000..05d8de6fc
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/header_test.go
@@ -0,0 +1,19 @@
+package gax
+
+import "testing"
+
+func TestXGoogHeader(t *testing.T) {
+	for _, tst := range []struct {
+		kv   []string
+		want string
+	}{
+		{nil, ""},
+		{[]string{"abc", "def"}, "abc/def"},
+		{[]string{"abc", "def", "xyz", "123", "foo", ""}, "abc/def xyz/123 foo/"},
+	} {
+		got := XGoogHeader(tst.kv...)
+		if got != tst.want {
+			t.Errorf("Header(%q) = %q, want %q", tst.kv, got, tst.want)
+		}
+	}
+}
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 000000000..86049d826
--- /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, CallSettings) 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, settings)
+		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/invoke_test.go b/vendor/github.com/googleapis/gax-go/invoke_test.go
new file mode 100644
index 000000000..3d12e6093
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/invoke_test.go
@@ -0,0 +1,156 @@
+// 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"
+	"testing"
+	"time"
+
+	"golang.org/x/net/context"
+)
+
+var canceledContext context.Context
+
+func init() {
+	ctx, cancel := context.WithCancel(context.Background())
+	cancel()
+	canceledContext = ctx
+}
+
+// recordSleeper is a test implementation of sleeper.
+type recordSleeper int
+
+func (s *recordSleeper) sleep(ctx context.Context, _ time.Duration) error {
+	*s++
+	return ctx.Err()
+}
+
+type boolRetryer bool
+
+func (r boolRetryer) Retry(err error) (time.Duration, bool) { return 0, bool(r) }
+
+func TestInvokeSuccess(t *testing.T) {
+	apiCall := func(context.Context, CallSettings) error { return nil }
+	var sp recordSleeper
+	err := invoke(context.Background(), apiCall, CallSettings{}, sp.sleep)
+
+	if err != nil {
+		t.Errorf("found error %s, want nil", err)
+	}
+	if sp != 0 {
+		t.Errorf("slept %d times, should not have slept since the call succeeded", int(sp))
+	}
+}
+
+func TestInvokeNoRetry(t *testing.T) {
+	apiErr := errors.New("foo error")
+	apiCall := func(context.Context, CallSettings) error { return apiErr }
+	var sp recordSleeper
+	err := invoke(context.Background(), apiCall, CallSettings{}, sp.sleep)
+
+	if err != apiErr {
+		t.Errorf("found error %s, want %s", err, apiErr)
+	}
+	if sp != 0 {
+		t.Errorf("slept %d times, should not have slept since retry is not specified", int(sp))
+	}
+}
+
+func TestInvokeNilRetry(t *testing.T) {
+	apiErr := errors.New("foo error")
+	apiCall := func(context.Context, CallSettings) error { return apiErr }
+	var settings CallSettings
+	WithRetry(func() Retryer { return nil }).Resolve(&settings)
+	var sp recordSleeper
+	err := invoke(context.Background(), apiCall, settings, sp.sleep)
+
+	if err != apiErr {
+		t.Errorf("found error %s, want %s", err, apiErr)
+	}
+	if sp != 0 {
+		t.Errorf("slept %d times, should not have slept since retry is not specified", int(sp))
+	}
+}
+
+func TestInvokeNeverRetry(t *testing.T) {
+	apiErr := errors.New("foo error")
+	apiCall := func(context.Context, CallSettings) error { return apiErr }
+	var settings CallSettings
+	WithRetry(func() Retryer { return boolRetryer(false) }).Resolve(&settings)
+	var sp recordSleeper
+	err := invoke(context.Background(), apiCall, settings, sp.sleep)
+
+	if err != apiErr {
+		t.Errorf("found error %s, want %s", err, apiErr)
+	}
+	if sp != 0 {
+		t.Errorf("slept %d times, should not have slept since retry is not specified", int(sp))
+	}
+}
+
+func TestInvokeRetry(t *testing.T) {
+	const target = 3
+
+	retryNum := 0
+	apiErr := errors.New("foo error")
+	apiCall := func(context.Context, CallSettings) error {
+		retryNum++
+		if retryNum < target {
+			return apiErr
+		}
+		return nil
+	}
+	var settings CallSettings
+	WithRetry(func() Retryer { return boolRetryer(true) }).Resolve(&settings)
+	var sp recordSleeper
+	err := invoke(context.Background(), apiCall, settings, sp.sleep)
+
+	if err != nil {
+		t.Errorf("found error %s, want nil, call should have succeeded after %d tries", err, target)
+	}
+	if sp != target-1 {
+		t.Errorf("retried %d times, want %d", int(sp), int(target-1))
+	}
+}
+
+func TestInvokeRetryTimeout(t *testing.T) {
+	apiErr := errors.New("foo error")
+	apiCall := func(context.Context, CallSettings) error { return apiErr }
+	var settings CallSettings
+	WithRetry(func() Retryer { return boolRetryer(true) }).Resolve(&settings)
+	var sp recordSleeper
+
+	err := invoke(canceledContext, apiCall, settings, sp.sleep)
+
+	if err != context.Canceled {
+		t.Errorf("found error %s, want %s", err, context.Canceled)
+	}
+}
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 000000000..41bda94cb
--- /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 000000000..79c8e759c
--- /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--
+}
diff --git a/vendor/github.com/googleapis/gax-go/path_template_test.go b/vendor/github.com/googleapis/gax-go/path_template_test.go
new file mode 100644
index 000000000..49dea47d5
--- /dev/null
+++ b/vendor/github.com/googleapis/gax-go/path_template_test.go
@@ -0,0 +1,211 @@
+// 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 "testing"
+
+func TestPathTemplateMatchRender(t *testing.T) {
+	testCases := []struct {
+		message  string
+		template string
+		path     string
+		values   map[string]string
+	}{
+		{
+			"base",
+			"buckets/*/*/objects/*",
+			"buckets/f/o/objects/bar",
+			map[string]string{"$0": "f", "$1": "o", "$2": "bar"},
+		},
+		{
+			"path wildcards",
+			"bar/**/foo/*",
+			"bar/foo/foo/foo/bar",
+			map[string]string{"$0": "foo/foo", "$1": "bar"},
+		},
+		{
+			"named binding",
+			"buckets/{foo}/objects/*",
+			"buckets/foo/objects/bar",
+			map[string]string{"$0": "bar", "foo": "foo"},
+		},
+		{
+			"named binding with colon",
+			"buckets/{foo}/objects/*",
+			"buckets/foo:boo/objects/bar",
+			map[string]string{"$0": "bar", "foo": "foo:boo"},
+		},
+		{
+			"named binding with complex patterns",
+			"buckets/{foo=x/*/y/**}/objects/*",
+			"buckets/x/foo/y/bar/baz/objects/quox",
+			map[string]string{"$0": "quox", "foo": "x/foo/y/bar/baz"},
+		},
+		{
+			"starts with slash",
+			"/foo/*",
+			"/foo/bar",
+			map[string]string{"$0": "bar"},
+		},
+	}
+	for _, testCase := range testCases {
+		pt, err := NewPathTemplate(testCase.template)
+		if err != nil {
+			t.Errorf("[%s] Failed to parse template %s: %v", testCase.message, testCase.template, err)
+			continue
+		}
+		values, err := pt.Match(testCase.path)
+		if err != nil {
+			t.Errorf("[%s] PathTemplate '%s' failed to match with '%s', %v", testCase.message, testCase.template, testCase.path, err)
+			continue
+		}
+		for key, expected := range testCase.values {
+			actual, ok := values[key]
+			if !ok {
+				t.Errorf("[%s] The matched data misses the value for %s", testCase.message, key)
+				continue
+			}
+			delete(values, key)
+			if actual != expected {
+				t.Errorf("[%s] Failed to match: value for '%s' is expected '%s' but is actually '%s'", testCase.message, key, expected, actual)
+			}
+		}
+		if len(values) != 0 {
+			t.Errorf("[%s] The matched data has unexpected keys: %v", testCase.message, values)
+		}
+		built, err := pt.Render(testCase.values)
+		if err != nil || built != testCase.path {
+			t.Errorf("[%s] Built path '%s' is different from the expected '%s', %v", testCase.message, built, testCase.path, err)
+		}
+	}
+}
+
+func TestPathTemplateMatchFailure(t *testing.T) {
+	testCases := []struct {
+		message  string
+		template string
+		path     string
+	}{
+		{
+			"too many paths",
+			"buckets/*/*/objects/*",
+			"buckets/f/o/o/objects/bar",
+		},
+		{
+			"missing last path",
+			"buckets/*/*/objects/*",
+			"buckets/f/o/objects",
+		},
+		{
+			"too many paths at end",
+			"buckets/*/*/objects/*",
+			"buckets/f/o/objects/too/long",
+		},
+	}
+	for _, testCase := range testCases {
+		pt, err := NewPathTemplate(testCase.template)
+		if err != nil {
+			t.Errorf("[%s] Failed to parse path %s: %v", testCase.message, testCase.template, err)
+			continue
+		}
+		if values, err := pt.Match(testCase.path); err == nil {
+			t.Errorf("[%s] PathTemplate %s doesn't expect to match %s, but succeeded somehow. Match result: %v", testCase.message, testCase.template, testCase.path, values)
+
+		}
+	}
+}
+
+func TestPathTemplateRenderTooManyValues(t *testing.T) {
+	// Test cases where Render() succeeds but Match() doesn't return the same map.
+	testCases := []struct {
+		message  string
+		template string
+		values   map[string]string
+		expected string
+	}{
+		{
+			"too many",
+			"bar/*/foo/*",
+			map[string]string{"$0": "_1", "$1": "_2", "$2": "_3"},
+			"bar/_1/foo/_2",
+		},
+	}
+	for _, testCase := range testCases {
+		pt, err := NewPathTemplate(testCase.template)
+		if err != nil {
+			t.Errorf("[%s] Failed to parse template %s (error %v)", testCase.message, testCase.template, err)
+			continue
+		}
+		if result, err := pt.Render(testCase.values); err != nil || result != testCase.expected {
+			t.Errorf("[%s] Failed to build the path (expected '%s' but returned '%s'", testCase.message, testCase.expected, result)
+		}
+	}
+}
+
+func TestPathTemplateParseErrors(t *testing.T) {
+	testCases := []struct {
+		message  string
+		template string
+	}{
+		{
+			"multiple path wildcards",
+			"foo/**/bar/**",
+		},
+		{
+			"recursive named bindings",
+			"foo/{foo=foo/{bar}/baz/*}/baz/*",
+		},
+		{
+			"complicated multiple path wildcards patterns",
+			"foo/{foo=foo/**/bar/*}/baz/**",
+		},
+		{
+			"consective slashes",
+			"foo//bar",
+		},
+		{
+			"invalid variable pattern",
+			"foo/{foo=foo/*/}bar",
+		},
+		{
+			"same name multiple times",
+			"foo/{foo}/bar/{foo}",
+		},
+		{
+			"empty string after '='",
+			"foo/{foo=}/bar",
+		},
+	}
+	for _, testCase := range testCases {
+		if pt, err := NewPathTemplate(testCase.template); err == nil {
+			t.Errorf("[%s] Template '%s' should fail to be parsed, but succeeded and returned %+v", testCase.message, testCase.template, pt)
+		}
+	}
+}