1 files changed, 146 insertions, 0 deletions
diff --git a/vendor/github.com/gobwas/glob/match/btree.go b/vendor/github.com/gobwas/glob/match/btree.go
new file mode 100644
index 0000000000..a8130e93ea
--- /dev/null
+++ b/vendor/github.com/gobwas/glob/match/btree.go
@@ -0,0 +1,146 @@
+package match
+
+import (
+	"fmt"
+	"unicode/utf8"
+)
+
+type BTree struct {
+	Value            Matcher
+	Left             Matcher
+	Right            Matcher
+	ValueLengthRunes int
+	LeftLengthRunes  int
+	RightLengthRunes int
+	LengthRunes      int
+}
+
+func NewBTree(Value, Left, Right Matcher) (tree BTree) {
+	tree.Value = Value
+	tree.Left = Left
+	tree.Right = Right
+
+	lenOk := true
+	if tree.ValueLengthRunes = Value.Len(); tree.ValueLengthRunes == -1 {
+		lenOk = false
+	}
+
+	if Left != nil {
+		if tree.LeftLengthRunes = Left.Len(); tree.LeftLengthRunes == -1 {
+			lenOk = false
+		}
+	}
+
+	if Right != nil {
+		if tree.RightLengthRunes = Right.Len(); tree.RightLengthRunes == -1 {
+			lenOk = false
+		}
+	}
+
+	if lenOk {
+		tree.LengthRunes = tree.LeftLengthRunes + tree.ValueLengthRunes + tree.RightLengthRunes
+	} else {
+		tree.LengthRunes = -1
+	}
+
+	return tree
+}
+
+func (self BTree) Len() int {
+	return self.LengthRunes
+}
+
+// todo?
+func (self BTree) Index(s string) (int, []int) {
+	return -1, nil
+}
+
+func (self BTree) Match(s string) bool {
+	inputLen := len(s)
+
+	// self.Length, self.RLen and self.LLen are values meaning the length of runes for each part
+	// here we manipulating byte length for better optimizations
+	// but these checks still works, cause minLen of 1-rune string is 1 byte.
+	if self.LengthRunes != -1 && self.LengthRunes > inputLen {
+		return false
+	}
+
+	// try to cut unnecessary parts
+	// by knowledge of length of right and left part
+	var offset, limit int
+	if self.LeftLengthRunes >= 0 {
+		offset = self.LeftLengthRunes
+	}
+	if self.RightLengthRunes >= 0 {
+		limit = inputLen - self.RightLengthRunes
+	} else {
+		limit = inputLen
+	}
+
+	for offset < limit {
+		// search for matching part in substring
+		index, segments := self.Value.Index(s[offset:limit])
+		if index == -1 {
+			releaseSegments(segments)
+			return false
+		}
+
+		l := s[:offset+index]
+		var left bool
+		if self.Left != nil {
+			left = self.Left.Match(l)
+		} else {
+			left = l == ""
+		}
+
+		if left {
+			for i := len(segments) - 1; i >= 0; i-- {
+				length := segments[i]
+
+				var right bool
+				var r string
+				// if there is no string for the right branch
+				if inputLen <= offset+index+length {
+					r = ""
+				} else {
+					r = s[offset+index+length:]
+				}
+
+				if self.Right != nil {
+					right = self.Right.Match(r)
+				} else {
+					right = r == ""
+				}
+
+				if right {
+					releaseSegments(segments)
+					return true
+				}
+			}
+		}
+
+		_, step := utf8.DecodeRuneInString(s[offset+index:])
+		offset += index + step
+
+		releaseSegments(segments)
+	}
+
+	return false
+}
+
+func (self BTree) String() string {
+	const n string = "<nil>"
+	var l, r string
+	if self.Left == nil {
+		l = n
+	} else {
+		l = self.Left.String()
+	}
+	if self.Right == nil {
+		r = n
+	} else {
+		r = self.Right.String()
+	}
+
+	return fmt.Sprintf("<btree:[%s<-%s->%s]>", l, self.Value, r)
+}