1 // Copyright 2019 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 use super::{Builder, Pushable, Value, VectorBuilder};
16
17 /// Builds a Flexbuffer map, returned by a [Builder](struct.Builder.html).
18 ///
19 /// ## Side effect when dropped:
20 /// When this is dropped, or `end_map` is called, the map is
21 /// commited to the buffer. If this map is the root of the flexbuffer, then the
22 /// root is written and the flexbuffer is complete.
23 /// ## Panics:
24 /// - Duplicate keys will result in a panic in both debug and release mode.
25 /// - Keys with internal nulls results in a panic in debug mode and result in silent truncaction
26 /// in release mode.
27 pub struct MapBuilder<'a> {
28 pub(super) builder: &'a mut Builder,
29 // If the root is this map then start == None. Otherwise start is the
30 // number of values in the 'values stack' before adding this map.
31 pub(super) start: Option<usize>,
32 }
33 impl<'a> MapBuilder<'a> {
34 /// Push `p` onto this map with key `key`.
35 /// This will panic (in debug mode) if `key` contains internal nulls.
36 #[inline]
push<P: Pushable>(&mut self, key: &str, p: P)37 pub fn push<P: Pushable>(&mut self, key: &str, p: P) {
38 self.builder.push_key(key);
39 self.builder.push(p);
40 }
41 /// Starts a nested vector that will be pushed onto this map
42 /// with key `key` when it is dropped.
43 ///
44 /// This will panic (in debug mode) if `key` contains internal nulls.
45 #[inline]
start_vector(&mut self, key: &str) -> VectorBuilder46 pub fn start_vector(&mut self, key: &str) -> VectorBuilder {
47 // Push the key that refers to this nested vector.
48 self.builder.push_key(key);
49 // Nested vector.
50 let start = Some(self.builder.values.len());
51 VectorBuilder {
52 builder: &mut self.builder,
53 start,
54 }
55 }
56 /// Starts a nested map which that will be pushed onto this map
57 /// with key `key` when it is dropped.
58 ///
59 /// This will panic (in debug mode) if `key` contains internal nulls.
60 #[inline]
start_map(&mut self, key: &str) -> MapBuilder61 pub fn start_map(&mut self, key: &str) -> MapBuilder {
62 // Push the key that refers to this nested vector.
63 self.builder.push_key(key);
64 // Nested map.
65 let start = Some(self.builder.values.len());
66 MapBuilder {
67 builder: &mut self.builder,
68 start,
69 }
70 }
71 /// `end_map` sorts the map by key and writes it to the buffer. This happens anyway
72 /// when the map builder is dropped.
73 #[inline]
end_map(self)74 pub fn end_map(self) {}
75 }
76 impl<'a> Drop for MapBuilder<'a> {
77 #[inline]
drop(&mut self)78 fn drop(&mut self) {
79 self.builder.end_map_or_vector(true, self.start);
80 }
81 }
82
83 // Read known keys / strings as iterators over bytes -- skipping utf8 validation and strlen.
get_key(buffer: &[u8], address: usize) -> impl Iterator<Item = &u8>84 pub(super) fn get_key(buffer: &[u8], address: usize) -> impl Iterator<Item = &u8> {
85 buffer[address..].iter().take_while(|&&b| b != b'\0')
86 }
87
88 // `values` is assumed to be of the format [key1, value1, ..., keyN, valueN].
89 // The keys refer to cstrings in `buffer`. When this function returns,
90 // `values` is sorted in place by key.
sort_map_by_keys(values: &mut [Value], buffer: &[u8])91 pub(super) fn sort_map_by_keys(values: &mut [Value], buffer: &[u8]) {
92 debug_assert_eq!(values.len() % 2, 0);
93 debug_assert!(values.iter().step_by(2).all(Value::is_key));
94 let raw_pairs = values.as_mut_ptr() as *mut [Value; 2];
95 let pairs_len = values.len() / 2;
96 // Unsafe code needed to treat the slice as key-value pairs when sorting in place. This is
97 // preferred over custom sorting or adding another dependency. By construction, this part
98 // of the values stack must be alternating (key, value) pairs. The public API must not be
99 // able to trigger the above debug_assets that protect this unsafe usage.
100 let pairs: &mut [[Value; 2]] = unsafe { std::slice::from_raw_parts_mut(raw_pairs, pairs_len) };
101 #[rustfmt::skip]
102 pairs.sort_unstable_by(|[key1, _], [key2, _]| {
103 if let Value::Key(a1) = *key1 {
104 if let Value::Key(a2) = *key2 {
105 let s1 = get_key(buffer, a1);
106 let s2 = get_key(buffer, a2);
107 let ord = s1.cmp(s2);
108 if ord == std::cmp::Ordering::Equal {
109 let dup: String = get_key(buffer, a1).map(|&b| b as char).collect();
110 panic!("Duplicated key in map {:?}", dup);
111 }
112 return ord;
113 }
114 }
115 unreachable!();
116 });
117 }
118