Coverage Report

Created: 2025-01-28 06:17

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