Custom fields in tree, mutable tree

[aachrisg]

I'm trying out lexy for a personal cppfront-type project.

I know the parse tree output is designed to be immutable and allow constexpr...

That said, have you thought about adding a mutable templated "userdata" field? In my usage case for instance, I would like to produce a parse tree for an expression, and then iteratively label each resultant node with a pointer to the typedef for the expression result type, if known.

Have you thought about a mutable tree option allowing node re-arrangement/replacement? For instance, in an optimizing language parser, you might want to do constant folding on the resultant tree, and other such operations.

I'm just getting into it, so I'm not sure how hard it would be to just implement my own tree output. Would one do it just be making the "value" output of rules be tree nodes (perhaps w/ children)?

Thanks for the library!

[foonathan]

You want an AST, not a parse tree for those operations. A parse tree is a lossless representation of the input, but it can have too much detail for further processing. Usually, a compiler will have a pass that converts a parse tree to an AST by throwing away data, e.g. in Rust's compiler: https://rustc-dev-guide.rust-lang.org/lowering.html (although they call the parse tree "AST" and what I call AST "HIR").

As a matter of fact, I am currently working on adding an AST to lexy and support this sort of lowering, as it is quite annoying boilerplate to write by hand.

Alternatively, you can add user data to the parse tree using a hash map using the .address() of a node as key. I don't want to add additional data inline.

I'm just getting into it, so I'm not sure how hard it would be to just implement my own tree output. Would one do it just be making the "value" output of rules be tree nodes (perhaps w/ children)?

It's not quite as simple, as you want to capture all tokens. The way to do it is to react to the parse events using your own handler, look at e.g. trace for an implementation that reacts to all events:

lexy/include/lexy/action/trace.hpp

Lines 305 to 462 in d5041eb

	template <typename OutputIt, typename Input, typename TokenKind = void>
	class _th
	{
	public:
	explicit _th(OutputIt out, const Input& input, visualization_options opts = {}) noexcept
	: _writer(out, opts), _input(&input), _anchor(input)
	{
	LEXY_PRECONDITION(opts.max_tree_depth <= visualization_options::max_tree_depth_limit);
	}
	class event_handler
	{
	using iterator = typename lexy::input_reader<Input>::iterator;
	public:
	constexpr event_handler(production_info info) : _info(info) {}
	void on(_th& handler, parse_events::production_start, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_production_start(loc, _info.name);
	// All events for the production are after the initial event.
	_previous_anchor.emplace(handler._anchor);
	handler._anchor = loc.anchor();
	}
	void on(_th& handler, parse_events::production_finish, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_finish(loc);
	}
	void on(_th& handler, parse_events::production_cancel, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_cancel(loc);
	// We've backtracked, so we need to restore the anchor.
	handler._anchor = *_previous_anchor;
	}
	int on(_th& handler, parse_events::operation_chain_start, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_production_start(loc, "operation chain");
	return 0; // need to return something
	}
	template <typename Operation>
	void on(_th& handler, parse_events::operation_chain_op, Operation, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_operation(loc, lexy::production_name<Operation>());
	}
	void on(_th& handler, parse_events::operation_chain_finish, int, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_finish(loc);
	}
	template <typename TK>
	void on(_th& handler, parse_events::token, TK kind, iterator begin, iterator end)
	{
	auto loc = handler.get_location(begin);
	handler._writer.write_token(loc, token_kind<TokenKind>(kind),
	lexeme_for<Input>(begin, end));
	}
	void on(_th& handler, parse_events::backtracked, iterator begin, iterator end)
	{
	auto loc = handler.get_location(begin);
	handler._writer.write_backtrack(loc, lexeme_for<Input>(begin, end));
	}
	template <typename Error>
	void on(_th& handler, parse_events::error, const Error& error)
	{
	auto loc = handler.get_location(error.position());
	handler._writer.write_error(loc, error);
	}
	void on(_th& handler, parse_events::recovery_start, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_recovery_start(loc);
	}
	void on(_th& handler, parse_events::recovery_finish, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_finish(loc);
	}
	void on(_th& handler, parse_events::recovery_cancel, iterator pos)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_cancel(loc);
	}
	void on(_th& handler, parse_events::debug, iterator pos, const char* str)
	{
	auto loc = handler.get_location(pos);
	handler._writer.write_debug(loc, str);
	}
	private:
	production_info _info;
	// The beginning of the previous production.
	// If the current production gets canceled, it needs to be restored.
	_detail::lazy_init<input_location_anchor<Input>> _previous_anchor;
	};
	template <typename Production, typename State>
	using value_callback = _detail::void_value_callback;
	template <typename>
	constexpr OutputIt get_result(bool) &&
	{
	return LEXY_MOV(_writer).finish();
	}
	private:
	input_location<Input> get_location(typename lexy::input_reader<Input>::iterator pos)
	{
	return get_input_location(*_input, pos, _anchor);
	}
	_detail::trace_writer<OutputIt, TokenKind> _writer;
	const Input* _input;
	input_location_anchor<Input> _anchor;
	};
	template <typename State, typename Input, typename OutputIt, typename TokenKind = void>
	struct trace_action
	{
	OutputIt _out;
	visualization_options _opts;
	State* _state = nullptr;
	using handler = _th<OutputIt, Input>;
	using state = State;
	using input = Input;
	template <typename>
	using result_type = OutputIt;
	constexpr explicit trace_action(OutputIt out, visualization_options opts = {})
	: _out(out), _opts(opts)
	{}
	template <typename U = State>
	constexpr explicit trace_action(U& state, OutputIt out, visualization_options opts = {})
	: _out(out), _opts(opts), _state(&state)
	{}
	template <typename Production>
	constexpr auto operator()(Production, const Input& input) const
	{
	auto reader = input.reader();
	return lexy::do_action<Production, result_type>(handler(_out, input, _opts), _state,
	reader);
	}
	};

But note that this interface is undocumented and subject to change without notice.

[aachrisg]

Thanks.
Yeah, after some thought I came to the conclusion that the easiest way to get my own tree representation was to just use the tree builder and then traverse it to generate my own data structures.