Go to the documentation of this file.
4 #ifndef LEXY_PARSE_TREE_HPP_INCLUDED
5 #define LEXY_PARSE_TREE_HPP_INCLUDED
17 template <
typename Reader>
19 template <
typename Reader>
21 template <
typename Reader>
24 template <
typename Reader>
35 unsigned type() const noexcept
61 return (
_value & 0b10) >> 1;
80 auto result =
reinterpret_cast<std::uintptr_t
>(ptr);
83 result |= (role & 0b1) << 1;
84 result |= (
type & 0b1);
95 template <
typename Reader>
100 = _detail::is_random_access_iterator<typename Reader::iterator>;
103 = std::conditional_t<_optimize_end, std::uint_least32_t, typename Reader::iterator>;
110 typename Reader::iterator
end) noexcept
116 typename Reader::iterator
end() const noexcept
143 template <
typename Reader>
144 struct pt_node_production : pt_node<Reader>
148 const char*
const*
id;
163 auto memory =
static_cast<void*
>(
this + 1);
187 template <
typename MemoryResource>
192 static constexpr std::size_t
block_size = 4096 -
sizeof(
void*);
214 unsigned char*
end() noexcept
222 explicit constexpr
pt_buffer(MemoryResource* resource) noexcept
230 other._head = other._cur_block =
nullptr;
231 other._cur_pos =
nullptr;
237 while (cur !=
nullptr)
276 template <
typename T,
typename... Args>
279 static_assert(std::is_trivially_copyable_v<T>);
280 static_assert(
alignof(T) ==
alignof(
void*));
281 constexpr
auto size =
sizeof(T);
287 return ::new (
static_cast<void*
>(memory)) T(
LEXY_FWD(args)...);
297 auto pos =
static_cast<unsigned char*
>(marker);
330 template <
typename Reader,
typename TokenKind =
void,
typename MemoryResource =
void>
345 return _root ==
nullptr;
348 std::size_t
size() const noexcept
376 class traverse_range;
404 template <
typename Input,
typename TokenKind =
void,
typename MemoryResource =
void>
407 template <
typename Reader,
typename TokenKind,
typename MemoryResource>
434 explicit marker(
void* unwind_pos, std::size_t cur_depth,
436 : unwind_pos(unwind_pos), prod(prod), child_count(0), first_child(nullptr),
437 last_child(nullptr), cur_depth(cur_depth), local_max_depth(cur_depth)
442 first_child =
nullptr;
443 last_child =
nullptr;
449 if (first_child ==
nullptr)
452 first_child = last_child =
child;
470 if (first_child ==
nullptr)
481 child_count += length;
487 if (child_count == 0)
490 if (first_child == parent + 1)
499 auto memory =
static_cast<void*
>(parent + 1);
516 if (cur_depth == local_max_depth && child_count > 0)
520 if (max_depth < local_max_depth)
521 max_depth = local_max_depth;
531 _result._buffer.reset();
536 = _result._buffer.template allocate<_detail::pt_node_production<Reader>>(production);
541 _cur =
marker(_result._buffer.top(), 0, _result._root);
548 _cur.insert_children_into(_cur.prod);
549 _cur.update_size_depth(_result._size, _result._depth);
568 = _result._buffer.template allocate<_detail::pt_node_production<Reader>>(production);
580 if (m.prod == _cur.prod)
584 _cur.update_size_depth(_result._size, m.local_max_depth);
585 _cur.insert_children_into(_cur.prod);
595 if (_cur.prod == m.prod)
599 _result._buffer.unwind(_cur.unwind_pos);
607 auto unwind_pos = _result._buffer.top();
608 if (_cur.prod && _cur.child_count == 0)
615 _result._buffer.template allocate<_detail::pt_node<Reader>*>(
nullptr);
620 _cur =
marker(unwind_pos, old.cur_depth);
637 = _result._buffer.template allocate<_detail::pt_node_production<Reader>>(production);
638 _result._buffer.template allocate<_detail::pt_node<Reader>*>(
nullptr);
642 auto new_container =
marker(_cur.unwind_pos, _cur.cur_depth);
643 new_container.insert(
node);
646 _cur.insert_children_into(
node);
649 new_container.local_max_depth = [&] {
650 if (_cur.cur_depth == _cur.local_max_depth && _cur.child_count > 0)
652 return _cur.local_max_depth + 1 + 1;
654 return _cur.local_max_depth + 1;
656 _result._size += _cur.child_count;
659 _cur = new_container;
667 m.insert_list(_cur.child_count, _cur.first_child, _cur.last_child);
671 std::size_t
size = 0;
672 _cur.update_size_depth(
size, m.local_max_depth);
683 _result._buffer.unwind(_cur.unwind_pos);
690 typename Reader::iterator
end)
702 _cur.last_child->as_token()->update_end(
end);
709 = _result._buffer.template allocate<_detail::pt_node_token<Reader>>(kind,
begin,
720 template <
typename Reader,
typename TokenKind,
typename MemoryResource>
726 return _ptr->as_token() !=
nullptr;
730 return _ptr->as_production() !=
nullptr;
736 return _ptr->next_node() ==
nullptr;
740 return is_production() && _ptr->as_production()->token_production;
743 const char*
name() const noexcept
745 if (
auto prod = _ptr->as_production())
747 else if (
auto token = _ptr->as_token())
759 return lhs.
_ptr->as_token()->kind == rhs.
_ptr->as_token()->kind;
761 return lhs.
_ptr->as_production()->id == rhs.
_ptr->as_production()->id;
765 return !(lhs == rhs);
798 return !(nk == info);
802 return !(nk == info);
813 template <
typename Reader,
typename TokenKind,
typename MemoryResource>
829 if (kind().is_root())
836 cur = cur->next_node();
837 return node(cur->next_node());
855 _cur = _cur->next_node();
860 return _cur == rhs._cur;
876 std::size_t
size() const noexcept
878 if (
auto prod = _node->as_production())
879 return prod->child_count;
886 if (
auto prod = _node->as_production(); prod && prod->first_child())
887 return iterator(prod->first_child());
931 _cur = _cur->next_node()->as_production()->first_child();
934 _cur = _cur->next_node();
939 return _cur == rhs._cur;
988 if (
auto token = _ptr->as_token())
998 auto token = _ptr->as_token();
1005 return lhs._ptr == rhs._ptr;
1009 return lhs._ptr != rhs._ptr;
1030 template <
typename Reader,
typename TokenKind,
typename MemoryResource>
1056 auto child = _cur->as_production()->first_child();
1060 if (
child->as_token())
1080 else if (_cur->next_node()->as_production())
1087 _cur = _cur->next_node();
1093 return _ev == rhs._ev && _cur == rhs._cur;
1105 return _begin == _end;
1122 if (
n.kind().is_token())
1124 _begin._cur =
n._ptr;
1131 _begin._cur =
n._ptr;
1146 #endif // LEXY_PARSE_TREE_HPP_INCLUDED
constexpr auto size(const C &c) -> decltype(c.size())
traverse_range traverse(const node &n) const noexcept
auto siblings() const noexcept
bool is_root() const noexcept
_detail::pt_node< Reader > * _ptr
static constexpr auto _optimize_end
iterator(_detail::pt_node< Reader > *ptr) noexcept
bool is_token() const noexcept
bool empty() const noexcept
friend bool operator==(production_info info, node_kind nk)
node deref() const noexcept
std::conditional_t< std::is_void_v< MemoryResource >, _memory_resource_ptr_empty< default_memory_resource >, std::conditional_t< std::is_empty_v< MemoryResource >, _memory_resource_ptr_empty< MemoryResource >, _memory_resource_ptr< MemoryResource > >> memory_resource_ptr
bool equal(iterator rhs) const noexcept
lexy::lexeme< Reader > _remaining_input
pt_node< Reader > * next_node() const noexcept
bool is_production() const noexcept
constexpr MemoryResource * get_memory_resource()
auto as_production() noexcept
_detail::pt_node< Reader > * _cur
traverse_range traverse() const noexcept
auto token() const noexcept
static constexpr auto role_parent
constexpr bool ignore_if_empty() const noexcept
constexpr parse_tree(MemoryResource *resource)
_detail::pt_node< Reader > * first_child
void set_container_production(production_info production)
@ exit
We're visiting a production node after all its children.
_detail::pt_node_production< Reader > * prod
pt_buffer(pt_buffer &&other) noexcept
static block * allocate(resource_ptr resource)
unsigned char memory[block_size]
friend bool operator==(node_kind nk, token_kind< TokenKind > tk)
A parsed token, i.e. its kind and its lexeme.
unsigned char * end() noexcept
void increment() noexcept
children_range(_detail::pt_node< Reader > *node)
iterator(_detail::pt_node< Reader > *ptr) noexcept
friend bool operator==(token_kind< TokenKind > tk, node_kind nk)
auto parent() const noexcept
builder(production_info production)
static constexpr auto type_token
constexpr Iterator next(Iterator iter)
void insert_children_into(_detail::pt_node_production< Reader > *parent)
friend bool operator!=(node_kind lhs, node_kind rhs)
builder(parse_tree &&tree, production_info production)
friend bool operator!=(token_kind< TokenKind > tk, node_kind nk)
#define LEXY_PRECONDITION(Expr)
constexpr bool is_production
void reserve(std::size_t size)
constexpr auto end(const C &c) -> decltype(c.end())
void finish_production(marker &&m)
iterator begin() const noexcept
node(_detail::pt_node< Reader > *ptr) noexcept
void update_end(typename Reader::iterator end) noexcept
bool is_token_production() const noexcept
bool is_last_child() const noexcept
iterator end() const noexcept
void set_parent(pt_node_production< Reader > *parent) noexcept
_detail::pt_node< Reader > * last_child
constexpr token_kind< TokenKind > kind() const noexcept
static constexpr auto role_sibling
node_kind(_detail::pt_node< Reader > *ptr)
friend bool operator!=(node_kind nk, token_kind< TokenKind > tk)
iterator begin() const noexcept
_detail::pt_node_production< Reader > * _root
void finish_container(marker &&m)
_detail::pt_node< Reader > * _cur
std::conditional_t< _optimize_end, std::uint_least32_t, typename Reader::iterator > _end_t
bool empty() const noexcept
pt_node_token(std::uint_least16_t kind, typename Reader::iterator begin, typename Reader::iterator end) noexcept
What sort of token it is.
auto start_production(production_info production)
std::size_t first_child_adjacent
constexpr void swap(T &lhs, T &rhs)
friend bool operator!=(node lhs, node rhs) noexcept
static std::uintptr_t _make_packed_ptr(pt_node< Reader > *ptr, unsigned type, unsigned role)
_detail::pt_node< Reader > * _ptr
friend bool operator!=(node_kind nk, production_info info)
auto child(const lexy::parse_tree< Reader, TokenKind, MemoryResource > &tree, typename lexy::parse_tree< Reader, TokenKind, MemoryResource >::node node, Predicate predicate) -> std::optional< typename lexy::parse_tree< Reader, TokenKind, MemoryResource >::node >
Returns the first child that matches predicate, if there is any.
static block * deallocate(resource_ptr resource, block *ptr)
pt_buffer & operator=(pt_buffer &&other) noexcept
static constexpr token_kind< TokenKind > from_raw(std::uint_least16_t kind) noexcept
parse_tree && finish(lexy::lexeme< Reader > remaining_input={}) &&
auto lexeme() const noexcept
@ leaf
We're visiting a token.
LEXY_EMPTY_MEMBER resource_ptr _resource
void cancel_production(marker &&m)
iterator end() const noexcept
_detail::pt_node< Reader > * _node
static constexpr auto type_production
std::size_t remaining_capacity() const noexcept
bool equal(iterator rhs) const noexcept
constexpr auto n() noexcept
_detail::pt_node< Reader > * _node
constexpr pt_buffer(MemoryResource *resource) noexcept
std::size_t size() const noexcept
constexpr auto begin(const C &c) -> decltype(c.begin())
void insert(_detail::pt_node< Reader > *child)
lexy::lexeme< Reader > remaining_input() const noexcept
auto kind() const noexcept
const char * name() const noexcept
static constexpr std::size_t child_count_bits
_detail::memory_resource_ptr< MemoryResource > resource_ptr
friend bool operator!=(production_info info, node_kind nk)
static constexpr std::size_t block_size
void cancel_container(marker &&m)
void * address() const noexcept
iterator end() const noexcept
bool empty() const noexcept
std::size_t local_max_depth
void set_sibling(pt_node< Reader > *sibling) noexcept
_value_type deref() const noexcept
unsigned type() const noexcept
_detail::pt_buffer< MemoryResource > _buffer
void unwind(void *marker) noexcept
void token(token_kind< TokenKind > _kind, typename Reader::iterator begin, typename Reader::iterator end)
bool empty() const noexcept
void update_size_depth(std::size_t &size, std::size_t &max_depth)
Reader::iterator end() const noexcept
marker(void *unwind_pos, std::size_t cur_depth, _detail::pt_node_production< Reader > *prod=nullptr)
pt_node_production(production_info info) noexcept
#define LEXY_EMPTY_MEMBER
void insert_list(std::size_t length, _detail::pt_node< Reader > *first, _detail::pt_node< Reader > *last)
void increment() noexcept
friend bool operator==(node lhs, node rhs) noexcept
std::size_t size() const noexcept
iterator begin() const noexcept
std::size_t token_production
auto children() const noexcept
pt_node< Reader > * first_child()
sibling_range(_detail::pt_node< Reader > *node) noexcept
@ enter
We're visiting a production node before all its children.
node deref() const noexcept
T * allocate(Args &&... args)
bool equal(iterator rhs) const noexcept
#define LEXY_ASSERT(Expr, Msg)
friend bool operator==(node_kind lhs, node_kind rhs)
void increment() noexcept
node root() const noexcept
std::size_t depth() const noexcept
unsigned next_role() const noexcept
static constexpr std::uint_least16_t to_raw(token_kind< TokenKind > kind) noexcept
friend bool operator==(node_kind nk, production_info info)