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.

Prefixed all tokens with 'TOKEN_'.

Inspired by commit commit c172f266b4b611cb69bde3b46e4be350819cde73.

Makefile.am: use 'AM_V_GEN' prefix to report custom rules.

run_tests.sh (with '--skeleton'): clarified message, use generic CC rathen than 'gcc'.

Renamed tests that contained uppercase letters in file extension.

We use file extensions to encode re2c options.
Some (short) options are uppercase letters: e.g. '-D', '-F', '-S'.
There also short options for the same lowercase letters: '-d', '-f', '-s'.
This can cause filename collisions on platforms with case-insensitive
file extensions (e.g. Windows and OS X).

See bud #125: "[OS X] git reports changes not staged for commit
in newly cloned repository".

Fix: use long versions for options that uppercase options.
Disallowed uppercase options in 'run_tests.sh'.

configure.ac: suppress some warnings with '-Weverything'.

'-Wundefined-control-flow': fixed patterns ordering, reduced memory consumption.

The problem with pattern ordering first emerged on FreeBSD-10.2
(I was able to reproduce it with 'CXXFLAGS=-fsanitize=address').
Some tests failed because patterns reported by '-Wundefined-control-flow'
were sorted in different order than expected. This is because
patterns ordering was inconsistent: patterns were compared by length,
(it doesn't work for patterns of equal length). Now first ordering
criterion is length, and second criterion is lexicographical order.

This commit reduces the amount of memory consumed by '-Wundefined-control-flow':
re2c no longer allocates vectors on stack while deep-first-searching skeleton.

This commit also reduces the limit of memory for '-Wundefined-control-flow'
(64Mb edges -> 1Kb edges). Real-world programs rarely need that much.
The limit was so high to acommodate some few artificial tests (with lower
limit these tests cannot find shortest patterns).

This commit also removes the upper bound for the number of faulty patterns
reported by '-Wundefined-control-flow'. This bound was needed by the
artificial tests mentioned above: they produce lots of patterns.
Now these tests are limited with 1Kb of edges anyway.

Note that 1Kb limit is checked after each new pattern is added, so that
at least one pattern will fit in (even if it takes more than 1Kb).

Removed one particularly fat test from test collection.

Substitute template class with non-template, as only one specialization is used.

Skeleton data generation: suffix should be multipath as well as prefix.

Prefix of current path under construction is a multipath, because prefix
arcs have not been covered yet. Suffix can be a simple path (that is, a
multipath of width 1), because all alternative suffix arcs have already
been covered.

prefix       suffix
_________   _________
...      \ /
--------- o
_________/

But nothing prevents us from alternating suffix arcs also, as long as
suffix remains a single multipath:

_________   _________
...      \ / ...
--------- o ---------
_________/ \_________

The resulting path's width is the maximum of prefix ans suffix width
(hence the growth in size of those tests in which suffix is wider
than prefix), but it only makes a small difference. And the generated
paths are more "variable".

Skeleton data generation: cover all edges in 1-byte range (not only range bounds).

If code units occupy 1 byte, then the generated path cover covers
*all* edges in the original DFA. If the size of code unit exceeds 1 byte,
then only some ~0x100 (or less) range values will be chosen
(including range bounds).

Skeleton data generation: dropped exponential algorithm, always use path cover.

Removed obsolete '__STDC_LIMIT_MACROS' and '__STDC_CONSTANT_MACROS' defines.

These defines were necessary to enable numeric limits definitions
(such as 'UINT32_MAX') in our local version of 'stdint.h' (which is
used on platforms that don't have system header 'stdint.h').

As noted by commit b237daed2095c1e138761fb94a01d53ba2c80c95, this
workaround doesn't work on FreeBSD, so re2c now uses 'numeric_limits.h'.

Fixed [-Wconversion] warning.

Warning was introduced in commit b237daed2095c1e138761fb94a01d53ba2c80c95:
compiler fails to recognise (or deliberately choses not to recognize)
'std::numeric_limits<...>::max()' as a special constant.

run_tests.sh: use '--no-version --no-generation-date' instead of sed hack.

These options make re2c omit version and date info and thus produce
stable test results.

Added option '--no-version' that omits version in fingerprint.

Get rid of UINT32_MAX and friends

UINT32_MAX is conditionally defined only
for C compiler on FreeBSD but not for C++,

Stop using __STDC_LIMIT_MACROS workaround
as it does not work on FreeBSD.

Use std::numeric_limits<> from C++98 instead.

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

Fixed crashes of 'ostream& operator<< (ostream& os, const char* s)' on NULL.

Crashes observed on platforms OS X (clang-7.0.0) and FreeBSD-10.2 (clang-3.4).
First reported in bug #122 "clang does not compile re2c 0.15.x".

What caused NULL passed to 'operator <<': re2c always generates content of
header file (regardless of '-t --type-header' option), but the content is
dumped to file (and header filename initialized to non-NULL) only if the
option was enabled.

Fix: always initialize header filename to non-NULL string.

run_tests.sh: use '/usr/bin/env bash' to locate bash.

Makefile.am: use '=' instead of '==' to compare strings.

'==' appears to be a bash feature.