From eb533d54bf1dd5e0c88b4b1ebf262349e368cfd1 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Mon, 18 Jan 2010 16:26:24 -0800 Subject: * regex.c (reg_derivative_list, reg_derivative): Recognition of cases to reduce consing. In reg_derivative_list, we avoid consing the full or expression if either branch is t, and also save a cons when the first element has a null derivative. In reg_derivative the oneplus and zeroplus cases are split, since zeroplus can re-use the input expression, when it's just a one-character match, deriving nil. --- ChangeLog | 10 ++++++++++ regex.c | 35 +++++++++++++++++++++++++++++------ 2 files changed, 39 insertions(+), 6 deletions(-) diff --git a/ChangeLog b/ChangeLog index 783a1d49..cf59daa3 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2010-01-18 Kaz Kylheku + + * regex.c (reg_derivative_list, reg_derivative): Recognition + of cases to reduce consing. In reg_derivative_list, we avoid + consing the full or expression if either branch is t, and + also save a cons when the first element has a null derivative. + In reg_derivative the oneplus and zeroplus cases are split, + since zeroplus can re-use the input expression, when it's + just a one-character match, deriving nil. + 2010-01-18 Kaz Kylheku Adjust semantics of non-greedy operator R%S, to avoid the broken diff --git a/regex.c b/regex.c index 174fb0d9..42968af2 100644 --- a/regex.c +++ b/regex.c @@ -1243,11 +1243,26 @@ static val reg_derivative_list(val exp_list, val ch) { if (rest(exp_list)) { if (reg_nullable(first(exp_list))) { - return list(or_s, cons(compound_s, - cons(reg_derivative(first(exp_list), ch), - rest(exp_list))), - reg_derivative_list(rest(exp_list), ch), - nao); + val d_first = reg_derivative(first(exp_list), ch); + val d_rest = reg_derivative_list(rest(exp_list), ch); + + if (d_rest == t && d_first == t) + return t; + + if (d_rest == t) + return if3(d_first == nil, + cons(compound_s, rest(exp_list)), + cons(compound_s, cons(d_first, rest(exp_list)))); + + if (d_first == t) + return d_rest; + + return list(or_s, + if3(d_first == nil, + cons(compound_s, rest(exp_list)), + cons(compound_s, cons(d_first, rest(exp_list)))), + d_rest, + nao); } else { val d_first = reg_derivative(first(exp_list), ch); @@ -1290,7 +1305,7 @@ static val reg_derivative(val exp, val ch) return reg_derivative_list(args, ch); } else if (sym == optional_s) { return reg_derivative(first(args), ch); - } else if (sym == oneplus_s || sym == zeroplus_s) { + } else if (sym == oneplus_s) { val arg = first(args); val d_arg = reg_derivative(arg, ch); if (d_arg == t) @@ -1300,6 +1315,14 @@ static val reg_derivative(val exp, val ch) return cons(compound_s, cons(d_arg, cons(cons(zeroplus_s, cons(arg, nil)), nil))); + } else if (sym == zeroplus_s) { + val arg = first(args); + val d_arg = reg_derivative(arg, ch); + if (d_arg == t) + return t; + if (d_arg == nil) + return exp; + return cons(compound_s, cons(d_arg, cons(exp, nil))); } else if (sym == compl_s) { return cons(sym, cons(reg_derivative(first(args), ch), nil)); } else if (sym == or_s) { -- cgit v1.2.3