Skip to main content

qualia_core_db/bundle/stream/plan/
schedule.rs

1//! Fair record-boundary schedule. Occupancy is an intent flag, not a ledger.
2use super::inventory::{
3    EntryFamily, EntryRef, Inventory, Obligation, PlanEntry, RepresentationClass, MAX_PLAN_ENTRIES,
4};
5use super::readiness::{evaluate, Readiness};
6use super::PlanError;
7use crate::bundle::stream::descriptor::CandidateIdentity;
8pub const MAX_SCHEDULE_ITEMS: usize = 64;
9pub const MAX_PRINCIPALS: usize = 8;
10/// Semantic class for this planner; not `net::peer::runtime::WorkClass`.
11#[derive(Clone, Copy, Debug, PartialEq, Eq)]
12pub enum WorkClass {
13    Control,
14    Metadata,
15    BaseRepresentation,
16    Enhancement,
17}
18impl WorkClass {
19    fn of(entry: &PlanEntry) -> Self {
20        match entry.role() {
21            RepresentationClass::Control => Self::Control,
22            RepresentationClass::Metadata => Self::Metadata,
23            RepresentationClass::Base => Self::BaseRepresentation,
24            RepresentationClass::Enhancement | RepresentationClass::Alternative => {
25                Self::Enhancement
26            }
27        }
28    }
29}
30fn deferred_family(family: Option<EntryFamily>) -> bool {
31    matches!(family, Some(EntryFamily::M64 | EntryFamily::P64))
32}
33#[derive(Clone, Copy, Debug, PartialEq, Eq)]
34pub struct Region {
35    start: u64,
36    end: u64,
37}
38impl Region {
39    pub fn declared(start: u64, end: u64) -> Result<Self, PlanError> {
40        if end <= start {
41            return Err(PlanError::Field);
42        }
43        Ok(Self { start, end })
44    }
45    pub const fn start(self) -> u64 {
46        self.start
47    }
48    pub const fn end(self) -> u64 {
49        self.end
50    }
51    pub const fn contains(self, leaf: u64) -> bool {
52        leaf >= self.start && leaf < self.end
53    }
54}
55/// One admitted record-boundary unit. `next` never yields more than one.
56#[derive(Clone, Copy, Debug, PartialEq, Eq)]
57pub struct RecordUnit {
58    leaf: u64,
59}
60impl RecordUnit {
61    pub const fn at(leaf: u64) -> Self {
62        Self { leaf }
63    }
64    pub const fn leaf(self) -> u64 {
65        self.leaf
66    }
67}
68#[derive(Clone, Copy, Debug, PartialEq, Eq)]
69pub struct SelectionIntent {
70    entry_id: u32,
71    family: EntryFamily,
72    interval: Option<super::RationalInterval>,
73    region: Option<Region>,
74}
75impl SelectionIntent {
76    pub fn scene(
77        entry_id: u32,
78        family: EntryFamily,
79        interval: Option<super::RationalInterval>,
80        region: Option<Region>,
81    ) -> Result<Self, PlanError> {
82        Ok(Self {
83            entry_id,
84            family,
85            interval,
86            region,
87        })
88    }
89    pub const fn entry_id(self) -> u32 {
90        self.entry_id
91    }
92    pub const fn family(self) -> EntryFamily {
93        self.family
94    }
95    pub const fn interval(self) -> Option<super::RationalInterval> {
96        self.interval
97    }
98    pub const fn region(self) -> Option<Region> {
99        self.region
100    }
101}
102/// Scene or analysis intent. Not an M64 path or filename.
103#[derive(Clone, Copy, Debug)]
104pub struct SelectionRequest<'a> {
105    intents: &'a [SelectionIntent],
106}
107impl<'a> SelectionRequest<'a> {
108    pub fn scene(intents: &'a [SelectionIntent]) -> Result<Self, PlanError> {
109        if intents.is_empty() || intents.len() > MAX_PLAN_ENTRIES {
110            return Err(PlanError::Limit);
111        }
112        for i in 0..intents.len() {
113            for j in 0..i {
114                if intents[i].entry_id == intents[j].entry_id
115                    && intents[i].region == intents[j].region
116                {
117                    return Err(PlanError::DuplicateId);
118                }
119            }
120        }
121        Ok(Self { intents })
122    }
123    pub const fn intents(&self) -> &'a [SelectionIntent] {
124        self.intents
125    }
126}
127#[derive(Clone, Copy, Debug)]
128pub struct PrincipalSelection<'a> {
129    principal: u64,
130    request: SelectionRequest<'a>,
131}
132impl<'a> PrincipalSelection<'a> {
133    pub fn new(principal: u64, request: SelectionRequest<'a>) -> Result<Self, PlanError> {
134        if principal == 0 {
135            return Err(PlanError::Field);
136        }
137        Ok(Self { principal, request })
138    }
139    pub const fn principal(&self) -> u64 {
140        self.principal
141    }
142    pub const fn request(&self) -> &SelectionRequest<'a> {
143        &self.request
144    }
145}
146#[derive(Clone, Copy, Debug, PartialEq, Eq)]
147pub struct ScheduledUnit {
148    principal: u64,
149    class: WorkClass,
150    family: Option<EntryFamily>,
151    entry_id: Option<u32>,
152    unit: RecordUnit,
153}
154impl ScheduledUnit {
155    pub const fn principal(self) -> u64 {
156        self.principal
157    }
158    pub const fn class(self) -> WorkClass {
159        self.class
160    }
161    pub const fn family(self) -> Option<EntryFamily> {
162        self.family
163    }
164    pub const fn entry_id(self) -> Option<u32> {
165        self.entry_id
166    }
167    pub const fn unit(self) -> RecordUnit {
168        self.unit
169    }
170}
171#[derive(Clone, Copy)]
172struct WorkItem {
173    principal: u64,
174    entry_id: Option<u32>,
175    family: Option<EntryFamily>,
176    class: WorkClass,
177    unit: RecordUnit,
178    key: Option<EntryRef>,
179    cancelled: bool,
180    occupancy: bool,
181    issued: bool,
182    ready: bool,
183}
184impl WorkItem {
185    const VACANT: Self = Self {
186        principal: 0,
187        entry_id: None,
188        family: None,
189        class: WorkClass::Control,
190        unit: RecordUnit::at(0),
191        key: None,
192        cancelled: false,
193        occupancy: false,
194        issued: false,
195        ready: false,
196    };
197}
198#[derive(Clone, Copy, PartialEq, Eq)]
199enum DeferFilter {
200    Live,
201    Deferred,
202}
203pub struct Schedule {
204    candidate: CandidateIdentity,
205    items: [WorkItem; MAX_SCHEDULE_ITEMS],
206    len: usize,
207    principals: [u64; MAX_PRINCIPALS],
208    principal_count: usize,
209    principal_cursor: usize,
210    charged: [Option<EntryRef>; MAX_SCHEDULE_ITEMS],
211    charged_len: usize,
212    charged_bytes: u64,
213}
214impl Schedule {
215    pub fn compile(
216        inventory: &Inventory<'_>,
217        selections: &[PrincipalSelection<'_>],
218        present: &[u32],
219    ) -> Result<Self, PlanError> {
220        if selections.is_empty() || selections.len() > MAX_PRINCIPALS {
221            return Err(PlanError::Limit);
222        }
223        let mut plan = Self {
224            candidate: inventory.candidate(),
225            items: [WorkItem::VACANT; MAX_SCHEDULE_ITEMS],
226            len: 0,
227            principals: [0; MAX_PRINCIPALS],
228            principal_count: 0,
229            principal_cursor: 0,
230            charged: [None; MAX_SCHEDULE_ITEMS],
231            charged_len: 0,
232            charged_bytes: 0,
233        };
234        for sel in selections {
235            plan.ensure_principal(sel.principal())?;
236            let mut leaves = [0u64; MAX_PLAN_ENTRIES];
237            for intent in sel.request().intents() {
238                let Some(entry) = inventory.entry(intent.entry_id()) else {
239                    return Err(PlanError::Graph);
240                };
241                if entry.family() != intent.family() {
242                    return Err(PlanError::Identity);
243                }
244                if let (Some(want), Some(have)) = (intent.interval(), entry.interval()) {
245                    if want != have {
246                        return Err(PlanError::Field);
247                    }
248                }
249                if let Some(idx) = inventory.index_of(intent.entry_id()) {
250                    if let Some(region) = intent.region() {
251                        leaves[idx] = region.start();
252                    }
253                }
254                close_selection(
255                    &mut plan,
256                    inventory,
257                    sel.principal(),
258                    intent,
259                    present,
260                    &leaves,
261                )?;
262            }
263        }
264        Ok(plan)
265    }
266    pub fn enqueue_unit(
267        &mut self,
268        principal: u64,
269        entry: &PlanEntry,
270        unit: RecordUnit,
271        ready: bool,
272    ) -> Result<(), PlanError> {
273        if entry.candidate() != self.candidate {
274            return Err(PlanError::Identity);
275        }
276        self.ensure_principal(principal)?;
277        self.push_item(
278            principal,
279            Some(entry.entry_id()),
280            Some(entry.family()),
281            WorkClass::of(entry),
282            unit,
283            Some(entry.key()),
284            ready,
285            entry.estimate().bytes(),
286        )
287    }
288    pub fn push_control(&mut self, principal: u64, unit: RecordUnit) -> Result<(), PlanError> {
289        self.ensure_principal(principal)?;
290        self.push_item(
291            principal,
292            None,
293            None,
294            WorkClass::Control,
295            unit,
296            None,
297            true,
298            0,
299        )
300    }
301    /// Mark overlapping units cancelled. Occupancy stays until `acknowledge_complete`.
302    pub fn cancel(&mut self, entry_id: u32, region: Option<Region>) -> usize {
303        let mut n = 0usize;
304        for i in 0..self.len {
305            let item = &mut self.items[i];
306            if item.entry_id != Some(entry_id) || item.cancelled {
307                continue;
308            }
309            let hit = match region {
310                None => true,
311                Some(r) => r.contains(item.unit.leaf()),
312            };
313            if hit {
314                item.cancelled = true;
315                n += 1;
316            }
317        }
318        n
319    }
320    /// At most one admitted record-boundary unit. Control is never starved.
321    /// M64/P64 wait while Ready EMF/QAC/10D (and other live families) remain.
322    pub fn next(&mut self) -> Option<ScheduledUnit> {
323        const ORDER: [(WorkClass, DeferFilter); 6] = [
324            (WorkClass::Metadata, DeferFilter::Live),
325            (WorkClass::BaseRepresentation, DeferFilter::Live),
326            (WorkClass::Enhancement, DeferFilter::Live),
327            (WorkClass::Metadata, DeferFilter::Deferred),
328            (WorkClass::BaseRepresentation, DeferFilter::Deferred),
329            (WorkClass::Enhancement, DeferFilter::Deferred),
330        ];
331        if let Some(i) = self.find_fair(WorkClass::Control, None) {
332            return self.take(i);
333        }
334        for (class, filter) in ORDER {
335            if let Some(i) = self.find_fair(class, Some(filter)) {
336                return self.take(i);
337            }
338        }
339        None
340    }
341    pub fn occupancy_retained(&self, principal: u64, entry_id: Option<u32>, leaf: u64) -> bool {
342        self.items[..self.len].iter().any(|item| {
343            item.principal == principal
344                && item.entry_id == entry_id
345                && item.unit.leaf() == leaf
346                && item.occupancy
347        })
348    }
349    pub fn acknowledge_complete(
350        &mut self,
351        principal: u64,
352        entry_id: Option<u32>,
353        leaf: u64,
354    ) -> Result<(), PlanError> {
355        for item in &mut self.items[..self.len] {
356            if item.principal == principal
357                && item.entry_id == entry_id
358                && item.unit.leaf() == leaf
359                && item.occupancy
360            {
361                item.occupancy = false;
362                return Ok(());
363            }
364        }
365        Err(PlanError::Graph)
366    }
367    pub fn is_charged(&self, candidate: CandidateIdentity, entry_id: u32) -> bool {
368        let key = EntryRef::new(candidate, entry_id);
369        self.charged[..self.charged_len]
370            .iter()
371            .any(|slot| *slot == Some(key))
372    }
373    pub const fn charged_bytes(&self) -> u64 {
374        self.charged_bytes
375    }
376    pub const fn candidate(&self) -> CandidateIdentity {
377        self.candidate
378    }
379    pub const fn len(&self) -> usize {
380        self.len
381    }
382    fn ensure_principal(&mut self, principal: u64) -> Result<usize, PlanError> {
383        if principal == 0 {
384            return Err(PlanError::Field);
385        }
386        if let Some(i) = self.principals[..self.principal_count]
387            .iter()
388            .position(|p| *p == principal)
389        {
390            return Ok(i);
391        }
392        if self.principal_count >= MAX_PRINCIPALS {
393            return Err(PlanError::Capacity);
394        }
395        let i = self.principal_count;
396        self.principals[i] = principal;
397        self.principal_count += 1;
398        Ok(i)
399    }
400    #[allow(clippy::too_many_arguments)]
401    fn push_item(
402        &mut self,
403        principal: u64,
404        entry_id: Option<u32>,
405        family: Option<EntryFamily>,
406        class: WorkClass,
407        unit: RecordUnit,
408        key: Option<EntryRef>,
409        ready: bool,
410        bytes: u64,
411    ) -> Result<(), PlanError> {
412        for item in &self.items[..self.len] {
413            if item.principal == principal
414                && item.entry_id == entry_id
415                && item.unit.leaf() == unit.leaf()
416                && item.class == class
417            {
418                return Ok(());
419            }
420        }
421        if let Some(key) = key {
422            if self.items[..self.len]
423                .iter()
424                .any(|item| item.key == Some(key) && item.unit.leaf() == unit.leaf())
425            {
426                self.charge(key, bytes)?;
427                return Ok(());
428            }
429            self.charge(key, bytes)?;
430        }
431        if self.len >= MAX_SCHEDULE_ITEMS {
432            return Err(PlanError::Capacity);
433        }
434        self.items[self.len] = WorkItem {
435            principal,
436            entry_id,
437            family,
438            class,
439            unit,
440            key,
441            cancelled: false,
442            occupancy: true,
443            issued: false,
444            ready,
445        };
446        self.len += 1;
447        Ok(())
448    }
449    fn charge(&mut self, key: EntryRef, bytes: u64) -> Result<(), PlanError> {
450        if self.charged[..self.charged_len]
451            .iter()
452            .any(|slot| *slot == Some(key))
453        {
454            return Ok(());
455        }
456        if self.charged_len >= MAX_SCHEDULE_ITEMS {
457            return Err(PlanError::Capacity);
458        }
459        self.charged[self.charged_len] = Some(key);
460        self.charged_len += 1;
461        self.charged_bytes = self
462            .charged_bytes
463            .checked_add(bytes)
464            .ok_or(PlanError::Limit)?;
465        Ok(())
466    }
467    fn find_fair(&self, class: WorkClass, filter: Option<DeferFilter>) -> Option<usize> {
468        if self.principal_count == 0 {
469            return None;
470        }
471        for step in 0..self.principal_count {
472            let p = (self.principal_cursor + step) % self.principal_count;
473            let principal = self.principals[p];
474            let mut best: Option<usize> = None;
475            for i in 0..self.len {
476                let item = &self.items[i];
477                if item.principal != principal
478                    || item.class != class
479                    || item.cancelled
480                    || item.issued
481                    || !item.ready
482                {
483                    continue;
484                }
485                if let Some(filter) = filter {
486                    let deferred = deferred_family(item.family);
487                    match filter {
488                        DeferFilter::Live if deferred => continue,
489                        DeferFilter::Deferred if !deferred => continue,
490                        _ => {}
491                    }
492                }
493                best = Some(match best {
494                    None => i,
495                    Some(j) if precedes(item, &self.items[j]) => i,
496                    Some(j) => j,
497                });
498            }
499            if best.is_some() {
500                return best;
501            }
502        }
503        None
504    }
505    fn take(&mut self, index: usize) -> Option<ScheduledUnit> {
506        let item = self.items.get_mut(index)?;
507        item.issued = true;
508        item.occupancy = true;
509        let unit = ScheduledUnit {
510            principal: item.principal,
511            class: item.class,
512            family: item.family,
513            entry_id: item.entry_id,
514            unit: item.unit,
515        };
516        if let Some(i) = self.principals[..self.principal_count]
517            .iter()
518            .position(|p| *p == unit.principal)
519        {
520            self.principal_cursor = (i + 1) % self.principal_count.max(1);
521        }
522        Some(unit)
523    }
524}
525fn precedes(a: &WorkItem, b: &WorkItem) -> bool {
526    match (a.entry_id, b.entry_id) {
527        (Some(x), Some(y)) if x != y => x < y,
528        _ => a.unit.leaf() < b.unit.leaf(),
529    }
530}
531fn close_selection(
532    plan: &mut Schedule,
533    inventory: &Inventory<'_>,
534    principal: u64,
535    intent: &SelectionIntent,
536    present: &[u32],
537    leaves: &[u64; MAX_PLAN_ENTRIES],
538) -> Result<(), PlanError> {
539    let mut stack = [0u32; MAX_PLAN_ENTRIES];
540    let mut sp = 0usize;
541    let mut seen = [false; MAX_PLAN_ENTRIES];
542    push_id(inventory, &mut stack, &mut sp, &mut seen, intent.entry_id())?;
543    while sp > 0 {
544        sp -= 1;
545        let id = stack[sp];
546        let entry = inventory.entry(id).ok_or(PlanError::Graph)?;
547        let readiness = evaluate(inventory, id, Some(entry.family()), present);
548        match readiness {
549            Readiness::Refused => return Err(PlanError::Refused),
550            Readiness::Ready => {
551                let leaf = inventory.index_of(id).map(|idx| leaves[idx]).unwrap_or(0);
552                plan.enqueue_unit(principal, entry, RecordUnit::at(leaf), true)?;
553            }
554            Readiness::Incomplete { .. } | Readiness::Opaque => {}
555        }
556        for edge in inventory.edges() {
557            if edge.from_id() != id {
558                continue;
559            }
560            let dep = edge.to_id();
561            let include = match edge.obligation() {
562                Obligation::Mandatory => true,
563                Obligation::Optional => evaluate(inventory, dep, None, present) == Readiness::Ready,
564            };
565            if include {
566                push_id(inventory, &mut stack, &mut sp, &mut seen, dep)?;
567            }
568        }
569    }
570    Ok(())
571}
572fn push_id(
573    inventory: &Inventory<'_>,
574    stack: &mut [u32; MAX_PLAN_ENTRIES],
575    sp: &mut usize,
576    seen: &mut [bool; MAX_PLAN_ENTRIES],
577    id: u32,
578) -> Result<(), PlanError> {
579    let idx = inventory.index_of(id).ok_or(PlanError::Graph)?;
580    if seen[idx] {
581        return Ok(());
582    }
583    if *sp >= MAX_PLAN_ENTRIES {
584        return Err(PlanError::Capacity);
585    }
586    seen[idx] = true;
587    stack[*sp] = id;
588    *sp += 1;
589    Ok(())
590}