ref: 44ce0097b612a1fefd754065bdf8d9d2e5ef60c8
dir: /appl/lib/ecmascript/regexp.b/
strhas(s: string, c: int): ref Val
{
for(i := 0; i < len s; i++)
if(s[i] == c)
return true;
return false;
}
rsplit(r: string): (string, string)
{
esc := 0;
i := 1; # skip '/'
for(;;){
c := r[i++];
if(!esc && c == '/')
break;
esc = !esc && c == '\\';
}
return (r[1: i-1], r[i: ]);
}
badflags(f: string): int
{
g := i := m := 0;
for(j := 0; j < len f; j++){
case(f[j]){
'g' =>
g++;
'i' =>
i++;
'm' =>
m++;
* =>
return 1;
}
}
return g > 1 || i > 1 || m > 1;
}
regexpvals(ex: ref Exec, v: ref Val, o: ref Ecmascript->Obj): (string, string, int)
{
if(v != nil){
if(v.ty == TRegExp)
return (v.rev.p, v.rev.f, v.rev.i);
o = v.obj;
}
p := toString(ex, esget(ex, o, "source", 0));
f := "";
if(toBoolean(ex, esget(ex, o, "global", 0)) == true)
f += "g";
if(toBoolean(ex, esget(ex, o, "ignoreCase", 0)) == true)
f += "i";
if(toBoolean(ex, esget(ex, o, "multiline", 0)) == true)
f += "m";
i := toInt32(ex, esget(ex, o, "lastIndex", 0));
return (p, f, i);
}
nregexp(ex: ref Exec, nil: ref Ecmascript->Obj, args: array of ref Val): ref Ecmascript->Obj
{
pat := biarg(args, 0);
flags := biarg(args, 1);
(p, f) := ("", "");
if(isregexp(pat)){
if(flags == undefined)
(p, f, nil) = regexpvals(ex, pat, nil);
else
runtime(ex, TypeError, "flags defined");
}
else{
if(pat == undefined)
p = "";
else
p = toString(ex, pat);
if(flags == undefined)
f = "";
else
f = toString(ex, flags);
}
o := nobj(ex, nil, array[] of { regexpval(p, f, 0) });
if(badflags(f))
runtime(ex, SyntaxError, "bad regexp flags");
regex = ex;
(re, err) := compile(p, 1);
if(re == nil || err != nil)
runtime(ex, SyntaxError, "bad regexp pattern");
o.re = re;
return o;
}
cregexp(ex: ref Exec, f, nil: ref Ecmascript->Obj, args: array of ref Val): ref Val
{
pat := biarg(args, 0);
flags := biarg(args, 1);
if(isregexp(pat) && flags == undefined)
return pat;
return objval(nregexp(ex, f, args));
}
cregexpprotoexec(ex: ref Exec, f, this: ref Ecmascript->Obj, args: array of ref Val): ref Val
{
m: array of (int, int);
regexpcheck(ex, this, f);
s := toString(ex, biarg(args, 0));
l := len s;
i := toInt32(ex, esget(ex, this, "lastIndex", 0));
e := 0;
glob := esget(ex, this, "global", 0);
multiline := esget(ex, this, "multiline", 0);
ignorecase := esget(ex, this, "ignoreCase", 0);
if(glob == false)
i = 0;
for(;;){
if(i < 0 || i >= l){
esput(ex, this, "lastIndex", numval(real 0), 0);
return null;
}
regex = ex;
m = executese(this.re, s, (i, len s), i == 0, 1, multiline == true, ignorecase == true);
if(m != nil)
break;
i++;
i = -1; # no need to loop with executese
}
(i, e) = m[0];
if(glob == true)
esput(ex, this, "lastIndex", numval(real e), 0);
n := len m;
av := array[n] of ref Val;
for(j := 0; j < n; j++){
(a, b) := m[j];
if(a < 0)
av[j] = undefined;
else
av[j] = strval(s[a: b]);
}
a := narray(ex, nil, av);
esput(ex, a, "index", numval(real i), 0);
esput(ex, a, "input", strval(s), 0);
return objval(a);
}
cregexpprototest(ex: ref Exec, f, this: ref Ecmascript->Obj, args: array of ref Val): ref Val
{
regexpcheck(ex, this, f);
v := cregexpprotoexec(ex, f, this, args);
if(!isnull(v))
return true;
return false;
}
cregexpprototoString(ex: ref Exec, f, this: ref Ecmascript->Obj, nil: array of ref Val): ref Val
{
regexpcheck(ex, this, f);
(p, fl, nil) := regexpvals(ex, nil, this);
return strval("/" + p + "/" + fl);
}
regexpcheck(ex: ref Exec, o: ref Ecmascript->Obj, f: ref Obj)
{
if(f == nil)
s := "exec";
else
s = f.val.str;
if(!isregexpobj(o))
runtime(ex, TypeError, "RegExp.prototype." + s + " called on non-RegExp object");
}
cstrprotomatch(ex: ref Exec, nil, this: ref Ecmascript->Obj, args: array of ref Val): ref Val
{
v := biarg(args, 0);
if(!isregexp(v))
re := nregexp(ex, nil, args);
else if(v.ty == TObj)
re = v.obj;
else
re = nobj(ex, nil, args);
s := toString(ex, this.val);
glob := esget(ex, re, "global", 0);
av := array[1] of ref Val;
av[0] = strval(s);
if(glob == false)
return cregexpprotoexec(ex, nil, re, av);
li := 0;
esput(ex, re, "lastIndex", numval(real li), 0);
ms: list of ref Val;
for(;;){
v = cregexpprotoexec(ex, nil, re, av);
if(isnull(v))
break;
ms = esget(ex, v.obj, "0", 0) :: ms;
ni := int toUint32(ex, esget(ex, re, "lastIndex", 0));
if(ni == li)
esput(ex, re, "lastIndex", numval(real ++li), 0);
else
li = ni;
}
n := len ms;
av = array[n] of ref Val;
for(j := n-1; j >= 0; j--){
av[j] = hd ms;
ms = tl ms;
}
return objval(narray(ex, nil, av));
}
cstrprotoreplace(ex: ref Exec, nil, this: ref Ecmascript->Obj, args: array of ref Val): ref Val
{
re: ref Ecmascript->Obj;
v := biarg(args, 0);
rege := isregexp(v);
if(!rege){
if(args == nil)
re = nregexp(ex, nil, args);
else
re = nregexp(ex, nil, args[0:1]);
}
else if(v.ty == TObj)
re = v.obj;
else
re = nobj(ex, nil, args);
s := toString(ex, this.val);
if(rege)
glob := esget(ex, re, "global", 0);
else
glob = false;
av := array[1] of ref Val;
av[0] = strval(s);
ms: list of ref Val;
li := 0;
if(glob == true)
esput(ex, re, "lastIndex", numval(real li), 0);
for(;;){
v = cregexpprotoexec(ex, nil, re, av);
if(!isnull(v))
ms = v :: ms;
if(isnull(v) || glob == false)
break;
ni := int toUint32(ex, esget(ex, re, "lastIndex", 0));
if(ni == li)
esput(ex, re, "lastIndex", numval(real ++li), 0);
else
li = ni;
}
if(ms == nil)
return strval(s);
ms = rev(ms);
if(rege)
lcp := int toUint32(ex, esget(ex, (hd ms).obj, "length", 0))-1;
else
lcp = 0;
v = biarg(args, 1);
if(isobj(v) && isfuncobj(v.obj)){
ns := s;
n := len ms;
args = array[lcp+3] of ref Val;
o := inc := 0;
for(i := 0; i < n; i++){
a := (hd ms).obj;
ms = tl ms;
for(j := 0; j <= lcp; j++)
args[j] = esget(ex, a, string j, 0);
ss := toString(ex, args[0]);
o = offset(ss, s, o);
args[lcp+1] = numval(real o);
args[lcp+2] = strval(s);
rs := toString(ex, getValue(ex, escall(ex, v.obj, nil, args, 0)));
ns = repl(ns, o+inc, o+inc+len ss, rs);
o += len ss;
inc += len rs - len ss;
}
return strval(ns);
}
else{
ps := toString(ex, v);
lps := len ps;
ns := s;
n := len ms;
o := inc := 0;
for(i := 0; i < n; i++){
a := (hd ms).obj;
ms = tl ms;
ss := toString(ex, esget(ex, a, "0", 0));
o = offset(ss, s, o);
rs := "";
for(j := 0; j < lps; j++){
if(ps[j] == '$' && j < lps-1){
j++;
case(c := ps[j]){
'$' =>
rs += "$";
'&' =>
rs += ss;
'`' =>
rs += s[0: o];
''' =>
rs += s[o+len ss: ];
'0' to '9' =>
if(j < lps-1 && isdigit(ps[j+1]))
c = 10*(c-'0')+ps[++j]-'0';
else
c = c-'0';
if(c >= 1 && c <= lcp)
rs += toString(ex, esget(ex, a, string c, 0));
}
}
else
rs += ps[j: j+1];
}
ns = repl(ns, o+inc, o+inc+len ss, rs);
o += len ss;
inc += len rs - len ss;
}
return strval(ns);
}
}
cstrprotosearch(ex: ref Exec, nil, this: ref Ecmascript->Obj, args: array of ref Val): ref Val
{
v := biarg(args, 0);
if(!isregexp(v))
re := nregexp(ex, nil, args);
else if(v.ty == TObj)
re = v.obj;
else
re = nobj(ex, nil, args);
s := toString(ex, this.val);
glob := esget(ex, re, "global", 0);
esput(ex, re, "global", false, 0);
av := array[1] of ref Val;
av[0] = strval(s);
v = cregexpprotoexec(ex, nil, re, av);
if(isnull(v))
r := -1;
else{
ss := toString(ex, esget(ex, v.obj, "0", 0));
r = offset(ss, s, 0);
}
esput(ex, re, "global", glob, 0);
return numval(real r);
}
offset(ss: string, s: string, m: int): int
{
nn := len ss;
n := len s;
for(i := m; i <= n-nn; i++){
if(s[i: i+nn] == ss)
return i;
}
return -1;
}
repl(s: string, a: int, b: int, ns: string): string
{
return s[0: a] + ns + s[b: ];
}
rev(ls: list of ref Val): list of ref Val
{
ns: list of ref Val;
for( ; ls != nil; ls = tl ls)
ns = hd ls :: ns;
return ns;
}
#########################################################################
# regex.b originally
# normally imported identifiers
# internal identifiers, not normally imported
ALT, CAT, DOT, SET, HAT, DOL, NUL, PCLO, CLO, OPT, LPN, RPN, LPN0, RPN0, LPN1, RPN1, LPN2, RPN2, BEET, BEEF, MNCLO, LCP, IDLE: con (1<<16)+iota;
# syntax
# RE ALT regular expression
# NUL
# ALT CAT alternation
# CAT | ALT
#
# CAT DUP catenation
# DUP CAT
#
# DUP PRIM possibly duplicated primary
# PCLO
# CLO
# OPT
#
# PCLO PRIM + 1 or more
# CLO PRIM * 0 or more
# OPT PRIM ? 0 or 1
#
# PRIM ( RE )
# ()
# DOT any character
# CHAR a single character
# ESC escape sequence
# [ SET ] character set
# NUL null string
# HAT beginning of string
# DOL end of string
#
regex: ref Exec;
NIL : con -1; # a refRex constant
NONE: con -2; # ditto, for an un-set value
BAD: con 1<<16; # a non-character
HUGE: con (1<<31) - 1;
# the data structures of re.m would like to be ref-linked, but are
# circular (see fn walk), thus instead of pointers we use indexes
# into an array (arena) of nodes of the syntax tree of a regular expression.
# from a storage-allocation standpoint, this replaces many small
# allocations of one size with one big one of variable size.
ReStr: adt {
s : string;
i : int; # cursor postion
n : int; # number of chars left; -1 on error
peek : fn(s: self ref ReStr): int;
next : fn(s: self ref ReStr): int;
unput: fn(s: self ref ReStr);
};
ReStr.peek(s: self ref ReStr): int
{
if(s.n <= 0)
return BAD;
return s.s[s.i];
}
ReStr.next(s: self ref ReStr): int
{
if(s.n <= 0)
syntax("bad regular expression");
s.n--;
return s.s[s.i++];
}
ReStr.unput(s: self ref ReStr)
{
s.n++;
s.i--;
}
newRe(kind: int, left, right: refRex, set: ref Set, ar: ref Arena, pno: int, greedy: int): refRex
{
ar.rex[ar.ptr] = Rex(kind, left, right, set, pno, greedy, nil);
return ar.ptr++;
}
# parse a regex by recursive descent to get a syntax tree
re(s: ref ReStr, ar: ref Arena): refRex
{
left := cat(s, ar);
if(left==NIL || s.peek()!='|')
return left;
s.next();
right := re(s, ar);
if(right == NIL)
return NIL;
return newRe(ALT, left, right, nil, ar, 0, 0);
}
cat(s: ref ReStr, ar: ref Arena): refRex
{
left := dup(s, ar);
if(left == NIL)
return left;
right := cat(s, ar);
if(right == NIL)
return left;
return newRe(CAT, left, right, nil, ar, 0, 0);
}
dup(s: ref ReStr, ar: ref Arena): refRex
{
n1, n2: int;
case s.peek() {
BAD or ')' or ']' or '|' or '?' or '*' or '+' =>
return NIL;
}
prim: refRex;
case kind:=s.next() {
'(' => if(ar.pno < 0) {
if(s.peek() == ')') {
s.next();
prim = newRe(NUL, NONE, NONE, nil, ar, 0, 0);
} else {
prim = re(s, ar);
if(prim==NIL || s.next()!=')')
syntax("( with no )");
}
} else {
pno := ++ar.pno;
lp := newRe(LPN, NONE, NONE, nil, ar, pno, 0);
rp := newRe(RPN, NONE, NONE, nil, ar, pno, 0);
if(s.peek() == ')') {
s.next();
prim = newRe(CAT, lp, rp, nil, ar, 0, 0);
} else {
if(s.peek() == '?'){
s.next();
case s.next(){
':' => ar.rex[lp].kind = LPN0;
ar.rex[rp].kind = RPN0;
'=' => ar.rex[lp].kind = LPN1;
ar.rex[rp].kind = RPN1;
'!' => ar.rex[lp].kind = LPN2;
ar.rex[rp].kind = RPN2;
* => syntax("bad char after ?");
}
}
prim = re(s, ar);
if(prim==NIL || s.next()!=')')
syntax("( with no )");
else {
prim = newRe(CAT, prim, rp, nil, ar, 0, 0);
prim = newRe(CAT, lp, prim, nil, ar, 0, 0);
}
}
}
'[' => prim = newRe(SET, NONE, NONE, newSet(s), ar, 0, 0);
* => case kind {
'.' => kind = DOT;
'^' => kind = HAT;
'$' => kind = DOL;
}
(c, set, op) := esc(s, kind, 0);
if(set != nil)
prim = newRe(SET, NONE, NONE, set, ar, 0, 0);
else if(op == LCP){
if(c > ar.pno)
syntax("\num too big");
prim = newRe(LCP, NONE, NONE, nil, ar, 0, 0);
ar.rex[prim].ns = ref Nstate(c, c);
}
else
prim = newRe(c, NONE, NONE, nil, ar, 0, 0);
}
case s.peek() {
'*' => kind = CLO;
'+' => kind = PCLO;
'?' => kind = OPT;
'{' => s.next();
(n1, n2) = drange(s);
kind = MNCLO;
if(s.peek() != '}')
syntax("{ with no }");
* => return prim;
}
s.next();
greedy := 1;
if(s.peek() == '?'){
# non-greedy op
greedy = 0;
s.next();
}
prim = newRe(kind, prim, NONE, nil, ar, 0, greedy);
if(kind == MNCLO)
ns := ar.rex[prim].ns = ref Nstate(n1, n2);
return prim;
}
esc(s: ref ReStr, char: int, inset: int): (int, ref Set, int)
{
set: ref Set;
op := 0;
if(char == '\\') {
char = s.next();
case char {
'b' =>
if(inset)
char = '\b';
else
char = BEET;
'B' => if(inset)
syntax("\\B in set");
else
char = BEEF;
'f' => char = '\u000c';
'n' => char = '\n';
'r' => char = '\r';
't' => char = '\t';
'v' => char = '\v';
'0' to '9' =>
s.unput();
char = digits(s);
if(char == 0)
char = '\0';
else if(inset)
syntax("\num in set");
else
op = LCP;
'x' => char = hexdigits(s, 2);
'u' => char = hexdigits(s, 4);
'c' => char = s.next()%32;
'd' or 'D' =>
set = newset('0', '9');
if(char == 'D')
set.neg = 1;
's' or 'S' =>
set = newset(' ', ' ');
addsets(set, "\t\v\u000c\u00a0\n\r\u2028\u2029");
if(char == 'S')
set.neg = 1;
'w' or 'W' =>
set = newset('0', '9');
addset(set, 'a', 'z');
addset(set, 'A', 'Z');
addset(set, '_', '_');
if(char == 'W')
set.neg = 1;
* =>
;
}
}
if(char == -1){
if(inset)
syntax("bad set");
else
syntax("bad character");
}
return (char, set, op);
}
isdigit(c: int): int
{
return c >= '0' && c <= '9';
}
islower(c: int): int
{
return c >= 'a' && c <= 'z';
}
isupper(c: int): int
{
return c >= 'A' && c <= 'Z';
}
isalpha(c: int): int
{
return islower(c) || isupper(c);
}
hexdigit(c: int): int
{
if(isdigit(c))
return c-'0';
if('a' <= c && c <= 'f')
return c-'a'+10;
if('A' <= c && c <= 'F')
return c-'A'+10;
return -1;
}
digits(s: ref ReStr): int
{
n := 0;
while(isdigit(s.peek()))
n = 10*n + s.next() -'0';
return n;
}
hexdigits(s: ref ReStr, n: int): int
{
x := 0;
for(i := 0; i < n; i++){
v := hexdigit(s.next());
if(v < 0)
return -1;
x = 16*x+v;
}
return x;
}
drange(s: ref ReStr): (int, int)
{
n1 := n2 := -1;
if(isdigit(s.peek()))
n1 = digits(s);
if(s.peek() == ','){
s.next();
if(isdigit(s.peek()))
n2 = digits(s);
else
n2 = HUGE;
}
else
n2 = n1;
if(n1 < 0 || n1 > n2)
syntax("bad number range");
return (n1, n2);
}
# walk the tree adjusting pointers to refer to
# next state of the finite state machine
walk(r: refRex, succ: refRex, ar: ref Arena)
{
if(r==NONE)
return;
rex := ar.rex[r];
case rex.kind {
ALT => walk(rex.left, succ, ar);
walk(rex.right, succ, ar);
return;
CAT => walk(rex.left, rex.right, ar);
walk(rex.right, succ, ar);
ar.rex[r] = ar.rex[rex.left]; # optimization
return;
CLO or PCLO =>
end := newRe(OPT, r, succ, nil, ar, 0, rex.greedy); # here's the circularity
walk(rex.left, end, ar);
OPT => walk(rex.left, succ, ar);
MNCLO =>
ar.ptr++;
walk(rex.left, r, ar);
LCP =>
ar.rex[r].left = newRe(IDLE, NONE, succ, nil, ar, 0, 0);
}
ar.rex[r].right = succ;
}
prtree(r: refRex, ar: ref Arena, done: list of int, ind: string): list of int
{
sys->print("%s", ind);
if(r==NIL){
sys->print("NIL\n");
return done;
}
if(r==NONE){
sys->print("NONE\n");
return done;
}
printed := 0;
for(li := done; li != nil; li = tl li){
if(hd li == r){
printed = 1;
break;
}
}
rex := ar.rex[r];
op := "";
z := "Z";
case rex.kind{
ALT => op = "|";
CAT => op = "and";
DOT => op = ".";
SET => op = "[]";
HAT => op = "^";
DOL => op = "$";
NUL => op = "NUL";
PCLO => op = "+";
CLO => op = "*";
OPT => op = "?";
LPN => op = "(";
RPN => op = ")";
LPN0 => op = "?:";
RPN0 => op = ":?";
LPN1 => op = "?=";
RPN1 => op = "=?";
LPN2 => op = "?!";
RPN2 => op = "!?";
BEET => op = "\\b";
BEEF => op = "\\B";
MNCLO => op = "{}";
LCP => op = "n";
IDLE => op = "i";
* => z[0] = rex.kind; op = z;
}
if(printed){
sys->print("node %d (%d)\n", r, r);
return done;
}
else{
if(rex.ns != nil)
sys->print("%s [%d-%d] (%d)\n", op, rex.ns.m, rex.ns.n, r);
else
sys->print("%s (%d)\n", op, r);
done = r :: done;
ind += " ";
done = prtree(rex.left, ar, done, ind);
done = prtree(rex.right, ar, done, ind);
return done;
}
}
compile(e: string, flag: int): (Re, string)
{
if(e == nil)
return (nil, "missing expression");
s := ref ReStr(e, 0, len e);
ar := ref Arena(array[2*s.n] of Rex, 0, 0, (flag&1)-1);
start := ar.start = re(s, ar);
if(start==NIL || s.n!=0)
syntax("invalid regular expression");
walk(start, NIL, ar);
# prtree(start, ar, nil, "");
if(ar.pno < 0)
ar.pno = 0;
return (ar, nil);
}
# todo: queue for epsilon and advancing transitions
Num: adt{
ns: ref Nstate;
m: int;
n: int;
};
Gaz: adt {
pno: int;
beg: int;
end: int;
};
Trace: adt {
cre: refRex; # cursor in Re
trans: int; # 0 epsilon transition, 1 advancing transition
beg: int; # where this trace began;
end: int; # where this trace ended if success (-1 by default)
gaz: list of Gaz;
ns: list of ref Num;
};
Queue: adt {
ptr: int;
q: array of Trace;
};
execute(re: Re, s: string): array of (int, int)
{
return executese(re, s, (-1,-1), 1, 1, 1, 0);
}
executese(re: Re, s: string, range: (int, int), bol: int, eol: int, multiline: int, ignorecase: int): array of (int,int)
{
if(re==nil)
return nil;
(s0, s1) := range;
if(s0 < 0)
s0 = 0;
if(s1 < 0)
s1 = len s;
match := 0;
todo := ref Queue(0, array[2*re.ptr] of Trace);
for(i:=s0; i<=s1; i++) {
if(!match) # no leftmost match yet
todo.q[todo.ptr++] = Trace(re.start, 0, i, -1, nil, nil);
for(k:=0; k<todo.ptr; k++) {
q := todo.q[k];
if(q.trans)
continue;
rex := re.rex[q.cre];
next0 := next1 := next2 := NONE;
case rex.kind {
NUL =>
next1 = rex.right;
DOT =>
if(i<len s && !islt(s[i]))
next2 = rex.right;
HAT =>
if(i == s0 && bol)
next1 = rex.right;
else if(multiline && i > 0 && islt(s[i-1]))
next1 = rex.right;
DOL =>
if(i == s1 && eol)
next1 = rex.right;
else if(multiline && i < s1 && islt(s[i]))
next1 = rex.right;
SET =>
if(i<len s && member(s[i], rex.set, ignorecase))
next2 = rex.right;
CAT or
PCLO =>
next1 = rex.left;
ALT or
CLO or
OPT =>
if(rex.kind == ALT || rex.greedy){
next0 = rex.left;
next1 = rex.right;
}
else{
next0 = rex.right;
next1 = rex.left;
}
LPN =>
next1 = rex.right;
q.gaz = Gaz(rex.pno,i,-1)::q.gaz;
RPN =>
next1 = rex.right;
for(r:=q.gaz; ; r=tl r) {
(pno,beg1,end1) := hd r;
if(rex.pno==pno && end1==-1) {
q.gaz = Gaz(pno,beg1,i)::q.gaz;
break;
}
}
LPN0 or RPN0 or RPN1 or RPN2 =>
next1 = rex.right;
LPN1 =>
(rpn, nxt, nre) := storetree(q.cre, re);
m := executese(nre, s, (i, -1), bol, eol, multiline, ignorecase);
if(m != nil && m[0].t0 == i){
next1 = nxt;
for(j := 1; j < len m; j++)
if(m[j].t0 >= 0)
q.gaz = Gaz(j, m[j].t0, m[j].t1)::q.gaz;
}
restoretree(LPN1, rpn, nxt, nre);
LPN2 =>
(rpn, nxt, nre) := storetree(q.cre, re);
m := executese(nre, s, (i, -1), bol, eol, multiline, ignorecase);
if(m == nil || m[0].t0 != i)
next1 = nxt;
restoretree(LPN2, rpn, nxt, nre);
MNCLO =>
num: ref Num;
(q.ns, num) = nextn(q.cre, q.ns, rex.ns.m, rex.ns.n, re);
if(num.m > 0)
next1 = rex.left;
else if(num.n > 0){
if(rex.greedy){
next0 = rex.left;
next1 = rex.right;
}
else{
next0 = rex.right;
next1 = rex.left;
}
}
else{
next1 = rex.right;
(num.m, num.n) = (-1, -1);
}
LCP =>
pno := rex.ns.m;
(beg1, end1) := lcpar(q.gaz, pno);
l := end1-beg1;
if(beg1 < 0) # undefined so succeeds
next1 = rex.right;
else if(i+l <= s1 && eqstr(s[beg1: end1], s[i: i+l], ignorecase)){
(q.ns, nil) = nextn(rex.left, q.ns, l, l, re);
next1 = rex.left; # idle
}
IDLE =>
num: ref Num;
(q.ns, num) = nextn(q.cre, q.ns, -1, -1, re);
if(num.m >= 0)
next2 = q.cre;
else{
next1 = rex.right;
(num.m, num.n) = (-1, -1);
}
BEET =>
if(iswordc(s, i-1) != iswordc(s, i))
next1 = rex.right;
BEEF =>
if(iswordc(s, i-1) == iswordc(s, i))
next1 = rex.right;
* =>
if(i<len s && (rex.kind==s[i] || (ignorecase && eqcase(rex.kind, s[i]))))
next2 = rex.right;
}
l := k;
if(next0 != NONE) {
if(next0 != NIL)
(k, l) = insert(next0, 0, q.beg, -1, q.gaz, q.ns, todo, k, l);
else{
match = 1;
(k, l) = insert(NIL, 2, q.beg, i, q.gaz, nil, todo, k, l);
}
}
if(next1 != NONE) {
if(next1 != NIL)
(k, l) = insert(next1, 0, q.beg, -1, q.gaz, q.ns, todo, k, l);
else{
match = 1;
(k, l) = insert(NIL, 2, q.beg, i, q.gaz, nil, todo, k, l);
}
}
if(next2 != NONE) {
if(next2 != NIL)
(k, l) = insert(next2, 1, q.beg, -1, q.gaz, q.ns, todo, k, l);
else{
match = 1;
(k, l) = insert(NIL, 2, q.beg, i+1, q.gaz, nil, todo, k, l);
}
}
}
if(!atoe(todo) && match)
break;
}
if(todo.ptr == 0)
return nil;
if(todo.ptr > 1)
rfatal(sys->sprint("todo.ptr = %d", todo.ptr));
if(todo.q[0].trans != 2)
rfatal(sys->sprint("trans = %d", todo.q[0].trans));
if(todo.q[0].cre != NIL)
rfatal(sys->sprint("cre = %d", todo.q[0].cre));
beg := todo.q[0].beg;
end := todo.q[0].end;
gaz := todo.q[0].gaz;
if(beg == -1)
return nil;
result := array[re.pno+1] of { 0 => (beg,end), * => (-1,-1) };
for( ; gaz!=nil; gaz=tl gaz) {
(pno, beg1, end1) := hd gaz;
(rbeg, nil) := result[pno];
if(rbeg==-1 && (beg1|end1)!=-1)
result[pno] = (beg1,end1);
}
return result;
}
better(newbeg, newend, oldbeg, oldend: int): int
{
return oldbeg==-1 || newbeg<oldbeg ||
newbeg==oldbeg && newend>oldend;
}
insert(next: refRex, trans: int, tbeg: int, tend: int, tgaz: list of Gaz, tns: list of ref Num, todo: ref Queue, k: int, l: int): (int, int)
{
# sys->print("insert %d eps=%d beg=%d end=%d (k, l) = (%d %d) => ", next, trans, tbeg, tend, k, l);
for(j:=0; j<todo.ptr; j++){
if(todo.q[j].trans == trans){
if(todo.q[j].cre == next){
if(better(todo.q[j].beg, todo.q[j].end, tbeg, tend))
return (k, l);
else if(better(tbeg, tend, todo.q[j].beg, todo.q[j].end))
break;
else if(j < k)
return (k, l);
else
break;
}
}
}
if(j < k){
k--;
l--;
}
if(j < todo.ptr){
todo.q[j: ] = todo.q[j+1: todo.ptr];
todo.ptr--;
}
todo.q[l+2: ] = todo.q[l+1: todo.ptr];
todo.ptr++;
todo.q[l+1] = Trace(next, trans, tbeg, tend, tgaz, tns);
# for(j=0; j < todo.ptr; j++) sys->print("%d(%d) ", todo.q[j].cre, todo.q[j].trans); sys->print("\n");
return (k, l+1);
}
# remove epsilon transitions and move advancing transitions to epsilon ones
atoe(todo: ref Queue): int
{
n := 0;
for(j := 0; j < todo.ptr; j++){
if(todo.q[j].trans){
if(todo.q[j].trans == 1){
todo.q[j].trans = 0;
n++;
}
}
else{
todo.q[j: ] = todo.q[j+1: todo.ptr];
todo.ptr--;
j--;
}
}
return n;
}
nextn(re: int, ln: list of ref Num, m: int, n: int, ar: ref Arena): (list of ref Num, ref Num)
{
num: ref Num;
ns := ar.rex[re].ns;
for(l := ln; l != nil; l = tl l){
if((hd l).ns == ns){
num = hd l;
break;
}
}
if(num == nil)
ln = (num = ref Num(ns, -1, -1)) :: ln;
if(num.m == -1 && num.n == -1)
(num.m, num.n) = (m, n);
else
(nil, nil) = (--num.m, --num.n);
return (ln, num);
}
ASCII : con 128;
WORD : con 32;
mem(c: int, set: ref Set): int
{
return (set.ascii[c/WORD]>>c%WORD)&1;
}
member(char: int, set: ref Set, ignorecase: int): int
{
if(set.subset != nil){
for(l := set.subset; l != nil; l = tl l)
if(member(char, hd l, ignorecase))
return !set.neg;
}
if(char < 128){
if(ignorecase)
return (mem(tolower(char), set) || mem(toupper(char), set))^set.neg;
else
return ((set.ascii[char/WORD]>>char%WORD)&1)^set.neg;
}
for(l:=set.unicode; l!=nil; l=tl l) {
(beg, end) := hd l;
if(char>=beg && char<=end)
return !set.neg;
}
return set.neg;
}
newSet(s: ref ReStr): ref Set
{
op: int;
set0: ref Set;
set := ref Set(0, array[ASCII/WORD] of {* => 0}, nil, nil);
if(s.peek() == '^') {
set.neg = 1;
s.next();
}
while(s.n > 0) {
char1 := s.next();
if(char1 == ']')
return set;
(char1, set0, op) = esc(s, char1, 1);
if(set0 != nil)
mergeset(set, set0);
char2 := char1;
if(s.peek() == '-') {
if(set0 != nil)
syntax("set in range");
s.next();
char2 = s.next();
if(char2 == ']')
break;
(char2, set0, op) = esc(s, char2, 1);
if(set0 != nil)
syntax("set in range");
if(char2 < char1)
break;
}
addset(set, char1, char2);
}
syntax("bad set");
return nil;
}
addset(set: ref Set, c1: int, c2: int)
{
for(c := c1; c <= c2; c++){
if(c < ASCII)
set.ascii[c/WORD] |= 1<<c%WORD;
else{
set.unicode = (c, c2) :: set.unicode;
break;
}
}
}
addsets(set: ref Set, s: string)
{
for(i := 0; i < len s; i++)
addset(set, s[i], s[i]);
}
mergeset(set: ref Set, set0: ref Set)
{
if(!set0.neg){
for(i := 0; i < ASCII/WORD; i++)
set.ascii[i] |= set0.ascii[i];
for(l := set0.unicode; l != nil; l = tl l)
set.unicode = hd l :: set.unicode;
}
else
set.subset = set0 :: set.subset;
}
newset(c1: int, c2: int): ref Set
{
set := ref Set(0, array[ASCII/WORD] of {* => 0}, nil, nil);
addset(set, c1, c2);
return set;
}
storetree(lpn: int, re: ref Arena): (int, int, ref Arena)
{
rpn: int;
rex := re.rex[lpn];
k := rex.kind;
l := 1;
for(;;){
rpn = rex.right;
rex = re.rex[rpn];
if(rex.kind == k)
l++;
else if(rex.kind == k+1 && --l == 0)
break;
}
re.rex[lpn].kind = LPN;
re.rex[rpn].kind = RPN;
nxt := re.rex[rpn].right;
re.rex[rpn].right = NIL;
nre := ref *re;
nre.start = lpn;
return (rpn, nxt, nre);
}
restoretree(lop: int, rpn: int, nxt: int, re: ref Arena)
{
lpn := re.start;
re.rex[lpn].kind = lop;
re.rex[rpn].kind = lop+1;
re.rex[rpn].right = nxt;
}
iswordc(s: string, i: int): int
{
if(i < 0 || i >= len s)
return 0;
c := s[i];
return isdigit(c) || isalpha(c) || c == '_';
}
lcpar(gaz: list of Gaz, pno: int): (int, int)
{
for(r := gaz; r != nil; r = tl r) {
(pno1, beg1, end1) := hd r;
if(pno == pno1)
return (beg1, end1);
}
return (-1, -1);
}
eqstr(s: string, t: string, ic: int): int
{
if(!ic)
return s == t;
if(len s != len t)
return 0;
for(i := 0; i < len s; i++)
if(!eqcase(s[i], t[i]))
return 0;
return 1;
}
eqcase(c1: int, c2: int): int
{
return toupper(c1) == toupper(c2);
}
syntax(s: string)
{
runtime(regex, SyntaxError, s);
}
rfatal(s: string)
{
runtime(regex, InternalError, s);
}