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

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.