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, 17 insertions, 0 deletions

diff --git a/lib.c b/lib.c
index 45adedbd..30d7b661 100644
--- a/lib.c
+++ b/lib.c
@@ -364,6 +364,13 @@ val memq(val obj, val list)
   return list;
 }
 
+val memqual(val obj, val list)
+{
+  while (list && !equal(car(list), obj))
+    list = cdr(list);
+  return list;
+}
+
 val tree_find(val obj, val tree)
 {
   if (equal(obj, tree))
@@ -1749,6 +1756,16 @@ val mapcar(val fun, val list)
   return out;
 }
 
+val mapcon(val fun, val list)
+{
+  list_collect_decl (out, iter);
+
+  for (; list; list = cdr(list))
+    list_collect_nconc (iter, funcall1(fun, list));
+
+  return out;
+}
+
 val mappend(val fun, val list)
 {
   list_collect_decl (out, iter);