Re: [PATCH] Exclude optimization

[Bruno Haible]

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