Returning `error_handler_result::fail` on expectation failure results in false continuation on the surrounding grammar

[Xeverous]

This is the bug I was writing about in other issue. It is very bizarre. The reproduction is somewhat large but I'm happy I managed to even recreate it after hours spent of pulling code out of my project without success.

(details at the bottom)

#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/home/x3/support/ast/variant.hpp>
#include <boost/spirit/home/x3/support/ast/position_tagged.hpp>
#include <boost/spirit/home/x3/support/utility/lambda_visitor.hpp>
#include <boost/fusion/include/adapt_struct.hpp>

#include <iostream>
#include <string>
#include <vector>

namespace x3 = boost::spirit::x3;

namespace ast
{
	struct identifier : x3::position_tagged
	{
		identifier& operator=(std::string str)
		{
			value = std::move(str);
			return *this;
		}

		const std::string& get_value() const { return value; }

		std::string value;
	};

	struct string_literal : std::string, x3::position_tagged
	{
		const std::string& get_value() const { return *this; }
	};

	struct integer_literal : x3::position_tagged
	{
		integer_literal& operator=(int n)
		{
			value = n;
			return *this;
		}

		int get_value() const { return value; }

		int value;
	};

	struct floating_point_literal : x3::position_tagged
	{
		floating_point_literal& operator=(double n)
		{
			value = n;
			return *this;
		}

		double get_value() const { return value; }

		double value;
	};

	struct literal_expression : x3::variant<floating_point_literal, integer_literal, string_literal>, x3::position_tagged
	{
		using base_type::base_type;
		using base_type::operator=;
	};

	struct sequence : std::vector<literal_expression>, x3::position_tagged {};

	struct constant_definition : x3::position_tagged
	{
		identifier name;
		sequence seq;
	};
} // namespace ast

BOOST_FUSION_ADAPT_STRUCT(ast::constant_definition, name, seq)

using iterator_type = const char*;

struct parse_error
{
	iterator_type error_place;
	iterator_type backtracking_place;
	std::string what_was_expected;
};

using error_holder_type = std::vector<parse_error>;
using position_cache_type = x3::position_cache<std::vector<iterator_type>>;

struct error_holder_tag;
struct position_cache_tag;

struct annotate_on_success
{
	// template <typename Iterator, typename Context, typename... Types>
	// void on_success(
	// 	const Iterator& first,
	// 	const Iterator& last,
	// 	x3::variant<Types...>& ast,
	// 	const Context& context)
	// {
	// 	ast.apply_visitor(x3::make_lambda_visitor<void>([&](auto& node)
	// 	{
	// 		this->on_success(first, last, node, context);
	// 	}));
	// }

	// template <typename T, typename Iterator, typename Context>
	// void on_success(
	// 	const Iterator& first,
	// 	const Iterator& last,
	// 	T& ast,
	// 	const Context& context)
	// {
	// 	position_cache_type& positions = x3::get<position_cache_tag>(context).get();
	// 	positions.annotate(ast, first, last);
	// }
};

struct error_on_error
{
	template <typename Iterator, typename Exception, typename Context>
	x3::error_handler_result on_error(
		Iterator& first,
		const Iterator& /* last */,
		const Exception& ex, // x3::expectation_failure<Iterator> or similar type
		const Context& context)
	{
		error_holder_type& error_holder = x3::get<error_holder_tag>(context).get();
		error_holder.push_back(parse_error{ex.where(), first, ex.which()});
		return x3::error_handler_result::fail;
	}
};


//struct identifier_class                      : error_on_error, annotate_on_success {};
//struct integer_literal_class                 : error_on_error, annotate_on_success {};
//struct floating_point_literal_class          : error_on_error, annotate_on_success {};
struct string_literal_class                  : error_on_error, annotate_on_success {};
//struct literal_expression_class              : error_on_error, annotate_on_success {};
//struct sequence_class                        : error_on_error, annotate_on_success {};
//struct constant_definition_class             : error_on_error, annotate_on_success {};

struct identifier_class                      {};
struct integer_literal_class                 {};
struct floating_point_literal_class          {};
//struct string_literal_class                  {};
struct literal_expression_class              {};
struct sequence_class                        {};
struct constant_definition_class             {};

using floating_point_literal_type = x3::rule<floating_point_literal_class, ast::floating_point_literal>;
BOOST_SPIRIT_DECLARE(floating_point_literal_type)

using integer_literal_type = x3::rule<integer_literal_class, ast::integer_literal>;
BOOST_SPIRIT_DECLARE(integer_literal_type)

using string_literal_type = x3::rule<string_literal_class, ast::string_literal>;
BOOST_SPIRIT_DECLARE(string_literal_type)

using literal_expression_type = x3::rule<literal_expression_class, ast::literal_expression>;
BOOST_SPIRIT_DECLARE(literal_expression_type)

using sequence_type = x3::rule<sequence_class, ast::sequence>;
BOOST_SPIRIT_DECLARE(sequence_type)

using identifier_impl_type = x3::rule<struct identifier_impl_class, std::string>;
BOOST_SPIRIT_DECLARE(identifier_impl_type)
using identifier_type = x3::rule<identifier_class, ast::identifier>;
BOOST_SPIRIT_DECLARE(identifier_type)

using constant_definition_type = x3::rule<constant_definition_class, ast::constant_definition>;
BOOST_SPIRIT_DECLARE(constant_definition_type)

const floating_point_literal_type floating_point_literal = "number (fractional)";
const auto floating_point_literal_def = x3::real_parser<double, x3::strict_real_policies<double>>{};
BOOST_SPIRIT_DEFINE(floating_point_literal)

const integer_literal_type integer_literal = "number (integer)";
const auto integer_literal_def = x3::int_;
BOOST_SPIRIT_DEFINE(integer_literal)

const string_literal_type string_literal = "string";
const auto string_literal_def = x3::lexeme['"' > *(x3::char_ - (x3::lit('"') | '\n' | '\r')) > '"'];
BOOST_SPIRIT_DEFINE(string_literal)

const literal_expression_type literal_expression = "literal";
const auto literal_expression_def = floating_point_literal | integer_literal | string_literal;
BOOST_SPIRIT_DEFINE(literal_expression)

const identifier_impl_type identifier_impl = "identifier";
const auto identifier_impl_def = x3::lexeme[(x3::alpha | x3::char_('_')) > *(x3::alnum | x3::char_('_'))];
BOOST_SPIRIT_DEFINE(identifier_impl)

const identifier_type identifier = identifier_impl.name;
const auto identifier_def = identifier_impl;
BOOST_SPIRIT_DEFINE(identifier)

const sequence_type sequence = "list of values";
const auto sequence_def = x3::skip(x3::space - x3::eol)[*literal_expression > (x3::eol | &x3::eoi)];
BOOST_SPIRIT_DEFINE(sequence)

const constant_definition_type constant_definition = "constant definiton";
const auto constant_definition_def = (identifier >> '=') > sequence;
BOOST_SPIRIT_DEFINE(constant_definition)

int main()
{
	std::string input =
		"abc = 123 \"abc\n" // intentionally bad input: missing "
		"xyz = 456 \"xyz\"";

	auto first = input.data();
	const auto last = input.data() + input.size();

	position_cache_type position_cache(first, last);
	error_holder_type error_holder;
	const auto parser = x3::with<position_cache_tag>(std::ref(position_cache))
	[
		x3::with<error_holder_tag>(std::ref(error_holder))[*constant_definition > x3::eoi]
	];

	std::vector<ast::constant_definition> ast;
	if (!x3::phrase_parse(first, last, parser, x3::space, ast)) {
		std::cout << "parse failed\n";
		return 1;
	}

	if (first != last) {
		std::cout << last - first << " characters left\n";
		return 1;
	}

	std::cout << "success:\n";

	for (const auto& cd : ast) {
		std::cout << cd.name.value << " = {\n";

		for (const auto& val : cd.seq) {
			std::cout << "    literal = ";
			val.apply_visitor(x3::make_lambda_visitor<void>([](const auto& val){ std::cout << val.get_value(); }));
			std::cout << "\n";
		}

		std::cout << "}\n";
	}
}

The code implements a simplified assignment/definition syntax from a more complex human-readable file format from my project. The basic idea of the syntax is to allow assigning multiple values to a single identifier, like this (no , and no ; and line breaks matter):

abc = 123 "abc"
xyz = 456 "xyz"

The code above has a typo in the input and I expect it to result in x3::expectation_failure. It throws this error correctly on Boost 1.76 but accepts the input in later versions.

$ git bisect bad
2db3fde0d02b9a48877147c595289934525882a0 is the first bad commit
commit 2db3fde0d02b9a48877147c595289934525882a0
Author: Nikita Kniazev <nok.raven@gmail.com>
Date:   Tue Jun 1 21:56:22 2021 +0300

    X3: Remove forced iterator rollback in rule
    
    Removes inconsistency when a parser part is factorized into a rule.
    
    Fixes regression introduced in #670.

 example/x3/rexpr/rexpr_full/test/parse_rexpr_test.cpp    |  6 ++++--
 example/x3/rexpr/rexpr_full/test/testing.hpp             |  4 ++--
 include/boost/spirit/home/x3/nonterminal/detail/rule.hpp | 10 +++-------
 test/x3/error_handler.cpp                                |  7 +++++--
 4 files changed, 14 insertions(+), 13 deletions(-)

When it doesn't error, it prints the following:

success:
abc = {
    literal = 123
}
xyz = {
    literal = 456
    literal = xyz
}

Somehow it skips over entire "abc without reporting any *_literal object or raising any parse error/exception.

What's even more bizarre, if you (un)comment which rules get error_on_error and annotate_on_success, e.g. by making all tag types empty, then the bug disappears. Somehow adding error_on_error to string_literal_class causes it to accept invalid input, even though the handler returns x3::error_handler_result::fail.

[Xeverous]

Calling @Kojoley because your commit appeared in git bisect, perhaps you will know more.

[saki7]

I ask that we avoid placing blame on Nikita for this implementation, even if the bisect points to his commit. You may not be aware of the history, so let me share some context. In recent years, a few people harshly criticized him for otherwise reasonable changes. That took a serious toll, and he ultimately stepped back from active work. It was one of the saddest chapters in Spirit's history, and I am genuinely heartbroken.

For this issue, I do not believe anyone here intends to repeat that pattern. I am sharing this background so we can keep the discussion constructive. Let’s focus on the technical problem and the path to a fix rather than assigning fault 😃

Regarding the issue itself, I can confirm that this is somewhat unintuitive. However, I'm not sure if there's trivial way to fix. We can alter the iterator handling, but doing so might break someone else's code. I think the problem is that I'm not sure what the correct (or well-defined) behavior should be.

[saki7]

By the way, I think you can return error_handler_result::rethrow; as a workaround, as you're engaging expectation failure anyway.

[saki7]

If you want me to consider this issue as the exception for feature-freeze, I need at least below information to proceed:

• A minimal reproducible unit test that illustrates the expected design
• A minimal reproducible unit test that illustrates the future incompatibility that will be occurring after the expected fix is deployed
• A technical description that clearly explains why the specific change included in the commit 2db3fde resulted in such regression

[Xeverous]

I ask that we avoid placing blame on Nikita for this implementation, even if the bisect points to his commit.

I am not aware of Spirit's history but I did not intent to place blame on anyone here. No sane person commits bugs on purpose. I just pinged Nikita because as the author of the change, he might be aware of something we don't know and the additional context can put some light into the issue - he was doing some significant changes to the library. I'm already grateful you and others are still willing to look into this given recent departure to X4.

It seems to be a somewhat complex problem because Nikita's commit states it fixes a regression and now this commit turned out to create another regression. Perhaps there is a bigger issue (a design issue) that can not be solved by small commits. Maybe Nikita knows something whether "bigger design flaw" actually exists.

I think the problem is that I'm not sure what the correct (or well-defined) behavior should be.

Yes and I think this might be an even bigger issue than this bug. Spirit X3 documentation taught me how to write grammars but not enough in "how to use the library effectively". I still do more or less blind assumptions about particular behaviors.

You can even see that this very example has 2-layer identifier because for unknown reason, using it directly results in compilation errors related to attributes (std::string has very complex synthesis logic and it may/may not always be compatible with some char_-based grammars). There is also a chance it's completely irrelevant now and is just a remnant of a bug I reported much earlier that has been fixed long ago (maybe even by Nikita).

A minimal reproducible unit test that illustrates the expected design

Sure, I will try to minimize the example further. Perhaps string_literal alone could be enough to test the bug.

A minimal reproducible unit test that illustrates the future incompatibility that will be occurring after the expected fix is deployed.

Not sure what you meant here. The code is already incompatible across Boost versions - it works in 1.76 but not in 1.77. In my opinion it should error on the missing " but we obviously can't just blindly revert Nikita's commit.

A technical description that clearly explains why the specific change included in the commit 2db3fde resulted in such regression

Right now I have no idea. And if I am supposed to write this explanation, I would very appreciate someone explaining to me how the implementation works. Spirit X3 documentation explains a lot but it treats the library like a black box - if something goes wrong or contrary to user's expectations, I have no idea where and why.

[Kojoley]

It's been quite a while and I don't remember much, it's most likely the case #719 was supposed to fix. I remember I almost finished the patch but haven't updated the PR. I can try to find and upload my latest version of that PR, but I'm not going to rebase and resolve merge conflicts that emerged from the code churn that has happened since then, sorry.

[Kojoley]

Here is your example reduced, rolling back an iterator in the error handler workarounds the issue:

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>

namespace x3 = boost::spirit::x3;


struct error_on_error
{
	template <typename Iterator, typename Exception, typename Context>
	x3::error_handler_result on_error(
		Iterator& first,
		const Iterator& last,
		const Exception& ex, // x3::expectation_failure<Iterator> or similar type
		const Context& context)
	{
        //first = last; // <-- uncomment to workaround the issue
		return x3::error_handler_result::fail;
	}
};


struct string_literal_class : error_on_error {};

using string_literal_type = x3::rule<string_literal_class>;
BOOST_SPIRIT_DECLARE(string_literal_type)

const string_literal_type string_literal = "string";
const auto string_literal_def = x3::lexeme['"' > *~x3::char_("\"\n\r") > '"'];
BOOST_SPIRIT_DEFINE(string_literal)


int main()
{
	std::string input =
		"\"123\n" // intentionally bad input: missing "
    ;

	auto first = input.data();
	const auto last = input.data() + input.size();

	const auto parser = *string_literal > x3::eol;
	if (!x3::phrase_parse(first, last, parser, x3::space - x3::eol)) {
		std::cout << "parse failed\n";
		return 1;
	}

	if (first != last) {
		std::cout << last - first << " characters left\n";
		return 1;
	}

	std::cout << "success\n";
}

[saki7]

Thanks for the code. I know it is merely a workaround, but I have a serious concern on modifying the iterator references from within the error handler.

Recently I've made some design decision on this area:

boostorg/spirit_x4@47945d1
Historically, Spirit has passed mutable lvalue references of the
internal iterators to the on_success/on_error handlers. This
behavior was semantically a mistake, because:
(1) on_success/on_error mechanism was designed to be
grammar-agnostic, and
(2) it does not make sense to modify the grammar-specific
iterator on the grammar-agnostic callback.

Furthermore, any modification to X3's internal iterator variables
may invoke undefined behavior, since we had never provided any
kind of guarantee on how those variables are processed in X3's
implementation details.

This was merged on X4 but abandoned on X3. However, the rationale still applies to X3 for some good reason.

While the manual rollback first = last; might work for certain applications, the problem is that we provide no guarantee of how the modified iterators are interpreted on the caller's part (i.e., Spirit's implementation details). And there's a risk for exposing such flexibility to the (innocent) users.

At the least, if we are going to fix the root problem, we need to clarify the "correct" semantics as I mentioned in #833 (comment).

A minimal reproducible unit test that illustrates the future incompatibility that will be occurring after the expected fix is deployed.

Not sure what you meant here. The code is already incompatible across Boost versions - it works in 1.76 but not in 1.77. In my opinion it should error on the missing " but we obviously can't just blindly revert Nikita's commit.

I meant that, if we're going to change the behavior then we are going to have three states:

1. Behavior of 1.76 and before
2. Behavior from 1.77 until now
3. Behavior after the potential fix is deployed

I assume that 1 and 3 may or may not be the same. If there exists some legitimate code that works on 2 but fails after 3, we need a unit test that asserts parse failure on such scenario.

Yes and I think this might be an even bigger issue than this bug.

I agree, and that's exactly the problem. If it turns out that we need to change the iterator rollback semantics in general, that would be a huge semantic change on the entire X3 codebase.

[Xeverous]

Thanks @Kojoley for a quick response and for smaller reproduction code.

My fear of bigger design issue was true. Personally I find modifying iterators in error handlers a very risky idea - even if implementation would support it, some iterators can be very complex (someone could use Spirit to parse network stream bytes/packets) and giving library user a capability to modify them results in very error-prone code. I think it was a good decision to disallow modifying iterators in X4.

At the least, if we are going to fix the root problem, we need to clarify the "correct" semantics as I mentioned in #833 (comment).

I was actually the person that reported missing error handling article in Spirit documentation long time ago because I found this area to be very undocumented. Since then the documentation contains a large example but I still feel uninformed how to use them effectively. Very little was explained what to do with all parameters in the handler.

I don't know what current semantics are implemented but this is my opinion (as a user of the library):

• if an error handler returns x3::error_handler_result::fail, the library should rollback the iterator
• if X3 wants to allow users modifying iterators, it should define precise semantics and interaction with library's implementation
• the library should not require any iterator modifications in error handler by default

A side question, do you @saki7 know why Spirit uses exceptions for reporting errors? I'm not a type of person that bans general use of exceptions in C++ but I still find their use in this case surprising (bad input is not enough in my opinion to throw). Is there any particular benefit of using exceptions in Spirit instead of ordinary function returns? Is X4 planned to be same in this area?

[Xeverous]

I assume that 1 and 3 may or may not be the same. If there exists some legitimate code that works on 2 but fails after 3, we need a unit test that asserts parse failure on such scenario.

I can't prove it but I think there is no legitimate code that works on 2. If some code would broke on 3, it would probably be broken on 1 aswell.

I find this whole issue to be a bug for this reason: if a parse fails (and there is no alternative), it should fail top-level parse (by throwing or returning an iterator that != last). There should be no situation where invalid input is skipped over and ignored. If a library user wants to skip over some invalid part and ignore it, the user should be required to modify the iterator in the handler.

[saki7]

A side question, do you @saki7 know why Spirit uses exceptions for reporting errors? I'm not a type of person that bans general use of exceptions in C++ but I still find their use in this case surprising (bad input is not enough in my opinion to throw). Is there any particular benefit of using exceptions in Spirit instead of ordinary function returns? Is X4 planned to be same in this area?

Try this: https://www.boost.org/doc/libs/1_89_0/libs/spirit/doc/x3/html/spirit_x3/tutorials/non_throwing_expectations.html

It is a relatively new feature implemented in August 2024.

You will have 90x faster runtime performance with the non-throwing expectation. This is implemented in both X3 and X4. I should also note that X4 even defaults to the non-throwing version.

Disclosure: I'm the person who implemented the feature, and it was my primary contribution before I became the maintainer.