ifc_schedule/query/timeline.rs
1//! Deterministic timeline queries over an authored schedule.
2//!
3//! # What "deterministic" means here
4//!
5//! Every result is ordered explicitly -- by file order, or by a stable
6//! tie-break -- so two runs over the same file produce the same sequence. That
7//! matters because these results feed diffs and reports, where a hash-ordered
8//! result set produces spurious changes.
9//!
10//! # What this module does NOT compute
11//!
12//! No critical path, no forward/backward pass, no date arithmetic. Those need
13//! calendar expansion and a date library, which this crate does not
14//! depend on. What it does provide is the ordering those algorithms run on,
15//! plus the anomalies that make them meaningless if ignored.
16
17use std::collections::{HashMap, HashSet};
18
19use ifc_model::{EntityId, Model};
20
21use crate::error::ScheduleReadError;
22use crate::release::ReadRelease;
23use crate::sequence::{sequences, SequenceCycle};
24
25const ASSIGNS: &str = "IFCRELASSIGNSTOCONTROL";
26const NESTS: &str = "IFCRELNESTS";
27
28/// `IfcRelAssignsToControl` slots, the same in IFC2X3, IFC4 and IFC4X3.
29/// The writers lay records out with them; the readers go by name.
30pub mod assigns {
31 /// `GlobalId` (from `IfcRoot`).
32 pub const GLOBAL_ID: usize = 0;
33 /// `RelatedObjects`.
34 pub const RELATED: usize = 4;
35 /// `RelatingControl`.
36 pub const RELATING: usize = 6;
37}
38
39/// `IfcRelNests` slots, the same in IFC2X3, IFC4 and IFC4X3. The writers
40/// lay records out with them; the readers go by name.
41pub mod nests {
42 /// `GlobalId` (from `IfcRoot`).
43 pub const GLOBAL_ID: usize = 0;
44 /// `RelatingObject`.
45 pub const RELATING: usize = 4;
46 /// `RelatedObjects`.
47 pub const RELATED: usize = 5;
48}
49
50/// Tasks assigned to a work schedule, in file order.
51///
52/// Uses `IfcRelAssignsToControl` and its subtypes in the bound release
53/// (IFC2X3's `IfcRelAssignsTasks`), whose `RelatingControl` is the
54/// schedule.
55///
56/// # Errors
57///
58/// [`ScheduleReadError::UnsupportedSchema`] or
59/// [`ScheduleReadError::MultipleSchemas`] for a header the readers cannot
60/// bind; a header with no schema reads as IFC4.
61pub fn tasks_of_schedule(
62 model: &Model,
63 schedule: EntityId,
64) -> Result<Vec<EntityId>, ScheduleReadError> {
65 let release = ReadRelease::of(model)?;
66 let mut out = Vec::new();
67 // IFC2X3 assigns a timed task with the `IfcRelAssignsTasks` subtype
68 // (#235), so every subtype in the bound release is read.
69 for id in release.instances_of(model, ASSIGNS) {
70 let Some(entity) = model.get(id) else {
71 continue;
72 };
73 if release.reference(ASSIGNS, entity, "RelatingControl") != Some(schedule) {
74 continue;
75 }
76 if let Some(v) = release.value(ASSIGNS, entity, "RelatedObjects") {
77 v.for_each_ref(&mut |id| {
78 if !out.contains(&id) {
79 out.push(id);
80 }
81 });
82 }
83 }
84 Ok(out)
85}
86
87/// Sub-tasks nested directly under a task, in authored order.
88///
89/// A work breakdown structure nests tasks with `IfcRelNests`, the same
90/// relationship cost items use.
91///
92/// # Errors
93///
94/// As [`tasks_of_schedule`].
95pub fn subtasks_of(model: &Model, parent: EntityId) -> Result<Vec<EntityId>, ScheduleReadError> {
96 let release = ReadRelease::of(model)?;
97 let mut out = Vec::new();
98 for (_, entity) in model.of_type(NESTS) {
99 if release.reference(NESTS, entity, "RelatingObject") != Some(parent) {
100 continue;
101 }
102 if let Some(v) = release.value(NESTS, entity, "RelatedObjects") {
103 v.for_each_ref(&mut |id| out.push(id));
104 }
105 }
106 Ok(out)
107}
108
109/// Tasks with no predecessor: where the schedule can start.
110///
111/// In file order, so the result is stable.
112///
113/// # Errors
114///
115/// The binding refusals of [`sequences`].
116pub fn start_tasks(model: &Model) -> Result<Vec<EntityId>, ScheduleReadError> {
117 let links = sequences(model)?;
118 let has_predecessor: HashSet<EntityId> = links.iter().map(|s| s.successor).collect();
119 Ok(model
120 .ids_of_type("IFCTASK")
121 .iter()
122 .copied()
123 .filter(|id| !has_predecessor.contains(id))
124 .collect())
125}
126
127/// Tasks with no successor: where the schedule ends.
128///
129/// # Errors
130///
131/// The binding refusals of [`sequences`].
132pub fn end_tasks(model: &Model) -> Result<Vec<EntityId>, ScheduleReadError> {
133 let links = sequences(model)?;
134 let has_successor: HashSet<EntityId> = links.iter().map(|s| s.predecessor).collect();
135 Ok(model
136 .ids_of_type("IFCTASK")
137 .iter()
138 .copied()
139 .filter(|id| !has_successor.contains(id))
140 .collect())
141}
142
143/// Every task in a valid execution order.
144///
145/// A deterministic topological sort: among tasks that are simultaneously
146/// ready, the one appearing first in the file wins. Without that tie-break the
147/// order would depend on hash iteration and change between runs.
148///
149/// The sort runs over every `IfcProcess` and keeps the `IfcTask`s (#236), so
150/// a constraint that passes through an `IfcEvent` or `IfcProcedure`
151/// (task A, then event E, then task B) still orders A before B, and a cycle
152/// through one is still refused. [`process_execution_order`] keeps every
153/// process.
154///
155/// # Errors
156///
157/// [`ScheduleReadError::Cycle`] when the graph loops, because a cyclic
158/// schedule has no valid ordering at all, and the refusals of
159/// [`process_execution_order`].
160pub fn execution_order(model: &Model) -> Result<Vec<EntityId>, ScheduleReadError> {
161 Ok(process_execution_order(model)?
162 .into_iter()
163 .filter(|id| {
164 model
165 .get(*id)
166 .is_some_and(|entity| entity.type_name.eq_ignore_ascii_case("IFCTASK"))
167 })
168 .collect())
169}
170
171/// Every `IfcProcess` (task, procedure or event) in a valid execution order
172/// (#236).
173///
174/// The same deterministic sort as [`execution_order`], over every process
175/// the model's release declares, in file order among those ready together.
176///
177/// # Errors
178///
179/// [`ScheduleReadError::Cycle`] when the graph loops,
180/// [`ScheduleReadError::SequenceDepthExceeded`] when locating that cycle
181/// meets a chain longer than the walk budget, and the binding refusals of
182/// [`sequences`].
183pub fn process_execution_order(model: &Model) -> Result<Vec<EntityId>, ScheduleReadError> {
184 let links = sequences(model)?;
185 let processes = crate::sequence::relation::processes(model)?;
186 let position: HashMap<EntityId, usize> = processes
187 .iter()
188 .enumerate()
189 .map(|(i, id)| (*id, i))
190 .collect();
191
192 let mut indegree: HashMap<EntityId, usize> = processes.iter().map(|id| (*id, 0)).collect();
193 let mut edges: HashMap<EntityId, Vec<EntityId>> = HashMap::new();
194 for link in &links {
195 // Ignore links naming entities that are not processes in this model:
196 // a dangling sequence must not silently drop a real process.
197 if !position.contains_key(&link.predecessor) || !position.contains_key(&link.successor) {
198 continue;
199 }
200 edges
201 .entry(link.predecessor)
202 .or_default()
203 .push(link.successor);
204 *indegree.entry(link.successor).or_insert(0) += 1;
205 }
206
207 // Ready set kept sorted by file position: deterministic, and cheap at the
208 // sizes real schedules reach.
209 let mut ready: Vec<EntityId> = processes
210 .iter()
211 .copied()
212 .filter(|id| indegree.get(id).copied().unwrap_or(0) == 0)
213 .collect();
214 ready.sort_by_key(|id| position.get(id).copied().unwrap_or(usize::MAX));
215
216 let mut out = Vec::new();
217 while let Some(next) = ready.first().copied() {
218 ready.remove(0);
219 out.push(next);
220 for successor in edges.get(&next).cloned().unwrap_or_default() {
221 let degree = indegree.entry(successor).or_insert(0);
222 *degree = degree.saturating_sub(1);
223 if *degree == 0 {
224 ready.push(successor);
225 ready.sort_by_key(|id| position.get(id).copied().unwrap_or(usize::MAX));
226 }
227 }
228 }
229
230 if out.len() != processes.len() {
231 // Kahn's algorithm stalls exactly when a cycle remains. Find it and
232 // report the path rather than a bare "graph is cyclic".
233 if let Some(cycle) = crate::sequence::find_cycle(model)? {
234 return Err(cycle.into());
235 }
236 // Unreachable for a well-formed model: a stall implies a cycle. Report
237 // the first unemitted process rather than claiming a clean result.
238 let emitted: HashSet<EntityId> = out.iter().copied().collect();
239 let stalled = processes
240 .iter()
241 .find(|id| !emitted.contains(id))
242 .copied()
243 .unwrap_or(EntityId(0));
244 return Err(SequenceCycle {
245 repeated: stalled,
246 path: vec![stalled],
247 }
248 .into());
249 }
250 Ok(out)
251}