Ulya Trofimovich [Mon, 10 Aug 2015 09:32:31 +0000 (10:32 +0100)]
Explicit cast of pointer difference to uint32_t: it seems to be safe from the code.
In theory, this function returns the number of 'Span's in the newly
constructed 'Span' array, so it must be a non-negative integer number
that fits into 32 bits and the cast is safe.
In practice, 'x0' variable stays unchanged in this function, while
'x' variable's value can only increase: whenever it can be (conditionally)
decremented, it is always unconditionally incremented. So 'x - x0'
must be non-negative.
Ulya Trofimovich [Mon, 10 Aug 2015 09:19:00 +0000 (10:19 +0100)]
Fixes some hidden NULL pointer dereferencing.
'specMap' parameter can sometimes be NULL (when not in '-c' mode).
In code it was dereferenced before the check for '-c', but due to
compiler optimizations this was never revealed.
I found the bug while trying to measure the size of 'specMap'
before the check (caught segfault). Fixed by moving the check prior
to dereferencing.
Warning status can be in fact represented with only 2 bits, but
since it's engaged in arithmetic operations it gets promoted and
special precautions are needed. Much easier to ure 32 bits:
warnings are nowhere near performance/memory bottleneck.
Use size_t to store the length of path in skeleton.
Though this length shouldn't actually excedd 32 bits (othewise
too much data will be generated, and that is checked), it's better
to use size_t and don't care about the order of checks.
A special truncated unsigned 32-bit type for overflow-sensitive calculations.
With --skeleton switch we need to generate lots of data: strings that
correspond to various paths in DFA and match given regular expression.
For small graphs we can afford to generate all paths, for large graphs
we can only generate path cover. Anyway we need to be able to estimate
the amount of data to be generated (measured in skeleton arcs). Since
it can easily exceed 32 bits (and 64 as well), calculations must stop
as soon as certain limit is reached.
Encodings: use 32-bit unsigned arithmetics instead of 8-bit and 16-bit.
8-bit and 16-bit unsigned integers used in arithmetic operations
are promoted to 32 bits before operation and then truncated back.
Theoretically this may change their value.
Fixed bug #115 "flex-style named definitions cause ambiguity in re2c grammar".
This commit removes 10 shift/reduce conflicts in bison grammar for re2c.
These conflicts are caused by allowing flex-style named definitions
name regular-expression
to contain newlines and to be mixed with rules. It's not just some
conflicts in LALR(1) grammar, it is genuine ambiguity as can be observed
from the following example:
/*!re2c
name "a"
"b" "c" {}
*/
which can be parsed in two ways:
definition -> name "a"
rule -> "b" "c" {}
and
definition -> name "a" "b"
rule -> "c" {}
, both ways being perfectly valid.
This commit resolves ambiguity by forbidding newlines in flex-style
named definitions (conforming to flex syntax). Newline in these
definitions is treated in a special way: lexer emits token 'FID_END',
which marks the end of flex-style named definition in parser.
Ulya Trofimovich [Tue, 16 Jun 2015 15:09:32 +0000 (16:09 +0100)]
More tests for "--empty-class" option.
This time I found all tests that are affected by this option
(that is, contain empty ranges) and added explicit option variants
for most of them (excluding 'test/empty_range.*' group, as we already
have 'test/bug61_positive.*' group that checks the same thing).
This option controls re2c actions when it encounters empty character
class (e.g. [], [^\0x00-\xFF] or [\0x00-\xFF]\[\0x00-\xFF]):
match-empty (default) - match on empty input
match-none - fail to match on any input
error - compilation error
This is a final fix for bug #61 "empty character class [] matches empty string".
Ulya Trofimovich [Tue, 16 Jun 2015 11:19:03 +0000 (12:19 +0100)]
Partial fix for bug #61 "empty character class [] matches empty string".
Given the following code:
/*!re2c
[] {}
*/
/*!re2c
[^\x00-\xFF] {}
*/
/*!re2c
[\x00-\xFF]\[\x00-\xFF] {}
*/
re2c versions <=0.13.6 and >=0.13.7 behaved differently.
0.13.6 consistently considered that empty range should match empty string.
Since 0.13.7 empty positive range [] and empty difference (e.g. [a-z][a-z])
still match empty string, but empty negative range (e.g. [^\x00-\xFF])
matches nothing (always fails). The faulty commit is 28ee7c95bca46ad3cdb965741c5c29e21c50df14
"Added UTF-8 encoding support and tests for it."
This commit brings back consistent behaviour of 0.13.6: empty range,
however it was constructed, always matches empty string. Whether this
behaviour is sane or not is another question.
Ulya Trofimovich [Mon, 15 Jun 2015 14:39:29 +0000 (15:39 +0100)]
Construct non-NULL regexps from NULL ranges (for variable-length encodings).
NULL range represents empty range: range union and difference functions
return NULL for empty ranges. Thus NULL can be passed to functions
that construct regexp from range ('MatchOp', 'UTF8Range' and 'UTF16Range').
All these functions must behave return non-NULL for NULL ranges, since
further code relies on this.
Ulya Trofimovich [Mon, 15 Jun 2015 14:09:02 +0000 (15:09 +0100)]
Crash on attempt to create range with lower bound greater or equal to lower bound.
Better have an assert than nothing until we handle such cases properly.
As for now, if the user inputs range like [9-0], it will be tranformed
to [0-9]. Later re2c should at least warn about such cases.
Ulya Trofimovich [Mon, 15 Jun 2015 13:31:26 +0000 (14:31 +0100)]
Now range internals are only visible to union/difference functions.
Ranges must be constructed so that linked ranges don't overlap and
are monotonous. This is always true for one-link ranges created by
range constructor, and we construct larger ranges from them using
union and difference functions (that maintain the invariant).
Inspired by sudden collision with '__COUNTER__' I occasionally got
while guarding 'src/util/counter.h'.
Now all headers use guards of the form '_RE2C_PATH_TO_HEADER_BASENAME_'.
Some compilers (e.g. clang++) would warn about [-Wreserved-id-macro],
but their reasonong about reserved macro names is quite crude and re2c
is not able to confirm their standards anyway (e.g. autoconf-generated
macro name 'SIZEOF___INT64').
As with labels, try to control how rule priorities are created:
make a special counter that creates new priorities and disallow
everyone but this counter do it.
Simplified creation of rule states and backup states.
New simpler implementation uses STL containers instaed of sparse
array. It's less efficient, but the place is not a bottleneck and
simplicity is more important than efficiency.
Bug description: sometimes re2c would generate code that backups
current input position (e.g. 'YYMARKER = YYCURSOR'), but wouldn't
generate code that restores backuped position (e.g. 'YYCURSOR =
YYMARKER').
Analyses: DFA may have overlapping rules (e.g. "a" and "aaa").
In such cases, if the shorter rule matched, lexer must attempt to
match the longer one. If the longer rule also mathed, then lexer
prefers it to the shorter rule. If the longer rule didn't match,
lexer must backtrack input position to the point when the shorter
rule matched. In order to be able to backtrack, re2c must generate
backup code (e.g. 'YYMARKER = YYCURSOR') and restore code (e.g.
'YYCURSOR = YYMARKER').
In some rare cases DFA has overlapping rules, but if the shorter rule
matched, then the longer rule will always match (perhaps on an
arbitrary long input string), e.g.:
/*!re2c
[^]+ "a" { 1st }
"b" { 2nd }
*/
In this cases there's no need to generate backup code for 2nd rule:
lexer will either encounter final "a" and the 1st rule will match
or YYFILL will not return; anyway, restore code will never be run.
re2c used to output backup code but not restore code in such cases.
This is the bug: backup code is useless without restore code and
should be omitted.
In future re2c should warn about such cases (when the shorter of
two overlapping rules is shadowed by the longer one).
The fix: postpone insertion of save actions (those with backup code)
untill it is known if restore code will be generated.
I also removed obsolete global variable 'bUsedYYMarker', which was
always set to 'true' (it should be per-DFA, not per-block configuration
anyway).
We have one 'yyaccept' initialization per re2c block. Each block
consists of one or more DFA (multiple DFA in '-c' mode in case of
multiple conditions). Each DFA may or may not use 'yyaccept'
(that is, save 'yyaccept' in some states and have a dispatch state
based on saved 'yyaccept' value).
Description of the bug: in '-c' mode, sometimes a DFA would have
states that save 'yyaccept', but no dispatch state that uses that
saved values. DFA didn't actually need 'yyaccept' (all the
assignments vanished if other conditions that need 'yyaccept' were
removed).
The essence of the bug: re2c decided whether to output 'yyaccept'
related stuff on a per-block basis: for multiple conditions in the
same block, the same decision was made (if any condition needed
'yyaccept', all of them would to output it).
The fix: 'yyaccept' initialization should be done on a per-block
basis, while assignments to 'yyaccept' should be done on a per-DFA
basis. Also, 'yyaccept' initialization must be delayed, while
assignments to 'yyaccept' must not.
Note: we may consider per-DFA 'yyaccept' initialization (have a
local 'yyaccept' variable per DFA). This wouldn't conflict with '-f'
switch (as it might seem) as long as we name all the variables
'yyaccept' and don't generate any 'yyaccept' initializations with '-f'.
As automake manual (chapter 27.6 "Flag Variables Ordering") states,
CXXFLAGS is a user variable and should be left for users to override
C++ compiler flags. Thus we should leave CXXFLAGS as is and modify
AM_CXXFLAGS insted.
Instead of unconditionally setting CXXFLAGS in Makefile.am,
check the presence of a flag in configure.ac. If the flag is
present (that is, an attempt to compile an empty C++ program with
this flag is successful), then it is added to CXXFLAGS.
Now one can add *any* compiler flag in configure.ac without
worrying about portability.
The only problem with 'make distcheck' was that we needed write
access to top source directory ('make' wanted to overwrite bootstrap
parser if it was built with bison and 'make check' wanted to create
temporary files in 'test/' directory).
This commit fixes it:
- 'make' doesn't try to overwrite bootstrap if it is identical
to the existing one (must always be true for 'make distcheck')
- testing script makes a temporary directory and keeps all
temporary files there. If some tests failed, temporary files
for them are left and test sources and reference results are
copied into temporary directory to make debug more convenient.
This commit makes use of 'make distcheck' in release script.
Fixed build system to support automake's 'subdir-objects' feature.
As I updated automake to version 1.15 it began to produce lots of
warnings about 'subdir-objects' not used when it should have been.
Turns out that 'subdir-objects' will be on by default in 2.0.
So I tried to turn on 'subdir-objects' and builds began to fail:
automake didn't expand '$(sourcedir)' and '$(builddir)' prefixes.
I erroneously prepended these prefixes in commit 38f526d04415adb7b5e6bca228fc26409833f5c3 "Updated build system.",
as commit message says:
...
Makefile.am:
- explicitly prefixed all file names with $(srcdir) or $(builddir)
...
But automake prepends these prefixes already where necessary, except
for custom rules with side effects: if a custom rule touches some
files that are not explicit targets or dependencies of this rule,
then automake won't find these files unless they are in build directory.
We have such side-effectful custom rules:
- parser rule produces multiple files and touches bootstrap files
- scanner rule touches bootstrap file
- doc rules touch bootstrap files
Multiple files is a common problem of make. Bootstrap introduces
circular dependency, since bootstrap files need to be updated after
they've been used. So it's hard to get rid of side effects in these
rules.
This commit enabels 'subdir-objects' feature and removes all prefixes
in variables and adds them in side-effectful custom rules (for files
from source directory, not for files from build directory). It also
makes use of '$@' and '$<' special variables in custom rules (which
makes side effects more explicit).
Still I don't yet fully understand how automake uses things like
'$(sourcedir)' and '$(builddir)' and their relation with 'subdir-objects'
(it's probably related with non-recursive makefiles).
Ulya Trofimovich [Thu, 28 May 2015 11:16:06 +0000 (12:16 +0100)]
Don't output newline instead if label in initial DFA state.
Rationale: the equivalence of initial label to
're2c::label_counter_t::FIRST' is NOT a proper criterion
and pretty-printing shouldn't rely on it. The real criterion
is something like "(first re2c block OR any use block in '-r'
mode) AND first condition in'-c' mode", but it's spurious and
introduces unnecessary complications.
Droping this newline allows us drop equivalence operator for
labels.
Used the following bash script to ensure that all the changes
in tests are caused by missing newline(s):
# missing: only newlines and line directives
if [[ $diff1 -ne $((diff1_line + diff1_newline)) ]]
then
echo "FAIL1: $f1"
exit 1
fi
# added: only line directives
if [[ $diff2 -ne $diff2_line ]]
then
echo "FAIL2: $f1"
exit 1
fi
# the number of missing line directives
# equals to the number of added line directives
if [[ $diff1_line -ne $diff2_line ]]
then
echo "FAIL4: $f1"
exit 1
fi
done
projects / re2c / log