diff options
| author | Kaz Kylheku <kaz@kylheku.com> | 2011-10-04 15:41:33 -0700 |
|---|---|---|
| committer | Kaz Kylheku <kaz@kylheku.com> | 2011-10-04 15:41:33 -0700 |
| commit | 6dba0b4836e192906c63773527861ddf9de1d679 (patch) | |
| tree | d1ffc53e6290394a4903e5ec7822c077970dd304 | |
| parent | b5d5dcb8dcde90bb1766eb88a36e962f8e43fd33 (diff) | |
| download | txr-6dba0b4836e192906c63773527861ddf9de1d679.tar.gz txr-6dba0b4836e192906c63773527861ddf9de1d679.tar.bz2 txr-6dba0b4836e192906c63773527861ddf9de1d679.zip | |
* 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.
| -rw-r--r-- | ChangeLog | 18 | ||||
| -rw-r--r-- | lib.c | 19 | ||||
| -rw-r--r-- | lib.h | 1 | ||||
| -rw-r--r-- | match.c | 24 |
4 files changed, 46 insertions, 16 deletions
@@ -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 @@ -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; @@ -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); @@ -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); |