1 files changed, 654 insertions, 0 deletions

diff --git a/vendor/github.com/dlclark/regexp2/syntax/tree.go b/vendor/github.com/dlclark/regexp2/syntax/tree.go
new file mode 100644
index 0000000..ea28829
--- /dev/null
+++ b/vendor/github.com/dlclark/regexp2/syntax/tree.go
@@ -0,0 +1,654 @@
+package syntax
+
+import (
+        "bytes"
+        "fmt"
+        "math"
+        "strconv"
+)
+
+type RegexTree struct {
+        root       *regexNode
+        caps       map[int]int
+        capnumlist []int
+        captop     int
+        Capnames   map[string]int
+        Caplist    []string
+        options    RegexOptions
+}
+
+// It is built into a parsed tree for a regular expression.
+
+// Implementation notes:
+//
+// Since the node tree is a temporary data structure only used
+// during compilation of the regexp to integer codes, it's
+// designed for clarity and convenience rather than
+// space efficiency.
+//
+// RegexNodes are built into a tree, linked by the n.children list.
+// Each node also has a n.parent and n.ichild member indicating
+// its parent and which child # it is in its parent's list.
+//
+// RegexNodes come in as many types as there are constructs in
+// a regular expression, for example, "concatenate", "alternate",
+// "one", "rept", "group". There are also node types for basic
+// peephole optimizations, e.g., "onerep", "notsetrep", etc.
+//
+// Because perl 5 allows "lookback" groups that scan backwards,
+// each node also gets a "direction". Normally the value of
+// boolean n.backward = false.
+//
+// During parsing, top-level nodes are also stacked onto a parse
+// stack (a stack of trees). For this purpose we have a n.next
+// pointer. [Note that to save a few bytes, we could overload the
+// n.parent pointer instead.]
+//
+// On the parse stack, each tree has a "role" - basically, the
+// nonterminal in the grammar that the parser has currently
+// assigned to the tree. That code is stored in n.role.
+//
+// Finally, some of the different kinds of nodes have data.
+// Two integers (for the looping constructs) are stored in
+// n.operands, an an object (either a string or a set)
+// is stored in n.data
+type regexNode struct {
+        t        nodeType
+        children []*regexNode
+        str      []rune
+        set      *CharSet
+        ch       rune
+        m        int
+        n        int
+        options  RegexOptions
+        next     *regexNode
+}
+
+type nodeType int32
+
+const (
+        // The following are leaves, and correspond to primitive operations
+
+        ntOnerep      nodeType = 0  // lef,back char,min,max    a {n}
+        ntNotonerep            = 1  // lef,back char,min,max    .{n}
+        ntSetrep               = 2  // lef,back set,min,max     [\d]{n}
+        ntOneloop              = 3  // lef,back char,min,max    a {,n}
+        ntNotoneloop           = 4  // lef,back char,min,max    .{,n}
+        ntSetloop              = 5  // lef,back set,min,max     [\d]{,n}
+        ntOnelazy              = 6  // lef,back char,min,max    a {,n}?
+        ntNotonelazy           = 7  // lef,back char,min,max    .{,n}?
+        ntSetlazy              = 8  // lef,back set,min,max     [\d]{,n}?
+        ntOne                  = 9  // lef      char            a
+        ntNotone               = 10 // lef      char            [^a]
+        ntSet                  = 11 // lef      set             [a-z\s]  \w \s \d
+        ntMulti                = 12 // lef      string          abcd
+        ntRef                  = 13 // lef      group           \#
+        ntBol                  = 14 //                          ^
+        ntEol                  = 15 //                          $
+        ntBoundary             = 16 //                          \b
+        ntNonboundary          = 17 //                          \B
+        ntBeginning            = 18 //                          \A
+        ntStart                = 19 //                          \G
+        ntEndZ                 = 20 //                          \Z
+        ntEnd                  = 21 //                          \Z
+
+        // Interior nodes do not correspond to primitive operations, but
+        // control structures compositing other operations
+
+        // Concat and alternate take n children, and can run forward or backwards
+
+        ntNothing     = 22 //          []
+        ntEmpty       = 23 //          ()
+        ntAlternate   = 24 //          a|b
+        ntConcatenate = 25 //          ab
+        ntLoop        = 26 // m,x      * + ? {,}
+        ntLazyloop    = 27 // m,x      *? +? ?? {,}?
+        ntCapture     = 28 // n        ()
+        ntGroup       = 29 //          (?:)
+        ntRequire     = 30 //          (?=) (?<=)
+        ntPrevent     = 31 //          (?!) (?<!)
+        ntGreedy      = 32 //          (?>) (?<)
+        ntTestref     = 33 //          (?(n) | )
+        ntTestgroup   = 34 //          (?(...) | )
+
+        ntECMABoundary    = 41 //                          \b
+        ntNonECMABoundary = 42 //                          \B
+)
+
+func newRegexNode(t nodeType, opt RegexOptions) *regexNode {
+        return &regexNode{
+                t:       t,
+                options: opt,
+        }
+}
+
+func newRegexNodeCh(t nodeType, opt RegexOptions, ch rune) *regexNode {
+        return &regexNode{
+                t:       t,
+                options: opt,
+                ch:      ch,
+        }
+}
+
+func newRegexNodeStr(t nodeType, opt RegexOptions, str []rune) *regexNode {
+        return &regexNode{
+                t:       t,
+                options: opt,
+                str:     str,
+        }
+}
+
+func newRegexNodeSet(t nodeType, opt RegexOptions, set *CharSet) *regexNode {
+        return &regexNode{
+                t:       t,
+                options: opt,
+                set:     set,
+        }
+}
+
+func newRegexNodeM(t nodeType, opt RegexOptions, m int) *regexNode {
+        return &regexNode{
+                t:       t,
+                options: opt,
+                m:       m,
+        }
+}
+func newRegexNodeMN(t nodeType, opt RegexOptions, m, n int) *regexNode {
+        return &regexNode{
+                t:       t,
+                options: opt,
+                m:       m,
+                n:       n,
+        }
+}
+
+func (n *regexNode) writeStrToBuf(buf *bytes.Buffer) {
+        for i := 0; i < len(n.str); i++ {
+                buf.WriteRune(n.str[i])
+        }
+}
+
+func (n *regexNode) addChild(child *regexNode) {
+        reduced := child.reduce()
+        n.children = append(n.children, reduced)
+        reduced.next = n
+}
+
+func (n *regexNode) insertChildren(afterIndex int, nodes []*regexNode) {
+        newChildren := make([]*regexNode, 0, len(n.children)+len(nodes))
+        n.children = append(append(append(newChildren, n.children[:afterIndex]...), nodes...), n.children[afterIndex:]...)
+}
+
+// removes children including the start but not the end index
+func (n *regexNode) removeChildren(startIndex, endIndex int) {
+        n.children = append(n.children[:startIndex], n.children[endIndex:]...)
+}
+
+// Pass type as OneLazy or OneLoop
+func (n *regexNode) makeRep(t nodeType, min, max int) {
+        n.t += (t - ntOne)
+        n.m = min
+        n.n = max
+}
+
+func (n *regexNode) reduce() *regexNode {
+        switch n.t {
+        case ntAlternate:
+                return n.reduceAlternation()
+
+        case ntConcatenate:
+                return n.reduceConcatenation()
+
+        case ntLoop, ntLazyloop:
+                return n.reduceRep()
+
+        case ntGroup:
+                return n.reduceGroup()
+
+        case ntSet, ntSetloop:
+                return n.reduceSet()
+
+        default:
+                return n
+        }
+}
+
+// Basic optimization. Single-letter alternations can be replaced
+// by faster set specifications, and nested alternations with no
+// intervening operators can be flattened:
+//
+// a|b|c|def|g|h -> [a-c]|def|[gh]
+// apple|(?:orange|pear)|grape -> apple|orange|pear|grape
+func (n *regexNode) reduceAlternation() *regexNode {
+        if len(n.children) == 0 {
+                return newRegexNode(ntNothing, n.options)
+        }
+
+        wasLastSet := false
+        lastNodeCannotMerge := false
+        var optionsLast RegexOptions
+        var i, j int
+
+        for i, j = 0, 0; i < len(n.children); i, j = i+1, j+1 {
+                at := n.children[i]
+
+                if j < i {
+                        n.children[j] = at
+                }
+
+                for {
+                        if at.t == ntAlternate {
+                                for k := 0; k < len(at.children); k++ {
+                                        at.children[k].next = n
+                                }
+                                n.insertChildren(i+1, at.children)
+
+                                j--
+                        } else if at.t == ntSet || at.t == ntOne {
+                                // Cannot merge sets if L or I options differ, or if either are negated.
+                                optionsAt := at.options & (RightToLeft | IgnoreCase)
+
+                                if at.t == ntSet {
+                                        if !wasLastSet || optionsLast != optionsAt || lastNodeCannotMerge || !at.set.IsMergeable() {
+                                                wasLastSet = true
+                                                lastNodeCannotMerge = !at.set.IsMergeable()
+                                                optionsLast = optionsAt
+                                                break
+                                        }
+                                } else if !wasLastSet || optionsLast != optionsAt || lastNodeCannotMerge {
+                                        wasLastSet = true
+                                        lastNodeCannotMerge = false
+                                        optionsLast = optionsAt
+                                        break
+                                }
+
+                                // The last node was a Set or a One, we're a Set or One and our options are the same.
+                                // Merge the two nodes.
+                                j--
+                                prev := n.children[j]
+
+                                var prevCharClass *CharSet
+                                if prev.t == ntOne {
+                                        prevCharClass = &CharSet{}
+                                        prevCharClass.addChar(prev.ch)
+                                } else {
+                                        prevCharClass = prev.set
+                                }
+
+                                if at.t == ntOne {
+                                        prevCharClass.addChar(at.ch)
+                                } else {
+                                        prevCharClass.addSet(*at.set)
+                                }
+
+                                prev.t = ntSet
+                                prev.set = prevCharClass
+                        } else if at.t == ntNothing {
+                                j--
+                        } else {
+                                wasLastSet = false
+                                lastNodeCannotMerge = false
+                        }
+                        break
+                }
+        }
+
+        if j < i {
+                n.removeChildren(j, i)
+        }
+
+        return n.stripEnation(ntNothing)
+}
+
+// Basic optimization. Adjacent strings can be concatenated.
+//
+// (?:abc)(?:def) -> abcdef
+func (n *regexNode) reduceConcatenation() *regexNode {
+        // Eliminate empties and concat adjacent strings/chars
+
+        var optionsLast RegexOptions
+        var optionsAt RegexOptions
+        var i, j int
+
+        if len(n.children) == 0 {
+                return newRegexNode(ntEmpty, n.options)
+        }
+
+        wasLastString := false
+
+        for i, j = 0, 0; i < len(n.children); i, j = i+1, j+1 {
+                var at, prev *regexNode
+
+                at = n.children[i]
+
+                if j < i {
+                        n.children[j] = at
+                }
+
+                if at.t == ntConcatenate &&
+                        ((at.options & RightToLeft) == (n.options & RightToLeft)) {
+                        for k := 0; k < len(at.children); k++ {
+                                at.children[k].next = n
+                        }
+
+                        //insert at.children at i+1 index in n.children
+                        n.insertChildren(i+1, at.children)
+
+                        j--
+                } else if at.t == ntMulti || at.t == ntOne {
+                        // Cannot merge strings if L or I options differ
+                        optionsAt = at.options & (RightToLeft | IgnoreCase)
+
+                        if !wasLastString || optionsLast != optionsAt {
+                                wasLastString = true
+                                optionsLast = optionsAt
+                                continue
+                        }
+
+                        j--
+                        prev = n.children[j]
+
+                        if prev.t == ntOne {
+                                prev.t = ntMulti
+                                prev.str = []rune{prev.ch}
+                        }
+
+                        if (optionsAt & RightToLeft) == 0 {
+                                if at.t == ntOne {
+                                        prev.str = append(prev.str, at.ch)
+                                } else {
+                                        prev.str = append(prev.str, at.str...)
+                                }
+                        } else {
+                                if at.t == ntOne {
+                                        // insert at the front by expanding our slice, copying the data over, and then setting the value
+                                        prev.str = append(prev.str, 0)
+                                        copy(prev.str[1:], prev.str)
+                                        prev.str[0] = at.ch
+                                } else {
+                                        //insert at the front...this one we'll make a new slice and copy both into it
+                                        merge := make([]rune, len(prev.str)+len(at.str))
+                                        copy(merge, at.str)
+                                        copy(merge[len(at.str):], prev.str)
+                                        prev.str = merge
+                                }
+                        }
+                } else if at.t == ntEmpty {
+                        j--
+                } else {
+                        wasLastString = false
+                }
+        }
+
+        if j < i {
+                // remove indices j through i from the children
+                n.removeChildren(j, i)
+        }
+
+        return n.stripEnation(ntEmpty)
+}
+
+// Nested repeaters just get multiplied with each other if they're not
+// too lumpy
+func (n *regexNode) reduceRep() *regexNode {
+
+        u := n
+        t := n.t
+        min := n.m
+        max := n.n
+
+        for {
+                if len(u.children) == 0 {
+                        break
+                }
+
+                child := u.children[0]
+
+                // multiply reps of the same type only
+                if child.t != t {
+                        childType := child.t
+
+                        if !(childType >= ntOneloop && childType <= ntSetloop && t == ntLoop ||
+                                childType >= ntOnelazy && childType <= ntSetlazy && t == ntLazyloop) {
+                                break
+                        }
+                }
+
+                // child can be too lumpy to blur, e.g., (a {100,105}) {3} or (a {2,})?
+                // [but things like (a {2,})+ are not too lumpy...]
+                if u.m == 0 && child.m > 1 || child.n < child.m*2 {
+                        break
+                }
+
+                u = child
+                if u.m > 0 {
+                        if (math.MaxInt32-1)/u.m < min {
+                                u.m = math.MaxInt32
+                        } else {
+                                u.m = u.m * min
+                        }
+                }
+                if u.n > 0 {
+                        if (math.MaxInt32-1)/u.n < max {
+                                u.n = math.MaxInt32
+                        } else {
+                                u.n = u.n * max
+                        }
+                }
+        }
+
+        if math.MaxInt32 == min {
+                return newRegexNode(ntNothing, n.options)
+        }
+        return u
+
+}
+
+// Simple optimization. If a concatenation or alternation has only
+// one child strip out the intermediate node. If it has zero children,
+// turn it into an empty.
+func (n *regexNode) stripEnation(emptyType nodeType) *regexNode {
+        switch len(n.children) {
+        case 0:
+                return newRegexNode(emptyType, n.options)
+        case 1:
+                return n.children[0]
+        default:
+                return n
+        }
+}
+
+func (n *regexNode) reduceGroup() *regexNode {
+        u := n
+
+        for u.t == ntGroup {
+                u = u.children[0]
+        }
+
+        return u
+}
+
+// Simple optimization. If a set is a singleton, an inverse singleton,
+// or empty, it's transformed accordingly.
+func (n *regexNode) reduceSet() *regexNode {
+        // Extract empty-set, one and not-one case as special
+
+        if n.set == nil {
+                n.t = ntNothing
+        } else if n.set.IsSingleton() {
+                n.ch = n.set.SingletonChar()
+                n.set = nil
+                n.t += (ntOne - ntSet)
+        } else if n.set.IsSingletonInverse() {
+                n.ch = n.set.SingletonChar()
+                n.set = nil
+                n.t += (ntNotone - ntSet)
+        }
+
+        return n
+}
+
+func (n *regexNode) reverseLeft() *regexNode {
+        if n.options&RightToLeft != 0 && n.t == ntConcatenate && len(n.children) > 0 {
+                //reverse children order
+                for left, right := 0, len(n.children)-1; left < right; left, right = left+1, right-1 {
+                        n.children[left], n.children[right] = n.children[right], n.children[left]
+                }
+        }
+
+        return n
+}
+
+func (n *regexNode) makeQuantifier(lazy bool, min, max int) *regexNode {
+        if min == 0 && max == 0 {
+                return newRegexNode(ntEmpty, n.options)
+        }
+
+        if min == 1 && max == 1 {
+                return n
+        }
+
+        switch n.t {
+        case ntOne, ntNotone, ntSet:
+                if lazy {
+                        n.makeRep(Onelazy, min, max)
+                } else {
+                        n.makeRep(Oneloop, min, max)
+                }
+                return n
+
+        default:
+                var t nodeType
+                if lazy {
+                        t = ntLazyloop
+                } else {
+                        t = ntLoop
+                }
+                result := newRegexNodeMN(t, n.options, min, max)
+                result.addChild(n)
+                return result
+        }
+}
+
+// debug functions
+
+var typeStr = []string{
+        "Onerep", "Notonerep", "Setrep",
+        "Oneloop", "Notoneloop", "Setloop",
+        "Onelazy", "Notonelazy", "Setlazy",
+        "One", "Notone", "Set",
+        "Multi", "Ref",
+        "Bol", "Eol", "Boundary", "Nonboundary",
+        "Beginning", "Start", "EndZ", "End",
+        "Nothing", "Empty",
+        "Alternate", "Concatenate",
+        "Loop", "Lazyloop",
+        "Capture", "Group", "Require", "Prevent", "Greedy",
+        "Testref", "Testgroup",
+        "Unknown", "Unknown", "Unknown",
+        "Unknown", "Unknown", "Unknown",
+        "ECMABoundary", "NonECMABoundary",
+}
+
+func (n *regexNode) description() string {
+        buf := &bytes.Buffer{}
+
+        buf.WriteString(typeStr[n.t])
+
+        if (n.options & ExplicitCapture) != 0 {
+                buf.WriteString("-C")
+        }
+        if (n.options & IgnoreCase) != 0 {
+                buf.WriteString("-I")
+        }
+        if (n.options & RightToLeft) != 0 {
+                buf.WriteString("-L")
+        }
+        if (n.options & Multiline) != 0 {
+                buf.WriteString("-M")
+        }
+        if (n.options & Singleline) != 0 {
+                buf.WriteString("-S")
+        }
+        if (n.options & IgnorePatternWhitespace) != 0 {
+                buf.WriteString("-X")
+        }
+        if (n.options & ECMAScript) != 0 {
+                buf.WriteString("-E")
+        }
+
+        switch n.t {
+        case ntOneloop, ntNotoneloop, ntOnelazy, ntNotonelazy, ntOne, ntNotone:
+                buf.WriteString("(Ch = " + CharDescription(n.ch) + ")")
+                break
+        case ntCapture:
+                buf.WriteString("(index = " + strconv.Itoa(n.m) + ", unindex = " + strconv.Itoa(n.n) + ")")
+                break
+        case ntRef, ntTestref:
+                buf.WriteString("(index = " + strconv.Itoa(n.m) + ")")
+                break
+        case ntMulti:
+                fmt.Fprintf(buf, "(String = %s)", string(n.str))
+                break
+        case ntSet, ntSetloop, ntSetlazy:
+                buf.WriteString("(Set = " + n.set.String() + ")")
+                break
+        }
+
+        switch n.t {
+        case ntOneloop, ntNotoneloop, ntOnelazy, ntNotonelazy, ntSetloop, ntSetlazy, ntLoop, ntLazyloop:
+                buf.WriteString("(Min = ")
+                buf.WriteString(strconv.Itoa(n.m))
+                buf.WriteString(", Max = ")
+                if n.n == math.MaxInt32 {
+                        buf.WriteString("inf")
+                } else {
+                        buf.WriteString(strconv.Itoa(n.n))
+                }
+                buf.WriteString(")")
+
+                break
+        }
+
+        return buf.String()
+}
+
+var padSpace = []byte("                                ")
+
+func (t *RegexTree) Dump() string {
+        return t.root.dump()
+}
+
+func (n *regexNode) dump() string {
+        var stack []int
+        CurNode := n
+        CurChild := 0
+
+        buf := bytes.NewBufferString(CurNode.description())
+        buf.WriteRune('\n')
+
+        for {
+                if CurNode.children != nil && CurChild < len(CurNode.children) {
+                        stack = append(stack, CurChild+1)
+                        CurNode = CurNode.children[CurChild]
+                        CurChild = 0
+
+                        Depth := len(stack)
+                        if Depth > 32 {
+                                Depth = 32
+                        }
+                        buf.Write(padSpace[:Depth])
+                        buf.WriteString(CurNode.description())
+                        buf.WriteRune('\n')
+                } else {
+                        if len(stack) == 0 {
+                                break
+                        }
+
+                        CurChild = stack[len(stack)-1]
+                        stack = stack[:len(stack)-1]
+                        CurNode = CurNode.next
+                }
+        }
+        return buf.String()
+}