Add const to newver_t operator()

A certain set of compilers gives a compiler error due to losing
"const-volatile qualifiers"

Allow trivial cycles (of length 1) in tag commands.

We forbid cycles of length 2 or more because they would need temporary
variable local to the basic block, which would complicate liveness
analysis. However, trivial cycles don't need a temporary.

Fixed typo that caused miscalculation of new tag version.

Invert comparison result instead of negating its arguments.

Skip (non-orbit) start tags during POSIX disambiguation.

Their position is fixed on some higher-priority tag (except the very
first tag, but in RE2C match is always anchored).
We cannot skip orbit start tag because the corresponding orbit end tag
is hoisted out of loop (by construction) and is, in fact, non-orbit.

Once again fixed history comparison for POSIX disambiguation.

Use Goldberg-Radzik shortest path algorithm for closure construction.

It has O(M*N) worst-case complexity, where M is the number of nodes (states)
and N is the number of arcs (transitions).

Papers: 1993, "A heuristic improvement of the Bellman-Ford algorithm"
by Goldberg, Radzik and 1996, Shortest paths algorithms: Theory and
experimental evaluation" by Cherkassky, Goldberg, Radzik.

Compare full tag histories, not just the last subhistories.

Comparing the last pair of subhistories is not enough: because of
the shortest-path algorithm mismatch may occur at some earlier point
(not at the last pair), in which case we still need to re-run the search.

Simplified queue handling in epsilon-closure algorithm.

Use the same comparison functions for closure construction and order calculation.

Use two tags instead of three for captures under iteration.

Before we simplified POSIX disambiguation by inserting missing
captures, using three tags to represent captures under iteration
was the only way: we needed to guard where the first iteration starts,
where the last iteration starts and where the last iteration ends.
Therefore we used three tags: opening, closing and orbit.

Now that we insert missing pieces of capture hierarchy, we no longer
need a special opening tag for captures under iteration: there always
is a higher-priority tag that guards the start of the first iteration.

Massive test updates are mostly due to the fact that orbit tag is no
longer fixed (fixed tags go in the end): ~100 out of 147 tests.
Some other ~45 tests have two tag variables flipped. There are 4 tests
with non-trivial changes. All updated tests pass POSIX test
(/test/posix_captures/.run/__run.sh).

Silenced '-Wnondeterministic-tags' warning with '--posix-captures'.

Skeleton should ignore fictive tags.

The combination of options '--skeleton' and '--posix-captures'
didn't work properly.

Forbid mixing leftmost greedy and POSIX disambiguation.

Mixing doesn't make much sense (there is no obvious use case).
It might be possible, but for now better forbid it before someone
starts to use it and it turns out to be impossible or very complex.

Simplified POSIX disambiguation by reconstructing capture hierarchy.

POSIX treats captured and non-captured subexpressions on equal terms.
However, non-captured subexpressions have no tags to guard them.
Previously we used default tags to infer ambiguous paths that correspond
to the missing captures: if one path had default tag and the other did
not, then desicion which path is better was made according to the leftmost
strategy. This algorithm works because in POSIX expressions without
captures have the property that leftmost path is the best path (for
example, 'a?' is greedy, it means 'a or epsilon').

However, this algorithm has one downside: because we may need leftmost
comparison, we have to impose leftmost order on NFA substates of each
DFA state, as well as maximize and orbit order for tags. This prevents
us from mapping perfectly mappable DFA states and we end up with a larger
DFA (which is sometimes folded back to smaller DFA, but not always).

Also, default-leftmost algorithm is more complex than inserting missing
hierarchy pieces: proving that it works is non-trivial.

Fixed history comparison in case both latest subhistories are bottoms.

In this case, instead of comparing histories by the leftmost criterion
(as it should be, if only one of them is bottom), we should assume that
from standpoint of this tag histories are equal and move on to other
tags.

Avoid exponential blowup in tagged epsilon-closure construction.

The previous algorithm waited until the full epsilon-path is built,
then compared it to already existing paths. The new algorithm compares
and merges partial epsilon-paths as soon as they arrive at the same
NFA state, so the overall number of paths is bounded by the number of
NFA states at all times.

Don't split tag history into individual sub-histories for tags.

This is necassary for correct comparison of orbit tag histories:
if orbit tag is nested in an outer capture, this outer capture is
under repetition and there is an epsilon-path through it, then
this epsilon-path may contain pieces of orbit history that belong
to different iterations of outer capture; these pieces will be
glued together and the boundary between them will be lost.

Example: ((""){0,3}){0,2}.

However, in a common history we can always find boundaries
(they are marked by tags that correspond to outer captures).

Skeleton: constified tag variables to get rid of compiler warning.

Command normalization: update pointer to last command, it might change.

If normalization of 'save' commands removes the last 'save' command,
then pointer to 'next' will point to the 'next' field of the removed
command and the chain of commands will break.

Added comment.

release.sh: added cppcheck and headers check to wish list.

Forbid dependency cycles in tag commands.

The previous attempt was to forbid 2-cycles; clearly it's not enough
and cycles of length greater than 2 also pose a problem.

We could allow cycles and deal with them by introducind a temporary
variable. However, this would create variables local to basic blocks,
which would complicate liveness analysis and dead code elimination.

Tag interference analysis: compare actual values, not formal RHS.

Commands in the same basic block may have equal right hand sides,
e.g. 'x = y; z = y;'. Clearly in this case 'x' and 'z' do not interfere:
both versions are equal to 'y'. This optimization allows to deduplicate
cases like '("a" @x @y @z "b")*', where multiple tags have the same
values.

However, it is insufficient to find all commands in the current block
with RHS equal to current RHS. An example when this algorithm fails:
'x = y; w = z; z = y;', here 'x' and 'z' are assigned to the same RHS
'y', but if we merge them into one variable, 'w' will get the wrong
value.

The fix is as follows: first, ignore subsequent commands and consider
only commands that precede current command: if subsequent command that
sets LHS to the same value precedes any use of it, liveness propagation
through basic block would mark this LHS as dead and not interfering
anyway; otherwise (if use precedes setting to the same value), then it
indeed interferes with current LHS. This fixes the above example
'x = y; w = z; z = y;': when analysing 'x = y;' command we find that
'z' is alive (as before), but ignore subsequent 'z = y;' command (due
to the fix).

Second, when analysing preceding commands, calculate actual value for
each LHS (based on pessimistic assumption that on entry of basic block
all used versions are different). Formal RHS of some preceding command
may coincide with current formal RHS, but their values might differ:
'x = y; y = w; z = y;', here 'x = y;' and 'z = y;' have identical formal
RHS, but the value may be different. On the other hand, formal RHS
might be different, while their actual values are equal, as in
'x = y; w = y; z = w;'.

Skeleton: don't forget to return error in case of tag mismatch.

Final tag versions in unreachable rules should be marked as unused.

'--dump-adfa': fixed pretty-printing of tag commands.

Preserve order of commands when adding fallback tags.

Added debug for tag optimizations (CFG and interference table).

Record full history for history-based tags on epsilon-paths.

Keep tag histories for the whole time of determinization.

Topsort: always initialize in-degree with zeroes.

Don't rely on the fact that topsort leaves all-zero in-degree:
it doesn't if cycles are present. One could manually zero the remaining
entries after topsort, but zero initialization is more reliable.
And it's quite efficient since we only need to initialize the entries
we use.

Don't forget final and fallback commands when looking for history-based tags.

Merged a couple of slightly different 'topsort' versions into one.

'save' commands also need topological sorting: they may depend on history.

When mapping states, avoid double substitution in 'save' commands.

When mapping states, we need to create a list of 'copy' commands.
However, if there is a 'save' command with LHS equal to RHS of the 'copy'
command, then instead of the 'copy' command we just fix LHS of the 'save'
command, as explained in this note:

    /* note [save(X), copy(Y,X) optimization]
     *
     * save(X) command followed by a copy(Y,X) command can be optimized to
     * save(Y). This helps reduce the number commands and versions (new version
     * X is gone), but what is more important, it allows to put copy commands
     * in front of save commands. This order is necessary when it comes to
     * fallback commands.
     *
     * Note that in case of injective mapping there may be more than one copy
     * command matching the same 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).
     *
     * For each save(X) command there must be at least one copy(Y,X) command
     * (exactly one case of bijective mapping). This is because X version in
     * save(X) command must be a new version which cannot occur in the older
     * DFA state. Thus all save commands are transformed (maybe replicated) by
     * copy commands, and some copy commands are erased by save commands.
     *
     * This optimization is applied after checking priority violation, so it
     * cannot affect the check.
    */

However, the previous implementation would sometimes erroneously re-fix
the already fixed 'save' commands. This patch rewrites it in a way that
avoids re-fixing.

Fixed checking duplicates when creating tag commands.

Don't forget histories when comparing right hand sides of tag commands.

Skeleton: don't emit declarations for tags that are optimized out.

Don't forget initial tag command when looking for history-based tags.

Tag histories in commands must be addressed by absolute value.

Don't sort and deduplicate 'save' commands for tags with history.

Otherwise chains like '2=(1,x); 1=(1,y)' will be rewritten to
'1=(1,y); 2=(1,x)', which is a totally different thing.

'save' commands for tags with history may need fallback copies.

For simple tags without history 'save' command is self-sufficient:
it does not depend on anything. However, for tags with history 'save'
commands depend on history, which may be overwritten on the way from
accepting state to fallback transition. We must take care and backup
such overwritten histories when leaving the accepting state.

If history is not overwritten, we don't need a copy, but we still
have to propagate its liveness forward on all fallthrough paths
outgoing from accepting state.

Added skeleton support for tags with history.

Fixed order of tag commands.

First, fallback 'copy' commands should go before 'save' commands.
Second, codegen should not reorder 'copy' and 'save' commands.
These two bugs shadowed each other and everything seemed to work.

Changed generic API for tags.

    - removed 'YYCOPYTAG', use simple assignment insted
      (it is hard to think of any other definition)
    - renamed 'YYBACKUPTAG' to 'YYTAGP'
    - added 'YYTAGN', 'YYTAGLISTP', 'YYTAGLISTN'
    - removed 're2c:tags:default' configuration

Added codegen primitives for tags with history.

Fixed tag optimizations to respect tags with history.

Added syntax for tags with history.

Started to add optional history for each tag.

This patch adds tracking and saving tag history during determinization;
however, optimizations and codegen totally neglect histories.

Separated lookahead tags from tag versions in closure items.

This commit reverts commit 0b2ca9bf141259baf6cb0b067621c06db5f06b46:
"Pack lookahead tags together with tag versions in TDFA state."

Packing was possible because we were not interested in tag version
if closure item had this tag in lookahead set. However, if we are
to store the full history of each tag, we'll need this intermediate
version in spite of the fact that it is overwritten on the next
transition.

Fixed liveness analysis inside of basic block.

Liveness flows backwards through basic block, so it should be
propagated backwards starting with live-out set and applying
commands one by one in reverse order.

Merge 'save' and 'copy' command lists into one common list.

Previously we used separate lists for them; however the structure
of 'save' and 'copy' commands is almost identical, so its easy to
use one C struct for both types. Also, this simplifies analysis:
both types of commands are handled in a uniform way.

However, now we have to do list transformations like sorting and
deleleting duplicates in chunks.

This is a preliminary step to allow intermixing 'copy' and 'save'
commands.

Explicitly track order of closure items for leftmost disambiguation.

Before this commit leftmost order was maintained implicitly by construction
of closure: NFA is traversed in left-first order, so the earliest item added
to closure is also the leftmost. Special care was taken to preserve this
order and never rearrange closure elements.

This is convenient if leftmost disambiguation strategy is the only one.
However, other strategies require explicit bookkeeping of disambiguation
information (POSIX needs tag history for orbit tags, maximize/minimize
needs most recent tag versions). Implicit handling of leftmost strategy
does not fall in line with other strategies.

By tracking leftmost order explicitly we achieve several goals:
    - uniform handling of disambiguation strategies
    - DFA states can be treated as good old sets again, which is more
      conventional and means less work for minimization

POSIX tests changed (but the '/test/posix_captures/.run/__run.sh' script
still passes all tests) because there was an error in the order items were
added to closure, which probably prevented minimization (if the new item
dominated the existing one, the old one was substituted with the new one,
while it should have been removed and the new one appended at the end).

Skeleton tests changed because the order of NFA states in DFA state does
not matter, so more states can be merged by determinization.

Forbid 2-cycles in tag commands; fixed topsort to skip cycles.

Moved a couple of files.

Moved the main driver out of parser grammar file.

Split options into constant and mutable; restricted access to mutable ones.

Some options are immutable (target, output files; global switches like
conditions, reuse mode, storable states; support of flex syntax, etc.).
These options are passed as command-line arguments and never change.
It is safe to read them from any program point after parsing command-line
arguments.

Other options are configurable; they have block scope (may be specified
anywhere inside of the block and still affect the whole block).
Reading mutable options of yet unparsed block is not allowed because
they may affect the way RE2C parses current block (RE2C would be tempted
to base decisions on the latest option value, which may not be the final
one).

Forbid configuration of certain options.

Configuration of these options either makes little sense (like changing
target on the fly) or is technically impossible to implement (the only
example is '-F, --flex-syntax' option which non-trivially affects the way
RE2C parses programs).

'-Wcondition-order': check '-t, --type-header' option together with other conditions.

Moved enum out of struct and added prefix 'TARGET_' to all members.

Delay check if tags are allowed until the whole block has been parsed.

Now that we never re-parse anything we can always dicard old data.

Tests for POSIX captures: avoid using 'flags:flex-syntax' configuration.

Use '--flex-syntax' command-line option instead.

The actual tests are not changed by this commit.

Allow to set new encoding without explicitely resetting the current one.

More elegant handling of flex definitions.

Check precondition inside of the function rather than at every call site.

Changes in tests are caused by the lack of newline after '/*!ignore:re2c*/'
directive. There's no particular reason why it should be emitted and RE2C
code is simpler without it.

Gathered all error checking related to '-r' option in one place.

Moved remaining option-sensitive code away from AST.

AST must be immutable and independent of options: it may be shared among
different blocks and conditions and reused with different options.

Merged small header with part of AST into big header with the whole AST.

Renamed 'RegExp' to 'AST'.

Don't ever reparse '/*!rules:re2c ... */' block.

AST is immutable and independent of options: encoding expansion and other
option-sensitive transformations are delayed until AST is converted to
intermediate representation. Thus AST can be shared among different blocks
and conditions and reused with any set of options without modifications.

Changes in tests are trivial: warnings from the rules block are no longer
emitted (we don't compile AST to DFA for rules block anymore, since it
will be discarded anyway); skeleton tests no longer emit '.input' and
'.keys' files for rules block.

Restructured source files layout.

Delay encoding expansion until AST is converted to intermediate representation.

Store locations in AST so that error reporting does not depend on parser.

This allows us to delay things that should be delayed (like expanding
regexps with respect to current encoding), but which may throw an error
and need location info.

Added test for '--posix-captures': implicit grouping is forbidden.

RE2C has named definitions, which allow to override operator precedence
without grouping parenthesis. However, in POSIX all parenthesis are
capturing: allowing some of them to be non-capturing would affect
disambiguation and might result in a different parse.

For now RE2C uses a crude criterion to determine if the given named
definition needs to be explicitely wrapped in parenthesis: if the topmost
constructor of the subexpression is either alternative, or catenation, or
another reference to another named definition, then wrapping is required.
This is an overapproximation, because it doesn't take the surrounding context
into account (e.g. catenation inside of an alternative doesn't need wrapping,
but catenation inside of an iteration does).

Added tests for POSIX captures.

Tests are adopted from Glenn Fowler's testregex suite and its derivative
regex-posix-unittest by Christopher Kuklewicz.

Irrelevant tests have been dropped:

    - tests for specific POSIX features not supported by RE2C, like
      begin/end markers '$' and '^', backreferences, predefined character
      classes (most of them come from 'basic' subdirectory)

    - all 'leftassoc' tests: they are exact copies of 'rightassoc' tests,
      differ only in match results and are supposed to fail

    - all tests from 'categorize' that are supposed to fail

I also added a few tests of my own (in the 'other' subdirectory).

Tests are arranged as a bunch of '.dat' files (each file contains lines of
the form '<regexp> <string> <match>' or blank lines) and two scripts.

    - '__run.sh' runs all tests (generates temporary '.re' file with the
      given regexp, compiles it, runs against the given string and checks
      that the result coincides with the given result)

    - '__gen.sh' regenerates '.re' files for regular RE2C test suite (the
      generated files do not contain any code, just the bare regexp)

All regexps are pre-patched to exclude '\x00' (terminating NULL) character
from subregexps like '.' or '[^a]: otherwise RE2C-generated programs would
greedily consume all characters and fail. Note that if only '.' was present
in the original tests, we might have used '\n' as terminator, but '[^a]'
includes newline. Also '()' subregexp was substituted with '("")'.

'--skeleton --posix-captures': use correct capture index when checking tags.

Instead of skipping fixed tags, skip orbit tags. For each orbit tag there is
a tag fixed on it, so if we check all fixed tags we'll surely check all orbit
tags. Anyway, with '--skeleton' all fixed tags correspond to orbit tags: other
fixed tags are forbidden with generic API (even zero-offset ones for now).

Remove dead 'copy' commands.

For some reason dead code elimination pass simply ignored 'copy' commands
and removed only dead 'save' commands. Strange as it seems, this went
unnoticed until now (when one of the POSIX tests compiled into C++ code
that triggered GCC warning about use of uninitialized variable).

Fixed code generation for '--skeleton' with '--posix-captures'.

Added option '--posix-captures'.

With this option re2c interprets all parenthetised subexpressions
as POSIX capturing groups and returns submatch according to POSIX
disambiguation rules (in variables 'yynmatch' and 'yypmatch', local
to each action).

The algorithm for disambiguation was invented by Christopher Kuklewicz.

Now code generation can handle zero-offset fixed tags with generic API.

We'll need this for POSIX captures: in the prsence of orbit tag,
opening tag is needed only for disambiguation; after determinization
we can pretend that it is fixed on orbit tag with zero offset.
This will save some time and space on tag optimizations and maybe
reduce the number of tag variables.

Prepare default tags insertion for non-sequential tag enumeration.

This will be needed when we add POSIX captures: opening and closing
capture tags must have sequential numbers, but the tags may be located
far from each other in the regexp tree (other tags are possible on
the way from the opening tag to the closing tag).

Delay expansion of counted repetition until NFA construction time.

This is necessary to avoid creating default tags for tags that
are duplicated by expansion of counted repetition. Default tags
should only be created if zero repetitions are acceptable; this case
is still expanded early.

Keep the full history of tag occurences found by epsilon-closure.

Currently this makes no difference because tag duplication in NFA
is forbidden. Anyway, we are only interested in the last occurence
of each tag on the epsilon-path to the given NFA state.

This will make difference for POSIX disambiguation strategy: we'll
have to allow tag duplication in NFA (because of counted repetition
and iteration expansion).

Moved splitting charset and nullable rule analysis from AST to regexp.

Added yet another intermediate representation (after AST, before NFA).

Rationale: AST must be immutable, because it is shared among different
regexps, rules, conditions and blocks. NFA is mutable, but inconvenient
for some transformations (adding fixed and default tags, rewriting parts
of regexp, etc.). Before this commit all these transformations were done
in one pass (during convertion of AST to NFA) which made the code rather
complex. In order to add POSIX captures we'll need to add even more
complexity (tracking captures, creating tags for them, maintaining tag
order, etc.).

'--dump-nfa': correctly print symbol ranges on NFA transitions.

Keep fixed and variable tags together in one array.

One must take fixed tags into account during determinization
if disambiguation policy is based on tag values.

Also, NFA construction is much easier when tags have common enumeration:
it allows to perdorm tag creation, tag fixing and adding default tags
in three distinct passes (for now they are intermixed and the code is
very complex).

Stop preserving order of tag versions when mapping TDFA states.

We no longer need it; now that disambiguation policy is leftmost rather
than tag-centric, relative order of tag versions is irrelevant.
Tag versions have no impact on conflict resolution; any bijective
mapping is ok.

Moved tests to subdirectory.

Changed disambiguation policy: leftmost rather than tag-centric.

Instead of tracking priority for each tag version and resolving conflicting
configurations encountered by the epsilon-closure based on version priorities
(trying to minimize or maximize each tag), we now simply pick the leftmost
epsilon-path through the NFA.

NFA construction has to accommodate this policy: for example, greedy iteration
should be compiled so that always choosing the left alternative correpongs to
re-iteration, while choosing the right alternative corresponds to leaving the
iteration. The necessary adjustments have been done by earlier commit
03c65121da3f8bcb412576568cfff6cbca039470.

Now we can drop priority comparison when mapping TDFA states and stick to
simple bijection. This may add cycles in reordering commands. (Has not been
done yet.)

The rationale of switching to leftmost policy is this: with tag maximization/
minimization policy tags could influence the regexp: for example, regexp
    "a"* @p "a"*
has different meaning depending on whether tag 'p' is minimized (first iteration
is non-greedy) or maximized (first iteration is greedy). Moreover, adding
another tag with the opposite policy and higher priority would change the
meaning (suppose 'q' is minimized and earlier tags have higher priority):
    "a"* @q @p "a"*
This all makes regexps somewhat fragile, since adding just one tag may change
the whole regexp (and in the presence of other tags, it may change parse
results).

But even worse, with tag-centric disambiguation simple (untagged) subexpressions
are inferior to tagged ones. This contradicts intuition and even POSIX standard,
where  a*(a*)  is the same as  (a*)(a*) . We don't keep to POSIX (and we can't
because of last-longest instead of first-longest semantics of iteration as shown
by the  (<|<a|<ab|<aba|abab|baba|b>|>)*  example), but even this somewhat
tag-centric standard respects non-captured parts of the regexp. Note that
Laurikari in his TRE library has to do special preprocessing of the regexp in
order to assign correct minimization/maximisation direction to each tag
depending on the context of the tag. His original tag-centric policy (open tag
is minimized and has higher priority than closing tag which is maximized,
nested tags have lower priority) is insufficient to accommodate POSIX.

Don't trace tags in epcilon-cycles when building tagged epsilon-closure.

In greedy regexps first alternative must correspond to consuming path.

By convention first alternative has higher priority.
So, for example, the following must be true:
    r*     = rr* | <empty>
    r{n,m} = r{n} (r{m - n} | r{m - n - 1} | ... | r{1} | <empty>)
    r{n,}  = r{n} (rr* | <empty>)

For now we don't care about priorities: this is a preparatory step
before transition to greedy leftmost semantics for tags.

Tags that occur earlier in regular expression must have greater priority.

Added debug option '--dump-nfa'.

re2c: cleanup a few clang ++ warnings

Found those as:

    $ make CXXFLAGS="-Weverything -Werror -Wno-gnu-statement-expression -Wno-nested-anon-types"

- cleaned struct<->class declaration mismatch
- 'static' around local function
- 'RE2C_GXX_ATTRIBUTE ((noreturn))' around functions known to fail

Signed-off-by: Sergei Trofimovich <slyfox@gentoo.org>

Pack lookahead tags together with tag versions in TDFA state.

This packing is possible because we are never interested in version
of the tag if the given item has this tag in lookahead set.

Use 'normal form' of version matrix to test if states are mappable.

Normal form is calculated for every new state before searching for
a mappable counterpart. All versions are renumbered to occupy consequent
numbers starting from one; version order is preserved.

Added tests that fail if mapping of TDFA states ignores version order.

These tests result in incorrect automaton unless mapping preserves
relative order of versions in TDFA states (respects version priority).