ifc_schedule/sequence/
relation.rs

1//! `IfcRelSequence`: predecessor/successor links and their lag.
2//!
3//! # Read by name in the declared release (#212)
4//!
5//! ```text
6//! IfcRelSequence  (IfcRelConnects -> IfcRelationship -> IfcRoot)
7//! IFC4, IFC4X3  0 GlobalId  1 OwnerHistory  2 Name  3 Description
8//!               4 RelatingProcess  5 RelatedProcess
9//!               6 TimeLag (OPTIONAL IfcLagTime)  7 SequenceType
10//!               8 UserDefinedSequenceType
11//! IFC2X3        the same first six, 6 TimeLag (IfcTimeMeasure, required)
12//!               7 SequenceType (required)
13//!
14//! IfcLagTime  (IfcSchedulingTime; IFC4 and IFC4X3 only)
15//! 0 Name              1 DataOrigin        2 UserDefinedDataOrigin
16//! 3 LagValue          4 DurationType
17//! ```
18//!
19//! Every attribute is found by name in the model's declared release. An
20//! IFC2X3 lag is a time measure on the relationship itself, reported as
21//! [`Sequence::time_lag_measure`], never as an `IfcLagTime`.
22//!
23//! # Direction is stated, not inferred
24//!
25//! Unlike `IfcRelConnectsPorts`, where authoring order carries no physical
26//! meaning, `IfcRelSequence` IS directed by definition: `RelatingProcess` is
27//! the predecessor and `RelatedProcess` is the successor. The schema's own
28//! inverse names confirm it -- `IsPredecessorTo` is `FOR RelatingProcess`.
29//!
30//! # Sequence type says WHICH ends are linked
31//!
32//! `IfcSequenceEnum` is not decoration: `FINISH_START` means the successor
33//! starts after the predecessor finishes, while `START_START` means they start
34//! together. A tool that treats every link as finish-to-start will compute a
35//! schedule that the file does not state.
36//!
37//! # Lag is signed
38//!
39//! `IfcLagTime.LagValue` may be negative: a negative lag is a lead, meaning
40//! the linked ends overlap. It is a stated fact, not a defect to refuse.
41
42use std::collections::{HashMap, HashSet};
43
44use ifc_model::{EntityId, Model, Value};
45
46use crate::error::ScheduleReadError;
47use crate::release::ReadRelease;
48use crate::task::DurationType;
49
50const SEQUENCE: &str = "IFCRELSEQUENCE";
51const LAG_TIME: &str = "IFCLAGTIME";
52
53/// `IfcRelSequence` slots in the layout IFC4 and IFC4X3 share, which the
54/// modelless `create_sequence` writes. The reader goes by name.
55pub(crate) mod slot {
56    /// `RelatingProcess`, the predecessor.
57    pub const RELATING: usize = 4;
58    /// `RelatedProcess`, the successor.
59    pub const RELATED: usize = 5;
60    /// `TimeLag`, an `IfcLagTime` reference.
61    pub const TIME_LAG: usize = 6;
62    /// `SequenceType`.
63    pub const SEQUENCE_TYPE: usize = 7;
64}
65
66/// `IfcLagTime` slots (IFC4 and IFC4X3; IFC2X3 has no `IfcLagTime`). The
67/// reader goes by name.
68pub mod lag_slot {
69    /// `LagValue`. Required by the schema.
70    pub const LAG_VALUE: usize = 3;
71    /// `DurationType`. Required by the schema.
72    pub const DURATION_TYPE: usize = 4;
73}
74
75/// The longest chain of processes a sequence walk follows.
76///
77/// A walk that would go deeper is refused with
78/// [`ScheduleReadError::SequenceDepthExceeded`] rather than returned
79/// truncated (#236).
80pub const MAX_SEQUENCE_DEPTH: usize = 4096;
81
82/// Which ends of two tasks a sequence links.
83///
84/// `IfcSequenceEnum`, verified against IFC4 EXPRESS.
85#[derive(Debug, Clone, Copy, PartialEq, Eq)]
86#[non_exhaustive]
87pub enum SequenceType {
88    /// Successor starts after predecessor starts.
89    StartStart,
90    /// Successor finishes after predecessor starts.
91    StartFinish,
92    /// Successor starts after predecessor finishes. The common case.
93    FinishStart,
94    /// Successor finishes after predecessor finishes.
95    FinishFinish,
96    /// `.USERDEFINED.`
97    UserDefined,
98    /// `.NOTDEFINED.`
99    NotDefined,
100}
101
102impl SequenceType {
103    fn parse(token: &str) -> Option<Self> {
104        Some(match token {
105            "START_START" => Self::StartStart,
106            "START_FINISH" => Self::StartFinish,
107            "FINISH_START" => Self::FinishStart,
108            "FINISH_FINISH" => Self::FinishFinish,
109            "USERDEFINED" => Self::UserDefined,
110            "NOTDEFINED" => Self::NotDefined,
111            _ => return None,
112        })
113    }
114}
115
116/// The lag between two sequenced tasks.
117#[derive(Debug, Clone, PartialEq)]
118#[non_exhaustive]
119pub struct Lag {
120    /// The `IfcLagTime` entity.
121    pub id: EntityId,
122    /// The lag as an authored ISO 8601 duration, when stated as a duration.
123    pub duration: Option<String>,
124    /// The lag as a ratio, when stated as one.
125    ///
126    /// `IfcTimeOrRatioSelect` admits both. A ratio lag means "start when the
127    /// predecessor is 50% done" and cannot be converted to a duration without
128    /// knowing that task's own duration.
129    pub ratio: Option<f64>,
130    /// `IfcLagTime.DurationType`: whether the lag counts working time or
131    /// elapsed time (#236). Required by the schema; `None` when the record
132    /// leaves it unset or states a token outside `IfcTaskDurationEnum`.
133    pub duration_type: Option<DurationType>,
134    /// `IfcSchedulingTime.Name`, as authored (#236).
135    pub name: Option<String>,
136}
137
138/// One directed sequence link.
139#[derive(Debug, Clone, PartialEq)]
140#[non_exhaustive]
141pub struct Sequence {
142    /// The `IfcRelSequence` entity.
143    pub id: EntityId,
144    /// The predecessor task.
145    pub predecessor: EntityId,
146    /// The successor task.
147    pub successor: EntityId,
148    /// Which ends are linked, if stated.
149    pub sequence_type: Option<SequenceType>,
150    /// The `IfcLagTime` lag, if stated (IFC4 and IFC4X3).
151    pub lag: Option<Lag>,
152    /// IFC2X3's `TimeLag`, an `IfcTimeMeasure` in the project's time unit
153    /// stated on the relationship itself; `None` in IFC4 and IFC4X3, whose
154    /// lag is [`Self::lag`].
155    pub time_lag_measure: Option<f64>,
156}
157
158/// A cycle in the sequence graph.
159///
160/// A schedule whose tasks depend on each other in a loop has no valid
161/// ordering. This is data to report, not a condition to crash on.
162#[derive(Debug, Clone, PartialEq, Eq)]
163#[non_exhaustive]
164pub struct SequenceCycle {
165    /// The task the walk returned to.
166    pub repeated: EntityId,
167    /// The path taken, ending at the repeat.
168    pub path: Vec<EntityId>,
169}
170
171/// Every sequence link in the model, in file order, read against the
172/// model's declared release.
173///
174/// # Errors
175///
176/// [`ScheduleReadError::UnsupportedSchema`] or
177/// [`ScheduleReadError::MultipleSchemas`] for a header the readers cannot
178/// bind; a header with no schema reads as IFC4.
179pub fn sequences(model: &Model) -> Result<Vec<Sequence>, ScheduleReadError> {
180    let release = ReadRelease::of(model)?;
181    let mut out = Vec::new();
182    for (id, entity) in model.of_type(SEQUENCE) {
183        let (Some(predecessor), Some(successor)) = (
184            release.reference(SEQUENCE, entity, "RelatingProcess"),
185            release.reference(SEQUENCE, entity, "RelatedProcess"),
186        ) else {
187            continue;
188        };
189        let sequence_type = release
190            .token(SEQUENCE, entity, "SequenceType")
191            .and_then(SequenceType::parse);
192        let (lag, time_lag_measure) = match release.value(SEQUENCE, entity, "TimeLag") {
193            Some(Value::Ref(lag_id)) => (read_lag(model, release, *lag_id), None),
194            Some(value) => (None, value.unwrap_typed().as_f64()),
195            None => (None, None),
196        };
197        out.push(Sequence {
198            id,
199            predecessor,
200            successor,
201            sequence_type,
202            lag,
203            time_lag_measure,
204        });
205    }
206    Ok(out)
207}
208
209fn read_lag(model: &Model, release: ReadRelease, id: EntityId) -> Option<Lag> {
210    let entity = model.get(id)?;
211    if !entity.type_name.eq_ignore_ascii_case(LAG_TIME) {
212        return None;
213    }
214    let value = release.value(LAG_TIME, entity, "LagValue");
215    // IfcTimeOrRatioSelect: IfcDuration is a string, IfcRatioMeasure a real.
216    // The wrapper distinguishes them, so read both rather than guessing.
217    let duration = value
218        .and_then(|v| v.unwrap_typed().as_text())
219        .map(str::to_string);
220    let ratio = if duration.is_some() {
221        None
222    } else {
223        value.and_then(|v| v.unwrap_typed().as_f64())
224    };
225    Some(Lag {
226        id,
227        duration,
228        ratio,
229        duration_type: release
230            .token(LAG_TIME, entity, "DurationType")
231            .and_then(DurationType::parse),
232        name: release.text(LAG_TIME, entity, "Name").map(str::to_string),
233    })
234}
235
236/// Processes that must finish (or start) before `task`, in file order.
237///
238/// # Errors
239///
240/// The binding refusals of [`sequences`].
241pub fn predecessors_of(model: &Model, task: EntityId) -> Result<Vec<EntityId>, ScheduleReadError> {
242    Ok(sequences(model)?
243        .into_iter()
244        .filter(|s| s.successor == task)
245        .map(|s| s.predecessor)
246        .collect())
247}
248
249/// Processes that follow `task`, in file order.
250///
251/// # Errors
252///
253/// The binding refusals of [`sequences`].
254pub fn successors_of(model: &Model, task: EntityId) -> Result<Vec<EntityId>, ScheduleReadError> {
255    Ok(sequences(model)?
256        .into_iter()
257        .filter(|s| s.predecessor == task)
258        .map(|s| s.successor)
259        .collect())
260}
261
262/// Every process reachable downstream of `task`, depth-first.
263///
264/// Excludes the start. Returns `Err` with the offending path if the graph
265/// cycles: a schedule that loops has no valid ordering, and the loop is the
266/// answer the caller needs. Every `IfcRelSequence` is followed, whatever
267/// `IfcProcess` it relates.
268///
269/// # Errors
270///
271/// [`ScheduleReadError::Cycle`] when a process is reachable from itself,
272/// [`ScheduleReadError::SequenceDepthExceeded`] when a chain from `task` is
273/// longer than [`MAX_SEQUENCE_DEPTH`], and the binding refusals of
274/// [`sequences`].
275pub fn downstream_of(model: &Model, task: EntityId) -> Result<Vec<EntityId>, ScheduleReadError> {
276    let all = sequences(model)?;
277    downstream_in(&successor_map(&all), task)
278}
279
280/// Successors of each predecessor, in file order of the links.
281fn successor_map(all: &[Sequence]) -> HashMap<EntityId, Vec<EntityId>> {
282    let mut map: HashMap<EntityId, Vec<EntityId>> = HashMap::new();
283    for link in all {
284        map.entry(link.predecessor)
285            .or_default()
286            .push(link.successor);
287    }
288    map
289}
290
291/// [`downstream_of`] over already read links.
292///
293/// An explicit stack rather than recursion, so the depth budget, not the
294/// thread's stack, bounds the walk.
295fn downstream_in(
296    successors: &HashMap<EntityId, Vec<EntityId>>,
297    start: EntityId,
298) -> Result<Vec<EntityId>, ScheduleReadError> {
299    let mut out = Vec::new();
300    let mut seen = HashSet::new();
301    // The current path, each node with the index of its next successor.
302    let mut path: Vec<(EntityId, usize)> = vec![(start, 0)];
303    let mut on_path = HashSet::from([start]);
304    while let Some((node, next)) = path.last_mut() {
305        let node = *node;
306        let Some(&successor) = successors.get(&node).and_then(|all| all.get(*next)) else {
307            path.pop();
308            on_path.remove(&node);
309            continue;
310        };
311        *next += 1;
312        if on_path.contains(&successor) {
313            let mut cycle: Vec<EntityId> = path.iter().map(|(id, _)| *id).collect();
314            cycle.push(successor);
315            return Err(SequenceCycle {
316                repeated: successor,
317                path: cycle,
318            }
319            .into());
320        }
321        // A diamond reconverges on the same process by two routes; report it
322        // once, but still descend the first time it is seen.
323        if seen.insert(successor) {
324            out.push(successor);
325            if path.len() >= MAX_SEQUENCE_DEPTH {
326                return Err(ScheduleReadError::SequenceDepthExceeded {
327                    start,
328                    limit: MAX_SEQUENCE_DEPTH,
329                });
330            }
331            path.push((successor, 0));
332            on_path.insert(successor);
333        }
334    }
335    Ok(out)
336}
337
338/// Every `IfcProcess` in the model, in file order, per its declared release.
339pub(crate) fn processes(model: &Model) -> Result<Vec<EntityId>, ScheduleReadError> {
340    Ok(ReadRelease::of(model)?.instances_of(model, "IFCPROCESS"))
341}
342
343/// The first cycle in the whole sequence graph, if any.
344///
345/// Walks from every `IfcProcess` (tasks, procedures and events alike), so a
346/// cycle through a non-task process, or in a disconnected component, is
347/// still found (#236).
348///
349/// # Errors
350///
351/// [`ScheduleReadError::SequenceDepthExceeded`] when a chain is longer than
352/// [`MAX_SEQUENCE_DEPTH`], since a truncated search cannot say there is no
353/// cycle, and the binding refusals of [`sequences`].
354pub fn find_cycle(model: &Model) -> Result<Option<SequenceCycle>, ScheduleReadError> {
355    let all = sequences(model)?;
356    let successors = successor_map(&all);
357    // A process already reached from an earlier start had its whole
358    // downstream walked without a cycle, so walking from it again finds none.
359    let mut covered = HashSet::new();
360    for id in processes(model)? {
361        if covered.contains(&id) {
362            continue;
363        }
364        match downstream_in(&successors, id) {
365            Ok(reached) => {
366                covered.insert(id);
367                covered.extend(reached);
368            }
369            Err(ScheduleReadError::Cycle(cycle)) => return Ok(Some(cycle)),
370            Err(other) => return Err(other),
371        }
372    }
373    Ok(None)
374}
ifc_schedule/sequence/relation.rs

ifc_schedule/sequence/
relation.rs
