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.

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.