Skip to content
Snippets Groups Projects
regexp.go 22.7 KiB
Newer Older
  • Learn to ignore specific revisions
  • // 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
    
    
    Rob Pike's avatar
    Rob Pike committed
    import (
    
    	"bytes";
    
    	"container/vector";
    
    Russ Cox's avatar
    Russ Cox committed
    	"os";
    
    Russ Cox's avatar
    Russ Cox committed
    	"utf8";
    
    Rob Pike's avatar
    Rob Pike committed
    )
    
    
    Rob Pike's avatar
    Rob Pike committed
    var debug = false;
    
    Rob Pike's avatar
    Rob Pike committed
    
    
    Rob Pike's avatar
    Rob Pike committed
    // Error codes returned by failures to parse an expression.
    
    Russ Cox's avatar
    Russ Cox committed
    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
    
    Rob Pike's avatar
    Rob Pike committed
    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
    
    Rob Pike's avatar
    Rob Pike committed
    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 }
    
    // The representation of a compiled regular expression.
    // The public interface is entirely through methods.
    type Regexp struct {
    
    	expr	string;	// the original expression
    
    	ch	chan<- *Regexp;	// reply channel when we're done
    
    	error	os.Error;	// compile- or run-time error; nil if OK
    
    Rob Pike's avatar
    Rob Pike committed
    	inst	*vector.Vector;
    
    Rob Pike's avatar
    Rob Pike committed
    	start	instr;
    
    Rob Pike's avatar
    Rob Pike committed
    	nbra	int;	// number of brackets in expression, for subexpressions
    
    	_START	// 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
    
    Rob Pike's avatar
    Rob Pike committed
    	common
    
    func (start *_Start) kind() int { return _START }
    func (start *_Start) print() { print("start") }
    
    
    // --- END end of program
    
    Rob Pike's avatar
    Rob Pike committed
    	common
    
    func (end *_End) kind() int { return _END }
    func (end *_End) print() { print("end") }
    
    
    // --- BOT beginning of text
    
    Rob Pike's avatar
    Rob Pike committed
    	common
    
    func (bot *_Bot) kind() int { return _BOT }
    func (bot *_Bot) print() { print("bot") }
    
    
    // --- EOT end of text
    
    Rob Pike's avatar
    Rob Pike committed
    	common
    
    func (eot *_Eot) kind() int { return _EOT }
    func (eot *_Eot) print() { print("eot") }
    
    
    // --- CHAR a regular character
    
    Rob Pike's avatar
    Rob Pike committed
    	common;
    
    Rob Pike's avatar
    Rob Pike committed
    	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;
    }
    
    
    Rob Pike's avatar
    Rob Pike committed
    // --- CHARCLASS [a-z]
    
    
    Rob Pike's avatar
    Rob Pike committed
    	common;
    
    Rob Pike's avatar
    Rob Pike committed
    	char	int;
    	negate	bool;	// is character class negated? ([^a-z])
    
    Rob Pike's avatar
    Rob Pike committed
    	// 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() {
    
    Rob Pike's avatar
    Rob Pike committed
    	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);
    
    Rob Pike's avatar
    Rob Pike committed
    		if l == r {
    			print(" [", string(l), "]");
    		} else {
    			print(" [", string(l), "-", string(r), "]");
    		}
    	}
    }
    
    
    func (cclass *_CharClass) addRange(a, b int) {
    
    Rob Pike's avatar
    Rob Pike committed
    	// range is a through b inclusive
    
    	cclass.ranges.Push(a);
    	cclass.ranges.Push(b);
    
    func (cclass *_CharClass) matches(c int) bool {
    
    Rob Pike's avatar
    Rob Pike committed
    	for i := 0; i < cclass.ranges.Len(); i = i+2 {
    
    		min := cclass.ranges.At(i);
    		max := cclass.ranges.At(i+1);
    
    Rob Pike's avatar
    Rob Pike committed
    		if min <= c && c <= max {
    			return !cclass.negate
    		}
    	}
    	return cclass.negate
    }
    
    
    func newCharClass() *_CharClass {
    	c := new(_CharClass);
    
    Rob Pike's avatar
    Rob Pike committed
    	c.ranges = vector.NewIntVector(0);
    
    Rob Pike's avatar
    Rob Pike committed
    	return c;
    }
    
    
    // --- ANY any character
    
    Rob Pike's avatar
    Rob Pike committed
    	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
    
    Rob Pike's avatar
    Rob Pike committed
    	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
    
    Rob Pike's avatar
    Rob Pike committed
    	common;
    
    	n	int;	// subexpression number
    }
    
    
    func (ebra *_Ebra) kind() int { return _EBRA }
    func (ebra *_Ebra) print() { print("ebra ", ebra.n); }
    
    
    // --- ALT alternation
    
    Rob Pike's avatar
    Rob Pike committed
    	common;
    
    Rob Pike's avatar
    Rob Pike committed
    	left	instr;	// other branch
    
    func (alt *_Alt) kind() int { return _ALT }
    func (alt *_Alt) print() { print("alt(", alt.left.index(), ")"); }
    
    
    // --- NOP no operation
    
    Rob Pike's avatar
    Rob Pike committed
    	common
    
    func (nop *_Nop) kind() int { return _NOP }
    func (nop *_Nop) print() { print("nop") }
    
    
    // report error and exit compiling/executing goroutine
    
    	re.error = err;
    	re.ch <- re;
    
    	runtime.Goexit();
    
    func (re *Regexp) add(i instr) instr {
    	i.setIndex(re.inst.Len());
    
    Rob Pike's avatar
    Rob Pike committed
    	return i;
    }
    
    
    Rob Pike's avatar
    Rob Pike committed
    type parser struct {
    
    	re	*Regexp;
    
    	nlpar	int;	// number of unclosed lpars
    
    Rob Pike's avatar
    Rob Pike committed
    const endOfFile = -1
    
    Rob Pike's avatar
    Rob Pike committed
    func (p *parser) c() int {
    
    Rob Pike's avatar
    Rob Pike committed
    func (p *parser) nextc() int {
    
    	if p.pos >= len(p.re.expr) {
    
    Rob Pike's avatar
    Rob Pike committed
    		p.ch = endOfFile
    
    		c, w := utf8.DecodeRuneInString(p.re.expr[p.pos:len(p.re.expr)]);
    
    		p.ch = c;
    		p.pos += w;
    	}
    	return p.ch;
    }
    
    
    func newParser(re *Regexp) *parser {
    
    Rob Pike's avatar
    Rob Pike committed
    	p := new(parser);
    	p.re = re;
    	p.nextc();	// load p.ch
    	return p;
    
    func (p *parser) regexp() (start, end instr)
    
    Rob Pike's avatar
    Rob Pike committed
    var iNULL instr
    
    
    func special(c int) bool {
    
    	s := `\.+*?()|[]^$`;
    
    Rob Pike's avatar
    Rob Pike committed
    	for i := 0; i < len(s); i++ {
    		if c == int(s[i]) {
    			return true
    		}
    	}
    	return false
    }
    
    func specialcclass(c int) bool {
    	s := `\-[]`;
    
    	for i := 0; i < len(s); i++ {
    		if c == int(s[i]) {
    			return true
    		}
    	}
    	return false
    }
    
    
    func (p *parser) charClass() instr {
    
    Rob Pike's avatar
    Rob Pike committed
    	cc := newCharClass();
    
    Rob Pike's avatar
    Rob Pike committed
    	if p.c() == '^' {
    		cc.negate = true;
    		p.nextc();
    	}
    	left := -1;
    	for {
    		switch c := p.c(); c {
    
    Rob Pike's avatar
    Rob Pike committed
    		case ']', endOfFile:
    
    Rob Pike's avatar
    Rob Pike committed
    			if left >= 0 {
    
    				p.re.setError(ErrBadRange);
    
    Rob Pike's avatar
    Rob Pike committed
    			}
    
    			// 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;
    			}
    			p.re.add(cc);
    
    Rob Pike's avatar
    Rob Pike committed
    			return cc;
    		case '-':	// do this before backslash processing
    
    			p.re.setError(ErrBadRange);
    
    Rob Pike's avatar
    Rob Pike committed
    		case '\\':
    			c = p.nextc();
    			switch {
    
    Rob Pike's avatar
    Rob Pike committed
    			case c == endOfFile:
    
    				p.re.setError(ErrExtraneousBackslash);
    
    Rob Pike's avatar
    Rob Pike committed
    			case c == 'n':
    				c = '\n';
    			case specialcclass(c):
    				// c is as delivered
    			default:
    
    				p.re.setError(ErrBadBackslash);
    
    Rob Pike's avatar
    Rob Pike committed
    			}
    			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);
    
    Rob Pike's avatar
    Rob Pike committed
    				}
    			case left <= c:	// second of pair
    
    				cc.addRange(left, c);
    
    Rob Pike's avatar
    Rob Pike committed
    				left = -1;
    			default:
    
    				p.re.setError(ErrBadRange);
    
    Rob Pike's avatar
    Rob Pike committed
    	return iNULL
    
    func (p *parser) term() (start, end instr) {
    
    	switch c := p.c(); c {
    
    Rob Pike's avatar
    Rob Pike committed
    	case '|', endOfFile:
    		return iNULL, iNULL;
    
    		p.re.setError(ErrBareClosure);
    
    Rob Pike's avatar
    Rob Pike committed
    	case ')':
    
    			p.re.setError(ErrUnmatchedRpar);
    
    Rob Pike's avatar
    Rob Pike committed
    		return iNULL, iNULL;
    
    Rob Pike's avatar
    Rob Pike committed
    	case ']':
    
    		p.re.setError(ErrUnmatchedRbkt);
    
    Rob Pike's avatar
    Rob Pike committed
    	case '^':
    		p.nextc();
    
    		start = p.re.add(new(_Bot));
    
    Rob Pike's avatar
    Rob Pike committed
    		return start, start;
    	case '$':
    		p.nextc();
    
    		start = p.re.add(new(_Eot));
    
    Rob Pike's avatar
    Rob Pike committed
    		return start, start;
    
    	case '.':
    		p.nextc();
    
    		start = p.re.add(new(_Any));
    
    Rob Pike's avatar
    Rob Pike committed
    		return start, start;
    	case '[':
    		p.nextc();
    
    		start = p.charClass();
    
    Rob Pike's avatar
    Rob Pike committed
    		if p.c() != ']' {
    
    			p.re.setError(ErrUnmatchedLbkt);
    
    Rob Pike's avatar
    Rob Pike committed
    		}
    		p.nextc();
    
    		return start, start;
    	case '(':
    		p.nextc();
    
    Rob Pike's avatar
    Rob Pike committed
    		p.re.nbra++;	// increment first so first subexpr is \1
    		nbra := p.re.nbra;
    
    		start, end = p.regexp();
    
    		if p.c() != ')' {
    
    			p.re.setError(ErrUnmatchedLpar);
    
    		p.nextc();
    
    		p.re.add(bra);
    
    		p.re.add(ebra);
    
    Rob Pike's avatar
    Rob Pike committed
    		bra.n = nbra;
    		ebra.n = nbra;
    
    Rob Pike's avatar
    Rob Pike committed
    		if start == iNULL {
    
    			if end == iNULL {
    				p.re.setError(ErrInternal)
    			}
    
    			end.setNext(ebra);
    
    		bra.setNext(start);
    
    	case '\\':
    		c = p.nextc();
    		switch {
    
    Rob Pike's avatar
    Rob Pike committed
    		case c == endOfFile:
    
    			p.re.setError(ErrExtraneousBackslash);
    
    		case c == 'n':
    			c = '\n';
    		case special(c):
    			// c is as delivered
    		default:
    
    			p.re.setError(ErrBadBackslash);
    
    		}
    		fallthrough;
    	default:
    		p.nextc();
    
    Rob Pike's avatar
    Rob Pike committed
    		start = newChar(c);
    
    		p.re.add(start);
    
    		return start, start
    	}
    	panic("unreachable");
    }
    
    
    func (p *parser) closure() (start, end instr) {
    	start, end = p.term();
    
    Rob Pike's avatar
    Rob Pike committed
    	if start == iNULL {
    
    Rob Pike's avatar
    Rob Pike committed
    		return
    
    	}
    	switch p.c() {
    	case '*':
    		// (start,end)*:
    
    		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)+:
    
    		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)?:
    
    		p.re.add(alt);
    
    		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
    
    Rob Pike's avatar
    Rob Pike committed
    		return
    
    	}
    	switch p.nextc() {
    	case '*', '+', '?':
    
    		p.re.setError(ErrBadClosure);
    
    Rob Pike's avatar
    Rob Pike committed
    	return
    
    func (p *parser) concatenation() (start, end instr) {
    
    Rob Pike's avatar
    Rob Pike committed
    	start, end = iNULL, iNULL;
    
    		nstart, nend := p.closure();
    
    Rob Pike's avatar
    Rob Pike committed
    		case nstart == iNULL:	// end of this concatenation
    			if start == iNULL {	// this is the empty string
    
    				nop := p.re.add(new(_Nop));
    
    Rob Pike's avatar
    Rob Pike committed
    				return nop, nop;
    			}
    
    Rob Pike's avatar
    Rob Pike committed
    			return;
    
    Rob Pike's avatar
    Rob Pike committed
    		case start == iNULL:	// 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();
    
    	for {
    		switch p.c() {
    		default:
    
    Rob Pike's avatar
    Rob Pike committed
    			return;
    
    		case '|':
    			p.nextc();
    
    			nstart, nend := p.concatenation();
    
    			p.re.add(alt);
    
    			alt.left = start;
    
    			alt.setNext(nstart);
    
    			p.re.add(nop);
    			end.setNext(nop);
    			nend.setNext(nop);
    
    			start, end = alt, nop;
    
    func unNop(i instr) instr {
    
    	for i.kind() == _NOP {
    		i = i.next()
    
    func (re *Regexp) eliminateNops() {
    
    Rob Pike's avatar
    Rob Pike committed
    	for i := 0; i < re.inst.Len(); i++ {
    
    Rob Pike's avatar
    Rob Pike committed
    		inst := re.inst.At(i).(instr);
    
    		if inst.kind() == _END {
    
    Rob Pike's avatar
    Rob Pike committed
    			continue
    		}
    
    		inst.setNext(unNop(inst.next()));
    		if inst.kind() == _ALT {
    
    			alt := inst.(*_Alt);
    			alt.left = unNop(alt.left);
    
    func (re *Regexp) dump() {
    
    Rob Pike's avatar
    Rob Pike committed
    	for i := 0; i < re.inst.Len(); i++ {
    
    Rob Pike's avatar
    Rob Pike committed
    		inst := re.inst.At(i).(instr);
    
    		print(inst.index(), ": ");
    		inst.print();
    		if inst.kind() != _END {
    			print(" -> ", inst.next().index())
    
    Rob Pike's avatar
    Rob Pike committed
    		print("\n");
    
    func (re *Regexp) doParse() {
    
    Rob Pike's avatar
    Rob Pike committed
    	p := newParser(re);
    
    	re.add(start);
    	s, e := p.regexp();
    	start.setNext(s);
    
    	e.setNext(re.add(new(_End)));
    
    Rob Pike's avatar
    Rob Pike committed
    	if debug {
    
    		re.dump();
    
    Rob Pike's avatar
    Rob Pike committed
    		println();
    	}
    
    	re.eliminateNops();
    
    Rob Pike's avatar
    Rob Pike committed
    	if debug {
    
    		re.dump();
    
    Rob Pike's avatar
    Rob Pike committed
    		println();
    	}
    
    Rob Pike's avatar
    Rob Pike committed
    
    
    func compiler(str string, ch chan *Regexp) {
    	re := new(Regexp);
    
    	re.expr = str;
    
    Rob Pike's avatar
    Rob Pike committed
    	re.inst = vector.New(0);
    
    	re.ch = ch;
    
    	re.doParse();
    
    // 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) {
    
    	// Compile in a separate goroutine and wait for the result.
    	ch := make(chan *Regexp);
    
    	re := <-ch;
    	return re, re.error
    }
    
    Rob Pike's avatar
    Rob Pike committed
    
    
    Rob Pike's avatar
    Rob Pike committed
    type state struct {
    	inst	instr;	// next instruction to execute
    
    Russ Cox's avatar
    Russ Cox committed
    	match	[]int;	// pairs of bracketing submatches. 0th is start,end
    
    Rob Pike's avatar
    Rob Pike committed
    }
    
    // Append new state to to-do list.  Leftmost-longest wins so avoid
    // adding a state that's already active.
    
    Rob Pike's avatar
    Rob Pike committed
    func addState(s []state, inst instr, match []int) []state {
    
    	index := inst.index();
    
    Rob Pike's avatar
    Rob Pike committed
    	l := len(s);
    	pos := match[0];
    	// TODO: Once the state is a vector and we can do insert, have inputs always
    	// go in order correctly and this "earlier" test is never necessary,
    	for i := 0; i < l; i++ {
    
    		if s[i].inst.index() == index && // same instruction
    
    Rob Pike's avatar
    Rob Pike committed
    		   s[i].match[0] < pos {	// earlier match already going; lefmost wins
    		   	return s
    		 }
    	}
    	if l == cap(s) {
    
    Rob Pike's avatar
    Rob Pike committed
    		s1 := make([]state, 2*l)[0:l];
    
    Rob Pike's avatar
    Rob Pike committed
    		for i := 0; i < l; i++ {
    			s1[i] = s[i];
    		}
    		s = s1;
    	}
    	s = s[0:l+1];
    	s[l].inst = inst;
    	s[l].match = match;
    	return s;
    }
    
    
    // Accepts either string or bytes - the logic is identical either way.
    // If bytes == nil, scan str.
    func (re *Regexp) doExecute(str string, bytes []byte, pos int) []int {
    
    Rob Pike's avatar
    Rob Pike committed
    	var s [2][]state;	// TODO: use a vector when state values (not ptrs) can be vector elements
    	s[0] = make([]state, 10)[0:0];
    	s[1] = make([]state, 10)[0:0];
    
    Rob Pike's avatar
    Rob Pike committed
    	in, out := 0, 1;
    
    Rob Pike's avatar
    Rob Pike committed
    	var final state;
    
    Rob Pike's avatar
    Rob Pike committed
    	found := false;
    
    	end := len(str);
    	if bytes != nil {
    		end = len(bytes)
    	}
    	for pos <= end {
    
    Rob Pike's avatar
    Rob Pike committed
    		if !found {
    			// prime the pump if we haven't seen a match yet
    
    Russ Cox's avatar
    Russ Cox committed
    			match := make([]int, 2*(re.nbra+1));
    
    Rob Pike's avatar
    Rob Pike committed
    			for i := 0; i < len(match); i++ {
    				match[i] = -1;	// no match seen; catches cases like "a(b)?c" on "ac"
    			}
    
    Rob Pike's avatar
    Rob Pike committed
    			match[0]  = pos;
    
    			s[out] = addState(s[out], re.start.next(), match);
    
    Rob Pike's avatar
    Rob Pike committed
    		}
    		in, out = out, in;	// old out state is new in state
    		s[out] = s[out][0:0];	// clear out state
    		if len(s[in]) == 0 {
    			// machine has completed
    			break;
    		}
    
    Rob Pike's avatar
    Rob Pike committed
    		charwidth := 1;
    
    Rob Pike's avatar
    Rob Pike committed
    		c := endOfFile;
    
    		if pos < end {
    			if bytes == nil {
    				c, charwidth = utf8.DecodeRuneInString(str[pos:end]);
    			} else {
    				c, charwidth = utf8.DecodeRune(bytes[pos:end]);
    			}
    
    Rob Pike's avatar
    Rob Pike committed
    		}
    		for i := 0; i < len(s[in]); i++ {
    
    Rob Pike's avatar
    Rob Pike committed
    			st := s[in][i];
    
    			switch s[in][i].inst.kind() {
    
    Rob Pike's avatar
    Rob Pike committed
    				if pos == 0 {
    
    					s[in] = addState(s[in], st.inst.next(), st.match)
    
    Rob Pike's avatar
    Rob Pike committed
    				}
    
    					s[in] = addState(s[in], st.inst.next(), st.match)
    
    Rob Pike's avatar
    Rob Pike committed
    				}
    
    			case _CHAR:
    				if c == st.inst.(*_Char).char {
    
    					s[out] = addState(s[out], st.inst.next(), st.match)
    
    Rob Pike's avatar
    Rob Pike committed
    				}
    
    				if st.inst.(*_CharClass).matches(c) {
    					s[out] = addState(s[out], st.inst.next(), st.match)
    
    Rob Pike's avatar
    Rob Pike committed
    				}
    
    Rob Pike's avatar
    Rob Pike committed
    				if c != endOfFile {
    
    					s[out] = addState(s[out], st.inst.next(), st.match)
    
    Rob Pike's avatar
    Rob Pike committed
    				}
    
    			case _NOTNL:
    				if c != endOfFile && c != '\n' {
    					s[out] = addState(s[out], st.inst.next(), st.match)
    				}
    
    			case _BRA:
    				n := st.inst.(*_Bra).n;
    
    Rob Pike's avatar
    Rob Pike committed
    				st.match[2*n] = pos;
    
    				s[in] = addState(s[in], st.inst.next(), st.match);
    
    			case _EBRA:
    				n := st.inst.(*_Ebra).n;
    
    Rob Pike's avatar
    Rob Pike committed
    				st.match[2*n+1] = pos;
    
    				s[in] = addState(s[in], st.inst.next(), st.match);
    
    			case _ALT:
    				s[in] = addState(s[in], st.inst.(*_Alt).left, st.match);
    
    Rob Pike's avatar
    Rob Pike committed
    				// give other branch a copy of this match vector
    
    Russ Cox's avatar
    Russ Cox committed
    				s1 := make([]int, 2*(re.nbra+1));
    
    Rob Pike's avatar
    Rob Pike committed
    				for i := 0; i < len(s1); i++ {
    
    Rob Pike's avatar
    Rob Pike committed
    					s1[i] = st.match[i]
    
    Rob Pike's avatar
    Rob Pike committed
    				}
    
    				s[in] = addState(s[in], st.inst.next(), s1);
    
    Rob Pike's avatar
    Rob Pike committed
    				// choose leftmost longest
    				if !found ||	// first
    
    Rob Pike's avatar
    Rob Pike committed
    				   st.match[0] < final.match[0] ||	// leftmost
    
    				   (st.match[0] == final.match[0] && pos > final.match[1]) {	// longest
    
    Rob Pike's avatar
    Rob Pike committed
    					final = st;
    
    Rob Pike's avatar
    Rob Pike committed
    					final.match[1] = pos;
    				}
    				found = true;
    			default:
    
    				st.inst.print();
    
    Rob Pike's avatar
    Rob Pike committed
    				panic("unknown instruction in execute");
    			}
    		}
    
    Rob Pike's avatar
    Rob Pike committed
    		pos += charwidth;
    
    Rob Pike's avatar
    Rob Pike committed
    	}
    	return final.match;
    }
    
    
    
    // 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.
    
    Rob Pike's avatar
    Rob Pike committed
    // 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)
    
    Rob Pike's avatar
    Rob Pike committed
    }
    
    // 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);
    
    	a = make([]string, len(r)/2);
    
    		if r[i] != -1 {	// -1 means no match for this subexpression
    			a[i/2] = s[r[i] : r[i+1]]
    		}
    
    // 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
    	}
    
    // 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.
    		rune, width := utf8.DecodeRuneInString(src[searchPos:len(src)]);
    		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:len(src)]);
    
    	return string(buf.Data());
    }
    
    
    // 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.
    		rune, width := utf8.DecodeRune(src[searchPos:len(src)]);
    		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:len(src)]);
    
    	return buf.Data();
    }
    
    
    // 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]);
    }