Fixed tags comparison in table minimization.

Bug was introduced in commit 5958a2366cdb1361b5158076924014a36ff19dcc
"Bind contexts (a.k.a. tags) to DFA transitions, not states.":
instead of comparing tags of single transition on one particular
symbol, we compared tags for all outgoing transitions at once
(probably copy-paste from Moore minimization).

The bug was revealed by multiple tests (including '--skeleton' ones)
as soon as I ran testsute with '--dfa-determinization table'.

More efficiently merge closure tags from different rules.

Exploit the fact that closure items are grouped by rule
instead of messing with a bit mask of rule tags.

Attribute tag liveness to edges, not states (to refine analysis).

State granularity is too crude: there might be
two different paths to the same state, with some tag alive on one
path but not on the other. If liveness is attributed to states, then
tag liveness on one path implies tag liveness in the join state,
which affects the other path. But if liveness is attributed to
edges, then liveness of one path won't affect liveness of the other.

Liveness of fallback tags is a forward-propagagation problem.

re2c used to merge all possible fallback tags and backward-propagate
them from states that have default transitions. This is an
overapproximation; some tags are marked alive while they are not.

Liveness of fallback tags should be forward-propagated, because
this is the only way to track paths that really need these tags
(that is, paths that start in final state and end with default
transition *without passing through another final state*).

Note that sometimes we can get to the same default transition
following two different paths, one path may passing through final
state; the other is not. One path cares for fallback tags; the
other doesn't. We have no way to find out if we start bacward
prpagation of fallback tags from default transition.

Comments and minor code rearrangements; nothing serious.

Tags can be calculated immediately after closure construction.

Typo in comment.

Sort closure right after construction.

Drop shadowed final NFA states when constructing DFA state.

By construction NFA has exactly one final state per rule.
Thus closure has at most one final item per rule (in other
words, all final items in closure belong to different rules).
The rule with the highest priority shadowes all other rules.
Final items that correspond to shadowed rules are useless
and should be removed as early as possible.

If we let such items remain in closure, they may prevent the
new DFA state from being merged with other states. But this
won't affect the resulting program: meaningless finalizing tags
will be removed by dead code elimination and after that DFA
minimization will merge equivalent final states.

But it is much easier and cleaner to remove useless items
immediately (and thas't what we do).

Some '--skeleton' tests changed: this is caused by collapsed
DFA states (shadowed final NFA states prevented them from
being collapsed before). All changes are verified with '--skeleton'.

Use 'Tagpool' for tag configurations during closure consruction.

Now that conflicting tag configurations are no longer merged,
we can insert them into 'Tagpool' immediately. This allows us
avoud ugly trick with 'union' in closure items.

Don't merge conflicting tags, choose arbitrary configuration.

Merging conflicting tags doesn't make sense: information is lost
anyway.

Use explicit constant 'ZERO_TAGS' instead of 0.

Ported 'Tagpool' on 'lookup_t' and got rid of 'ord_hash_set_t'.

An effort to reduce entities with similar functionality:
'lookup_t' is more flexible than 'ord_hash_set_t'.

Removed unused header.

Use 'std::vector' to store closure items during determinization.

This makes code somewhat clearer compared to using plain C arrays:
all function accept one parameter (vector) instead of two (array
start, array end/array length).

However, vectors have nontrivial structure and 'ord_hash_set_t'
is not suitable for them. That's why instead of 'ord_hash_set_t'
we now use 'lookup_t': just like 'ord_hash_set_t' it has constant
random access ang logarithmic insertion complexity, but unike
'ord_hash_set_t' it is not meant to be a container (rather an index).

Restructured determinization algorithm DFA construction in a more canonical way.

All textbooks describe determinization (powerset construction)
like this:

    S0 <- epsilon-closure of start NFA state
    add S0 to DFA
    while there is unmarked state S:
        mark S
        for each symbol X in the alphabet:
            R <- the set of NFA states reachable from S on X
            T <- epsilon-closure of R
            if T is not in DFA
                add T to DFA

In re2c the inner loop on alphabet symbols was split in two parts
and somewhat obfuscated; this commit makes re2c follow textbook
version more closely.

Moved important DFA construction subroutines into separate files.

Base '*' (zero or more repetitions) on '+' (one or more repetitions).

This commit effectively reverts commit 5cf441dc936c16e2264e49038ebe9a108dc750b9
"Base '+' (one or more repetitions) on '*' (zero or more repetitions)."

It turn out, there is a good reason for using '+' as base operation:
'*' can be expressed in terms of '+' as 'r* ::= r+ | <empty>', while
'+' expands as 'r+ ::= r r*' and 'r' is duplicated.

Duplication becomes crucial in presence of tags: if the duplicated
subexpression has tags, then duplication causes an error.

Added test fot bug #152 "Line number in #line directive after enum
YYCONDTYPE is 0-based".

(thanks to sirzooro for reporting)

Traverse NFA from left to right when building epsilon-closure.

Flip dimensions in 2d array (as it is slightly more convenient).

Renaming only.

Remove useless final states; calculate fallback states more accurately.

Removing useless final states allows some further optimizations
which would otherwise be impossible (see the changed tests for
example).

However, removing useless final states revealed previously hidden
defects in calculating fallback states: in some tests spurious
new 'yyaccept' values appeared. It turned out that we used incorrect
(imprecise, too pessimistic) algorithm to calculate fallback states:
the given state was considered to be fallback state if it was final
and had transitions to non-default and non-final states. This
algorithm erroneousl captures cases when all paths from the given
state are accepting and long enough (longer than one transition).
The new algorithm to find fallback states uses information obtained
by rule liveness analyses (reachability of "none-rule" in particular).

Some important tests changed a lot; skeleton says the changes are
correct (as well as manual looking into the changes).

Fixed rule reachability analyses.

The previous algorithm handled loops incorrectly: if deep-first search
from current DFA state happened to visit looping paths before non-looping
paths, then result accumulated from non-looping paths was not propagated
into loopback states.

Now we use back propagation (from states that have transitions to default
state), which handles loops correctly.

Tag deduplication should go before DFA minimization.

Tags prevent minimization in some cases; deduplicating them before
minimzation gives better chances to the latter.

Don't bother with reachability when reporting nullable rules.

We couldn't trace all unreachable nullable rules anyway, e.g.:
    [^]?
Nullable part of this rule is unreachable, but it was reported.
Besides, there's nothing bad in reporting all probles at once.

Give up the idea of sharing reversed DFA across different algorithms.

Reversed DFA reflects state of the original DFA in the moment when
its reversed copy was built. Original DFA undergoes many changes;
it's hard (and needless) to keep reversed DFA in sync with the
original.

We only need reversed DFA in a couple of places, better make a new
copy in each case.

There's no use in looping twice when tracing default paths.

Use backwards propagation for liveness analyses on tags.

In commit a7a26d17cee825afcbe8659cb31a04a165172eed we added fix-point
iterative algorithm to do liveness analyses on tags:

    The usual algorithm for liveness analyses doesn't use DFS;
    instead, it iterates on DFA states until fix point is reached
    (next iteration adds no changes to live set compared to the
    previous iteration). The fix applies this algorithm.

However, instead of iterating until fix point is reached, one may
use backwards propagation of live variables starting from the points
where these variables are used.

Moved loop-invariant code out of loop.

Use tagpool to store and manipulate intermediate tag sets.

Tagpool now has a special buffer to accommodate the needs of
intermediate calculations involving tag sets. Tagpool is in charge
of these calculations now; it has various functions to merge,
mask and whatever one has to do with tag sets.

Fixed bug in tag liveness analyses (tags lost in loops).

Example that revealed failure (added as test):
    (@p "ac")* "b" { @p }

We used forward propagation: starting from initial state, walk DFA
in deep-first order; in each state, add tags associated with rule
or fallback set if necessary, then recurse to child states, then
merge all child sets into this node's live set.

This algorithm cannot propagate live tags in loops in cases when
DFS visits loopbacks before non-looping paths (tags don't propagate
into loopback states).

The usual algorithm for liveness analyses doesn't use DFS;
instead, it iterates on DFA states until fix point is reached
(next iteration adds no changes to live set compared to the
previous iteration). The fix applies this algorithm.

A more efficient algorithm may be possible; one that uses backwards
propagation instead of fix point (I'm not sure).

Fixed occasional double-freeing tag names.

Tag names belong to regexps, which may be shared between automata,
so names should be freed on regexp destruction, not on automata
destruction.

Code cleanup.

Don't forget to dereference tag aliases.

Some tags are merged to other tags during tag deduplication.
These tags are referenced by their distinct name in action code,
but in fact they are just aliases to their representative tag
(origin).

Moved dispatch on fixed/variable tags inside of tag-printing function.

Fixed tag substitution.

If one tag name, say 'p', is a prefix of another tag name, say 'p1',
and we try to substitute all occurences of '@p' in the given string,
we might occasionally substitute '@p1'.

I made a small re2c lexer that recognizes tag-like lexemes and
tries to match them agains rule's tags. If a tag's name matches the
recognized substring, than it is the perfect match (name cannot be
a prefix of a longer name because lexer recognizes the longest match).

Code cleanup: removed useless/added missing includes.

Don't use '-Werror-nondeterministic-tags' with '-T, --tags'.

If tags are explicitly enabled, re2c should always fail with error
on nondeterministic tags. There's no good in '-Werror-nondeterministic-tags'
diagnostic --- the user cannot reset it anyway.

This commit fixes unsuccessful attempt 2bfe75d57c71c7102dd6e7b4e5f7139411c7c080
"Restore user warnings after temporarily enforcing a warning.", which
resulted in hiding tag errors if '-Wnondeterministic-tags' is not set.

Fixed bug #142 "segvault with null terminated input"

Steps to reproduce:
    $ echo -ne "&\x00" > A
    $ re2c A
    Segmentation fault

Analyses: when re2c finds NULL in the input file, it checks for the
end of input; if indeed it has reached the end of input, it stops.
Otherwise, it's just some NULL byte in the middle of input; it should
be handled like any other character.

The first case (NULL as end of input) was handled correctly, but
in the second case (NULL in the middle of input) re2c crashed:
someone forgot to put an appropriate 'goto' statement, which caused
completely ad-hoc control flow in lexer.

Don't loose tags on epsilon-loops in NFA.

Added tests for tags (nondeterminism, unsuccessfull minimization).

Restore user warnings after temporarily enforcing a warning.

This is a temporary (and quite inconvenient) hack; in fact,
warnings should be handled in the same way as options (via
user config / real config that are synced on each read access
just in case user config has been changed).

Fixed memleak.

Allow to override output and header filenames with configurations.

Fixed parsing of some configurations (forgot to parse semicolon).

Added test for various 're2c:flags:' configurations.

Added tests for bug #121 "trailing contexts are fundamentally broken".

Code cleanup: use anonymous union to shorten names.

Renamed 'contexts' to 'tags' (and all related stuff likewise).

No serious changes.

Keep fixed and variable tags together in one array.

This complicates tag deduplication a little (fixed tags have to be
masked), but simplifies tag initialization and rule handling.

Don't force mutations of immutable regexp AST.

Regexp AST should stay immutable as it may be shared between
different conditions. This means we have to store tag indices
somwhere else.

Allow tags in any part of regexp, not only on top-level concatenation.

Fixed-length tag optimization applies only to top-level concatenation:
since we cannot predict which path lexer will choose, we cannot be
sure that any tags except top-level concatenation will ever be
initialized. If a tag may be uninitialized, we cannot fix other
tags on this one (we cannot even fix same-level tags relative to
each other, because fixed tags won't preserve the default value).

Fixed comparison for struct 'kitem_t' (constified both operands).

Bind contexts (a.k.a. tags) to DFA transitions, not states.

This is a very imortant change: it makes tracing tag conflicts as
simple as comparing tags on transitions during DFA construction.
If during determinization we get two identical transitions that
differ only in tags, then we have a tag conflict. Tags that cause
conflicts are called non-deterministic (since they don't allow
deterministic match).

This approach if very similar to Ville Laurikari's TDFA: as he does,
we first build TNFA and then apply determinization; however Laurikari's
TDFA uses complex bookkeeping to track all possible tag values,
while re2c simply forbids tags that cannot be matche efficiently.

Binding tags to transitions allows more fine-grained liveness
analyses, dead tag elimination and tag deduplication.

Keep rule number in each NFA state (not only in final states).

This is currently not necessary, but we'll need it to distinguish
between different rules when comparing tags: if rules are different,
we don't care about tag difference; otherwise tags must be equal.

Cleanup in codegen (minor changes in '-D, --emit-dot' output).

    - more elegant hanling of default case when generatin code
      for 'switch' cases
    - dumbed down complex logic behind the generation of sequential
      'if' statements: explicitely list all different cases and
      corresponding conditions

More precise liveness analyses for context deduplication.

Liveness analyses should exclude contexts that are updated before
they are used past certain point in the program.

Cleanup in code generation (mostly formatting).

Simplified rule tracking during DFA construction.

Simplified collecting context names during code generation.

Rule contexts are consecutive, so we only need to store bounds.

Count contexts after deduplication.

Break from loop if the remaining iterations have no effect.

Cleaned up code that merges arcs while tunneling DFA.

Behaviour should be unchanged.

Moved conditions and contexts from global scope to block scope.

Directives like '/*!re2c:types*/' and '/*!re2c:contexts*/' have
global scope, they are not binded to any particular block and therefore
accumulate items (conditions/contexts/etc.) from the whole program.

There's currently no way to bind these directives to a particular
block (re2c will probably add scoping rules in future).

However, things like default context declaration or condition dispatch
have block scope (it's only natural that they are binded to the block
that generates them).

Unrelated change: context marker should be set for each condition,
re2c must generate it after condition label: this way code that skips
condition dispatch and jums directly to condition label will still
have context marker adjusted properly.

Added configurations for all command-line options.

Separated .dot code generation from common case.

Omit some useless newlines in the generated code.

Lexer: minor code cleanup (check errors before doing anything else).

Lexer: moved 'end of comment' sublexer to a separate function.

Lexer: unified handling of various re2c directives.

Now when lexer encounters the beginning of a new directive, it
dumps all the intermediate code to the output.

Before this commit re2c lexer dumped intermediate code on each
newline that occured in the input.

So this commit affects two aspects:
    - Intermediate code is dumped much less often: it's good for
      performance, but it becomes more probable that the intermediate
      code will occasionally occupy too much buffer space and incur
      buffer resize.
    - Some re2c directives ignored characters right before the
      (on the same line). These unfortunate characters are no longer
      ignored.

Lexer: drop useless rule.

The 'end of comment' rule was used to detect end of re2c directives;
however, now it is handled by a special 'end of comment' lexer block.

Lexer: don't care if end of comment is followed by a newline.

re2c used to swallow newline that immediately followes end of directive:
for most of the directives re2c generates code block that ends with a
newline, so the generated code looks better if the newline is not doubled.

However, this unnecessarily complicates the lexer.

Lexer: suppressed directives in skeleton mode, cleaned up code.

Explicitely handle empty string in lexer.

(rather that hide it inside of a definition)

Added directive '/*!contexts:re2c ... */'.

Directive is a new type of re2c block that consists of zero or more
of the following configurations (example values are the defaults):
    line = "long @@;";
    sep = "";

Renamed configuration: 're2c:ctxprefix' -> 're2c:contexts:prefix'

Added configuration: 're2c:contexts:expr = "@@"' that allows to
override the way context markers are accessed (but nottheir names).

Removed configuration: 're2c:define:YYDISTTYPE' (use the new
directive '/*!contexts:re2c ... */' instead).

Parser grammar cleanup.

 - Rearranged some rules to avoid code duplication.
 - Added production and error message about contexts in named definitions.
 - Removed productions and error messages about missing expression
   (simple 'syntax error' is enough, given that only part of the
   errors was captured by the removed productions).

Optimized pointer arithmetics generated with '-C, --contexts'.

If default input API is used and fixed-length context is based on
the rightmost context (that is, YYCURSOR), then the following expression
(that calculates pointer corresponding to the given context):
    (YYCTXMARKER + ((YYCURSOR - YYCTXMARKER) - yyctx))
can be optimized to:
    (YYCURSOR - yyctx)

Note: unfortunately, as of GCC < 7.0, expressions like:
    (YYCURSOR - 3) - (YYCURSOR - 5)
trigger warning:
    warning: integer overflow in expression [-Woverflow]
See this GCC bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61240

Added some configurations related to '-C, --contexts' option.

Configurations:
    "define:YYCTX"      (defaults to 'YYCTX')
    "define:YYDIST"     (defaults to 'YYDIST')
    "define:YYDISTTYPE" (defaults to 'long')
    "ctxprefix"         (defaults to 'yyctx')

Use 'std::valarray' instead of 'std::vector' to avoid copy semantics.

Had to rename 'INFINITY' to 'SCC_INF': inclusion of '<valarray.h>'
pulled '<math.h>' and introduced name collision.

Use 'size_t' instead of 'uint32_t' to avoid 'static_cast'.

Make sure that default rule is handled together with other rules.

Moved nontrivial context handling from parser to NFA construction phase.

Parser should simply construct AST; all the complex reasoning about
contexts (fixed vs variable) should be delayed until NFA is being
constructed. This way AST can be immutable and it's very easy to share
parts of AST between different conditions, etc.

Removed rule ranks and rank counter: rules are now stored in NFA-local
array and addressed by index.

Added partial submatch extraction.

Enabled with '-C, --contexts' option.

Warning '-Wselfoverlapping-contexts'.

Moved loop counters out of skeleton; they belong to algorithm-local stuff.

Pack all stuff relevant to skeleton data generation in a struct.

Use distinct type for path suffixes during skeleton data generation.

Address skeleton nodes by indices rather than by pointers.

This way it is more convenient to add various graph algorithms:
each algorithm can keep its own data in array indexed by skeleton
node numbers (instead of pushing all relevant data inside of the
node).

Reuse the same struct to represent different kinds of paths in skeleton.

[-Wundefined-control-flow] analyses: simplified path structure.

Now paths involved in [-Wundefined-control-flow] analyses have
exactly the same structure as paths involved in skeleton data generation.

Added comments.

Moved comment.

Moved calculation of fallback states to earlier stage of DFA construction.

We will need this later, when adding multiple context markers
(liveness analyses during context marker deduplication).

Eradicated occasional copy-paste.

Used function 'make_rule_copy' introduced by commit
f781c3a3a07cde0243c894da640070d6c62ef4bc.

Moved function definitions out of header.

Skeleton: simplified path structure.

Just store pointers to skeleton nodes (instead of bookkeeping arcs,
contexts and rules in each path). All the necessary information can
be easily retrieved from nodes when path is baing dumped to file.

Three tests in '--skeleton' mode have been broken by this commit.
Actually, these are not breakages: these cases reveal incorrect
re2c-generated code. The change is due to the fact that skeleton
now doesn't simulate contexts that go *after* the matched rule:

    ------o------o------> ... (fallback to rule)
        rule   context

Skeleton: respect fixed-length contexts.

run_tests.sh: fixed cleanup of intermediate files with '--skeleton'.

Broken by commit c56a14582de4fbbed34d231e521ab2e6af5d43c3
"run_tests.sh: don't crash on absolute filepaths in test names."

run_tests.sh: don't crash on absolute filepaths in test names.

This patch fixes bug #137 "run_tests.sh fail when running configure
script with absolute path".

The fix: copy all test files into temporary build directory (which
is addressed by a relative filepath) and keep messing with relative
filepaths.

Code cleanup: moved rule construction to a separate file.