Skip to main content

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}