Bison: Avoid default construction of semantic values

Question

I'm using Bison with C++ and the variants option to construct an AST. If I understand it correctly, Bison always default constructs the semantic values (the AST nodes in my case) before I assign something to them with $$ = .... However, I'd like to keep some (actually most) of my AST nodes non-default constructible, because that would leave them in an invalid state. If I allow default construction of every node, I'd have to rely on runtime checks to ensure that every node I'm working with is valid. Is there any way to make Bison not default construct my nodes and only construct them when I do the $$ = ... action?

Edit: @Some programmer dude requested an example, so here it is, but it's quite long, so sorry about that.

Suppose the following AST structure:

namespace node {
    template 
    struct component {
        // Not default constructible.
        component (T &&);
        component (component &&);
        component & operator = (T &&);
        component & operator = (component &&);
        ~component ();
        T & get ();
        T const & get () const;
    private:
        T * ptr;
    };

    template 
    struct optional_component {
        // Default constructible:
        optional_component (): ptr{nullptr} {}
        optional_component (T &&);
        optional_component (component &&);
        optional_component & operator = (T &&);
        optional_component & operator = (component &&);
        ~optional_component ();
        T & get ();
        T const & get () const;
        // Need to check for present value before use:
        bool has_value () const { return ptr; }
    private:
        T * ptr;
    };

    struct C {
        int val;
    };

    struct A {
        // Not default constructible, because component is not.
        component bar;
    };

    struct B {
        // Default constructible, because component is too.
        optional_component c;
    }
}

namespace category {

    struct X {
        // Not default constructible,
        // unless the first type of the variant is default constructible,
        // or I provide the default constructor manually.
        std::variant node;
    };

}

And the following parser definition:

%language "c++"
%define api.value.type variant
%define api.value.automove
%parse-param { category::X & result }

%token A
%token B
%token BB
%token  C
%nterm  node_a
%nterm  node_b
%nterm  node_c
%nterm  start

%%

start:  node_a   { result = {.node = $node_a}; } |
        node_b   { result = {.node = $node_b}; }
node_c: C        { $$ = {.val = $1};           }
node_a: A node_c { $$ = {.c = $node_c};        }
node_b: B node_c { $$ = {.c = $node_c};        } |
        BB       { $$ = {};                    }

The generated parser first tries to default construct the nodes. E.g.:

yylhs.value.emplace();

And only then assigns the value. E.g:

yylhs.value.as() = {.c = YY_MOVE(yystack_[1].value.as())};

What I need is to skip the default constructing emplace call and actually construct the node with the given child nodes directly.

I've found this in the generated header file:

# if 201103L <= YY_CPLUSPLUS
    /// Instantiate a \a T in here from \a t.
    template 
    T& emplace (U&&... u) {
      return *new (yyas_ ()) T (std::forward (u)...);
    }
# else
    /// Instantiate an empty \a T in here.
    template 
    T& emplace () {
        return *new (yyas_ ()) T ();
    }

    /// Instantiate a \a T in here from \a t.
    template 
    T& emplace (const T& t) {
        return *new (yyas_ ()) T (t);
    }
# endif

So it seems that the emplace method is actually meant to be able to construct the final value directly.

user_1566221 · Answer

As I understand it, the intent of the bison implementation in this case is to avoid the possibility of an uninitialised variant value, which would be lead to undefined behaviour because of the nature of a Bison variant. The bison variant does not record the type of the object it has been initialised with, because that case never occurs during a parse. So as soon as the parser knows which type the stack slot will contain (which is to say, when it decides that it will execute the reduction action), it must initialise the stack slot, and it can only use a default constructor because it hasn't yet executed the reduction action.

A Bison variant object is basically a union, not a discriminated union; the variant part refers to the fact that the control flow of the program is sufficient to determine the type of the contained object. So there can be no such thing as an uninitialised variant. Moreover, since the variant has an (implicit) type from the moment of its creation until the moment of its destruction, the type cannot be changed during its lifetime.

So your desired semantics are at odds with this design. That doesn't make your semantics wrong (or, for that matter, bison's), but it does mean that you cannot use a bison variant if you want the possibility of an "uninitialised" variant. On the other hand, I'm not sure how you can accomplish this:

However, I'd like to keep some (actually most) of my AST nodes non-default constructible, because that would leave them in an invalid state. If I allow default construction of every node, I'd have to rely on runtime checks to ensure that every node I'm working with is valid.

The question is, what does it mean for an AST node to be in an invalid state? And how will you know that to be the case without a runtime check? Do you expect it to throw an exception on use or some such? If so, there is definitely a run-time check.

You could implement an invalid state by using a std::variant whose first alternative is a default-constructible InvalidNode type, or some such, although you'll have to take care that it doesn't become an no-op instead of an error when you try to use the variant object. In that case, you could tell Bison to use std::variant as a semantic type, although that won't be quite as convenient as using a Bison variant.

Note: In a comment (which is not at all the best place to clarify a question) you seem to be saying that your desired variants are always pointers, meaning that the "invalid node" type is essentially a nullptr. I'm sure that can be made to work with Bison, but you'll need to do it in a different way than the use of Bison variants. How good a match it is for std::variant is not entirely clear to me either :-)

user_1953032 · Answer

With helpful explanations from @rici and after some deeper examination of the generated C++ file for the parser, I've found a rather "dirty" solution. I don't think it's a good idea to rely on such a solution, but it works and I'd like to share it:

Before executing the actions specified in the parser definition, Bison pushes some default values to its stack by calling:

yylhs.value.emplace< type > ();

...where type is the semantic value type of the corresponding non-terminal in the parser definition. Only after that, it proceeds to execute the appropriate action that might assign a value to this newly pushed item. Bison has no way of knowing whether any value will be assigned, so it has to push at least this default constructed value. However, if you are sure, that you assign a value in every action, you don't really need these default constructions. So my solution is to simply tweak the generated C++ file by modifying these default constructions to:

yylhs.value.emplace< int > ();

I do this by simply sticking a line of sed command in my makefile:

sed -i 's/yylhs.value.emplace< my_ast_namespace::[^ ]* > ();/yylhs.value.emplace< int > (); \/\/ Modified./g' generated_parser.cpp

(Note: The regex relies on the fact that there are always spaces inside the outer <> but no spaces in the contained type, otherwise it would be impossible to do with nested templates.)

Now there is no need for a default constructor for my nodes. The pushed value has a wrong type, but in my case, it's not any worse to have an int value in there than to have the correct node with all of its children as null pointers - both will lead to incorrect behaviour.

I won't accept my answer, since it's really just a "hacky workaround" that might break with different versions of Bison. I also don't want to accept the @rici's answer yet, because it seems that with this experiment I've confirmed, that it is in principle possible to do what I wanted.

Bison: Avoid default construction of semantic values

2 Answers