1 #include "jsi.h"
2 #include "jsvalue.h"
3
4 /*
5 Use an AA-tree to quickly look up properties in objects:
6
7 The level of every leaf node is one.
8 The level of every left child is one less than its parent.
9 The level of every right child is equal or one less than its parent.
10 The level of every right grandchild is less than its grandparent.
11 Every node of level greater than one has two children.
12
13 A link where the child's level is equal to that of its parent is called a horizontal link.
14 Individual right horizontal links are allowed, but consecutive ones are forbidden.
15 Left horizontal links are forbidden.
16
17 skew() fixes left horizontal links.
18 split() fixes consecutive right horizontal links.
19 */
20
21 static js_Property sentinel = {
22 "",
23 &sentinel, &sentinel,
24 0, 0,
25 { {0}, {0}, JS_TUNDEFINED },
26 NULL, NULL
27 };
28
newproperty(js_State * J,js_Object * obj,const char * name)29 static js_Property *newproperty(js_State *J, js_Object *obj, const char *name)
30 {
31 js_Property *node = js_malloc(J, sizeof *node);
32 node->name = js_intern(J, name);
33 node->left = node->right = &sentinel;
34 node->level = 1;
35 node->atts = 0;
36 node->value.type = JS_TUNDEFINED;
37 node->value.u.number = 0;
38 node->getter = NULL;
39 node->setter = NULL;
40 ++obj->count;
41 ++J->gccounter;
42 return node;
43 }
44
lookup(js_Property * node,const char * name)45 static js_Property *lookup(js_Property *node, const char *name)
46 {
47 while (node != &sentinel) {
48 int c = strcmp(name, node->name);
49 if (c == 0)
50 return node;
51 else if (c < 0)
52 node = node->left;
53 else
54 node = node->right;
55 }
56 return NULL;
57 }
58
skew(js_Property * node)59 static js_Property *skew(js_Property *node)
60 {
61 if (node->left->level == node->level) {
62 js_Property *temp = node;
63 node = node->left;
64 temp->left = node->right;
65 node->right = temp;
66 }
67 return node;
68 }
69
split(js_Property * node)70 static js_Property *split(js_Property *node)
71 {
72 if (node->right->right->level == node->level) {
73 js_Property *temp = node;
74 node = node->right;
75 temp->right = node->left;
76 node->left = temp;
77 ++node->level;
78 }
79 return node;
80 }
81
insert(js_State * J,js_Object * obj,js_Property * node,const char * name,js_Property ** result)82 static js_Property *insert(js_State *J, js_Object *obj, js_Property *node, const char *name, js_Property **result)
83 {
84 if (node != &sentinel) {
85 int c = strcmp(name, node->name);
86 if (c < 0)
87 node->left = insert(J, obj, node->left, name, result);
88 else if (c > 0)
89 node->right = insert(J, obj, node->right, name, result);
90 else
91 return *result = node;
92 node = skew(node);
93 node = split(node);
94 return node;
95 }
96 return *result = newproperty(J, obj, name);
97 }
98
freeproperty(js_State * J,js_Object * obj,js_Property * node)99 static void freeproperty(js_State *J, js_Object *obj, js_Property *node)
100 {
101 js_free(J, node);
102 --obj->count;
103 }
104
delete(js_State * J,js_Object * obj,js_Property * node,const char * name)105 static js_Property *delete(js_State *J, js_Object *obj, js_Property *node, const char *name)
106 {
107 js_Property *temp, *succ;
108
109 if (node != &sentinel) {
110 int c = strcmp(name, node->name);
111 if (c < 0) {
112 node->left = delete(J, obj, node->left, name);
113 } else if (c > 0) {
114 node->right = delete(J, obj, node->right, name);
115 } else {
116 if (node->left == &sentinel) {
117 temp = node;
118 node = node->right;
119 freeproperty(J, obj, temp);
120 } else if (node->right == &sentinel) {
121 temp = node;
122 node = node->left;
123 freeproperty(J, obj, temp);
124 } else {
125 succ = node->right;
126 while (succ->left != &sentinel)
127 succ = succ->left;
128 node->name = succ->name;
129 node->atts = succ->atts;
130 node->value = succ->value;
131 node->right = delete(J, obj, node->right, succ->name);
132 }
133 }
134
135 if (node->left->level < node->level - 1 ||
136 node->right->level < node->level - 1)
137 {
138 if (node->right->level > --node->level)
139 node->right->level = node->level;
140 node = skew(node);
141 node->right = skew(node->right);
142 node->right->right = skew(node->right->right);
143 node = split(node);
144 node->right = split(node->right);
145 }
146 }
147 return node;
148 }
149
jsV_newobject(js_State * J,enum js_Class type,js_Object * prototype)150 js_Object *jsV_newobject(js_State *J, enum js_Class type, js_Object *prototype)
151 {
152 js_Object *obj = js_malloc(J, sizeof *obj);
153 memset(obj, 0, sizeof *obj);
154 obj->gcmark = 0;
155 obj->gcnext = J->gcobj;
156 J->gcobj = obj;
157 ++J->gccounter;
158
159 obj->type = type;
160 obj->properties = &sentinel;
161 obj->prototype = prototype;
162 obj->extensible = 1;
163 return obj;
164 }
165
jsV_getownproperty(js_State * J,js_Object * obj,const char * name)166 js_Property *jsV_getownproperty(js_State *J, js_Object *obj, const char *name)
167 {
168 return lookup(obj->properties, name);
169 }
170
jsV_getpropertyx(js_State * J,js_Object * obj,const char * name,int * own)171 js_Property *jsV_getpropertyx(js_State *J, js_Object *obj, const char *name, int *own)
172 {
173 *own = 1;
174 do {
175 js_Property *ref = lookup(obj->properties, name);
176 if (ref)
177 return ref;
178 obj = obj->prototype;
179 *own = 0;
180 } while (obj);
181 return NULL;
182 }
183
jsV_getproperty(js_State * J,js_Object * obj,const char * name)184 js_Property *jsV_getproperty(js_State *J, js_Object *obj, const char *name)
185 {
186 do {
187 js_Property *ref = lookup(obj->properties, name);
188 if (ref)
189 return ref;
190 obj = obj->prototype;
191 } while (obj);
192 return NULL;
193 }
194
jsV_getenumproperty(js_State * J,js_Object * obj,const char * name)195 static js_Property *jsV_getenumproperty(js_State *J, js_Object *obj, const char *name)
196 {
197 do {
198 js_Property *ref = lookup(obj->properties, name);
199 if (ref && !(ref->atts & JS_DONTENUM))
200 return ref;
201 obj = obj->prototype;
202 } while (obj);
203 return NULL;
204 }
205
jsV_setproperty(js_State * J,js_Object * obj,const char * name)206 js_Property *jsV_setproperty(js_State *J, js_Object *obj, const char *name)
207 {
208 js_Property *result;
209
210 if (!obj->extensible) {
211 result = lookup(obj->properties, name);
212 if (J->strict && !result)
213 js_typeerror(J, "object is non-extensible");
214 return result;
215 }
216
217 obj->properties = insert(J, obj, obj->properties, name, &result);
218
219 return result;
220 }
221
jsV_delproperty(js_State * J,js_Object * obj,const char * name)222 void jsV_delproperty(js_State *J, js_Object *obj, const char *name)
223 {
224 obj->properties = delete(J, obj, obj->properties, name);
225 }
226
227 /* Flatten hierarchy of enumerable properties into an iterator object */
228
itwalk(js_State * J,js_Iterator * iter,js_Property * prop,js_Object * seen)229 static js_Iterator *itwalk(js_State *J, js_Iterator *iter, js_Property *prop, js_Object *seen)
230 {
231 if (prop->right != &sentinel)
232 iter = itwalk(J, iter, prop->right, seen);
233 if (!(prop->atts & JS_DONTENUM)) {
234 if (!seen || !jsV_getenumproperty(J, seen, prop->name)) {
235 js_Iterator *head = js_malloc(J, sizeof *head);
236 head->name = prop->name;
237 head->next = iter;
238 iter = head;
239 }
240 }
241 if (prop->left != &sentinel)
242 iter = itwalk(J, iter, prop->left, seen);
243 return iter;
244 }
245
itflatten(js_State * J,js_Object * obj)246 static js_Iterator *itflatten(js_State *J, js_Object *obj)
247 {
248 js_Iterator *iter = NULL;
249 if (obj->prototype)
250 iter = itflatten(J, obj->prototype);
251 if (obj->properties != &sentinel)
252 iter = itwalk(J, iter, obj->properties, obj->prototype);
253 return iter;
254 }
255
jsV_newiterator(js_State * J,js_Object * obj,int own)256 js_Object *jsV_newiterator(js_State *J, js_Object *obj, int own)
257 {
258 char buf[32];
259 int k;
260 js_Object *io = jsV_newobject(J, JS_CITERATOR, NULL);
261 io->u.iter.target = obj;
262 if (own) {
263 io->u.iter.head = NULL;
264 if (obj->properties != &sentinel)
265 io->u.iter.head = itwalk(J, io->u.iter.head, obj->properties, NULL);
266 } else {
267 io->u.iter.head = itflatten(J, obj);
268 }
269 if (obj->type == JS_CSTRING) {
270 js_Iterator *tail = io->u.iter.head;
271 if (tail)
272 while (tail->next)
273 tail = tail->next;
274 for (k = 0; k < obj->u.s.length; ++k) {
275 js_itoa(buf, k);
276 if (!jsV_getenumproperty(J, obj, buf)) {
277 js_Iterator *node = js_malloc(J, sizeof *node);
278 node->name = js_intern(J, js_itoa(buf, k));
279 node->next = NULL;
280 if (!tail)
281 io->u.iter.head = tail = node;
282 else {
283 tail->next = node;
284 tail = node;
285 }
286 }
287 }
288 }
289 return io;
290 }
291
jsV_nextiterator(js_State * J,js_Object * io)292 const char *jsV_nextiterator(js_State *J, js_Object *io)
293 {
294 int k;
295 if (io->type != JS_CITERATOR)
296 js_typeerror(J, "not an iterator");
297 while (io->u.iter.head) {
298 js_Iterator *next = io->u.iter.head->next;
299 const char *name = io->u.iter.head->name;
300 js_free(J, io->u.iter.head);
301 io->u.iter.head = next;
302 if (jsV_getproperty(J, io->u.iter.target, name))
303 return name;
304 if (io->u.iter.target->type == JS_CSTRING)
305 if (js_isarrayindex(J, name, &k) && k < io->u.iter.target->u.s.length)
306 return name;
307 }
308 return NULL;
309 }
310
311 /* Walk all the properties and delete them one by one for arrays */
312
jsV_resizearray(js_State * J,js_Object * obj,int newlen)313 void jsV_resizearray(js_State *J, js_Object *obj, int newlen)
314 {
315 char buf[32];
316 const char *s;
317 int k;
318 if (newlen < obj->u.a.length) {
319 if (obj->u.a.length > obj->count * 2) {
320 js_Object *it = jsV_newiterator(J, obj, 1);
321 while ((s = jsV_nextiterator(J, it))) {
322 k = jsV_numbertointeger(jsV_stringtonumber(J, s));
323 if (k >= newlen && !strcmp(s, jsV_numbertostring(J, buf, k)))
324 jsV_delproperty(J, obj, s);
325 }
326 } else {
327 for (k = newlen; k < obj->u.a.length; ++k) {
328 jsV_delproperty(J, obj, js_itoa(buf, k));
329 }
330 }
331 }
332 obj->u.a.length = newlen;
333 }
334