path: root/src/pkg/testing/regexp.go

// 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.

// The testing package implements a simple regular expression library.
// It is a reduced version of the regular expression package suitable
// for use in tests; it avoids many dependencies.
//
// The syntax of the regular expressions accepted is:
//
//	regexp:
//		concatenation { '|' concatenation }
//	concatenation:
//		{ closure }
//	closure:
//		term [ '*' | '+' | '?' ]
//	term:
//		'^'
//		'$'
//		'.'
//		character
//		'[' [ '^' ] character-ranges ']'
//		'(' regexp ')'
//

package testing

import (
	"utf8";
)

var debug = false

// Error codes returned by failures to parse an expression.
var (
	ErrInternal		= "internal error";
	ErrUnmatchedLpar	= "unmatched ''";
	ErrUnmatchedRpar	= "unmatched ''";
	ErrUnmatchedLbkt	= "unmatched '['";
	ErrUnmatchedRbkt	= "unmatched ']'";
	ErrBadRange		= "bad range in character class";
	ErrExtraneousBackslash	= "extraneous backslash";
	ErrBadClosure		= "repeated closure **, ++, etc.";
	ErrBareClosure		= "closure applies to nothing";
	ErrBadBackslash		= "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 }

// The representation of a compiled regular expression.
// The public interface is entirely through methods.
type Regexp struct {
	expr	string;	// the original expression
	inst	[]instr;
	start	instr;
	nbra	int;	// number of brackets in expression, for subexpressions
}

const (
	_START	=	// beginning of program
	iota;
	_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])
	// stored pairwise: [a-z] is (a,z); x is (x,x):
	ranges	[]int;
}

func (cclass *_CharClass) kind() int	{ return _CHARCLASS }

func (cclass *_CharClass) print() {
	print("charclass");
	if cclass.negate {
		print(" (negated)")
	}
	for i := 0; i < len(cclass.ranges); i += 2 {
		l := cclass.ranges[i];
		r := cclass.ranges[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
	n := len(cclass.ranges);
	if n >= cap(cclass.ranges) {
		nr := make([]int, n, 2*n);
		for i, j := range nr {
			nr[i] = j
		}
		cclass.ranges = nr;
	}
	cclass.ranges = cclass.ranges[0 : n+2];
	cclass.ranges[n] = a;
	n++;
	cclass.ranges[n] = b;
	n++;
}

func (cclass *_CharClass) matches(c int) bool {
	for i := 0; i < len(cclass.ranges); i = i + 2 {
		min := cclass.ranges[i];
		max := cclass.ranges[i+1];
		if min <= c && c <= max {
			return !cclass.negate
		}
	}
	return cclass.negate;
}

func newCharClass() *_CharClass {
	c := new(_CharClass);
	c.ranges = make([]int, 0, 20);
	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 {
	n := len(re.inst);
	i.setIndex(len(re.inst));
	if n >= cap(re.inst) {
		ni := make([]instr, n, 2*n);
		for i, j := range re.inst {
			ni[i] = j
		}
		re.inst = ni;
	}
	re.inst = re.inst[0 : n+1];
	re.inst[n] = i;
	return i;
}

type parser struct {
	re	*Regexp;
	error	string;
	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:len(p.re.expr)]);
		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 {
	s := `\.+*?()|[]^$`;
	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 {
	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 && len(cc.ranges) == 2 &&
				cc.ranges[0] == '\n' && cc.ranges[1] == '\n' {
				nl := new(_NotNl);
				p.re.add(nl);
				return nl;
			}
			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 != "" {
		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 != "" {
			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 != "" {
		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 != "" {
			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 != "" {
		return
	}
	for {
		switch p.c() {
		default:
			return
		case '|':
			p.nextc();
			nstart, nend := p.concatenation();
			if p.error != "" {
				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 < len(re.inst); i++ {
		inst := re.inst[i];
		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) doParse() string {
	p := newParser(re);
	start := new(_Start);
	re.add(start);
	s, e := p.regexp();
	if p.error != "" {
		return p.error
	}
	start.setNext(s);
	re.start = start;
	e.setNext(re.add(new(_End)));
	re.eliminateNops();
	return p.error;
}

// CompileRegexp parses a regular expression and returns, if successful, a Regexp
// object that can be used to match against text.
func CompileRegexp(str string) (regexp *Regexp, error string) {
	regexp = new(Regexp);
	regexp.expr = str;
	regexp.inst = make([]instr, 0, 20);
	error = regexp.doParse();
	return;
}

// MustCompileRegexp is like CompileRegexp 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 := CompileRegexp(str);
	if error != "" {
		panicln(`regexp: compiling "`, str, `": `, error)
	}
	return regexp;
}

type state struct {
	inst	instr;	// next instruction to execute
	match	[]int;	// pairs of bracketing submatches. 0th is start,end
}

// Append new state to to-do list.  Leftmost-longest wins so avoid
// adding a state that's already active.
func addState(s []state, inst instr, match []int) []state {
	index := inst.index();
	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
			s[i].match[0] < pos {	// earlier match already going; lefmost wins
			return s
		}
	}
	if l == cap(s) {
		s1 := make([]state, 2*l)[0:l];
		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 {
	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];
	in, out := 0, 1;
	var final state;
	found := false;
	end := len(str);
	if bytes != nil {
		end = len(bytes)
	}
	for pos <= end {
		if !found {
			// prime the pump if we haven't seen a match yet
			match := make([]int, 2*(re.nbra+1));
			for i := 0; i < len(match); i++ {
				match[i] = -1	// no match seen; catches cases like "a(b)?c" on "ac"
			}
			match[0] = pos;
			s[out] = addState(s[out], re.start.next(), match);
		}
		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
		}
		charwidth := 1;
		c := endOfFile;
		if pos < end {
			if bytes == nil {
				c, charwidth = utf8.DecodeRuneInString(str[pos:end])
			} else {
				c, charwidth = utf8.DecodeRune(bytes[pos:end])
			}
		}
		for i := 0; i < len(s[in]); i++ {
			st := s[in][i];
			switch s[in][i].inst.kind() {
			case _BOT:
				if pos == 0 {
					s[in] = addState(s[in], st.inst.next(), st.match)
				}
			case _EOT:
				if pos == end {
					s[in] = addState(s[in], st.inst.next(), st.match)
				}
			case _CHAR:
				if c == st.inst.(*_Char).char {
					s[out] = addState(s[out], st.inst.next(), st.match)
				}
			case _CHARCLASS:
				if st.inst.(*_CharClass).matches(c) {
					s[out] = addState(s[out], st.inst.next(), st.match)
				}
			case _ANY:
				if c != endOfFile {
					s[out] = addState(s[out], st.inst.next(), st.match)
				}
			case _NOTNL:
				if c != endOfFile && c != '\n' {
					s[out] = addState(s[out], st.inst.next(), st.match)
				}
			case _BRA:
				n := st.inst.(*_Bra).n;
				st.match[2*n] = pos;
				s[in] = addState(s[in], st.inst.next(), st.match);
			case _EBRA:
				n := st.inst.(*_Ebra).n;
				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);
				// give other branch a copy of this match vector
				s1 := make([]int, 2*(re.nbra+1));
				for i := 0; i < len(s1); i++ {
					s1[i] = st.match[i]
				}
				s[in] = addState(s[in], st.inst.next(), s1);
			case _END:
				// choose leftmost longest
				if !found ||	// first
					st.match[0] < final.match[0] ||	// leftmost
					(st.match[0] == final.match[0] && pos > final.match[1]) {	// longest
					final = st;
					final.match[1] = pos;
				}
				found = true;
			default:
				st.inst.print();
				panic("unknown instruction in execute");
			}
		}
		pos += charwidth;
	}
	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.
// 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 string) {
	re, err := CompileRegexp(pattern);
	if err != "" {
		return false, err
	}
	return re.MatchString(s), "";
}

// 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 string) {
	re, err := CompileRegexp(pattern);
	if err != "" {
		return false, err
	}
	return re.Match(b), "";
}