Optimization in derivative-based regex engine.

Exponential memory consumption behavior was observed when
matching the input aaaaaa....
against the regex a?a?a?a?....aaaa....
The fix is to eliminate common subexpressions
from the derivative for the or operator.

1 files changed, 2 insertions, 0 deletions

diff --git a/lib.h b/lib.h
index 85e21374..55f0ba6d 100644
--- a/lib.h
+++ b/lib.h
@@ -261,6 +261,7 @@ val append2(val list1, val list2);
 val nappend2(val list1, val list2);
 val flatten(val list);
 val memq(val obj, val list);
+val memqual(val obj, val list);
 val tree_find(val obj, val tree);
 val some_satisfy(val list, val pred, val key);
 val all_satisfy(val list, val pred, val key);
@@ -365,6 +366,7 @@ val alist_remove1(val list, val key);
 val copy_cons(val cons);
 val copy_alist(val list);
 val mapcar(val fun, val list);
+val mapcon(val fun, val list);
 val mappend(val fun, val list);
 val merge(val list1, val list2, val lessfun, val keyfun);
 val sort(val list, val lessfun, val keyfun);