Merge pull request #153 from jow-/lib-sort-object-support

lib: support object ordering in `uc_sort()`

5 files changed, 160 insertions, 15 deletions

diff --git a/README.md b/README.md
index 423a1d7..d0d21ca 100644
--- a/README.md
+++ b/README.md
@@ -916,16 +916,52 @@ array was empty or if a non-array argument was passed.
 
 Return the sine of x, where x is given in radians.
 
-#### 6.31. `sort(arr, fn)`
+#### 6.31. `sort(val, fn)`
 
-Sort the given array according to the given sort function. If no sort
-function is provided, a default ascending sort order is applied.
+Sort the given array or object according to the given comparison function.
+If no comparison function is provided, a default lexical sort order is
+applied.
+
+Values are sorted in-place, the given array of object value is modified
+by this function.
+
+Sorting of objects is performed by reordering the internal key sequence
+without modifying or rehashing the contained values themselves. Since
+ucode maintains insertion order of keys within object values, this is
+useful to sort object keys for output purposes.
+
+The comparison function is repeatedly invoked until the array values
+or object key sequence is fully sorted. It should return a numeric
+value less than, equal to or greater than zero when the first item
+is smaller, equal or larger than the second one respectively.
+
+When sorting array values, the comparison function is invoked with two
+array value arguments to compare against each other.
+
+When sorting object values, the comparison function is invoked with four
+arguments; two keys to compare to each other as well as their
+corresponding object values.
+
+Returns the given, ordered array or object value.
+
+Returns `null` if the given argument was neither an array nor object.
+
+Throws an exception if a non-callable custom comparison function was
+provided or if the comparison function triggered an exception.
 
 ```javascript
 sort([8, 1, 5, 9]) // [1, 5, 8, 9]
 sort(["Bean", "Orange", "Apple"], function(a, b) {
-    return length(a) < length(b);
+    return length(a) - length(b);
 }) // ["Bean", "Apple", "Orange"]
+
+sort({ qrx: 1, foo: 2, abc: 3 }) // { "abc": 3, "foo": 2, "qrx": 1 }
+sort({ a: 5, b: 3, c: 2, d: 4, e: 1 }, function(k1, k2, v1, v2) {
+	return v1 - v2;
+}) // { "e": 1, "c": 2, "b": 3, "d": 4, "a": 5 }
+sort({ "Bean": true, "Orange": true, "Apple": true }, function(k1, k2) {
+    return length(k1) - length(k2);
+}) // { "Bean": true, "Apple": true, "Orange": true }
 ```
 
 #### 6.32. `splice(arr, off, len, ...)`
diff --git a/include/ucode/types.h b/include/ucode/types.h
index 22fe9a9..9827db5 100644
--- a/include/ucode/types.h
+++ b/include/ucode/types.h
@@ -369,6 +369,7 @@ size_t ucv_array_length(uc_value_t *);
 uc_value_t *ucv_object_new(uc_vm_t *);
 uc_value_t *ucv_object_get(uc_value_t *, const char *, bool *);
 bool ucv_object_add(uc_value_t *, const char *, uc_value_t *);
+void ucv_object_sort(uc_value_t *, int (*)(const void *, const void *));
 bool ucv_object_delete(uc_value_t *, const char *);
 size_t ucv_object_length(uc_value_t *);
 
diff --git a/lib.c b/lib.c
index a0a1b9b..93ea022 100644
--- a/lib.c
+++ b/lib.c
@@ -404,11 +404,8 @@ uc_rindex(uc_vm_t *vm, size_t nargs)
 }
 
 static bool
-assert_mutable_array(uc_vm_t *vm, uc_value_t *val)
+assert_mutable(uc_vm_t *vm, uc_value_t *val)
 {
-	if (ucv_type(val) != UC_ARRAY)
-		return false;
-
 	if (ucv_is_constant(val)) {
 		uc_vm_raise_exception(vm, EXCEPTION_TYPE,
 		                      "%s value is immutable",
@@ -420,6 +417,15 @@ assert_mutable_array(uc_vm_t *vm, uc_value_t *val)
 	return true;
 }
 
+static bool
+assert_mutable_array(uc_vm_t *vm, uc_value_t *val)
+{
+	if (ucv_type(val) != UC_ARRAY)
+		return false;
+
+	return assert_mutable(vm, val);
+}
+
 static uc_value_t *
 uc_push(uc_vm_t *vm, size_t nargs)
 {
@@ -894,7 +900,7 @@ default_cmp(uc_value_t *v1, uc_value_t *v2)
 }
 
 static int
-sort_fn(const void *k1, const void *k2)
+array_sort_fn(const void *k1, const void *k2)
 {
 	uc_value_t *rv, *null = ucv_int64_new(0);
 	uc_value_t * const *v1 = k1;
@@ -928,21 +934,69 @@ sort_fn(const void *k1, const void *k2)
 	return res;
 }
 
+static int
+object_sort_fn(const void *k1, const void *k2)
+{
+	uc_value_t *rv, *null = ucv_int64_new(0);
+	struct lh_entry * const *e1 = k1;
+	struct lh_entry * const *e2 = k2;
+	int res;
+
+	if (!sort_ctx.fn)
+		return strcmp((char *)lh_entry_k(*e1), (char *)lh_entry_k(*e2));
+
+	if (sort_ctx.ex)
+		return 0;
+
+	uc_vm_ctx_push(sort_ctx.vm);
+	uc_vm_stack_push(sort_ctx.vm, ucv_get(sort_ctx.fn));
+	uc_vm_stack_push(sort_ctx.vm, ucv_string_new((char *)lh_entry_k(*e1)));
+	uc_vm_stack_push(sort_ctx.vm, ucv_string_new((char *)lh_entry_k(*e2)));
+	uc_vm_stack_push(sort_ctx.vm, ucv_get((uc_value_t *)lh_entry_v(*e1)));
+	uc_vm_stack_push(sort_ctx.vm, ucv_get((uc_value_t *)lh_entry_v(*e2)));
+
+	if (uc_vm_call(sort_ctx.vm, true, 4)) {
+		sort_ctx.ex = true;
+
+		return 0;
+	}
+
+	rv = uc_vm_stack_pop(sort_ctx.vm);
+
+	ucv_compare(0, rv, null, &res);
+
+	ucv_put(null);
+	ucv_put(rv);
+
+	return res;
+}
+
 static uc_value_t *
 uc_sort(uc_vm_t *vm, size_t nargs)
 {
-	uc_value_t *arr = uc_fn_arg(0);
+	uc_value_t *val = uc_fn_arg(0);
 	uc_value_t *fn = uc_fn_arg(1);
 
-	if (!assert_mutable_array(vm, arr))
+	if (!assert_mutable(vm, val))
 		return NULL;
 
 	sort_ctx.vm = vm;
 	sort_ctx.fn = fn;
 
-	ucv_array_sort(arr, sort_fn);
+	switch (ucv_type(val)) {
+	case UC_ARRAY:
+		ucv_array_sort(val, array_sort_fn);
+		break;
+
+	case UC_OBJECT:
+		ucv_object_sort(val, object_sort_fn);
+		break;
+
+	default:
+		return NULL;
+	}
 
-	return sort_ctx.ex ? NULL : ucv_get(arr);
+	return sort_ctx.ex ? NULL : ucv_get(val);
 }
 
 static uc_value_t *
diff --git a/tests/custom/03_stdlib/16_sort b/tests/custom/03_stdlib/16_sort
index ac4a0e1..14d0e12 100644
--- a/tests/custom/03_stdlib/16_sort
+++ b/tests/custom/03_stdlib/16_sort
@@ -40,7 +40,16 @@ Returns `null` if the given input array value is not an array.
 				return 1;
 
 			return 0;
-		})
+		}),
+
+		// default lexical object key sort
+		sort({ qrx: 1, foo: 2, abc: 3 }),
+
+		// object sort with custom callback (by value)
+		sort({ a: 5, b: 3, c: 2, d: 4, e: 1 }, (k1, k2, v1, v2) => v1 - v2),
+
+		// object sort with custom callback (by key length)
+		sort({ "Bean": true, "Orange": true, "Apple": true }, (k1, k2) => length(k1) - length(k2))
 	]), "\n");
 %}
 -- End --
@@ -51,6 +60,9 @@ Returns `null` if the given input array value is not an array.
 [ 1, "2b", false, null, true ]
 [ "pear", "apple", "banana", "grapefruit" ]
 [ 1, 2, 4, 9, "a", "b", "q", "x" ]
+{ "abc": 3, "foo": 2, "qrx": 1 }
+{ "e": 1, "c": 2, "b": 3, "d": 4, "a": 5 }
+{ "Bean": true, "Apple": true, "Orange": true }
 -- End --
 
 
@@ -73,7 +85,7 @@ In line 2, byte 34:
 -- End --
 
 
-Supplying an invalid array will yield `null`.
+Supplying a non-array, non-object value will yield `null`.
 
 -- Testcase --
 {%
diff --git a/types.c b/types.c
index 7bb67a6..5758f74 100644
--- a/types.c
+++ b/types.c
@@ -956,6 +956,48 @@ ucv_object_add(uc_value_t *uv, const char *key, uc_value_t *val)
 	return true;
 }
 
+void
+ucv_object_sort(uc_value_t *uv, int (*cmp)(const void *, const void *))
+{
+	uc_object_t *object = (uc_object_t *)uv;
+	struct lh_table *t;
+	struct lh_entry *e;
+	size_t i;
+
+	struct {
+		struct lh_entry **entries;
+		size_t count;
+	} keys = { 0 };
+
+	if (ucv_type(uv) != UC_OBJECT || lh_table_length(object->table) <= 1)
+		return;
+
+	for (t = object->table, e = t->head; e; e = e->next)
+		uc_vector_push(&keys, e);
+
+	if (!keys.entries)
+		return;
+
+	qsort(keys.entries, keys.count, sizeof(keys.entries[0]), cmp);
+
+	for (i = 0; i < keys.count; i++) {
+		e = keys.entries[i];
+
+		if (i == 0) {
+			t->head = t->tail = e;
+			e->next = e->prev = NULL;
+		}
+		else {
+			t->tail->next = e;
+			e->prev = t->tail;
+			e->next = NULL;
+			t->tail = e;
+		}
+	}
+
+	uc_vector_clear(&keys);
+}
+
 bool
 ucv_object_delete(uc_value_t *uv, const char *key)
 {