Search for the best candidate in case of non-bijective mapping.

For bijective mappings there is always at most one mapping candidate,
for non-bijective mappings there may be many candidates.

Respect injective mappings when optimizing save(X), copy(Y,X) to save(Y).

If mapping is injective, there may be multiple copy commands per one
save command: save(X), copy(Y,X), copy(Z,X). In this case save command
must be replicated for each copy command: save(Y), save(Z).

Now checking for tag priority violation respects injective mappings.

Fixed atrocious typo that unconditionally enabled injective mapping.

However, injectivity never showed up because every injective mapping
(as of now) is erroneously considered to violate tag priority.

Added test: exponential blowup if bottom is treated as special version.

One tempting way to track default value of tags is to forbid mapping
bottom (default) to non-bottom versions. This way we don't need to
explicitely save bottom to variable; bottom value is encoded in state
(once a tag becomes bottom, it will never become non-bottom again).

However, this may exponentially blow up the number of states.

Cleaned up determinization.

Moved creation of new DFA states and finalizers to a separate routine,
together with building tag commands.

Untwined determinization and '-Wnondeterministic-tags' analysis.

Now '-Wnondeterministic-tags' analysis is done right after determinization,
while we still have all the kernels available. Instead of comparing
transition tags (which are available in closure items, but not in kernels)
we now compare tag versions: maximum number of distinct versions per tag is
the desired degree of nondeterminism. Kernel items that belong to another
rule do not count (all tags that don't belong to a particular rule should
have initial versions in all items belonging to this rule).

Added test with an example of pathological regexp: counted repetition
cannot be folded efficiently in DFA, and combined with nondeterministic
tags it results in arbitrary long chains of reordering commands.
Length of command choin grows linearly with the number of repetitions
(as DFA itself does).

Debug '--dump-adfa' option: drop 'YYFILL' in move states, it's fictive.

Added debug option '--dump-dfa-raw'.

It dumps DFA at the very early stage of construction, expanding underlying
state kernels with NFA substates and correspondings sets of tag versions.

Added option '--dfa-mapping <bijective | injective>'.

This option controls how tag versions in DFA states are mapped to each
other during determinization. By default mapping is 'bijective', however
if it is set to 'injective' the new state must be less versatile than
the old one.

Debug '--dump-adfa' option: correctly display range lower bound.

Drop hoisted tags in 'base' states duplicated by tunneling.

Tunneling optimization finds certain states and splits them into
two parts: First part consumes a character and unconditionally moves
to the second part. Second part does not consume characters, but
contains a switch on character value.

Second part is a 'base switch', which may be utilized by many other
states. So if the first part has hoisted tags, they should be dropped
in the second part (the aforementioned many other states may have hoisted
tags of there own or no hoisted tags at all).

Found by slyfox's fuzzer. :)

Yet unable to construct a test case that reveals the error: the original
test case found by fuzzer is not breaking anymore after recent commit
44045203c211531cc3e3a47f0b5eb2e5d993cc15 "Properly remove useless final states.".

Fixed 'uniq' on commands (algorithm that removes duplicates).

The previous version erroneously skipped a coomand after removal,
so it would fail in case of three identical commands in a row.

Don't loose liveness of tags that occur on both sides of 'copy' commands.

When processing chain of 'copy' commands like 'x = y; y = z;'
one should first mark all left hand sides ('x' and 'y') as dead,
then mark all right hand sides as alive ('y' and 'z'). This way
'y' will end up alive, as it should be.

Found by slyfox's fuzzer. :)

Properly remove useless final states.

Before this commit the algorithm considered final state useless only
if its rule is unreachable in this state. However, this leaves out
cases when final state is shadowed by other final states of the same
rule (longer alternatives of the same rule always match). In such
cases the rule is reachable because some (maybe all) outgoing accepting
paths match the same rule.

Now the algorithm considers final state useless if all outgoing paths
are accepting (there's no default transitions and default rule is
unreachable in all successors).

Retry tunnel optimization if the first attempt is unsuccessful.

This is probably a decades-old typo (misplaced 'break' statement).
Surely the author intended to try all successors, not just the first one.

Added debug option '--dump-adfa'.

Topologically sort 'copy' commands.

The order in which copy commands are executed is important:
'x = y; y = z;' is not the same as 'y = z; x = y;' (the latter
overwrites 'y' before its precious value is copied to 'x').
To avoid overwrites, commands should be topologically sorted.
This is always possible because there's no cyclic dependencies
by construction.

Found by slyfox's fuzzer. :)

Added debug options '--dump-dfa-det', '--dump-dfa-tagopt' and '--dump-dfa-min'.

Skeleton: apply 'copy' commands before 'save' commands.

This is how the generated TDFA does and how it should be done.

Found by slyfox's fuzzer. :)

Allow nondeterministic tags.

This commit makes some important changes:

    - Each DFA state under construction keeps a set of tag versions
      (which version of each tag is actual for each NFA sub-state).

    - Tag versions now have priorities which allow to disambuguate
      between two competing configurations when building tagged epsilon-
      closure. We try to maximaze value of each tag, thus versions
      that correspond to greater tag value have greater priority.

    - Comparison of DFA states (when trying to find an existing state
      equal to the new one) has become more complex. We try to find
      a similar enough (not necessarily identical) state: one that is
      equal to the new state up to reordering of tag versions. Mapping
      should be either bijective or injective (new state must be less
      or equally versatile then the old one), default is bijective.
      Mapping should not violate tag priorities: relative order of
      versions must hold (absolute values of priorities don't have to
      coincide).

    - On each update tag gets new version: if tag is updated to bottom,
      it gets negative version; otherwise it gets positive version.

    - Different tags that updated by the same transition still get
      different versions. This may seem to be a waste: we know exactly
      that input position is equal for all tags on the same transition,
      even more, for all tags on all outgoung transitions from the same
      state, so we can alocate exactly one version for all of them.
      However, allocating one version for different tags creates states
      with a very specific tag configurations: these states don't map
      to existing states and the automaton gets bloated (sometimes
      exponentially). Furthermore, allocating independent versions is
      good for optimizations.

    - Second pass of optimizations: it only makes difference for one
      test case (usually the first pass does a good job), but it's cheap
      (all the necessary infrastructure is in place) and powerful.

    - The resulting automaton is similar to Laurikari's TDFA, except
      for one important difference: re2c's automaton makes use of
      lookahead tags, while Laurikari's does not.

Added test: tags in trailing context.

Keep fixed and variable tags separately.

This commit reverts commit de3f9e70a45c42fcb848a347ece3a727b8fb983e:
    Keep fixed and variable tags together in one array.
Optimizations of variable tags get more complicated and fixed tags
should not get in the way.

This commit also drops check for tags in trailing context: there's
nothing special about them; no technical reason to forbid them.

Merged computation of fixed / variable tags into NFA construction.

NFA construction is already complex because of insertion of default tags,
now it gets even worse. However, keeping two separate passes requires
maintaining exactly the same order of traversal, which is fragile.

Removed redundant computation.

Tags used in the given sub-regexp are already tracked by tag index;
boolean array is redundant.

Use different datatypes for closures and kernels.

This is a preliminary step for tracking tag versions in closures / kernels.

For now closures and kernels store the same information, but it will
diverge when we start tracking tag versions: closure items will need
some extra-data that is needed during closure construction, but shouldn't
be in kernel.

Kernel representation should also allow efficient comparison for identitiy
or compatibility (for mapping).

Skeleton: fixed comparison of transition tags during construction.

At the time of skeleton construction DFA has just been build and
all tags in it are just raw pointers to lists of commands. These
pointers are unique for each transition (tags are not shared between
transitions). This means, comparing tags for different transitions
will always result in 'not equal', except if both transitions have
no tags (pointers are NULLs).

Found by slyfox's fuzzer. ;)

Skeleton: generate proper keys for tags.

Instead of calculating all necessary keys, then attributing keys
of the first path to all paths, write proper keys for each path.

Found by slyfox's fuzzer. :)

Track uninitialized tags and set them to default value.

Uninitialized tags come from alternative and iteration:
    ... @t ... | ...
    (... @t ...)*

Tags under alternative preserve their initial value (given to them
before entering DFA) -- they don't have to be explicitely set to
default value (but it is convenient, otherwise we'd have to initialize
all tags every time before entering DFA).

Tags enclosed in iteration might be assigned positional values on
some iterarions, but not on the last one -- their default value must
be restored explicitely before each iteration.

This commit adds specail kind of 'save' commands that set the given
tag to default value (instead of current input position). We insert
these 'save default' commands for tags in alternatives: all tags that
are present on left alternative get default values at the end of right
alternative.

Later on (during DFA construction and optimizations) we treat default
value just like normal positional value: save it to a variable, copy
values between variables, etc. This way DFA gets additional commands,
but the number of states does not grow much.

Another way would be to treat default value as a special bottom value:
instead of saving it to variable, keep a dedicated bottom tag version
and forbid mixing bottom version with other versions. This way default
values would be encoded in the structure of DFA, so there would be no
need to explicitely save them. DFA would gain no additional default
commands, but new states would appear.

Test changes have been verified with '--skeleton'.
Test 'tags/interference.i--tags.re' have been completely rewritten --
the old version no longer captures what it should (see comment in the
test). The old vesion has been moved to 'tags/fallback6.i--tags.re'.

Don't loose 'yyaccept' when fallback and initial states coincide.

Before code generation each DFA state is assigned a specific action.
Actions are mutually exclussive except for one: inital state may
coincide with fallback state. The bug was in overriding fallback
action with initial action (we lost 'yyaccept' which cause the wrong
match).

The bug was found with '--skeleton'.

Reduce all final versions of the given tag to one common version.

Tag may have different final versions in different accepting states
(currently either fallback version of the main version). Now we
reduce all final versions to one (this takes one additional 'copy'
command for normal tags and none for tags that have fallback copy).

Skeleton tests: count re2c crashes as fatal (not expected) errors.

Skeleton: code cleanup: split large function into subroutines.

Skeleton: check tags.

Calculate final tag values during string generation and put them into
'.keys' file together with the length of the consumed / matched input
and the matching rule number. Each pack of keys only gets those tags
that belong to the matching rule (no tags for default paths or paths
corresponding to untagged rules). Tags do not include trailing context,
as it is already included into the length of matching input.

Emulate tag calculation when generating paths for skeleton.

Limited skeleton lifespan to the time of DFA construction.

There's no need to pull the whole skeleton up to code generation phase:
skeleton itself is used only for string generation and tracing undefined
control flow, both things are done after DFA construction and before any
optimizations.

By the time code generation starts skeleton is obsolete: its structure
is no longer in sync with DFA and it shouldn't be used.
Code generation only needs some attributes (key size and default rule
index), which can be explicitely stored in DFA.

Moved '-Wundefined-control-flow' analysis to the point of skeleton generation.

Skeleton: share data with DFA, generate strings before optimizing DFA.

Skeleton must use unoptimized DFA right after determinization, otherwise
it won't be able to track optimization errors. Therefore skeleton must
either use a copy of DFA, or use the original before any optimizations.
Copy-pasting the whole DFA is a waste (especially when it comes to tag
commands, which are stored in linked lists), so we take the second approach.

However, this means that skeleton '.input' files are generated every time
DFA is constructed, not every time DFA is used for code generation.
This explains changes in tests: in reuse mode, we sometimes construct
DFA and never use it for code generation.

Skeleton: don't keep expanded range representation in nodes.

For the most part character range is represented as a pair of bounds.
When generating data for skeleton programs we need to pick some
256 distinct characters from each range; only these characters will
participate in data generation.

Before this commit range expansion happened at the time of skeleton
construction. Now it is delayed until the time of dumping skeleton
paths to file. This means that expansion of particular range is done
multiple times (every time the corresponding skeleton multiarc is
dumped to file). However, data generation only happens with '--skeleton'
option, while skeleton construction is unavoidable.

Added test and comment about tag backups in fallback states.

Moved tag optimizing functions to 'cfg_t' struct namespace.

Moved tag optimization stuff to subdirectory.

Slab allocator for tag commands.

Disallow accidental change of tag commands that share representation.

After inserting commands into common index some of them may share
representations in memory. Initially commands are stored in mutable
lists, which is very convenient for tag optimizations. However,
leaving this representation after indexing is dangerous, because
accidental modification of one command may affect other commands.

This commit hides mutable lists behind indices in hash table.
Table gives read-only access to the lists.

Table index is 32-bit, which is smaller than the previous 'index'
type (a pair of pointers). So in theory command comparison has
become a little faster.

Pre-calculate initial liveness of final tag versions used in rules.

Restricted 'Tagpool' lifetime to DFA construction phase.

Build control flow graph of DFA before tag optimizations.

DFA may be very large, but have only few tagged transitions.
In such cases doing tag optimizations on the whole DFA is a waste:
space aloocations and (respectively) processing time is proportional
to the number of all DFA transitions.

Instead, we spend a little effort to create CFG. It has one basic
block per each tagged transition or tagged final state, plus root
basic block.

Update struct field instead of passing return value.

Added comment.

Constified comparison predicate in lookup table.

Use linked lists instead of arrays for 'save tag' commands.

Fixed-length arrays are widely used during DFA construction, where
we need to keep all versions of all tags in each NFA sub-state of the
DFA state under construction. These arrays are deduplicated, indexed
and stored in a hash table.

However, after determinization we deal with small (probably empty)
sets of tag versions that are updated on a given transition.
Corresponding arrays are sparse. We don't care about storage space
(arrays are deduplicated anyway), but traversing sparse arrays is
wasteful and the code is somewhat bloated.

We already used linked lists for 'copy' commands; now we also use
them for 'save' commands.

Minor tweak in tag version allocation; updated tests.

The previous commit 394fec90c1d7a66f2e13c658c5cc28e0d38c5678
"Use tag versions to implement fallback tags." added copy coalescing
and introduced serious changes to allocation algorithm. It simulated
the order of allocation used by previous algorithm to preserve test
results.

Now we drop this simulation and keep to the natural order: it is easy
to see that changes in test results are caused by different order of
tag version allocation.

Use tag versions to implement fallback tags.

This commit adds new data structure to represent copy commands for
tags: list of pairs (X, Y) which stand for command 'X = Y'.

Previously we used the same bit vectors that are used for constructing
DFA states, but this representation is inconvenient.

We no longer need special tag names (postfixed with underscore) for
fallback tags: we simply use a fresh version for each fallback tag.

Split tag optimization into multiple files.

Introduced tag versioning.

Instead of treating tag as boolean variable (true - present,
false - absent) we now allow it to have many versions. Special
version value 'TAGVER_ZERO' denotes tag absense (corresponds to
'false').

For now, each tag has exactly one version except 'TAGVER_ZERO':
tag's number plus one.

We need tag versions because with only two values it's impossible
to expess more subtle states, e.g. initialized / uninitialized.
Tag versions will also allow to treat fallback tags like any other
tags (in particular, allow them participate in deduplication).
In future, when we add nondeterministic tags, versions will be used
to implement tag copies.

Moved tag liveness data out of Tagpool.

This is necessary to introduce tag versions: we'll have to
calculate liveness of tag versions (rather than tags) and won't be
able to keep liveness data in Tagpool.

Tag liveness: use control-flow analysis instead of backward propagation.

This commit effectively reverts commit eeceb1d5baf3f868a64bf5fa0408f0a06cc48285,
"Use backwards propagation for liveness analyses on tags.", which changed
control flow analyses to backward propagation of liveness from final states.

The reason for rollback is that common control-flow analysis is more
general. Backward propagation is simple if tags are only used in final states.
While this is currently true, but we'll have to allow tag uses on arbitrary
arcs, and this will complicate backward propagation a lot.

Make tags absolute, not relative.

Relative tags have some advantages:
    - only base marker has to be updated by YYFILL
    - ever-broken old code with overlapping trailing contexts
      can be fixed without user's help (provided that re2c
      autogenerates declarations of tag variables)
    - fixed-length contexts may be used with generic API
      (though it becomes less generic with relative tags,
      as we rely on the concept of relative offset)

However, the generated code is less efficient in simple cases
(default API, no YYFILL): relativity adds extra arithmetics with base
marker (which implies dereference of base marker in most of the cases),
so the code is actually worse than hand-written.

Even with YYFILL it turns out to be more efficient to keep all tags
in a struct together with other pointers and update them once in a
while: YYFILL is called very infrequently (if properly implemented
by the user), while tag operations happen unconditionally.

However, making tags absolute means that re2c will fail with error
on old code with overlapping trailing contexts (unless they have fixed
length or can be deduplicated). These cases are probably rare.

Generic API can't make use of fixed tags, but becomes truly generic:
'YYBACKUPTAG / YYRESTORETAG / YYCOPYTAG' make less assumptions
about the input.

Don't generate 'yyt<N>' variables without explicit '/*!tags:re2c*/'.

Reasoning:
    - with YYFILL, one must use '/*!tags:re2c*/
    - without YYFIL, one might still want to use '/*!tags:re2c*/'
      (e.g. to avoid warnings about initialized variables)
    - unconditional behaviour is easier to remember
    - everyone who uses tags should know about '/*!tags:re2c*/'
    - re2c code is simpler

Problems:
    - without scoping rules multiple blocks with tags are troublesome

Note that actual code generation for '/*!tags:re2c*/' is still delayed.

Renamed configurations and updated tests.

    'tags:line' -> 'tags:format'
    'tags:sep' -> 'tags:separator'

Merged 'ir/tagpool.{h,cc}' files into 'ir/tag.{h,cc}' files.

Renamed header and added forgotten function.

Forbid fixed tags in case of generic API.

This is a preparation step before making tags absolute (rather than
relative to context marker). Generic API should make no assumptions
about the input source; in particular, it should not rely on the
notion of distance between input positions.

Dump final tag values to variables; actions must use these variables.

Having one variable per tag name is convenient:
    - tag calculation is not duplicated if tag is used multiple
      times in the action body
    - tag name is an l-value
    - there's no need to patch actions

Variables are user-defined: users know which variables they need
(unlike distance variables 'yyt<N>', which are generated by re2c
and affected by things like tag fixedness, deduplication, etc.);
users may also want to initialize these variables in some particular
way.

Renamed configuration 'tags:expr' to 'tags:expression'.

Renamed default tag prefix from 'yytag' to 'yyt'.

Buffer statements into a list to avoid complex pre-counting.

Formatting of 'if' or 'case' statements depends on the number of
statements in the correspoonding code block: multi-statement blockss
must be wrapped in braces or extra-tabulated.

Estimating the number of lines has never been particularly elegant,
but it gets worse every time we add possible new instructions to
transitions.

Backup overwritten tags in fallback states.

We need to backup tags in fallback states: these tags may be
updated on some non-accepting path from fallback state, and if
the attempt to match longer rule fails, there's no way to restore
the overwritten tags.

Such tags may appear in self-overlapping rules, e.g.:
    (@p "ab")* {}

We create a special backup variable for each potentially overwritten
tag. Backup tags do not participate in deduplication.

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