Ruby 4.1.0dev (2026-11-18 revision bcf3b03b44ae598e3adb59d359cf32202091a318)
static_literals.c
1#include "prism/internal/static_literals.h"
2
5
6#include "prism/internal/allocator.h"
7#include "prism/internal/assert.h"
8#include "prism/internal/buffer.h"
9#include "prism/internal/integer.h"
10#include "prism/internal/isinf.h"
11#include "prism/internal/oom.h"
12#include "prism/internal/parser.h"
13#include "prism/internal/stringy.h"
14#include "prism/internal/xxh3.h"
15
16#include <inttypes.h>
17#include <math.h>
18#include <stdlib.h>
19#include <string.h>
20
28static PRISM_INLINE uint64_t
29key_hash(uint64_t type, uint64_t a, uint64_t b) {
30 const uint64_t key[3] = { type, a, b };
31 return pm_xxh3((const uint8_t *) key, sizeof(key));
32}
33
39static uint64_t
40integer_hash(const pm_integer_t *integer) {
41 uint64_t magnitude = (integer->length > 2)
42 ? pm_xxh3((const uint8_t *) integer->words.values, sizeof(uint32_t) * integer->length)
43 : pm_integer_uint64_value(integer);
44 return key_hash(PM_INTEGER_NODE, integer->negative, magnitude);
45}
46
52static uint64_t
53node_hash(const pm_parser_t *parser, const pm_node_t *node) {
54 switch (PM_NODE_TYPE(node)) {
55 case PM_INTEGER_NODE:
56 return integer_hash(&((const pm_integer_node_t *) node)->value);
57 case PM_SOURCE_LINE_NODE: {
58 int64_t line = (int64_t) pm_line_offset_list_line_column(&parser->line_offsets, node->location.start, parser->start_line).line;
59 return key_hash(PM_INTEGER_NODE, line < 0, (uint64_t) (line < 0 ? -line : line));
60 }
61 case PM_FLOAT_NODE: {
62 const pm_float_node_t *cast = (const pm_float_node_t *) node;
63 double value = cast->value;
64 if (value == 0.0) value = 0.0; /* Normalize -0.0 to 0.0. */
65
66 uint64_t bits;
67 memcpy(&bits, &value, sizeof(bits));
68 return key_hash(PM_FLOAT_NODE, bits, 0);
69 }
70 case PM_RATIONAL_NODE: {
71 const pm_rational_node_t *cast = (const pm_rational_node_t *) node;
72 return key_hash(PM_RATIONAL_NODE, integer_hash(&cast->numerator), integer_hash(&cast->denominator));
73 }
74 case PM_IMAGINARY_NODE: {
75 const pm_imaginary_node_t *cast = (const pm_imaginary_node_t *) node;
76 return key_hash(PM_IMAGINARY_NODE, node_hash(parser, cast->numeric), 0);
77 }
78 case PM_STRING_NODE: {
79 const pm_string_node_t *cast = (const pm_string_node_t *) node;
80
81 pm_node_flags_t mask = PM_STRING_FLAGS_FORCED_BINARY_ENCODING;
82 if (parser->encoding != PM_ENCODING_UTF_8_ENTRY) mask |= PM_STRING_FLAGS_FORCED_UTF8_ENCODING;
83
84 return key_hash(PM_STRING_NODE, pm_xxh3(pm_string_source(&cast->unescaped), pm_string_length(&cast->unescaped)), node->flags & mask);
85 }
86 case PM_SOURCE_FILE_NODE: {
87 const pm_source_file_node_t *cast = (const pm_source_file_node_t *) node;
88 return key_hash(PM_STRING_NODE, pm_xxh3(pm_string_source(&cast->filepath), pm_string_length(&cast->filepath)), 0);
89 }
90 case PM_REGULAR_EXPRESSION_NODE: {
91 const pm_regular_expression_node_t *cast = (const pm_regular_expression_node_t *) node;
92 return key_hash(PM_REGULAR_EXPRESSION_NODE, pm_xxh3(pm_string_source(&cast->unescaped), pm_string_length(&cast->unescaped)), node->flags & (pm_node_flags_t) ~PM_REGULAR_EXPRESSION_FLAGS_ONCE);
93 }
94 case PM_SYMBOL_NODE: {
95 const pm_symbol_node_t *cast = (const pm_symbol_node_t *) node;
96
97 pm_node_flags_t mask = PM_SYMBOL_FLAGS_FORCED_BINARY_ENCODING | PM_SYMBOL_FLAGS_FORCED_US_ASCII_ENCODING;
98 if (parser->encoding != PM_ENCODING_UTF_8_ENTRY) mask |= PM_SYMBOL_FLAGS_FORCED_UTF8_ENCODING;
99
100 return key_hash(PM_SYMBOL_NODE, pm_xxh3(pm_string_source(&cast->unescaped), pm_string_length(&cast->unescaped)), node->flags & mask);
101 }
102 case PM_FALSE_NODE:
103 case PM_NIL_NODE:
104 case PM_SOURCE_ENCODING_NODE:
105 case PM_TRUE_NODE:
106 return key_hash(PM_NODE_TYPE(node), 0, 0);
107 default:
108 PRISM_ASSERT(false && "unreachable");
109 return 0;
110 }
111}
112
116#define COMPARE(left_, right_) (((left_) < (right_)) ? -1 : ((left_) > (right_)) ? 1 : 0)
117
121static int64_t
122int64_value(const pm_parser_t *parser, const pm_node_t *node) {
123 switch (PM_NODE_TYPE(node)) {
124 case PM_INTEGER_NODE: {
125 const pm_integer_t *integer = &((const pm_integer_node_t *) node)->value;
126 if (integer->length > 1) return integer->negative ? INT64_MIN : INT64_MAX;
127
128 int64_t value = (int64_t) pm_integer_uint64_value(integer);
129 return integer->negative ? -value : value;
130 }
131 case PM_SOURCE_LINE_NODE:
132 return (int64_t) pm_line_offset_list_line_column(&parser->line_offsets, node->location.start, parser->start_line).line;
133 default:
134 PRISM_ASSERT(false && "unreachable");
135 return 0;
136 }
137}
138
143static int
144compare_integer_nodes(const pm_parser_t *parser, const pm_node_t *left, const pm_node_t *right) {
145 if (PM_NODE_TYPE_P(left, PM_SOURCE_LINE_NODE) || PM_NODE_TYPE_P(right, PM_SOURCE_LINE_NODE)) {
146 return COMPARE(int64_value(parser, left), int64_value(parser, right));
147 }
148
149 const pm_integer_t *left_integer = &((const pm_integer_node_t *) left)->value;
150 const pm_integer_t *right_integer = &((const pm_integer_node_t *) right)->value;
151 return pm_integer_compare(left_integer, right_integer);
152}
153
157static int
158compare_float_nodes(PRISM_UNUSED const pm_parser_t *parser, const pm_node_t *left, const pm_node_t *right) {
159 return COMPARE(((const pm_float_node_t *) left)->value, ((const pm_float_node_t *) right)->value);
160}
161
165static const pm_string_t *
166string_value(const pm_node_t *node) {
167 switch (PM_NODE_TYPE(node)) {
168 case PM_STRING_NODE:
169 return &((const pm_string_node_t *) node)->unescaped;
170 case PM_SOURCE_FILE_NODE:
171 return &((const pm_source_file_node_t *) node)->filepath;
172 case PM_SYMBOL_NODE:
173 return &((const pm_symbol_node_t *) node)->unescaped;
174 default:
175 PRISM_ASSERT(false && "unreachable");
176 return NULL;
177 }
178}
179
192static int
193compare_string_nodes(const pm_node_t *left, const pm_node_t *right, pm_node_flags_t mask) {
194 const pm_string_t *left_string = string_value(left);
195 const pm_string_t *right_string = string_value(right);
196
197 int result = pm_string_compare(left_string, right_string);
198 if (result != 0) return result;
199
200 /*
201 * Equal bytes are not enough. In a binary source file the two bytes written
202 * as `"\xC3\xA9"` stay BINARY while a `"\u00E9"` escape is forced to UTF-8,
203 * so those are distinct keys even though the bytes match.
204 */
205 return COMPARE(left->flags & mask, right->flags & mask);
206}
207
213static int
214compare_regular_expression_nodes(PRISM_UNUSED const pm_parser_t *parser, const pm_node_t *left, const pm_node_t *right) {
215 const pm_regular_expression_node_t *left_regexp = (const pm_regular_expression_node_t *) left;
216 const pm_regular_expression_node_t *right_regexp = (const pm_regular_expression_node_t *) right;
217
218 int result = pm_string_compare(&left_regexp->unescaped, &right_regexp->unescaped);
219 if (result != 0) return result;
220
221 pm_node_flags_t mask = (pm_node_flags_t) ~PM_REGULAR_EXPRESSION_FLAGS_ONCE;
222 return COMPARE(left->flags & mask, right->flags & mask);
223}
224
230static enum pm_node_type
231static_literal_type(const pm_node_t *node) {
232 switch (PM_NODE_TYPE(node)) {
233 case PM_SOURCE_LINE_NODE:
234 return PM_INTEGER_NODE;
235 case PM_SOURCE_FILE_NODE:
236 return PM_STRING_NODE;
237 default:
238 return PM_NODE_TYPE(node);
239 }
240}
241
246static int
247compare_nodes(const pm_parser_t *parser, const pm_node_t *left, const pm_node_t *right) {
248 enum pm_node_type left_type = static_literal_type(left);
249 enum pm_node_type right_type = static_literal_type(right);
250 if (left_type != right_type) return COMPARE(left_type, right_type);
251
252 switch (left_type) {
253 case PM_INTEGER_NODE:
254 return compare_integer_nodes(parser, left, right);
255 case PM_FLOAT_NODE:
256 return compare_float_nodes(parser, left, right);
257 case PM_IMAGINARY_NODE:
258 return compare_nodes(parser, ((const pm_imaginary_node_t *) left)->numeric, ((const pm_imaginary_node_t *) right)->numeric);
259 case PM_RATIONAL_NODE: {
260 const pm_rational_node_t *left_rational = (const pm_rational_node_t *) left;
261 const pm_rational_node_t *right_rational = (const pm_rational_node_t *) right;
262
263 int result = pm_integer_compare(&left_rational->denominator, &right_rational->denominator);
264 if (result != 0) return result;
265
266 return pm_integer_compare(&left_rational->numerator, &right_rational->numerator);
267 }
268 case PM_STRING_NODE: {
269 pm_node_flags_t mask = PM_STRING_FLAGS_FORCED_BINARY_ENCODING;
270 if (parser->encoding != PM_ENCODING_UTF_8_ENTRY) mask |= PM_STRING_FLAGS_FORCED_UTF8_ENCODING;
271 return compare_string_nodes(left, right, mask);
272 }
273 case PM_SYMBOL_NODE: {
274 pm_node_flags_t mask = PM_SYMBOL_FLAGS_FORCED_BINARY_ENCODING | PM_SYMBOL_FLAGS_FORCED_US_ASCII_ENCODING;
275 if (parser->encoding != PM_ENCODING_UTF_8_ENTRY) mask |= PM_SYMBOL_FLAGS_FORCED_UTF8_ENCODING;
276 return compare_string_nodes(left, right, mask);
277 }
278 case PM_REGULAR_EXPRESSION_NODE:
279 return compare_regular_expression_nodes(parser, left, right);
280 case PM_FALSE_NODE:
281 case PM_NIL_NODE:
282 case PM_SOURCE_ENCODING_NODE:
283 case PM_TRUE_NODE:
284 return 0;
285 default:
286 PRISM_ASSERT(false && "unreachable");
287 return 0;
288 }
289}
290
291#undef COMPARE
292
297static void
298pm_static_literals_place(pm_static_literals_entry_t *entries, uint32_t mask, pm_static_literals_entry_t entry) {
299 uint32_t index = (uint32_t) (entry.hash & mask);
300 while (entries[index].node != NULL) {
301 index = (index + 1) & mask;
302 }
303 entries[index] = entry;
304}
305
311static void
312pm_static_literals_resize(const pm_parser_t *parser, pm_static_literals_t *literals, uint32_t capacity) {
314 if (entries == NULL) PRISM_OOM();
315
316 /* It turns out to be more efficient to mask the hash value than to use the
317 * modulo operator. Because our capacities are always powers of two, we can
318 * use a bitwise AND to get the same result as the modulo operator. */
319 uint32_t mask = capacity - 1;
320
321 if (literals->capacity == 0) {
322 for (uint32_t index = 0; index < literals->size; index++) {
323 pm_node_t *node = literals->nodes[index];
324 pm_static_literals_place(entries, mask, (pm_static_literals_entry_t) { .node = node, .hash = node_hash(parser, node) });
325 }
326 } else {
327 for (uint32_t index = 0; index < literals->capacity; index++) {
328 if (literals->entries[index].node != NULL) {
329 pm_static_literals_place(entries, mask, literals->entries[index]);
330 }
331 }
332
333 xfree_sized(literals->entries, literals->capacity * sizeof(pm_static_literals_entry_t));
334 }
335
336 literals->entries = entries;
337 literals->capacity = capacity;
338}
339
346pm_node_t *
347pm_static_literals_add(const pm_parser_t *parser, pm_static_literals_t *literals, pm_node_t *node, bool replace) {
348 switch (PM_NODE_TYPE(node)) {
349 case PM_FALSE_NODE:
350 case PM_FLOAT_NODE:
351 case PM_IMAGINARY_NODE:
352 case PM_INTEGER_NODE:
353 case PM_NIL_NODE:
354 case PM_RATIONAL_NODE:
355 case PM_REGULAR_EXPRESSION_NODE:
356 case PM_SOURCE_ENCODING_NODE:
357 case PM_SOURCE_FILE_NODE:
358 case PM_SOURCE_LINE_NODE:
359 case PM_STRING_NODE:
360 case PM_SYMBOL_NODE:
361 case PM_TRUE_NODE:
362 break;
363 default:
364 return NULL;
365 }
366
367 if (literals->capacity == 0) {
368 /* A set without a hash table compares the new node against each of
369 * its nodes directly. Comparing nodes of different types returns
370 * early, so this costs about as much as hashing the new node. */
371 for (uint32_t index = 0; index < literals->size; index++) {
372 pm_node_t *existing = literals->nodes[index];
373
374 if (compare_nodes(parser, existing, node) == 0) {
375 if (replace) literals->nodes[index] = node;
376 return existing;
377 }
378 }
379
380 if (literals->size < PM_STATIC_LITERALS_INLINE_CAPACITY) {
381 literals->nodes[literals->size++] = node;
382 return NULL;
383 }
384
385 /* The set is full, so its nodes move into a hash table. The table is
386 * sized to stay at most half full after this node is added, with room
387 * to spare before its first resize. */
388 pm_static_literals_resize(parser, literals, PM_STATIC_LITERALS_INLINE_CAPACITY * 4);
389 } else if (literals->size * 2 >= literals->capacity) {
390 /* If we are out of space, we need to resize the hash. */
391 pm_static_literals_resize(parser, literals, literals->capacity * 2);
392 }
393
394 uint64_t hash = node_hash(parser, node);
395 uint32_t mask = literals->capacity - 1;
396 uint32_t index = (uint32_t) (hash & mask);
397
398 /* We use linear probing to resolve collisions. This means that if the
399 * current index is occupied, we will move to the next index and try again.
400 * We are guaranteed that this will eventually find an empty slot because we
401 * resize the hash when it gets too full. Entries whose hash differs cannot
402 * be equal, so only entries with a matching hash are compared. */
403 while (literals->entries[index].node != NULL) {
404 const pm_static_literals_entry_t *entry = &literals->entries[index];
405 if (entry->hash == hash && compare_nodes(parser, entry->node, node) == 0) break;
406 index = (index + 1) & mask;
407 }
408
409 /* If the current index is occupied, we need to return the node that was
410 * already in the hash. Otherwise, we can just increment the size and insert
411 * the new node. */
412 pm_node_t *result = literals->entries[index].node;
413
414 if (result == NULL) {
415 literals->size++;
416 literals->entries[index] = (pm_static_literals_entry_t) { .node = node, .hash = hash };
417 } else if (replace) {
418 literals->entries[index].node = node;
419 }
420
421 return result;
422}
423
427void
428pm_static_literals_free(pm_static_literals_t *literals) {
429 if (literals->capacity > 0) xfree_sized(literals->entries, literals->capacity * sizeof(pm_static_literals_entry_t));
430}
431
436static bool
437pm_static_literal_positive_p(const pm_node_t *node) {
438 switch (PM_NODE_TYPE(node)) {
439 case PM_FLOAT_NODE:
440 return ((const pm_float_node_t *) node)->value > 0;
441 case PM_INTEGER_NODE:
442 return !((const pm_integer_node_t *) node)->value.negative;
443 case PM_RATIONAL_NODE:
444 return !((const pm_rational_node_t *) node)->numerator.negative;
445 case PM_IMAGINARY_NODE:
446 return pm_static_literal_positive_p(((const pm_imaginary_node_t *) node)->numeric);
447 default:
448 PRISM_ASSERT(false && "unreachable");
449 return false;
450 }
451}
452
456void
457pm_static_literal_inspect(pm_buffer_t *buffer, const pm_parser_t *parser, const pm_node_t *node) {
458 switch (PM_NODE_TYPE(node)) {
459 case PM_FALSE_NODE:
460 PM_BUFFER_APPEND_LITERAL(buffer, "false");
461 break;
462 case PM_FLOAT_NODE: {
463 const double value = ((const pm_float_node_t *) node)->value;
464
465 if (PRISM_ISINF(value)) {
466 if (parser->start[node->location.start] == '-') {
467 pm_buffer_append_byte(buffer, '-');
468 }
469 PM_BUFFER_APPEND_LITERAL(buffer, "Infinity");
470 } else if (value == 0.0) {
471 if (parser->start[node->location.start] == '-') {
472 pm_buffer_append_byte(buffer, '-');
473 }
474 PM_BUFFER_APPEND_LITERAL(buffer, "0.0");
475 } else {
476 pm_buffer_append_format(buffer, "%g", value);
477
478 /* %g will not insert a .0 for 1e100 (we'll get back 1e+100). So
479 * we check for the decimal point and add it in here if it's not
480 * present. */
481 if (pm_buffer_index(buffer, '.') == SIZE_MAX) {
482 size_t exponent_index = pm_buffer_index(buffer, 'e');
483 size_t index = exponent_index == SIZE_MAX ? pm_buffer_length(buffer) : exponent_index;
484 pm_buffer_insert(buffer, index, ".0", 2);
485 }
486 }
487
488 break;
489 }
490 case PM_IMAGINARY_NODE: {
491 const pm_node_t *numeric = ((const pm_imaginary_node_t *) node)->numeric;
492 PM_BUFFER_APPEND_LITERAL(buffer, "(0");
493 if (pm_static_literal_positive_p(numeric)) pm_buffer_append_byte(buffer, '+');
494 pm_static_literal_inspect(buffer, parser, numeric);
495 if (PM_NODE_TYPE_P(numeric, PM_RATIONAL_NODE)) {
496 pm_buffer_append_byte(buffer, '*');
497 }
498 PM_BUFFER_APPEND_LITERAL(buffer, "i)");
499 break;
500 }
501 case PM_INTEGER_NODE:
502 pm_integer_string(buffer, &((const pm_integer_node_t *) node)->value);
503 break;
504 case PM_NIL_NODE:
505 PM_BUFFER_APPEND_LITERAL(buffer, "nil");
506 break;
507 case PM_RATIONAL_NODE: {
508 const pm_rational_node_t *rational = (const pm_rational_node_t *) node;
509 pm_buffer_append_byte(buffer, '(');
510 pm_integer_string(buffer, &rational->numerator);
511 pm_buffer_append_byte(buffer, '/');
512 pm_integer_string(buffer, &rational->denominator);
513 pm_buffer_append_byte(buffer, ')');
514 break;
515 }
516 case PM_REGULAR_EXPRESSION_NODE: {
517 const pm_string_t *unescaped = &((const pm_regular_expression_node_t *) node)->unescaped;
518 pm_buffer_append_byte(buffer, '/');
519 pm_buffer_append_source(buffer, pm_string_source(unescaped), pm_string_length(unescaped), PM_BUFFER_ESCAPING_RUBY);
520 pm_buffer_append_byte(buffer, '/');
521
522 if (PM_NODE_FLAG_P(node, PM_REGULAR_EXPRESSION_FLAGS_MULTI_LINE)) pm_buffer_append_byte(buffer, 'm');
523 if (PM_NODE_FLAG_P(node, PM_REGULAR_EXPRESSION_FLAGS_IGNORE_CASE)) pm_buffer_append_byte(buffer, 'i');
524 if (PM_NODE_FLAG_P(node, PM_REGULAR_EXPRESSION_FLAGS_EXTENDED)) pm_buffer_append_byte(buffer, 'x');
525 if (PM_NODE_FLAG_P(node, PM_REGULAR_EXPRESSION_FLAGS_ASCII_8BIT)) pm_buffer_append_byte(buffer, 'n');
526
527 break;
528 }
529 case PM_SOURCE_ENCODING_NODE:
530 pm_buffer_append_format(buffer, "#<Encoding:%s>", parser->encoding->name);
531 break;
532 case PM_SOURCE_FILE_NODE: {
533 const pm_string_t *filepath = &((const pm_source_file_node_t *) node)->filepath;
534 pm_buffer_append_byte(buffer, '"');
535 pm_buffer_append_source(buffer, pm_string_source(filepath), pm_string_length(filepath), PM_BUFFER_ESCAPING_RUBY);
536 pm_buffer_append_byte(buffer, '"');
537 break;
538 }
539 case PM_SOURCE_LINE_NODE:
540 pm_buffer_append_format(buffer, "%" PRIi32, pm_line_offset_list_line_column(&parser->line_offsets, node->location.start, parser->start_line).line);
541 break;
542 case PM_STRING_NODE: {
543 const pm_string_t *unescaped = &((const pm_string_node_t *) node)->unescaped;
544 pm_buffer_append_byte(buffer, '"');
545 pm_buffer_append_source(buffer, pm_string_source(unescaped), pm_string_length(unescaped), PM_BUFFER_ESCAPING_RUBY);
546 pm_buffer_append_byte(buffer, '"');
547 break;
548 }
549 case PM_SYMBOL_NODE: {
550 const pm_string_t *unescaped = &((const pm_symbol_node_t *) node)->unescaped;
551 pm_buffer_append_byte(buffer, ':');
552 pm_buffer_append_source(buffer, pm_string_source(unescaped), pm_string_length(unescaped), PM_BUFFER_ESCAPING_RUBY);
553 break;
554 }
555 case PM_TRUE_NODE:
556 PM_BUFFER_APPEND_LITERAL(buffer, "true");
557 break;
558 default:
559 PRISM_ASSERT(false && "unreachable");
560 break;
561 }
562}
#define xcalloc
Old name of ruby_xcalloc.
Definition xmalloc.h:55
#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
static PRISM_INLINE uint64_t pm_integer_uint64_value(const pm_integer_t *integer)
Return the magnitude of an integer whose length is at most 2, which always fits in a uint64_t.
Definition integer.h:75
VALUE type(ANYARGS)
ANYARGS-ed function type.
T * cast(pm_node_t *node) noexcept
Cast the given node, which must not be null and must be of the given struct, to that struct.
Definition node.hpp:50
A structure represents an arbitrary-sized integer.
Definition integer.h:19
uint32_t length
The number of words in the magnitude, with no leading zero words.
Definition integer.h:24
uint32_t * values
The words of an integer whose length is greater than 2.
Definition integer.h:45
bool negative
Whether or not the integer is negative.
Definition integer.h:29
uint32_t value[2]
The words of an integer whose length is at most 2.
Definition integer.h:40
union pm_integer_t::@344106104334032307171003340315163164214337104357 words
The words of the magnitude.
uint32_t start
The offset of the location from the start of the source.
Definition ast.h:581
pm_node_flags_t flags
This represents any flags on the node.
Definition ast.h:1102
pm_location_t location
This is the location of the node in the source.
Definition ast.h:1116
pm_integer_t denominator
RationalNode::denominator.
Definition ast.h:6959
pm_integer_t numerator
RationalNode::numerator.
Definition ast.h:6950
pm_string_t unescaped
RegularExpressionNode::unescaped.
Definition ast.h:7026
A view of a sequence of bytes.
Definition stringy.h:23
#define PRISM_UNUSED
GCC will warn if you specify a function or parameter that is unused at runtime.
Definition unused.h:13