/src/mupdf/thirdparty/mujs/jsproperty.c

Source (jump to first uncovered line)
#include "jsi.h"

#include <assert.h>

/*
  Use an AA-tree to quickly look up properties in objects:

  The level of every leaf node is one.
  The level of every left child is one less than its parent.
  The level of every right child is equal or one less than its parent.
  The level of every right grandchild is less than its grandparent.
  Every node of level greater than one has two children.

  A link where the child's level is equal to that of its parent is called a horizontal link.
  Individual right horizontal links are allowed, but consecutive ones are forbidden.
  Left horizontal links are forbidden.

  skew() fixes left horizontal links.
  split() fixes consecutive right horizontal links.
*/

static js_Property sentinel = {
  &sentinel, &sentinel,
  0, 0,
  { { {0}, JS_TUNDEFINED } },
  NULL, NULL, ""
};

static js_Property *newproperty(js_State *J, js_Object *obj, const char *name)
{
  int n = strlen(name) + 1;
  js_Property *node = js_malloc(J, offsetof(js_Property, name) + n);
  node->left = node->right = &sentinel;
  node->level = 1;
  node->atts = 0;
  node->value.t.type = JS_TUNDEFINED;
  node->value.u.number = 0;
  node->getter = NULL;
  node->setter = NULL;
  memcpy(node->name, name, n);
  ++obj->count;
  ++J->gccounter;
  return node;
}

static js_Property *lookup(js_Property *node, const char *name)
{
  while (node != &sentinel) {
    int c = strcmp(name, node->name);
    if (c == 0)
      return node;
    else if (c < 0)
      node = node->left;
    else
      node = node->right;
  }
  return NULL;
}

static js_Property *skew(js_Property *node)
{
  if (node->left->level == node->level) {
    js_Property *temp = node;
    node = node->left;
    temp->left = node->right;
    node->right = temp;
  }
  return node;
}

static js_Property *split(js_Property *node)
{
  if (node->right->right->level == node->level) {
    js_Property *temp = node;
    node = node->right;
    temp->right = node->left;
    node->left = temp;
    ++node->level;
  }
  return node;
}

static js_Property *insert(js_State *J, js_Object *obj, js_Property *node, const char *name, js_Property **result)
{
  if (node != &sentinel) {
    int c = strcmp(name, node->name);
    if (c < 0)
      node->left = insert(J, obj, node->left, name, result);
    else if (c > 0)
      node->right = insert(J, obj, node->right, name, result);
    else
      return *result = node;
    node = skew(node);
    node = split(node);
    return node;
  }
  return *result = newproperty(J, obj, name);
}

static void freeproperty(js_State *J, js_Object *obj, js_Property *node)
{
  js_free(J, node);
  --obj->count;
}

static js_Property *unlinkproperty(js_Property *node, const char *name, js_Property **garbage)
{
  js_Property *temp, *a, *b;
  if (node != &sentinel) {
    int c = strcmp(name, node->name);
    if (c < 0) {
      node->left = unlinkproperty(node->left, name, garbage);
    } else if (c > 0) {
      node->right = unlinkproperty(node->right, name, garbage);
    } else {
      *garbage = node;
      if (node->left == &sentinel && node->right == &sentinel) {
        return &sentinel;
      }
      else if (node->left == &sentinel) {
        a = node->right;
        while (a->left != &sentinel)
          a = a->left;
        b = unlinkproperty(node->right, a->name, &temp);
        temp->level = node->level;
        temp->left = node->left;
        temp->right = b;
        node = temp;
      }
      else {
        a = node->left;
        while (a->right != &sentinel)
          a = a->right;
        b = unlinkproperty(node->left, a->name, &temp);
        temp->level = node->level;
        temp->left = b;
        temp->right = node->right;
        node = temp;
      }
    }

    if (node->left->level < node->level - 1 || node->right->level < node->level - 1)
    {
      if (node->right->level > --node->level)
        node->right->level = node->level;
      node = skew(node);
      node->right = skew(node->right);
      node->right->right = skew(node->right->right);
      node = split(node);
      node->right = split(node->right);
    }
  }
  return node;
}

static js_Property *deleteproperty(js_State *J, js_Object *obj, js_Property *tree, const char *name)
{
  js_Property *garbage = &sentinel;
  tree = unlinkproperty(tree, name, &garbage);
  if (garbage != &sentinel)
    freeproperty(J, obj, garbage);
  return tree;
}

js_Object *jsV_newobject(js_State *J, enum js_Class type, js_Object *prototype)
{
  js_Object *obj = js_malloc(J, sizeof *obj);
  memset(obj, 0, sizeof *obj);
  obj->gcmark = 0;
  obj->gcnext = J->gcobj;
  J->gcobj = obj;
  ++J->gccounter;

  obj->type = type;
  obj->properties = &sentinel;
  obj->prototype = prototype;
  obj->extensible = 1;
  return obj;
}

js_Property *jsV_getownproperty(js_State *J, js_Object *obj, const char *name)
{
  return lookup(obj->properties, name);
}

js_Property *jsV_getpropertyx(js_State *J, js_Object *obj, const char *name, int *own)
{
  *own = 1;
  do {
    js_Property *ref = lookup(obj->properties, name);
    if (ref)
      return ref;
    obj = obj->prototype;
    *own = 0;
  } while (obj);
  return NULL;
}

js_Property *jsV_getproperty(js_State *J, js_Object *obj, const char *name)
{
  do {
    js_Property *ref = lookup(obj->properties, name);
    if (ref)
      return ref;
    obj = obj->prototype;
  } while (obj);
  return NULL;
}

static js_Property *jsV_getenumproperty(js_State *J, js_Object *obj, const char *name)
{
  do {
    js_Property *ref = lookup(obj->properties, name);
    if (ref && !(ref->atts & JS_DONTENUM))
      return ref;
    obj = obj->prototype;
  } while (obj);
  return NULL;
}

js_Property *jsV_setproperty(js_State *J, js_Object *obj, const char *name)
{
  js_Property *result;

  if (!obj->extensible) {
    result = lookup(obj->properties, name);
    if (J->strict && !result)
      js_typeerror(J, "object is non-extensible");
    return result;
  }

  obj->properties = insert(J, obj, obj->properties, name, &result);

  return result;
}

void jsV_delproperty(js_State *J, js_Object *obj, const char *name)
{
  obj->properties = deleteproperty(J, obj, obj->properties, name);
}

/* Flatten hierarchy of enumerable properties into an iterator object */

static js_Iterator *itnewnode(js_State *J, const char *name, js_Iterator *next) {
  int n = strlen(name) + 1;
  js_Iterator *node = js_malloc(J, offsetof(js_Iterator, name) + n);
  node->next = next;
  memcpy(node->name, name, n);
  return node;
}

static js_Iterator *itwalk(js_State *J, js_Iterator *iter, js_Property *prop, js_Object *seen)
{
  if (prop->right != &sentinel)
    iter = itwalk(J, iter, prop->right, seen);
  if (!(prop->atts & JS_DONTENUM)) {
    if (!seen || !jsV_getenumproperty(J, seen, prop->name)) {
      iter = itnewnode(J, prop->name, iter);
    }
  }
  if (prop->left != &sentinel)
    iter = itwalk(J, iter, prop->left, seen);
  return iter;
}

static js_Iterator *itflatten(js_State *J, js_Object *obj)
{
  js_Iterator *iter = NULL;
  if (obj->prototype)
    iter = itflatten(J, obj->prototype);
  if (obj->properties != &sentinel)
    iter = itwalk(J, iter, obj->properties, obj->prototype);
  return iter;
}

js_Object *jsV_newiterator(js_State *J, js_Object *obj, int own)
{
  js_Object *io = jsV_newobject(J, JS_CITERATOR, NULL);
  io->u.iter.target = obj;
  io->u.iter.i = 0;
  io->u.iter.n = 0;
  if (own) {
    io->u.iter.head = NULL;
    if (obj->properties != &sentinel)
      io->u.iter.head = itwalk(J, io->u.iter.head, obj->properties, NULL);
  } else {
    io->u.iter.head = itflatten(J, obj);
  }
  io->u.iter.current = io->u.iter.head;

  if (obj->type == JS_CSTRING)
    io->u.iter.n = obj->u.s.length;

  if (obj->type == JS_CARRAY && obj->u.a.simple)
    io->u.iter.n = obj->u.a.flat_length;

  return io;
}

const char *jsV_nextiterator(js_State *J, js_Object *io)
{
  if (io->type != JS_CITERATOR)
    js_typeerror(J, "not an iterator");
  if (io->u.iter.i < io->u.iter.n) {
    js_itoa(J->scratch, io->u.iter.i);
    io->u.iter.i++;
    return J->scratch;
  }
  while (io->u.iter.current) {
    const char *name = io->u.iter.current->name;
    io->u.iter.current = io->u.iter.current->next;
    if (jsV_getproperty(J, io->u.iter.target, name))
      return name;
  }
  return NULL;
}

/* Walk all the properties and delete them one by one for arrays */

void jsV_resizearray(js_State *J, js_Object *obj, int newlen)
{
  char buf[32];
  const char *s;
  int k;
  assert(!obj->u.a.simple);
  if (newlen < obj->u.a.length) {
    if (obj->u.a.length > obj->count * 2) {
      js_Object *it = jsV_newiterator(J, obj, 1);
      while ((s = jsV_nextiterator(J, it))) {
        k = jsV_numbertointeger(jsV_stringtonumber(J, s));
        if (k >= newlen && !strcmp(s, jsV_numbertostring(J, buf, k)))
          jsV_delproperty(J, obj, s);
      }
    } else {
      for (k = newlen; k < obj->u.a.length; ++k) {
        jsV_delproperty(J, obj, js_itoa(buf, k));
      }
    }
  }
  obj->u.a.length = newlen;
}

Coverage Report

Created: 2024-05-20 06:23

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	}