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