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
extern crate alloc;
use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;
use super::{DotSet, StationDots};
mod error;
mod pure;
mod runs;
pub use error::{HaveSetDecodeBudget, HaveSetDecodeError};
use pure::{HAVE_SET_WIRE_V1, PureDecodeError};
use runs::{maximal_run_count, maximal_runs};
// Crate-visible for the lifecycle frames' cut-embedding preflight (S284):
// a gap-free embedding is header plus one run-free station record per
// vector entry, and the preflight must speak this codec's own widths
// rather than re-derive them (the second-byte-oracle hazard the R-62
// preflight discipline names). The agreement is property-pinned in the
// lifecycle wire suite.
pub use pure::HAVE_SET_WIRE_HEADER_LEN;
pub const HAVE_SET_STATION_LEN: usize = 4 + 8 + 4;
const HAVE_SET_RUN_LEN: usize = 8 + 8;
/// Lifts the pure core's error onto the public error surface, variant for
/// variant (the core carries no `thiserror`, per the S94 subset record; the
/// public type keeps the derive and its `Display` text unchanged).
const fn lift(error: PureDecodeError) -> HaveSetDecodeError {
match error {
PureDecodeError::UnknownVersion(version) => HaveSetDecodeError::UnknownVersion(version),
PureDecodeError::UnexpectedLength { expected, found } => {
HaveSetDecodeError::UnexpectedLength { expected, found }
}
PureDecodeError::EmptyStation { station } => HaveSetDecodeError::EmptyStation { station },
PureDecodeError::NonAscendingStations { previous, found } => {
HaveSetDecodeError::NonAscendingStations { previous, found }
}
PureDecodeError::ZeroLengthRun { station } => HaveSetDecodeError::ZeroLengthRun { station },
PureDecodeError::NonMaximalRun { station, start } => {
HaveSetDecodeError::NonMaximalRun { station, start }
}
PureDecodeError::RunOverflow {
station,
start,
len,
} => HaveSetDecodeError::RunOverflow {
station,
start,
len,
},
PureDecodeError::RunTooLong {
station,
start,
len,
} => HaveSetDecodeError::RunTooLong {
station,
start,
len,
},
}
}
impl DotSet {
/// Exact byte length of [`to_bytes`](Self::to_bytes), computed without
/// allocating either the frame or its canonical exception runs.
///
/// Embedding protocols use this to enforce their outer byte budget before
/// asking the canonical encoder to allocate. The walk is
/// `O(stations + exceptions)` and saturation preserves totality if an
/// in-memory value could theoretically exceed `usize`.
#[must_use]
pub fn encoded_len(&self) -> usize {
self.stations
.values()
.fold(HAVE_SET_WIRE_HEADER_LEN, |length, slot| {
length
.saturating_add(HAVE_SET_STATION_LEN)
.saturating_add(maximal_run_count(&slot.above).saturating_mul(HAVE_SET_RUN_LEN))
})
}
/// Encodes this have-set as its canonical version-1 wire frame (PRD 0016): a
/// version byte, a `u32` big-endian station count, then that many station
/// records in strictly ascending `station_id` order (the map's own order).
/// Each record is `[station_id: u32][floor: u64][run_count: u32]` followed by
/// `run_count` runs `[start: u64][len: u64]`, where the runs are the station's
/// out-of-order exception set compressed as maximal runs of consecutive dots,
/// in strictly ascending order. All integers are big-endian. Infallible;
/// the frame is allocated once at its exact
/// [`encoded_len`](Self::encoded_len), plus one temporary run list per
/// station.
///
/// Equal have-sets encode to identical bytes, so the frame is a sound
/// content hash (the canonical bijection: [`from_bytes`](Self::from_bytes)
/// re-encodes every accepted frame byte for byte). Deliberately not a
/// causal sort key: a have-set is only partially ordered.
///
/// # Byte identity is a v1 contract, not an evolving format
///
/// Every value has exactly one encoding. A future need is a sibling
/// codec under a new version byte, never an in-place evolution of v1
/// (R-8; the `VersionVector` frame's discipline, PRD 0007). Polis
/// possession protocol v1 embeds these exact bytes since Polis S3
/// (`5d10141`), so a version change is coordinated with that protocol.
#[must_use]
pub fn to_bytes(&self) -> Vec<u8> {
// A canonical map holds at most one entry per `u32` station, so the count
// fits a `u32` for every have-set representable in memory; saturate rather
// than panic on the unreachable 2^32-station case, since `to_bytes` is
// infallible.
let station_count = u32::try_from(self.stations.len()).unwrap_or(u32::MAX);
let mut out = Vec::with_capacity(self.encoded_len());
out.push(HAVE_SET_WIRE_V1);
out.extend_from_slice(&station_count.to_be_bytes());
for (&station, slot) in &self.stations {
out.extend_from_slice(&station.to_be_bytes());
out.extend_from_slice(&slot.floor.to_be_bytes());
// The exception set as maximal runs of consecutive dots, ascending.
let runs = maximal_runs(&slot.above);
let run_count = u32::try_from(runs.len()).unwrap_or(u32::MAX);
out.extend_from_slice(&run_count.to_be_bytes());
for (start, len) in runs {
out.extend_from_slice(&start.to_be_bytes());
out.extend_from_slice(&len.to_be_bytes());
}
}
out
}
/// Decodes exactly one canonical frame produced by [`to_bytes`](Self::to_bytes),
/// rejecting trailing bytes.
///
/// # Errors
/// [`HaveSetDecodeError::UnexpectedLength`] if `bytes` carries trailing bytes;
/// otherwise the variants of [`from_prefix`](Self::from_prefix). Never panics
/// on adversarial input.
pub fn from_bytes(bytes: &[u8]) -> Result<Self, HaveSetDecodeError> {
Self::from_bytes_with_budget(bytes, HaveSetDecodeBudget::new(bytes.len()))
}
/// Decodes exactly one canonical frame under a caller-supplied expansion
/// budget, rejecting trailing bytes.
///
/// This is the embedding-protocol counterpart to [`from_bytes`](Self::from_bytes).
/// The caller must derive `budget` from a validated outer resource limit or
/// authenticated structure. The default decoder remains the secure choice
/// when no such bound exists.
///
/// Polis possession protocol v1 uses this seam beneath its authenticated
/// envelope, passing the receiver's validated exception ceiling. Accepted
/// bytes and budget semantics are therefore a downstream protocol contract.
///
/// # Errors
/// [`HaveSetDecodeError::UnexpectedLength`] if `bytes` carries trailing bytes;
/// otherwise the variants of
/// [`from_prefix_with_budget`](Self::from_prefix_with_budget). Never panics
/// on adversarial input.
pub fn from_bytes_with_budget(
bytes: &[u8],
budget: HaveSetDecodeBudget,
) -> Result<Self, HaveSetDecodeError> {
let (set, tail) = Self::from_prefix_with_budget(bytes, budget)?;
if tail.is_empty() {
Ok(set)
} else {
// `from_bytes` is `from_prefix` plus "the tail must be empty"; the
// consumed prefix is the exact frame the counts described.
Err(HaveSetDecodeError::UnexpectedLength {
expected: bytes.len() - tail.len(),
found: bytes.len(),
})
}
}
/// Decodes a canonical frame from the start of `bytes`, returning the have-set
/// and the unconsumed tail (the [`VersionVector::from_prefix`] seam, one type
/// over).
///
/// Decode validates structure *and* canonical form, so a frame the type's own
/// encoder could never produce is rejected rather than admitted, and every
/// accepted frame re-encodes bit-for-bit (the canonical bijection). Rejected:
/// stations not strictly ascending; a station with `floor == 0` and no runs
/// (canonical form holds it absent); runs not strictly ascending; a run
/// adjacent to the floor or to its predecessor (absorbable, so non-maximal); a
/// zero-length run; a run whose end (`start + len - 1`) overflows [`u64`].
///
/// Allocation is bounded by the input length, never by an untrusted count: the
/// remaining byte budget is checked (in `u64`, so it cannot overflow `usize` on
/// a 32-bit target) before each station header and before each station's run
/// block, so a frame claiming `u32::MAX` stations or runs is rejected in `O(1)`
/// against the buffer it cannot fill, exactly as [`VersionVector::from_prefix`]
/// does.
///
/// [`VersionVector::from_prefix`]: crate::metis::VersionVector::from_prefix
///
/// # Errors
/// [`HaveSetDecodeError::UnknownVersion`] for an unrecognized version byte;
/// [`HaveSetDecodeError::UnexpectedLength`] if the input is shorter than a
/// declared count requires; [`HaveSetDecodeError::EmptyStation`],
/// [`HaveSetDecodeError::NonAscendingStations`],
/// [`HaveSetDecodeError::ZeroLengthRun`],
/// [`HaveSetDecodeError::NonMaximalRun`], and
/// [`HaveSetDecodeError::RunOverflow`] for the canonical-form violations; and
/// [`HaveSetDecodeError::RunTooLong`] when the runs would materialize more dots
/// than the input length justifies. Never panics on adversarial input.
pub fn from_prefix(bytes: &[u8]) -> Result<(Self, &[u8]), HaveSetDecodeError> {
Self::from_prefix_with_budget(bytes, HaveSetDecodeBudget::new(bytes.len()))
}
/// [`from_prefix`](Self::from_prefix) under a caller-supplied dot
/// budget, for embedding codecs whose validated structure bounds the
/// honest set (the rhapsody frames pass their decoded skeleton's
/// cardinality: visibility is a subset of the skeleton). This buys an
/// embedder what the byte-length default cannot: dense-above-a-hole
/// values round-trip, and prefix acceptance is independent of the tail
/// (a byte budget read through an outer tail inflates with it; the
/// S197 gate review's finding). The standalone frame keeps the
/// PRD 0016 byte-length budget.
///
/// # Errors
/// The [`HaveSetDecodeError`] variants of
/// [`from_prefix`](Self::from_prefix), with
/// [`RunTooLong`](HaveSetDecodeError::RunTooLong) read against
/// `budget`. Never panics on adversarial input.
pub fn from_prefix_with_budget(
bytes: &[u8],
budget: HaveSetDecodeBudget,
) -> Result<(Self, &[u8]), HaveSetDecodeError> {
// Structure and canonical form are validated by the pure decode core
// (`wire/pure.rs`), whose totality and acceptance-shape contracts are
// machine-checked under the detached `proofs/` crate (ruling R-18);
// this adapter only folds the flat validated output into the map form
// and never re-derives a check. The proven code is the running code.
// A wire run cannot name more than `u64::MAX` dots. Saturating a wider
// allocation domain therefore preserves every representable budget.
let dot_budget = u64::try_from(budget.max_dots()).unwrap_or(u64::MAX);
let decoded = pure::decode_prefix_with_budget(bytes, dot_budget).map_err(lift)?;
let mut stations = BTreeMap::new();
let mut next_run = 0usize;
for &(station, floor) in &decoded.stations {
// The core emits each station's runs contiguously under its id,
// in frame order, so a linear cursor partitions them exactly.
let mut above = BTreeSet::new();
while let Some(&(run_station, start, len)) = decoded.runs.get(next_run) {
if run_station != station {
break;
}
// The core proved `len >= 1` and refused an end past the
// `u64` ceiling; the total fallbacks keep this fold
// panic-free without leaning on the proof.
let last = start.checked_add(len.saturating_sub(1)).unwrap_or(start);
for dot in start..=last {
let _ = above.insert(dot);
}
next_run += 1;
}
let _ = stations.insert(station, StationDots { floor, above });
}
Ok((
Self { stations },
bytes.get(decoded.consumed..).unwrap_or(&[]),
))
}
}