Ruby 4.1.0dev (2026-11-17 revision 373d8c72a360f0d6c3be9cd13d1f0c27360e5d90)
node.h
1#ifndef PRISM_INTERNAL_NODE_H
2#define PRISM_INTERNAL_NODE_H
3
4#include "prism/node.h"
5
8
9#include "prism/arena.h"
10#include "prism/internal/assert.h"
11
12#include <stddef.h>
13#include <stdint.h>
14
15/* The offset of the start of the given location. */
16#define PM_LOCATION_START(location_) ((location_)->start)
17
18/* The offset just past the end of the given location. */
19#define PM_LOCATION_END(location_) ((location_)->start + (location_)->length)
20
21/* Return the span covering two initialized locations. Read both endpoints
22 * before changing either field, so moving the start preserves the old end.
23 * An unset location must be initialized separately from the first child. */
25pm_location_join(pm_location_t left, pm_location_t right) {
26 uint32_t start = left.start < right.start ? left.start : right.start;
27 uint32_t left_end = PM_LOCATION_END(&left);
28 uint32_t right_end = PM_LOCATION_END(&right);
29 uint32_t end = left_end > right_end ? left_end : right_end;
30 pm_location_t location = { .start = start, .length = end - start };
31 return location;
32}
33
34/*
35 * A growable list of nodes for bookkeeping that never becomes part of the tree,
36 * such as the block exits and implicit parameters that are tracked while
37 * parsing. These lists are read, truncated, and edited in the middle while
38 * they are still being built, so unlike node lists they keep a capacity and
39 * grow by doubling.
40 */
41typedef struct {
42 /* The number of nodes in the list. */
43 uint32_t size;
44
45 /* The number of nodes that fit in the list's array. */
46 uint32_t capacity;
47
48 /* The nodes in the list. */
49 pm_node_t **nodes;
51
52/*
53 * Slow path for pm_scratch_node_list_append: grow the list and append the
54 * node. Do not call directly — use pm_scratch_node_list_append instead.
55 */
56void pm_scratch_node_list_append_slow(pm_arena_t *arena, pm_scratch_node_list_t *list, pm_node_t *node);
57
58/*
59 * Append a node onto the end of a scratch list, handling the common case inline
60 * and growing the list through pm_scratch_node_list_append_slow.
61 */
62static PRISM_FORCE_INLINE void
63pm_scratch_node_list_append(pm_arena_t *arena, pm_scratch_node_list_t *list, pm_node_t *node) {
64 if (list->size < list->capacity) {
65 list->nodes[list->size++] = node;
66 } else {
67 pm_scratch_node_list_append_slow(arena, list, node);
68 }
69}
70
71/* Append every node of the other scratch list onto the end of the list. */
72void pm_scratch_node_list_concat(pm_arena_t *arena, pm_scratch_node_list_t *list, const pm_scratch_node_list_t *other);
73
74/*
75 * A fixed-size piece of a node list that is still being built. It is exactly
76 * eight pointers wide, so its size is a power of two. The type itself only
77 * requires pointer alignment; pm_node_chunks_carve explicitly allocates each
78 * batch aligned to the chunk size. Each chunk in the batch has that alignment
79 * because the stride is also the chunk size. The link comes first, so a cursor
80 * just past the last slot has zero low bits, the same as NULL. One mask test
81 * then tells an append that the list needs a new chunk, whether the list is
82 * empty or its last chunk is full.
83 */
84typedef struct pm_node_chunk {
85 /* The previous chunk of the same list, or the next chunk on the freelist. */
86 struct pm_node_chunk *prev;
87
88 /* The nodes held by this chunk, in order. */
89 pm_node_t *slots[7];
90} pm_node_chunk_t;
91
92/* The size of a chunk and the alignment requested when allocating its batch. */
93#define PM_NODE_CHUNK_SIZE sizeof(pm_node_chunk_t)
94
95/* The low bits of an address that give its offset within a chunk. */
96#define PM_NODE_CHUNK_MASK ((uintptr_t) (PM_NODE_CHUNK_SIZE - 1))
97
98/* The number of nodes that fit in a chunk. */
99#define PM_NODE_CHUNK_SLOTS (sizeof(((pm_node_chunk_t *) 0)->slots) / sizeof(pm_node_t *))
100
101/* The chunk that contains the given address. */
102#define PM_NODE_CHUNK_OF(pointer_) ((pm_node_chunk_t *) ((uintptr_t) (pointer_) & ~PM_NODE_CHUNK_MASK))
103
104/* The number of chunks carved out of the arena at once. */
105#define PM_NODE_CHUNK_BATCH 32
106
107/*
108 * The source of chunks for open node lists. Chunks are reused through the
109 * freelist, and new ones come from a batch that has been carved out of the
110 * arena but not yet handed out. They are never freed individually; they are
111 * all released together when the arena is cleaned up.
112 */
113typedef struct {
114 /* Chunks returned by finalized lists, linked through prev. */
115 pm_node_chunk_t *free;
116
117 /* The next chunk in the current batch that has not been handed out. */
118 pm_node_chunk_t *next;
119
120 /* One past the last chunk in the current batch. */
121 pm_node_chunk_t *end;
122
123 /* The arena that batches are carved from. */
124 pm_arena_t *arena;
126
127/*
128 * Slow path for pm_node_list_open_append: link a new chunk onto the end of the
129 * list and append the node to it. Do not call directly — use
130 * pm_node_list_open_append instead.
131 */
132void pm_node_list_open_append_slow(pm_node_chunks_t *chunks, pm_node_list_t *list, pm_node_t *node);
133
134/*
135 * Append a node onto the end of an open list. While a list is open, its nodes
136 * field is a cursor to the next free slot of its last chunk, or NULL when the
137 * list is empty. A zeroed list is an empty open list.
138 */
139static PRISM_INLINE void
140pm_node_list_open_append(pm_node_chunks_t *chunks, pm_node_list_t *list, pm_node_t *node) {
141 if (((uintptr_t) list->nodes & PM_NODE_CHUNK_MASK) != 0) {
142 *list->nodes++ = node;
143 list->size++;
144 } else {
145 pm_node_list_open_append_slow(chunks, list, node);
146 }
147}
148
149/*
150 * The last node in an open list, which must not be empty. The cursor is always
151 * just past it, in the same chunk.
152 */
153static PRISM_INLINE pm_node_t *
154pm_node_list_open_last(const pm_node_list_t *list) {
155 return list->nodes[-1];
156}
157
158/*
159 * Copy an open list into an array of exactly its size allocated from the given
160 * arena, and return its chunks to the freelist. Afterward the list holds that
161 * array, and it must not be appended to through pm_node_list_open_append or
162 * finalized again.
163 */
164void pm_node_list_finalize(pm_node_chunks_t *chunks, pm_arena_t *arena, pm_node_list_t *list);
165
166/*
167 * A finalized list holding just the given node, in an array allocated from the
168 * given arena without going through chunks.
169 */
170pm_node_list_t pm_node_list_single(pm_arena_t *arena, pm_node_t *node);
171
172/*
173 * Prepend a node onto the beginning of a finalized list, copying it into a new
174 * array in the given arena of exactly the new size.
175 */
176void pm_node_list_prepend_finalized(pm_arena_t *arena, pm_node_list_t *list, pm_node_t *node);
177
178/*
179 * A finalized list of the size nodes starting at the given index of another
180 * finalized list. It shares that list's array instead of copying it.
181 */
182static PRISM_INLINE pm_node_list_t
183pm_node_list_slice(const pm_node_list_t *list, uint32_t start, uint32_t size) {
184 PRISM_ASSERT(start + size <= list->size);
185 return (pm_node_list_t) { .size = size, .nodes = size == 0 ? NULL : list->nodes + start };
186}
187
188#endif
A bump allocator for the prism parser.
#define PRISM_FORCE_INLINE
Force a function to be inlined at every call site.
#define PRISM_INLINE
Old Visual Studio versions do not support the inline keyword, so we need to define it to be __inline.
Definition inline.h:12
Functions related to nodes in the AST.
This struct represents a slice in the source code, defined by an offset and a length.
Definition ast.h:579
uint32_t start
The offset of the location from the start of the source.
Definition ast.h:581
uint32_t size
The number of nodes in the list.
Definition ast.h:598
struct pm_node ** nodes
The nodes in the list.
Definition ast.h:601