Ruby 3.5.0dev (2025-06-07 revision 20cf46039a90135b3d9efceabc73b0d41ad257b8)
shape.h (20cf46039a90135b3d9efceabc73b0d41ad257b8)
1#ifndef RUBY_SHAPE_H
2#define RUBY_SHAPE_H
3
4#include "internal/gc.h"
5
6typedef uint16_t attr_index_t;
7typedef uint32_t shape_id_t;
8#define SHAPE_ID_NUM_BITS 32
9#define SHAPE_ID_OFFSET_NUM_BITS 19
10
11STATIC_ASSERT(shape_id_num_bits, SHAPE_ID_NUM_BITS == sizeof(shape_id_t) * CHAR_BIT);
12
13#define SHAPE_BUFFER_SIZE (1 << SHAPE_ID_OFFSET_NUM_BITS)
14#define SHAPE_ID_OFFSET_MASK (SHAPE_BUFFER_SIZE - 1)
15#define SHAPE_ID_FLAGS_MASK (shape_id_t)(((1 << (SHAPE_ID_NUM_BITS - SHAPE_ID_OFFSET_NUM_BITS)) - 1) << SHAPE_ID_OFFSET_NUM_BITS)
16#define SHAPE_ID_FL_FROZEN (SHAPE_FL_FROZEN << SHAPE_ID_OFFSET_NUM_BITS)
17#define SHAPE_ID_FL_HAS_OBJECT_ID (SHAPE_FL_HAS_OBJECT_ID << SHAPE_ID_OFFSET_NUM_BITS)
18#define SHAPE_ID_FL_TOO_COMPLEX (SHAPE_FL_TOO_COMPLEX << SHAPE_ID_OFFSET_NUM_BITS)
19#define SHAPE_ID_FL_NON_CANONICAL_MASK (SHAPE_FL_NON_CANONICAL_MASK << SHAPE_ID_OFFSET_NUM_BITS)
20#define SHAPE_ID_READ_ONLY_MASK (~SHAPE_ID_FL_FROZEN)
21
22typedef uint32_t redblack_id_t;
23
24#define SHAPE_MAX_FIELDS (attr_index_t)(-1)
25#define SHAPE_FLAG_SHIFT ((SIZEOF_VALUE * CHAR_BIT) - SHAPE_ID_NUM_BITS)
26#define SHAPE_FLAG_MASK (((VALUE)-1) >> SHAPE_ID_NUM_BITS)
27
28#define SHAPE_MAX_VARIATIONS 8
29
30#define INVALID_SHAPE_ID ((shape_id_t)-1)
31#define ATTR_INDEX_NOT_SET ((attr_index_t)-1)
32
33#define ROOT_SHAPE_ID 0x0
34#define ROOT_SHAPE_WITH_OBJ_ID 0x1
35#define ROOT_TOO_COMPLEX_SHAPE_ID (ROOT_SHAPE_ID | SHAPE_ID_FL_TOO_COMPLEX)
36#define ROOT_TOO_COMPLEX_WITH_OBJ_ID (ROOT_SHAPE_WITH_OBJ_ID | SHAPE_ID_FL_TOO_COMPLEX | SHAPE_ID_FL_HAS_OBJECT_ID)
37#define SPECIAL_CONST_SHAPE_ID (ROOT_SHAPE_ID | SHAPE_ID_FL_FROZEN)
38#define FIRST_T_OBJECT_SHAPE_ID 0x2
39
40extern ID ruby_internal_object_id;
41
42typedef struct redblack_node redblack_node_t;
43
44struct rb_shape {
45 VALUE edges; // id_table from ID (ivar) to next shape
46 ID edge_name; // ID (ivar) for transition from parent to rb_shape
47 redblack_node_t *ancestor_index;
48 shape_id_t parent_id;
49 attr_index_t next_field_index; // Fields are either ivars or internal properties like `object_id`
50 attr_index_t capacity; // Total capacity of the object with this shape
51 uint8_t type;
52 uint8_t heap_index;
53};
54
55typedef struct rb_shape rb_shape_t;
56
58 ID key;
59 rb_shape_t *value;
60 redblack_id_t l;
61 redblack_id_t r;
62};
63
64enum shape_type {
65 SHAPE_ROOT,
66 SHAPE_IVAR,
67 SHAPE_OBJ_ID,
68 SHAPE_T_OBJECT,
69};
70
71enum shape_flags {
72 SHAPE_FL_FROZEN = 1 << 0,
73 SHAPE_FL_HAS_OBJECT_ID = 1 << 1,
74 SHAPE_FL_TOO_COMPLEX = 1 << 2,
75
76 SHAPE_FL_NON_CANONICAL_MASK = SHAPE_FL_FROZEN | SHAPE_FL_HAS_OBJECT_ID,
77};
78
79typedef struct {
80 /* object shapes */
81 rb_shape_t *shape_list;
82 rb_shape_t *root_shape;
83 rb_atomic_t next_shape_id;
84
85 redblack_node_t *shape_cache;
86 unsigned int cache_size;
88RUBY_EXTERN rb_shape_tree_t *rb_shape_tree_ptr;
89
91 uint64_t pack;
92 struct {
93 shape_id_t shape_id;
94 attr_index_t index;
95 } unpack;
96};
97
98static inline rb_shape_tree_t *
99rb_current_shape_tree(void)
100{
101 return rb_shape_tree_ptr;
102}
103#define GET_SHAPE_TREE() rb_current_shape_tree()
104
105static inline shape_id_t
106RBASIC_SHAPE_ID(VALUE obj)
107{
110#if RBASIC_SHAPE_ID_FIELD
111 return (shape_id_t)((RBASIC(obj)->shape_id));
112#else
113 return (shape_id_t)((RBASIC(obj)->flags) >> SHAPE_FLAG_SHIFT);
114#endif
115}
116
117// Same as RBASIC_SHAPE_ID but with flags that have no impact
118// on reads removed. e.g. Remove FL_FROZEN.
119static inline shape_id_t
120RBASIC_SHAPE_ID_FOR_READ(VALUE obj)
121{
122 return RBASIC_SHAPE_ID(obj) & SHAPE_ID_READ_ONLY_MASK;
123}
124
125#if RUBY_DEBUG
126bool rb_shape_verify_consistency(VALUE obj, shape_id_t shape_id);
127#endif
128
129static inline void
130RBASIC_SET_SHAPE_ID(VALUE obj, shape_id_t shape_id)
131{
134 RUBY_ASSERT(rb_shape_verify_consistency(obj, shape_id));
135#if RBASIC_SHAPE_ID_FIELD
136 RBASIC(obj)->shape_id = (VALUE)shape_id;
137#else
138 // Object shapes are occupying top bits
139 RBASIC(obj)->flags &= SHAPE_FLAG_MASK;
140 RBASIC(obj)->flags |= ((VALUE)(shape_id) << SHAPE_FLAG_SHIFT);
141#endif
142}
143
144#define RSHAPE rb_shape_lookup
145
146int32_t rb_shape_id_offset(void);
147
148RUBY_FUNC_EXPORTED rb_shape_t *rb_shape_lookup(shape_id_t shape_id);
149RUBY_FUNC_EXPORTED shape_id_t rb_obj_shape_id(VALUE obj);
150shape_id_t rb_shape_get_next_iv_shape(shape_id_t shape_id, ID id);
151bool rb_shape_get_iv_index(shape_id_t shape_id, ID id, attr_index_t *value);
152bool rb_shape_get_iv_index_with_hint(shape_id_t shape_id, ID id, attr_index_t *value, shape_id_t *shape_id_hint);
153
154shape_id_t rb_shape_transition_frozen(VALUE obj);
155shape_id_t rb_shape_transition_complex(VALUE obj);
156shape_id_t rb_shape_transition_remove_ivar(VALUE obj, ID id, shape_id_t *removed_shape_id);
157shape_id_t rb_shape_transition_add_ivar(VALUE obj, ID id);
158shape_id_t rb_shape_transition_add_ivar_no_warnings(VALUE obj, ID id);
159shape_id_t rb_shape_transition_object_id(VALUE obj);
160shape_id_t rb_shape_object_id(shape_id_t original_shape_id);
161
162void rb_shape_free_all(void);
163
164shape_id_t rb_shape_rebuild(shape_id_t initial_shape_id, shape_id_t dest_shape_id);
165void rb_shape_copy_fields(VALUE dest, VALUE *dest_buf, shape_id_t dest_shape_id, VALUE src, VALUE *src_buf, shape_id_t src_shape_id);
166void rb_shape_copy_complex_ivars(VALUE dest, VALUE obj, shape_id_t src_shape_id, st_table *fields_table);
167
168static inline bool
169rb_shape_too_complex_p(shape_id_t shape_id)
170{
171 return shape_id & SHAPE_ID_FL_TOO_COMPLEX;
172}
173
174static inline bool
175rb_shape_obj_too_complex_p(VALUE obj)
176{
177 return !RB_SPECIAL_CONST_P(obj) && rb_shape_too_complex_p(RBASIC_SHAPE_ID(obj));
178}
179
180static inline bool
181rb_shape_has_object_id(shape_id_t shape_id)
182{
183 return shape_id & SHAPE_ID_FL_HAS_OBJECT_ID;
184}
185
186static inline bool
187rb_shape_canonical_p(shape_id_t shape_id)
188{
189 return !(shape_id & SHAPE_ID_FL_NON_CANONICAL_MASK);
190}
191
192static inline shape_id_t
193rb_shape_root(size_t heap_id)
194{
195 return (shape_id_t)(heap_id + FIRST_T_OBJECT_SHAPE_ID);
196}
197
198static inline bool
199RSHAPE_TYPE_P(shape_id_t shape_id, enum shape_type type)
200{
201 return RSHAPE(shape_id)->type == type;
202}
203
204static inline attr_index_t
205RSHAPE_CAPACITY(shape_id_t shape_id)
206{
207 return RSHAPE(shape_id)->capacity;
208}
209
210static inline attr_index_t
211RSHAPE_LEN(shape_id_t shape_id)
212{
213 return RSHAPE(shape_id)->next_field_index;
214}
215
216static inline attr_index_t
217RSHAPE_INDEX(shape_id_t shape_id)
218{
219 return RSHAPE_LEN(shape_id) - 1;
220}
221
222static inline ID
223RSHAPE_EDGE_NAME(shape_id_t shape_id)
224{
225 return RSHAPE(shape_id)->edge_name;
226}
227
228static inline uint32_t
229ROBJECT_FIELDS_CAPACITY(VALUE obj)
230{
231 RBIMPL_ASSERT_TYPE(obj, RUBY_T_OBJECT);
232 // Asking for capacity doesn't make sense when the object is using
233 // a hash table for storing instance variables
234 RUBY_ASSERT(!rb_shape_obj_too_complex_p(obj));
235 return RSHAPE_CAPACITY(RBASIC_SHAPE_ID(obj));
236}
237
238static inline st_table *
239ROBJECT_FIELDS_HASH(VALUE obj)
240{
241 RBIMPL_ASSERT_TYPE(obj, RUBY_T_OBJECT);
242 RUBY_ASSERT(rb_shape_obj_too_complex_p(obj));
243 return (st_table *)ROBJECT(obj)->as.heap.fields;
244}
245
246static inline void
247ROBJECT_SET_FIELDS_HASH(VALUE obj, const st_table *tbl)
248{
249 RBIMPL_ASSERT_TYPE(obj, RUBY_T_OBJECT);
250 RUBY_ASSERT(rb_shape_obj_too_complex_p(obj));
251 ROBJECT(obj)->as.heap.fields = (VALUE *)tbl;
252}
253
254static inline uint32_t
255ROBJECT_FIELDS_COUNT(VALUE obj)
256{
257 if (rb_shape_obj_too_complex_p(obj)) {
258 return (uint32_t)rb_st_table_size(ROBJECT_FIELDS_HASH(obj));
259 }
260 else {
261 RBIMPL_ASSERT_TYPE(obj, RUBY_T_OBJECT);
262 RUBY_ASSERT(!rb_shape_obj_too_complex_p(obj));
263 return RSHAPE(RBASIC_SHAPE_ID(obj))->next_field_index;
264 }
265}
266
267static inline uint32_t
268RBASIC_FIELDS_COUNT(VALUE obj)
269{
270 return RSHAPE(rb_obj_shape_id(obj))->next_field_index;
271}
272
273shape_id_t rb_shape_traverse_from_new_root(shape_id_t initial_shape_id, shape_id_t orig_shape_id);
274
275bool rb_obj_set_shape_id(VALUE obj, shape_id_t shape_id);
276
277static inline bool
278rb_shape_obj_has_id(VALUE obj)
279{
280 return rb_shape_has_object_id(RBASIC_SHAPE_ID(obj));
281}
282
283// For ext/objspace
284RUBY_SYMBOL_EXPORT_BEGIN
285typedef void each_shape_callback(shape_id_t shape_id, void *data);
286void rb_shape_each_shape_id(each_shape_callback callback, void *data);
287size_t rb_shape_memsize(shape_id_t shape);
288size_t rb_shape_edges_count(shape_id_t shape_id);
289size_t rb_shape_depth(shape_id_t shape_id);
290RUBY_SYMBOL_EXPORT_END
291
292#endif
#define RUBY_ASSERT(...)
Asserts that the given expression is truthy if and only if RUBY_DEBUG is truthy.
Definition assert.h:219
std::atomic< unsigned > rb_atomic_t
Type that is eligible for atomic operations.
Definition atomic.h:69
#define RUBY_EXTERN
Declaration of externally visible global variables.
Definition dllexport.h:45
#define T_IMEMO
Old name of RUBY_T_IMEMO.
Definition value_type.h:67
VALUE type(ANYARGS)
ANYARGS-ed function type.
#define RBASIC(obj)
Convenient casting macro.
Definition rbasic.h:40
#define ROBJECT(obj)
Convenient casting macro.
Definition robject.h:43
static bool RB_SPECIAL_CONST_P(VALUE obj)
Checks if the given object is of enum ruby_special_consts.
Definition st.h:79
uintptr_t ID
Type that represents a Ruby identifier such as a variable name.
Definition value.h:52
uintptr_t VALUE
Type that represents a Ruby object.
Definition value.h:40
static bool RB_TYPE_P(VALUE obj, enum ruby_value_type t)
Queries if the given object is of given type.
Definition value_type.h:376
@ RUBY_T_OBJECT
Definition value_type.h:116