diff options
Diffstat (limited to 'vendor/github.com/mattermost/rsc/regexp')
7 files changed, 0 insertions, 1379 deletions
diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/copy.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/copy.go deleted file mode 100644 index 4e723260b..000000000 --- a/vendor/github.com/mattermost/rsc/regexp/regmerge/copy.go +++ /dev/null @@ -1,225 +0,0 @@ -// Copyright 2011 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Copied from code.google.com/p/codesearch/regexp/copy.go. - -// Copied from Go's regexp/syntax. -// Formatters edited to handle instByteRange. - -package main - -import ( - "bytes" - "fmt" - "regexp/syntax" - "sort" - "strconv" - "unicode" -) - -// cleanClass sorts the ranges (pairs of elements of r), -// merges them, and eliminates duplicates. -func cleanClass(rp *[]rune) []rune { - - // Sort by lo increasing, hi decreasing to break ties. - sort.Sort(ranges{rp}) - - r := *rp - if len(r) < 2 { - return r - } - - // Merge abutting, overlapping. - w := 2 // write index - for i := 2; i < len(r); i += 2 { - lo, hi := r[i], r[i+1] - if lo <= r[w-1]+1 { - // merge with previous range - if hi > r[w-1] { - r[w-1] = hi - } - continue - } - // new disjoint range - r[w] = lo - r[w+1] = hi - w += 2 - } - - return r[:w] -} - -// appendRange returns the result of appending the range lo-hi to the class r. -func appendRange(r []rune, lo, hi rune) []rune { - // Expand last range or next to last range if it overlaps or abuts. - // Checking two ranges helps when appending case-folded - // alphabets, so that one range can be expanding A-Z and the - // other expanding a-z. - n := len(r) - for i := 2; i <= 4; i += 2 { // twice, using i=2, i=4 - if n >= i { - rlo, rhi := r[n-i], r[n-i+1] - if lo <= rhi+1 && rlo <= hi+1 { - if lo < rlo { - r[n-i] = lo - } - if hi > rhi { - r[n-i+1] = hi - } - return r - } - } - } - - return append(r, lo, hi) -} - -const ( - // minimum and maximum runes involved in folding. - // checked during test. - minFold = 0x0041 - maxFold = 0x1044f -) - -// appendFoldedRange returns the result of appending the range lo-hi -// and its case folding-equivalent runes to the class r. -func appendFoldedRange(r []rune, lo, hi rune) []rune { - // Optimizations. - if lo <= minFold && hi >= maxFold { - // Range is full: folding can't add more. - return appendRange(r, lo, hi) - } - if hi < minFold || lo > maxFold { - // Range is outside folding possibilities. - return appendRange(r, lo, hi) - } - if lo < minFold { - // [lo, minFold-1] needs no folding. - r = appendRange(r, lo, minFold-1) - lo = minFold - } - if hi > maxFold { - // [maxFold+1, hi] needs no folding. - r = appendRange(r, maxFold+1, hi) - hi = maxFold - } - - // Brute force. Depend on appendRange to coalesce ranges on the fly. - for c := lo; c <= hi; c++ { - r = appendRange(r, c, c) - f := unicode.SimpleFold(c) - for f != c { - r = appendRange(r, f, f) - f = unicode.SimpleFold(f) - } - } - return r -} - -// ranges implements sort.Interface on a []rune. -// The choice of receiver type definition is strange -// but avoids an allocation since we already have -// a *[]rune. -type ranges struct { - p *[]rune -} - -func (ra ranges) Less(i, j int) bool { - p := *ra.p - i *= 2 - j *= 2 - return p[i] < p[j] || p[i] == p[j] && p[i+1] > p[j+1] -} - -func (ra ranges) Len() int { - return len(*ra.p) / 2 -} - -func (ra ranges) Swap(i, j int) { - p := *ra.p - i *= 2 - j *= 2 - p[i], p[i+1], p[j], p[j+1] = p[j], p[j+1], p[i], p[i+1] -} - -func progString(p *syntax.Prog) string { - var b bytes.Buffer - dumpProg(&b, p) - return b.String() -} - -func instString(i *syntax.Inst) string { - var b bytes.Buffer - dumpInst(&b, i) - return b.String() -} - -func bw(b *bytes.Buffer, args ...string) { - for _, s := range args { - b.WriteString(s) - } -} - -func dumpProg(b *bytes.Buffer, p *syntax.Prog) { - for j := range p.Inst { - i := &p.Inst[j] - pc := strconv.Itoa(j) - if len(pc) < 3 { - b.WriteString(" "[len(pc):]) - } - if j == p.Start { - pc += "*" - } - bw(b, pc, "\t") - dumpInst(b, i) - bw(b, "\n") - } -} - -func u32(i uint32) string { - return strconv.FormatUint(uint64(i), 10) -} - -func dumpInst(b *bytes.Buffer, i *syntax.Inst) { - switch i.Op { - case syntax.InstAlt: - bw(b, "alt -> ", u32(i.Out), ", ", u32(i.Arg)) - case syntax.InstAltMatch: - bw(b, "altmatch -> ", u32(i.Out), ", ", u32(i.Arg)) - case syntax.InstCapture: - bw(b, "cap ", u32(i.Arg), " -> ", u32(i.Out)) - case syntax.InstEmptyWidth: - bw(b, "empty ", u32(i.Arg), " -> ", u32(i.Out)) - case syntax.InstMatch: - bw(b, "match") - case syntax.InstFail: - bw(b, "fail") - case syntax.InstNop: - bw(b, "nop -> ", u32(i.Out)) - case instByteRange: - fmt.Fprintf(b, "byte %02x-%02x", (i.Arg>>8)&0xFF, i.Arg&0xFF) - if i.Arg&argFold != 0 { - bw(b, "/i") - } - bw(b, " -> ", u32(i.Out)) - - // Should not happen - case syntax.InstRune: - if i.Rune == nil { - // shouldn't happen - bw(b, "rune <nil>") - } - bw(b, "rune ", strconv.QuoteToASCII(string(i.Rune))) - if syntax.Flags(i.Arg)&syntax.FoldCase != 0 { - bw(b, "/i") - } - bw(b, " -> ", u32(i.Out)) - case syntax.InstRune1: - bw(b, "rune1 ", strconv.QuoteToASCII(string(i.Rune)), " -> ", u32(i.Out)) - case syntax.InstRuneAny: - bw(b, "any -> ", u32(i.Out)) - case syntax.InstRuneAnyNotNL: - bw(b, "anynotnl -> ", u32(i.Out)) - } -} diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/main.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/main.go deleted file mode 100644 index 672337a04..000000000 --- a/vendor/github.com/mattermost/rsc/regexp/regmerge/main.go +++ /dev/null @@ -1,96 +0,0 @@ -// Copyright 2012 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -package main - -import ( - "flag" - "fmt" - "log" - "os" - "regexp/syntax" - "runtime/pprof" -) - -var maxState = flag.Int("m", 1e5, "maximum number of states to explore") -var cpuprof = flag.String("cpuprofile", "", "cpu profile file") - -func main() { - flag.Usage = func() { - fmt.Fprintf(os.Stderr, "usage: regmerge [-m maxstate] regexp [regexp2 regexp3....]\n") - os.Exit(2) - } - flag.Parse() - - if len(flag.Args()) < 1 { - flag.Usage() - } - - os.Exit(run(flag.Args())) -} - -func run(args []string) int { - if *cpuprof != "" { - f, err := os.Create(*cpuprof) - if err != nil { - log.Fatal(err) - } - pprof.StartCPUProfile(f) - defer pprof.StopCPUProfile() - } - - m, err := compile(flag.Args()...) - if err != nil { - log.Fatal(err) - } - n := 100 - for ;; n *= 2 { - if n >= *maxState { - if n >= 2* *maxState { - fmt.Printf("reached state limit\n") - return 1 - } - n = *maxState - } - log.Printf("try %d states...\n", n) - s, err := m.findMatch(n) - if err == nil { - fmt.Printf("%q\n", s) - return 0 - } - if err != ErrMemory { - fmt.Printf("failed: %s\n", err) - return 3 - } - } - panic("unreachable") -} - -func compile(exprs ...string) (*matcher, error) { - var progs []*syntax.Prog - for _, expr := range exprs { - re, err := syntax.Parse(expr, syntax.Perl) - if err != nil { - return nil, err - } - sre := re.Simplify() - prog, err := syntax.Compile(sre) - if err != nil { - return nil, err - } - if err := toByteProg(prog); err != nil { - return nil, err - } - progs = append(progs, prog) - } - m := &matcher{} - if err := m.init(joinProgs(progs), len(progs)); err != nil { - return nil, err - } - return m, nil -} - -func bug() { - panic("regmerge: internal error") -} diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/match.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/match.go deleted file mode 100644 index 6a4b1f967..000000000 --- a/vendor/github.com/mattermost/rsc/regexp/regmerge/match.go +++ /dev/null @@ -1,406 +0,0 @@ -// Copyright 2011 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Copied from code.google.com/p/codesearch/regexp/copy.go -// and adapted for the problem of finding a matching string, not -// testing whether a particular string matches. - -package main - -import ( - "encoding/binary" - "errors" - "fmt" - "hash/fnv" - "hash" - "log" - "regexp/syntax" -) - -// A matcher holds the state for running regular expression search. -type matcher struct { - buf []byte - prog *syntax.Prog // compiled program - dstate map[uint32]*dstate // dstate cache - start *dstate // start state - startLine *dstate // start state for beginning of line - z1, z2, z3 nstate // three temporary nstates - ids []int - numState int - maxState int - numByte int - numMatch int - undo [256]byte - all *dstate - allTail **dstate - h hash.Hash32 -} - -// An nstate corresponds to an NFA state. -type nstate struct { - q Set // queue of program instructions - flag flags // flags (TODO) - needFlag syntax.EmptyOp -} - -// The flags record state about a position between bytes in the text. -type flags uint32 - -const ( - flagBOL flags = 1 << iota // beginning of line - flagEOL // end of line - flagBOT // beginning of text - flagEOT // end of text - flagWord // last byte was word byte -) - -// A dstate corresponds to a DFA state. -type dstate struct { - enc string // encoded nstate - nextAll *dstate - nextHash *dstate - prev *dstate - prevByte int - done bool -} - -func (z *nstate) String() string { - return fmt.Sprintf("%v/%#x+%#x", z.q.Dense(), z.flag, z.needFlag) -} - -// enc encodes z as a string. -func (m *matcher) enc(z *nstate) []byte { - buf := m.buf[:0] - buf = append(buf, byte(z.needFlag), byte(z.flag)) - ids := m.ids[:0] - for _, id := range z.q.Dense() { - ids = append(ids, int(id)) - } - sortInts(ids) - last := ^uint32(0) - for _, id := range ids { - x := uint32(id)-last - last = uint32(id) - for x >= 0x80 { - buf = append(buf, byte(x)|0x80) - x >>= 7 - } - buf = append(buf, byte(x)) - } - m.buf = buf - return buf -} - -// dec decodes the encoding s into z. -func (m *matcher) dec(z *nstate, s string) { - b := append(m.buf[:0], s...) - m.buf = b - z.needFlag = syntax.EmptyOp(b[0]) - b = b[1:] - i, n := binary.Uvarint(b) - if n <= 0 { - bug() - } - b = b[n:] - z.flag = flags(i) - z.q.Reset() - last := ^uint32(0) - for len(b) > 0 { - i, n = binary.Uvarint(b) - if n <= 0 { - bug() - } - b = b[n:] - last += uint32(i) - z.q.Add(last, 0, 0) - } -} - -// init initializes the matcher. -func (m *matcher) init(prog *syntax.Prog, n int) error { - m.prog = prog - m.dstate = make(map[uint32]*dstate) - m.numMatch = n - m.maxState = 10 - m.allTail = &m.all - m.numByte = 256 - for i := range m.undo { - m.undo[i] = byte(i) - } - m.h = fnv.New32() - - m.z1.q.Init(uint32(len(prog.Inst))) - m.z2.q.Init(uint32(len(prog.Inst))) - m.z3.q.Init(uint32(len(prog.Inst))) - m.ids = make([]int, 0, len(prog.Inst)) - - m.addq(&m.z1.q, uint32(prog.Start), syntax.EmptyBeginLine|syntax.EmptyBeginText) - m.z1.flag = flagBOL | flagBOT - m.start = m.cache(&m.z1, nil, 0) - - m.z1.q.Reset() - m.addq(&m.z1.q, uint32(prog.Start), syntax.EmptyBeginLine) - m.z1.flag = flagBOL - m.startLine = m.cache(&m.z1, nil, 0) - - m.crunchProg() - - return nil -} - -// stepEmpty steps runq to nextq expanding according to flag. -func (m *matcher) stepEmpty(runq, nextq *Set, flag syntax.EmptyOp) { - nextq.Reset() - for _, id := range runq.Dense() { - m.addq(nextq, id, flag) - } -} - -// stepByte steps runq to nextq consuming c and then expanding according to flag. -// It returns true if a match ends immediately before c. -// c is either an input byte or endText. -func (m *matcher) stepByte(runq, nextq *Set, c int, flag syntax.EmptyOp) (match bool) { - nextq.Reset() - m.addq(nextq, uint32(m.prog.Start), flag) - - nmatch := 0 - for _, id := range runq.Dense() { - i := &m.prog.Inst[id] - switch i.Op { - default: - continue - case syntax.InstMatch: - nmatch++ - continue - case instByteRange: - if c == endText { - break - } - lo := int((i.Arg >> 8) & 0xFF) - hi := int(i.Arg & 0xFF) - if i.Arg&argFold != 0 && 'a' <= c && c <= 'z' { - c += 'A' - 'a' - } - if lo <= c && c <= hi { - m.addq(nextq, i.Out, flag) - } - } - } - return nmatch == m.numMatch -} - -// addq adds id to the queue, expanding according to flag. -func (m *matcher) addq(q *Set, id uint32, flag syntax.EmptyOp) { - if q.Has(id, 0) { - return - } - q.MustAdd(id) - i := &m.prog.Inst[id] - switch i.Op { - case syntax.InstCapture, syntax.InstNop: - m.addq(q, i.Out, flag) - case syntax.InstAlt, syntax.InstAltMatch: - m.addq(q, i.Out, flag) - m.addq(q, i.Arg, flag) - case syntax.InstEmptyWidth: - if syntax.EmptyOp(i.Arg)&^flag == 0 { - m.addq(q, i.Out, flag) - } - } -} - -const endText = -1 - -// computeNext computes the next DFA state if we're in d reading c (an input byte or endText). -func (m *matcher) computeNext(this, next *nstate, d *dstate, c int) bool { - // compute flags in effect before c - flag := syntax.EmptyOp(0) - if this.flag&flagBOL != 0 { - flag |= syntax.EmptyBeginLine - } - if this.flag&flagBOT != 0 { - flag |= syntax.EmptyBeginText - } - if this.flag&flagWord != 0 { - if !isWordByte(c) { - flag |= syntax.EmptyWordBoundary - } else { - flag |= syntax.EmptyNoWordBoundary - } - } else { - if isWordByte(c) { - flag |= syntax.EmptyWordBoundary - } else { - flag |= syntax.EmptyNoWordBoundary - } - } - if c == '\n' { - flag |= syntax.EmptyEndLine - } - if c == endText { - flag |= syntax.EmptyEndLine | syntax.EmptyEndText - } - - if flag &= this.needFlag; flag != 0 { - // re-expand queue using new flags. - // TODO: only do this when it matters - // (something is gating on word boundaries). - m.stepEmpty(&this.q, &next.q, flag) - this, next = next, &m.z3 - } - - // now compute flags after c. - flag = 0 - next.flag = 0 - if c == '\n' { - flag |= syntax.EmptyBeginLine - next.flag |= flagBOL - } - if isWordByte(c) { - next.flag |= flagWord - } - - // re-add start, process rune + expand according to flags. - if m.stepByte(&this.q, &next.q, c, flag) { - return true - } - next.needFlag = m.queueFlag(&next.q) - if next.needFlag&syntax.EmptyBeginLine == 0 { - next.flag &^= flagBOL - } - if next.needFlag&(syntax.EmptyWordBoundary|syntax.EmptyNoWordBoundary) == 0{ - next.flag &^= flagWord - } - - m.cache(next, d, c) - return false -} - -func (m *matcher) queueFlag(runq *Set) syntax.EmptyOp { - var e uint32 - for _, id := range runq.Dense() { - i := &m.prog.Inst[id] - if i.Op == syntax.InstEmptyWidth { - e |= i.Arg - } - } - return syntax.EmptyOp(e) -} - -func (m *matcher) hash(enc []byte) uint32 { - m.h.Reset() - m.h.Write(enc) - return m.h.Sum32() -} - -func (m *matcher) find(h uint32, enc []byte) *dstate { -Search: - for d := m.dstate[h]; d!=nil; d=d.nextHash { - s := d.enc - if len(s) != len(enc) { - continue Search - } - for i, b := range enc { - if s[i] != b { - continue Search - } - } - return d - } - return nil -} - -func (m *matcher) cache(z *nstate, prev *dstate, prevByte int) *dstate { - enc := m.enc(z) - h := m.hash(enc) - d := m.find(h, enc) - if d != nil { - return d - } - - if m.numState >= m.maxState { - panic(ErrMemory) - } - m.numState++ - d = &dstate{ - enc: string(enc), - prev: prev, - prevByte: prevByte, - nextHash: m.dstate[h], - } - m.dstate[h] = d - *m.allTail = d - m.allTail = &d.nextAll - - return d -} - -// isWordByte reports whether the byte c is a word character: ASCII only. -// This is used to implement \b and \B. This is not right for Unicode, but: -// - it's hard to get right in a byte-at-a-time matching world -// (the DFA has only one-byte lookahead) -// - this crude approximation is the same one PCRE uses -func isWordByte(c int) bool { - return 'A' <= c && c <= 'Z' || - 'a' <= c && c <= 'z' || - '0' <= c && c <= '9' || - c == '_' -} - -var ErrNoMatch = errors.New("no matching strings") -var ErrMemory = errors.New("exhausted memory") - -func (m *matcher) findMatch(maxState int) (s string, err error) { - defer func() { - switch r := recover().(type) { - case nil: - return - case error: - err = r - return - default: - panic(r) - } - }() - - m.maxState = maxState - numState := 0 - var d *dstate - var c int - for d = m.all; d != nil; d = d.nextAll { - numState++ - if d.done { - continue - } - this, next := &m.z1, &m.z2 - m.dec(this, d.enc) - if m.computeNext(this, next, d, endText) { - c = endText - goto Found - } - for _, cb := range m.undo[:m.numByte] { - if m.computeNext(this, next, d, int(cb)) { - c = int(cb) - goto Found - } - } - d.done = true - } - log.Printf("searched %d states; queued %d states", numState, m.numState) - return "", ErrNoMatch - -Found: - var buf []byte - if c >= 0 { - buf = append(buf, byte(c)) - } - for d1 := d; d1.prev != nil; d1= d1.prev { - buf = append(buf, byte(d1.prevByte)) - } - for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 { - buf[i], buf[j] = buf[j], buf[i] - } - log.Printf("searched %d states; queued %d states", numState, m.numState) - return string(buf), nil -} diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/merge.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/merge.go deleted file mode 100644 index 15f51cfa7..000000000 --- a/vendor/github.com/mattermost/rsc/regexp/regmerge/merge.go +++ /dev/null @@ -1,103 +0,0 @@ -// Copyright 2011 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Code to merge (join) multiple regexp progs into a single prog. -// New code; not copied from anywhere. - -package main - -import "regexp/syntax" - -func joinProgs(progs []*syntax.Prog) *syntax.Prog { - all := &syntax.Prog{} - for i, p := range progs { - n := len(all.Inst) - all.Inst = append(all.Inst, p.Inst...) - match := shiftInst(all.Inst[n:], n) - if match < 0 { - // no match instruction; give up - all.Inst = []syntax.Inst{{Op: syntax.InstFail}} - all.Start = 0 - return all - } - match += n - m := len(all.Inst) - all.Inst = append(all.Inst, - syntax.Inst{Op: syntax.InstAlt, Out: uint32(p.Start+n), Arg: uint32(m+1)}, - syntax.Inst{Op: instByteRange, Arg: 0x00FF, Out: uint32(m)}, - syntax.Inst{Op: instByteRange, Arg: 0x00FF, Out: uint32(match)}, - syntax.Inst{Op: syntax.InstMatch}, - ) - all.Inst[match] = syntax.Inst{Op: syntax.InstAlt, Out: uint32(m+2), Arg: uint32(m+3)} - - if i == 0 { - all.Start = m - } else { - old := all.Start - all.Start = len(all.Inst) - all.Inst = append(all.Inst, syntax.Inst{Op: syntax.InstAlt, Out: uint32(old), Arg: uint32(m)}) - } - } - - return all -} - -func shiftInst(inst []syntax.Inst, n int) int { - match := -1 - for i := range inst { - ip := &inst[i] - ip.Out += uint32(n) - if ip.Op == syntax.InstMatch { - if match >= 0 { - panic("double match") - } - match = i - } - if ip.Op == syntax.InstAlt || ip.Op == syntax.InstAltMatch { - ip.Arg += uint32(n) - } - } - return match -} - -func (m *matcher) crunchProg() { - var rewrite [256]byte - - for i := range m.prog.Inst { - ip := &m.prog.Inst[i] - switch ip.Op { - case instByteRange: - lo, hi := byte(ip.Arg>>8), byte(ip.Arg) - rewrite[lo] = 1 - if hi < 255 { - rewrite[hi+1] = 1 - } - case syntax.InstEmptyWidth: - switch op := syntax.EmptyOp(ip.Arg); { - case op&(syntax.EmptyBeginLine|syntax.EmptyEndLine) != 0: - rewrite['\n'] = 1 - rewrite['\n'+1] = 1 - case op&(syntax.EmptyWordBoundary|syntax.EmptyNoWordBoundary) != 0: - rewrite['A'] = 1 - rewrite['Z'+1] = 1 - rewrite['a'] = 1 - rewrite['z'+1] = 1 - rewrite['0'] = 1 - rewrite['9'+1] = 1 - rewrite['_'] = 1 - rewrite['_'+1] = 1 - } - } - } - - rewrite[0] = 0 - for i := 1; i < 256; i++ { - rewrite[i] += rewrite[i-1] - } - m.numByte = int(rewrite[255]) + 1 - - for i := 255; i >= 0; i-- { - m.undo[rewrite[i]] = byte(i) - } -} diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/sort.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/sort.go deleted file mode 100644 index e40f87714..000000000 --- a/vendor/github.com/mattermost/rsc/regexp/regmerge/sort.go +++ /dev/null @@ -1,199 +0,0 @@ -// Copyright 2012 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Copy of go/src/pkg/sort/sort.go, specialized for []int -// and to remove some array indexing. - -package main - -func min(a, b int) int { - if a < b { - return a - } - return b -} - -// Insertion sort -func insertionSort(data []int, a, b int) { - for i := a + 1; i < b; i++ { - for j := i; j > a && data[j] < data[j-1]; j-- { - data[j], data[j-1] = data[j-1], data[j] - } - } -} - -// siftDown implements the heap property on data[lo, hi). -// first is an offset into the array where the root of the heap lies. -func siftDown(data []int, lo, hi, first int) { - root := lo - for { - child := 2*root + 1 - if child >= hi { - break - } - if child+1 < hi && data[first+child] < data[first+child+1] { - child++ - } - if !(data[first+root] < data[first+child]) { - return - } - data[first+root], data[first+child] = data[first+child], data[first+root] - root = child - } -} - -func heapSort(data []int, a, b int) { - first := a - lo := 0 - hi := b - a - - // Build heap with greatest element at top. - for i := (hi - 1) / 2; i >= 0; i-- { - siftDown(data, i, hi, first) - } - - // Pop elements, largest first, into end of data. - for i := hi - 1; i >= 0; i-- { - data[first], data[first+i] = data[first+i], data[first] - siftDown(data, lo, i, first) - } -} - -// Quicksort, following Bentley and McIlroy, -// ``Engineering a Sort Function,'' SP&E November 1993. - -// medianOfThree moves the median of the three values data[a], data[b], data[c] into data[a]. -func medianOfThree(data []int, a, b, c int) { - m0 := b - m1 := a - m2 := c - // bubble sort on 3 elements - if data[m1] < data[m0] { - data[m1], data[m0] = data[m0], data[m1] - } - if data[m2] < data[m1] { - data[m2], data[m1] = data[m1], data[m2] - } - if data[m1] < data[m0] { - data[m1], data[m0] = data[m0], data[m1] - } - // now data[m0] <= data[m1] <= data[m2] -} - -func swapRange(data []int, a, b, n int) { - for i := 0; i < n; i++ { - data[a+i], data[b+i] = data[b+i], data[a+i] - } -} - -func doPivot(data []int, lo, hi int) (midlo, midhi int) { - m := lo + (hi-lo)/2 // Written like this to avoid integer overflow. - if hi-lo > 40 { - // Tukey's ``Ninther,'' median of three medians of three. - s := (hi - lo) / 8 - medianOfThree(data, lo, lo+s, lo+2*s) - medianOfThree(data, m, m-s, m+s) - medianOfThree(data, hi-1, hi-1-s, hi-1-2*s) - } - medianOfThree(data, lo, m, hi-1) - - // Invariants are: - // data[lo] = pivot (set up by ChoosePivot) - // data[lo <= i < a] = pivot - // data[a <= i < b] < pivot - // data[b <= i < c] is unexamined - // data[c <= i < d] > pivot - // data[d <= i < hi] = pivot - // - // Once b meets c, can swap the "= pivot" sections - // into the middle of the slice. - pivot := lo - a, b, c, d := lo+1, lo+1, hi, hi - dpivot := data[pivot] - db, dc1 := data[b], data[c-1] - for b < c { - if db < dpivot { // data[b] < pivot - b++ - if b < c { - db = data[b] - } - continue - } - if !(dpivot < db) { // data[b] = pivot - data[a], data[b] = db, data[a] - a++ - b++ - if b < c { - db = data[b] - } - continue - } - if dpivot < dc1 { // data[c-1] > pivot - c-- - if c > 0 { - dc1 = data[c-1] - } - continue - } - if !(dc1 < dpivot) { // data[c-1] = pivot - data[c-1], data[d-1] = data[d-1], dc1 - c-- - d-- - if c > 0 { - dc1 = data[c-1] - } - continue - } - // data[b] > pivot; data[c-1] < pivot - data[b], data[c-1] = dc1, db - b++ - c-- - if b < c { - db = data[b] - dc1 = data[c-1] - } - } - - n := min(b-a, a-lo) - swapRange(data, lo, b-n, n) - - n = min(hi-d, d-c) - swapRange(data, c, hi-n, n) - - return lo + b - a, hi - (d - c) -} - -func quickSort(data []int, a, b, maxDepth int) { - for b-a > 7 { - if maxDepth == 0 { - heapSort(data, a, b) - return - } - maxDepth-- - mlo, mhi := doPivot(data, a, b) - // Avoiding recursion on the larger subproblem guarantees - // a stack depth of at most lg(b-a). - if mlo-a < b-mhi { - quickSort(data, a, mlo, maxDepth) - a = mhi // i.e., quickSort(data, mhi, b) - } else { - quickSort(data, mhi, b, maxDepth) - b = mlo // i.e., quickSort(data, a, mlo) - } - } - if b-a > 1 { - insertionSort(data, a, b) - } -} - -func sortInts(data []int) { - // Switch to heapsort if depth of 2*ceil(lg(n)) is reached. - n := len(data) - maxDepth := 0 - for 1<<uint(maxDepth) < n { - maxDepth++ - } - maxDepth *= 2 - quickSort(data, 0, n, maxDepth) -} diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go deleted file mode 100644 index 461027080..000000000 --- a/vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go +++ /dev/null @@ -1,80 +0,0 @@ -// Copyright 2011 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Copied from code.google.com/p/codesearch/sparse/set.go, -// tweaked for better inlinability. - -package main - -// For comparison: running cindex over the Linux 2.6 kernel with this -// implementation of trigram sets takes 11 seconds. If I change it to -// a bitmap (which must be cleared between files) it takes 25 seconds. - -// A Set is a sparse set of uint32 values. -// http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html -type Set struct { - dense []uint32 - sparse []uint32 -} - -// NewSet returns a new Set with a given maximum size. -// The set can contain numbers in [0, max-1]. -func NewSet(max uint32) *Set { - return &Set{ - sparse: make([]uint32, max), - } -} - -// Init initializes a Set to have a given maximum size. -// The set can contain numbers in [0, max-1]. -func (s *Set) Init(max uint32) { - s.sparse = make([]uint32, max) -} - -// Reset clears (empties) the set. -func (s *Set) Reset() { - s.dense = s.dense[:0] -} - -// Add adds x to the set if it is not already there. -// -// TODO: The ugly additional variables v and n make the -// function inlinable. When the 6g inliner gets better -// they will not be necessary. -func (s *Set) Add(x uint32, v uint32, n int) { - v = s.sparse[x] - if v < uint32(len(s.dense)) && s.dense[v] == x { - return - } - n = len(s.dense) - s.sparse[x] = uint32(n) - s.dense = append(s.dense, x) -} - -func (s *Set) MustAdd(x uint32) { - s.sparse[x] = uint32(len(s.dense)) - s.dense = append(s.dense, x) -} - -// Has reports whether x is in the set. -// -// TODO: The ugly additional variables v makes -// function inlinable. When the 6g inliner gets better -// it will not be necessary. -func (s *Set) Has(x uint32, v uint32) bool { - v = s.sparse[x] - return v < uint32(len(s.dense)) && s.dense[v] == x -} - -// Dense returns the values in the set. -// The values are listed in the order in which they -// were inserted. -func (s *Set) Dense() []uint32 { - return s.dense -} - -// Len returns the number of values in the set. -func (s *Set) Len() int { - return len(s.dense) -} diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/utf.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/utf.go deleted file mode 100644 index 605e01c10..000000000 --- a/vendor/github.com/mattermost/rsc/regexp/regmerge/utf.go +++ /dev/null @@ -1,270 +0,0 @@ -// Copyright 2011 The Go Authors. All rights reserved. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -// Copy of code.google.com/p/codesearch/regexp/utf.go. - -package main - -import ( - "regexp/syntax" - "unicode" - "unicode/utf8" -) - -const ( - instFail = syntax.InstFail - instAlt = syntax.InstAlt - instByteRange = syntax.InstRune | 0x80 // local opcode - - argFold = 1 << 16 -) - -func toByteProg(prog *syntax.Prog) error { - var b runeBuilder - for pc := range prog.Inst { - i := &prog.Inst[pc] - switch i.Op { - case syntax.InstRune, syntax.InstRune1: - // General rune range. PIA. - // TODO: Pick off single-byte case. - if lo, hi, fold, ok := oneByteRange(i); ok { - i.Op = instByteRange - i.Arg = uint32(lo)<<8 | uint32(hi) - if fold { - i.Arg |= argFold - } - break - } - - r := i.Rune - if syntax.Flags(i.Arg)&syntax.FoldCase != 0 { - // Build folded list. - var rr []rune - if len(r) == 1 { - rr = appendFoldedRange(rr, r[0], r[0]) - } else { - for j := 0; j < len(r); j += 2 { - rr = appendFoldedRange(rr, r[j], r[j+1]) - } - } - r = rr - } - - b.init(prog, uint32(pc), i.Out) - if len(r) == 1 { - b.addRange(r[0], r[0], false) - } else { - for j := 0; j < len(r); j += 2 { - b.addRange(r[j], r[j+1], false) - } - } - - case syntax.InstRuneAny, syntax.InstRuneAnyNotNL: - // All runes. - // AnyNotNL should exclude \n but the line-at-a-time - // execution takes care of that for us. - b.init(prog, uint32(pc), i.Out) - b.addRange(0, unicode.MaxRune, false) - } - } - return nil -} - -func oneByteRange(i *syntax.Inst) (lo, hi byte, fold, ok bool) { - if i.Op == syntax.InstRune1 { - r := i.Rune[0] - if r < utf8.RuneSelf { - return byte(r), byte(r), false, true - } - } - if i.Op != syntax.InstRune { - return - } - fold = syntax.Flags(i.Arg)&syntax.FoldCase != 0 - if len(i.Rune) == 1 || len(i.Rune) == 2 && i.Rune[0] == i.Rune[1] { - r := i.Rune[0] - if r >= utf8.RuneSelf { - return - } - if fold && !asciiFold(r) { - return - } - return byte(r), byte(r), fold, true - } - if len(i.Rune) == 2 && i.Rune[1] < utf8.RuneSelf { - if fold { - for r := i.Rune[0]; r <= i.Rune[1]; r++ { - if asciiFold(r) { - return - } - } - } - return byte(i.Rune[0]), byte(i.Rune[1]), fold, true - } - if len(i.Rune) == 4 && i.Rune[0] == i.Rune[1] && i.Rune[2] == i.Rune[3] && unicode.SimpleFold(i.Rune[0]) == i.Rune[2] && unicode.SimpleFold(i.Rune[2]) == i.Rune[0] { - return byte(i.Rune[0]), byte(i.Rune[0]), true, true - } - - return -} - -func asciiFold(r rune) bool { - if r >= utf8.RuneSelf { - return false - } - r1 := unicode.SimpleFold(r) - if r1 >= utf8.RuneSelf { - return false - } - if r1 == r { - return true - } - return unicode.SimpleFold(r1) == r -} - -func maxRune(n int) rune { - b := 0 - if n == 1 { - b = 7 - } else { - b = 8 - (n + 1) + 6*(n-1) - } - return 1<<uint(b) - 1 -} - -type cacheKey struct { - lo, hi uint8 - fold bool - next uint32 -} - -type runeBuilder struct { - begin uint32 - out uint32 - cache map[cacheKey]uint32 - p *syntax.Prog -} - -func (b *runeBuilder) init(p *syntax.Prog, begin, out uint32) { - // We will rewrite p.Inst[begin] to hold the accumulated - // machine. For now, there is no match. - p.Inst[begin].Op = instFail - - b.begin = begin - b.out = out - if b.cache == nil { - b.cache = make(map[cacheKey]uint32) - } - for k := range b.cache { - delete(b.cache, k) - } - b.p = p -} - -func (b *runeBuilder) uncachedSuffix(lo, hi byte, fold bool, next uint32) uint32 { - if next == 0 { - next = b.out - } - pc := len(b.p.Inst) - i := syntax.Inst{Op: instByteRange, Arg: uint32(lo)<<8 | uint32(hi), Out: next} - if fold { - i.Arg |= argFold - } - b.p.Inst = append(b.p.Inst, i) - return uint32(pc) -} - -func (b *runeBuilder) suffix(lo, hi byte, fold bool, next uint32) uint32 { - if lo < 0x80 || hi > 0xbf { - // Not a continuation byte, no need to cache. - return b.uncachedSuffix(lo, hi, fold, next) - } - - key := cacheKey{lo, hi, fold, next} - if pc, ok := b.cache[key]; ok { - return pc - } - - pc := b.uncachedSuffix(lo, hi, fold, next) - b.cache[key] = pc - return pc -} - -func (b *runeBuilder) addBranch(pc uint32) { - // Add pc to the branch at the beginning. - i := &b.p.Inst[b.begin] - switch i.Op { - case syntax.InstFail: - i.Op = syntax.InstNop - i.Out = pc - return - case syntax.InstNop: - i.Op = syntax.InstAlt - i.Arg = pc - return - case syntax.InstAlt: - apc := uint32(len(b.p.Inst)) - b.p.Inst = append(b.p.Inst, syntax.Inst{Op: instAlt, Out: i.Arg, Arg: pc}) - i = &b.p.Inst[b.begin] - i.Arg = apc - b.begin = apc - } -} - -func (b *runeBuilder) addRange(lo, hi rune, fold bool) { - if lo > hi { - return - } - - // TODO: Pick off 80-10FFFF for special handling? - if lo == 0x80 && hi == 0x10FFFF { - } - - // Split range into same-length sized ranges. - for i := 1; i < utf8.UTFMax; i++ { - max := maxRune(i) - if lo <= max && max < hi { - b.addRange(lo, max, fold) - b.addRange(max+1, hi, fold) - return - } - } - - // ASCII range is special. - if hi < utf8.RuneSelf { - b.addBranch(b.suffix(byte(lo), byte(hi), fold, 0)) - return - } - - // Split range into sections that agree on leading bytes. - for i := 1; i < utf8.UTFMax; i++ { - m := rune(1)<<uint(6*i) - 1 // last i bytes of UTF-8 sequence - if lo&^m != hi&^m { - if lo&m != 0 { - b.addRange(lo, lo|m, fold) - b.addRange((lo|m)+1, hi, fold) - return - } - if hi&m != m { - b.addRange(lo, hi&^m-1, fold) - b.addRange(hi&^m, hi, fold) - return - } - } - } - - // Finally. Generate byte matching equivalent for lo-hi. - var ulo, uhi [utf8.UTFMax]byte - n := utf8.EncodeRune(ulo[:], lo) - m := utf8.EncodeRune(uhi[:], hi) - if n != m { - panic("codesearch/regexp: bad utf-8 math") - } - - pc := uint32(0) - for i := n - 1; i >= 0; i-- { - pc = b.suffix(ulo[i], uhi[i], false, pc) - } - b.addBranch(pc) -} |