Path length were initialized with 0 instead 'DIST_ERROR', which caused
incorrect calculation of maximal path length. This in turn caused errors
in estimating the number of byted necessary to hold keys during data
generation in skeleton. The resulting keys were one-byte while maximal
path length was more than one byte, which (fortunately!) caused runtime
errors in skeleton programs.
Example of program that caused skeleton error:
/*!re2c
(@t [\x00] [^]{5,6})* {}
*/
The error was hidden for so long because in practice inputs that need
more than one-byte keys are rare, and fuzzer sets 'ulimit -t 10' when
running re2c, so most of such programs were simply aborted. Those that
were not aborted still had a chance of estimating key size correctly.
Makefile.am: use portable POSIX primitive to get directory name.
Use '$(@D)' instead of '$(dir $@)', as the latter requires secondary
expansion feature specific to GNU make; it causes build failures on
bmake.
'$(@D)', on the other hand, is a POSIX make feature documented e.g. in
http://pubs.opengroup.org/onlinepubs/9699919799/utilities/make.html
(section "Internal Macros").
Makefile.am: fixed other custom rules to avoid writing into unexistent directory.
The fixed rules do not presently trigger any build errors: target directory
is created by configure as it need to put autogenerated files doc/manpage.rst
and doc/help.rst in it.
However, this behaviour is occasional: if one removes the .in files, build
failure would be unmasked. So it makes sense to ensure that target directory
exists.
Ross Burton [Mon, 31 Jul 2017 14:43:41 +0000 (15:43 +0100)]
Makefile.am: create target directory before writing into it
In some situations src/parse/ may not exist before a file is copied into the
directory. Ensure that this doesn't happen by creating the directory first.
Don't assert that comparator arguments are non-equal.
Comparator is used in 'std::sort'.
All items in closure have unnique TNFA states, therefore we assumed
that the compared items must always be different. However, 'std::sort'
does not have this requirement and some implementations of it compare
the element with itself.
The removed assert caused crashes with old version of GCC (4.2).
Thanks to Sergei Trofimovich for debugging the issue.
Ross Burton [Mon, 31 Jul 2017 14:43:41 +0000 (15:43 +0100)]
Makefile.am: create target directory before writing into it
In some situations src/parse/ may not exist before a file is copied into the
directory. Ensure that this doesn't happen by creating the directory first.
With CXXFLAGS='-fsanitize=undefined' GCC complains about unaligned access:
if custom allocator is used to allocate structs or other alignment-sensitive
things, then it must take care of the alignment (for example, add padding
to all unaligned blocks of memory which it allocates).
Recognize newlines in character strings and classes.
As for now, newline inside of a character string or class is an error:
re2c should emit clear error message. Different styles of newlines
should be recognized ("\n", "\r\n").
This commit fixes bug #162 reported by pauloscustodio:
Reading files with "rb" causes issues in Windows
Fixed line endings in output files on Windows (#162, #163).
This fix consists of two issues, both reported and fixed by pauloscustodio.
1. #162 "Open text files with "wb" causes issues on Windows"
Text files need to be opened for writing with "w", so that stdio does
the right thing in respect to the correct line endings for the current OS.
("\r\n" in Windows, "\n" in Linux).
2. #163 "Reading files with "rb" causes issues in Windows"
re2c reads input files in binary mode and writes the generated output in
text mode. This caused CR LF conversion to CR CR LF on Windows: first CR
comes from reading input in binary mode, second CR is added when writing
output in text mode. This only happened to those parts of input which are
not transformed by re2c: we used to copy-paste verbatim, now we patch line
endings. Now we convert all line endings to LF before writing the generated
code to file.
Ulya Trofimovich [Sat, 25 Jun 2016 15:22:08 +0000 (16:22 +0100)]
Fixed #147 "Please add symbol name to "can't find symbol" error message".
As suggested by sirzooro:
Please add symbol name to "can't find symbol" error message,
it would allow to quickly spot what is wrong. Now we have to
position cursor at given row and column to find that name.
Also tweaked error reporitng function to append "..." at the end
of the message if it didn't fit into buffer.
Ulya Trofimovich [Fri, 24 Jun 2016 21:46:16 +0000 (22:46 +0100)]
Fixed bug #145 "Values for enum YYCONDTYPE are not generated
when default rules with conditions are used".
Default rule is handled in a special (delayed) way;
re2c uses different code for default rule than for normal rules.
This special code simply forgot to add condition name to the list
of conditions.
run_tests.sh: fix permissions after copying source files to build directory.
`make distcheck` protects source files from writing.
Test script run_tests.sh copies source files into build directory,
but the copied files inherit permissions, so `make distcheck` fails.
run_tests.sh: patch line endings in the generated file.
Line endings in the generated code depend on the target platform: e.g.,
"\r\n" on Windows vs. "\n" on Linux. However, reference test results are
(currently) generated on Linux and therefore contain "\n" line endings.
So we have to patch line endings in the generated code in order to pass
the tests on Windows.
Testing script did patch line endings in stdout and stderr, but forgot
to patch them in the generated file (it was broken since we started to
use '-o' option for testing). This commit fixes testing script.
It also deletes a couple of tests in which source code contains "\r\n"
instead of "\n". These tests are duplicates of other tests (they were
added by commit bd2875441cae4ab3934bfafcd34728021295b842 supposedly to
test that re2c preserves line endings in source code). They are broken
by current commit and fixing them is probably not worth of the effort.
Thanks to Abs62, who noted that under Windows (in MSYS) tests fail
because '2>"$outc.stderr"' dumps CRLF to file instead of LF
and proposed a fix:
sed -i 's/\r//g' "$outc.stderr"
Explicitly pass line/column info in all error messages.
Updated tests. Some error messages are more precise now, e.g. ill-formed
character classes and escape sequences: column points to the beginning
of the faulty lexeme rather than to the middle of it where the error
occured. Other error messages are less precise (lack column info), but
the column reported before was too inexact and didn't make much sense.
POSIX disambiguation: use the same comparison algorithm for orbit and non-orbit tags.
Previously we needed a different algorithm for non-orbit tags, because
disambiguation was based on both start and end tags. Non-orbit start tags
cannot be compared incrementally, like orbit tags, becuse default value
may be discovered on a later step than non-default value. Non-orbit end
tags do not have this problem: since negative tags are inserted at the end
of alternatives, default value is always discovered on the same step as
non-default value (provided that all higher-priority tags agree and
comparison reaches this tag at all).
Now that start tags are ignored, we can use incremental comparison for both
orbit and non-orbit subhistories, which simplifies the code.
Nicer output with '--dump-dfa-raw' and '--posix-captures'.
Don't add closure items to "shadowed" set if there is an identical
"unshadowed" item: otherwise Goldberg-Radzik algorithm generates too much
"shadowed" items and the output becomes too noisy.
Use different closure algorithms for leftmost greedy and POSIX policies.
With leftmost greedy policy we can use simple depth-first search.
With POSIX policy we need Goldberg-Radzik algorithm, which is more complex
(and the necessity to accommodate both policies complicates it even more).
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.
Ulya Trofimovich [Tue, 27 Jun 2017 13:05:26 +0000 (14:05 +0100)]
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.
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.
Ulya Trofimovich [Sun, 21 May 2017 09:07:58 +0000 (10:07 +0100)]
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).
Ulya Trofimovich [Fri, 19 May 2017 21:11:24 +0000 (22:11 +0100)]
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.
Ulya Trofimovich [Fri, 19 May 2017 07:47:36 +0000 (08:47 +0100)]
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.
Ulya Trofimovich [Tue, 16 May 2017 21:11:55 +0000 (22:11 +0100)]
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.
Ulya Trofimovich [Tue, 16 May 2017 17:07:00 +0000 (18:07 +0100)]
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).
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.
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;'.
run_tests.sh: fix permissions after copying source files to build directory.
`make distcheck` protects source files from writing.
Test script run_tests.sh copies source files into build directory,
but the copied files inherit permissions, so `make distcheck` fails.
projects / re2c / log