summaryrefslogtreecommitdiff
path: root/appl/lib/ecmascript/regexp.b
diff options
context:
space:
mode:
Diffstat (limited to 'appl/lib/ecmascript/regexp.b')
-rw-r--r--appl/lib/ecmascript/regexp.b1286
1 files changed, 1286 insertions, 0 deletions
diff --git a/appl/lib/ecmascript/regexp.b b/appl/lib/ecmascript/regexp.b
new file mode 100644
index 00000000..945e0cc5
--- /dev/null
+++ b/appl/lib/ecmascript/regexp.b
@@ -0,0 +1,1286 @@
+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);
+}
generated by cgit v1.2.3 (git 2.46.0) at 2025-12-10 11:57:38 +0000