[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] Exclude optimization
From: |
Bruno Haible |
Subject: |
Re: [PATCH] Exclude optimization |
Date: |
Mon, 10 Aug 2009 10:44:49 +0200 |
User-agent: |
KMail/1.9.9 |
Sergey Poznyakoff wrote:
> By the way, I am also experimenting with the idea of re-implementing
> the exclude module using DFA, i.e. regarding the entire exclude list
> as a set of regular language definitions and creating a DFA for each
> of them (it is a *set* of definitions, because its parts can have
> different EXCLUDE_* flags, so they should be processed differently).
> This may constitute a significant speed-up.
Why does it not fit into two regexes / DFAs? I would think that
- The EXCLUDE_INCLUDE flag is a negation on the result, so we can
handle the "excluded" condition in one regex and the "included"
condition in another regex.
- The two other flags EXCLUDE_ANCHORED, EXCLUDE_WILDCARDS only
affect the transformation from fnmatch pattern to regex:
EXCLUDE_WILDCARDS on: 'a?b*' -> 'a.b.*'
EXCLUDE_WILDCARDS off: 'a?b*' -> 'a[?]b[*]'
EXCLUDE_ANCHORED on: 'a?b' -> '^a.b$'
EXCLUDE_ANCHORED off: 'a?b' -> '^\([^/]*/\)*a.b$'
- After the transformation from fnmatch pattern to regex, you
apply alternation: \(regex1\|regex2\|...\)
> using DFA
The DFA code from grep and gawk is next to unmaintainable [1]. Aharon Robbins
agrees that it would be good to rewrite it.
Bruno
[1] http://lists.gnu.org/archive/html/bug-gnulib/2009-07/msg00001.html
- [PATCH] Exclude optimization, Sergey Poznyakoff, 2009/08/09
- Re: [PATCH] Exclude optimization, Bruno Haible, 2009/08/09
- Re: [PATCH] Exclude optimization, Sergey Poznyakoff, 2009/08/11
- Re: [PATCH] Exclude optimization, Ralf Wildenhues, 2009/08/11
- Re: [PATCH] Exclude optimization, Sergey Poznyakoff, 2009/08/11
- Re: [PATCH] Exclude optimization, Sergey Poznyakoff, 2009/08/11
- Re: [PATCH] Exclude optimization, Ralf Wildenhues, 2009/08/13
Re: [PATCH] Exclude optimization, Ralf Wildenhues, 2009/08/10