polyspec_crudui_validator/compose/
member_order.rs

1//! Specification member order (docs/spec/schema.md, "Member order").
2//!
3//! Every object inside a specification lists its members in JavaScript's
4//! own-property order: names that are array indexes (canonical decimal integers
5//! from 0 to 4294967294) first in ascending numeric order, then every other name
6//! in insertion order. Record data keeps its arrival order and is never passed
7//! through this module.
8
9use serde_json::{Map, Value};
10
11/// The largest array index (2^32 - 2).
12const MAX_ARRAY_INDEX: u64 = 4_294_967_294;
13
14/// The numeric value of a member name that is an array index: a canonical decimal
15/// integer from 0 to 4294967294 without a sign or leading zeros.
16fn array_index(name: &str) -> Option<u64> {
17    let bytes = name.as_bytes();
18    if bytes.is_empty()
19        || bytes.len() > 10
20        || !bytes.iter().all(u8::is_ascii_digit)
21        || (bytes.len() > 1 && bytes[0] == b'0')
22    {
23        return None;
24    }
25    // The checks above leave at most ten ASCII digits, which always fit a u64.
26    let index = name
27        .parse::<u64>()
28        .expect("ten ASCII digits always fit a u64");
29    (index <= MAX_ARRAY_INDEX).then_some(index)
30}
31
32/// A copy of a specification value with every object, at every depth, in
33/// specification member order. Arrays keep their element order.
34pub fn member_ordered(value: &Value) -> Value {
35    match value {
36        Value::Object(map) => Value::Object(member_ordered_map(map)),
37        Value::Array(items) => Value::Array(items.iter().map(member_ordered).collect()),
38        other => other.clone(),
39    }
40}
41
42/// A copy of a specification object with its members, and every nested object,
43/// in specification member order.
44pub fn member_ordered_map(map: &Map<String, Value>) -> Map<String, Value> {
45    let mut indexes: Vec<(u64, &String, &Value)> = Vec::new();
46    let mut names: Vec<(&String, &Value)> = Vec::new();
47    for (name, value) in map {
48        match array_index(name) {
49            Some(index) => indexes.push((index, name, value)),
50            None => names.push((name, value)),
51        }
52    }
53    indexes.sort_by_key(|(index, _, _)| *index);
54    let mut out = Map::with_capacity(map.len());
55    for (_, name, value) in indexes {
56        out.insert(name.clone(), member_ordered(value));
57    }
58    for (name, value) in names {
59        out.insert(name.clone(), member_ordered(value));
60    }
61    out
62}
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67    use serde_json::json;
68
69    fn keys(value: &Value) -> Vec<&str> {
70        value
71            .as_object()
72            .unwrap()
73            .keys()
74            .map(String::as_str)
75            .collect()
76    }
77
78    /// Build an object with members inserted in exactly the given order.
79    fn object(names: &[&str]) -> Value {
80        let mut map = Map::new();
81        for name in names {
82            map.insert((*name).to_string(), Value::Null);
83        }
84        Value::Object(map)
85    }
86
87    #[test]
88    fn array_indexes_come_first_in_numeric_order() {
89        let ordered = member_ordered(&object(&["b", "10", "a", "2", "0"]));
90        assert_eq!(keys(&ordered), vec!["0", "2", "10", "b", "a"]);
91    }
92
93    #[test]
94    fn index_boundaries_follow_the_canonical_form() {
95        let ordered = member_ordered(&object(&[
96            "z",
97            "4294967295",
98            "01",
99            "-1",
100            "4294967294",
101            "1.5",
102            "",
103            " 1",
104            "+1",
105            "0",
106            "99999999999",
107        ]));
108        assert_eq!(
109            keys(&ordered),
110            vec![
111                "0",
112                "4294967294",
113                "z",
114                "4294967295",
115                "01",
116                "-1",
117                "1.5",
118                "",
119                " 1",
120                "+1",
121                "99999999999"
122            ]
123        );
124    }
125
126    #[test]
127    fn nested_objects_and_array_elements_are_ordered() {
128        let mut inner = object(&["y", "3"]);
129        inner["y"] = object(&["q", "7"]);
130        let mut outer = Map::new();
131        outer.insert(
132            "list".into(),
133            Value::Array(vec![object(&["b", "1"]), json!(5)]),
134        );
135        outer.insert("5".into(), inner);
136        let ordered = member_ordered(&Value::Object(outer));
137        assert_eq!(keys(&ordered), vec!["5", "list"]);
138        assert_eq!(keys(&ordered["5"]), vec!["3", "y"]);
139        assert_eq!(keys(&ordered["5"]["y"]), vec!["7", "q"]);
140        assert_eq!(keys(&ordered["list"][0]), vec!["1", "b"]);
141        assert_eq!(ordered["list"][1], json!(5));
142    }
143
144    #[test]
145    fn the_input_is_left_untouched() {
146        let data = object(&["b", "10", "a"]);
147        let ordered = member_ordered(&data);
148        assert_eq!(keys(&ordered), vec!["10", "b", "a"]);
149        assert_eq!(keys(&data), vec!["b", "10", "a"]);
150    }
151}
polyspec_crudui_validator/compose/member_order.rs

polyspec_crudui_validator/compose/
member_order.rs
