Ruby 4.1.0dev (2026-11-18 revision bcf3b03b44ae598e3adb59d359cf32202091a318)
constant_pool.h
1#ifndef PRISM_INTERNAL_CONSTANT_POOL_H
2#define PRISM_INTERNAL_CONSTANT_POOL_H
3
5
6#include "prism/arena.h"
8
9#include <stdbool.h>
10
11/* A constant in the pool which effectively stores a string. */
13 /* A pointer to the start of the string. */
14 const uint8_t *start;
15
16 /* The length of the string. */
17 size_t length;
18};
19
20/*
21 * The type of bucket in the constant pool hash map. This determines how the
22 * bucket should be freed.
23 */
24typedef unsigned int pm_constant_pool_bucket_type_t;
25
26/* By default, each constant is a slice of the source. */
27static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_DEFAULT = 0;
28
29/* An owned constant is one for which memory has been allocated. */
30static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_OWNED = 1;
31
32/* A constant constant is known at compile time. */
33static const pm_constant_pool_bucket_type_t PM_CONSTANT_POOL_BUCKET_CONSTANT = 2;
34
35/*
36 * A bucket in the hash map. It holds no string, so that it stays eight bytes
37 * wide for every slot of a mostly empty table. A probe compares hashes first,
38 * and reads the string through the constants array only when they match, which
39 * is almost always a real hit.
40 */
41typedef struct {
42 /* The incremental ID used for indexing back into the pool. */
43 unsigned int id: 30;
44
45 /* The type of the bucket, which determines how to free it. */
46 pm_constant_pool_bucket_type_t type: 2;
47
48 /* The hash of the bucket. */
49 uint32_t hash;
51
52/* The overall constant pool, which stores constants found while parsing. */
54 /* The buckets in the hash map. */
56
57 /*
58 * The constants that are stored in the buckets, indexed by id minus one.
59 * The pool grows before it is three quarters full, so this has room for
60 * three quarters as many constants as there are buckets, rounded up.
61 */
62 pm_constant_t *constants;
63
64 /* The number of buckets in the hash map. */
65 uint32_t size;
66
67 /* The number of buckets that have been allocated in the hash map. */
68 uint32_t capacity;
69};
70
71/*
72 * When we allocate constants into the pool, we reserve 0 to mean that the slot
73 * is not yet filled. This constant is reused in other places to indicate the
74 * lack of a constant id.
75 */
76#define PM_CONSTANT_ID_UNSET 0
77
78/* Set the unset constant id at the specified index of a list of constant ids. */
79void pm_constant_id_list_insert(pm_constant_id_list_t *list, uint32_t index, pm_constant_id_t id);
80
81/*
82 * Mix the bits of a constant id so that ids which are close together, as
83 * sequentially assigned ids are, land in unrelated slots of a hash table.
84 */
85static PRISM_INLINE uint32_t
86pm_constant_id_hash(pm_constant_id_t id) {
87 id = ((id >> 16) ^ id) * 0x45d9f3b;
88 id = ((id >> 16) ^ id) * 0x45d9f3b;
89 id = (id >> 16) ^ id;
90 return id;
91}
92
93/*
94 * A set of constant ids, for where the parser only needs to know whether it has
95 * already seen a name, as with the variables a pattern captures or the named
96 * capture groups of a regular expression.
97 */
98typedef struct {
99 /* The number of ids in the set. */
100 size_t size;
101
102 /* The number of slots in `ids`, either zero or a power of two. */
103 size_t capacity;
104
105 /*
106 * An open-addressed table of the ids in the set, where PM_CONSTANT_ID_UNSET
107 * marks an empty slot. It is NULL until the first id is added.
108 */
109 pm_constant_id_t *ids;
111
112/*
113 * Add a constant id, which must not be PM_CONSTANT_ID_UNSET, to the set.
114 * Returns whether the set did not already contain it.
115 */
116bool pm_constant_id_set_insert(pm_arena_t *arena, pm_constant_id_set_t *set, pm_constant_id_t id);
117
118/* Initialize a new constant pool with a given capacity. */
119void pm_constant_pool_init(pm_arena_t *arena, pm_constant_pool_t *pool, uint32_t capacity);
120
121/*
122 * Return the number of bytes that pm_constant_pool_init allocates for the given
123 * capacity.
124 */
125size_t pm_constant_pool_init_size(uint32_t capacity);
126
127/* Return a pointer to the constant indicated by the given constant id. */
128pm_constant_t * pm_constant_pool_id_to_constant(const pm_constant_pool_t *pool, pm_constant_id_t constant_id);
129
130/*
131 * Find a constant in a constant pool. Returns the id of the constant, or 0 if
132 * the constant is not found.
133 */
134pm_constant_id_t pm_constant_pool_find(const pm_constant_pool_t *pool, const uint8_t *start, size_t length);
135
136/*
137 * Insert a constant into a constant pool that is a slice of a source string.
138 * Returns the id of the constant, or 0 if any potential calls to resize fail.
139 */
140pm_constant_id_t pm_constant_pool_insert_shared(pm_arena_t *arena, pm_constant_pool_t *pool, const uint8_t *start, size_t length);
141
142/*
143 * Insert a constant into a constant pool from memory that is now owned by the
144 * constant pool. Returns the id of the constant, or 0 if any potential calls to
145 * resize fail.
146 */
147pm_constant_id_t pm_constant_pool_insert_owned(pm_arena_t *arena, pm_constant_pool_t *pool, uint8_t *start, size_t length);
148
149/*
150 * Insert a constant into a constant pool from memory that is constant. Returns
151 * the id of the constant, or 0 if any potential calls to resize fail.
152 */
153pm_constant_id_t pm_constant_pool_insert_constant(pm_arena_t *arena, pm_constant_pool_t *pool, const uint8_t *start, size_t length);
154
155#endif
A bump allocator for the prism parser.
A data structure that stores a set of strings.
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.