ref: 46745c5e5cf56cc496fe35609ad50d76f9c57235
parent: abb9afd2d01c17dc1b3b94835a56f3110e1974de
author: Matthew Flatt <mflatt@racket-lang.org>
date: Sat Jul 23 12:47:03 CDT 2022
Zuo: sort hash keys Printing in a sorted order is helpful to make things more deterministic independent of symbol inputs. Making `hash-keys` produce a sorted list generalizes that determinism.
--- a/build.zuo
+++ b/build.zuo
@@ -47,7 +47,10 @@
(target (at-dir (add-exe name))
(lambda (path token)
(rule (list image_zuo.c
- (input-data-target 'config config)
+ (input-data-target 'config (cons
+ lib-path
+ (map (lambda (key) (hash-ref config key))
+ '(CC CPPFLAGS CFLAGS LDFLAGS LIBS))))
(quote-module-path))
(lambda ()
(define l (split-path path))
--- a/tests/hash.zuo
+++ b/tests/hash.zuo
@@ -35,9 +35,7 @@
(check (hash-keys (hash)) '())
(check (hash-keys (hash 'a 1)) '(a))
-(check (let ([keys (hash-keys (hash 'a 1 'b 2))])
- (or (equal? keys '(a b))
- (equal? keys '(b a)))))
+(check (hash-keys (hash 'a 1 'b 2)) '(a b)) ; always in order
(check (length (hash-keys (hash 'a 1 'b 2 'c 3))) 3)
(check (length (hash-keys (hash 'a 1 'b 2 'a 3))) 2)
(check-arg-fail (hash-keys 0) "not a hash table")
@@ -50,3 +48,7 @@
(check (hash-keys-subset? (hash 'a 1 'b 2) (hash 'b 1)) #f)
(check-arg-fail (hash-keys-subset? 0 (hash)) "not a hash table")
(check-arg-fail (hash-keys-subset? (hash) 0) "not a hash table")
+
+;; print sorts keys alphabetically:
+(check (~a (hash 'a 1 'b 2)) "#hash((a . 1) (b . 2))")
+(check (~a (hash 'b 2 'a 1)) "#hash((a . 1) (b . 2))")
--- a/zuo-doc/lang-zuo.scrbl
+++ b/zuo-doc/lang-zuo.scrbl
@@ -538,10 +538,20 @@
Analogous to @realracket*[hash? hash hash-ref hash-set hash-remove
hash-keys hash-count hash-keys-subset?] from @racketmodname[racket].
-Besides being constrained to symbol keys, there is one additional
-difference: the third argument to @racket[hash-ref], when supplied,
-is always used as a value to return if a key is missing, as
-opposed to a failure thunk.}
+
+Besides being constrained to symbol keys, there are two additional
+differences:
+
+@itemlist[
+
+ @item{the third argument to @racket[hash-ref], when supplied, is+ always used as a value to return if a key is missing, as
+ opposed to a failure thunk; and}
+
+ @item{the @racket[hash-keys] function returns interned keys sorted+ alphabetically.}
+
+]}
@section{Procedures}--- a/zuo.c
+++ b/zuo.c
@@ -1299,6 +1299,59 @@
}
/*======================================================================*/
+/* symbol-list sorting */
+/*======================================================================*/
+
+/* merge sort used to make hash printing deterministic */
+static zuo_t *zuo_symbol_list_sort(zuo_t *l_in) {+ zuo_t *l, *left, *right, *first, *last;
+ zuo_uint_t len = 0, i;
+
+ for (l = l_in, len = 0; l != z.o_null; l = _zuo_cdr(l))
+ len++;
+
+ if (len < 2)
+ return l_in;
+
+ left = z.o_null;
+ for (l = l_in, i = len >> 1; i > 0; l = _zuo_cdr(l), i--)
+ left = zuo_cons(_zuo_car(l), left);
+ right = l;
+
+ left = zuo_symbol_list_sort(left);
+ right = zuo_symbol_list_sort(right);
+
+ first = last = z.o_null;
+ while ((left != z.o_null) && (right != z.o_null)) {+ zuo_t *p;
+
+ if (strcmp(ZUO_STRING_PTR(((zuo_symbol_t *)_zuo_car(left))->str),
+ ZUO_STRING_PTR(((zuo_symbol_t *)_zuo_car(right))->str))
+ < 1) {+ p = zuo_cons(_zuo_car(left), z.o_null);
+ left = _zuo_cdr(left);
+ } else {+ p = zuo_cons(_zuo_car(right), z.o_null);
+ right = _zuo_cdr(right);
+ }
+
+ if (first == z.o_null)
+ first = p;
+ else
+ ((zuo_pair_t *)last)->cdr = p;
+ last = p;
+ }
+
+ ((zuo_pair_t *)last)->cdr = ((left != z.o_null) ? left : right);
+
+ return first;
+}
+
+static zuo_t *zuo_trie_sorted_keys(zuo_t *trie_in, zuo_t *accum) {+ return zuo_symbol_list_sort(zuo_trie_keys(trie_in, accum));
+}
+
+/*======================================================================*/
/* terminal support */
/*======================================================================*/
@@ -1571,7 +1624,7 @@
out_string(out, "opaque");
out_string(out, ">");
} else if (obj->tag == zuo_trie_node_tag) {- zuo_t *keys = zuo_trie_keys(obj, z.o_null);
+ zuo_t *keys = zuo_trie_sorted_keys(obj, z.o_null);
if (mode == zuo_print_mode) {out_string(out, "(hash");
if (keys != z.o_null)
@@ -2587,7 +2640,7 @@
static zuo_t *zuo_hash_keys(zuo_t *ht) { check_hash("hash-keys", ht);- return zuo_trie_keys(ht, z.o_null);
+ return zuo_trie_sorted_keys(ht, z.o_null);
}
static zuo_t *zuo_hash_keys_subset_p(zuo_t *ht, zuo_t *ht2) {