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