shithub: libmujs

Info  •  Files  •  Log  •  Branches

Fix issue 66: Stack overflow when compiling long regexp sequences.

The syntax tree for long chains of Cat nodes leaned leftwards, which
made the compile() step potentially run out of stack. If we build the
Cat tree leaning right, we can use an iterative loop instead of
recursion.

--- a/regexp.c

+++ b/regexp.c

@@ -550,16 +550,19 @@

 static Renode *parsecat(struct cstate *g)

 {

-	Renode *cat, *x;

+	Renode *cat, *head, **tail;

 	if (g->lookahead && g->lookahead != '|' && g->lookahead != ')') {

-		cat = parserep(g);

+		/* Build a right-leaning tree by splicing in new 'cat' at the tail. */

+		head = parserep(g);

+		tail = &head;

 		while (g->lookahead && g->lookahead != '|' && g->lookahead != ')') {

-			x = cat;

 			cat = newnode(g, P_CAT);

-			cat->x = x;

+			cat->x = *tail;

 			cat->y = parserep(g);

+			*tail = cat;

+			tail = &cat->y;

 		}

-		return cat;

+		return head;

 	}

 	return NULL;

 }

@@ -636,11 +639,12 @@

 	if (!node)

 		return;

+loop:

 	switch (node->type) {

 	case P_CAT:

 		compile(prog, node->x);

-		compile(prog, node->y);

-		break;

+		node = node->y;

+		goto loop;

 	case P_ALT:

 		split = emit(prog, I_SPLIT);