Ruby 4.1.0dev (2026-11-17 revision 373d8c72a360f0d6c3be9cd13d1f0c27360e5d90)
constant_pool.c
1#include "prism/internal/constant_pool.h"
2
5#include "prism/internal/arena.h"
6#include "prism/internal/assert.h"
7
8#include <stdbool.h>
9
13void
14pm_constant_id_list_init(pm_constant_id_list_t *list) {
15 list->ids = NULL;
16 list->size = 0;
17 list->capacity = 0;
18}
19
23void
24pm_constant_id_list_init_capacity(pm_arena_t *arena, pm_constant_id_list_t *list, size_t capacity) {
25 if (capacity) {
26 list->ids = (pm_constant_id_t *) pm_arena_zalloc(arena, capacity * sizeof(pm_constant_id_t), PRISM_ALIGNOF(pm_constant_id_t));
27 } else {
28 list->ids = NULL;
29 }
30
31 list->size = 0;
32 list->capacity = capacity;
33}
34
38void
39pm_constant_id_list_append(pm_arena_t *arena, pm_constant_id_list_t *list, pm_constant_id_t id) {
40 if (list->size >= list->capacity) {
41 size_t new_capacity = list->capacity == 0 ? 8 : list->capacity * 2;
42 pm_constant_id_t *new_ids = (pm_constant_id_t *) pm_arena_alloc(arena, sizeof(pm_constant_id_t) * new_capacity, PRISM_ALIGNOF(pm_constant_id_t));
43
44 if (list->size > 0) {
45 memcpy(new_ids, list->ids, list->size * sizeof(pm_constant_id_t));
46 }
47
48 list->ids = new_ids;
49 list->capacity = new_capacity;
50 }
51
52 list->ids[list->size++] = id;
53}
54
58void
59pm_constant_id_list_insert(pm_constant_id_list_t *list, size_t index, pm_constant_id_t id) {
60 PRISM_ASSERT(index < list->capacity);
61 PRISM_ASSERT(list->ids[index] == PM_CONSTANT_ID_UNSET);
62
63 list->ids[index] = id;
64 list->size++;
65}
66
71static PRISM_INLINE size_t
72pm_constant_id_set_slot(const pm_constant_id_set_t *set, pm_constant_id_t id) {
73 PRISM_ASSERT(set->capacity != 0);
74
75 size_t mask = set->capacity - 1;
76 size_t index = ((size_t) pm_constant_id_hash(id)) & mask;
77
78 while (set->ids[index] != PM_CONSTANT_ID_UNSET && set->ids[index] != id) {
79 index = (index + 1) & mask;
80 }
81
82 return index;
83}
84
88bool
89pm_constant_id_set_insert(pm_arena_t *arena, pm_constant_id_set_t *set, pm_constant_id_t id) {
90 /* PM_CONSTANT_ID_UNSET marks an empty slot, so it cannot also be a member. */
91 PRISM_ASSERT(id != PM_CONSTANT_ID_UNSET);
92
93 /*
94 * Grow at the same load factor the locals table and the constant pool use.
95 * An empty set has no slots at all, so this also builds the first table.
96 */
97 if (set->size >= (set->capacity / 4 * 3)) {
98 size_t capacity = set->capacity == 0 ? 8 : set->capacity * 2;
99 pm_constant_id_set_t grown = {
100 .size = set->size,
101 .capacity = capacity,
102 .ids = (pm_constant_id_t *) pm_arena_zalloc(arena, capacity * sizeof(pm_constant_id_t), PRISM_ALIGNOF(pm_constant_id_t))
103 };
104
105 for (size_t index = 0; index < set->capacity; index++) {
106 pm_constant_id_t moved = set->ids[index];
107 if (moved != PM_CONSTANT_ID_UNSET) grown.ids[pm_constant_id_set_slot(&grown, moved)] = moved;
108 }
109
110 *set = grown;
111 }
112
113 size_t index = pm_constant_id_set_slot(set, id);
114 if (set->ids[index] == id) return false;
115
116 set->ids[index] = id;
117 set->size++;
118 return true;
119}
120
128static PRISM_INLINE uint32_t
129pm_constant_pool_hash(const uint8_t *start, size_t length) {
130 // This constant is borrowed from wyhash. It is a 64-bit odd integer with
131 // roughly equal 0/1 bits, chosen for good avalanche behavior when used in
132 // multiply-xorshift sequences.
133 static const uint64_t secret = 0x517cc1b727220a95ULL;
134 uint64_t hash = (uint64_t) length;
135
136 if (length <= 8) {
137 // Short strings: read first and last 4 bytes (overlapping for len < 8).
138 // This covers the majority of Ruby identifiers with a single multiply.
139 if (length >= 4) {
140 uint32_t a, b;
141 memcpy(&a, start, 4);
142 memcpy(&b, start + length - 4, 4);
143 hash ^= (uint64_t) a | ((uint64_t) b << 32);
144 } else if (length > 0) {
145 hash ^= (uint64_t) start[0] | ((uint64_t) start[length >> 1] << 8) | ((uint64_t) start[length - 1] << 16);
146 }
147 hash *= secret;
148 } else if (length <= 16) {
149 // Medium strings: read first and last 8 bytes (overlapping).
150 // Two multiplies instead of the three the loop-based approach needs.
151 uint64_t word;
152 memcpy(&word, start, 8);
153 hash ^= word;
154 hash *= secret;
155 memcpy(&word, start + length - 8, 8);
156 hash ^= word;
157 hash *= secret;
158 } else {
159 const uint8_t *ptr = start;
160 size_t remaining = length;
161
162 while (remaining >= 8) {
163 uint64_t word;
164 memcpy(&word, ptr, 8);
165 hash ^= word;
166 hash *= secret;
167 ptr += 8;
168 remaining -= 8;
169 }
170
171 if (remaining > 0) {
172 // Read the last 8 bytes (overlapping with already-processed data).
173 uint64_t word;
174 memcpy(&word, start + length - 8, 8);
175 hash ^= word;
176 hash *= secret;
177 }
178 }
179
180 hash ^= hash >> 32;
181 return (uint32_t) hash;
182}
183
187static uint32_t
188next_power_of_two(uint32_t v) {
189 // Avoid underflow in subtraction on next line.
190 if (v == 0) {
191 // 1 is the nearest power of 2 to 0 (2^0)
192 return 1;
193 }
194 v--;
195 v |= v >> 1;
196 v |= v >> 2;
197 v |= v >> 4;
198 v |= v >> 8;
199 v |= v >> 16;
200 v++;
201 return v;
202}
203
207static PRISM_INLINE void
208pm_constant_pool_resize(pm_arena_t *arena, pm_constant_pool_t *pool) {
209 uint32_t next_capacity = pool->capacity * 2;
210 const uint32_t mask = next_capacity - 1;
211
212 pm_constant_pool_bucket_t *next_buckets = (pm_constant_pool_bucket_t *) pm_arena_zalloc(arena, next_capacity * sizeof(pm_constant_pool_bucket_t), PRISM_ALIGNOF(pm_constant_pool_bucket_t));
213 pm_constant_t *next_constants = (pm_constant_t *) pm_arena_alloc(arena, next_capacity * sizeof(pm_constant_t), PRISM_ALIGNOF(pm_constant_t));
214
215 // For each bucket in the current constant pool, find the index in the
216 // next constant pool, and insert it.
217 for (uint32_t index = 0; index < pool->capacity; index++) {
218 pm_constant_pool_bucket_t *bucket = &pool->buckets[index];
219
220 // If an id is set on this constant, then we know we have content here.
221 // In this case we need to insert it into the next constant pool.
222 if (bucket->id != PM_CONSTANT_ID_UNSET) {
223 uint32_t next_index = bucket->hash & mask;
224
225 // This implements linear scanning to find the next available slot
226 // in case this index is already taken. We don't need to bother
227 // comparing the values since we know that the hash is unique.
228 while (next_buckets[next_index].id != PM_CONSTANT_ID_UNSET) {
229 next_index = (next_index + 1) & mask;
230 }
231
232 // Here we copy over the entire bucket, which includes the id so
233 // that they are consistent between resizes.
234 next_buckets[next_index] = *bucket;
235 }
236 }
237
238 // The constants are stable with respect to hash table resizes.
239 memcpy(next_constants, pool->constants, pool->size * sizeof(pm_constant_t));
240
241 pool->constants = next_constants;
242 pool->buckets = next_buckets;
243 pool->capacity = next_capacity;
244}
245
249void
250pm_constant_pool_init(pm_arena_t *arena, pm_constant_pool_t *pool, uint32_t capacity) {
251 capacity = next_power_of_two(capacity);
252
253 pool->buckets = (pm_constant_pool_bucket_t *) pm_arena_zalloc(arena, capacity * sizeof(pm_constant_pool_bucket_t), PRISM_ALIGNOF(pm_constant_pool_bucket_t));
254 pool->constants = (pm_constant_t *) pm_arena_alloc(arena, capacity * sizeof(pm_constant_t), PRISM_ALIGNOF(pm_constant_t));
255 pool->size = 0;
256 pool->capacity = capacity;
257}
258
263pm_constant_pool_id_to_constant(const pm_constant_pool_t *pool, pm_constant_id_t constant_id) {
264 PRISM_ASSERT(constant_id != PM_CONSTANT_ID_UNSET && constant_id <= pool->size);
265 return &pool->constants[constant_id - 1];
266}
267
273pm_constant_pool_find(const pm_constant_pool_t *pool, const uint8_t *start, size_t length) {
274 const uint32_t mask = pool->capacity - 1;
275
276 uint32_t hash = pm_constant_pool_hash(start, length);
277 uint32_t index = hash & mask;
279
280 while (bucket = &pool->buckets[index], bucket->id != PM_CONSTANT_ID_UNSET) {
281 // Compare the stored hash before touching the contents so that probe
282 // collisions are rejected without a memcmp call.
283 if ((bucket->hash == hash) && (bucket->length == length) && memcmp(bucket->start, start, length) == 0) {
284 return bucket->id;
285 }
286
287 index = (index + 1) & mask;
288 }
289
290 return PM_CONSTANT_ID_UNSET;
291}
292
297pm_constant_pool_insert(pm_arena_t *arena, pm_constant_pool_t *pool, const uint8_t *start, size_t length, pm_constant_pool_bucket_type_t type) {
298 if (pool->size >= (pool->capacity / 4 * 3)) {
299 pm_constant_pool_resize(arena, pool);
300 }
301
302 const uint32_t mask = pool->capacity - 1;
303
304 uint32_t hash = pm_constant_pool_hash(start, length);
305 uint32_t index = hash & mask;
307
308 while (bucket = &pool->buckets[index], bucket->id != PM_CONSTANT_ID_UNSET) {
309 // If there is a collision, then we need to check if the content is the
310 // same as the content we are trying to insert. If it is, then we can
311 // return the id of the existing constant. Compare the stored hash
312 // first so that probe collisions are rejected without a memcmp call.
313 if ((bucket->hash == hash) && (bucket->length == length) && memcmp(bucket->start, start, length) == 0) {
314 // Since we have found a match, we need to check if this is
315 // attempting to insert a shared or an owned constant. We want to
316 // prefer shared constants since they don't require allocations.
317 if (type != PM_CONSTANT_POOL_BUCKET_OWNED && bucket->type == PM_CONSTANT_POOL_BUCKET_OWNED) {
318 // If we're attempting to insert a shared constant and the
319 // existing constant is owned, then we can replace it with the
320 // shared constant to prefer non-owned references.
321 bucket->start = start;
322 bucket->type = (unsigned int) (type & 0x3);
323 pool->constants[bucket->id - 1].start = start;
324 }
325
326 return bucket->id;
327 }
328
329 index = (index + 1) & mask;
330 }
331
332 // IDs are allocated starting at 1, since the value 0 denotes a non-existent
333 // constant.
334 uint32_t id = ++pool->size;
335 PRISM_ASSERT(pool->size < ((uint32_t) (1 << 30)));
336
337 *bucket = (pm_constant_pool_bucket_t) {
338 .id = (unsigned int) (id & 0x3fffffff),
339 .type = (unsigned int) (type & 0x3),
340 .hash = hash,
341 .start = start,
342 .length = length
343 };
344
345 pool->constants[id - 1] = (pm_constant_t) {
346 .start = start,
347 .length = length,
348 };
349
350 return id;
351}
352
358pm_constant_pool_insert_shared(pm_arena_t *arena, pm_constant_pool_t *pool, const uint8_t *start, size_t length) {
359 return pm_constant_pool_insert(arena, pool, start, length, PM_CONSTANT_POOL_BUCKET_DEFAULT);
360}
361
368pm_constant_pool_insert_owned(pm_arena_t *arena, pm_constant_pool_t *pool, uint8_t *start, size_t length) {
369 return pm_constant_pool_insert(arena, pool, start, length, PM_CONSTANT_POOL_BUCKET_OWNED);
370}
371
378pm_constant_pool_insert_constant(pm_arena_t *arena, pm_constant_pool_t *pool, const uint8_t *start, size_t length) {
379 return pm_constant_pool_insert(arena, pool, start, length, PM_CONSTANT_POOL_BUCKET_CONSTANT);
380}
381
385const uint8_t *
386pm_constant_start(const pm_constant_t *constant) {
387 return constant->start;
388}
389
393size_t pm_constant_length(const pm_constant_t *constant) {
394 return constant->length;
395}
#define PRISM_ALIGNOF
Get the alignment requirement of a type.
Definition align.h:15
uint32_t pm_constant_id_t
A constant id is a unique identifier for a constant in the constant pool.
#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
C99 shim for <stdbool.h>.
A list of constant IDs.
size_t size
The number of constant ids in the list.
size_t capacity
The number of constant ids that have been allocated in the list.
pm_constant_id_t * ids
The constant ids in the list.