Hello,
the glr2.cc skeleton corrupts memory for any grammar whose semantic
value type is a non-trivial C++ class (e.g. containing std::string).
Seen with bison 3.8.2 on Debian (g++ 14, libstdc++); the offending
code is unchanged in current master (data/skeletons/glr2.cc).
Symptom: as soon as a parse actually splits the GLR stack, the parser
reads, writes, or frees dead memory. With glibc this typically aborts
with "free(): invalid pointer"; AddressSanitizer reports
stack-use-after-return (trace below).
Root cause
----------
glr_stack_item's copy constructor copies the state/option union with
std::memcpy, and its assignment operator swaps the raw bytes:
glr_stack_item (const glr_stack_item& other) YY_NOEXCEPT YY_NOTHROW
: is_state_ (other.is_state_)
{
std::memcpy (raw_, other.raw_, union_size);
}
For self-referential value representations - most notably libstdc++'s
SSO std::string, whose data pointer points into the object itself -
every such copy keeps pointing into the *source* object. Two code
paths then die:
* yynewGLRStackItem does yyitems.push_back (glr_stack_item (...)):
the pushed copy points into the function-argument temporary, which
is destroyed at the end of the statement. The next use of that
item (e.g. the assignment in yynewSemanticOption) touches the dead
stack frame.
* yyexpandGLRStack calls yyitems.reserve (): the vector relocates all
items through the memcpy copy constructor and then destroys the old
elements, so every resolved semantic value in the stack is left
dangling (and its destruction frees storage shared with the copy).
I assume memcpy was chosen because yypred/yyfirstVal hold relative
offsets which must survive block relocation of the stack - the patch
below keeps that property (offsets are copied verbatim) while properly
copy-constructing the semantic value through glr_state's existing copy
logic.
Reproducer
----------
bison -o repro.tab.cpp glr2-value-corruption.y
g++ -std=c++17 -g -O0 -fsanitize=address repro.tab.cpp -o repro
./repro
ASan output (head):
ERROR: AddressSanitizer: stack-use-after-return ...
WRITE of size 10 ...
#3 Mini::Val::operator=(Mini::Val const&)
#4 Mini::parser::basic_symbol<Mini::parser::by_kind>::operator=
#5 Mini::parser::symbol_type::operator=
#6 operator= repro.tab.cpp (semantic_option)
#7 yynewSemanticOption
#8 yyaddDeferredAction
Address ... is located in stack of thread T0 ... in frame
yynewGLRStackItem
glr2-value-corruption.y:
%require "3.8"
%skeleton "glr2.cc"
%glr-parser
%expect 0
%expect-rr 1
%define api.namespace {Mini}
%define api.value.type {Mini::Val}
%code requires {
#include <string>
namespace Mini {
struct Val {
std::string str; // SSO: self-referential while short
Val () : str ("0123456789") {}
};
}
}
%code {
namespace Mini { int yylex (parser::value_type* v); }
static int Result;
}
%token TOK
%%
/* A minimal ambiguity: TOK reduces via either a or b, so the stack
splits on it; %dprec resolves the ambiguity at the end. */
input: a %dprec 1 { Result = 1; }
| b %dprec 2 { Result = 2; }
;
a: TOK ;
b: TOK ;
%%
#include <cstdio>
namespace Mini {
static bool done;
int yylex (parser::value_type* v)
{
v->str = "token";
return done ? 0 : (done = true, parser::token::TOK);
}
void parser::error (const std::string& m)
{
std::fprintf (stderr, "err: %s\n", m.c_str ());
}
}
int main (void)
{
int r = Mini::parser ().parse ();
std::printf ("rc=%d result=%d\n", r, Result);
return r;
}
Fix
---
With the patch below the reproducer runs clean under ASan (also with
-Dparse.assert) and prints the expected "rc=0 result=2". The same fix
applied to the generated parser is exercised by FreeCAD's expression
grammar (class-typed semantic values, %dprec disambiguation); its test
suite passes and valgrind reports no errors there.
The copy constructor is no longer noexcept since copying the semantic
value may throw.
(The analysis and the patch were worked out with the assistance of
Claude.)
--- a/data/skeletons/glr2.cc
+++ b/data/skeletons/glr2.cc
@@ -910,6 +910,28 @@
return *this;
}
+ /** Copy *this into the uninitialized storage DST. The yypred and
+ * yyfirstVal fields are copied verbatim: they are relative offsets,
+ * which must survive block relocation of the state stack. The
+ * semantic value, if resolved, is properly copy-constructed. */
+ void copy_to (void* dst) const
+ {
+ glr_state& s = *new (dst) glr_state;
+ s.yylrState = yylrState;
+ s.yyposn = yyposn;
+ s.yypred = yypred;
+ if (yyresolved)
+ {
+ s.yyresolved = true;
+ new (&s.value ()) value_type (value ());
+ }
+ else
+ {
+ s.yyresolved = false;
+ s.yyfirstVal = yyfirstVal;
+ }
+ }
+
/** Type tag for the semantic value. If true, yyval applies, otherwise
* yyfirstVal applies. */
bool yyresolved;
@@ -1420,20 +1442,26 @@
new (&raw_) semantic_option;
}
- glr_stack_item (const glr_stack_item& other) YY_NOEXCEPT YY_NOTHROW
+ glr_stack_item (const glr_stack_item& other)
: is_state_ (other.is_state_)]b4_parse_assert_if([[
, magic_ (MAGIC)]])[
{]b4_parse_assert_if([[
other.check_ ();]])[
- std::memcpy (raw_, other.raw_, union_size);
+ if (is_state_)
+ other.getState ().copy_to (&raw_);
+ else
+ new (&raw_) semantic_option (other.getOption ());
}
- glr_stack_item& operator= (glr_stack_item other)
+ glr_stack_item& operator= (const glr_stack_item& other)
{]b4_parse_assert_if([[
check_ ();
other.check_ ();]])[
- std::swap (is_state_, other.is_state_);
- std::swap (raw_, other.raw_);
+ if (this != &other)
+ {
+ this->~glr_stack_item ();
+ new (this) glr_stack_item (other);
+ }
return *this;
}
