Cleanup in code generation (mostly formatting).

Simplified rule tracking during DFA construction.

Simplified collecting context names during code generation.

Rule contexts are consecutive, so we only need to store bounds.

Count contexts after deduplication.

Break from loop if the remaining iterations have no effect.

Cleaned up code that merges arcs while tunneling DFA.

Behaviour should be unchanged.

Moved conditions and contexts from global scope to block scope.

Directives like '/*!re2c:types*/' and '/*!re2c:contexts*/' have
global scope, they are not binded to any particular block and therefore
accumulate items (conditions/contexts/etc.) from the whole program.

There's currently no way to bind these directives to a particular
block (re2c will probably add scoping rules in future).

However, things like default context declaration or condition dispatch
have block scope (it's only natural that they are binded to the block
that generates them).

Unrelated change: context marker should be set for each condition,
re2c must generate it after condition label: this way code that skips
condition dispatch and jums directly to condition label will still
have context marker adjusted properly.

Added configurations for all command-line options.

Separated .dot code generation from common case.

Omit some useless newlines in the generated code.

Lexer: minor code cleanup (check errors before doing anything else).

Lexer: moved 'end of comment' sublexer to a separate function.

Lexer: unified handling of various re2c directives.

Now when lexer encounters the beginning of a new directive, it
dumps all the intermediate code to the output.

Before this commit re2c lexer dumped intermediate code on each
newline that occured in the input.

So this commit affects two aspects:
    - Intermediate code is dumped much less often: it's good for
      performance, but it becomes more probable that the intermediate
      code will occasionally occupy too much buffer space and incur
      buffer resize.
    - Some re2c directives ignored characters right before the
      (on the same line). These unfortunate characters are no longer
      ignored.

Lexer: drop useless rule.

The 'end of comment' rule was used to detect end of re2c directives;
however, now it is handled by a special 'end of comment' lexer block.

Lexer: don't care if end of comment is followed by a newline.

re2c used to swallow newline that immediately followes end of directive:
for most of the directives re2c generates code block that ends with a
newline, so the generated code looks better if the newline is not doubled.

However, this unnecessarily complicates the lexer.

Lexer: suppressed directives in skeleton mode, cleaned up code.

Explicitely handle empty string in lexer.

(rather that hide it inside of a definition)

Added directive '/*!contexts:re2c ... */'.

Directive is a new type of re2c block that consists of zero or more
of the following configurations (example values are the defaults):
    line = "long @@;";
    sep = "";

Renamed configuration: 're2c:ctxprefix' -> 're2c:contexts:prefix'

Added configuration: 're2c:contexts:expr = "@@"' that allows to
override the way context markers are accessed (but nottheir names).

Removed configuration: 're2c:define:YYDISTTYPE' (use the new
directive '/*!contexts:re2c ... */' instead).

Parser grammar cleanup.

 - Rearranged some rules to avoid code duplication.
 - Added production and error message about contexts in named definitions.
 - Removed productions and error messages about missing expression
   (simple 'syntax error' is enough, given that only part of the
   errors was captured by the removed productions).

Optimized pointer arithmetics generated with '-C, --contexts'.

If default input API is used and fixed-length context is based on
the rightmost context (that is, YYCURSOR), then the following expression
(that calculates pointer corresponding to the given context):
    (YYCTXMARKER + ((YYCURSOR - YYCTXMARKER) - yyctx))
can be optimized to:
    (YYCURSOR - yyctx)

Note: unfortunately, as of GCC < 7.0, expressions like:
    (YYCURSOR - 3) - (YYCURSOR - 5)
trigger warning:
    warning: integer overflow in expression [-Woverflow]
See this GCC bug: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61240

Added some configurations related to '-C, --contexts' option.

Configurations:
    "define:YYCTX"      (defaults to 'YYCTX')
    "define:YYDIST"     (defaults to 'YYDIST')
    "define:YYDISTTYPE" (defaults to 'long')
    "ctxprefix"         (defaults to 'yyctx')

Use 'std::valarray' instead of 'std::vector' to avoid copy semantics.

Had to rename 'INFINITY' to 'SCC_INF': inclusion of '<valarray.h>'
pulled '<math.h>' and introduced name collision.

Use 'size_t' instead of 'uint32_t' to avoid 'static_cast'.

Make sure that default rule is handled together with other rules.

Moved nontrivial context handling from parser to NFA construction phase.

Parser should simply construct AST; all the complex reasoning about
contexts (fixed vs variable) should be delayed until NFA is being
constructed. This way AST can be immutable and it's very easy to share
parts of AST between different conditions, etc.

Removed rule ranks and rank counter: rules are now stored in NFA-local
array and addressed by index.

Added partial submatch extraction.

Enabled with '-C, --contexts' option.

Warning '-Wselfoverlapping-contexts'.

Moved loop counters out of skeleton; they belong to algorithm-local stuff.

Pack all stuff relevant to skeleton data generation in a struct.

Use distinct type for path suffixes during skeleton data generation.

Address skeleton nodes by indices rather than by pointers.

This way it is more convenient to add various graph algorithms:
each algorithm can keep its own data in array indexed by skeleton
node numbers (instead of pushing all relevant data inside of the
node).

Reuse the same struct to represent different kinds of paths in skeleton.

[-Wundefined-control-flow] analyses: simplified path structure.

Now paths involved in [-Wundefined-control-flow] analyses have
exactly the same structure as paths involved in skeleton data generation.

Added comments.

Moved comment.

Moved calculation of fallback states to earlier stage of DFA construction.

We will need this later, when adding multiple context markers
(liveness analyses during context marker deduplication).

Eradicated occasional copy-paste.

Used function 'make_rule_copy' introduced by commit
f781c3a3a07cde0243c894da640070d6c62ef4bc.

Moved function definitions out of header.

Skeleton: simplified path structure.

Just store pointers to skeleton nodes (instead of bookkeeping arcs,
contexts and rules in each path). All the necessary information can
be easily retrieved from nodes when path is baing dumped to file.

Three tests in '--skeleton' mode have been broken by this commit.
Actually, these are not breakages: these cases reveal incorrect
re2c-generated code. The change is due to the fact that skeleton
now doesn't simulate contexts that go *after* the matched rule:

    ------o------o------> ... (fallback to rule)
        rule   context

Skeleton: respect fixed-length contexts.

run_tests.sh: fixed cleanup of intermediate files with '--skeleton'.

Broken by commit c56a14582de4fbbed34d231e521ab2e6af5d43c3
"run_tests.sh: don't crash on absolute filepaths in test names."

run_tests.sh: don't crash on absolute filepaths in test names.

This patch fixes bug #137 "run_tests.sh fail when running configure
script with absolute path".

The fix: copy all test files into temporary build directory (which
is addressed by a relative filepath) and keep messing with relative
filepaths.

Code cleanup: moved rule construction to a separate file.

Mark rules as nullable rather than keep a separate collection of nullable rules.

Now regexp AST is immutable.

We don't do any transformations on AST anyway: it is analysed
and converted to NFA. This patch simply fixes the fact that AST
is immutable.

Code cleanup: replaced Regexp inheritance hierarchy with tagged union.

Code cleanup: factored RuleInfo out of RuleOp.

Rule information (line, attached code block, rank, shadowing set, etc.)
is used throughout the program. Before this patch, rule information was
inlined in RuleOp. It was inconvenient because RuleOp belongs to early
stages of compilation (AST, prior to NFA), but it had to live throughout
the whole program.

Simplified tracking of fixed-length trailing contexts.

Static (that is, of fixed length) trailing contexts don't need
recording context position with YYCTXMARKER and restoring it
back on successful match. They can be tracked simply by decreasing
input position by context length.

Fixed an old bug in function calculating regexp length.

The bug: the function treated 'r1 | r2' as 'r1 | r2'
(used 'r1' twice instead of 'r1' and 'r2').

As the function was rarely used the bug went unnoticed for about
two decades.

Simplified [-Wmatch-empty-rule] analyses.

Before this patch [-Wmatch-empty-rule] was based on:
    - DFA structural analyses (skeleton phase)
    - rule reachability analyses (skeleton phase)

Now it is based on:
    - NFA structural analyses (NFA phase)
    - rule reachability analyses (skeleton phase)

It's much easier to find nullable rules in NFA than in DFA.
The problem with DFA is in rules with trailing context, both
dynamic and especially static (as it leaves no trace in DFA
states). re2c currently treats static context as dynamic, but
it will change soon.

On the other side NFA may give some false positives because of
unreachable rules:
    [^] {}
    ""  {}
infinite rules:
    [^]* {}
or self-shadowing rules:
    [^]?
Reachability analyses in skeleton helps to filter out unreachable
and infinite rules, but not self-shadowing ones.

run_tests.sh: avoid another '+=' in bash arrays (compatibility with old bash).

See #135 "In installation "make check" give syntax error".

run_tests.sh: avoid '+=' in bash arrays (compatibility with old bash).

See #135 "In installation "make check" give syntax error".

add basic support for travis-ci.org integration

Signed-off-by: Sergei Trofimovich <siarheit@google.com>

re2c/Makefile.am: use RST2MAN variable instead of hardcoded rst2man.py

Ubuntu installs docutils binaries without .py prefix.

Signed-off-by: Sergei Trofimovich <siarheit@google.com>

Release 0.16.

Merged branch 'devel'.

Updated CHANGELOG (preparing release 0.16).

Makefile.am: fixed path to header.

Removed forgotten 'typename' kewyword in non-template code.

Fixed includes (applied some of 'include-what-you-use' suggestions).

Applied #131: "Use bash-specific '[[' builtin".

Stabilized the list of shadowing rules reported by [-Wunreachable-rules].

Before this commit, the list of rules depended on the order of NFA states
in each DFA state under construction (which is simply a matter of ordering
pointers to heap: the order can be different).

Now all rules for each DFA state are collected and the final choice of
rule is delayed until DFA is constructed, so the order of NFA states
no longer matters.

Merged two small headers into one.

Compact DFA states after minimization.

Replaced class method with function.

Keep data relevant to DFA determinization outsde of DFA states.

Moved YYFILL points calculation to the earlier stage of DFA construction.

No serious changes intended (mostly cleanup and comments).

The underlying algorithm for finding strongly connected components
(SCC) remains the same: it's a slightly modified Tarjan's algorithm.

We now mark non-YYFILL states by setting YYFILL argument to zero,
which is only logical: why would anyone call YYFILL to provide zero
characters. In fact, re2c didn't generate 'YYFILL(0)' call itself,
but some remnants of YYFILL did remain (which caused changes in tests).

Serialize '--skeleton' generated data in little-endian.

This commit fixes bug #132 "test failure on big endian archs with 0.15.3".

Tests failed because re2c with '--skeleton' option used host endianness
when serializing binary data to file. Expected test result was generated
on little-endian arch, while actual test was run on big-endian arch.

Only three tests failed (out of ~40 tests that are always run with
'--skeleton'), because in most cases data unit is 1 byte and endianness
doesn't matter.

The fix: re2c now converts binary data from host-endian to little-endian
before dumping it to file. Skeleton programs convert data back from
little-endian to host-endian when reading it from file (iff data unit
size is greater than 1 byte).

Serialize '--skeleton' generated data in little-endian.

This commit fixes bug #132 "test failure on big endian archs with 0.15.3".

Tests failed because re2c with '--skeleton' option used host endianness
when serializing binary data to file. Expected test result was generated
on little-endian arch, while actual test was run on big-endian arch.

Only three tests failed (out of ~40 tests that are always run with
'--skeleton'), because in most cases data unit is 1 byte and endianness
doesn't matter.

The fix: re2c now converts binary data from host-endian to little-endian
before dumping it to file. Skeleton programs convert data back from
little-endian to host-endian when reading it from file (iff data unit
size is greater than 1 byte).

configure.ac: fixed error message.

Message should report 'rst2man' as well as 'rst2man.py'.

configure.ac: check for 'rst2man' as well as 'rst2man.py'.

Fixes bug #133 "rst2man.py depreciated in RHEL7".

Explicitely handle default state as special case during DFA construction.

Check accumulated parameter before entering recursion.

Renamed files and function.

Moved source subdirectory.

Moved source files to a proper subdirectory.

Removed obsolete code deduplication mechanism.

This mechanism was tricky and fragile; it cost us a most unfortunate
bug in PHP lexer: https://bugs.gentoo.org/show_bug.cgi?id=518904
(and a couple of other bugs).

Now that re2c does DFA minimization this is no longer needed. Hoooray!

The updated test changed because skeleton is constructed prior to
DFA minimization.

Removed obsolete comments.

Added test for bug #128 "very slow DFA construction (resulting in a very large DFA)".

After minimization the resulting DFA is much smaller:
    /*!re2c
        [ac]{0,14} [a] [ac]{0,14} {}
    */

Was:
    $ time re2c slow.re > slow.c && stat -c '%s' slow.c

    real    1m54.837s
    user    1m54.733s
    sys     0m0.120s
    5627102

Now:
    $ time ./re2c slow.re > slow.c && stat -c '%s' slow.c

    real    0m0.732s
    user    0m0.684s
    sys     0m0.048s
    15078

Added DFA minimization and option '--dfa-minimization <table | moore>'.

Test results changed a lot; it is next to impossible to verify them
by hand. I therefore implemented two different minimization algorithms:
    - "table filling" algorithm (simple and inefficient)
    - Moore's algorithm (not so simple and efficient enough)
They produce identical minimized DFA (up to states relabelling), thus
giving some confidence in that the resulting DFA is correct.

I also checked the results with '--skeleton': re2c constructs
skeleton prior to reordering and minimization, therefore
skeleton-generated data is free of (potential) minimization errors.

Split DFA intermediate representation in two parts: DFA and ADFA.

ADFA stands for 'action DFA', that is, DFA with actions.

During DFA construction (aka NFA determinization) it is convenient
to represent DFA states as indexes to array of states.
Later on, while binding actions, it is more convanient to store
states in a linked list.

Merge branch 'master' of git://github.com/jcfp/re2c

*  missed some occurrences...

missed some occurrences...

Merge branch 'master' into devel

Merge branch 'jcfp-master'

typ0 fixes

Keep DFA states in a hash map (to speedup lookup fo an identical state).

This partially fixes bug #128: "very slow DFA construction (resulting
in a very large DFA)". DFA construction is no longer slow, but the
resulting DFA is still too large and needs to be minimized.

DFA construction: epsilon-closure of NFA states: pick only kernel states.

Changed bytecode intermediate representation to a simpler NFA representation.

Base '+' (one or more repetitions) on '*' (zero or more repetitions).

Kleene star '*' (aka iteration, repetition, etc.) is a primitive
operation in regular expressions.

For some reason re2c used '+' as a primitive operation and expressed
'*' in terms of '+'. It is inconvenient, because all algorithms
described in literature are based on '*'.

Because we now express 'a+' as 'a* a', we have to set 'PRIVATE' attribute
on 'a': otherwize 'a' gets shared between the two occurences which causes
complex bugs.

Expressing 'a+' in a more intuitive way as 'a a*' rather than 'a* a'
causes the generated code to duplicate certain states. The generated code
is (supposedly correct), but re2c fails to deduplicate these states.
We therefore prefer 'a* a' expansion, which results in exactly the same
code as before.

No need to preserve special order of states while building DFA (thanks to states reordering).

Dropped the difference between left and right default rule (thanks to states reordering).

Bootstrap lexer changed a lot: this change is caused by commit
a4c192f27ae8806e67a8ff311eeff53d74dacb71: "Reordered states in DFA.".
Changes in parser by this commit triggered lexer regeneration.

Reordered states in DFA.

Fixed bug #127: "code generation error with wide chars and bitmaps (omitted 'goto' statement)".

Minimal test case:
    /*!re2c
        [^a]+ {}
        [a]   {}
    */

Catched with skeleton:
    $ re2c -W -ubi err.re -S -o err.c && gcc err.c -o err && ./err
    error: lex_line4: at position 294 (iteration 98):
            expected: match length 2, rule 0
            actual:   match length 1, rule 1

Simplified handling of character ranges in DFA construction algorithm.

Now disjoint character ranges in bytecode are represented using
range index rather than range lower bound (as it used to be).

Optimized charset representation.

re2c used a complex and slow algorithm to split charset into
disjoint character ranges. This commit replaces old algorithm with
new (much simpler and quicker).

re2c test suite now runs 2x faster due to speedup in Unicode tests.

Release 0.15.3.

Prepare release 0.15.3: updated CHANGELOG.

Added description of '--no-version' option to help and manpage.

Fixed '#include's (appied most of 'include-what-you-use' suggestions).

The worst dependency which 'include-what-you-use' fails to see
(and rightly so) is 'src/parse/lex.re' -> 'src/parse/parser.h'.
This dependency is caused by '#include "y.tab.h"' in 'src/parse/lex.re'.

Another ubiquitos issue is 'src/util/c99_stdint.h' ('include-what-you-use'
suggests to substitute it with '<stdint.h>').

And a couple of other dependencies that 'include-what-you-use' fails to see.