reallyme-codec-cbor 0.4.4

Canonical CBOR codec support for ReallyMe Codec.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
// SPDX-FileCopyrightText: 2026 ReallyMe Technologies Limited
//
// SPDX-License-Identifier: MIT OR Apache-2.0

//! Map-key uniqueness using a bounded index, independent of received key order.
//!
//! Keys are sorted with a bounded, fallible merge sort under a total preorder
//! whose ties include every pair that [`equivalent`] accepts. Equivalent keys
//! therefore end up adjacent, inside one tie run, and only runs are checked
//! with [`equivalent`]. Keys without descendant maps have an exact preorder and
//! need `O(n log n)` comparisons. Maps tie on entry count, so maps and compound
//! keys containing maps can share coarse ties. Their runs use pairwise semantic
//! comparisons and may exhaust work before the entry ceiling. Every traversal
//! and comparison charges the shared work budget.
//! Only key start offsets are stored; key bytes are never copied.

use core::cmp::Ordering;

use super::compare::{equivalent, next};
use super::error::{error, CborError, ErrorReason};
use super::limits::Budget;
use super::read_header::MajorType;
use super::receipt::Frame;
use super::scan::{add, tail};

/// Maps with at most this many keys are checked pairwise from inline storage,
/// so validating typical small maps performs no heap allocation.
const INLINE_KEYS: usize = 16;

/// Key start offsets for one map: inline for small maps, then a bounded heap
/// list. Offsets are not key material.
pub(super) struct KeyStarts {
    inline: [usize; INLINE_KEYS],
    len: usize,
    heap: Vec<usize>,
}

impl KeyStarts {
    /// Prepare empty storage. Heap storage grows only as keys are actually
    /// read, so a declared count never reserves memory ahead of the input.
    pub(super) const fn new() -> Self {
        Self {
            inline: [0; INLINE_KEYS],
            len: 0,
            heap: Vec::new(),
        }
    }

    pub(super) fn push(&mut self, start: usize) -> Result<(), CborError> {
        if self.heap.is_empty() {
            if let Some(slot) = self.inline.get_mut(self.len) {
                *slot = start;
                self.len = add(self.len, 1)?;
                return Ok(());
            }
            let inline = self
                .inline
                .get(..self.len)
                .ok_or(error(ErrorReason::ArithmeticOverflow))?;
            self.heap
                .try_reserve(
                    INLINE_KEYS
                        .checked_mul(2)
                        .ok_or(error(ErrorReason::ArithmeticOverflow))?,
                )
                .map_err(|_| error(ErrorReason::AllocationFailure))?;
            self.heap.extend_from_slice(inline);
        }
        self.heap
            .try_reserve(1)
            .map_err(|_| error(ErrorReason::AllocationFailure))?;
        self.heap.push(start);
        Ok(())
    }

    fn as_slice(&self) -> Result<&[usize], CborError> {
        if self.heap.is_empty() {
            self.inline
                .get(..self.len)
                .ok_or(error(ErrorReason::ArithmeticOverflow))
        } else {
            Ok(&self.heap)
        }
    }
}

/// Reject a map whose recorded keys contain two equivalent keys.
pub(super) fn check_unique(
    input: &[u8],
    keys: &KeyStarts,
    budget: &mut Budget,
) -> Result<(), CborError> {
    let starts = keys.as_slice()?;
    check_unique_by(
        starts.len(),
        budget,
        |first, second, budget| compare_at(input, starts, first, second, budget),
        |first, second, budget| {
            let left = frame_at(input, starts, first, budget)?;
            let right = frame_at(input, starts, second, budget)?;
            equivalent(&left, &right, budget, 0)
        },
    )
}

// The index traversal needs a preorder to group candidates and a separate
// equality test to resolve ties. Both comparisons charge the same budget.
fn check_unique_by(
    len: usize,
    budget: &mut Budget,
    mut compare: impl FnMut(usize, usize, &mut Budget) -> Result<Ordering, CborError>,
    mut equal: impl FnMut(usize, usize, &mut Budget) -> Result<bool, CborError>,
) -> Result<(), CborError> {
    if len < 2 {
        return Ok(());
    }
    if len <= INLINE_KEYS {
        let indices: [usize; INLINE_KEYS] = core::array::from_fn(|index| index);
        let run = indices
            .get(..len)
            .ok_or(error(ErrorReason::ArithmeticOverflow))?;
        return check_run(run, budget, &mut equal);
    }
    let mut order = try_indices(len)?;
    let mut scratch = try_indices(len)?;
    merge_sort(&mut order, &mut scratch, budget, &mut compare)?;
    check_sorted_runs(&order, budget, &mut compare, &mut equal)
}

fn check_sorted_runs(
    order: &[usize],
    budget: &mut Budget,
    compare: &mut impl FnMut(usize, usize, &mut Budget) -> Result<Ordering, CborError>,
    equal: &mut impl FnMut(usize, usize, &mut Budget) -> Result<bool, CborError>,
) -> Result<(), CborError> {
    let mut run_start = 0_usize;
    for index in 1..=order.len() {
        let previous_index = index
            .checked_sub(1)
            .ok_or(error(ErrorReason::ArithmeticOverflow))?;
        let tied = match (order.get(previous_index), order.get(index)) {
            (Some(&previous), Some(&current)) => {
                compare(previous, current, budget)? == Ordering::Equal
            }
            _ => false,
        };
        if !tied {
            let run = order
                .get(run_start..index)
                .ok_or(error(ErrorReason::ArithmeticOverflow))?;
            check_run(run, budget, equal)?;
            run_start = index;
        }
    }
    Ok(())
}

fn try_indices(len: usize) -> Result<Vec<usize>, CborError> {
    let mut indices = Vec::new();
    indices
        .try_reserve_exact(len)
        .map_err(|_| error(ErrorReason::AllocationFailure))?;
    indices.extend(0..len);
    Ok(indices)
}

fn check_run(
    run: &[usize],
    budget: &mut Budget,
    equal: &mut impl FnMut(usize, usize, &mut Budget) -> Result<bool, CborError>,
) -> Result<(), CborError> {
    for (position, &first) in run.iter().enumerate() {
        let rest = run
            .get(add(position, 1)?..)
            .ok_or(error(ErrorReason::ArithmeticOverflow))?;
        for &second in rest {
            if equal(first, second, budget)? {
                return Err(error(ErrorReason::DuplicateMapKey));
            }
        }
    }
    Ok(())
}

fn merge_sort(
    order: &mut [usize],
    scratch: &mut [usize],
    budget: &mut Budget,
    compare: &mut impl FnMut(usize, usize, &mut Budget) -> Result<Ordering, CborError>,
) -> Result<(), CborError> {
    let len = order.len();
    let mut width = 1_usize;
    while width < len {
        let mut start = 0_usize;
        while start < len {
            let middle = add(start, width)?.min(len);
            let end = add(middle, width)?.min(len);
            let left = order
                .get(start..middle)
                .ok_or(error(ErrorReason::ArithmeticOverflow))?;
            let right = order
                .get(middle..end)
                .ok_or(error(ErrorReason::ArithmeticOverflow))?;
            let output = scratch
                .get_mut(start..end)
                .ok_or(error(ErrorReason::ArithmeticOverflow))?;
            merge(left, right, output, budget, compare)?;
            start = end;
        }
        if order.len() != scratch.len() {
            return Err(error(ErrorReason::ArithmeticOverflow));
        }
        order.copy_from_slice(scratch);
        width = width
            .checked_mul(2)
            .ok_or(error(ErrorReason::ArithmeticOverflow))?;
    }
    Ok(())
}

fn merge(
    left: &[usize],
    right: &[usize],
    output: &mut [usize],
    budget: &mut Budget,
    compare: &mut impl FnMut(usize, usize, &mut Budget) -> Result<Ordering, CborError>,
) -> Result<(), CborError> {
    let mut left = left.iter().copied().peekable();
    let mut right = right.iter().copied().peekable();
    for slot in output.iter_mut() {
        let take_left = match (left.peek(), right.peek()) {
            (Some(&first), Some(&second)) => compare(first, second, budget)? != Ordering::Greater,
            (Some(_), None) => true,
            (None, Some(_)) => false,
            (None, None) => return Err(error(ErrorReason::ArithmeticOverflow)),
        };
        let next_index = if take_left { left.next() } else { right.next() };
        *slot = next_index.ok_or(error(ErrorReason::ArithmeticOverflow))?;
    }
    Ok(())
}

fn frame_at<'a>(
    input: &'a [u8],
    starts: &[usize],
    index: usize,
    budget: &mut Budget,
) -> Result<Frame<'a>, CborError> {
    let start = *starts
        .get(index)
        .ok_or(error(ErrorReason::ArithmeticOverflow))?;
    let mut offset = 0_usize;
    next(tail(input, start)?, &mut offset, budget)
}

fn compare_at(
    input: &[u8],
    starts: &[usize],
    first: usize,
    second: usize,
    budget: &mut Budget,
) -> Result<Ordering, CborError> {
    let left = frame_at(input, starts, first, budget)?;
    let right = frame_at(input, starts, second, budget)?;
    key_order(&left, &right, budget, 0)
}

const fn rank(major: MajorType) -> Result<u8, CborError> {
    match major {
        MajorType::Unsigned => Ok(0),
        MajorType::Negative => Ok(1),
        MajorType::Bytes => Ok(2),
        MajorType::Text => Ok(3),
        MajorType::Array => Ok(4),
        MajorType::Map => Ok(5),
        MajorType::Tag => Ok(6),
        MajorType::Simple => Ok(7),
        _ => Err(error(ErrorReason::UnsupportedPolicy)),
    }
}

fn key_order(
    left: &Frame<'_>,
    right: &Frame<'_>,
    budget: &mut Budget,
    depth: usize,
) -> Result<Ordering, CborError> {
    budget.charge(1)?;
    let major = left.header.major_type();
    match rank(major)?.cmp(&rank(right.header.major_type())?) {
        Ordering::Equal => {}
        different => return Ok(different),
    }
    match major {
        MajorType::Unsigned | MajorType::Negative => {
            Ok(left.header.argument().cmp(&right.header.argument()))
        }
        MajorType::Bytes | MajorType::Text => strings_order(left, right, budget),
        MajorType::Simple => Ok(simple_key(left)?.cmp(&simple_key(right)?)),
        MajorType::Tag => {
            match left.header.argument().cmp(&right.header.argument()) {
                Ordering::Equal => {}
                different => return Ok(different),
            }
            let depth = budget.enter(depth)?;
            let first = next(left.body, &mut 0, budget)?;
            let second = next(right.body, &mut 0, budget)?;
            key_order(&first, &second, budget, depth)
        }
        MajorType::Array => {
            let depth = budget.enter(depth)?;
            let (mut first, mut second) = (0_usize, 0_usize);
            loop {
                match (first < left.body.len(), second < right.body.len()) {
                    (true, true) => {
                        let x = next(left.body, &mut first, budget)?;
                        let y = next(right.body, &mut second, budget)?;
                        match key_order(&x, &y, budget, depth)? {
                            Ordering::Equal => {}
                            different => return Ok(different),
                        }
                    }
                    (false, false) => return Ok(Ordering::Equal),
                    (false, true) => return Ok(Ordering::Less),
                    (true, false) => return Ok(Ordering::Greater),
                }
            }
        }
        MajorType::Map => map_key_order_by(left.body, right.body, budget, next),
        _ => Err(error(ErrorReason::UnsupportedPolicy)),
    }
}

fn simple_key(frame: &Frame<'_>) -> Result<(u8, u8, u8, u64), CborError> {
    match frame.header.float()? {
        Some(value) => {
            let (class, bits) = value.equivalence_key();
            Ok((1, 0, class, bits))
        }
        None => Ok((
            0,
            frame
                .header
                .simple_value()?
                .ok_or(error(ErrorReason::WrongType))?,
            0,
            0,
        )),
    }
}

/// Count entries by walking the body, so definite and indefinite maps with
/// the same content tie.
fn map_key_order_by<'a, T>(
    left: &'a [u8],
    right: &'a [u8],
    budget: &mut Budget,
    mut read: impl FnMut(&'a [u8], &mut usize, &mut Budget) -> Result<T, CborError>,
) -> Result<Ordering, CborError> {
    Ok(entry_count_by(left, budget, &mut read)?.cmp(&entry_count_by(right, budget, &mut read)?))
}

fn entry_count_by<'a, T>(
    body: &'a [u8],
    budget: &mut Budget,
    read: &mut impl FnMut(&'a [u8], &mut usize, &mut Budget) -> Result<T, CborError>,
) -> Result<usize, CborError> {
    let mut offset = 0_usize;
    let mut count = 0_usize;
    while offset < body.len() {
        read(body, &mut offset, budget)?;
        read(body, &mut offset, budget)?;
        count = count
            .checked_add(1)
            .ok_or(error(ErrorReason::ArithmeticOverflow))?;
    }
    Ok(count)
}

// Lexicographic order over logical string contents, walking chunks so a
// chunked string ties with a definite string of the same contents.
fn strings_order(
    left: &Frame<'_>,
    right: &Frame<'_>,
    budget: &mut Budget,
) -> Result<Ordering, CborError> {
    let mut left = left.string_chunks()?;
    let mut right = right.string_chunks()?;
    let mut first: &[u8] = &[];
    let mut second: &[u8] = &[];
    loop {
        while first.is_empty() {
            match left.next() {
                Some(chunk) => {
                    budget.charge(1)?;
                    first = chunk?;
                }
                None => break,
            }
        }
        while second.is_empty() {
            match right.next() {
                Some(chunk) => {
                    budget.charge(1)?;
                    second = chunk?;
                }
                None => break,
            }
        }
        match (first.is_empty(), second.is_empty()) {
            (true, true) => return Ok(Ordering::Equal),
            (true, false) => return Ok(Ordering::Less),
            (false, true) => return Ok(Ordering::Greater),
            (false, false) => {
                let length = first.len().min(second.len());
                budget.charge(length)?;
                match first.get(..length).cmp(&second.get(..length)) {
                    Ordering::Equal => {}
                    different => return Ok(different),
                }
                first = tail(first, length)?;
                second = tail(second, length)?;
            }
        }
    }
}

#[cfg(kani)]
#[path = "unique_proof_tests.rs"]
mod proofs;