shithub: libmujs

Download patch

ref: 2b4d05a575dae7837fda17b3ec8e240654f5a752
parent: f18f2c0c9965f4ccf80da9b00ff518bff3f81a32
author: Tor Andersson <[email protected]>
date: Thu Apr 20 19:06:03 EDT 2017

Revert 'Maintain order of property enumeration by keeping a linked list.'

Reduce memory use per property by not keeping the properties in two
parallel data structures. Maintaining the order of insertion is not
required by the spec, and is not a very useful feature.

--- a/jsgc.c
+++ b/jsgc.c
@@ -24,11 +24,9 @@
 
 static void jsG_freeproperty(js_State *J, js_Property *node)
 {
-	while (node) {
-		js_Property *next = node->next;
-		js_free(J, node);
-		node = next;
-	}
+	if (node->left->level) jsG_freeproperty(J, node->left);
+	if (node->right->level) jsG_freeproperty(J, node->right);
+	js_free(J, node);
 }
 
 static void jsG_freeiterator(js_State *J, js_Iterator *node)
@@ -42,8 +40,8 @@
 
 static void jsG_freeobject(js_State *J, js_Object *obj)
 {
-	if (obj->head)
-		jsG_freeproperty(J, obj->head);
+	if (obj->properties->level)
+		jsG_freeproperty(J, obj->properties);
 	if (obj->type == JS_CREGEXP) {
 		js_free(J, obj->u.r.source);
 		js_regfreex(J->alloc, J->actx, obj->u.r.prog);
@@ -76,24 +74,24 @@
 
 static void jsG_markproperty(js_State *J, int mark, js_Property *node)
 {
-	while (node) {
-		if (node->value.type == JS_TMEMSTR && node->value.u.memstr->gcmark != mark)
-			node->value.u.memstr->gcmark = mark;
-		if (node->value.type == JS_TOBJECT && node->value.u.object->gcmark != mark)
-			jsG_markobject(J, mark, node->value.u.object);
-		if (node->getter && node->getter->gcmark != mark)
-			jsG_markobject(J, mark, node->getter);
-		if (node->setter && node->setter->gcmark != mark)
-			jsG_markobject(J, mark, node->setter);
-		node = node->next;
-	}
+	if (node->left->level) jsG_markproperty(J, mark, node->left);
+	if (node->right->level) jsG_markproperty(J, mark, node->right);
+
+	if (node->value.type == JS_TMEMSTR && node->value.u.memstr->gcmark != mark)
+		node->value.u.memstr->gcmark = mark;
+	if (node->value.type == JS_TOBJECT && node->value.u.object->gcmark != mark)
+		jsG_markobject(J, mark, node->value.u.object);
+	if (node->getter && node->getter->gcmark != mark)
+		jsG_markobject(J, mark, node->getter);
+	if (node->setter && node->setter->gcmark != mark)
+		jsG_markobject(J, mark, node->setter);
 }
 
 static void jsG_markobject(js_State *J, int mark, js_Object *obj)
 {
 	obj->gcmark = mark;
-	if (obj->head)
-		jsG_markproperty(J, mark, obj->head);
+	if (obj->properties->level)
+		jsG_markproperty(J, mark, obj->properties);
 	if (obj->prototype && obj->prototype->gcmark != mark)
 		jsG_markobject(J, mark, obj->prototype);
 	if (obj->type == JS_CITERATOR) {
--- a/jsobject.c
+++ b/jsobject.c
@@ -137,10 +137,20 @@
 	}
 }
 
+static int O_getOwnPropertyNames_walk(js_State *J, js_Property *ref, int i)
+{
+	if (ref->left->level)
+		i = O_getOwnPropertyNames_walk(J, ref->left, i);
+	js_pushliteral(J, ref->name);
+	js_setindex(J, -2, i++);
+	if (ref->right->level)
+		i = O_getOwnPropertyNames_walk(J, ref->right, i);
+	return i;
+}
+
 static void O_getOwnPropertyNames(js_State *J)
 {
 	js_Object *obj;
-	js_Property *ref;
 	int k;
 	int i;
 
@@ -150,11 +160,10 @@
 
 	js_newarray(J);
 
-	i = 0;
-	for (ref = obj->head; ref; ref = ref->next) {
-		js_pushliteral(J, ref->name);
-		js_setindex(J, -2, i++);
-	}
+	if (obj->properties->level)
+		i = O_getOwnPropertyNames_walk(J, obj->properties, 0);
+	else
+		i = 0;
 
 	if (obj->type == JS_CARRAY) {
 		js_pushliteral(J, "length");
@@ -245,32 +254,51 @@
 	js_copy(J, 1);
 }
 
+static void O_defineProperties_walk(js_State *J, js_Property *ref)
+{
+	if (ref->left->level)
+		O_defineProperties_walk(J, ref->left);
+	if (!(ref->atts & JS_DONTENUM)) {
+		js_pushvalue(J, ref->value);
+		ToPropertyDescriptor(J, js_toobject(J, 1), ref->name, js_toobject(J, -1));
+		js_pop(J, 1);
+	}
+	if (ref->right->level)
+		O_defineProperties_walk(J, ref->right);
+}
+
 static void O_defineProperties(js_State *J)
 {
 	js_Object *props;
-	js_Property *ref;
 
 	if (!js_isobject(J, 1)) js_typeerror(J, "not an object");
 	if (!js_isobject(J, 2)) js_typeerror(J, "not an object");
 
 	props = js_toobject(J, 2);
-	for (ref = props->head; ref; ref = ref->next) {
-		if (!(ref->atts & JS_DONTENUM)) {
-			js_pushvalue(J, ref->value);
-			ToPropertyDescriptor(J, js_toobject(J, 1), ref->name, js_toobject(J, -1));
-			js_pop(J, 1);
-		}
-	}
+	if (props->properties->level)
+		O_defineProperties_walk(J, props->properties);
 
 	js_copy(J, 1);
 }
 
+static void O_create_walk(js_State *J, js_Object *obj, js_Property *ref)
+{
+	if (ref->left->level)
+		O_create_walk(J, obj, ref->left);
+	if (!(ref->atts & JS_DONTENUM)) {
+		if (ref->value.type != JS_TOBJECT)
+			js_typeerror(J, "not an object");
+		ToPropertyDescriptor(J, obj, ref->name, ref->value.u.object);
+	}
+	if (ref->right->level)
+		O_create_walk(J, obj, ref->right);
+}
+
 static void O_create(js_State *J)
 {
 	js_Object *obj;
 	js_Object *proto;
 	js_Object *props;
-	js_Property *ref;
 
 	if (js_isobject(J, 1))
 		proto = js_toobject(J, 1);
@@ -283,23 +311,31 @@
 	js_pushobject(J, obj);
 
 	if (js_isdefined(J, 2)) {
-		if (!js_isobject(J, 2)) js_typeerror(J, "not an object");
+		if (!js_isobject(J, 2))
+			js_typeerror(J, "not an object");
 		props = js_toobject(J, 2);
-		for (ref = props->head; ref; ref = ref->next) {
-			if (!(ref->atts & JS_DONTENUM)) {
-				if (ref->value.type != JS_TOBJECT) js_typeerror(J, "not an object");
-				ToPropertyDescriptor(J, obj, ref->name, ref->value.u.object);
-			}
-		}
+		if (props->properties->level)
+			O_create_walk(J, obj, props->properties);
 	}
 }
 
+static int O_keys_walk(js_State *J, js_Property *ref, int i)
+{
+	if (ref->left->level)
+		i = O_keys_walk(J, ref->left, i);
+	if (!(ref->atts & JS_DONTENUM)) {
+		js_pushliteral(J, ref->name);
+		js_setindex(J, -2, i++);
+	}
+	if (ref->right->level)
+		i = O_keys_walk(J, ref->right, i);
+	return i;
+}
+
 static void O_keys(js_State *J)
 {
 	js_Object *obj;
-	js_Property *ref;
-	int k;
-	int i;
+	int i, k;
 
 	if (!js_isobject(J, 1))
 		js_typeerror(J, "not an object");
@@ -307,13 +343,10 @@
 
 	js_newarray(J);
 
-	i = 0;
-	for (ref = obj->head; ref; ref = ref->next) {
-		if (!(ref->atts & JS_DONTENUM)) {
-			js_pushliteral(J, ref->name);
-			js_setindex(J, -2, i++);
-		}
-	}
+	if (obj->properties->level)
+		i = O_keys_walk(J, obj->properties, 0);
+	else
+		i = 0;
 
 	if (obj->type == JS_CSTRING) {
 		for (k = 0; k < obj->u.s.length; ++k) {
@@ -338,10 +371,18 @@
 	js_pushboolean(J, js_toobject(J, 1)->extensible);
 }
 
+static void O_seal_walk(js_State *J, js_Property *ref)
+{
+	if (ref->left->level)
+		O_seal_walk(J, ref->left);
+	ref->atts |= JS_DONTCONF;
+	if (ref->right->level)
+		O_seal_walk(J, ref->right);
+}
+
 static void O_seal(js_State *J)
 {
 	js_Object *obj;
-	js_Property *ref;
 
 	if (!js_isobject(J, 1))
 		js_typeerror(J, "not an object");
@@ -349,16 +390,28 @@
 	obj = js_toobject(J, 1);
 	obj->extensible = 0;
 
-	for (ref = obj->head; ref; ref = ref->next)
-		ref->atts |= JS_DONTCONF;
+	if (obj->properties->level)
+		O_seal_walk(J, obj->properties);
 
 	js_copy(J, 1);
 }
 
+static int O_isSealed_walk(js_State *J, js_Property *ref)
+{
+	if (ref->left->level)
+		if (!O_isSealed_walk(J, ref->left))
+			return 0;
+	if (!(ref->atts & JS_DONTCONF))
+		return 0;
+	if (ref->right->level)
+		if (!O_isSealed_walk(J, ref->right))
+			return 0;
+	return 1;
+}
+
 static void O_isSealed(js_State *J)
 {
 	js_Object *obj;
-	js_Property *ref;
 
 	if (!js_isobject(J, 1))
 		js_typeerror(J, "not an object");
@@ -369,20 +422,24 @@
 		return;
 	}
 
-	for (ref = obj->head; ref; ref = ref->next) {
-		if (!(ref->atts & JS_DONTCONF)) {
-			js_pushboolean(J, 0);
-			return;
-		}
-	}
+	if (obj->properties->level)
+		js_pushboolean(J, O_isSealed_walk(J, obj->properties));
+	else
+		js_pushboolean(J, 1);
+}
 
-	js_pushboolean(J, 1);
+static void O_freeze_walk(js_State *J, js_Property *ref)
+{
+	if (ref->left->level)
+		O_freeze_walk(J, ref->left);
+	ref->atts |= JS_READONLY | JS_DONTCONF;
+	if (ref->right->level)
+		O_freeze_walk(J, ref->right);
 }
 
 static void O_freeze(js_State *J)
 {
 	js_Object *obj;
-	js_Property *ref;
 
 	if (!js_isobject(J, 1))
 		js_typeerror(J, "not an object");
@@ -390,16 +447,28 @@
 	obj = js_toobject(J, 1);
 	obj->extensible = 0;
 
-	for (ref = obj->head; ref; ref = ref->next)
-		ref->atts |= JS_READONLY | JS_DONTCONF;
+	if (obj->properties->level)
+		O_freeze_walk(J, obj->properties);
 
 	js_copy(J, 1);
 }
 
+static int O_isFrozen_walk(js_State *J, js_Property *ref)
+{
+	if (ref->left->level)
+		if (!O_isFrozen_walk(J, ref->left))
+			return 0;
+	if (!(ref->atts & (JS_READONLY | JS_DONTCONF)))
+		return 0;
+	if (ref->right->level)
+		if (!O_isFrozen_walk(J, ref->right))
+			return 0;
+	return 1;
+}
+
 static void O_isFrozen(js_State *J)
 {
 	js_Object *obj;
-	js_Property *ref;
 
 	if (!js_isobject(J, 1))
 		js_typeerror(J, "not an object");
@@ -410,14 +479,10 @@
 		return;
 	}
 
-	for (ref = obj->head; ref; ref = ref->next) {
-		if (!(ref->atts & (JS_READONLY | JS_DONTCONF))) {
-			js_pushboolean(J, 0);
-			return;
-		}
-	}
-
-	js_pushboolean(J, 1);
+	if (obj->properties->level)
+		js_pushboolean(J, O_isFrozen_walk(J, obj->properties));
+	else
+		js_pushboolean(J, 1);
 }
 
 void jsB_initobject(js_State *J)
--- a/jsproperty.c
+++ b/jsproperty.c
@@ -21,7 +21,6 @@
 static js_Property sentinel = {
 	"",
 	&sentinel, &sentinel,
-	NULL, NULL,
 	0, 0,
 	{ {0}, {0}, JS_TUNDEFINED },
 	NULL, NULL
@@ -32,8 +31,6 @@
 	js_Property *node = js_malloc(J, sizeof *node);
 	node->name = js_intern(J, name);
 	node->left = node->right = &sentinel;
-	node->prevp = NULL;
-	node->next = NULL;
 	node->level = 1;
 	node->atts = 0;
 	node->value.type = JS_TUNDEFINED;
@@ -100,11 +97,6 @@
 
 static void freeproperty(js_State *J, js_Object *obj, js_Property *node)
 {
-	if (node->next)
-		node->next->prevp = node->prevp;
-	else
-		obj->tailp = node->prevp;
-	*node->prevp = node->next;
 	js_free(J, node);
 	--obj->count;
 }
@@ -165,8 +157,6 @@
 
 	obj->type = type;
 	obj->properties = &sentinel;
-	obj->head = NULL;
-	obj->tailp = &obj->head;
 	obj->prototype = prototype;
 	obj->extensible = 1;
 	return obj;
@@ -201,6 +191,17 @@
 	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;
@@ -213,11 +214,7 @@
 	}
 
 	obj->properties = insert(J, obj, obj->properties, name, &result);
-	if (!result->prevp) {
-		result->prevp = obj->tailp;
-		*obj->tailp = result;
-		obj->tailp = &result->next;
-	}
+
 	return result;
 }
 
@@ -228,69 +225,66 @@
 
 /* Flatten hierarchy of enumerable properties into an iterator object */
 
-static int itshadow(js_State *J, js_Object *top, js_Object *bot, const char *name)
+static js_Iterator *itwalk(js_State *J, js_Iterator *iter, js_Property *prop, js_Object *seen)
 {
-	int k;
-	while (top != bot) {
-		js_Property *prop = lookup(top->properties, name);
-		if (prop && !(prop->atts & JS_DONTENUM))
-			return 1;
-		if (top->type == JS_CSTRING)
-			if (js_isarrayindex(J, name, &k) && k < top->u.s.length)
-				return 1;
-		top = top->prototype;
+	if (prop->right != &sentinel)
+		iter = itwalk(J, iter, prop->right, seen);
+	if (!(prop->atts & JS_DONTENUM)) {
+		if (!seen || !jsV_getenumproperty(J, seen, prop->name)) {
+			js_Iterator *head = js_malloc(J, sizeof *head);
+			head->name = prop->name;
+			head->next = iter;
+			iter = head;
+		}
 	}
-	return 0;
+	if (prop->left != &sentinel)
+		iter = itwalk(J, iter, prop->left, seen);
+	return iter;
 }
 
-static void itwalk(js_State *J, js_Object *io, js_Object *top, int own)
+static js_Iterator *itflatten(js_State *J, js_Object *obj)
 {
-	js_Object *obj = top;
-	js_Iterator *tail = NULL;
+	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)
+{
 	char buf[32];
 	int k;
-
-#define ITADD(x) \
-	js_Iterator *node = js_malloc(J, sizeof *node); \
-	node->name = x; \
-	node->next = NULL; \
-	if (!tail) { \
-		io->u.iter.head = tail = node; \
-	} else { \
-		tail->next = node; \
-		tail = node; \
+	js_Object *io = jsV_newobject(J, JS_CITERATOR, NULL);
+	io->u.iter.target = obj;
+	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);
 	}
-
-	while (obj) {
-		js_Property *prop = obj->head;
-		while (prop) {
-			if (!(prop->atts & JS_DONTENUM) && !itshadow(J, top, obj, prop->name)) {
-				ITADD(prop->name);
-			}
-			prop = prop->next;
-		}
-
-		if (obj->type == JS_CSTRING) {
-			for (k = 0; k < obj->u.s.length; ++k) {
-				js_itoa(buf, k);
-				if (!itshadow(J, top, obj, buf)) {
-					ITADD(js_intern(J, buf));
+	if (obj->type == JS_CSTRING) {
+		js_Iterator *tail = io->u.iter.head;
+		if (tail)
+			while (tail->next)
+				tail = tail->next;
+		for (k = 0; k < obj->u.s.length; ++k) {
+			js_itoa(buf, k);
+			if (!jsV_getenumproperty(J, obj, buf)) {
+				js_Iterator *node = js_malloc(J, sizeof *node);
+				node->name = js_intern(J, js_itoa(buf, k));
+				node->next = NULL;
+				if (!tail)
+					io->u.iter.head = tail = node;
+				else {
+					tail->next = node;
+					tail = node;
 				}
 			}
 		}
-
-		if (own)
-			break;
-		obj = obj->prototype;
 	}
-}
-
-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.head = NULL;
-	itwalk(J, io, obj, own);
 	return io;
 }
 
--- a/jsvalue.h
+++ b/jsvalue.h
@@ -81,7 +81,6 @@
 	enum js_Class type;
 	int extensible;
 	js_Property *properties;
-	js_Property *head, **tailp; /* for enumeration */
 	int count; /* number of properties, for array sparseness check */
 	js_Object *prototype;
 	union {
@@ -126,7 +125,6 @@
 {
 	const char *name;
 	js_Property *left, *right;
-	js_Property *next, **prevp; /* for enumeration */
 	int level;
 	int atts;
 	js_Value value;