4 files changed, 46 insertions, 16 deletions
diff --git a/ChangeLog b/ChangeLog
index 553f3b26..69f49eb2 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,23 @@
 2011-10-04  Kaz Kylheku  <kaz@kylheku.com>
 
+	* lib.c (acons): New function.
+	(set_diff): Optimize common case: list1 and list2
+	are the same, or list2 is substructure of list1.
+	Situations in which this won't be the case for variable bindings are
+	rare.
+
+	* lib.h (acons): Declared.
+
+	* match.c (match_line): Use acons rather than acons_new, when binding
+	variables that we know are new (the symbol is unbound). 
+	When computing the set difference over bindings, use cons cell
+	equality, rather than symbol equality. Symbol equality is wrong
+	because a binding can be removed, and then a new binding can be
+	introduced using the same symbol. This must be treated as
+	a different binding.
+
+2011-10-04  Kaz Kylheku  <kaz@kylheku.com>
+
 	Bugfixes to the semantics of binding environments, which
 	were broken in the face of deletions (local, forget).
 	For some stupid reason, I had written a destructive routine for
diff --git a/lib.c b/lib.c
index 9ed67c57..4e54280a 100644
--- a/lib.c
+++ b/lib.c
@@ -1864,6 +1864,11 @@ val assoc(val list, val key)
   return nil;
 }
 
+val acons(val list, val car, val cdr)
+{
+  return cons(cons(car, cdr), list);
+}
+
 val acons_new(val list, val key, val value)
 {
   val existing = assoc(list, key);
@@ -2073,11 +2078,17 @@ val set_diff(val list1, val list2, val testfun, val keyfun)
     testfun = equal_f;
 
   for (; list1; list1 = cdr(list1)) {
-    val item = car(list1);
-    val list1_key = funcall1(keyfun, item);
+    /* optimization: list2 is a tail of list1, and so we
+       are done, unless the application has a weird test function. */
+    if (list1 == list2) {
+      break;
+    } else {
+      val item = car(list1);
+      val list1_key = funcall1(keyfun, item);
 
-    if (!find(list2, list1_key, testfun, keyfun))
-      list_collect (ptail, item);
+      if (!find(list2, list1_key, testfun, keyfun))
+        list_collect (ptail, item);
+    }
   }
 
   return out;
diff --git a/lib.h b/lib.h
index 6dd743f9..d1323f23 100644
--- a/lib.h
+++ b/lib.h
@@ -376,6 +376,7 @@ val cobj(mem_t *handle, val cls_sym, struct cobj_ops *ops);
 val cobjp(val obj);
 mem_t *cobj_handle(val cobj, val cls_sym);
 val assoc(val list, val key);
+val acons(val list, val car, val cdr);
 val acons_new(val list, val key, val value);
 val *acons_new_l(val *list, val key, val *new_p);
 val alist_remove(val list, val keys);
diff --git a/match.c b/match.c
index 75e3bb0f..a5dbaacd 100644
--- a/match.c
+++ b/match.c
@@ -353,7 +353,7 @@ static val match_line(val bindings, val specline, val dataline,
               return nil;
             }
             LOG_MATCH("var positive regex", past);
-            bindings = acons_new(bindings, sym, sub_str(dataline, pos, past));
+            bindings = acons(bindings, sym, sub_str(dataline, pos, past));
             pos = past;
             /* This may have another variable attached */
             if (pat) {
@@ -368,7 +368,7 @@ static val match_line(val bindings, val specline, val dataline,
               return nil;
             }
             LOG_MATCH("count based var", past);
-            bindings = acons_new(bindings, sym, trim_str(sub_str(dataline, pos, past)));
+            bindings = acons(bindings, sym, trim_str(sub_str(dataline, pos, past)));
             pos = past;
             /* This may have another variable attached */
             if (pat) {
@@ -379,7 +379,7 @@ static val match_line(val bindings, val specline, val dataline,
             sem_error(spec_lineno, lit("invalid modifier ~s on variable ~s"),
                       modifier, sym, nao);
           } else if (pat == nil) { /* no modifier, no elem -> to end of line */
-            bindings = acons_new(bindings, sym, sub_str(dataline, pos, nil));
+            bindings = acons(bindings, sym, sub_str(dataline, pos, nil));
             pos = length_str(dataline);
           } else if (type(pat) == STR) {
             val find = search_str(dataline, pat, pos, modifier);
@@ -388,7 +388,7 @@ static val match_line(val bindings, val specline, val dataline,
               return nil;
             }
             LOG_MATCH("var delimiting string", find);
-            bindings = acons_new(bindings, sym, sub_str(dataline, pos, find));
+            bindings = acons(bindings, sym, sub_str(dataline, pos, find));
             pos = plus(find, length_str(pat));
           } else if (consp(pat) && regexp(first(pat))) {
             val find = search_regex(dataline, first(pat), pos, modifier);
@@ -399,7 +399,7 @@ static val match_line(val bindings, val specline, val dataline,
               return nil;
             }
             LOG_MATCH("var delimiting regex", fpos);
-            bindings = acons_new(bindings, sym, sub_str(dataline, pos, fpos));
+            bindings = acons(bindings, sym, sub_str(dataline, pos, fpos));
             pos = plus(fpos, flen);
           } else if (consp(pat) && first(pat) == var_s) {
             /* Unbound var followed by var: the following one must either
@@ -428,10 +428,10 @@ static val match_line(val bindings, val specline, val dataline,
 
               /* Text from here to start of regex match goes to this
                  variable. */
-              bindings = acons_new(bindings, sym, sub_str(dataline, pos, fpos));
+              bindings = acons(bindings, sym, sub_str(dataline, pos, fpos));
               /* Text from start of regex match to end goes to the
                  second variable */
-              bindings = acons_new(bindings, second_sym, sub_str(dataline, fpos, plus(fpos, flen)));
+              bindings = acons(bindings, second_sym, sub_str(dataline, fpos, plus(fpos, flen)));
               LOG_MATCH("double var regex (first var)", fpos);
               pos = fpos;
               LOG_MATCH("double var regex (second var)", plus(fpos, flen));
@@ -459,7 +459,7 @@ static val match_line(val bindings, val specline, val dataline,
               LOG_MISMATCH("string");
               return nil;
             }
-            bindings = acons_new(bindings, sym, sub_str(dataline, pos, find));
+            bindings = acons(bindings, sym, sub_str(dataline, pos, find));
             pos = plus(find, len);
           } else {
             sem_error(spec_lineno,
@@ -520,7 +520,7 @@ static val match_line(val bindings, val specline, val dataline,
                   LOG_MATCH("until/last", until_pos);
                   if (sym == last_s) {
                     last_bindings = set_diff(until_last_bindings,
-                                             new_bindings, eq_f, car_f);
+                                             new_bindings, eq_f, nil);
                     pos = until_pos;
                   }
                   break;
@@ -531,7 +531,7 @@ static val match_line(val bindings, val specline, val dataline,
 
               if (new_pos) {
                 val strictly_new_bindings = set_diff(new_bindings,
-                                                     bindings, eq_f, car_f);
+                                                     bindings, eq_f, nil);
                 LOG_MATCH("coll", new_pos);
 
                 for (iter = strictly_new_bindings; iter; iter = cdr(iter))
@@ -1544,7 +1544,7 @@ repeat_spec_same_data:
                 /* Until discards bindings and position, last keeps them. */
                 if (sym == last_s) {
                   last_bindings = set_diff(until_last_bindings,
-                                           new_bindings, eq_f, car_f);
+                                           new_bindings, eq_f, nil);
                   if (success == t) {
                     data = t;
                   } else {
@@ -1559,7 +1559,7 @@ repeat_spec_same_data:
 
             if (success) {
               val strictly_new_bindings = set_diff(new_bindings,
-                                                   bindings, eq_f, car_f);
+                                                   bindings, eq_f, nil);
 
               debuglf(spec_linenum, lit("collect matched ~a:~a"),
                       first(files), num(data_lineno), nao);