Deduplicated tag history definitions used in re2c and libre2c.

Avoid allocating new scratch buffer for each closure, reuse the same buffer.

Exit early from loops in GOR1.

libre2c: updated benchmark.

libre2c: use a more efficient algorithm for computing POSIX precedence matrix.

The old alrorithm was straightforward: it computed precedence for each
pair of core closure items. This has worst-case cubic complexity in the
size of TNFA, because closure can have O(N) states and tag history length
can be also O(N). One example is ((a?){1,1000})*.

The new algorithm avoids that by computing parecedence for all pairs of
core items in one traversal of the shortest path tree constructed by
closure. It avoids traversing deadend branches (those that were cancelled
by search because a better path was found) by marking used nodes of the
tree from each leaf down to the root. The new algorithm has worst-case
quadratic behaviour. It can be slightly slower for simple cases when the
number of core items is low and histories are short.

Moved hot functions to header to enable inlining.

libre2c (benchmark): do not try to link with re2 if it's not available.

libre2c: found pathological case for constant-memory POSIX algorithms.

The regexp is ((a?){1,200})*, and the input string is just "a".

Takes quibic time in the size of counter. This is caused by quadratic-
time computation of precedence matrix on each step (the number of TNFA
states in the closure approaches TNFA size), multiplied by the length
of compared histores (which also approaches TNFA size). Trie-based
algorithms are not affected, but they consume memory proportional to
the length of the input string, and so are also not practical.

libre2c: added simplistic benchmark to compare different libre2c algorithms and re2.

Simplification of GOR1 (following similar changes in libre2c).

No need to fully unwind tag histories when calculating POSIX precedence.

Histories are stored in a trie. Each history is represented by an index
to its tail in the trie. In order to compare two histories, we can simply
unwind both indices, step by step, until they coincide or root index is
reached.

Related commits in libre2c:
    062da2dca6908c0f6da54711b897e3bafca2628c
    2a7158b401d7e925696fc1b0c8da37a59e364dd4

libre2c: deleted unused buffers.

Use signed integers as tag history indices (this way root index -1 is the least one).

run_tests.sh: ignore trailing whitespace in test diffs if compiler name matches "mingw".

We already ignore trailing whitespace when running in Wine, but binaries
that built with Mingw and run on windows (not in Wine) also need this option.

Constified std::map comparator (apparently MSVC fails to compile otherwise).

Problem reported by Denis Naumov.

Correctly handle multi-character newlines (e.g. CR LF) when parsing #line directives.

Bug report thanks to Denis Naumov.

libre2c: avoid -Wreturn compiler warnings (no return value from non-void function).

libre2c: use core state indices when possible.

libre2c: inlined hot function.

libre2c: updating marker of last matched rule after closure has been constructed (non-constant-memory version).

See commit 9998f616a314d635adbfea360d9882276c237e6d (same for constant-memory version).

libre2c: compare histories in a trie without reconstructing them (non-constant-memory version.)

See commit 2a7158b401d7e925696fc1b0c8da37a59e364dd4.

libre2c: added forgotten file.

libre2c: rearranged code to avoid checking configuration type when computing precedence matrix.

libre2c: ensure TNFA simulation algorithms clean up context before exiting.

libre2c: use templates to avoid dynamic dispatch between closure algorithms.

libre2c: hid some of the implementation details behind a pointer in regex_t struct.

libre2c: simplified construction of configurations.

libre2c: added GOR1 algorithm for POSIX closure construction.

libre2c: compare histories in a trie without reconstructing them.

Previously we used to unwing each history, store it as a linear sequence
in a separate buffer, and then iterate buffers from the beginning of
histories to fing the fork point.

This reconstruction step can be avoided, because we can find fork by
tracing both histories together from tail to root, element by element,
until their indices coincide (this is the fork point. Someone called
thos "two-fingers algorithm".

libre2c: use signed indices in tag history (this way root index -1 is the least one).

libre2c: marked hot function as inline.

libre2c: updating marker of last matched rule after closure has been constructed.

libre2c: use lookahead to  to filter leftmost closure before computing offsets.

libre2c: use lookahead to filter POSIX closure before computing offsets and precedence matrix.

This significantly reduces the amount of work on each step.

libre2c: implemented constant-memory (non trie-based) TNFA POSIX matching algorithm.

libre2c: renamed a couple of struct fields (cosmetic).

Correctly set values on main diagonal of POSIX precedence matrix (configuration compared to itself).

It doesn't show any difference on the tests, probably because previously
these values were set to zero, which unpacks to symmetrical (though
incorrect) values, and thus doesn't affect comparison.

libre2c: added (stub for) constant-memory (non trie-based) TNFA POSIX matching algorithm.

libre2c: use preallocated buffer.

libre2c: added constant-memory (non trie-based) TNFA matching algorithm for leftmost greedy.

Assign indices to core TNFA states (those that are final or have transitions on symbols).

During epsilon closure constructions, many operations only need to be
performed for core states. This allows to save some memory, e.g.
precedence matrix can be indexed by core states.

Structural tags are only needed for POSIX disambiguation, not for POSIX syntax.

Added option --verbose that prints a message to stderr in case of success.

Removed useless code in tests for misused option arguments.

Tweaked error messages for misused option arguments, added some tests for them.

Added option --location-format <gnu | msvc> (default is gnu).

This option controls the formatting of locations in error messages
and warnings.

With --location-format gnu:

    filename:line:column: ...

With --location-format msvc:

    filename(line,column): ...

Moved files.

Deduplicated filename strings in locations by interning them in a table and using indices.

Unified location handling by grouping relevant information in a struct.

Massive test updates are caused by refined locations for various error
messages and warnings (re2c now reports not only line, but also column).

Added test for EOF rule.

Use GNU-style location format 'file:line:column: ...' in warnings and error messages.

Added build script that uses '-D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC'.

Fixed out of bounds read when sorting one-element initial closure.

The error only occurred on some libc implementations, e.g. on debug
glibc (options -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC).

Fixed use of invalidated iterator after erase on std::map.

Problem reported by Denis Naumov.

Use per-tag cache of history comparisons to avoid repeated computation.

Use counting sort for tag histories (the number tags is limited, so it is faster).

Use insertion sort instead of bubble sort (it is slightly faster).

Fixed typo.

Speedup in determinization (using a more efficient way to compare lookahead tags).

Yet another speedup in determinization (early exit when comparing history with itself).

Small speedup in determinization (by inlining small hot functions).

Small speedup in determinization by delaying computation of costly conditions.

libre2c: added comment.

libre2c: speedup of POSIX NFA matcher by lazy computation and caching of precedence.

A lot of the match time was taken by eagerly computing precedence values
on each step for each pair of closure states. Most of these values are not
needed: RE may be unambigous; or the given input string may be unambigous,
even if there is ambiguity, it may take only a few comparisons to resolve.
All the rest is wasted effort.

We can avoid it by delaying precedence computation until necessary, and
then unwinding all the steps backwards, computing precedence for each step
and caching the computed values (so that the same pair of histories is not
compared twice). It is still the same incremental comparison as with
precedence matrices: we compare step by step, going from the fork frame to
the join frame. The result of comparison on each step is folded to a triple
of numbers and recorded in cache. It is important that we do record each
step, not just the first step, because the next pair of ambiguous histories
may unwind to the same pair of prefixes that was compared before.

For all this to work, it is necessary that we can store all history until
the very end, because at any step we might need to unwind an arbitrary
number of steps back. We also need to address individual subhistories
efficiently in order to use them as keys in the cache. All this is achieved
by storing history in the form of a trie and addressing individual
histories by indices in the trie. We also use trie to compute the resulting
tag values (instead of storing tags in registers at each step).

libre2c: small performance improvement in POSIX TNFA matcher.

libre2c: extracted common parts of TNFA matchers (leftmost and POSIX).

libre2c: performance optimization: get all tag values in one scan of history.

Renamed libre2c_posix -> libre2c (as it now also supports leftmost greedy semantics).

Differentiate between "POSIX syntax" and "POSIX semantics" options.

This is needed because we may want to use POSIX syntax with leftmost
greedy disambiguation. In that case, we still need parentheses-as-tags
attitude, but we don't want all the overhead and heuristics to spped
up POSIX closure.

libre2c_posix: added test for leftmost TNFA matcher.

libre2c_posix: added TNFA matcher with leftmost greedy disambiguation semantics.

libre2c_posix: small performance improvement in NFA-based matcher.

libre2c_posix: added NFA-based matcher.

Constified function parameter.

libre2c_posix: another small improvement in regexec() implementation.

libre2c_posix: a small performance improvement in regexec() implementation.

libre2c_posix: regex_t definition must be exposed to users.

POSIX standard says that:

    The regex_t structure is defined in <regex.h> and contains at
    least the following member: re_nsub (number of parenthesized
    subexpressions).

libre2c_posix: enable tag optimizations.

libre2c_posix: extended regex_t structure to hold more submatch data.

Added fields:
    - re_nsub: total number of submatch groups, required by POSIX standard

    - pmatch: buffer for submatch results, usually supplied by the user to
      regexec(), but we allow to do the allocation and storage in regex_t.
      This is convenient for users that have hard time managing memory, e.g.
      java bindings to libre2c_posix.

    - regs: buffer for internal use by regexec(), strored in regex_t to
      avoid repeated memory allocation on each call to regexec() with the
      same regex.

Adjusted build system to correctly build DLLs for windows.

Adjustments:
    - configure.ac:  pass win32-dll option to LT_INIT

    - Makefile_libre2c_posix.am: use -no-undefined in LDFLAGS

    - use slibtool: https://github.com/midipix-project/slibtool for windows
      builds The problem with libtool is that it doesn't allow to link libstdc++
      and libgcc statically, which is necessary to build portable DLLs with
      Mingw. Libtool adds -nostdlib option to LDFLAGS and links some predefined
      objects that pull in dependency on dynamic libstdc++ and libgcc, even in
      the presence of -static-libstdc++ -static-libgcc.

Use libtool to build libraries.

Fixed operator precedence with --flex-syntax option.

Operator precedence was broken because re2c tried to parse whole strings
of characters at once instead of parsing one character at a time (in
much the same way as it would parse properly quotes string literals in
the original re2c format). This caused ab* being parsed as (ab)*, which
is clearly wrong (should be a(b)*).

This fixes bug #242:
    "Operator precedence with --flex-syntax is broken."

libre2c_posix: handle empty group () in parser; added more tests.

Make re2c:eof usable with push-model lexers (-f, --storable-state option).

libre2c_posix: parse repetition counters in the lexer.

libre2c_posix: initial support for character classes in parser.

libre2c_posix (test): clear error status on expected failures.

libre2c_posix: skip fictive tags in regexec(); handle dot in parser; added more tests.

libre2c_posix: use C-array initializers instead of variadic functions for offset lists.

Variadic functions cause subtle toolchain-specific errors because integer
literals used to initialize offsets may have different type than the type
expected by variadic function (e.g. int vs long).

libre2c_posix (test): a more concise error message.

libre2c_posix: fixed -Wmaybe-uninitialized GCC warning.

libre2c_posix: fixed memleaks.

Experimental: initial implementation of libre2c_posix, POSIX regexp library based on re2c.

Paper: don't forget to pass precedence matrices to initial closure.

Makefile.am: further simplify parser generation rules and avoid copying file to itself.

Makefile.am: don't forget to run main test suite on `make check`.

Makefile.am: use more universal rules for autogenerated lexers and parsers.

Avoid unexpected removal of untracked files and directories.

Moved function declarations to the header they belong in.

Updated range test.

Use a simple fixed-size slab allocator for ranges.