1use 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#[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#[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#[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 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 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}