deps: github.com/hashicorp/terraform@sdk-v0.11-with-go-modules

Updated via: go get github.com/hashicorp/terraform@sdk-v0.11-with-go-modules and go mod tidy

1 files changed, 523 insertions, 0 deletions

diff --git a/vendor/github.com/ulikunitz/xz/lzma/bintree.go b/vendor/github.com/ulikunitz/xz/lzma/bintree.go
new file mode 100644
index 0000000..a781bd1
--- /dev/null
+++ b/vendor/github.com/ulikunitz/xz/lzma/bintree.go
@@ -0,0 +1,523 @@
+// Copyright 2014-2017 Ulrich Kunitz. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package lzma
+
+import (
+        "bufio"
+        "errors"
+        "fmt"
+        "io"
+        "unicode"
+)
+
+// node represents a node in the binary tree.
+type node struct {
+        // x is the search value
+        x uint32
+        // p parent node
+        p uint32
+        // l left child
+        l uint32
+        // r right child
+        r uint32
+}
+
+// wordLen is the number of bytes represented by the v field of a node.
+const wordLen = 4
+
+// binTree supports the identification of the next operation based on a
+// binary tree.
+//
+// Nodes will be identified by their index into the ring buffer.
+type binTree struct {
+        dict *encoderDict
+        // ring buffer of nodes
+        node []node
+        // absolute offset of the entry for the next node. Position 4
+        // byte larger.
+        hoff int64
+        // front position in the node ring buffer
+        front uint32
+        // index of the root node
+        root uint32
+        // current x value
+        x uint32
+        // preallocated array
+        data []byte
+}
+
+// null represents the nonexistent index. We can't use zero because it
+// would always exist or we would need to decrease the index for each
+// reference.
+const null uint32 = 1<<32 - 1
+
+// newBinTree initializes the binTree structure. The capacity defines
+// the size of the buffer and defines the maximum distance for which
+// matches will be found.
+func newBinTree(capacity int) (t *binTree, err error) {
+        if capacity < 1 {
+                return nil, errors.New(
+                        "newBinTree: capacity must be larger than zero")
+        }
+        if int64(capacity) >= int64(null) {
+                return nil, errors.New(
+                        "newBinTree: capacity must less 2^{32}-1")
+        }
+        t = &binTree{
+                node: make([]node, capacity),
+                hoff: -int64(wordLen),
+                root: null,
+                data: make([]byte, maxMatchLen),
+        }
+        return t, nil
+}
+
+func (t *binTree) SetDict(d *encoderDict) { t.dict = d }
+
+// WriteByte writes a single byte into the binary tree.
+func (t *binTree) WriteByte(c byte) error {
+        t.x = (t.x << 8) | uint32(c)
+        t.hoff++
+        if t.hoff < 0 {
+                return nil
+        }
+        v := t.front
+        if int64(v) < t.hoff {
+                // We are overwriting old nodes stored in the tree.
+                t.remove(v)
+        }
+        t.node[v].x = t.x
+        t.add(v)
+        t.front++
+        if int64(t.front) >= int64(len(t.node)) {
+                t.front = 0
+        }
+        return nil
+}
+
+// Writes writes a sequence of bytes into the binTree structure.
+func (t *binTree) Write(p []byte) (n int, err error) {
+        for _, c := range p {
+                t.WriteByte(c)
+        }
+        return len(p), nil
+}
+
+// add puts the node v into the tree. The node must not be part of the
+// tree before.
+func (t *binTree) add(v uint32) {
+        vn := &t.node[v]
+        // Set left and right to null indices.
+        vn.l, vn.r = null, null
+        // If the binary tree is empty make v the root.
+        if t.root == null {
+                t.root = v
+                vn.p = null
+                return
+        }
+        x := vn.x
+        p := t.root
+        // Search for the right leave link and add the new node.
+        for {
+                pn := &t.node[p]
+                if x <= pn.x {
+                        if pn.l == null {
+                                pn.l = v
+                                vn.p = p
+                                return
+                        }
+                        p = pn.l
+                } else {
+                        if pn.r == null {
+                                pn.r = v
+                                vn.p = p
+                                return
+                        }
+                        p = pn.r
+                }
+        }
+}
+
+// parent returns the parent node index of v and the pointer to v value
+// in the parent.
+func (t *binTree) parent(v uint32) (p uint32, ptr *uint32) {
+        if t.root == v {
+                return null, &t.root
+        }
+        p = t.node[v].p
+        if t.node[p].l == v {
+                ptr = &t.node[p].l
+        } else {
+                ptr = &t.node[p].r
+        }
+        return
+}
+
+// Remove node v.
+func (t *binTree) remove(v uint32) {
+        vn := &t.node[v]
+        p, ptr := t.parent(v)
+        l, r := vn.l, vn.r
+        if l == null {
+                // Move the right child up.
+                *ptr = r
+                if r != null {
+                        t.node[r].p = p
+                }
+                return
+        }
+        if r == null {
+                // Move the left child up.
+                *ptr = l
+                t.node[l].p = p
+                return
+        }
+
+        // Search the in-order predecessor u.
+        un := &t.node[l]
+        ur := un.r
+        if ur == null {
+                // In order predecessor is l. Move it up.
+                un.r = r
+                t.node[r].p = l
+                un.p = p
+                *ptr = l
+                return
+        }
+        var u uint32
+        for {
+                // Look for the max value in the tree where l is root.
+                u = ur
+                ur = t.node[u].r
+                if ur == null {
+                        break
+                }
+        }
+        // replace u with ul
+        un = &t.node[u]
+        ul := un.l
+        up := un.p
+        t.node[up].r = ul
+        if ul != null {
+                t.node[ul].p = up
+        }
+
+        // replace v by u
+        un.l, un.r = l, r
+        t.node[l].p = u
+        t.node[r].p = u
+        *ptr = u
+        un.p = p
+}
+
+// search looks for the node that have the value x or for the nodes that
+// brace it. The node highest in the tree with the value x will be
+// returned. All other nodes with the same value live in left subtree of
+// the returned node.
+func (t *binTree) search(v uint32, x uint32) (a, b uint32) {
+        a, b = null, null
+        if v == null {
+                return
+        }
+        for {
+                vn := &t.node[v]
+                if x <= vn.x {
+                        if x == vn.x {
+                                return v, v
+                        }
+                        b = v
+                        if vn.l == null {
+                                return
+                        }
+                        v = vn.l
+                } else {
+                        a = v
+                        if vn.r == null {
+                                return
+                        }
+                        v = vn.r
+                }
+        }
+}
+
+// max returns the node with maximum value in the subtree with v as
+// root.
+func (t *binTree) max(v uint32) uint32 {
+        if v == null {
+                return null
+        }
+        for {
+                r := t.node[v].r
+                if r == null {
+                        return v
+                }
+                v = r
+        }
+}
+
+// min returns the node with the minimum value in the subtree with v as
+// root.
+func (t *binTree) min(v uint32) uint32 {
+        if v == null {
+                return null
+        }
+        for {
+                l := t.node[v].l
+                if l == null {
+                        return v
+                }
+                v = l
+        }
+}
+
+// pred returns the in-order predecessor of node v.
+func (t *binTree) pred(v uint32) uint32 {
+        if v == null {
+                return null
+        }
+        u := t.max(t.node[v].l)
+        if u != null {
+                return u
+        }
+        for {
+                p := t.node[v].p
+                if p == null {
+                        return null
+                }
+                if t.node[p].r == v {
+                        return p
+                }
+                v = p
+        }
+}
+
+// succ returns the in-order successor of node v.
+func (t *binTree) succ(v uint32) uint32 {
+        if v == null {
+                return null
+        }
+        u := t.min(t.node[v].r)
+        if u != null {
+                return u
+        }
+        for {
+                p := t.node[v].p
+                if p == null {
+                        return null
+                }
+                if t.node[p].l == v {
+                        return p
+                }
+                v = p
+        }
+}
+
+// xval converts the first four bytes of a into an 32-bit unsigned
+// integer in big-endian order.
+func xval(a []byte) uint32 {
+        var x uint32
+        switch len(a) {
+        default:
+                x |= uint32(a[3])
+                fallthrough
+        case 3:
+                x |= uint32(a[2]) << 8
+                fallthrough
+        case 2:
+                x |= uint32(a[1]) << 16
+                fallthrough
+        case 1:
+                x |= uint32(a[0]) << 24
+        case 0:
+        }
+        return x
+}
+
+// dumpX converts value x into a four-letter string.
+func dumpX(x uint32) string {
+        a := make([]byte, 4)
+        for i := 0; i < 4; i++ {
+                c := byte(x >> uint((3-i)*8))
+                if unicode.IsGraphic(rune(c)) {
+                        a[i] = c
+                } else {
+                        a[i] = '.'
+                }
+        }
+        return string(a)
+}
+
+// dumpNode writes a representation of the node v into the io.Writer.
+func (t *binTree) dumpNode(w io.Writer, v uint32, indent int) {
+        if v == null {
+                return
+        }
+
+        vn := &t.node[v]
+
+        t.dumpNode(w, vn.r, indent+2)
+
+        for i := 0; i < indent; i++ {
+                fmt.Fprint(w, " ")
+        }
+        if vn.p == null {
+                fmt.Fprintf(w, "node %d %q parent null\n", v, dumpX(vn.x))
+        } else {
+                fmt.Fprintf(w, "node %d %q parent %d\n", v, dumpX(vn.x), vn.p)
+        }
+
+        t.dumpNode(w, vn.l, indent+2)
+}
+
+// dump prints a representation of the binary tree into the writer.
+func (t *binTree) dump(w io.Writer) error {
+        bw := bufio.NewWriter(w)
+        t.dumpNode(bw, t.root, 0)
+        return bw.Flush()
+}
+
+func (t *binTree) distance(v uint32) int {
+        dist := int(t.front) - int(v)
+        if dist <= 0 {
+                dist += len(t.node)
+        }
+        return dist
+}
+
+type matchParams struct {
+        rep [4]uint32
+        // length when match will be accepted
+        nAccept int
+        // nodes to check
+        check int
+        // finish if length get shorter
+        stopShorter bool
+}
+
+func (t *binTree) match(m match, distIter func() (int, bool), p matchParams,
+) (r match, checked int, accepted bool) {
+        buf := &t.dict.buf
+        for {
+                if checked >= p.check {
+                        return m, checked, true
+                }
+                dist, ok := distIter()
+                if !ok {
+                        return m, checked, false
+                }
+                checked++
+                if m.n > 0 {
+                        i := buf.rear - dist + m.n - 1
+                        if i < 0 {
+                                i += len(buf.data)
+                        } else if i >= len(buf.data) {
+                                i -= len(buf.data)
+                        }
+                        if buf.data[i] != t.data[m.n-1] {
+                                if p.stopShorter {
+                                        return m, checked, false
+                                }
+                                continue
+                        }
+                }
+                n := buf.matchLen(dist, t.data)
+                switch n {
+                case 0:
+                        if p.stopShorter {
+                                return m, checked, false
+                        }
+                        continue
+                case 1:
+                        if uint32(dist-minDistance) != p.rep[0] {
+                                continue
+                        }
+                }
+                if n < m.n || (n == m.n && int64(dist) >= m.distance) {
+                        continue
+                }
+                m = match{int64(dist), n}
+                if n >= p.nAccept {
+                        return m, checked, true
+                }
+        }
+}
+
+func (t *binTree) NextOp(rep [4]uint32) operation {
+        // retrieve maxMatchLen data
+        n, _ := t.dict.buf.Peek(t.data[:maxMatchLen])
+        if n == 0 {
+                panic("no data in buffer")
+        }
+        t.data = t.data[:n]
+
+        var (
+                m                  match
+                x, u, v            uint32
+                iterPred, iterSucc func() (int, bool)
+        )
+        p := matchParams{
+                rep:     rep,
+                nAccept: maxMatchLen,
+                check:   32,
+        }
+        i := 4
+        iterSmall := func() (dist int, ok bool) {
+                i--
+                if i <= 0 {
+                        return 0, false
+                }
+                return i, true
+        }
+        m, checked, accepted := t.match(m, iterSmall, p)
+        if accepted {
+                goto end
+        }
+        p.check -= checked
+        x = xval(t.data)
+        u, v = t.search(t.root, x)
+        if u == v && len(t.data) == 4 {
+                iter := func() (dist int, ok bool) {
+                        if u == null {
+                                return 0, false
+                        }
+                        dist = t.distance(u)
+                        u, v = t.search(t.node[u].l, x)
+                        if u != v {
+                                u = null
+                        }
+                        return dist, true
+                }
+                m, _, _ = t.match(m, iter, p)
+                goto end
+        }
+        p.stopShorter = true
+        iterSucc = func() (dist int, ok bool) {
+                if v == null {
+                        return 0, false
+                }
+                dist = t.distance(v)
+                v = t.succ(v)
+                return dist, true
+        }
+        m, checked, accepted = t.match(m, iterSucc, p)
+        if accepted {
+                goto end
+        }
+        p.check -= checked
+        iterPred = func() (dist int, ok bool) {
+                if u == null {
+                        return 0, false
+                }
+                dist = t.distance(u)
+                u = t.pred(u)
+                return dist, true
+        }
+        m, _, _ = t.match(m, iterPred, p)
+end:
+        if m.n == 0 {
+                return lit{t.data[0]}
+        }
+        return m
+}