Skip to main content

qualia_core_db/bundle/stream/plan/
inventory.rs

1//! Authenticated mixed-HMC inventory. Family is declared metadata, not a suffix.
2use super::PlanError;
3use crate::bundle::stream::descriptor::CandidateIdentity;
4use crate::net::qdnf::types::StrongDigest;
5pub const MAX_PLAN_ENTRIES: usize = 64;
6pub const MAX_PLAN_EDGES: usize = 256;
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub enum EntryFamily {
9    TenD,
10    Q42,
11    Emf,
12    Qac,
13    M64,
14    P64,
15    Opaque,
16}
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub enum Obligation {
19    Mandatory,
20    Optional,
21}
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23pub enum RepresentationClass {
24    Control,
25    Metadata,
26    Base,
27    Enhancement,
28    Alternative,
29}
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
31pub enum DependencyReason {
32    Frame,
33    Calibration,
34    Clock,
35    Geometry,
36    Query,
37}
38/// Exact source-declared interval. Equal ticks do not mint a shared clock.
39#[derive(Clone, Copy, Debug, PartialEq, Eq)]
40pub struct RationalInterval {
41    start_num: i64,
42    start_den: u64,
43    end_num: i64,
44    end_den: u64,
45}
46impl RationalInterval {
47    pub fn declared(
48        start_num: i64,
49        start_den: u64,
50        end_num: i64,
51        end_den: u64,
52    ) -> Result<Self, PlanError> {
53        if start_den == 0 || end_den == 0 {
54            return Err(PlanError::Field);
55        }
56        Ok(Self {
57            start_num,
58            start_den,
59            end_num,
60            end_den,
61        })
62    }
63    pub const fn start_num(self) -> i64 {
64        self.start_num
65    }
66    pub const fn start_den(self) -> u64 {
67        self.start_den
68    }
69    pub const fn end_num(self) -> i64 {
70        self.end_num
71    }
72    pub const fn end_den(self) -> u64 {
73        self.end_den
74    }
75}
76/// Authenticated timebase identity. Absence means no clock, not epoch zero.
77#[derive(Clone, Copy, Debug, PartialEq, Eq)]
78pub struct TimebaseId {
79    identity: StrongDigest,
80}
81impl TimebaseId {
82    pub fn declared(identity: StrongDigest) -> Result<Self, PlanError> {
83        if identity.is_zero() {
84            return Err(PlanError::Field);
85        }
86        Ok(Self { identity })
87    }
88    pub const fn identity(self) -> StrongDigest {
89        self.identity
90    }
91}
92#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
93pub struct ResourceEstimate {
94    bytes: u64,
95    work: u64,
96    io: u64,
97}
98impl ResourceEstimate {
99    pub const fn new(bytes: u64, work: u64, io: u64) -> Self {
100        Self { bytes, work, io }
101    }
102    pub const fn bytes(self) -> u64 {
103        self.bytes
104    }
105    pub const fn work(self) -> u64 {
106        self.work
107    }
108    pub const fn io(self) -> u64 {
109        self.io
110    }
111}
112#[derive(Clone, Copy, Debug, PartialEq, Eq)]
113pub struct EntryRef {
114    candidate: CandidateIdentity,
115    entry_id: u32,
116}
117impl EntryRef {
118    pub const fn new(candidate: CandidateIdentity, entry_id: u32) -> Self {
119        Self {
120            candidate,
121            entry_id,
122        }
123    }
124    pub const fn candidate(self) -> CandidateIdentity {
125        self.candidate
126    }
127    pub const fn entry_id(self) -> u32 {
128        self.entry_id
129    }
130}
131#[derive(Clone, Copy, Debug, PartialEq, Eq)]
132pub struct PlanEntrySpec {
133    pub candidate: CandidateIdentity,
134    pub entry_id: u32,
135    pub family: EntryFamily,
136    pub role: RepresentationClass,
137    pub interval: Option<RationalInterval>,
138    pub timebase: Option<TimebaseId>,
139    pub estimate: ResourceEstimate,
140    pub obligation: Obligation,
141}
142#[derive(Clone, Copy, Debug, PartialEq, Eq)]
143pub struct PlanEntry {
144    candidate: CandidateIdentity,
145    entry_id: u32,
146    family: EntryFamily,
147    role: RepresentationClass,
148    interval: Option<RationalInterval>,
149    timebase: Option<TimebaseId>,
150    estimate: ResourceEstimate,
151    obligation: Obligation,
152}
153impl PlanEntry {
154    pub fn new(spec: PlanEntrySpec) -> Result<Self, PlanError> {
155        if spec.candidate.descriptor_id().is_zero() || spec.candidate.context_id().is_zero() {
156            return Err(PlanError::Identity);
157        }
158        Ok(Self {
159            candidate: spec.candidate,
160            entry_id: spec.entry_id,
161            family: spec.family,
162            role: spec.role,
163            interval: spec.interval,
164            timebase: spec.timebase,
165            estimate: spec.estimate,
166            obligation: spec.obligation,
167        })
168    }
169    pub const fn candidate(&self) -> CandidateIdentity {
170        self.candidate
171    }
172    pub const fn entry_id(&self) -> u32 {
173        self.entry_id
174    }
175    pub const fn family(&self) -> EntryFamily {
176        self.family
177    }
178    pub const fn role(&self) -> RepresentationClass {
179        self.role
180    }
181    pub const fn interval(&self) -> Option<RationalInterval> {
182        self.interval
183    }
184    pub const fn timebase(&self) -> Option<TimebaseId> {
185        self.timebase
186    }
187    pub const fn estimate(&self) -> ResourceEstimate {
188        self.estimate
189    }
190    pub const fn obligation(&self) -> Obligation {
191        self.obligation
192    }
193    pub const fn key(&self) -> EntryRef {
194        EntryRef::new(self.candidate, self.entry_id)
195    }
196}
197/// `from` depends on `to`. Bind by candidate identity, never by filename.
198#[derive(Clone, Copy, Debug, PartialEq, Eq)]
199pub struct DependencyEdge {
200    from: EntryRef,
201    to: EntryRef,
202    obligation: Obligation,
203    reason: DependencyReason,
204}
205impl DependencyEdge {
206    pub fn bind(
207        from: &PlanEntry,
208        to: &PlanEntry,
209        obligation: Obligation,
210        reason: DependencyReason,
211    ) -> Result<Self, PlanError> {
212        if from.candidate() != to.candidate() {
213            return Err(PlanError::Identity);
214        }
215        if from.entry_id() == to.entry_id() {
216            return Err(PlanError::Graph);
217        }
218        if reason == DependencyReason::Clock && !declared_shared_clock(from, to) {
219            return Err(PlanError::Refused);
220        }
221        Ok(Self {
222            from: from.key(),
223            to: to.key(),
224            obligation,
225            reason,
226        })
227    }
228    pub const fn from_ref(self) -> EntryRef {
229        self.from
230    }
231    pub const fn to_ref(self) -> EntryRef {
232        self.to
233    }
234    pub const fn from_id(self) -> u32 {
235        self.from.entry_id
236    }
237    pub const fn to_id(self) -> u32 {
238        self.to.entry_id
239    }
240    pub const fn obligation(self) -> Obligation {
241        self.obligation
242    }
243    pub const fn reason(self) -> DependencyReason {
244        self.reason
245    }
246}
247fn declared_shared_clock(a: &PlanEntry, b: &PlanEntry) -> bool {
248    match (a.timebase(), b.timebase()) {
249        (Some(ta), Some(tb)) => ta == tb,
250        _ => false,
251    }
252}
253pub struct Inventory<'a> {
254    candidate: CandidateIdentity,
255    entries: &'a [PlanEntry],
256    edges: &'a [DependencyEdge],
257}
258impl<'a> Inventory<'a> {
259    pub fn compile(
260        candidate: CandidateIdentity,
261        entries: &'a [PlanEntry],
262        edges: &'a [DependencyEdge],
263    ) -> Result<Self, PlanError> {
264        if candidate.descriptor_id().is_zero() || candidate.context_id().is_zero() {
265            return Err(PlanError::Identity);
266        }
267        if entries.is_empty() || entries.len() > MAX_PLAN_ENTRIES || edges.len() > MAX_PLAN_EDGES {
268            return Err(PlanError::Limit);
269        }
270        for entry in entries {
271            if entry.candidate() != candidate {
272                return Err(PlanError::Identity);
273            }
274        }
275        for i in 0..entries.len() {
276            for j in 0..i {
277                if entries[i].entry_id() == entries[j].entry_id() {
278                    return Err(PlanError::DuplicateId);
279                }
280            }
281        }
282        for (i, edge) in edges.iter().enumerate() {
283            if edge.from.candidate != candidate || edge.to.candidate != candidate {
284                return Err(PlanError::Identity);
285            }
286            let from = index_of(entries, edge.from_id()).ok_or(PlanError::Graph)?;
287            let to = index_of(entries, edge.to_id()).ok_or(PlanError::Graph)?;
288            if from == to {
289                return Err(PlanError::Graph);
290            }
291            for prior in &edges[..i] {
292                if prior.from_id() == edge.from_id() && prior.to_id() == edge.to_id() {
293                    return Err(PlanError::Graph);
294                }
295            }
296            if edge.reason == DependencyReason::Clock
297                && !declared_shared_clock(&entries[from], &entries[to])
298            {
299                return Err(PlanError::Refused);
300            }
301        }
302        acyclic(entries, edges)?;
303        Ok(Self {
304            candidate,
305            entries,
306            edges,
307        })
308    }
309    pub const fn candidate(&self) -> CandidateIdentity {
310        self.candidate
311    }
312    pub const fn entries(&self) -> &'a [PlanEntry] {
313        self.entries
314    }
315    pub const fn edges(&self) -> &'a [DependencyEdge] {
316        self.edges
317    }
318    pub const fn len(&self) -> usize {
319        self.entries.len()
320    }
321    pub fn entry(&self, id: u32) -> Option<&'a PlanEntry> {
322        self.entries.iter().find(|e| e.entry_id() == id)
323    }
324    pub fn index_of(&self, id: u32) -> Option<usize> {
325        index_of(self.entries, id)
326    }
327    /// True only when both entries named the same authenticated timebase.
328    pub fn share_clock(&self, a: u32, b: u32) -> bool {
329        match (self.entry(a), self.entry(b)) {
330            (Some(x), Some(y)) => declared_shared_clock(x, y),
331            _ => false,
332        }
333    }
334}
335fn index_of(entries: &[PlanEntry], id: u32) -> Option<usize> {
336    entries.iter().position(|e| e.entry_id() == id)
337}
338fn acyclic(entries: &[PlanEntry], edges: &[DependencyEdge]) -> Result<(), PlanError> {
339    let n = entries.len();
340    let mut indeg = [0u16; MAX_PLAN_ENTRIES];
341    for edge in edges {
342        let to = index_of(entries, edge.to_id()).ok_or(PlanError::Graph)?;
343        indeg[to] = indeg[to].checked_add(1).ok_or(PlanError::Limit)?;
344    }
345    let mut queue = [0usize; MAX_PLAN_ENTRIES];
346    let mut qh = 0usize;
347    let mut qt = 0usize;
348    for i in 0..n {
349        if indeg[i] == 0 {
350            queue[qt] = i;
351            qt += 1;
352        }
353    }
354    let mut seen = 0usize;
355    while qh < qt {
356        let i = queue[qh];
357        qh += 1;
358        seen += 1;
359        let id = entries[i].entry_id();
360        for edge in edges {
361            if edge.from_id() != id {
362                continue;
363            }
364            let to = index_of(entries, edge.to_id()).ok_or(PlanError::Graph)?;
365            indeg[to] = indeg[to].checked_sub(1).ok_or(PlanError::Graph)?;
366            if indeg[to] == 0 {
367                queue[qt] = to;
368                qt += 1;
369            }
370        }
371    }
372    if seen != n {
373        return Err(PlanError::Cycle);
374    }
375    Ok(())
376}