1 #include <string.h>
2 #include <stdlib.h>
3 #include <assert.h>
4 #include "jv_alloc.h"
5 
parse_slice(jv j,jv slice,int * pstart,int * pend)6 static int parse_slice(jv j, jv slice, int* pstart, int* pend) {
7   // Array slices
8   jv start_jv = jv_object_get(jv_copy(slice), jv_string("start"));
9   jv end_jv = jv_object_get(slice, jv_string("end"));
10   if (jv_get_kind(start_jv) == JV_KIND_NULL) {
11     jv_free(start_jv);
12     start_jv = jv_number(0);
13   }
14   int len;
15   if (jv_get_kind(j) == JV_KIND_ARRAY) {
16     len = jv_array_length(j);
17   } else if (jv_get_kind(j) == JV_KIND_STRING) {
18     len = jv_string_length_codepoints(j);
19   } else {
20     jv_free(j);
21     return 0;
22   }
23   if (jv_get_kind(end_jv) == JV_KIND_NULL) {
24     jv_free(end_jv);
25     end_jv = jv_number(len);
26   }
27   if (jv_get_kind(start_jv) != JV_KIND_NUMBER ||
28       jv_get_kind(end_jv) != JV_KIND_NUMBER) {
29     jv_free(start_jv);
30     jv_free(end_jv);
31     return 0;
32   } else {
33     double dstart = jv_number_value(start_jv);
34     double dend = jv_number_value(end_jv);
35     if (dstart < 0) dstart += len;
36     if (dend < 0) dend += len;
37     if (dstart < 0) dstart = 0;
38     if (dstart > len) dstart = len;
39 
40     int start = (int)dstart;
41     int end = (dend > len) ? len : (int)dend;
42     // Ends are exclusive but e.g. 1 < 1.5 so :1.5 should be :2 not :1
43     if(end < dend) end += 1;
44 
45     if (end > len) end = len;
46     if (end < start) end = start;
47     assert(0 <= start && start <= end && end <= len);
48     *pstart = start;
49     *pend = end;
50     return 1;
51   }
52 }
53 
jv_get(jv t,jv k)54 jv jv_get(jv t, jv k) {
55   jv v;
56   if (jv_get_kind(t) == JV_KIND_OBJECT && jv_get_kind(k) == JV_KIND_STRING) {
57     v = jv_object_get(t, k);
58     if (!jv_is_valid(v)) {
59       jv_free(v);
60       v = jv_null();
61     }
62   } else if (jv_get_kind(t) == JV_KIND_ARRAY && jv_get_kind(k) == JV_KIND_NUMBER) {
63     if(jv_is_integer(k)){
64       int idx = (int)jv_number_value(k);
65       if (idx < 0)
66         idx += jv_array_length(jv_copy(t));
67       v = jv_array_get(t, idx);
68       if (!jv_is_valid(v)) {
69         jv_free(v);
70         v = jv_null();
71       }
72     } else {
73       jv_free(t);
74       jv_free(k);
75       v = jv_null();
76     }
77   } else if (jv_get_kind(t) == JV_KIND_ARRAY && jv_get_kind(k) == JV_KIND_OBJECT) {
78     int start, end;
79     if (parse_slice(jv_copy(t), k, &start, &end)) {
80       v = jv_array_slice(t, start, end);
81     } else {
82       jv_free(t);
83       v = jv_invalid_with_msg(jv_string_fmt("Start and end indices of an array slice must be numbers"));
84     }
85   } else if (jv_get_kind(t) == JV_KIND_STRING && jv_get_kind(k) == JV_KIND_OBJECT) {
86     int start, end;
87     if (parse_slice(jv_copy(t), k, &start, &end)) {
88       v = jv_string_slice(t, start, end);
89     } else {
90       v = jv_invalid_with_msg(jv_string_fmt("Start and end indices of an string slice must be numbers"));
91       jv_free(t);
92     }
93   } else if (jv_get_kind(t) == JV_KIND_ARRAY && jv_get_kind(k) == JV_KIND_ARRAY) {
94     v = jv_array_indexes(t, k);
95   } else if (jv_get_kind(t) == JV_KIND_NULL &&
96              (jv_get_kind(k) == JV_KIND_STRING ||
97               jv_get_kind(k) == JV_KIND_NUMBER ||
98               jv_get_kind(k) == JV_KIND_OBJECT)) {
99     jv_free(t);
100     jv_free(k);
101     v = jv_null();
102   } else {
103     /*
104      * If k is a short string it's probably from a jq .foo expression or
105      * similar, in which case putting it in the invalid msg may help the
106      * user.  The length 30 is arbitrary.
107      */
108     if (jv_get_kind(k) == JV_KIND_STRING && jv_string_length_bytes(jv_copy(k)) < 30) {
109       v = jv_invalid_with_msg(jv_string_fmt("Cannot index %s with string \"%s\"",
110                                             jv_kind_name(jv_get_kind(t)),
111                                             jv_string_value(k)));
112     } else {
113       v = jv_invalid_with_msg(jv_string_fmt("Cannot index %s with %s",
114                                             jv_kind_name(jv_get_kind(t)),
115                                             jv_kind_name(jv_get_kind(k))));
116     }
117     jv_free(t);
118     jv_free(k);
119   }
120   return v;
121 }
122 
jv_set(jv t,jv k,jv v)123 jv jv_set(jv t, jv k, jv v) {
124   if (!jv_is_valid(v)) {
125     jv_free(t);
126     jv_free(k);
127     return v;
128   }
129   int isnull = jv_get_kind(t) == JV_KIND_NULL;
130   if (jv_get_kind(k) == JV_KIND_STRING &&
131       (jv_get_kind(t) == JV_KIND_OBJECT || isnull)) {
132     if (isnull) t = jv_object();
133     t = jv_object_set(t, k, v);
134   } else if (jv_get_kind(k) == JV_KIND_NUMBER &&
135              (jv_get_kind(t) == JV_KIND_ARRAY || isnull)) {
136     if (isnull) t = jv_array();
137     t = jv_array_set(t, (int)jv_number_value(k), v);
138   } else if (jv_get_kind(k) == JV_KIND_OBJECT &&
139              (jv_get_kind(t) == JV_KIND_ARRAY || isnull)) {
140     if (isnull) t = jv_array();
141     int start, end;
142     if (parse_slice(jv_copy(t), k, &start, &end)) {
143       if (jv_get_kind(v) == JV_KIND_ARRAY) {
144         int array_len = jv_array_length(jv_copy(t));
145         assert(0 <= start && start <= end && end <= array_len);
146         int slice_len = end - start;
147         int insert_len = jv_array_length(jv_copy(v));
148         if (slice_len < insert_len) {
149           // array is growing
150           int shift = insert_len - slice_len;
151           for (int i = array_len - 1; i >= end; i--) {
152             t = jv_array_set(t, i + shift, jv_array_get(jv_copy(t), i));
153           }
154         } else if (slice_len > insert_len) {
155           // array is shrinking
156           int shift = slice_len - insert_len;
157           for (int i = end; i < array_len; i++) {
158             t = jv_array_set(t, i - shift, jv_array_get(jv_copy(t), i));
159           }
160           t = jv_array_slice(t, 0, array_len - shift);
161         }
162         for (int i=0; i < insert_len; i++) {
163           t = jv_array_set(t, start + i, jv_array_get(jv_copy(v), i));
164         }
165         jv_free(v);
166       } else {
167         jv_free(t);
168         jv_free(v);
169         t = jv_invalid_with_msg(jv_string_fmt("A slice of an array can only be assigned another array"));
170       }
171     } else {
172       jv_free(t);
173       jv_free(v);
174       t = jv_invalid_with_msg(jv_string_fmt("Start and end indices of an array slice must be numbers"));
175     }
176   } else {
177     jv err = jv_invalid_with_msg(jv_string_fmt("Cannot update field at %s index of %s",
178                                                jv_kind_name(jv_get_kind(k)),
179                                                jv_kind_name(jv_get_kind(t))));
180     jv_free(t);
181     jv_free(k);
182     jv_free(v);
183     t = err;
184   }
185   return t;
186 }
187 
jv_has(jv t,jv k)188 jv jv_has(jv t, jv k) {
189   assert(jv_is_valid(t));
190   assert(jv_is_valid(k));
191   jv ret;
192   if (jv_get_kind(t) == JV_KIND_NULL) {
193     jv_free(t);
194     jv_free(k);
195     ret = jv_false();
196   } else if (jv_get_kind(t) == JV_KIND_OBJECT &&
197              jv_get_kind(k) == JV_KIND_STRING) {
198     jv elem = jv_object_get(t, k);
199     ret = jv_bool(jv_is_valid(elem));
200     jv_free(elem);
201   } else if (jv_get_kind(t) == JV_KIND_ARRAY &&
202              jv_get_kind(k) == JV_KIND_NUMBER) {
203     jv elem = jv_array_get(t, (int)jv_number_value(k));
204     ret = jv_bool(jv_is_valid(elem));
205     jv_free(elem);
206   } else {
207     ret = jv_invalid_with_msg(jv_string_fmt("Cannot check whether %s has a %s key",
208                                             jv_kind_name(jv_get_kind(t)),
209                                             jv_kind_name(jv_get_kind(k))));
210     jv_free(t);
211     jv_free(k);
212   }
213   return ret;
214 }
215 
216 // assumes keys is a sorted array
jv_dels(jv t,jv keys)217 static jv jv_dels(jv t, jv keys) {
218   assert(jv_get_kind(keys) == JV_KIND_ARRAY);
219   assert(jv_is_valid(t));
220 
221   if (jv_get_kind(t) == JV_KIND_NULL || jv_array_length(jv_copy(keys)) == 0) {
222     // no change
223   } else if (jv_get_kind(t) == JV_KIND_ARRAY) {
224     // extract slices, they must be handled differently
225     jv neg_keys = jv_array();
226     jv nonneg_keys = jv_array();
227     jv new_array = jv_array();
228     jv starts = jv_array(), ends = jv_array();
229     jv_array_foreach(keys, i, key) {
230       if (jv_get_kind(key) == JV_KIND_NUMBER) {
231         if (jv_number_value(key) < 0) {
232           neg_keys = jv_array_append(neg_keys, key);
233         } else {
234           nonneg_keys = jv_array_append(nonneg_keys, key);
235         }
236       } else if (jv_get_kind(key) == JV_KIND_OBJECT) {
237         int start, end;
238         if (parse_slice(jv_copy(t), key, &start, &end)) {
239           starts = jv_array_append(starts, jv_number(start));
240           ends = jv_array_append(ends, jv_number(end));
241         } else {
242           jv_free(new_array);
243           new_array = jv_invalid_with_msg(jv_string_fmt("Start and end indices of an array slice must be numbers"));
244           goto arr_out;
245         }
246       } else {
247         jv_free(new_array);
248         new_array = jv_invalid_with_msg(jv_string_fmt("Cannot delete %s element of array",
249                                                       jv_kind_name(jv_get_kind(key))));
250         jv_free(key);
251         goto arr_out;
252       }
253     }
254 
255     int neg_idx = 0;
256     int nonneg_idx = 0;
257     int len = jv_array_length(jv_copy(t));
258     jv_array_foreach(t, i, elem) {
259       int del = 0;
260       while (neg_idx < jv_array_length(jv_copy(neg_keys))) {
261         int delidx = len + (int)jv_number_value(jv_array_get(jv_copy(neg_keys), neg_idx));
262         if (i == delidx) {
263           del = 1;
264         }
265         if (i < delidx) {
266           break;
267         }
268         neg_idx++;
269       }
270       while (nonneg_idx < jv_array_length(jv_copy(nonneg_keys))) {
271         int delidx = (int)jv_number_value(jv_array_get(jv_copy(nonneg_keys), nonneg_idx));
272         if (i == delidx) {
273           del = 1;
274         }
275         if (i < delidx) {
276           break;
277         }
278         nonneg_idx++;
279       }
280       for (int sidx=0; !del && sidx<jv_array_length(jv_copy(starts)); sidx++) {
281         if ((int)jv_number_value(jv_array_get(jv_copy(starts), sidx)) <= i &&
282             i < (int)jv_number_value(jv_array_get(jv_copy(ends), sidx))) {
283           del = 1;
284         }
285       }
286       if (!del)
287         new_array = jv_array_append(new_array, elem);
288       else
289         jv_free(elem);
290     }
291   arr_out:
292     jv_free(neg_keys);
293     jv_free(nonneg_keys);
294     jv_free(starts);
295     jv_free(ends);
296     jv_free(t);
297     t = new_array;
298   } else if (jv_get_kind(t) == JV_KIND_OBJECT) {
299     jv_array_foreach(keys, i, k) {
300       if (jv_get_kind(k) != JV_KIND_STRING) {
301         jv_free(t);
302         t = jv_invalid_with_msg(jv_string_fmt("Cannot delete %s field of object",
303                                               jv_kind_name(jv_get_kind(k))));
304         jv_free(k);
305         break;
306       }
307       t = jv_object_delete(t, k);
308     }
309   } else {
310     jv err = jv_invalid_with_msg(jv_string_fmt("Cannot delete fields from %s",
311                                                jv_kind_name(jv_get_kind(t))));
312     jv_free(t);
313     t = err;
314   }
315   jv_free(keys);
316   return t;
317 }
318 
jv_setpath(jv root,jv path,jv value)319 jv jv_setpath(jv root, jv path, jv value) {
320   if (jv_get_kind(path) != JV_KIND_ARRAY) {
321     jv_free(value);
322     jv_free(root);
323     jv_free(path);
324     return jv_invalid_with_msg(jv_string("Path must be specified as an array"));
325   }
326   if (!jv_is_valid(root)){
327     jv_free(value);
328     jv_free(path);
329     return root;
330   }
331   if (jv_array_length(jv_copy(path)) == 0) {
332     jv_free(path);
333     jv_free(root);
334     return value;
335   }
336   jv pathcurr = jv_array_get(jv_copy(path), 0);
337   jv pathrest = jv_array_slice(path, 1, jv_array_length(jv_copy(path)));
338   return jv_set(root, pathcurr,
339                 jv_setpath(jv_get(jv_copy(root), jv_copy(pathcurr)), pathrest, value));
340 }
341 
jv_getpath(jv root,jv path)342 jv jv_getpath(jv root, jv path) {
343   if (jv_get_kind(path) != JV_KIND_ARRAY) {
344     jv_free(root);
345     jv_free(path);
346     return jv_invalid_with_msg(jv_string("Path must be specified as an array"));
347   }
348   if (!jv_is_valid(root)) {
349     jv_free(path);
350     return root;
351   }
352   if (jv_array_length(jv_copy(path)) == 0) {
353     jv_free(path);
354     return root;
355   }
356   jv pathcurr = jv_array_get(jv_copy(path), 0);
357   jv pathrest = jv_array_slice(path, 1, jv_array_length(jv_copy(path)));
358   return jv_getpath(jv_get(root, pathcurr), pathrest);
359 }
360 
361 // assumes paths is a sorted array of arrays
delpaths_sorted(jv object,jv paths,int start)362 static jv delpaths_sorted(jv object, jv paths, int start) {
363   jv delkeys = jv_array();
364   for (int i=0; i<jv_array_length(jv_copy(paths));) {
365     int j = i;
366     assert(jv_array_length(jv_array_get(jv_copy(paths), i)) > start);
367     int delkey = jv_array_length(jv_array_get(jv_copy(paths), i)) == start + 1;
368     jv key = jv_array_get(jv_array_get(jv_copy(paths), i), start);
369     while (j < jv_array_length(jv_copy(paths)) &&
370            jv_equal(jv_copy(key), jv_array_get(jv_array_get(jv_copy(paths), j), start)))
371       j++;
372     // if i <= entry < j, then entry starts with key
373     if (delkey) {
374       // deleting this entire key, we don't care about any more specific deletions
375       delkeys = jv_array_append(delkeys, key);
376     } else {
377       // deleting certain sub-parts of this key
378       jv subobject = jv_get(jv_copy(object), jv_copy(key));
379       if (!jv_is_valid(subobject)) {
380         jv_free(key);
381         jv_free(object);
382         object = subobject;
383         break;
384       } else if (jv_get_kind(subobject) == JV_KIND_NULL) {
385         jv_free(key);
386         jv_free(subobject);
387       } else {
388         jv newsubobject = delpaths_sorted(subobject, jv_array_slice(jv_copy(paths), i, j), start+1);
389         if (!jv_is_valid(newsubobject)) {
390           jv_free(key);
391           jv_free(object);
392           object = newsubobject;
393           break;
394         }
395         object = jv_set(object, key, newsubobject);
396       }
397       if (!jv_is_valid(object)) break;
398     }
399     i = j;
400   }
401   jv_free(paths);
402   if (jv_is_valid(object))
403     object = jv_dels(object, delkeys);
404   else
405     jv_free(delkeys);
406   return object;
407 }
408 
jv_delpaths(jv object,jv paths)409 jv jv_delpaths(jv object, jv paths) {
410   if (jv_get_kind(paths) != JV_KIND_ARRAY) {
411     jv_free(object);
412     jv_free(paths);
413     return jv_invalid_with_msg(jv_string("Paths must be specified as an array"));
414   }
415   paths = jv_sort(paths, jv_copy(paths));
416   jv_array_foreach(paths, i, elem) {
417     if (jv_get_kind(elem) != JV_KIND_ARRAY) {
418       jv_free(object);
419       jv_free(paths);
420       jv err = jv_invalid_with_msg(jv_string_fmt("Path must be specified as array, not %s",
421                                                  jv_kind_name(jv_get_kind(elem))));
422       jv_free(elem);
423       return err;
424     }
425     jv_free(elem);
426   }
427   if (jv_array_length(jv_copy(paths)) == 0) {
428     // nothing is being deleted
429     jv_free(paths);
430     return object;
431   }
432   if (jv_array_length(jv_array_get(jv_copy(paths), 0)) == 0) {
433     // everything is being deleted
434     jv_free(paths);
435     jv_free(object);
436     return jv_null();
437   }
438   return delpaths_sorted(object, paths, 0);
439 }
440 
441 
string_cmp(const void * pa,const void * pb)442 static int string_cmp(const void* pa, const void* pb){
443   const jv* a = pa;
444   const jv* b = pb;
445   int lena = jv_string_length_bytes(jv_copy(*a));
446   int lenb = jv_string_length_bytes(jv_copy(*b));
447   int minlen = lena < lenb ? lena : lenb;
448   int r = memcmp(jv_string_value(*a), jv_string_value(*b), minlen);
449   if (r == 0) r = lena - lenb;
450   return r;
451 }
452 
jv_keys_unsorted(jv x)453 jv jv_keys_unsorted(jv x) {
454   if (jv_get_kind(x) != JV_KIND_OBJECT)
455     return jv_keys(x);
456   jv answer = jv_array_sized(jv_object_length(jv_copy(x)));
457   jv_object_foreach(x, key, value) {
458     answer = jv_array_append(answer, key);
459     jv_free(value);
460   }
461   jv_free(x);
462   return answer;
463 }
464 
jv_keys(jv x)465 jv jv_keys(jv x) {
466   if (jv_get_kind(x) == JV_KIND_OBJECT) {
467     int nkeys = jv_object_length(jv_copy(x));
468     jv* keys = jv_mem_calloc(sizeof(jv), nkeys);
469     int kidx = 0;
470     jv_object_foreach(x, key, value) {
471       keys[kidx++] = key;
472       jv_free(value);
473     }
474     qsort(keys, nkeys, sizeof(jv), string_cmp);
475     jv answer = jv_array_sized(nkeys);
476     for (int i = 0; i<nkeys; i++) {
477       answer = jv_array_append(answer, keys[i]);
478     }
479     jv_mem_free(keys);
480     jv_free(x);
481     return answer;
482   } else if (jv_get_kind(x) == JV_KIND_ARRAY) {
483     int n = jv_array_length(x);
484     jv answer = jv_array();
485     for (int i=0; i<n; i++){
486       answer = jv_array_set(answer, i, jv_number(i));
487     }
488     return answer;
489   } else {
490     assert(0 && "jv_keys passed something neither object nor array");
491     return jv_invalid();
492   }
493 }
494 
jv_cmp(jv a,jv b)495 int jv_cmp(jv a, jv b) {
496   if (jv_get_kind(a) != jv_get_kind(b)) {
497     int r = (int)jv_get_kind(a) - (int)jv_get_kind(b);
498     jv_free(a);
499     jv_free(b);
500     return r;
501   }
502   int r = 0;
503   switch (jv_get_kind(a)) {
504   default:
505     assert(0 && "invalid kind passed to jv_cmp");
506   case JV_KIND_NULL:
507   case JV_KIND_FALSE:
508   case JV_KIND_TRUE:
509     // there's only one of each of these values
510     r = 0;
511     break;
512 
513   case JV_KIND_NUMBER: {
514     double da = jv_number_value(a), db = jv_number_value(b);
515 
516     // handle NaN as though it were null
517     if (da != da) r = jv_cmp(jv_null(), jv_number(db));
518     else if (db != db) r = jv_cmp(jv_number(da), jv_null());
519     else if (da < db) r = -1;
520     else if (da == db) r = 0;
521     else r = 1;
522     break;
523   }
524 
525   case JV_KIND_STRING: {
526     r = string_cmp(&a, &b);
527     break;
528   }
529 
530   case JV_KIND_ARRAY: {
531     // Lexical ordering of arrays
532     int i = 0;
533     while (r == 0) {
534       int a_done = i >= jv_array_length(jv_copy(a));
535       int b_done = i >= jv_array_length(jv_copy(b));
536       if (a_done || b_done) {
537         r = b_done - a_done; //suddenly, logic
538         break;
539       }
540       jv xa = jv_array_get(jv_copy(a), i);
541       jv xb = jv_array_get(jv_copy(b), i);
542       r = jv_cmp(xa, xb);
543       i++;
544     }
545     break;
546   }
547 
548   case JV_KIND_OBJECT: {
549     jv keys_a = jv_keys(jv_copy(a));
550     jv keys_b = jv_keys(jv_copy(b));
551     r = jv_cmp(jv_copy(keys_a), keys_b);
552     if (r == 0) {
553       jv_array_foreach(keys_a, i, key) {
554         jv xa = jv_object_get(jv_copy(a), jv_copy(key));
555         jv xb = jv_object_get(jv_copy(b), key);
556         r = jv_cmp(xa, xb);
557         if (r) break;
558       }
559     }
560     jv_free(keys_a);
561     break;
562   }
563   }
564 
565   jv_free(a);
566   jv_free(b);
567   return r;
568 }
569 
570 
571 struct sort_entry {
572   jv object;
573   jv key;
574   int index;
575 };
576 
sort_cmp(const void * pa,const void * pb)577 static int sort_cmp(const void* pa, const void* pb) {
578   const struct sort_entry* a = pa;
579   const struct sort_entry* b = pb;
580   int r = jv_cmp(jv_copy(a->key), jv_copy(b->key));
581   // comparing by index if r == 0 makes the sort stable
582   return r ? r : (a->index - b->index);
583 }
584 
sort_items(jv objects,jv keys)585 static struct sort_entry* sort_items(jv objects, jv keys) {
586   assert(jv_get_kind(objects) == JV_KIND_ARRAY);
587   assert(jv_get_kind(keys) == JV_KIND_ARRAY);
588   assert(jv_array_length(jv_copy(objects)) == jv_array_length(jv_copy(keys)));
589   int n = jv_array_length(jv_copy(objects));
590   struct sort_entry* entries = jv_mem_calloc(sizeof(struct sort_entry), n);
591   for (int i=0; i<n; i++) {
592     entries[i].object = jv_array_get(jv_copy(objects), i);
593     entries[i].key = jv_array_get(jv_copy(keys), i);
594     entries[i].index = i;
595   }
596   jv_free(objects);
597   jv_free(keys);
598   qsort(entries, n, sizeof(struct sort_entry), sort_cmp);
599   return entries;
600 }
601 
jv_sort(jv objects,jv keys)602 jv jv_sort(jv objects, jv keys) {
603   assert(jv_get_kind(objects) == JV_KIND_ARRAY);
604   assert(jv_get_kind(keys) == JV_KIND_ARRAY);
605   assert(jv_array_length(jv_copy(objects)) == jv_array_length(jv_copy(keys)));
606   int n = jv_array_length(jv_copy(objects));
607   struct sort_entry* entries = sort_items(objects, keys);
608   jv ret = jv_array();
609   for (int i=0; i<n; i++) {
610     jv_free(entries[i].key);
611     ret = jv_array_set(ret, i, entries[i].object);
612   }
613   jv_mem_free(entries);
614   return ret;
615 }
616 
jv_group(jv objects,jv keys)617 jv jv_group(jv objects, jv keys) {
618   assert(jv_get_kind(objects) == JV_KIND_ARRAY);
619   assert(jv_get_kind(keys) == JV_KIND_ARRAY);
620   assert(jv_array_length(jv_copy(objects)) == jv_array_length(jv_copy(keys)));
621   int n = jv_array_length(jv_copy(objects));
622   struct sort_entry* entries = sort_items(objects, keys);
623   jv ret = jv_array();
624   if (n > 0) {
625     jv curr_key = entries[0].key;
626     jv group = jv_array_append(jv_array(), entries[0].object);
627     for (int i = 1; i < n; i++) {
628       if (jv_equal(jv_copy(curr_key), jv_copy(entries[i].key))) {
629         jv_free(entries[i].key);
630       } else {
631         jv_free(curr_key);
632         curr_key = entries[i].key;
633         ret = jv_array_append(ret, group);
634         group = jv_array();
635       }
636       group = jv_array_append(group, entries[i].object);
637     }
638     jv_free(curr_key);
639     ret = jv_array_append(ret, group);
640   }
641   jv_mem_free(entries);
642   return ret;
643 }
644