// Copyright 2009 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 regexp implements a simple regular expression library.
//
// The syntax of the regular expressions accepted is:
//
// regexp:
// concatenation { '|' concatenation }
// concatenation:
// { closure }
// closure:
// term [ '*' | '+' | '?' ]
// term:
// '^'
// '$'
// '.'
// character
// '[' [ '^' ] character-ranges ']'
// '(' regexp ')'
//
package regexp
import (
"bytes";
"container/vector";
"io";
"os";
"strings";
"utf8";
)
var debug = false
// Error codes returned by failures to parse an expression.
var (
ErrInternal = os.NewError("internal error");
ErrUnmatchedLpar = os.NewError("unmatched '('");
ErrUnmatchedRpar = os.NewError("unmatched ')'");
ErrUnmatchedLbkt = os.NewError("unmatched '['");
ErrUnmatchedRbkt = os.NewError("unmatched ']'");
ErrBadRange = os.NewError("bad range in character class");
ErrExtraneousBackslash = os.NewError("extraneous backslash");
ErrBadClosure = os.NewError("repeated closure (**, ++, etc.)");
ErrBareClosure = os.NewError("closure applies to nothing");
ErrBadBackslash = os.NewError("illegal backslash escape");
)
// An instruction executed by the NFA
type instr interface {
kind() int; // the type of this instruction: _CHAR, _ANY, etc.
next() instr; // the instruction to execute after this one
setNext(i instr);
index() int;
setIndex(i int);
print();
}
// Fields and methods common to all instructions
type common struct {
_next instr;
_index int;
}
func (c *common) next() instr { return c._next }
func (c *common) setNext(i instr) { c._next = i }
func (c *common) index() int { return c._index }
func (c *common) setIndex(i int) { c._index = i }
// Regexp is the representation of a compiled regular expression.
// The public interface is entirely through methods.
type Regexp struct {
expr string; // the original expression
prefix string; // initial plain text string
prefixBytes []byte; // initial plain text bytes
inst *vector.Vector;
start instr;
nbra int; // number of brackets in expression, for subexpressions
}
const (
_START = iota; // beginning of program
_END; // end of program: success
_BOT; // '^' beginning of text
_EOT; // '$' end of text
_CHAR; // 'a' regular character
_CHARCLASS; // [a-z] character class
_ANY; // '.' any character including newline
_NOTNL; // [^\n] special case: any character but newline
_BRA; // '(' parenthesized expression
_EBRA; // ')'; end of '(' parenthesized expression
_ALT; // '|' alternation
_NOP; // do nothing; makes it easy to link without patching
)
// --- START start of program
type _Start struct {
common;
}
func (start *_Start) kind() int { return _START }
func (start *_Start) print() { print("start") }
// --- END end of program
type _End struct {
common;
}
func (end *_End) kind() int { return _END }
func (end *_End) print() { print("end") }
// --- BOT beginning of text
type _Bot struct {
common;
}
func (bot *_Bot) kind() int { return _BOT }
func (bot *_Bot) print() { print("bot") }
// --- EOT end of text
type _Eot struct {
common;
}
func (eot *_Eot) kind() int { return _EOT }
func (eot *_Eot) print() { print("eot") }
// --- CHAR a regular character
type _Char struct {
common;
char int;
}
func (char *_Char) kind() int { return _CHAR }
func (char *_Char) print() { print("char ", string(char.char)) }
func newChar(char int) *_Char {
c := new(_Char);
c.char = char;
return c;
}
// --- CHARCLASS [a-z]
type _CharClass struct {
common;
char int;
negate bool; // is character class negated? ([^a-z])
// vector of int, stored pairwise: [a-z] is (a,z); x is (x,x):
ranges *vector.IntVector;
}
func (cclass *_CharClass) kind() int { return _CHARCLASS }
func (cclass *_CharClass) print() {
print("charclass");
if cclass.negate {
print(" (negated)")
}
for i := 0; i < cclass.ranges.Len(); i += 2 {
l := cclass.ranges.At(i);
r := cclass.ranges.At(i + 1);
if l == r {
print(" [", string(l), "]")
} else {
print(" [", string(l), "-", string(r), "]")
}
}
}
func (cclass *_CharClass) addRange(a, b int) {
// range is a through b inclusive
cclass.ranges.Push(a);
cclass.ranges.Push(b);
}
func (cclass *_CharClass) matches(c int) bool {
for i := 0; i < cclass.ranges.Len(); i = i + 2 {
min := cclass.ranges.At(i);
max := cclass.ranges.At(i + 1);
if min <= c && c <= max {
return !cclass.negate
}
}
return cclass.negate;
}
func newCharClass() *_CharClass {
c := new(_CharClass);
c.ranges = new(vector.IntVector);
return c;
}
// --- ANY any character
type _Any struct {
common;
}
func (any *_Any) kind() int { return _ANY }
func (any *_Any) print() { print("any") }
// --- NOTNL any character but newline
type _NotNl struct {
common;
}
func (notnl *_NotNl) kind() int { return _NOTNL }
func (notnl *_NotNl) print() { print("notnl") }
// --- BRA parenthesized expression
type _Bra struct {
common;
n int; // subexpression number
}
func (bra *_Bra) kind() int { return _BRA }
func (bra *_Bra) print() { print("bra", bra.n) }
// --- EBRA end of parenthesized expression
type _Ebra struct {
common;
n int; // subexpression number
}
func (ebra *_Ebra) kind() int { return _EBRA }
func (ebra *_Ebra) print() { print("ebra ", ebra.n) }
// --- ALT alternation
type _Alt struct {
common;
left instr; // other branch
}
func (alt *_Alt) kind() int { return _ALT }
func (alt *_Alt) print() { print("alt(", alt.left.index(), ")") }
// --- NOP no operation
type _Nop struct {
common;
}
func (nop *_Nop) kind() int { return _NOP }
func (nop *_Nop) print() { print("nop") }
func (re *Regexp) add(i instr) instr {
i.setIndex(re.inst.Len());
re.inst.Push(i);
return i;
}
type parser struct {
re *Regexp;
error os.Error;
nlpar int; // number of unclosed lpars
pos int;
ch int;
}
const endOfFile = -1
func (p *parser) c() int { return p.ch }
func (p *parser) nextc() int {
if p.pos >= len(p.re.expr) {
p.ch = endOfFile
} else {
c, w := utf8.DecodeRuneInString(p.re.expr[p.pos:]);
p.ch = c;
p.pos += w;
}
return p.ch;
}
func newParser(re *Regexp) *parser {
p := new(parser);
p.re = re;
p.nextc(); // load p.ch
return p;
}
func special(c int) bool {
for _, r := range `\.+*?()|[]^$` {
if c == r {
return true
}
}
return false;
}
func specialcclass(c int) bool {
for _, r := range `\-[]` {
if c == r {
return true
}
}
return false;
}
func (p *parser) charClass() instr {
cc := newCharClass();
if p.c() == '^' {
cc.negate = true;
p.nextc();
}
left := -1;
for {
switch c := p.c(); c {
case ']', endOfFile:
if left >= 0 {
p.error = ErrBadRange;
return nil;
}
// Is it [^\n]?
if cc.negate && cc.ranges.Len() == 2 &&
cc.ranges.At(0) == '\n' && cc.ranges.At(1) == '\n' {
nl := new(_NotNl);
p.re.add(nl);
return nl;
}
// Special common case: "[a]" -> "a"
if !cc.negate && cc.ranges.Len() == 2 && cc.ranges.At(0) == cc.ranges.At(1) {
c := newChar(cc.ranges.At(0));
p.re.add(c);
return c;
}
p.re.add(cc);
return cc;
case '-': // do this before backslash processing
p.error = ErrBadRange;
return nil;
case '\\':
c = p.nextc();
switch {
case c == endOfFile:
p.error = ErrExtraneousBackslash;
return nil;
case c == 'n':
c = '\n'
case specialcclass(c):
// c is as delivered
default:
p.error = ErrBadBackslash;
return nil;
}
fallthrough;
default:
p.nextc();
switch {
case left < 0: // first of pair
if p.c() == '-' { // range
p.nextc();
left = c;
} else { // single char
cc.addRange(c, c)
}
case left <= c: // second of pair
cc.addRange(left, c);
left = -1;
default:
p.error = ErrBadRange;
return nil;
}
}
}
return nil;
}
func (p *parser) term() (start, end instr) {
// term() is the leaf of the recursion, so it's sufficient to pick off the
// error state here for early exit.
// The other functions (closure(), concatenation() etc.) assume
// it's safe to recur to here.
if p.error != nil {
return
}
switch c := p.c(); c {
case '|', endOfFile:
return nil, nil
case '*', '+':
p.error = ErrBareClosure;
return;
case ')':
if p.nlpar == 0 {
p.error = ErrUnmatchedRpar;
return;
}
return nil, nil;
case ']':
p.error = ErrUnmatchedRbkt;
return;
case '^':
p.nextc();
start = p.re.add(new(_Bot));
return start, start;
case '$':
p.nextc();
start = p.re.add(new(_Eot));
return start, start;
case '.':
p.nextc();
start = p.re.add(new(_Any));
return start, start;
case '[':
p.nextc();
start = p.charClass();
if p.error != nil {
return
}
if p.c() != ']' {
p.error = ErrUnmatchedLbkt;
return;
}
p.nextc();
return start, start;
case '(':
p.nextc();
p.nlpar++;
p.re.nbra++; // increment first so first subexpr is \1
nbra := p.re.nbra;
start, end = p.regexp();
if p.c() != ')' {
p.error = ErrUnmatchedLpar;
return;
}
p.nlpar--;
p.nextc();
bra := new(_Bra);
p.re.add(bra);
ebra := new(_Ebra);
p.re.add(ebra);
bra.n = nbra;
ebra.n = nbra;
if start == nil {
if end == nil {
p.error = ErrInternal;
return;
}
start = ebra;
} else {
end.setNext(ebra)
}
bra.setNext(start);
return bra, ebra;
case '\\':
c = p.nextc();
switch {
case c == endOfFile:
p.error = ErrExtraneousBackslash;
return;
case c == 'n':
c = '\n'
case special(c):
// c is as delivered
default:
p.error = ErrBadBackslash;
return;
}
fallthrough;
default:
p.nextc();
start = newChar(c);
p.re.add(start);
return start, start;
}
panic("unreachable");
}
func (p *parser) closure() (start, end instr) {
start, end = p.term();
if start == nil || p.error != nil {
return
}
switch p.c() {
case '*':
// (start,end)*:
alt := new(_Alt);
p.re.add(alt);
end.setNext(alt); // after end, do alt
alt.left = start; // alternate brach: return to start
start = alt; // alt becomes new (start, end)
end = alt;
case '+':
// (start,end)+:
alt := new(_Alt);
p.re.add(alt);
end.setNext(alt); // after end, do alt
alt.left = start; // alternate brach: return to start
end = alt; // start is unchanged; end is alt
case '?':
// (start,end)?:
alt := new(_Alt);
p.re.add(alt);
nop := new(_Nop);
p.re.add(nop);
alt.left = start; // alternate branch is start
alt.setNext(nop); // follow on to nop
end.setNext(nop); // after end, go to nop
start = alt; // start is now alt
end = nop; // end is nop pointed to by both branches
default:
return
}
switch p.nextc() {
case '*', '+', '?':
p.error = ErrBadClosure
}
return;
}
func (p *parser) concatenation() (start, end instr) {
for {
nstart, nend := p.closure();
if p.error != nil {
return
}
switch {
case nstart == nil: // end of this concatenation
if start == nil { // this is the empty string
nop := p.re.add(new(_Nop));
return nop, nop;
}
return;
case start == nil: // this is first element of concatenation
start, end = nstart, nend
default:
end.setNext(nstart);
end = nend;
}
}
panic("unreachable");
}
func (p *parser) regexp() (start, end instr) {
start, end = p.concatenation();
if p.error != nil {
return
}
for {
switch p.c() {
default:
return
case '|':
p.nextc();
nstart, nend := p.concatenation();
if p.error != nil {
return
}
alt := new(_Alt);
p.re.add(alt);
alt.left = start;
alt.setNext(nstart);
nop := new(_Nop);
p.re.add(nop);
end.setNext(nop);
nend.setNext(nop);
start, end = alt, nop;
}
}
panic("unreachable");
}
func unNop(i instr) instr {
for i.kind() == _NOP {
i = i.next()
}
return i;
}
func (re *Regexp) eliminateNops() {
for i := 0; i < re.inst.Len(); i++ {
inst := re.inst.At(i).(instr);
if inst.kind() == _END {
continue
}
inst.setNext(unNop(inst.next()));
if inst.kind() == _ALT {
alt := inst.(*_Alt);
alt.left = unNop(alt.left);
}
}
}
func (re *Regexp) dump() {
print("prefix <", re.prefix, ">\n");
for i := 0; i < re.inst.Len(); i++ {
inst := re.inst.At(i).(instr);
print(inst.index(), ": ");
inst.print();
if inst.kind() != _END {
print(" -> ", inst.next().index())
}
print("\n");
}
}
func (re *Regexp) doParse() os.Error {
p := newParser(re);
start := new(_Start);
re.add(start);
s, e := p.regexp();
if p.error != nil {
return p.error
}
start.setNext(s);
re.start = start;
e.setNext(re.add(new(_End)));
if debug {
re.dump();
println();
}
re.eliminateNops();
if debug {
re.dump();
println();
}
if p.error == nil {
re.setPrefix();
if debug {
re.dump();
println();
}
}
return p.error;
}
// Extract regular text from the beginning of the pattern.
// That text can be used by doExecute to speed up matching.
func (re *Regexp) setPrefix() {
var b []byte;
var utf = make([]byte, utf8.UTFMax);
// First instruction is start; skip that.
i := re.inst.At(0).(instr).next().index();
Loop:
for i < re.inst.Len() {
inst := re.inst.At(i).(instr);
// stop if this is not a char
if inst.kind() != _CHAR {
break
}
// stop if this char can be followed by a match for an empty string,
// which includes closures, ^, and $.
switch re.inst.At(inst.next().index()).(instr).kind() {
case _BOT, _EOT, _ALT:
break Loop
}
n := utf8.EncodeRune(inst.(*_Char).char, utf);
b = bytes.Add(b, utf[0:n]);
i = inst.next().index();
}
// point start instruction to first non-CHAR
re.inst.At(0).(instr).setNext(re.inst.At(i).(instr));
re.prefixBytes = b;
re.prefix = string(b);
}
// Compile parses a regular expression and returns, if successful, a Regexp
// object that can be used to match against text.
func Compile(str string) (regexp *Regexp, error os.Error) {
regexp = new(Regexp);
regexp.expr = str;
regexp.inst = new(vector.Vector);
error = regexp.doParse();
return;
}
// MustCompile is like Compile but panics if the expression cannot be parsed.
// It simplifies safe initialization of global variables holding compiled regular
// expressions.
func MustCompile(str string) *Regexp {
regexp, error := Compile(str);
if error != nil {
panicln(`regexp: compiling "`, str, `": `, error.String())
}
return regexp;
}
// The match arena allows us to reduce the garbage generated by tossing
// match vectors away as we execute. Matches are ref counted and returned
// to a free list when no longer active. Increases a simple benchmark by 22X.
type matchArena struct {
head *matchVec;
len int; // length of match vector
}
type matchVec struct {
m []int; // pairs of bracketing submatches. 0th is start,end
ref int;
next *matchVec;
}
func (a *matchArena) new() *matchVec {
if a.head == nil {
const N = 10;
block := make([]matchVec, N);
for i := 0; i < N; i++ {
b := &block[i];
b.next = a.head;
a.head = b;
}
}
m := a.head;
a.head = m.next;
m.ref = 0;
if m.m == nil {
m.m = make([]int, a.len)
}
return m;
}
func (a *matchArena) free(m *matchVec) {
m.ref--;
if m.ref == 0 {
m.next = a.head;
a.head = m;
}
}
func (a *matchArena) copy(m *matchVec) *matchVec {
m1 := a.new();
copy(m1.m, m.m);
return m1;
}
func (a *matchArena) noMatch() *matchVec {
m := a.new();
for i := range m.m {
m.m[i] = -1 // no match seen; catches cases like "a(b)?c" on "ac"
}
m.ref = 1;
return m;
}
type state struct {
inst instr; // next instruction to execute
match *matchVec;
}
// Append new state to to-do list. Leftmost-longest wins so avoid
// adding a state that's already active. The matchVec will be inc-ref'ed
// if it is assigned to a state.
func (a *matchArena) addState(s []state, inst instr, match *matchVec, pos, end int) []state {
switch inst.kind() {
case _BOT:
if pos == 0 {
s = a.addState(s, inst.next(), match, pos, end)
}
return s;
case _EOT:
if pos == end {
s = a.addState(s, inst.next(), match, pos, end)
}
return s;
case _BRA:
n := inst.(*_Bra).n;
match.m[2*n] = pos;
s = a.addState(s, inst.next(), match, pos, end);
return s;
case _EBRA:
n := inst.(*_Ebra).n;
match.m[2*n+1] = pos;
s = a.addState(s, inst.next(), match, pos, end);
return s;
}
index := inst.index();
l := len(s);
// States are inserted in order so it's sufficient to see if we have the same
// instruction; no need to see if existing match is earlier (it is).
for i := 0; i < l; i++ {
if s[i].inst.index() == index {
return s
}
}
if l == cap(s) {
s1 := make([]state, 2*l)[0:l];
copy(s1, s);
s = s1;
}
s = s[0 : l+1];
s[l].inst = inst;
s[l].match = match;
match.ref++;
if inst.kind() == _ALT {
s = a.addState(s, inst.(*_Alt).left, a.copy(match), pos, end);
// give other branch a copy of this match vector
s = a.addState(s, inst.next(), a.copy(match), pos, end);
}
return s;
}
// Accepts either string or bytes - the logic is identical either way.
// If bytes == nil, scan str.
func (re *Regexp) doExecute(str string, bytestr []byte, pos int) []int {
var s [2][]state;
s[0] = make([]state, 10)[0:0];
s[1] = make([]state, 10)[0:0];
in, out := 0, 1;
var final state;
found := false;
end := len(str);
if bytestr != nil {
end = len(bytestr)
}
// fast check for initial plain substring
if re.prefix != "" {
var advance int;
if bytestr == nil {
advance = strings.Index(str[pos:], re.prefix)
} else {
advance = bytes.Index(bytestr[pos:], re.prefixBytes)
}
if advance == -1 {
return []int{}
}
pos += advance + len(re.prefix);
}
arena := &matchArena{nil, 2 * (re.nbra + 1)};
for pos <= end {
if !found {
// prime the pump if we haven't seen a match yet
match := arena.noMatch();
match.m[0] = pos;
s[out] = arena.addState(s[out], re.start.next(), match, pos, end);
arena.free(match); // if addState saved it, ref was incremented
}
in, out = out, in; // old out state is new in state
// clear out old state
old := s[out];
for _, state := range old {
arena.free(state.match)
}
s[out] = old[0:0]; // truncate state vector
if found && len(s[in]) == 0 {
// machine has completed
break
}
charwidth := 1;
c := endOfFile;
if pos < end {
if bytestr == nil {
c, charwidth = utf8.DecodeRuneInString(str[pos:end])
} else {
c, charwidth = utf8.DecodeRune(bytestr[pos:end])
}
}
pos += charwidth;
for _, st := range s[in] {
switch st.inst.kind() {
case _BOT:
case _EOT:
case _CHAR:
if c == st.inst.(*_Char).char {
s[out] = arena.addState(s[out], st.inst.next(), st.match, pos, end)
}
case _CHARCLASS:
if st.inst.(*_CharClass).matches(c) {
s[out] = arena.addState(s[out], st.inst.next(), st.match, pos, end)
}
case _ANY:
if c != endOfFile {
s[out] = arena.addState(s[out], st.inst.next(), st.match, pos, end)
}
case _NOTNL:
if c != endOfFile && c != '\n' {
s[out] = arena.addState(s[out], st.inst.next(), st.match, pos, end)
}
case _BRA:
case _EBRA:
case _ALT:
case _END:
// choose leftmost longest
if !found || // first
st.match.m[0] < final.match.m[0] || // leftmost
(st.match.m[0] == final.match.m[0] && pos-charwidth > final.match.m[1]) { // longest
if final.match != nil {
arena.free(final.match)
}
final = st;
final.match.ref++;
final.match.m[1] = pos - charwidth;
}
found = true;
default:
st.inst.print();
panic("unknown instruction in execute");
}
}
}
if final.match == nil {
return nil
}
// if match found, back up start of match by width of prefix.
if re.prefix != "" && len(final.match.m) > 0 {
final.match.m[0] -= len(re.prefix)
}
return final.match.m;
}
// ExecuteString matches the Regexp against the string s.
// The return value is an array of integers, in pairs, identifying the positions of
// substrings matched by the expression.
// s[a[0]:a[1]] is the substring matched by the entire expression.
// s[a[2*i]:a[2*i+1]] for i > 0 is the substring matched by the ith parenthesized subexpression.
// A negative value means the subexpression did not match any element of the string.
// An empty array means "no match".
func (re *Regexp) ExecuteString(s string) (a []int) {
return re.doExecute(s, nil, 0)
}
// Execute matches the Regexp against the byte slice b.
// The return value is an array of integers, in pairs, identifying the positions of
// subslices matched by the expression.
// b[a[0]:a[1]] is the subslice matched by the entire expression.
// b[a[2*i]:a[2*i+1]] for i > 0 is the subslice matched by the ith parenthesized subexpression.
// A negative value means the subexpression did not match any element of the slice.
// An empty array means "no match".
func (re *Regexp) Execute(b []byte) (a []int) { return re.doExecute("", b, 0) }
// MatchString returns whether the Regexp matches the string s.
// The return value is a boolean: true for match, false for no match.
func (re *Regexp) MatchString(s string) bool { return len(re.doExecute(s, nil, 0)) > 0 }
// Match returns whether the Regexp matches the byte slice b.
// The return value is a boolean: true for match, false for no match.
func (re *Regexp) Match(b []byte) bool { return len(re.doExecute("", b, 0)) > 0 }
// MatchStrings matches the Regexp against the string s.
// The return value is an array of strings matched by the expression.
// a[0] is the substring matched by the entire expression.
// a[i] for i > 0 is the substring matched by the ith parenthesized subexpression.
// An empty array means ``no match''.
func (re *Regexp) MatchStrings(s string) (a []string) {
r := re.doExecute(s, nil, 0);
if r == nil {
return nil
}
a = make([]string, len(r)/2);
for i := 0; i < len(r); i += 2 {
if r[i] != -1 { // -1 means no match for this subexpression
a[i/2] = s[r[i]:r[i+1]]
}
}
return;
}
// MatchSlices matches the Regexp against the byte slice b.
// The return value is an array of subslices matched by the expression.
// a[0] is the subslice matched by the entire expression.
// a[i] for i > 0 is the subslice matched by the ith parenthesized subexpression.
// An empty array means ``no match''.
func (re *Regexp) MatchSlices(b []byte) (a [][]byte) {
r := re.doExecute("", b, 0);
if r == nil {
return nil
}
a = make([][]byte, len(r)/2);
for i := 0; i < len(r); i += 2 {
if r[i] != -1 { // -1 means no match for this subexpression
a[i/2] = b[r[i]:r[i+1]]
}
}
return;
}
// MatchString checks whether a textual regular expression
// matches a string. More complicated queries need
// to use Compile and the full Regexp interface.
func MatchString(pattern string, s string) (matched bool, error os.Error) {
re, err := Compile(pattern);
if err != nil {
return false, err
}
return re.MatchString(s), nil;
}
// Match checks whether a textual regular expression
// matches a byte slice. More complicated queries need
// to use Compile and the full Regexp interface.
func Match(pattern string, b []byte) (matched bool, error os.Error) {
re, err := Compile(pattern);
if err != nil {
return false, err
}
return re.Match(b), nil;
}
// ReplaceAllString returns a copy of src in which all matches for the Regexp
// have been replaced by repl. No support is provided for expressions
// (e.g. \1 or $1) in the replacement string.
func (re *Regexp) ReplaceAllString(src, repl string) string {
lastMatchEnd := 0; // end position of the most recent match
searchPos := 0; // position where we next look for a match
buf := new(bytes.Buffer);
for searchPos <= len(src) {
a := re.doExecute(src, nil, searchPos);
if len(a) == 0 {
break // no more matches
}
// Copy the unmatched characters before this match.
io.WriteString(buf, src[lastMatchEnd:a[0]]);
// Now insert a copy of the replacement string, but not for a
// match of the empty string immediately after another match.
// (Otherwise, we get double replacement for patterns that
// match both empty and nonempty strings.)
if a[1] > lastMatchEnd || a[0] == 0 {
io.WriteString(buf, repl)
}
lastMatchEnd = a[1];
// Advance past this match; always advance at least one character.
_, width := utf8.DecodeRuneInString(src[searchPos:]);
if searchPos+width > a[1] {
searchPos += width
} else if searchPos+1 > a[1] {
// This clause is only needed at the end of the input
// string. In that case, DecodeRuneInString returns width=0.
searchPos++
} else {
searchPos = a[1]
}
}
// Copy the unmatched characters after the last match.
io.WriteString(buf, src[lastMatchEnd:]);
return buf.String();
}
// ReplaceAll returns a copy of src in which all matches for the Regexp
// have been replaced by repl. No support is provided for expressions
// (e.g. \1 or $1) in the replacement text.
func (re *Regexp) ReplaceAll(src, repl []byte) []byte {
lastMatchEnd := 0; // end position of the most recent match
searchPos := 0; // position where we next look for a match
buf := new(bytes.Buffer);
for searchPos <= len(src) {
a := re.doExecute("", src, searchPos);
if len(a) == 0 {
break // no more matches
}
// Copy the unmatched characters before this match.
buf.Write(src[lastMatchEnd:a[0]]);
// Now insert a copy of the replacement string, but not for a
// match of the empty string immediately after another match.
// (Otherwise, we get double replacement for patterns that
// match both empty and nonempty strings.)
if a[1] > lastMatchEnd || a[0] == 0 {
buf.Write(repl)
}
lastMatchEnd = a[1];
// Advance past this match; always advance at least one character.
_, width := utf8.DecodeRune(src[searchPos:]);
if searchPos+width > a[1] {
searchPos += width
} else if searchPos+1 > a[1] {
// This clause is only needed at the end of the input
// string. In that case, DecodeRuneInString returns width=0.
searchPos++
} else {
searchPos = a[1]
}
}
// Copy the unmatched characters after the last match.
buf.Write(src[lastMatchEnd:]);
return buf.Bytes();
}
// QuoteMeta returns a string that quotes all regular expression metacharacters
// inside the argument text; the returned string is a regular expression matching
// the literal text. For example, QuoteMeta(`[foo]`) returns `\[foo\]`.
func QuoteMeta(s string) string {
b := make([]byte, 2*len(s));
// A byte loop is correct because all metacharacters are ASCII.
j := 0;
for i := 0; i < len(s); i++ {
if special(int(s[i])) {
b[j] = '\\';
j++;
}
b[j] = s[i];
j++;
}
return string(b[0:j]);
}
// Find matches in slice b if b is non-nil, otherwise find matches in string s.
func (re *Regexp) allMatches(s string, b []byte, n int, deliver func(int, int)) {
var end int;
if b == nil {
end = len(s)
} else {
end = len(b)
}
for pos, i, prevMatchEnd := 0, 0, -1; i < n && pos <= end; {
matches := re.doExecute(s, b, pos);
if len(matches) == 0 {
break
}
accept := true;
if matches[1] == pos {
// We've found an empty match.
if matches[0] == prevMatchEnd {
// We don't allow an empty match right
// after a previous match, so ignore it.
accept = false
}
var width int;
if b == nil {
_, width = utf8.DecodeRuneInString(s[pos:end])
} else {
_, width = utf8.DecodeRune(b[pos:end])
}
if width > 0 {
pos += width
} else {
pos = end + 1
}
} else {
pos = matches[1]
}
prevMatchEnd = matches[1];
if accept {
deliver(matches[0], matches[1]);
i++;
}
}
}
// AllMatches slices the byte slice b into substrings that are successive
// matches of the Regexp within b. If n > 0, the function returns at most n
// matches. Text that does not match the expression will be skipped. Empty
// matches abutting a preceding match are ignored. The function returns a slice
// containing the matching substrings.
func (re *Regexp) AllMatches(b []byte, n int) [][]byte {
if n <= 0 {
n = len(b) + 1
}
result := make([][]byte, n);
i := 0;
re.allMatches("", b, n, func(start, end int) {
result[i] = b[start:end];
i++;
});
return result[0:i];
}
// AllMatchesString slices the string s into substrings that are successive
// matches of the Regexp within s. If n > 0, the function returns at most n
// matches. Text that does not match the expression will be skipped. Empty
// matches abutting a preceding match are ignored. The function returns a slice
// containing the matching substrings.
func (re *Regexp) AllMatchesString(s string, n int) []string {
if n <= 0 {
n = len(s) + 1
}
result := make([]string, n);
i := 0;
re.allMatches(s, nil, n, func(start, end int) {
result[i] = s[start:end];
i++;
});
return result[0:i];
}
// AllMatchesIter slices the byte slice b into substrings that are successive
// matches of the Regexp within b. If n > 0, the function returns at most n
// matches. Text that does not match the expression will be skipped. Empty
// matches abutting a preceding match are ignored. The function returns a
// channel that iterates over the matching substrings.
func (re *Regexp) AllMatchesIter(b []byte, n int) <-chan []byte {
if n <= 0 {
n = len(b) + 1
}
c := make(chan []byte, 10);
go func() {
re.allMatches("", b, n, func(start, end int) { c <- b[start:end] });
close(c);
}();
return c;
}
// AllMatchesStringIter slices the string s into substrings that are successive
// matches of the Regexp within s. If n > 0, the function returns at most n
// matches. Text that does not match the expression will be skipped. Empty
// matches abutting a preceding match are ignored. The function returns a
// channel that iterates over the matching substrings.
func (re *Regexp) AllMatchesStringIter(s string, n int) <-chan string {
if n <= 0 {
n = len(s) + 1
}
c := make(chan string, 10);
go func() {
re.allMatches(s, nil, n, func(start, end int) { c <- s[start:end] });
close(c);
}();
return c;
}
|
