Fixing two instances of unintentional O(n*n) behavior and poor memory use

that occur in horizontal matching of basic text patterns.

* lib.c (match_str, match_str_tree): New functions.

* lib.h (match_str, match_str_tree): Declared.

* match.c (do_match_line): Use match_str_tree and match_str when matching
strings and string lists, respectively, rather than stupidly calling
search functions and then asserting that the match was found at the
starting position.

1 files changed, 35 insertions, 0 deletions

diff --git a/lib.c b/lib.c
index b23b1598..6b80b848 100644
--- a/lib.c
+++ b/lib.c
@@ -1523,6 +1523,41 @@ val search_str_tree(val haystack, val tree, val start_num, val from_end)
   return nil;
 }
 
+val match_str(val bigstr, val str, val pos)
+{
+  val i, p;
+
+  for (i = zero;
+       length_str_gt(bigstr, p = plus(pos, i)) && length_str_gt(str, i);
+       i = plus(i, one))
+  {
+    if (chr_str(bigstr, p) != chr_str(str, i))
+      return nil;
+  }
+
+  return length_str_le(str, i) ? t : nil;
+}
+
+val match_str_tree(val bigstr, val tree, val pos)
+{
+  if (stringp(tree)) {
+    if (match_str(bigstr, tree, pos))
+      return length_str(tree);
+  } else if (consp(tree)) {
+    val maxlen = nil;
+
+    for (; tree; tree = cdr(tree)) {
+      val result = match_str_tree(bigstr, car(tree), pos);
+      if (result && (!maxlen || gt(result, maxlen)))
+        maxlen = result;
+    }
+
+    return maxlen;
+  }
+
+  return nil;
+}
+
 static val lazy_sub_str(val lstr, val from, val to)
 {
   val len = nil;