jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020-2021, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibJS/Heap/DeferGC.h>
8#include <LibJS/Runtime/Shape.h>
9#include <LibJS/Runtime/VM.h>
10
11namespace JS {
12
13Shape* Shape::create_unique_clone() const
14{
15 auto new_shape = heap().allocate_without_realm<Shape>(m_realm);
16 new_shape->m_unique = true;
17 new_shape->m_prototype = m_prototype;
18 ensure_property_table();
19 new_shape->ensure_property_table();
20 (*new_shape->m_property_table) = *m_property_table;
21 new_shape->m_property_count = new_shape->m_property_table->size();
22 return new_shape;
23}
24
25Shape* Shape::get_or_prune_cached_forward_transition(TransitionKey const& key)
26{
27 if (!m_forward_transitions)
28 return nullptr;
29 auto it = m_forward_transitions->find(key);
30 if (it == m_forward_transitions->end())
31 return nullptr;
32 if (!it->value) {
33 // The cached forward transition has gone stale (from garbage collection). Prune it.
34 m_forward_transitions->remove(it);
35 return nullptr;
36 }
37 return it->value;
38}
39
40Shape* Shape::get_or_prune_cached_prototype_transition(Object* prototype)
41{
42 if (!m_prototype_transitions)
43 return nullptr;
44 auto it = m_prototype_transitions->find(prototype);
45 if (it == m_prototype_transitions->end())
46 return nullptr;
47 if (!it->value) {
48 // The cached prototype transition has gone stale (from garbage collection). Prune it.
49 m_prototype_transitions->remove(it);
50 return nullptr;
51 }
52 return it->value;
53}
54
55Shape* Shape::create_put_transition(StringOrSymbol const& property_key, PropertyAttributes attributes)
56{
57 TransitionKey key { property_key, attributes };
58 if (auto* existing_shape = get_or_prune_cached_forward_transition(key))
59 return existing_shape;
60 auto new_shape = heap().allocate_without_realm<Shape>(*this, property_key, attributes, TransitionType::Put);
61 if (!m_forward_transitions)
62 m_forward_transitions = make<HashMap<TransitionKey, WeakPtr<Shape>>>();
63 m_forward_transitions->set(key, new_shape.ptr());
64 return new_shape;
65}
66
67Shape* Shape::create_configure_transition(StringOrSymbol const& property_key, PropertyAttributes attributes)
68{
69 TransitionKey key { property_key, attributes };
70 if (auto* existing_shape = get_or_prune_cached_forward_transition(key))
71 return existing_shape;
72 auto new_shape = heap().allocate_without_realm<Shape>(*this, property_key, attributes, TransitionType::Configure);
73 if (!m_forward_transitions)
74 m_forward_transitions = make<HashMap<TransitionKey, WeakPtr<Shape>>>();
75 m_forward_transitions->set(key, new_shape.ptr());
76 return new_shape;
77}
78
79Shape* Shape::create_prototype_transition(Object* new_prototype)
80{
81 if (auto* existing_shape = get_or_prune_cached_prototype_transition(new_prototype))
82 return existing_shape;
83 auto new_shape = heap().allocate_without_realm<Shape>(*this, new_prototype);
84 if (!m_prototype_transitions)
85 m_prototype_transitions = make<HashMap<Object*, WeakPtr<Shape>>>();
86 m_prototype_transitions->set(new_prototype, new_shape.ptr());
87 return new_shape;
88}
89
90Shape::Shape(Realm& realm)
91 : m_realm(realm)
92{
93}
94
95Shape::Shape(Shape& previous_shape, StringOrSymbol const& property_key, PropertyAttributes attributes, TransitionType transition_type)
96 : m_realm(previous_shape.m_realm)
97 , m_previous(&previous_shape)
98 , m_property_key(property_key)
99 , m_prototype(previous_shape.m_prototype)
100 , m_property_count(transition_type == TransitionType::Put ? previous_shape.m_property_count + 1 : previous_shape.m_property_count)
101 , m_attributes(attributes)
102 , m_transition_type(transition_type)
103{
104}
105
106Shape::Shape(Shape& previous_shape, Object* new_prototype)
107 : m_realm(previous_shape.m_realm)
108 , m_previous(&previous_shape)
109 , m_prototype(new_prototype)
110 , m_property_count(previous_shape.m_property_count)
111 , m_transition_type(TransitionType::Prototype)
112{
113}
114
115void Shape::visit_edges(Cell::Visitor& visitor)
116{
117 Cell::visit_edges(visitor);
118 visitor.visit(&m_realm);
119 visitor.visit(m_prototype);
120 visitor.visit(m_previous);
121 m_property_key.visit_edges(visitor);
122 if (m_property_table) {
123 for (auto& it : *m_property_table)
124 it.key.visit_edges(visitor);
125 }
126}
127
128Optional<PropertyMetadata> Shape::lookup(StringOrSymbol const& property_key) const
129{
130 if (m_property_count == 0)
131 return {};
132 auto property = property_table().get(property_key);
133 if (!property.has_value())
134 return {};
135 return property;
136}
137
138FLATTEN HashMap<StringOrSymbol, PropertyMetadata> const& Shape::property_table() const
139{
140 ensure_property_table();
141 return *m_property_table;
142}
143
144Vector<Shape::Property> Shape::property_table_ordered() const
145{
146 auto vec = Vector<Shape::Property>();
147 vec.resize(property_count());
148
149 for (auto& it : property_table()) {
150 vec[it.value.offset] = { it.key, it.value };
151 }
152
153 return vec;
154}
155
156void Shape::ensure_property_table() const
157{
158 if (m_property_table)
159 return;
160 m_property_table = make<HashMap<StringOrSymbol, PropertyMetadata>>();
161
162 u32 next_offset = 0;
163
164 Vector<Shape const&, 64> transition_chain;
165 for (auto* shape = m_previous; shape; shape = shape->m_previous) {
166 if (shape->m_property_table) {
167 *m_property_table = *shape->m_property_table;
168 next_offset = shape->m_property_count;
169 break;
170 }
171 transition_chain.append(*shape);
172 }
173 transition_chain.append(*this);
174
175 for (auto const& shape : transition_chain.in_reverse()) {
176 if (!shape.m_property_key.is_valid()) {
177 // Ignore prototype transitions as they don't affect the key map.
178 continue;
179 }
180 if (shape.m_transition_type == TransitionType::Put) {
181 m_property_table->set(shape.m_property_key, { next_offset++, shape.m_attributes });
182 } else if (shape.m_transition_type == TransitionType::Configure) {
183 auto it = m_property_table->find(shape.m_property_key);
184 VERIFY(it != m_property_table->end());
185 it->value.attributes = shape.m_attributes;
186 }
187 }
188}
189
190void Shape::add_property_to_unique_shape(StringOrSymbol const& property_key, PropertyAttributes attributes)
191{
192 VERIFY(is_unique());
193 VERIFY(m_property_table);
194 VERIFY(!m_property_table->contains(property_key));
195 m_property_table->set(property_key, { static_cast<u32>(m_property_table->size()), attributes });
196
197 VERIFY(m_property_count < NumericLimits<u32>::max());
198 ++m_property_count;
199}
200
201void Shape::reconfigure_property_in_unique_shape(StringOrSymbol const& property_key, PropertyAttributes attributes)
202{
203 VERIFY(is_unique());
204 VERIFY(m_property_table);
205 auto it = m_property_table->find(property_key);
206 VERIFY(it != m_property_table->end());
207 it->value.attributes = attributes;
208 m_property_table->set(property_key, it->value);
209}
210
211void Shape::remove_property_from_unique_shape(StringOrSymbol const& property_key, size_t offset)
212{
213 VERIFY(is_unique());
214 VERIFY(m_property_table);
215 if (m_property_table->remove(property_key))
216 --m_property_count;
217 for (auto& it : *m_property_table) {
218 VERIFY(it.value.offset != offset);
219 if (it.value.offset > offset)
220 --it.value.offset;
221 }
222}
223
224void Shape::add_property_without_transition(StringOrSymbol const& property_key, PropertyAttributes attributes)
225{
226 VERIFY(property_key.is_valid());
227 ensure_property_table();
228 if (m_property_table->set(property_key, { m_property_count, attributes }) == AK::HashSetResult::InsertedNewEntry) {
229 VERIFY(m_property_count < NumericLimits<u32>::max());
230 ++m_property_count;
231 }
232}
233
234FLATTEN void Shape::add_property_without_transition(PropertyKey const& property_key, PropertyAttributes attributes)
235{
236 VERIFY(property_key.is_valid());
237 add_property_without_transition(property_key.to_string_or_symbol(), attributes);
238}
239
240}