Added 'clear()' method to slab allocator.

Paper: removed nested negative tags from TNFA and added complexity analysis.

libre2c: don't add nested negative tags to TNFA, as it increases its size and makes matching slower.

Instead, add only one negative tag (top-level closing one) and record
the remaining tags in its metadata. Use this metadata to update nested
negative tags during TNFA simulation.

libre2c benchmark: make a couple of warmup iterations before the main run.

Paper: added "Benchmarks" section.

libre2c benchmark: print size of each regular expression and the number of capturing groups in it.

libre2c: removed unused variable.

Makefile.am: added 'bench_libre2c' to noinst_PROGRAMS (so that automake picks it as a target).

Paper: added section about lazy disambiguation.

Added a test for '--input-encoding utf8' option.

Added option --input-encoding <ascii | utf8> that allows to use UTF-8 literals in regular expressions.

Allow to mix multiple /*!rules:re2c*/, /*!use:re2c*/ and /*!re2c*/ blocks in -r mode.

libre2c: added GOR1 option for lazy disambiguation algorithm.

libre2c: do not include benchmark in 'make check' programs.

libre2c: added forgotten benchmark data samples.

libre2c: added missing include.

libre2c: updated benchmark.

libre2c: extended lexer to handle some escape sequences in charachter classes.

Inlined closure cleanup in the pruning procedure to further speedup determinization.

Make unreachable rule analysis conditional to further sppedup closure pruning.

Rewrite of closure pruning function to speedup determinization on large automata.

Hash in 4-byte chunks to speedup determinization on large automata.

Use correct formula to find the next aligned address.

The previous formula worked incorrectly for already aligned addresses
(it added alignment to them).

Paper: updated "TNFA construction" section.

configure.ac: use AC_USE_SYSTEM_EXTENSIONS, as --std=c++98 disables POSIX extensions on Cygwin.

Attempted fix for #247.

Makefile.am: reflected the rename of README to README.md.

This fixes bug #248.

Paper: updated sections about representation of paths and match results.

Paper: rearranged "epsilon-closure" section.

Paper: updated pseudocode for precedence procedures.

Paper: restructured "formalization" section.

Paper: wrote "main idea" section.

libre2c: restructured main loop to avoid double call to closure.

Paper: wrote the "introduction" section.

Fixed compilation error caused by extra namespace qualification (second attempt).

Fixed compilation error caused by extra namespace qualification.

libre2c: implemented Kuklewicz disambiguation algorithm for POSIX TNFA matching.

libre2c: free tag history after each step (it's no longer needed).

Seems to be a copy-paste error from TDFA implementation, where history
for each state is needed until the end of determinization.

Parameterize determinization/simulation context directly by history type.

Added logs with test failures of backward matching algorithm.

libre2c: added Cox backward matching algorithm (incorrect, but interesting).

Fictive tags for right alt/cat must be added after adding all tags for left alt/cat.

Previous order was incorrect: fictive tags for both left and right
alternative or catenation were added before recursing into the right
alternative or catenation. This resulted in right fictive tags habving
higher precedence than left non-fictive tags.

Debug: don't print NFA in-degree in each node, it takes too much space.

libre2c: added POSIX tests that show why closure can't use DFS and needs worst-case quadratic shortest path algorithm.

In particular, test ((((a?)+)|(aa))+) and string "aaa" demonstrates why
we cannot replace SSSP (GOR1 or GTOP) with a liner-time DFS that sets
predecessor chains of TNFA states and sorts initial closure configurations
according to POSIX relation imposed by precedence matrix.

Consider what happens after consuming the first to 'a's (see the .dot
encoded TNFA below):

- initial states are 8, 14 and 9 (in the order imposed by D-matrix)

- start DFS from 8

- find path 8->7->6->5->4->3->2->22->21->11->10

- find path 8->7->6->5->4->3->2->22->21->20->19->18->17->16->15

- find path
  8->7->6->5->4->3->2->22->21->20->19->18->17->16->14->13->17
  compare it to the previous path to 17 and discard the new looping path

- find path
  8->7->6->5->4->3->2->22->21->20->19->18->17->16->14->13->12->3
  compare it to the previous path to 3 and discard the new looping path

- find path 8->7->6->5->4->3->2->1->0

- DFS from 8 complete, start DFS from 14

- find path 14, compare it to the previous path to 14 and accept the new
  one as it is better (but do not attempt to propagate the improvement
  and rescan states: this is DFS, not GOR1, and the whole idea is to
  avoid rescanning and have linear complexity)

- DFS from 14 complete, start DFS from 9

- find path 9

The end, and we have an incorrect path to 15: the long path through the
outer loop from 8, rather than the short path through the inner loop
from 14. This further leads to incorrect results.

digraph NFA {
  rankdir=LR
  node[shape=Mrecord fontname=Courier height=0.2 width=0.2]
  edge[arrowhead=vee fontname=Courier label=" "]

  n23 [label="23"]
  n23 -> n22 [label="/0&uarr;(1)"]
  n22 [label="22"]
  n22 -> n21 [label="/2&uarr;(2)"]
  n21 [label="21"]
  n21 -> n11
  n21 -> n20 [color=lightgray]
  n20 [label="20"]
  n20 -> n19 [label="/4&darr;(3)"]
  n19 [label="19"]
  n19 -> n18 [label="/5&darr;(2)"]
  n18 [label="18"]
  n18 -> n17 [label="/6&uarr;(3)"]
  n17 [label="17"]
  n17 -> n16 [label="/8&uarr;(4)"]
  n16 [label="16"]
  n16 -> n15
  n16 -> n14 [color=lightgray]
  n15 [label="15"]
  n15 -> n14 [label="97"]
  n14 [label="14"]
  n14 -> n13 [label="/9&uarr;(3)"]
  n13 [label="13"]
  n13 -> n17
  n13 -> n12 [color=lightgray]
  n12 [label="12"]
  n12 -> n3 [label="/7&uarr;(2)"]
  n11 [label="11"]
  n11 -> n10 [label="/4&uarr;(3)"]
  n10 [label="10"]
  n10 -> n9 [label="97"]
  n9 [label="9"]
  n9 -> n8 [label="97"]
  n8 [label="8"]
  n8 -> n7 [label="/5&uarr;(2)"]
  n7 [label="7"]
  n7 -> n6 [label="/6&darr;(3)"]
  n6 [label="6"]
  n6 -> n5 [label="/8&darr;(4)"]
  n5 [label="5"]
  n5 -> n4 [label="/9&darr;(3)"]
  n4 [label="4"]
  n4 -> n3 [label="/7&darr;(2)"]
  n3 [label="3"]
  n3 -> n2 [label="/3&uarr;(1)"]
  n2 [label="2"]
  n2 -> n22
  n2 -> n1 [color=lightgray]
  n1 [label="1"]
  n1 -> n0 [label="/1&uarr;(0)"]
  n0 [label="0"] [fillcolor=gray]
}

Use state index in closure instead of core index, and don't keep core indices at all.

Added tests for errors in case of out-of-bounds EOF value.

Give a concise error message when EOF rule is present, but no other rules are.

Updated .gitignore.

Updating .travis.yml after global move.

Moved re2c subdirectory to root directory and renamed old libre2c to libre2c_old.

Makefile.am: use wildcard instead of braces in macro expansion (the latter breaks on BSD).

Avoid using ULLONG_MAX as it is non-standard prior to C++11.

Handle cases when rename() fails because destination file exists.

In C/C++ rename() behaviour is implementation-defined. POSIX and Windows
have different behaviour when destination file exists: POSIX says rename()
should overwrite it, but Windows says rename() should fail.

Added more tests for EOF rule.

Improved label generation with EOF rule (removed unused and added missing labels).

Added some tests for EOF rule.

Fixed EOF rule handling in case when EOF symbol is the upper bound of charset.

run_tests.sh: ignore difference in trailing whitespace with --wine option.

Added test for newline conversion.

Consistently convert all newlines in the generated file to Unix-style LF.

Some newlines originate in user-defined code (including semantic actions
and code fragments in configurations and directives), some are generated
by re2c itself. In order to maintain consistency we convert all newlines
to LF when writing output to file.

Need to include <fcntl.h> with MSVC to get definitions of _O_CREAT, _O_EXCL and _O_RDWR.

Avoid warnings about uninitialized variables.

Use macro _MSC_VER instead of nonexistent _MSVC to detect Visual Studio.

Do not access vector element by reference that is invalidated due to reallocation.

Use autoconf header detection to guard non-C++98 includes (POSIX file API).

Use something that Mingw understands instead of UINTMAX_MAX from <stdint.h>.

Write output to temporary file and then rename it to output file atomically.

This is more conveniet for build systems: if code generation is interrupted
for some reason, we don't end up with half-generated or empty output file.

Note that re2c there still can be discrepancy between the generated header
file and output file.

Use C array instead of vector (of known size) to avoid iterator invalidation warnings.

Respect platforms with 32-bit 'long' and 64-bit pointers.

Previously used ~0U works incorrectly in such cases: ~0U equals
0xFFFFffff, and maximum (numerical) pointer value is 0xFFFFffffFFFFffff.
This caused incorrect comparison result when tracking include files that
have been fully processed and can be removed frm the include stack.

Problem report thanks to Denis Naumov.

Renamed README to README.md to make github render it nicely.

Prettified README somewhat.

Moved LICENSE, README, NO_WARRANTY and CHANGELOG to the root directory.

Added license file.

Deduplicated leftmost greedy closure implementations in re2c and libre2c.

Reuse second closure buffer as a stack for leftmost greedy closure.

Further deduplicated POSIX closure implementation in libre2c and re2c.

Parameterized determinization/simulation context over history type.

libre2c: parameterized context type over semantics (POSX/leftmost) and eval strategy (lazy/strict).

Deduplicated POSIX closure computation in re2c and libre2c.

libre2c: updated benchmark.

Deduplicated algorithm that computes POSIX precedence matrix in re2c and libre2c.

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).