diff options
Diffstat (limited to 'vendor/github.com/mattermost/rsc/regexp')
7 files changed, 1379 insertions, 0 deletions
diff --git a/vendor/github.com/mattermost/rsc/regexp/regmerge/copy.go b/vendor/github.com/mattermost/rsc/regexp/regmerge/copy.go new file mode 100644 index 000000000..4e723260b --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/copy.go @@ -0,0 +1,225 @@ +// 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 new file mode 100644 index 000000000..672337a04 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/main.go @@ -0,0 +1,96 @@ +// 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 new file mode 100644 index 000000000..6a4b1f967 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/match.go @@ -0,0 +1,406 @@ +// 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 new file mode 100644 index 000000000..15f51cfa7 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/merge.go @@ -0,0 +1,103 @@ +// 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 new file mode 100644 index 000000000..e40f87714 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/sort.go @@ -0,0 +1,199 @@ +// 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 new file mode 100644 index 000000000..461027080 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/sparse.go @@ -0,0 +1,80 @@ +// 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 new file mode 100644 index 000000000..605e01c10 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/regexp/regmerge/utf.go @@ -0,0 +1,270 @@ +// 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) +} |