// 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. package syntax import ( "strconv" "strings" "unicode" "unicode/utf8" ) // Compiled program. // May not belong in this package, but convenient for now. // A Prog is a compiled regular expression program. type Prog struct { Inst []Inst Start int // index of start instruction NumCap int // number of InstCapture insts in re } // An InstOp is an instruction opcode. type InstOp uint8 const ( InstAlt InstOp = iota InstAltMatch InstCapture InstEmptyWidth InstMatch InstFail InstNop InstRune InstRune1 InstRuneAny InstRuneAnyNotNL ) var instOpNames = []string{ "InstAlt", "InstAltMatch", "InstCapture", "InstEmptyWidth", "InstMatch", "InstFail", "InstNop", "InstRune", "InstRune1", "InstRuneAny", "InstRuneAnyNotNL", } func (i InstOp) String() string { if uint(i) >= uint(len(instOpNames)) { return "" } return instOpNames[i] } // An EmptyOp specifies a kind or mixture of zero-width assertions. type EmptyOp uint8 const ( EmptyBeginLine EmptyOp = 1 << iota EmptyEndLine EmptyBeginText EmptyEndText EmptyWordBoundary EmptyNoWordBoundary ) // EmptyOpContext returns the zero-width assertions // satisfied at the position between the runes r1 and r2. // Passing r1 == -1 indicates that the position is // at the beginning of the text. // Passing r2 == -1 indicates that the position is // at the end of the text. func EmptyOpContext(r1, r2 rune) EmptyOp { var op EmptyOp = EmptyNoWordBoundary var boundary byte switch { case IsWordChar(r1): boundary = 1 case r1 == '\n': op |= EmptyBeginLine case r1 < 0: op |= EmptyBeginText | EmptyBeginLine } switch { case IsWordChar(r2): boundary ^= 1 case r2 == '\n': op |= EmptyEndLine case r2 < 0: op |= EmptyEndText | EmptyEndLine } if boundary != 0 { // IsWordChar(r1) != IsWordChar(r2) op ^= (EmptyWordBoundary | EmptyNoWordBoundary) } return op } // IsWordChar reports whether r is considered a “word character” // during the evaluation of the \b and \B zero-width assertions. // These assertions are ASCII-only: the word characters are [A-Za-z0-9_]. func IsWordChar(r rune) bool { // Test for lowercase letters first, as these occur more // frequently than uppercase letters in common cases. return 'a' <= r && r <= 'z' || 'A' <= r && r <= 'Z' || '0' <= r && r <= '9' || r == '_' } // An Inst is a single instruction in a regular expression program. type Inst struct { Op InstOp Out uint32 // all but InstMatch, InstFail Arg uint32 // InstAlt, InstAltMatch, InstCapture, InstEmptyWidth Rune []rune } func (p *Prog) String() string { var b strings.Builder dumpProg(&b, p) return b.String() } // skipNop follows any no-op or capturing instructions. func (p *Prog) skipNop(pc uint32) *Inst { i := &p.Inst[pc] for i.Op == InstNop || i.Op == InstCapture { i = &p.Inst[i.Out] } return i } // op returns i.Op but merges all the Rune special cases into InstRune func (i *Inst) op() InstOp { op := i.Op switch op { case InstRune1, InstRuneAny, InstRuneAnyNotNL: op = InstRune } return op } // Prefix returns a literal string that all matches for the // regexp must start with. Complete is true if the prefix // is the entire match. func (p *Prog) Prefix() (prefix string, complete bool) { i := p.skipNop(uint32(p.Start)) // Avoid allocation of buffer if prefix is empty. if i.op() != InstRune || len(i.Rune) != 1 { return "", i.Op == InstMatch } // Have prefix; gather characters. var buf strings.Builder for i.op() == InstRune && len(i.Rune) == 1 && Flags(i.Arg)&FoldCase == 0 && i.Rune[0] != utf8.RuneError { buf.WriteRune(i.Rune[0]) i = p.skipNop(i.Out) } return buf.String(), i.Op == InstMatch } // StartCond returns the leading empty-width conditions that must // be true in any match. It returns ^EmptyOp(0) if no matches are possible. func (p *Prog) StartCond() EmptyOp { var flag EmptyOp pc := uint32(p.Start) i := &p.Inst[pc] Loop: for { switch i.Op { case InstEmptyWidth: flag |= EmptyOp(i.Arg) case InstFail: return ^EmptyOp(0) case InstCapture, InstNop: // skip default: break Loop } pc = i.Out i = &p.Inst[pc] } return flag } const noMatch = -1 // MatchRune reports whether the instruction matches (and consumes) r. // It should only be called when i.Op == InstRune. func (i *Inst) MatchRune(r rune) bool { return i.MatchRunePos(r) != noMatch } // MatchRunePos checks whether the instruction matches (and consumes) r. // If so, MatchRunePos returns the index of the matching rune pair // (or, when len(i.Rune) == 1, rune singleton). // If not, MatchRunePos returns -1. // MatchRunePos should only be called when i.Op == InstRune. func (i *Inst) MatchRunePos(r rune) int { rune := i.Rune switch len(rune) { case 0: return noMatch case 1: // Special case: single-rune slice is from literal string, not char class. r0 := rune[0] if r == r0 { return 0 } if Flags(i.Arg)&FoldCase != 0 { for r1 := unicode.SimpleFold(r0); r1 != r0; r1 = unicode.SimpleFold(r1) { if r == r1 { return 0 } } } return noMatch case 2: if r >= rune[0] && r <= rune[1] { return 0 } return noMatch case 4, 6, 8: // Linear search for a few pairs. // Should handle ASCII well. for j := 0; j < len(rune); j += 2 { if r < rune[j] { return noMatch } if r <= rune[j+1] { return j / 2 } } return noMatch } // Otherwise binary search. lo := 0 hi := len(rune) / 2 for lo < hi { m := int(uint(lo+hi) >> 1) if c := rune[2*m]; c <= r { if r <= rune[2*m+1] { return m } lo = m + 1 } else { hi = m } } return noMatch } // MatchEmptyWidth reports whether the instruction matches // an empty string between the runes before and after. // It should only be called when i.Op == InstEmptyWidth. func (i *Inst) MatchEmptyWidth(before rune, after rune) bool { switch EmptyOp(i.Arg) { case EmptyBeginLine: return before == '\n' || before == -1 case EmptyEndLine: return after == '\n' || after == -1 case EmptyBeginText: return before == -1 case EmptyEndText: return after == -1 case EmptyWordBoundary: return IsWordChar(before) != IsWordChar(after) case EmptyNoWordBoundary: return IsWordChar(before) == IsWordChar(after) } panic("unknown empty width arg") } func (i *Inst) String() string { var b strings.Builder dumpInst(&b, i) return b.String() } func bw(b *strings.Builder, args ...string) { for _, s := range args { b.WriteString(s) } } func dumpProg(b *strings.Builder, p *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 *strings.Builder, i *Inst) { switch i.Op { case InstAlt: bw(b, "alt -> ", u32(i.Out), ", ", u32(i.Arg)) case InstAltMatch: bw(b, "altmatch -> ", u32(i.Out), ", ", u32(i.Arg)) case InstCapture: bw(b, "cap ", u32(i.Arg), " -> ", u32(i.Out)) case InstEmptyWidth: bw(b, "empty ", u32(i.Arg), " -> ", u32(i.Out)) case InstMatch: bw(b, "match") case InstFail: bw(b, "fail") case InstNop: bw(b, "nop -> ", u32(i.Out)) case InstRune: if i.Rune == nil { // shouldn't happen bw(b, "rune ") } bw(b, "rune ", strconv.QuoteToASCII(string(i.Rune))) if Flags(i.Arg)&FoldCase != 0 { bw(b, "/i") } bw(b, " -> ", u32(i.Out)) case InstRune1: bw(b, "rune1 ", strconv.QuoteToASCII(string(i.Rune)), " -> ", u32(i.Out)) case InstRuneAny: bw(b, "any -> ", u32(i.Out)) case InstRuneAnyNotNL: bw(b, "anynotnl -> ", u32(i.Out)) } }