VOL-1497 : Add more control to kv/memory access
- Added kv locking mechanism (etcd only)
- (watch) control path access whenever possible
- (watch) use a transaction for updates and merge with memory
- cleaned up vendoring
- misc changes to fix exceptions found along the way
Amendments:
- Copyright header got removed in auto-generated file
- Changed default locking to false for KV list operation
- Updated backend api to allow the passing of locking parameter
Change-Id: Ie1a55d3ca8b9d92ae71a85ce42bb22fcf1419e2c
diff --git a/vendor/github.com/hashicorp/consul/api/agent.go b/vendor/github.com/hashicorp/consul/api/agent.go
index 8e5ffde..6a3fb27 100644
--- a/vendor/github.com/hashicorp/consul/api/agent.go
+++ b/vendor/github.com/hashicorp/consul/api/agent.go
@@ -3,6 +3,8 @@
import (
"bufio"
"fmt"
+ "net/http"
+ "net/url"
)
// ServiceKind is the kind of service being registered.
@@ -89,6 +91,13 @@
Connect *AgentServiceConnect `json:",omitempty"`
}
+// AgentServiceChecksInfo returns information about a Service and its checks
+type AgentServiceChecksInfo struct {
+ AggregatedStatus string
+ Service *AgentService
+ Checks HealthChecks
+}
+
// AgentServiceConnect represents the Connect configuration of a service.
type AgentServiceConnect struct {
Native bool `json:",omitempty"`
@@ -407,6 +416,73 @@
return out, nil
}
+// AgentHealthServiceByID returns for a given serviceID: the aggregated health status, the service definition or an error if any
+// - If the service is not found, will return status (critical, nil, nil)
+// - If the service is found, will return (critical|passing|warning), AgentServiceChecksInfo, nil)
+// - In all other cases, will return an error
+func (a *Agent) AgentHealthServiceByID(serviceID string) (string, *AgentServiceChecksInfo, error) {
+ path := fmt.Sprintf("/v1/agent/health/service/id/%v", url.PathEscape(serviceID))
+ r := a.c.newRequest("GET", path)
+ r.params.Add("format", "json")
+ r.header.Set("Accept", "application/json")
+ _, resp, err := a.c.doRequest(r)
+ if err != nil {
+ return "", nil, err
+ }
+ defer resp.Body.Close()
+ // Service not Found
+ if resp.StatusCode == http.StatusNotFound {
+ return HealthCritical, nil, nil
+ }
+ var out *AgentServiceChecksInfo
+ if err := decodeBody(resp, &out); err != nil {
+ return HealthCritical, out, err
+ }
+ switch resp.StatusCode {
+ case http.StatusOK:
+ return HealthPassing, out, nil
+ case http.StatusTooManyRequests:
+ return HealthWarning, out, nil
+ case http.StatusServiceUnavailable:
+ return HealthCritical, out, nil
+ }
+ return HealthCritical, out, fmt.Errorf("Unexpected Error Code %v for %s", resp.StatusCode, path)
+}
+
+// AgentHealthServiceByName returns for a given service name: the aggregated health status for all services
+// having the specified name.
+// - If no service is not found, will return status (critical, [], nil)
+// - If the service is found, will return (critical|passing|warning), []api.AgentServiceChecksInfo, nil)
+// - In all other cases, will return an error
+func (a *Agent) AgentHealthServiceByName(service string) (string, []AgentServiceChecksInfo, error) {
+ path := fmt.Sprintf("/v1/agent/health/service/name/%v", url.PathEscape(service))
+ r := a.c.newRequest("GET", path)
+ r.params.Add("format", "json")
+ r.header.Set("Accept", "application/json")
+ _, resp, err := a.c.doRequest(r)
+ if err != nil {
+ return "", nil, err
+ }
+ defer resp.Body.Close()
+ // Service not Found
+ if resp.StatusCode == http.StatusNotFound {
+ return HealthCritical, nil, nil
+ }
+ var out []AgentServiceChecksInfo
+ if err := decodeBody(resp, &out); err != nil {
+ return HealthCritical, out, err
+ }
+ switch resp.StatusCode {
+ case http.StatusOK:
+ return HealthPassing, out, nil
+ case http.StatusTooManyRequests:
+ return HealthWarning, out, nil
+ case http.StatusServiceUnavailable:
+ return HealthCritical, out, nil
+ }
+ return HealthCritical, out, fmt.Errorf("Unexpected Error Code %v for %s", resp.StatusCode, path)
+}
+
// Service returns a locally registered service instance and allows for
// hash-based blocking.
//
diff --git a/vendor/github.com/hashicorp/consul/api/api.go b/vendor/github.com/hashicorp/consul/api/api.go
index cf8bad2..b913fa3 100644
--- a/vendor/github.com/hashicorp/consul/api/api.go
+++ b/vendor/github.com/hashicorp/consul/api/api.go
@@ -773,7 +773,7 @@
func (c *Client) query(endpoint string, out interface{}, q *QueryOptions) (*QueryMeta, error) {
r := c.newRequest("GET", endpoint)
r.setQueryOptions(q)
- rtt, resp, err := requireOK(c.doRequest(r))
+ rtt, resp, err := c.doRequest(r)
if err != nil {
return nil, err
}
diff --git a/vendor/github.com/hashicorp/consul/api/connect_ca.go b/vendor/github.com/hashicorp/consul/api/connect_ca.go
index a863d21..600a3e0 100644
--- a/vendor/github.com/hashicorp/consul/api/connect_ca.go
+++ b/vendor/github.com/hashicorp/consul/api/connect_ca.go
@@ -23,7 +23,10 @@
// CommonCAProviderConfig is the common options available to all CA providers.
type CommonCAProviderConfig struct {
- LeafCertTTL time.Duration
+ LeafCertTTL time.Duration
+ SkipValidate bool
+ CSRMaxPerSecond float32
+ CSRMaxConcurrent int
}
// ConsulCAProviderConfig is the config for the built-in Consul CA provider.
@@ -41,7 +44,6 @@
var config ConsulCAProviderConfig
decodeConf := &mapstructure.DecoderConfig{
DecodeHook: mapstructure.StringToTimeDurationHookFunc(),
- ErrorUnused: true,
Result: &config,
WeaklyTypedInput: true,
}
diff --git a/vendor/github.com/hashicorp/consul/api/health.go b/vendor/github.com/hashicorp/consul/api/health.go
index eae6a01..9faf6b6 100644
--- a/vendor/github.com/hashicorp/consul/api/health.go
+++ b/vendor/github.com/hashicorp/consul/api/health.go
@@ -1,8 +1,10 @@
package api
import (
+ "encoding/json"
"fmt"
"strings"
+ "time"
)
const (
@@ -36,21 +38,99 @@
ServiceTags []string
Definition HealthCheckDefinition
+
+ CreateIndex uint64
+ ModifyIndex uint64
}
// HealthCheckDefinition is used to store the details about
// a health check's execution.
type HealthCheckDefinition struct {
- HTTP string
- Header map[string][]string
- Method string
- TLSSkipVerify bool
- TCP string
+ HTTP string
+ Header map[string][]string
+ Method string
+ TLSSkipVerify bool
+ TCP string
+ IntervalDuration time.Duration `json:"-"`
+ TimeoutDuration time.Duration `json:"-"`
+ DeregisterCriticalServiceAfterDuration time.Duration `json:"-"`
+
+ // DEPRECATED in Consul 1.4.1. Use the above time.Duration fields instead.
Interval ReadableDuration
Timeout ReadableDuration
DeregisterCriticalServiceAfter ReadableDuration
}
+func (d *HealthCheckDefinition) MarshalJSON() ([]byte, error) {
+ type Alias HealthCheckDefinition
+ out := &struct {
+ Interval string
+ Timeout string
+ DeregisterCriticalServiceAfter string
+ *Alias
+ }{
+ Interval: d.Interval.String(),
+ Timeout: d.Timeout.String(),
+ DeregisterCriticalServiceAfter: d.DeregisterCriticalServiceAfter.String(),
+ Alias: (*Alias)(d),
+ }
+
+ if d.IntervalDuration != 0 {
+ out.Interval = d.IntervalDuration.String()
+ } else if d.Interval != 0 {
+ out.Interval = d.Interval.String()
+ }
+ if d.TimeoutDuration != 0 {
+ out.Timeout = d.TimeoutDuration.String()
+ } else if d.Timeout != 0 {
+ out.Timeout = d.Timeout.String()
+ }
+ if d.DeregisterCriticalServiceAfterDuration != 0 {
+ out.DeregisterCriticalServiceAfter = d.DeregisterCriticalServiceAfterDuration.String()
+ } else if d.DeregisterCriticalServiceAfter != 0 {
+ out.DeregisterCriticalServiceAfter = d.DeregisterCriticalServiceAfter.String()
+ }
+
+ return json.Marshal(out)
+}
+
+func (d *HealthCheckDefinition) UnmarshalJSON(data []byte) error {
+ type Alias HealthCheckDefinition
+ aux := &struct {
+ Interval string
+ Timeout string
+ DeregisterCriticalServiceAfter string
+ *Alias
+ }{
+ Alias: (*Alias)(d),
+ }
+ if err := json.Unmarshal(data, &aux); err != nil {
+ return err
+ }
+
+ // Parse the values into both the time.Duration and old ReadableDuration fields.
+ var err error
+ if aux.Interval != "" {
+ if d.IntervalDuration, err = time.ParseDuration(aux.Interval); err != nil {
+ return err
+ }
+ d.Interval = ReadableDuration(d.IntervalDuration)
+ }
+ if aux.Timeout != "" {
+ if d.TimeoutDuration, err = time.ParseDuration(aux.Timeout); err != nil {
+ return err
+ }
+ d.Timeout = ReadableDuration(d.TimeoutDuration)
+ }
+ if aux.DeregisterCriticalServiceAfter != "" {
+ if d.DeregisterCriticalServiceAfterDuration, err = time.ParseDuration(aux.DeregisterCriticalServiceAfter); err != nil {
+ return err
+ }
+ d.DeregisterCriticalServiceAfter = ReadableDuration(d.DeregisterCriticalServiceAfterDuration)
+ }
+ return nil
+}
+
// HealthChecks is a collection of HealthCheck structs.
type HealthChecks []*HealthCheck
diff --git a/vendor/github.com/hashicorp/consul/api/kv.go b/vendor/github.com/hashicorp/consul/api/kv.go
index 97f5156..bd45a06 100644
--- a/vendor/github.com/hashicorp/consul/api/kv.go
+++ b/vendor/github.com/hashicorp/consul/api/kv.go
@@ -45,44 +45,6 @@
// KVPairs is a list of KVPair objects
type KVPairs []*KVPair
-// KVOp constants give possible operations available in a KVTxn.
-type KVOp string
-
-const (
- KVSet KVOp = "set"
- KVDelete KVOp = "delete"
- KVDeleteCAS KVOp = "delete-cas"
- KVDeleteTree KVOp = "delete-tree"
- KVCAS KVOp = "cas"
- KVLock KVOp = "lock"
- KVUnlock KVOp = "unlock"
- KVGet KVOp = "get"
- KVGetTree KVOp = "get-tree"
- KVCheckSession KVOp = "check-session"
- KVCheckIndex KVOp = "check-index"
- KVCheckNotExists KVOp = "check-not-exists"
-)
-
-// KVTxnOp defines a single operation inside a transaction.
-type KVTxnOp struct {
- Verb KVOp
- Key string
- Value []byte
- Flags uint64
- Index uint64
- Session string
-}
-
-// KVTxnOps defines a set of operations to be performed inside a single
-// transaction.
-type KVTxnOps []*KVTxnOp
-
-// KVTxnResponse has the outcome of a transaction.
-type KVTxnResponse struct {
- Results []*KVPair
- Errors TxnErrors
-}
-
// KV is used to manipulate the K/V API
type KV struct {
c *Client
@@ -300,121 +262,25 @@
return res, qm, nil
}
-// TxnOp is the internal format we send to Consul. It's not specific to KV,
-// though currently only KV operations are supported.
-type TxnOp struct {
- KV *KVTxnOp
-}
-
-// TxnOps is a list of transaction operations.
-type TxnOps []*TxnOp
-
-// TxnResult is the internal format we receive from Consul.
-type TxnResult struct {
- KV *KVPair
-}
-
-// TxnResults is a list of TxnResult objects.
-type TxnResults []*TxnResult
-
-// TxnError is used to return information about an operation in a transaction.
-type TxnError struct {
- OpIndex int
- What string
-}
-
-// TxnErrors is a list of TxnError objects.
-type TxnErrors []*TxnError
-
-// TxnResponse is the internal format we receive from Consul.
-type TxnResponse struct {
- Results TxnResults
- Errors TxnErrors
-}
-
-// Txn is used to apply multiple KV operations in a single, atomic transaction.
-//
-// Note that Go will perform the required base64 encoding on the values
-// automatically because the type is a byte slice. Transactions are defined as a
-// list of operations to perform, using the KVOp constants and KVTxnOp structure
-// to define operations. If any operation fails, none of the changes are applied
-// to the state store. Note that this hides the internal raw transaction interface
-// and munges the input and output types into KV-specific ones for ease of use.
-// If there are more non-KV operations in the future we may break out a new
-// transaction API client, but it will be easy to keep this KV-specific variant
-// supported.
-//
-// Even though this is generally a write operation, we take a QueryOptions input
-// and return a QueryMeta output. If the transaction contains only read ops, then
-// Consul will fast-path it to a different endpoint internally which supports
-// consistency controls, but not blocking. If there are write operations then
-// the request will always be routed through raft and any consistency settings
-// will be ignored.
-//
-// Here's an example:
-//
-// ops := KVTxnOps{
-// &KVTxnOp{
-// Verb: KVLock,
-// Key: "test/lock",
-// Session: "adf4238a-882b-9ddc-4a9d-5b6758e4159e",
-// Value: []byte("hello"),
-// },
-// &KVTxnOp{
-// Verb: KVGet,
-// Key: "another/key",
-// },
-// }
-// ok, response, _, err := kv.Txn(&ops, nil)
-//
-// If there is a problem making the transaction request then an error will be
-// returned. Otherwise, the ok value will be true if the transaction succeeded
-// or false if it was rolled back. The response is a structured return value which
-// will have the outcome of the transaction. Its Results member will have entries
-// for each operation. Deleted keys will have a nil entry in the, and to save
-// space, the Value of each key in the Results will be nil unless the operation
-// is a KVGet. If the transaction was rolled back, the Errors member will have
-// entries referencing the index of the operation that failed along with an error
-// message.
+// The Txn function has been deprecated from the KV object; please see the Txn
+// object for more information about Transactions.
func (k *KV) Txn(txn KVTxnOps, q *QueryOptions) (bool, *KVTxnResponse, *QueryMeta, error) {
- r := k.c.newRequest("PUT", "/v1/txn")
- r.setQueryOptions(q)
-
- // Convert into the internal format since this is an all-KV txn.
- ops := make(TxnOps, 0, len(txn))
- for _, kvOp := range txn {
- ops = append(ops, &TxnOp{KV: kvOp})
+ var ops TxnOps
+ for _, op := range txn {
+ ops = append(ops, &TxnOp{KV: op})
}
- r.obj = ops
- rtt, resp, err := k.c.doRequest(r)
+
+ respOk, txnResp, qm, err := k.c.txn(ops, q)
if err != nil {
return false, nil, nil, err
}
- defer resp.Body.Close()
- qm := &QueryMeta{}
- parseQueryMeta(resp, qm)
- qm.RequestTime = rtt
-
- if resp.StatusCode == http.StatusOK || resp.StatusCode == http.StatusConflict {
- var txnResp TxnResponse
- if err := decodeBody(resp, &txnResp); err != nil {
- return false, nil, nil, err
- }
-
- // Convert from the internal format.
- kvResp := KVTxnResponse{
- Errors: txnResp.Errors,
- }
- for _, result := range txnResp.Results {
- kvResp.Results = append(kvResp.Results, result.KV)
- }
- return resp.StatusCode == http.StatusOK, &kvResp, qm, nil
+ // Convert from the internal format.
+ kvResp := KVTxnResponse{
+ Errors: txnResp.Errors,
}
-
- var buf bytes.Buffer
- if _, err := io.Copy(&buf, resp.Body); err != nil {
- return false, nil, nil, fmt.Errorf("Failed to read response: %v", err)
+ for _, result := range txnResp.Results {
+ kvResp.Results = append(kvResp.Results, result.KV)
}
- return false, nil, nil, fmt.Errorf("Failed request: %s", buf.String())
+ return respOk, &kvResp, qm, nil
}
diff --git a/vendor/github.com/hashicorp/consul/api/operator_keyring.go b/vendor/github.com/hashicorp/consul/api/operator_keyring.go
index 6b61429..038d5d5 100644
--- a/vendor/github.com/hashicorp/consul/api/operator_keyring.go
+++ b/vendor/github.com/hashicorp/consul/api/operator_keyring.go
@@ -16,6 +16,9 @@
// Segment has the network segment this request corresponds to.
Segment string
+ // Messages has information or errors from serf
+ Messages map[string]string `json:",omitempty"`
+
// A map of the encryption keys to the number of nodes they're installed on
Keys map[string]int
diff --git a/vendor/github.com/hashicorp/consul/api/txn.go b/vendor/github.com/hashicorp/consul/api/txn.go
new file mode 100644
index 0000000..65d7a16
--- /dev/null
+++ b/vendor/github.com/hashicorp/consul/api/txn.go
@@ -0,0 +1,230 @@
+package api
+
+import (
+ "bytes"
+ "fmt"
+ "io"
+ "net/http"
+)
+
+// Txn is used to manipulate the Txn API
+type Txn struct {
+ c *Client
+}
+
+// Txn is used to return a handle to the K/V apis
+func (c *Client) Txn() *Txn {
+ return &Txn{c}
+}
+
+// TxnOp is the internal format we send to Consul. Currently only K/V and
+// check operations are supported.
+type TxnOp struct {
+ KV *KVTxnOp
+ Node *NodeTxnOp
+ Service *ServiceTxnOp
+ Check *CheckTxnOp
+}
+
+// TxnOps is a list of transaction operations.
+type TxnOps []*TxnOp
+
+// TxnResult is the internal format we receive from Consul.
+type TxnResult struct {
+ KV *KVPair
+ Node *Node
+ Service *CatalogService
+ Check *HealthCheck
+}
+
+// TxnResults is a list of TxnResult objects.
+type TxnResults []*TxnResult
+
+// TxnError is used to return information about an operation in a transaction.
+type TxnError struct {
+ OpIndex int
+ What string
+}
+
+// TxnErrors is a list of TxnError objects.
+type TxnErrors []*TxnError
+
+// TxnResponse is the internal format we receive from Consul.
+type TxnResponse struct {
+ Results TxnResults
+ Errors TxnErrors
+}
+
+// KVOp constants give possible operations available in a transaction.
+type KVOp string
+
+const (
+ KVSet KVOp = "set"
+ KVDelete KVOp = "delete"
+ KVDeleteCAS KVOp = "delete-cas"
+ KVDeleteTree KVOp = "delete-tree"
+ KVCAS KVOp = "cas"
+ KVLock KVOp = "lock"
+ KVUnlock KVOp = "unlock"
+ KVGet KVOp = "get"
+ KVGetTree KVOp = "get-tree"
+ KVCheckSession KVOp = "check-session"
+ KVCheckIndex KVOp = "check-index"
+ KVCheckNotExists KVOp = "check-not-exists"
+)
+
+// KVTxnOp defines a single operation inside a transaction.
+type KVTxnOp struct {
+ Verb KVOp
+ Key string
+ Value []byte
+ Flags uint64
+ Index uint64
+ Session string
+}
+
+// KVTxnOps defines a set of operations to be performed inside a single
+// transaction.
+type KVTxnOps []*KVTxnOp
+
+// KVTxnResponse has the outcome of a transaction.
+type KVTxnResponse struct {
+ Results []*KVPair
+ Errors TxnErrors
+}
+
+// NodeOp constants give possible operations available in a transaction.
+type NodeOp string
+
+const (
+ NodeGet NodeOp = "get"
+ NodeSet NodeOp = "set"
+ NodeCAS NodeOp = "cas"
+ NodeDelete NodeOp = "delete"
+ NodeDeleteCAS NodeOp = "delete-cas"
+)
+
+// NodeTxnOp defines a single operation inside a transaction.
+type NodeTxnOp struct {
+ Verb NodeOp
+ Node Node
+}
+
+// ServiceOp constants give possible operations available in a transaction.
+type ServiceOp string
+
+const (
+ ServiceGet ServiceOp = "get"
+ ServiceSet ServiceOp = "set"
+ ServiceCAS ServiceOp = "cas"
+ ServiceDelete ServiceOp = "delete"
+ ServiceDeleteCAS ServiceOp = "delete-cas"
+)
+
+// ServiceTxnOp defines a single operation inside a transaction.
+type ServiceTxnOp struct {
+ Verb ServiceOp
+ Node string
+ Service AgentService
+}
+
+// CheckOp constants give possible operations available in a transaction.
+type CheckOp string
+
+const (
+ CheckGet CheckOp = "get"
+ CheckSet CheckOp = "set"
+ CheckCAS CheckOp = "cas"
+ CheckDelete CheckOp = "delete"
+ CheckDeleteCAS CheckOp = "delete-cas"
+)
+
+// CheckTxnOp defines a single operation inside a transaction.
+type CheckTxnOp struct {
+ Verb CheckOp
+ Check HealthCheck
+}
+
+// Txn is used to apply multiple Consul operations in a single, atomic transaction.
+//
+// Note that Go will perform the required base64 encoding on the values
+// automatically because the type is a byte slice. Transactions are defined as a
+// list of operations to perform, using the different fields in the TxnOp structure
+// to define operations. If any operation fails, none of the changes are applied
+// to the state store.
+//
+// Even though this is generally a write operation, we take a QueryOptions input
+// and return a QueryMeta output. If the transaction contains only read ops, then
+// Consul will fast-path it to a different endpoint internally which supports
+// consistency controls, but not blocking. If there are write operations then
+// the request will always be routed through raft and any consistency settings
+// will be ignored.
+//
+// Here's an example:
+//
+// ops := KVTxnOps{
+// &KVTxnOp{
+// Verb: KVLock,
+// Key: "test/lock",
+// Session: "adf4238a-882b-9ddc-4a9d-5b6758e4159e",
+// Value: []byte("hello"),
+// },
+// &KVTxnOp{
+// Verb: KVGet,
+// Key: "another/key",
+// },
+// &CheckTxnOp{
+// Verb: CheckSet,
+// HealthCheck: HealthCheck{
+// Node: "foo",
+// CheckID: "redis:a",
+// Name: "Redis Health Check",
+// Status: "passing",
+// },
+// }
+// }
+// ok, response, _, err := kv.Txn(&ops, nil)
+//
+// If there is a problem making the transaction request then an error will be
+// returned. Otherwise, the ok value will be true if the transaction succeeded
+// or false if it was rolled back. The response is a structured return value which
+// will have the outcome of the transaction. Its Results member will have entries
+// for each operation. For KV operations, Deleted keys will have a nil entry in the
+// results, and to save space, the Value of each key in the Results will be nil
+// unless the operation is a KVGet. If the transaction was rolled back, the Errors
+// member will have entries referencing the index of the operation that failed
+// along with an error message.
+func (t *Txn) Txn(txn TxnOps, q *QueryOptions) (bool, *TxnResponse, *QueryMeta, error) {
+ return t.c.txn(txn, q)
+}
+
+func (c *Client) txn(txn TxnOps, q *QueryOptions) (bool, *TxnResponse, *QueryMeta, error) {
+ r := c.newRequest("PUT", "/v1/txn")
+ r.setQueryOptions(q)
+
+ r.obj = txn
+ rtt, resp, err := c.doRequest(r)
+ if err != nil {
+ return false, nil, nil, err
+ }
+ defer resp.Body.Close()
+
+ qm := &QueryMeta{}
+ parseQueryMeta(resp, qm)
+ qm.RequestTime = rtt
+
+ if resp.StatusCode == http.StatusOK || resp.StatusCode == http.StatusConflict {
+ var txnResp TxnResponse
+ if err := decodeBody(resp, &txnResp); err != nil {
+ return false, nil, nil, err
+ }
+
+ return resp.StatusCode == http.StatusOK, &txnResp, qm, nil
+ }
+
+ var buf bytes.Buffer
+ if _, err := io.Copy(&buf, resp.Body); err != nil {
+ return false, nil, nil, fmt.Errorf("Failed to read response: %v", err)
+ }
+ return false, nil, nil, fmt.Errorf("Failed request: %s", buf.String())
+}
diff --git a/vendor/github.com/hashicorp/go-cleanhttp/go.mod b/vendor/github.com/hashicorp/go-cleanhttp/go.mod
new file mode 100644
index 0000000..310f075
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-cleanhttp/go.mod
@@ -0,0 +1 @@
+module github.com/hashicorp/go-cleanhttp
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/.gitignore b/vendor/github.com/hashicorp/go-immutable-radix/.gitignore
new file mode 100644
index 0000000..daf913b
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/.gitignore
@@ -0,0 +1,24 @@
+# Compiled Object files, Static and Dynamic libs (Shared Objects)
+*.o
+*.a
+*.so
+
+# Folders
+_obj
+_test
+
+# Architecture specific extensions/prefixes
+*.[568vq]
+[568vq].out
+
+*.cgo1.go
+*.cgo2.c
+_cgo_defun.c
+_cgo_gotypes.go
+_cgo_export.*
+
+_testmain.go
+
+*.exe
+*.test
+*.prof
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/.travis.yml b/vendor/github.com/hashicorp/go-immutable-radix/.travis.yml
new file mode 100644
index 0000000..1a0bbea
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/.travis.yml
@@ -0,0 +1,3 @@
+language: go
+go:
+ - tip
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/LICENSE b/vendor/github.com/hashicorp/go-immutable-radix/LICENSE
new file mode 100644
index 0000000..e87a115
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/LICENSE
@@ -0,0 +1,363 @@
+Mozilla Public License, version 2.0
+
+1. Definitions
+
+1.1. "Contributor"
+
+ means each individual or legal entity that creates, contributes to the
+ creation of, or owns Covered Software.
+
+1.2. "Contributor Version"
+
+ means the combination of the Contributions of others (if any) used by a
+ Contributor and that particular Contributor's Contribution.
+
+1.3. "Contribution"
+
+ means Covered Software of a particular Contributor.
+
+1.4. "Covered Software"
+
+ means Source Code Form to which the initial Contributor has attached the
+ notice in Exhibit A, the Executable Form of such Source Code Form, and
+ Modifications of such Source Code Form, in each case including portions
+ thereof.
+
+1.5. "Incompatible With Secondary Licenses"
+ means
+
+ a. that the initial Contributor has attached the notice described in
+ Exhibit B to the Covered Software; or
+
+ b. that the Covered Software was made available under the terms of
+ version 1.1 or earlier of the License, but not also under the terms of
+ a Secondary License.
+
+1.6. "Executable Form"
+
+ means any form of the work other than Source Code Form.
+
+1.7. "Larger Work"
+
+ means a work that combines Covered Software with other material, in a
+ separate file or files, that is not Covered Software.
+
+1.8. "License"
+
+ means this document.
+
+1.9. "Licensable"
+
+ means having the right to grant, to the maximum extent possible, whether
+ at the time of the initial grant or subsequently, any and all of the
+ rights conveyed by this License.
+
+1.10. "Modifications"
+
+ means any of the following:
+
+ a. any file in Source Code Form that results from an addition to,
+ deletion from, or modification of the contents of Covered Software; or
+
+ b. any new file in Source Code Form that contains any Covered Software.
+
+1.11. "Patent Claims" of a Contributor
+
+ means any patent claim(s), including without limitation, method,
+ process, and apparatus claims, in any patent Licensable by such
+ Contributor that would be infringed, but for the grant of the License,
+ by the making, using, selling, offering for sale, having made, import,
+ or transfer of either its Contributions or its Contributor Version.
+
+1.12. "Secondary License"
+
+ means either the GNU General Public License, Version 2.0, the GNU Lesser
+ General Public License, Version 2.1, the GNU Affero General Public
+ License, Version 3.0, or any later versions of those licenses.
+
+1.13. "Source Code Form"
+
+ means the form of the work preferred for making modifications.
+
+1.14. "You" (or "Your")
+
+ means an individual or a legal entity exercising rights under this
+ License. For legal entities, "You" includes any entity that controls, is
+ controlled by, or is under common control with You. For purposes of this
+ definition, "control" means (a) the power, direct or indirect, to cause
+ the direction or management of such entity, whether by contract or
+ otherwise, or (b) ownership of more than fifty percent (50%) of the
+ outstanding shares or beneficial ownership of such entity.
+
+
+2. License Grants and Conditions
+
+2.1. Grants
+
+ Each Contributor hereby grants You a world-wide, royalty-free,
+ non-exclusive license:
+
+ a. under intellectual property rights (other than patent or trademark)
+ Licensable by such Contributor to use, reproduce, make available,
+ modify, display, perform, distribute, and otherwise exploit its
+ Contributions, either on an unmodified basis, with Modifications, or
+ as part of a Larger Work; and
+
+ b. under Patent Claims of such Contributor to make, use, sell, offer for
+ sale, have made, import, and otherwise transfer either its
+ Contributions or its Contributor Version.
+
+2.2. Effective Date
+
+ The licenses granted in Section 2.1 with respect to any Contribution
+ become effective for each Contribution on the date the Contributor first
+ distributes such Contribution.
+
+2.3. Limitations on Grant Scope
+
+ The licenses granted in this Section 2 are the only rights granted under
+ this License. No additional rights or licenses will be implied from the
+ distribution or licensing of Covered Software under this License.
+ Notwithstanding Section 2.1(b) above, no patent license is granted by a
+ Contributor:
+
+ a. for any code that a Contributor has removed from Covered Software; or
+
+ b. for infringements caused by: (i) Your and any other third party's
+ modifications of Covered Software, or (ii) the combination of its
+ Contributions with other software (except as part of its Contributor
+ Version); or
+
+ c. under Patent Claims infringed by Covered Software in the absence of
+ its Contributions.
+
+ This License does not grant any rights in the trademarks, service marks,
+ or logos of any Contributor (except as may be necessary to comply with
+ the notice requirements in Section 3.4).
+
+2.4. Subsequent Licenses
+
+ No Contributor makes additional grants as a result of Your choice to
+ distribute the Covered Software under a subsequent version of this
+ License (see Section 10.2) or under the terms of a Secondary License (if
+ permitted under the terms of Section 3.3).
+
+2.5. Representation
+
+ Each Contributor represents that the Contributor believes its
+ Contributions are its original creation(s) or it has sufficient rights to
+ grant the rights to its Contributions conveyed by this License.
+
+2.6. Fair Use
+
+ This License is not intended to limit any rights You have under
+ applicable copyright doctrines of fair use, fair dealing, or other
+ equivalents.
+
+2.7. Conditions
+
+ Sections 3.1, 3.2, 3.3, and 3.4 are conditions of the licenses granted in
+ Section 2.1.
+
+
+3. Responsibilities
+
+3.1. Distribution of Source Form
+
+ All distribution of Covered Software in Source Code Form, including any
+ Modifications that You create or to which You contribute, must be under
+ the terms of this License. You must inform recipients that the Source
+ Code Form of the Covered Software is governed by the terms of this
+ License, and how they can obtain a copy of this License. You may not
+ attempt to alter or restrict the recipients' rights in the Source Code
+ Form.
+
+3.2. Distribution of Executable Form
+
+ If You distribute Covered Software in Executable Form then:
+
+ a. such Covered Software must also be made available in Source Code Form,
+ as described in Section 3.1, and You must inform recipients of the
+ Executable Form how they can obtain a copy of such Source Code Form by
+ reasonable means in a timely manner, at a charge no more than the cost
+ of distribution to the recipient; and
+
+ b. You may distribute such Executable Form under the terms of this
+ License, or sublicense it under different terms, provided that the
+ license for the Executable Form does not attempt to limit or alter the
+ recipients' rights in the Source Code Form under this License.
+
+3.3. Distribution of a Larger Work
+
+ You may create and distribute a Larger Work under terms of Your choice,
+ provided that You also comply with the requirements of this License for
+ the Covered Software. If the Larger Work is a combination of Covered
+ Software with a work governed by one or more Secondary Licenses, and the
+ Covered Software is not Incompatible With Secondary Licenses, this
+ License permits You to additionally distribute such Covered Software
+ under the terms of such Secondary License(s), so that the recipient of
+ the Larger Work may, at their option, further distribute the Covered
+ Software under the terms of either this License or such Secondary
+ License(s).
+
+3.4. Notices
+
+ You may not remove or alter the substance of any license notices
+ (including copyright notices, patent notices, disclaimers of warranty, or
+ limitations of liability) contained within the Source Code Form of the
+ Covered Software, except that You may alter any license notices to the
+ extent required to remedy known factual inaccuracies.
+
+3.5. Application of Additional Terms
+
+ You may choose to offer, and to charge a fee for, warranty, support,
+ indemnity or liability obligations to one or more recipients of Covered
+ Software. However, You may do so only on Your own behalf, and not on
+ behalf of any Contributor. You must make it absolutely clear that any
+ such warranty, support, indemnity, or liability obligation is offered by
+ You alone, and You hereby agree to indemnify every Contributor for any
+ liability incurred by such Contributor as a result of warranty, support,
+ indemnity or liability terms You offer. You may include additional
+ disclaimers of warranty and limitations of liability specific to any
+ jurisdiction.
+
+4. Inability to Comply Due to Statute or Regulation
+
+ If it is impossible for You to comply with any of the terms of this License
+ with respect to some or all of the Covered Software due to statute,
+ judicial order, or regulation then You must: (a) comply with the terms of
+ this License to the maximum extent possible; and (b) describe the
+ limitations and the code they affect. Such description must be placed in a
+ text file included with all distributions of the Covered Software under
+ this License. Except to the extent prohibited by statute or regulation,
+ such description must be sufficiently detailed for a recipient of ordinary
+ skill to be able to understand it.
+
+5. Termination
+
+5.1. The rights granted under this License will terminate automatically if You
+ fail to comply with any of its terms. However, if You become compliant,
+ then the rights granted under this License from a particular Contributor
+ are reinstated (a) provisionally, unless and until such Contributor
+ explicitly and finally terminates Your grants, and (b) on an ongoing
+ basis, if such Contributor fails to notify You of the non-compliance by
+ some reasonable means prior to 60 days after You have come back into
+ compliance. Moreover, Your grants from a particular Contributor are
+ reinstated on an ongoing basis if such Contributor notifies You of the
+ non-compliance by some reasonable means, this is the first time You have
+ received notice of non-compliance with this License from such
+ Contributor, and You become compliant prior to 30 days after Your receipt
+ of the notice.
+
+5.2. If You initiate litigation against any entity by asserting a patent
+ infringement claim (excluding declaratory judgment actions,
+ counter-claims, and cross-claims) alleging that a Contributor Version
+ directly or indirectly infringes any patent, then the rights granted to
+ You by any and all Contributors for the Covered Software under Section
+ 2.1 of this License shall terminate.
+
+5.3. In the event of termination under Sections 5.1 or 5.2 above, all end user
+ license agreements (excluding distributors and resellers) which have been
+ validly granted by You or Your distributors under this License prior to
+ termination shall survive termination.
+
+6. Disclaimer of Warranty
+
+ Covered Software is provided under this License on an "as is" basis,
+ without warranty of any kind, either expressed, implied, or statutory,
+ including, without limitation, warranties that the Covered Software is free
+ of defects, merchantable, fit for a particular purpose or non-infringing.
+ The entire risk as to the quality and performance of the Covered Software
+ is with You. Should any Covered Software prove defective in any respect,
+ You (not any Contributor) assume the cost of any necessary servicing,
+ repair, or correction. This disclaimer of warranty constitutes an essential
+ part of this License. No use of any Covered Software is authorized under
+ this License except under this disclaimer.
+
+7. Limitation of Liability
+
+ Under no circumstances and under no legal theory, whether tort (including
+ negligence), contract, or otherwise, shall any Contributor, or anyone who
+ distributes Covered Software as permitted above, be liable to You for any
+ direct, indirect, special, incidental, or consequential damages of any
+ character including, without limitation, damages for lost profits, loss of
+ goodwill, work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses, even if such party shall have been
+ informed of the possibility of such damages. This limitation of liability
+ shall not apply to liability for death or personal injury resulting from
+ such party's negligence to the extent applicable law prohibits such
+ limitation. Some jurisdictions do not allow the exclusion or limitation of
+ incidental or consequential damages, so this exclusion and limitation may
+ not apply to You.
+
+8. Litigation
+
+ Any litigation relating to this License may be brought only in the courts
+ of a jurisdiction where the defendant maintains its principal place of
+ business and such litigation shall be governed by laws of that
+ jurisdiction, without reference to its conflict-of-law provisions. Nothing
+ in this Section shall prevent a party's ability to bring cross-claims or
+ counter-claims.
+
+9. Miscellaneous
+
+ This License represents the complete agreement concerning the subject
+ matter hereof. If any provision of this License is held to be
+ unenforceable, such provision shall be reformed only to the extent
+ necessary to make it enforceable. Any law or regulation which provides that
+ the language of a contract shall be construed against the drafter shall not
+ be used to construe this License against a Contributor.
+
+
+10. Versions of the License
+
+10.1. New Versions
+
+ Mozilla Foundation is the license steward. Except as provided in Section
+ 10.3, no one other than the license steward has the right to modify or
+ publish new versions of this License. Each version will be given a
+ distinguishing version number.
+
+10.2. Effect of New Versions
+
+ You may distribute the Covered Software under the terms of the version
+ of the License under which You originally received the Covered Software,
+ or under the terms of any subsequent version published by the license
+ steward.
+
+10.3. Modified Versions
+
+ If you create software not governed by this License, and you want to
+ create a new license for such software, you may create and use a
+ modified version of this License if you rename the license and remove
+ any references to the name of the license steward (except to note that
+ such modified license differs from this License).
+
+10.4. Distributing Source Code Form that is Incompatible With Secondary
+ Licenses If You choose to distribute Source Code Form that is
+ Incompatible With Secondary Licenses under the terms of this version of
+ the License, the notice described in Exhibit B of this License must be
+ attached.
+
+Exhibit A - Source Code Form License Notice
+
+ This Source Code Form is subject to the
+ terms of the Mozilla Public License, v.
+ 2.0. If a copy of the MPL was not
+ distributed with this file, You can
+ obtain one at
+ http://mozilla.org/MPL/2.0/.
+
+If it is not possible or desirable to put the notice in a particular file,
+then You may include the notice in a location (such as a LICENSE file in a
+relevant directory) where a recipient would be likely to look for such a
+notice.
+
+You may add additional accurate notices of copyright ownership.
+
+Exhibit B - "Incompatible With Secondary Licenses" Notice
+
+ This Source Code Form is "Incompatible
+ With Secondary Licenses", as defined by
+ the Mozilla Public License, v. 2.0.
+
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/README.md b/vendor/github.com/hashicorp/go-immutable-radix/README.md
new file mode 100644
index 0000000..8910fcc
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/README.md
@@ -0,0 +1,41 @@
+go-immutable-radix [](https://travis-ci.org/hashicorp/go-immutable-radix)
+=========
+
+Provides the `iradix` package that implements an immutable [radix tree](http://en.wikipedia.org/wiki/Radix_tree).
+The package only provides a single `Tree` implementation, optimized for sparse nodes.
+
+As a radix tree, it provides the following:
+ * O(k) operations. In many cases, this can be faster than a hash table since
+ the hash function is an O(k) operation, and hash tables have very poor cache locality.
+ * Minimum / Maximum value lookups
+ * Ordered iteration
+
+A tree supports using a transaction to batch multiple updates (insert, delete)
+in a more efficient manner than performing each operation one at a time.
+
+For a mutable variant, see [go-radix](https://github.com/armon/go-radix).
+
+Documentation
+=============
+
+The full documentation is available on [Godoc](http://godoc.org/github.com/hashicorp/go-immutable-radix).
+
+Example
+=======
+
+Below is a simple example of usage
+
+```go
+// Create a tree
+r := iradix.New()
+r, _, _ = r.Insert([]byte("foo"), 1)
+r, _, _ = r.Insert([]byte("bar"), 2)
+r, _, _ = r.Insert([]byte("foobar"), 2)
+
+// Find the longest prefix match
+m, _, _ := r.Root().LongestPrefix([]byte("foozip"))
+if string(m) != "foo" {
+ panic("should be foo")
+}
+```
+
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/edges.go b/vendor/github.com/hashicorp/go-immutable-radix/edges.go
new file mode 100644
index 0000000..a636747
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/edges.go
@@ -0,0 +1,21 @@
+package iradix
+
+import "sort"
+
+type edges []edge
+
+func (e edges) Len() int {
+ return len(e)
+}
+
+func (e edges) Less(i, j int) bool {
+ return e[i].label < e[j].label
+}
+
+func (e edges) Swap(i, j int) {
+ e[i], e[j] = e[j], e[i]
+}
+
+func (e edges) Sort() {
+ sort.Sort(e)
+}
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/go.mod b/vendor/github.com/hashicorp/go-immutable-radix/go.mod
new file mode 100644
index 0000000..27e7b7c
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/go.mod
@@ -0,0 +1,6 @@
+module github.com/hashicorp/go-immutable-radix
+
+require (
+ github.com/hashicorp/go-uuid v1.0.0
+ github.com/hashicorp/golang-lru v0.5.0
+)
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/go.sum b/vendor/github.com/hashicorp/go-immutable-radix/go.sum
new file mode 100644
index 0000000..7de5dfc
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/go.sum
@@ -0,0 +1,4 @@
+github.com/hashicorp/go-uuid v1.0.0 h1:RS8zrF7PhGwyNPOtxSClXXj9HA8feRnJzgnI1RJCSnM=
+github.com/hashicorp/go-uuid v1.0.0/go.mod h1:6SBZvOh/SIDV7/2o3Jml5SYk/TvGqwFJ/bN7x4byOro=
+github.com/hashicorp/golang-lru v0.5.0 h1:CL2msUPvZTLb5O648aiLNJw3hnBxN2+1Jq8rCOH9wdo=
+github.com/hashicorp/golang-lru v0.5.0/go.mod h1:/m3WP610KZHVQ1SGc6re/UDhFvYD7pJ4Ao+sR/qLZy8=
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/iradix.go b/vendor/github.com/hashicorp/go-immutable-radix/iradix.go
new file mode 100644
index 0000000..e5e6e57
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/iradix.go
@@ -0,0 +1,662 @@
+package iradix
+
+import (
+ "bytes"
+ "strings"
+
+ "github.com/hashicorp/golang-lru/simplelru"
+)
+
+const (
+ // defaultModifiedCache is the default size of the modified node
+ // cache used per transaction. This is used to cache the updates
+ // to the nodes near the root, while the leaves do not need to be
+ // cached. This is important for very large transactions to prevent
+ // the modified cache from growing to be enormous. This is also used
+ // to set the max size of the mutation notify maps since those should
+ // also be bounded in a similar way.
+ defaultModifiedCache = 8192
+)
+
+// Tree implements an immutable radix tree. This can be treated as a
+// Dictionary abstract data type. The main advantage over a standard
+// hash map is prefix-based lookups and ordered iteration. The immutability
+// means that it is safe to concurrently read from a Tree without any
+// coordination.
+type Tree struct {
+ root *Node
+ size int
+}
+
+// New returns an empty Tree
+func New() *Tree {
+ t := &Tree{
+ root: &Node{
+ mutateCh: make(chan struct{}),
+ },
+ }
+ return t
+}
+
+// Len is used to return the number of elements in the tree
+func (t *Tree) Len() int {
+ return t.size
+}
+
+// Txn is a transaction on the tree. This transaction is applied
+// atomically and returns a new tree when committed. A transaction
+// is not thread safe, and should only be used by a single goroutine.
+type Txn struct {
+ // root is the modified root for the transaction.
+ root *Node
+
+ // snap is a snapshot of the root node for use if we have to run the
+ // slow notify algorithm.
+ snap *Node
+
+ // size tracks the size of the tree as it is modified during the
+ // transaction.
+ size int
+
+ // writable is a cache of writable nodes that have been created during
+ // the course of the transaction. This allows us to re-use the same
+ // nodes for further writes and avoid unnecessary copies of nodes that
+ // have never been exposed outside the transaction. This will only hold
+ // up to defaultModifiedCache number of entries.
+ writable *simplelru.LRU
+
+ // trackChannels is used to hold channels that need to be notified to
+ // signal mutation of the tree. This will only hold up to
+ // defaultModifiedCache number of entries, after which we will set the
+ // trackOverflow flag, which will cause us to use a more expensive
+ // algorithm to perform the notifications. Mutation tracking is only
+ // performed if trackMutate is true.
+ trackChannels map[chan struct{}]struct{}
+ trackOverflow bool
+ trackMutate bool
+}
+
+// Txn starts a new transaction that can be used to mutate the tree
+func (t *Tree) Txn() *Txn {
+ txn := &Txn{
+ root: t.root,
+ snap: t.root,
+ size: t.size,
+ }
+ return txn
+}
+
+// TrackMutate can be used to toggle if mutations are tracked. If this is enabled
+// then notifications will be issued for affected internal nodes and leaves when
+// the transaction is committed.
+func (t *Txn) TrackMutate(track bool) {
+ t.trackMutate = track
+}
+
+// trackChannel safely attempts to track the given mutation channel, setting the
+// overflow flag if we can no longer track any more. This limits the amount of
+// state that will accumulate during a transaction and we have a slower algorithm
+// to switch to if we overflow.
+func (t *Txn) trackChannel(ch chan struct{}) {
+ // In overflow, make sure we don't store any more objects.
+ if t.trackOverflow {
+ return
+ }
+
+ // If this would overflow the state we reject it and set the flag (since
+ // we aren't tracking everything that's required any longer).
+ if len(t.trackChannels) >= defaultModifiedCache {
+ // Mark that we are in the overflow state
+ t.trackOverflow = true
+
+ // Clear the map so that the channels can be garbage collected. It is
+ // safe to do this since we have already overflowed and will be using
+ // the slow notify algorithm.
+ t.trackChannels = nil
+ return
+ }
+
+ // Create the map on the fly when we need it.
+ if t.trackChannels == nil {
+ t.trackChannels = make(map[chan struct{}]struct{})
+ }
+
+ // Otherwise we are good to track it.
+ t.trackChannels[ch] = struct{}{}
+}
+
+// writeNode returns a node to be modified, if the current node has already been
+// modified during the course of the transaction, it is used in-place. Set
+// forLeafUpdate to true if you are getting a write node to update the leaf,
+// which will set leaf mutation tracking appropriately as well.
+func (t *Txn) writeNode(n *Node, forLeafUpdate bool) *Node {
+ // Ensure the writable set exists.
+ if t.writable == nil {
+ lru, err := simplelru.NewLRU(defaultModifiedCache, nil)
+ if err != nil {
+ panic(err)
+ }
+ t.writable = lru
+ }
+
+ // If this node has already been modified, we can continue to use it
+ // during this transaction. We know that we don't need to track it for
+ // a node update since the node is writable, but if this is for a leaf
+ // update we track it, in case the initial write to this node didn't
+ // update the leaf.
+ if _, ok := t.writable.Get(n); ok {
+ if t.trackMutate && forLeafUpdate && n.leaf != nil {
+ t.trackChannel(n.leaf.mutateCh)
+ }
+ return n
+ }
+
+ // Mark this node as being mutated.
+ if t.trackMutate {
+ t.trackChannel(n.mutateCh)
+ }
+
+ // Mark its leaf as being mutated, if appropriate.
+ if t.trackMutate && forLeafUpdate && n.leaf != nil {
+ t.trackChannel(n.leaf.mutateCh)
+ }
+
+ // Copy the existing node. If you have set forLeafUpdate it will be
+ // safe to replace this leaf with another after you get your node for
+ // writing. You MUST replace it, because the channel associated with
+ // this leaf will be closed when this transaction is committed.
+ nc := &Node{
+ mutateCh: make(chan struct{}),
+ leaf: n.leaf,
+ }
+ if n.prefix != nil {
+ nc.prefix = make([]byte, len(n.prefix))
+ copy(nc.prefix, n.prefix)
+ }
+ if len(n.edges) != 0 {
+ nc.edges = make([]edge, len(n.edges))
+ copy(nc.edges, n.edges)
+ }
+
+ // Mark this node as writable.
+ t.writable.Add(nc, nil)
+ return nc
+}
+
+// Visit all the nodes in the tree under n, and add their mutateChannels to the transaction
+// Returns the size of the subtree visited
+func (t *Txn) trackChannelsAndCount(n *Node) int {
+ // Count only leaf nodes
+ leaves := 0
+ if n.leaf != nil {
+ leaves = 1
+ }
+ // Mark this node as being mutated.
+ if t.trackMutate {
+ t.trackChannel(n.mutateCh)
+ }
+
+ // Mark its leaf as being mutated, if appropriate.
+ if t.trackMutate && n.leaf != nil {
+ t.trackChannel(n.leaf.mutateCh)
+ }
+
+ // Recurse on the children
+ for _, e := range n.edges {
+ leaves += t.trackChannelsAndCount(e.node)
+ }
+ return leaves
+}
+
+// mergeChild is called to collapse the given node with its child. This is only
+// called when the given node is not a leaf and has a single edge.
+func (t *Txn) mergeChild(n *Node) {
+ // Mark the child node as being mutated since we are about to abandon
+ // it. We don't need to mark the leaf since we are retaining it if it
+ // is there.
+ e := n.edges[0]
+ child := e.node
+ if t.trackMutate {
+ t.trackChannel(child.mutateCh)
+ }
+
+ // Merge the nodes.
+ n.prefix = concat(n.prefix, child.prefix)
+ n.leaf = child.leaf
+ if len(child.edges) != 0 {
+ n.edges = make([]edge, len(child.edges))
+ copy(n.edges, child.edges)
+ } else {
+ n.edges = nil
+ }
+}
+
+// insert does a recursive insertion
+func (t *Txn) insert(n *Node, k, search []byte, v interface{}) (*Node, interface{}, bool) {
+ // Handle key exhaustion
+ if len(search) == 0 {
+ var oldVal interface{}
+ didUpdate := false
+ if n.isLeaf() {
+ oldVal = n.leaf.val
+ didUpdate = true
+ }
+
+ nc := t.writeNode(n, true)
+ nc.leaf = &leafNode{
+ mutateCh: make(chan struct{}),
+ key: k,
+ val: v,
+ }
+ return nc, oldVal, didUpdate
+ }
+
+ // Look for the edge
+ idx, child := n.getEdge(search[0])
+
+ // No edge, create one
+ if child == nil {
+ e := edge{
+ label: search[0],
+ node: &Node{
+ mutateCh: make(chan struct{}),
+ leaf: &leafNode{
+ mutateCh: make(chan struct{}),
+ key: k,
+ val: v,
+ },
+ prefix: search,
+ },
+ }
+ nc := t.writeNode(n, false)
+ nc.addEdge(e)
+ return nc, nil, false
+ }
+
+ // Determine longest prefix of the search key on match
+ commonPrefix := longestPrefix(search, child.prefix)
+ if commonPrefix == len(child.prefix) {
+ search = search[commonPrefix:]
+ newChild, oldVal, didUpdate := t.insert(child, k, search, v)
+ if newChild != nil {
+ nc := t.writeNode(n, false)
+ nc.edges[idx].node = newChild
+ return nc, oldVal, didUpdate
+ }
+ return nil, oldVal, didUpdate
+ }
+
+ // Split the node
+ nc := t.writeNode(n, false)
+ splitNode := &Node{
+ mutateCh: make(chan struct{}),
+ prefix: search[:commonPrefix],
+ }
+ nc.replaceEdge(edge{
+ label: search[0],
+ node: splitNode,
+ })
+
+ // Restore the existing child node
+ modChild := t.writeNode(child, false)
+ splitNode.addEdge(edge{
+ label: modChild.prefix[commonPrefix],
+ node: modChild,
+ })
+ modChild.prefix = modChild.prefix[commonPrefix:]
+
+ // Create a new leaf node
+ leaf := &leafNode{
+ mutateCh: make(chan struct{}),
+ key: k,
+ val: v,
+ }
+
+ // If the new key is a subset, add to to this node
+ search = search[commonPrefix:]
+ if len(search) == 0 {
+ splitNode.leaf = leaf
+ return nc, nil, false
+ }
+
+ // Create a new edge for the node
+ splitNode.addEdge(edge{
+ label: search[0],
+ node: &Node{
+ mutateCh: make(chan struct{}),
+ leaf: leaf,
+ prefix: search,
+ },
+ })
+ return nc, nil, false
+}
+
+// delete does a recursive deletion
+func (t *Txn) delete(parent, n *Node, search []byte) (*Node, *leafNode) {
+ // Check for key exhaustion
+ if len(search) == 0 {
+ if !n.isLeaf() {
+ return nil, nil
+ }
+ // Copy the pointer in case we are in a transaction that already
+ // modified this node since the node will be reused. Any changes
+ // made to the node will not affect returning the original leaf
+ // value.
+ oldLeaf := n.leaf
+
+ // Remove the leaf node
+ nc := t.writeNode(n, true)
+ nc.leaf = nil
+
+ // Check if this node should be merged
+ if n != t.root && len(nc.edges) == 1 {
+ t.mergeChild(nc)
+ }
+ return nc, oldLeaf
+ }
+
+ // Look for an edge
+ label := search[0]
+ idx, child := n.getEdge(label)
+ if child == nil || !bytes.HasPrefix(search, child.prefix) {
+ return nil, nil
+ }
+
+ // Consume the search prefix
+ search = search[len(child.prefix):]
+ newChild, leaf := t.delete(n, child, search)
+ if newChild == nil {
+ return nil, nil
+ }
+
+ // Copy this node. WATCH OUT - it's safe to pass "false" here because we
+ // will only ADD a leaf via nc.mergeChild() if there isn't one due to
+ // the !nc.isLeaf() check in the logic just below. This is pretty subtle,
+ // so be careful if you change any of the logic here.
+ nc := t.writeNode(n, false)
+
+ // Delete the edge if the node has no edges
+ if newChild.leaf == nil && len(newChild.edges) == 0 {
+ nc.delEdge(label)
+ if n != t.root && len(nc.edges) == 1 && !nc.isLeaf() {
+ t.mergeChild(nc)
+ }
+ } else {
+ nc.edges[idx].node = newChild
+ }
+ return nc, leaf
+}
+
+// delete does a recursive deletion
+func (t *Txn) deletePrefix(parent, n *Node, search []byte) (*Node, int) {
+ // Check for key exhaustion
+ if len(search) == 0 {
+ nc := t.writeNode(n, true)
+ if n.isLeaf() {
+ nc.leaf = nil
+ }
+ nc.edges = nil
+ return nc, t.trackChannelsAndCount(n)
+ }
+
+ // Look for an edge
+ label := search[0]
+ idx, child := n.getEdge(label)
+ // We make sure that either the child node's prefix starts with the search term, or the search term starts with the child node's prefix
+ // Need to do both so that we can delete prefixes that don't correspond to any node in the tree
+ if child == nil || (!bytes.HasPrefix(child.prefix, search) && !bytes.HasPrefix(search, child.prefix)) {
+ return nil, 0
+ }
+
+ // Consume the search prefix
+ if len(child.prefix) > len(search) {
+ search = []byte("")
+ } else {
+ search = search[len(child.prefix):]
+ }
+ newChild, numDeletions := t.deletePrefix(n, child, search)
+ if newChild == nil {
+ return nil, 0
+ }
+ // Copy this node. WATCH OUT - it's safe to pass "false" here because we
+ // will only ADD a leaf via nc.mergeChild() if there isn't one due to
+ // the !nc.isLeaf() check in the logic just below. This is pretty subtle,
+ // so be careful if you change any of the logic here.
+
+ nc := t.writeNode(n, false)
+
+ // Delete the edge if the node has no edges
+ if newChild.leaf == nil && len(newChild.edges) == 0 {
+ nc.delEdge(label)
+ if n != t.root && len(nc.edges) == 1 && !nc.isLeaf() {
+ t.mergeChild(nc)
+ }
+ } else {
+ nc.edges[idx].node = newChild
+ }
+ return nc, numDeletions
+}
+
+// Insert is used to add or update a given key. The return provides
+// the previous value and a bool indicating if any was set.
+func (t *Txn) Insert(k []byte, v interface{}) (interface{}, bool) {
+ newRoot, oldVal, didUpdate := t.insert(t.root, k, k, v)
+ if newRoot != nil {
+ t.root = newRoot
+ }
+ if !didUpdate {
+ t.size++
+ }
+ return oldVal, didUpdate
+}
+
+// Delete is used to delete a given key. Returns the old value if any,
+// and a bool indicating if the key was set.
+func (t *Txn) Delete(k []byte) (interface{}, bool) {
+ newRoot, leaf := t.delete(nil, t.root, k)
+ if newRoot != nil {
+ t.root = newRoot
+ }
+ if leaf != nil {
+ t.size--
+ return leaf.val, true
+ }
+ return nil, false
+}
+
+// DeletePrefix is used to delete an entire subtree that matches the prefix
+// This will delete all nodes under that prefix
+func (t *Txn) DeletePrefix(prefix []byte) bool {
+ newRoot, numDeletions := t.deletePrefix(nil, t.root, prefix)
+ if newRoot != nil {
+ t.root = newRoot
+ t.size = t.size - numDeletions
+ return true
+ }
+ return false
+
+}
+
+// Root returns the current root of the radix tree within this
+// transaction. The root is not safe across insert and delete operations,
+// but can be used to read the current state during a transaction.
+func (t *Txn) Root() *Node {
+ return t.root
+}
+
+// Get is used to lookup a specific key, returning
+// the value and if it was found
+func (t *Txn) Get(k []byte) (interface{}, bool) {
+ return t.root.Get(k)
+}
+
+// GetWatch is used to lookup a specific key, returning
+// the watch channel, value and if it was found
+func (t *Txn) GetWatch(k []byte) (<-chan struct{}, interface{}, bool) {
+ return t.root.GetWatch(k)
+}
+
+// Commit is used to finalize the transaction and return a new tree. If mutation
+// tracking is turned on then notifications will also be issued.
+func (t *Txn) Commit() *Tree {
+ nt := t.CommitOnly()
+ if t.trackMutate {
+ t.Notify()
+ }
+ return nt
+}
+
+// CommitOnly is used to finalize the transaction and return a new tree, but
+// does not issue any notifications until Notify is called.
+func (t *Txn) CommitOnly() *Tree {
+ nt := &Tree{t.root, t.size}
+ t.writable = nil
+ return nt
+}
+
+// slowNotify does a complete comparison of the before and after trees in order
+// to trigger notifications. This doesn't require any additional state but it
+// is very expensive to compute.
+func (t *Txn) slowNotify() {
+ snapIter := t.snap.rawIterator()
+ rootIter := t.root.rawIterator()
+ for snapIter.Front() != nil || rootIter.Front() != nil {
+ // If we've exhausted the nodes in the old snapshot, we know
+ // there's nothing remaining to notify.
+ if snapIter.Front() == nil {
+ return
+ }
+ snapElem := snapIter.Front()
+
+ // If we've exhausted the nodes in the new root, we know we need
+ // to invalidate everything that remains in the old snapshot. We
+ // know from the loop condition there's something in the old
+ // snapshot.
+ if rootIter.Front() == nil {
+ close(snapElem.mutateCh)
+ if snapElem.isLeaf() {
+ close(snapElem.leaf.mutateCh)
+ }
+ snapIter.Next()
+ continue
+ }
+
+ // Do one string compare so we can check the various conditions
+ // below without repeating the compare.
+ cmp := strings.Compare(snapIter.Path(), rootIter.Path())
+
+ // If the snapshot is behind the root, then we must have deleted
+ // this node during the transaction.
+ if cmp < 0 {
+ close(snapElem.mutateCh)
+ if snapElem.isLeaf() {
+ close(snapElem.leaf.mutateCh)
+ }
+ snapIter.Next()
+ continue
+ }
+
+ // If the snapshot is ahead of the root, then we must have added
+ // this node during the transaction.
+ if cmp > 0 {
+ rootIter.Next()
+ continue
+ }
+
+ // If we have the same path, then we need to see if we mutated a
+ // node and possibly the leaf.
+ rootElem := rootIter.Front()
+ if snapElem != rootElem {
+ close(snapElem.mutateCh)
+ if snapElem.leaf != nil && (snapElem.leaf != rootElem.leaf) {
+ close(snapElem.leaf.mutateCh)
+ }
+ }
+ snapIter.Next()
+ rootIter.Next()
+ }
+}
+
+// Notify is used along with TrackMutate to trigger notifications. This must
+// only be done once a transaction is committed via CommitOnly, and it is called
+// automatically by Commit.
+func (t *Txn) Notify() {
+ if !t.trackMutate {
+ return
+ }
+
+ // If we've overflowed the tracking state we can't use it in any way and
+ // need to do a full tree compare.
+ if t.trackOverflow {
+ t.slowNotify()
+ } else {
+ for ch := range t.trackChannels {
+ close(ch)
+ }
+ }
+
+ // Clean up the tracking state so that a re-notify is safe (will trigger
+ // the else clause above which will be a no-op).
+ t.trackChannels = nil
+ t.trackOverflow = false
+}
+
+// Insert is used to add or update a given key. The return provides
+// the new tree, previous value and a bool indicating if any was set.
+func (t *Tree) Insert(k []byte, v interface{}) (*Tree, interface{}, bool) {
+ txn := t.Txn()
+ old, ok := txn.Insert(k, v)
+ return txn.Commit(), old, ok
+}
+
+// Delete is used to delete a given key. Returns the new tree,
+// old value if any, and a bool indicating if the key was set.
+func (t *Tree) Delete(k []byte) (*Tree, interface{}, bool) {
+ txn := t.Txn()
+ old, ok := txn.Delete(k)
+ return txn.Commit(), old, ok
+}
+
+// DeletePrefix is used to delete all nodes starting with a given prefix. Returns the new tree,
+// and a bool indicating if the prefix matched any nodes
+func (t *Tree) DeletePrefix(k []byte) (*Tree, bool) {
+ txn := t.Txn()
+ ok := txn.DeletePrefix(k)
+ return txn.Commit(), ok
+}
+
+// Root returns the root node of the tree which can be used for richer
+// query operations.
+func (t *Tree) Root() *Node {
+ return t.root
+}
+
+// Get is used to lookup a specific key, returning
+// the value and if it was found
+func (t *Tree) Get(k []byte) (interface{}, bool) {
+ return t.root.Get(k)
+}
+
+// longestPrefix finds the length of the shared prefix
+// of two strings
+func longestPrefix(k1, k2 []byte) int {
+ max := len(k1)
+ if l := len(k2); l < max {
+ max = l
+ }
+ var i int
+ for i = 0; i < max; i++ {
+ if k1[i] != k2[i] {
+ break
+ }
+ }
+ return i
+}
+
+// concat two byte slices, returning a third new copy
+func concat(a, b []byte) []byte {
+ c := make([]byte, len(a)+len(b))
+ copy(c, a)
+ copy(c[len(a):], b)
+ return c
+}
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/iter.go b/vendor/github.com/hashicorp/go-immutable-radix/iter.go
new file mode 100644
index 0000000..9815e02
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/iter.go
@@ -0,0 +1,91 @@
+package iradix
+
+import "bytes"
+
+// Iterator is used to iterate over a set of nodes
+// in pre-order
+type Iterator struct {
+ node *Node
+ stack []edges
+}
+
+// SeekPrefixWatch is used to seek the iterator to a given prefix
+// and returns the watch channel of the finest granularity
+func (i *Iterator) SeekPrefixWatch(prefix []byte) (watch <-chan struct{}) {
+ // Wipe the stack
+ i.stack = nil
+ n := i.node
+ watch = n.mutateCh
+ search := prefix
+ for {
+ // Check for key exhaution
+ if len(search) == 0 {
+ i.node = n
+ return
+ }
+
+ // Look for an edge
+ _, n = n.getEdge(search[0])
+ if n == nil {
+ i.node = nil
+ return
+ }
+
+ // Update to the finest granularity as the search makes progress
+ watch = n.mutateCh
+
+ // Consume the search prefix
+ if bytes.HasPrefix(search, n.prefix) {
+ search = search[len(n.prefix):]
+
+ } else if bytes.HasPrefix(n.prefix, search) {
+ i.node = n
+ return
+ } else {
+ i.node = nil
+ return
+ }
+ }
+}
+
+// SeekPrefix is used to seek the iterator to a given prefix
+func (i *Iterator) SeekPrefix(prefix []byte) {
+ i.SeekPrefixWatch(prefix)
+}
+
+// Next returns the next node in order
+func (i *Iterator) Next() ([]byte, interface{}, bool) {
+ // Initialize our stack if needed
+ if i.stack == nil && i.node != nil {
+ i.stack = []edges{
+ edges{
+ edge{node: i.node},
+ },
+ }
+ }
+
+ for len(i.stack) > 0 {
+ // Inspect the last element of the stack
+ n := len(i.stack)
+ last := i.stack[n-1]
+ elem := last[0].node
+
+ // Update the stack
+ if len(last) > 1 {
+ i.stack[n-1] = last[1:]
+ } else {
+ i.stack = i.stack[:n-1]
+ }
+
+ // Push the edges onto the frontier
+ if len(elem.edges) > 0 {
+ i.stack = append(i.stack, elem.edges)
+ }
+
+ // Return the leaf values if any
+ if elem.leaf != nil {
+ return elem.leaf.key, elem.leaf.val, true
+ }
+ }
+ return nil, nil, false
+}
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/node.go b/vendor/github.com/hashicorp/go-immutable-radix/node.go
new file mode 100644
index 0000000..7a065e7
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/node.go
@@ -0,0 +1,292 @@
+package iradix
+
+import (
+ "bytes"
+ "sort"
+)
+
+// WalkFn is used when walking the tree. Takes a
+// key and value, returning if iteration should
+// be terminated.
+type WalkFn func(k []byte, v interface{}) bool
+
+// leafNode is used to represent a value
+type leafNode struct {
+ mutateCh chan struct{}
+ key []byte
+ val interface{}
+}
+
+// edge is used to represent an edge node
+type edge struct {
+ label byte
+ node *Node
+}
+
+// Node is an immutable node in the radix tree
+type Node struct {
+ // mutateCh is closed if this node is modified
+ mutateCh chan struct{}
+
+ // leaf is used to store possible leaf
+ leaf *leafNode
+
+ // prefix is the common prefix we ignore
+ prefix []byte
+
+ // Edges should be stored in-order for iteration.
+ // We avoid a fully materialized slice to save memory,
+ // since in most cases we expect to be sparse
+ edges edges
+}
+
+func (n *Node) isLeaf() bool {
+ return n.leaf != nil
+}
+
+func (n *Node) addEdge(e edge) {
+ num := len(n.edges)
+ idx := sort.Search(num, func(i int) bool {
+ return n.edges[i].label >= e.label
+ })
+ n.edges = append(n.edges, e)
+ if idx != num {
+ copy(n.edges[idx+1:], n.edges[idx:num])
+ n.edges[idx] = e
+ }
+}
+
+func (n *Node) replaceEdge(e edge) {
+ num := len(n.edges)
+ idx := sort.Search(num, func(i int) bool {
+ return n.edges[i].label >= e.label
+ })
+ if idx < num && n.edges[idx].label == e.label {
+ n.edges[idx].node = e.node
+ return
+ }
+ panic("replacing missing edge")
+}
+
+func (n *Node) getEdge(label byte) (int, *Node) {
+ num := len(n.edges)
+ idx := sort.Search(num, func(i int) bool {
+ return n.edges[i].label >= label
+ })
+ if idx < num && n.edges[idx].label == label {
+ return idx, n.edges[idx].node
+ }
+ return -1, nil
+}
+
+func (n *Node) delEdge(label byte) {
+ num := len(n.edges)
+ idx := sort.Search(num, func(i int) bool {
+ return n.edges[i].label >= label
+ })
+ if idx < num && n.edges[idx].label == label {
+ copy(n.edges[idx:], n.edges[idx+1:])
+ n.edges[len(n.edges)-1] = edge{}
+ n.edges = n.edges[:len(n.edges)-1]
+ }
+}
+
+func (n *Node) GetWatch(k []byte) (<-chan struct{}, interface{}, bool) {
+ search := k
+ watch := n.mutateCh
+ for {
+ // Check for key exhaustion
+ if len(search) == 0 {
+ if n.isLeaf() {
+ return n.leaf.mutateCh, n.leaf.val, true
+ }
+ break
+ }
+
+ // Look for an edge
+ _, n = n.getEdge(search[0])
+ if n == nil {
+ break
+ }
+
+ // Update to the finest granularity as the search makes progress
+ watch = n.mutateCh
+
+ // Consume the search prefix
+ if bytes.HasPrefix(search, n.prefix) {
+ search = search[len(n.prefix):]
+ } else {
+ break
+ }
+ }
+ return watch, nil, false
+}
+
+func (n *Node) Get(k []byte) (interface{}, bool) {
+ _, val, ok := n.GetWatch(k)
+ return val, ok
+}
+
+// LongestPrefix is like Get, but instead of an
+// exact match, it will return the longest prefix match.
+func (n *Node) LongestPrefix(k []byte) ([]byte, interface{}, bool) {
+ var last *leafNode
+ search := k
+ for {
+ // Look for a leaf node
+ if n.isLeaf() {
+ last = n.leaf
+ }
+
+ // Check for key exhaution
+ if len(search) == 0 {
+ break
+ }
+
+ // Look for an edge
+ _, n = n.getEdge(search[0])
+ if n == nil {
+ break
+ }
+
+ // Consume the search prefix
+ if bytes.HasPrefix(search, n.prefix) {
+ search = search[len(n.prefix):]
+ } else {
+ break
+ }
+ }
+ if last != nil {
+ return last.key, last.val, true
+ }
+ return nil, nil, false
+}
+
+// Minimum is used to return the minimum value in the tree
+func (n *Node) Minimum() ([]byte, interface{}, bool) {
+ for {
+ if n.isLeaf() {
+ return n.leaf.key, n.leaf.val, true
+ }
+ if len(n.edges) > 0 {
+ n = n.edges[0].node
+ } else {
+ break
+ }
+ }
+ return nil, nil, false
+}
+
+// Maximum is used to return the maximum value in the tree
+func (n *Node) Maximum() ([]byte, interface{}, bool) {
+ for {
+ if num := len(n.edges); num > 0 {
+ n = n.edges[num-1].node
+ continue
+ }
+ if n.isLeaf() {
+ return n.leaf.key, n.leaf.val, true
+ } else {
+ break
+ }
+ }
+ return nil, nil, false
+}
+
+// Iterator is used to return an iterator at
+// the given node to walk the tree
+func (n *Node) Iterator() *Iterator {
+ return &Iterator{node: n}
+}
+
+// rawIterator is used to return a raw iterator at the given node to walk the
+// tree.
+func (n *Node) rawIterator() *rawIterator {
+ iter := &rawIterator{node: n}
+ iter.Next()
+ return iter
+}
+
+// Walk is used to walk the tree
+func (n *Node) Walk(fn WalkFn) {
+ recursiveWalk(n, fn)
+}
+
+// WalkPrefix is used to walk the tree under a prefix
+func (n *Node) WalkPrefix(prefix []byte, fn WalkFn) {
+ search := prefix
+ for {
+ // Check for key exhaution
+ if len(search) == 0 {
+ recursiveWalk(n, fn)
+ return
+ }
+
+ // Look for an edge
+ _, n = n.getEdge(search[0])
+ if n == nil {
+ break
+ }
+
+ // Consume the search prefix
+ if bytes.HasPrefix(search, n.prefix) {
+ search = search[len(n.prefix):]
+
+ } else if bytes.HasPrefix(n.prefix, search) {
+ // Child may be under our search prefix
+ recursiveWalk(n, fn)
+ return
+ } else {
+ break
+ }
+ }
+}
+
+// WalkPath is used to walk the tree, but only visiting nodes
+// from the root down to a given leaf. Where WalkPrefix walks
+// all the entries *under* the given prefix, this walks the
+// entries *above* the given prefix.
+func (n *Node) WalkPath(path []byte, fn WalkFn) {
+ search := path
+ for {
+ // Visit the leaf values if any
+ if n.leaf != nil && fn(n.leaf.key, n.leaf.val) {
+ return
+ }
+
+ // Check for key exhaution
+ if len(search) == 0 {
+ return
+ }
+
+ // Look for an edge
+ _, n = n.getEdge(search[0])
+ if n == nil {
+ return
+ }
+
+ // Consume the search prefix
+ if bytes.HasPrefix(search, n.prefix) {
+ search = search[len(n.prefix):]
+ } else {
+ break
+ }
+ }
+}
+
+// recursiveWalk is used to do a pre-order walk of a node
+// recursively. Returns true if the walk should be aborted
+func recursiveWalk(n *Node, fn WalkFn) bool {
+ // Visit the leaf values if any
+ if n.leaf != nil && fn(n.leaf.key, n.leaf.val) {
+ return true
+ }
+
+ // Recurse on the children
+ for _, e := range n.edges {
+ if recursiveWalk(e.node, fn) {
+ return true
+ }
+ }
+ return false
+}
diff --git a/vendor/github.com/hashicorp/go-immutable-radix/raw_iter.go b/vendor/github.com/hashicorp/go-immutable-radix/raw_iter.go
new file mode 100644
index 0000000..04814c1
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-immutable-radix/raw_iter.go
@@ -0,0 +1,78 @@
+package iradix
+
+// rawIterator visits each of the nodes in the tree, even the ones that are not
+// leaves. It keeps track of the effective path (what a leaf at a given node
+// would be called), which is useful for comparing trees.
+type rawIterator struct {
+ // node is the starting node in the tree for the iterator.
+ node *Node
+
+ // stack keeps track of edges in the frontier.
+ stack []rawStackEntry
+
+ // pos is the current position of the iterator.
+ pos *Node
+
+ // path is the effective path of the current iterator position,
+ // regardless of whether the current node is a leaf.
+ path string
+}
+
+// rawStackEntry is used to keep track of the cumulative common path as well as
+// its associated edges in the frontier.
+type rawStackEntry struct {
+ path string
+ edges edges
+}
+
+// Front returns the current node that has been iterated to.
+func (i *rawIterator) Front() *Node {
+ return i.pos
+}
+
+// Path returns the effective path of the current node, even if it's not actually
+// a leaf.
+func (i *rawIterator) Path() string {
+ return i.path
+}
+
+// Next advances the iterator to the next node.
+func (i *rawIterator) Next() {
+ // Initialize our stack if needed.
+ if i.stack == nil && i.node != nil {
+ i.stack = []rawStackEntry{
+ rawStackEntry{
+ edges: edges{
+ edge{node: i.node},
+ },
+ },
+ }
+ }
+
+ for len(i.stack) > 0 {
+ // Inspect the last element of the stack.
+ n := len(i.stack)
+ last := i.stack[n-1]
+ elem := last.edges[0].node
+
+ // Update the stack.
+ if len(last.edges) > 1 {
+ i.stack[n-1].edges = last.edges[1:]
+ } else {
+ i.stack = i.stack[:n-1]
+ }
+
+ // Push the edges onto the frontier.
+ if len(elem.edges) > 0 {
+ path := last.path + string(elem.prefix)
+ i.stack = append(i.stack, rawStackEntry{path, elem.edges})
+ }
+
+ i.pos = elem
+ i.path = last.path + string(elem.prefix)
+ return
+ }
+
+ i.pos = nil
+ i.path = ""
+}
diff --git a/vendor/github.com/hashicorp/go-rootcerts/go.mod b/vendor/github.com/hashicorp/go-rootcerts/go.mod
new file mode 100644
index 0000000..3c0e0e6
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-rootcerts/go.mod
@@ -0,0 +1,3 @@
+module github.com/hashicorp/go-rootcerts
+
+require github.com/mitchellh/go-homedir v1.0.0
diff --git a/vendor/github.com/hashicorp/go-rootcerts/go.sum b/vendor/github.com/hashicorp/go-rootcerts/go.sum
new file mode 100644
index 0000000..d12bb75
--- /dev/null
+++ b/vendor/github.com/hashicorp/go-rootcerts/go.sum
@@ -0,0 +1,2 @@
+github.com/mitchellh/go-homedir v1.0.0 h1:vKb8ShqSby24Yrqr/yDYkuFz8d0WUjys40rvnGC8aR0=
+github.com/mitchellh/go-homedir v1.0.0/go.mod h1:SfyaCUpYCn1Vlf4IUYiD9fPX4A5wJrkLzIz1N1q0pr0=
diff --git a/vendor/github.com/hashicorp/golang-lru/LICENSE b/vendor/github.com/hashicorp/golang-lru/LICENSE
new file mode 100644
index 0000000..be2cc4d
--- /dev/null
+++ b/vendor/github.com/hashicorp/golang-lru/LICENSE
@@ -0,0 +1,362 @@
+Mozilla Public License, version 2.0
+
+1. Definitions
+
+1.1. "Contributor"
+
+ means each individual or legal entity that creates, contributes to the
+ creation of, or owns Covered Software.
+
+1.2. "Contributor Version"
+
+ means the combination of the Contributions of others (if any) used by a
+ Contributor and that particular Contributor's Contribution.
+
+1.3. "Contribution"
+
+ means Covered Software of a particular Contributor.
+
+1.4. "Covered Software"
+
+ means Source Code Form to which the initial Contributor has attached the
+ notice in Exhibit A, the Executable Form of such Source Code Form, and
+ Modifications of such Source Code Form, in each case including portions
+ thereof.
+
+1.5. "Incompatible With Secondary Licenses"
+ means
+
+ a. that the initial Contributor has attached the notice described in
+ Exhibit B to the Covered Software; or
+
+ b. that the Covered Software was made available under the terms of
+ version 1.1 or earlier of the License, but not also under the terms of
+ a Secondary License.
+
+1.6. "Executable Form"
+
+ means any form of the work other than Source Code Form.
+
+1.7. "Larger Work"
+
+ means a work that combines Covered Software with other material, in a
+ separate file or files, that is not Covered Software.
+
+1.8. "License"
+
+ means this document.
+
+1.9. "Licensable"
+
+ means having the right to grant, to the maximum extent possible, whether
+ at the time of the initial grant or subsequently, any and all of the
+ rights conveyed by this License.
+
+1.10. "Modifications"
+
+ means any of the following:
+
+ a. any file in Source Code Form that results from an addition to,
+ deletion from, or modification of the contents of Covered Software; or
+
+ b. any new file in Source Code Form that contains any Covered Software.
+
+1.11. "Patent Claims" of a Contributor
+
+ means any patent claim(s), including without limitation, method,
+ process, and apparatus claims, in any patent Licensable by such
+ Contributor that would be infringed, but for the grant of the License,
+ by the making, using, selling, offering for sale, having made, import,
+ or transfer of either its Contributions or its Contributor Version.
+
+1.12. "Secondary License"
+
+ means either the GNU General Public License, Version 2.0, the GNU Lesser
+ General Public License, Version 2.1, the GNU Affero General Public
+ License, Version 3.0, or any later versions of those licenses.
+
+1.13. "Source Code Form"
+
+ means the form of the work preferred for making modifications.
+
+1.14. "You" (or "Your")
+
+ means an individual or a legal entity exercising rights under this
+ License. For legal entities, "You" includes any entity that controls, is
+ controlled by, or is under common control with You. For purposes of this
+ definition, "control" means (a) the power, direct or indirect, to cause
+ the direction or management of such entity, whether by contract or
+ otherwise, or (b) ownership of more than fifty percent (50%) of the
+ outstanding shares or beneficial ownership of such entity.
+
+
+2. License Grants and Conditions
+
+2.1. Grants
+
+ Each Contributor hereby grants You a world-wide, royalty-free,
+ non-exclusive license:
+
+ a. under intellectual property rights (other than patent or trademark)
+ Licensable by such Contributor to use, reproduce, make available,
+ modify, display, perform, distribute, and otherwise exploit its
+ Contributions, either on an unmodified basis, with Modifications, or
+ as part of a Larger Work; and
+
+ b. under Patent Claims of such Contributor to make, use, sell, offer for
+ sale, have made, import, and otherwise transfer either its
+ Contributions or its Contributor Version.
+
+2.2. Effective Date
+
+ The licenses granted in Section 2.1 with respect to any Contribution
+ become effective for each Contribution on the date the Contributor first
+ distributes such Contribution.
+
+2.3. Limitations on Grant Scope
+
+ The licenses granted in this Section 2 are the only rights granted under
+ this License. No additional rights or licenses will be implied from the
+ distribution or licensing of Covered Software under this License.
+ Notwithstanding Section 2.1(b) above, no patent license is granted by a
+ Contributor:
+
+ a. for any code that a Contributor has removed from Covered Software; or
+
+ b. for infringements caused by: (i) Your and any other third party's
+ modifications of Covered Software, or (ii) the combination of its
+ Contributions with other software (except as part of its Contributor
+ Version); or
+
+ c. under Patent Claims infringed by Covered Software in the absence of
+ its Contributions.
+
+ This License does not grant any rights in the trademarks, service marks,
+ or logos of any Contributor (except as may be necessary to comply with
+ the notice requirements in Section 3.4).
+
+2.4. Subsequent Licenses
+
+ No Contributor makes additional grants as a result of Your choice to
+ distribute the Covered Software under a subsequent version of this
+ License (see Section 10.2) or under the terms of a Secondary License (if
+ permitted under the terms of Section 3.3).
+
+2.5. Representation
+
+ Each Contributor represents that the Contributor believes its
+ Contributions are its original creation(s) or it has sufficient rights to
+ grant the rights to its Contributions conveyed by this License.
+
+2.6. Fair Use
+
+ This License is not intended to limit any rights You have under
+ applicable copyright doctrines of fair use, fair dealing, or other
+ equivalents.
+
+2.7. Conditions
+
+ Sections 3.1, 3.2, 3.3, and 3.4 are conditions of the licenses granted in
+ Section 2.1.
+
+
+3. Responsibilities
+
+3.1. Distribution of Source Form
+
+ All distribution of Covered Software in Source Code Form, including any
+ Modifications that You create or to which You contribute, must be under
+ the terms of this License. You must inform recipients that the Source
+ Code Form of the Covered Software is governed by the terms of this
+ License, and how they can obtain a copy of this License. You may not
+ attempt to alter or restrict the recipients' rights in the Source Code
+ Form.
+
+3.2. Distribution of Executable Form
+
+ If You distribute Covered Software in Executable Form then:
+
+ a. such Covered Software must also be made available in Source Code Form,
+ as described in Section 3.1, and You must inform recipients of the
+ Executable Form how they can obtain a copy of such Source Code Form by
+ reasonable means in a timely manner, at a charge no more than the cost
+ of distribution to the recipient; and
+
+ b. You may distribute such Executable Form under the terms of this
+ License, or sublicense it under different terms, provided that the
+ license for the Executable Form does not attempt to limit or alter the
+ recipients' rights in the Source Code Form under this License.
+
+3.3. Distribution of a Larger Work
+
+ You may create and distribute a Larger Work under terms of Your choice,
+ provided that You also comply with the requirements of this License for
+ the Covered Software. If the Larger Work is a combination of Covered
+ Software with a work governed by one or more Secondary Licenses, and the
+ Covered Software is not Incompatible With Secondary Licenses, this
+ License permits You to additionally distribute such Covered Software
+ under the terms of such Secondary License(s), so that the recipient of
+ the Larger Work may, at their option, further distribute the Covered
+ Software under the terms of either this License or such Secondary
+ License(s).
+
+3.4. Notices
+
+ You may not remove or alter the substance of any license notices
+ (including copyright notices, patent notices, disclaimers of warranty, or
+ limitations of liability) contained within the Source Code Form of the
+ Covered Software, except that You may alter any license notices to the
+ extent required to remedy known factual inaccuracies.
+
+3.5. Application of Additional Terms
+
+ You may choose to offer, and to charge a fee for, warranty, support,
+ indemnity or liability obligations to one or more recipients of Covered
+ Software. However, You may do so only on Your own behalf, and not on
+ behalf of any Contributor. You must make it absolutely clear that any
+ such warranty, support, indemnity, or liability obligation is offered by
+ You alone, and You hereby agree to indemnify every Contributor for any
+ liability incurred by such Contributor as a result of warranty, support,
+ indemnity or liability terms You offer. You may include additional
+ disclaimers of warranty and limitations of liability specific to any
+ jurisdiction.
+
+4. Inability to Comply Due to Statute or Regulation
+
+ If it is impossible for You to comply with any of the terms of this License
+ with respect to some or all of the Covered Software due to statute,
+ judicial order, or regulation then You must: (a) comply with the terms of
+ this License to the maximum extent possible; and (b) describe the
+ limitations and the code they affect. Such description must be placed in a
+ text file included with all distributions of the Covered Software under
+ this License. Except to the extent prohibited by statute or regulation,
+ such description must be sufficiently detailed for a recipient of ordinary
+ skill to be able to understand it.
+
+5. Termination
+
+5.1. The rights granted under this License will terminate automatically if You
+ fail to comply with any of its terms. However, if You become compliant,
+ then the rights granted under this License from a particular Contributor
+ are reinstated (a) provisionally, unless and until such Contributor
+ explicitly and finally terminates Your grants, and (b) on an ongoing
+ basis, if such Contributor fails to notify You of the non-compliance by
+ some reasonable means prior to 60 days after You have come back into
+ compliance. Moreover, Your grants from a particular Contributor are
+ reinstated on an ongoing basis if such Contributor notifies You of the
+ non-compliance by some reasonable means, this is the first time You have
+ received notice of non-compliance with this License from such
+ Contributor, and You become compliant prior to 30 days after Your receipt
+ of the notice.
+
+5.2. If You initiate litigation against any entity by asserting a patent
+ infringement claim (excluding declaratory judgment actions,
+ counter-claims, and cross-claims) alleging that a Contributor Version
+ directly or indirectly infringes any patent, then the rights granted to
+ You by any and all Contributors for the Covered Software under Section
+ 2.1 of this License shall terminate.
+
+5.3. In the event of termination under Sections 5.1 or 5.2 above, all end user
+ license agreements (excluding distributors and resellers) which have been
+ validly granted by You or Your distributors under this License prior to
+ termination shall survive termination.
+
+6. Disclaimer of Warranty
+
+ Covered Software is provided under this License on an "as is" basis,
+ without warranty of any kind, either expressed, implied, or statutory,
+ including, without limitation, warranties that the Covered Software is free
+ of defects, merchantable, fit for a particular purpose or non-infringing.
+ The entire risk as to the quality and performance of the Covered Software
+ is with You. Should any Covered Software prove defective in any respect,
+ You (not any Contributor) assume the cost of any necessary servicing,
+ repair, or correction. This disclaimer of warranty constitutes an essential
+ part of this License. No use of any Covered Software is authorized under
+ this License except under this disclaimer.
+
+7. Limitation of Liability
+
+ Under no circumstances and under no legal theory, whether tort (including
+ negligence), contract, or otherwise, shall any Contributor, or anyone who
+ distributes Covered Software as permitted above, be liable to You for any
+ direct, indirect, special, incidental, or consequential damages of any
+ character including, without limitation, damages for lost profits, loss of
+ goodwill, work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses, even if such party shall have been
+ informed of the possibility of such damages. This limitation of liability
+ shall not apply to liability for death or personal injury resulting from
+ such party's negligence to the extent applicable law prohibits such
+ limitation. Some jurisdictions do not allow the exclusion or limitation of
+ incidental or consequential damages, so this exclusion and limitation may
+ not apply to You.
+
+8. Litigation
+
+ Any litigation relating to this License may be brought only in the courts
+ of a jurisdiction where the defendant maintains its principal place of
+ business and such litigation shall be governed by laws of that
+ jurisdiction, without reference to its conflict-of-law provisions. Nothing
+ in this Section shall prevent a party's ability to bring cross-claims or
+ counter-claims.
+
+9. Miscellaneous
+
+ This License represents the complete agreement concerning the subject
+ matter hereof. If any provision of this License is held to be
+ unenforceable, such provision shall be reformed only to the extent
+ necessary to make it enforceable. Any law or regulation which provides that
+ the language of a contract shall be construed against the drafter shall not
+ be used to construe this License against a Contributor.
+
+
+10. Versions of the License
+
+10.1. New Versions
+
+ Mozilla Foundation is the license steward. Except as provided in Section
+ 10.3, no one other than the license steward has the right to modify or
+ publish new versions of this License. Each version will be given a
+ distinguishing version number.
+
+10.2. Effect of New Versions
+
+ You may distribute the Covered Software under the terms of the version
+ of the License under which You originally received the Covered Software,
+ or under the terms of any subsequent version published by the license
+ steward.
+
+10.3. Modified Versions
+
+ If you create software not governed by this License, and you want to
+ create a new license for such software, you may create and use a
+ modified version of this License if you rename the license and remove
+ any references to the name of the license steward (except to note that
+ such modified license differs from this License).
+
+10.4. Distributing Source Code Form that is Incompatible With Secondary
+ Licenses If You choose to distribute Source Code Form that is
+ Incompatible With Secondary Licenses under the terms of this version of
+ the License, the notice described in Exhibit B of this License must be
+ attached.
+
+Exhibit A - Source Code Form License Notice
+
+ This Source Code Form is subject to the
+ terms of the Mozilla Public License, v.
+ 2.0. If a copy of the MPL was not
+ distributed with this file, You can
+ obtain one at
+ http://mozilla.org/MPL/2.0/.
+
+If it is not possible or desirable to put the notice in a particular file,
+then You may include the notice in a location (such as a LICENSE file in a
+relevant directory) where a recipient would be likely to look for such a
+notice.
+
+You may add additional accurate notices of copyright ownership.
+
+Exhibit B - "Incompatible With Secondary Licenses" Notice
+
+ This Source Code Form is "Incompatible
+ With Secondary Licenses", as defined by
+ the Mozilla Public License, v. 2.0.
diff --git a/vendor/github.com/hashicorp/golang-lru/simplelru/lru.go b/vendor/github.com/hashicorp/golang-lru/simplelru/lru.go
new file mode 100644
index 0000000..5673773
--- /dev/null
+++ b/vendor/github.com/hashicorp/golang-lru/simplelru/lru.go
@@ -0,0 +1,161 @@
+package simplelru
+
+import (
+ "container/list"
+ "errors"
+)
+
+// EvictCallback is used to get a callback when a cache entry is evicted
+type EvictCallback func(key interface{}, value interface{})
+
+// LRU implements a non-thread safe fixed size LRU cache
+type LRU struct {
+ size int
+ evictList *list.List
+ items map[interface{}]*list.Element
+ onEvict EvictCallback
+}
+
+// entry is used to hold a value in the evictList
+type entry struct {
+ key interface{}
+ value interface{}
+}
+
+// NewLRU constructs an LRU of the given size
+func NewLRU(size int, onEvict EvictCallback) (*LRU, error) {
+ if size <= 0 {
+ return nil, errors.New("Must provide a positive size")
+ }
+ c := &LRU{
+ size: size,
+ evictList: list.New(),
+ items: make(map[interface{}]*list.Element),
+ onEvict: onEvict,
+ }
+ return c, nil
+}
+
+// Purge is used to completely clear the cache.
+func (c *LRU) Purge() {
+ for k, v := range c.items {
+ if c.onEvict != nil {
+ c.onEvict(k, v.Value.(*entry).value)
+ }
+ delete(c.items, k)
+ }
+ c.evictList.Init()
+}
+
+// Add adds a value to the cache. Returns true if an eviction occurred.
+func (c *LRU) Add(key, value interface{}) (evicted bool) {
+ // Check for existing item
+ if ent, ok := c.items[key]; ok {
+ c.evictList.MoveToFront(ent)
+ ent.Value.(*entry).value = value
+ return false
+ }
+
+ // Add new item
+ ent := &entry{key, value}
+ entry := c.evictList.PushFront(ent)
+ c.items[key] = entry
+
+ evict := c.evictList.Len() > c.size
+ // Verify size not exceeded
+ if evict {
+ c.removeOldest()
+ }
+ return evict
+}
+
+// Get looks up a key's value from the cache.
+func (c *LRU) Get(key interface{}) (value interface{}, ok bool) {
+ if ent, ok := c.items[key]; ok {
+ c.evictList.MoveToFront(ent)
+ return ent.Value.(*entry).value, true
+ }
+ return
+}
+
+// Contains checks if a key is in the cache, without updating the recent-ness
+// or deleting it for being stale.
+func (c *LRU) Contains(key interface{}) (ok bool) {
+ _, ok = c.items[key]
+ return ok
+}
+
+// Peek returns the key value (or undefined if not found) without updating
+// the "recently used"-ness of the key.
+func (c *LRU) Peek(key interface{}) (value interface{}, ok bool) {
+ var ent *list.Element
+ if ent, ok = c.items[key]; ok {
+ return ent.Value.(*entry).value, true
+ }
+ return nil, ok
+}
+
+// Remove removes the provided key from the cache, returning if the
+// key was contained.
+func (c *LRU) Remove(key interface{}) (present bool) {
+ if ent, ok := c.items[key]; ok {
+ c.removeElement(ent)
+ return true
+ }
+ return false
+}
+
+// RemoveOldest removes the oldest item from the cache.
+func (c *LRU) RemoveOldest() (key interface{}, value interface{}, ok bool) {
+ ent := c.evictList.Back()
+ if ent != nil {
+ c.removeElement(ent)
+ kv := ent.Value.(*entry)
+ return kv.key, kv.value, true
+ }
+ return nil, nil, false
+}
+
+// GetOldest returns the oldest entry
+func (c *LRU) GetOldest() (key interface{}, value interface{}, ok bool) {
+ ent := c.evictList.Back()
+ if ent != nil {
+ kv := ent.Value.(*entry)
+ return kv.key, kv.value, true
+ }
+ return nil, nil, false
+}
+
+// Keys returns a slice of the keys in the cache, from oldest to newest.
+func (c *LRU) Keys() []interface{} {
+ keys := make([]interface{}, len(c.items))
+ i := 0
+ for ent := c.evictList.Back(); ent != nil; ent = ent.Prev() {
+ keys[i] = ent.Value.(*entry).key
+ i++
+ }
+ return keys
+}
+
+// Len returns the number of items in the cache.
+func (c *LRU) Len() int {
+ return c.evictList.Len()
+}
+
+// removeOldest removes the oldest item from the cache.
+func (c *LRU) removeOldest() {
+ ent := c.evictList.Back()
+ if ent != nil {
+ c.removeElement(ent)
+ }
+}
+
+// removeElement is used to remove a given list element from the cache
+func (c *LRU) removeElement(e *list.Element) {
+ c.evictList.Remove(e)
+ kv := e.Value.(*entry)
+ delete(c.items, kv.key)
+ if c.onEvict != nil {
+ c.onEvict(kv.key, kv.value)
+ }
+}
diff --git a/vendor/github.com/hashicorp/golang-lru/simplelru/lru_interface.go b/vendor/github.com/hashicorp/golang-lru/simplelru/lru_interface.go
new file mode 100644
index 0000000..74c7077
--- /dev/null
+++ b/vendor/github.com/hashicorp/golang-lru/simplelru/lru_interface.go
@@ -0,0 +1,36 @@
+package simplelru
+
+// LRUCache is the interface for simple LRU cache.
+type LRUCache interface {
+ // Adds a value to the cache, returns true if an eviction occurred and
+ // updates the "recently used"-ness of the key.
+ Add(key, value interface{}) bool
+
+ // Returns key's value from the cache and
+ // updates the "recently used"-ness of the key. #value, isFound
+ Get(key interface{}) (value interface{}, ok bool)
+
+ // Check if a key exsists in cache without updating the recent-ness.
+ Contains(key interface{}) (ok bool)
+
+ // Returns key's value without updating the "recently used"-ness of the key.
+ Peek(key interface{}) (value interface{}, ok bool)
+
+ // Removes a key from the cache.
+ Remove(key interface{}) bool
+
+ // Removes the oldest entry from cache.
+ RemoveOldest() (interface{}, interface{}, bool)
+
+ // Returns the oldest entry from the cache. #key, value, isFound
+ GetOldest() (interface{}, interface{}, bool)
+
+ // Returns a slice of the keys in the cache, from oldest to newest.
+ Keys() []interface{}
+
+ // Returns the number of items in the cache.
+ Len() int
+
+ // Clear all cache entries
+ Purge()
+}