Compact tag versions before doing liveness analysis.

After TDFA construction tag versions occupy non-contiguous range
of natural numbers: there may be "holes" between versions. This wastes
space (and time) spent on liveness analysis and subsequent optimization
passes. This commit adds a simple pass that renumbers versions so that
they occupy contiguios range.

Updated parser for bison-3.0.4.

Added option '--no-lookahead'.

This option makes re2c generate TDFA that does not exploit lookahead
symbol when making tagged transitions.

Added option '--eager-skip'.

This option allows to control program points in which cursor is
advanced to the next input character. Normally it happens after moving
to the next state (lazyly). With '--eager-skip' cursor is advanced
before moving to the next state (eagerly).

Eager mode presents some difficulties compared to the lazy mode:
transitions may disagree on whether advance cursor or not. Some of
them may go to accepting states and should not advance cursor, while
others go normal states and should advance cursor. In such cases
advancement must happen on a per-transition basis. If all transitions
agree on the matter, advancement can be hoisted out and performed on
a per-state basis, just as it happens in lazy mode.

Reuse mode: always reparse rules and restore options of the rules block.

Consistently use current block's options for code generation.

Fold output expressions in a separate pass over the output.

re2c folds sequences of simple statements to complex tatements, e.g.:
    ++YYCURSOR;
    yych = *YYCURSOR;
is folded to:
    yych = *++YYCURSOR;

It is hard to fold expressions on the fly (at the time they are generated),
because one needs to forsee all the cases in advance. Some cases cannot be
anticipated (e.g. if substatements belong to different states, which is often
the case), so many statements remain unfolded.

This commit separates code generation and folding by delaying output of
skip, peek and backup primitives. Folding now is done in a separate pass
when all the substatements are already known.

Memorize options for each block and use them for delayed code generation.

Option scope is very poorly defined in re2c. Most options should have block
scope, but some have global scope (because they belong to global directives
like '/*!types:re2c ... */', '/*!tags:re2c ... */' or other global things
like generation date, etc.).

For now, options are applied immediately as they are parsed.
Code generation just reads the most recent state of options, so the output
depends not only on the location in source code when the option is defined,
but also on program points in which re2c generates and outputs code.
Generation and output may happen at different times, so they may use
different options. This is all very bad.

This commit is the first attempt to introduce scoped options: re2c now
makes a snapshot of options at the end of each block and uses this snapshot
for delayed code generation for this block (unless the given option must be
global).

This is not perfect (immediate code generation still uses 'seen-so-far'
options instead of block options), but at least it allows to delay code
generation for non-global things without loosing options.

Delay code generation for condition dispatch.

Finally separated parsing, consistensy checking and after-parse transformation.

Updates in test results are caused by the changed order of condition
compilation, see commit b7bbbf471778b487d0717c85a5e586b595e495ec.
Changes do not affect code generation, only the error messages.

Emit conditions ordered by their number rather than lexicograhically.

Each condition has a unique name and unique number. Numbers are assigned
to conditions in the order they appear in source file. This order must
be preserved since some users rely on it (user code makes implicit
assumptions about condition order, see '-Wcondition-order').

However, once the order is preserved, the automata code can be emitted
in any order (user code can only address conditions by their start label,
and it can be anywhere in the output file).

This commit changes the order of automata: now they are emitted according
to their numbers, not names.

Test results have changed in cases when lexicographical order does not
coinside with number order. The changes touch some important files and
are not easy to verify. However, rearranging conditions in the generated
code back in lexicographical order makes the differences trivial (labels,
'YYDEBUG' parameter, 'YYFILL' labels, 'YYSETSTATE' parameter --- in other
words, everything that depends on state numbering). It is easy to see
that the structure of the code is not changed.

Reuse 'Code' data struct for setup code.

Reduced one argument to function as it is a part of another argument.

Parser: started gathering all error messages in one place.

Keep startup code '<>' separately from other rules.

Keep '*' rules separately from other rules.

Setup code for rules belongs in DFA scope, not the entire block scope.

Restructured parser grammar to explicitly list different rule types.

Parser grammar: separate production for code in conditional rules.

Pass context as parameter to 'yyparse' instead of a bunch of static variables.

As a side effect of this commit a long-standing bug with setup rules
has been fixed: re2c forgot to clean up the list of setup rules together
with other data, which resulted in false errors about duplicate setup code.

Removed unused typedef.

Fixed memleaks (found by valgrind).

Handle all types of rules in one place (in parser).

Simplified handling of user-defined code in parser.

Inlined small function with only one user.

Simplified line tracking in lexer.

Separated compilation pass from code generation pass.

They might be totally disconnected in case of '-r' option and it's
more convenient to handle them separately.

Parse rules in a uniform way regardless of the '-c' option.

Simplified parsing of startup code '<>'.

Don't use special token type for '<!' and '<>'.

Parse them as character sequences.

Further simplified default rule parsing.

Simplified handling of default rule in parser.

Don't loose condition if it consists of default rule only.

Simplified '*' condition handling in parser.

Moved variable from global scope to function scope.

Make 'Scanner' parameter to 'yyparse' instead of global variable.

Removed empty header 'globals.h' and all includes of it.

Removed variable from global scope.

Removed variable from global scope.

Removed variable from global scope, simplified bitmaps.

Removed variable from global scope.

Removed variable from global scope.

Removed warnings from global scope.

Removed options from global scope.

Simplified code generation for initial state.

Simplified generation of code for buffer refilling.

Don't delay reading next character until dispatch.

Instead of sometimes generating code like this:

    ++YYCURSOR;
    switch ((yych = *YYCURSOR)) {

re2c now always generates

    yych = *++YYCURSOR;
    switch (yych) {

There's not much difference: it's hard to say which would be better
optimized by C/C++ compiler. Most likely they would be optimized
equally well; practical experiments with GCC -O2 resulted in bit-to-bit
identical binaries.

However, dropping the first form allows to cut off a lot of tricky code
in re2c itself (a whole layer of code spread across multiple files was
tracking whether next input character has been already read or not).

Changes to the test results are multiple, but trivial; they have been
verified with skeleton.

Don't peek next input character if all transitions go to final state.

A similar heuristic already existed, but it was imprecise and captured
only those cases when final state happened to be next to the one in
question.

A lot of tests were updated; however changes are trivial and I verified
them with skeleton.

Renamed option '--dfa-mapping <bijective | injective>' to '--non-bijective-mapping'.

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.