Skip to main content

stepq/pmi/
items.rs

1//! The representation items shape aspects stand for: from a tolerance's,
2//! dimension's or datum's shape aspect to the faces, edges and points the
3//! file names for it. See [`AspectItems`].
4
5use std::collections::hash_map::Entry;
6use std::collections::{HashMap, HashSet, VecDeque};
7use std::fmt;
8
9use crate::model::Graph;
10use crate::p21::{Exchange, Instance, Param, Record};
11use crate::record::{self, text};
12
13/// Aspects more than this many relationships from the definition, by the
14/// shortest route, are not reached ([`UnresolvedReason::TooDeep`]). The
15/// longest route in the fixtures has two.
16const MAX_DEPTH: usize = 64;
17
18/// `shape_aspect_relationship` and its subtypes, in the four schemas.
19const RELATIONSHIPS: &[&str] = &[
20    "SHAPE_ASPECT_RELATIONSHIP",
21    "ANGULAR_LOCATION",
22    "ASSEMBLY_JOINT",
23    "ASSEMBLY_SHAPE_CONSTRAINT_ITEM_RELATIONSHIP",
24    "ASSEMBLY_SHAPE_JOINT_ITEM_RELATIONSHIP",
25    "COMPONENT_FEATURE_JOINT",
26    "COMPONENT_FEATURE_RELATIONSHIP",
27    "CONNECTION_ZONE_BASED_ASSEMBLY_JOINT",
28    "CONNECTION_ZONE_INTERFACE_PLANE_RELATIONSHIP",
29    "CONNECTIVITY_DEFINITION_ITEM_RELATIONSHIP",
30    "CONTACT_FEATURE_FIT_RELATIONSHIP",
31    "DIMENSIONAL_LOCATION",
32    "DIMENSIONAL_LOCATION_WITH_DATUM_FEATURE",
33    "DIMENSIONAL_LOCATION_WITH_NORMAL_CONSTRAINT",
34    "DIMENSIONAL_LOCATION_WITH_PATH",
35    "DIRECTED_DIMENSIONAL_LOCATION",
36    "FEATURE_COMPONENT_RELATIONSHIP",
37    "FEATURE_FOR_DATUM_TARGET_RELATIONSHIP",
38    "MAKE_FROM_FEATURE_RELATIONSHIP",
39    "PATTERN_OFFSET_MEMBERSHIP",
40    "PATTERN_OMIT_MEMBERSHIP",
41    "SHAPE_ASPECT_ASSOCIATIVITY",
42    "SHAPE_ASPECT_DERIVING_RELATIONSHIP",
43    "SHAPE_ASPECT_TRANSITION",
44    "SHAPE_DEFINING_RELATIONSHIP",
45    "SHAPE_FEATURE_DEFINITION_ELEMENT_RELATIONSHIP",
46    "SHAPE_FEATURE_FIT_RELATIONSHIP",
47];
48
49/// Simple relationship records whose `shape_aspect_relationship` attributes
50/// do not come first: the number that do. Every other subtype keeps
51/// `relating_shape_aspect` and `related_shape_aspect` as attributes 2 and 3.
52const RELATIONSHIP_OFFSETS: &[(&str, usize)] = &[
53    ("CONNECTION_ZONE_INTERFACE_PLANE_RELATIONSHIP", 4),
54    ("DIMENSIONAL_LOCATION_WITH_DATUM_FEATURE", 4),
55];
56
57/// `dimensional_location` and its subtypes: dimensions, which `pmi` reads,
58/// not links between aspects.
59const LOCATIONS: &[&str] = &[
60    "ANGULAR_LOCATION",
61    "DIMENSIONAL_LOCATION",
62    "DIMENSIONAL_LOCATION_WITH_DATUM_FEATURE",
63    "DIMENSIONAL_LOCATION_WITH_NORMAL_CONSTRAINT",
64    "DIMENSIONAL_LOCATION_WITH_PATH",
65    "DIRECTED_DIMENSIONAL_LOCATION",
66];
67
68/// `dimensional_size` and its subtypes.
69const SIZES: &[&str] = &[
70    "ANGULAR_SIZE",
71    "DIMENSIONAL_SIZE",
72    "DIMENSIONAL_SIZE_WITH_DATUM_FEATURE",
73    "DIMENSIONAL_SIZE_WITH_PATH",
74    "EXTERNALLY_DEFINED_DIMENSION_DEFINITION",
75];
76
77/// `item_identified_representation_usage` and its subtypes.
78const USAGES: &[&str] = &[
79    "ITEM_IDENTIFIED_REPRESENTATION_USAGE",
80    "CHAIN_BASED_GEOMETRIC_ITEM_SPECIFIC_USAGE",
81    "CHAIN_BASED_ITEM_IDENTIFIED_REPRESENTATION_USAGE",
82    "DRAUGHTING_MODEL_ITEM_ASSOCIATION",
83    "DRAUGHTING_MODEL_ITEM_ASSOCIATION_WITH_EXTERNAL_IMAGE_PLACEMENT",
84    "DRAUGHTING_MODEL_ITEM_ASSOCIATION_WITH_PLACEHOLDER",
85    "GEOMETRIC_ITEM_SPECIFIC_USAGE",
86    "MECHANICAL_DESIGN_REQUIREMENT_ITEM_ASSOCIATION",
87    "PMI_REQUIREMENT_ITEM_ASSOCIATION",
88];
89
90/// `draughting_model_item_association` and its subtypes: presentation.
91const PRESENTATION: &[&str] = &[
92    "DRAUGHTING_MODEL_ITEM_ASSOCIATION",
93    "DRAUGHTING_MODEL_ITEM_ASSOCIATION_WITH_EXTERNAL_IMAGE_PLACEMENT",
94    "DRAUGHTING_MODEL_ITEM_ASSOCIATION_WITH_PLACEHOLDER",
95];
96
97/// `composite_shape_aspect` and its subtypes: their components are the
98/// related sides of their plain relationships.
99const COMPOSITES: &[&str] = &[
100    "ALL_AROUND_SHAPE_ASPECT",
101    "BETWEEN_SHAPE_ASPECT",
102    "COMMON_DATUM",
103    "COMPOSITE_GROUP_SHAPE_ASPECT",
104    "COMPOSITE_SHAPE_ASPECT",
105    "COMPOSITE_UNIT_SHAPE_ASPECT",
106    "CONTINUOUS_SHAPE_ASPECT",
107];
108
109/// `derived_shape_aspect` and its subtypes.
110const DERIVED: &[&str] = &[
111    "APEX",
112    "CENTRE_OF_SYMMETRY",
113    "DERIVED_SHAPE_ASPECT",
114    "EXTENSION",
115    "GEOMETRIC_ALIGNMENT",
116    "GEOMETRIC_CONTACT",
117    "GEOMETRIC_INTERSECTION",
118    "PARALLEL_OFFSET",
119    "PERPENDICULAR_TO",
120    "TANGENT",
121];
122
123/// `datum_feature` and its subtypes.
124const DATUM_FEATURES: &[&str] = &[
125    "DATUM_FEATURE",
126    "DIMENSIONAL_LOCATION_WITH_DATUM_FEATURE",
127    "DIMENSIONAL_SIZE_WITH_DATUM_FEATURE",
128];
129
130/// `datum_target` and its subtypes.
131const DATUM_TARGETS: &[&str] = &["DATUM_TARGET", "PLACED_DATUM_TARGET_FEATURE"];
132
133/// `datum` and its subtypes.
134const DATUMS: &[&str] = &["COMMON_DATUM", "DATUM"];
135
136/// How a route reaches an aspect from the one before it.
137#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
138#[cfg_attr(feature = "serde", derive(serde::Serialize))]
139#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
140#[non_exhaustive]
141pub enum StepKind {
142    /// From a composite (`composite_shape_aspect` and its subtypes,
143    /// `common_datum` included) to a component, by a plain
144    /// `shape_aspect_relationship`: the value applies to the group, not to
145    /// each member.
146    Component,
147    /// From a derived aspect (`centre_of_symmetry`, `apex`, …) to one it is
148    /// derived from, by a `shape_aspect_deriving_relationship`: the faces an
149    /// axis or a centre plane is derived from, not what is toleranced.
150    DerivedFrom,
151    /// From a datum to a datum feature whose plain relationship names it
152    /// (the schema's `datum_feature` WR1).
153    DatumFeature,
154    /// From a datum to a datum target whose plain relationship names it.
155    DatumTarget,
156    /// From a datum target to the feature it lies on, by a
157    /// `feature_for_datum_target_relationship`.
158    TargetFeature,
159}
160
161impl StepKind {
162    const ALL: [Self; 5] = [
163        Self::Component,
164        Self::DerivedFrom,
165        Self::DatumFeature,
166        Self::DatumTarget,
167        Self::TargetFeature,
168    ];
169
170    fn bit(self) -> u8 {
171        match self {
172            Self::Component => 1,
173            Self::DerivedFrom => 2,
174            Self::DatumFeature => 4,
175            Self::DatumTarget => 8,
176            Self::TargetFeature => 16,
177        }
178    }
179}
180
181/// A set of [`StepKind`]s: the kinds of step one route takes. The empty set
182/// is a usage naming the item directly.
183#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Hash, PartialOrd, Ord)]
184pub struct StepKinds(u8);
185
186impl StepKinds {
187    /// No kind: a direct usage.
188    pub const NONE: Self = Self(0);
189    /// Every kind.
190    pub const ALL: Self = Self(31);
191
192    /// This set with `kind` added.
193    #[must_use]
194    pub fn with(self, kind: StepKind) -> Self {
195        Self(self.0 | kind.bit())
196    }
197
198    /// True if `kind` is in the set.
199    pub fn contains(self, kind: StepKind) -> bool {
200        self.0 & kind.bit() != 0
201    }
202
203    /// True if every kind in this set is in `other`.
204    pub fn is_subset(self, other: Self) -> bool {
205        self.0 & !other.0 == 0
206    }
207
208    /// True if the set is empty: a direct usage.
209    pub fn is_empty(self) -> bool {
210        self.0 == 0
211    }
212
213    /// The kinds in the set, in [`StepKind`] order.
214    pub fn iter(self) -> impl Iterator<Item = StepKind> {
215        StepKind::ALL
216            .into_iter()
217            .filter(move |&kind| self.contains(kind))
218    }
219}
220
221impl FromIterator<StepKind> for StepKinds {
222    fn from_iter<I: IntoIterator<Item = StepKind>>(kinds: I) -> Self {
223        kinds.into_iter().fold(Self::NONE, Self::with)
224    }
225}
226
227#[cfg(feature = "serde")]
228impl serde::Serialize for StepKinds {
229    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
230        serializer.collect_seq(self.iter())
231    }
232}
233
234/// The distinct [`StepKinds`] of a set of routes, at most 32 (one per subset
235/// of the five kinds), as a bit per subset.
236#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
237struct Routes(u32);
238
239impl Routes {
240    const DIRECT: Self = Self(1);
241
242    /// Every route here, extended by a step of `kind`.
243    fn then(self, kind: StepKind) -> Self {
244        let mut extended = 0;
245        for subset in 0..32u8 {
246            if self.0 & (1 << subset) != 0 {
247                extended |= 1 << (subset | kind.bit());
248            }
249        }
250        Self(extended)
251    }
252
253    fn sets(self) -> Vec<StepKinds> {
254        (0..32u8)
255            .filter(|subset| self.0 & (1 << subset) != 0)
256            .map(StepKinds)
257            .collect()
258    }
259}
260
261/// One `item_identified_representation_usage`, of any subtype.
262#[derive(Debug, Clone, PartialEq, Eq)]
263#[cfg_attr(feature = "serde", derive(serde::Serialize))]
264#[non_exhaustive]
265pub struct ItemUsage {
266    /// The usage's `#id`.
267    pub instance: u64,
268    /// Its kind, and whether [`AspectItems::resolve`] follows it.
269    pub kind: ItemUsageKind,
270    /// Its upper-cased entity types, joined with `+`.
271    pub entity: String,
272    /// `name`.
273    pub name: Option<String>,
274    /// `description`.
275    pub description: Option<String>,
276    /// `definition`: what its items stand for.
277    pub definition: u64,
278    /// `used_representation` as written; `None` if it is not a reference.
279    /// stepq does not check that it lists the items (the schema's WR1): 510
280    /// of the 2,587 items the NIST files identify lie in a representation
281    /// related to it instead.
282    pub used_representation: Option<u64>,
283    /// `identified_item`: one item, or the members of a typed
284    /// `set_representation_item` or `list_representation_item`, in order;
285    /// empty if it is neither.
286    pub items: Vec<u64>,
287}
288
289/// What an [`ItemUsage`] is.
290#[derive(Debug, Clone, Copy, PartialEq, Eq)]
291#[cfg_attr(feature = "serde", derive(serde::Serialize))]
292#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
293#[non_exhaustive]
294pub enum ItemUsageKind {
295    /// A simple `geometric_item_specific_usage`. Followed.
296    GeometricItemSpecific,
297    /// A simple `item_identified_representation_usage` of no subtype.
298    /// Followed.
299    ItemIdentified,
300    /// A `draughting_model_item_association`, of any subtype: it ties
301    /// semantic PMI to its presentation. Listed, never followed.
302    Presentation,
303    /// Any other subtype (a chain-based usage, which needs an assembly path,
304    /// a requirement association), a complex instance, or a usage whose
305    /// `identified_item` is neither a reference nor a typed set or list of
306    /// them. Reported, never followed.
307    Other,
308}
309
310/// One step of a route: a relationship followed to an aspect.
311#[derive(Debug, Clone, Copy, PartialEq, Eq)]
312#[cfg_attr(feature = "serde", derive(serde::Serialize))]
313#[non_exhaustive]
314pub struct Step {
315    /// The relationship's `#id`.
316    pub relationship: u64,
317    /// What kind of step it is.
318    pub kind: StepKind,
319    /// The aspect it leads to.
320    pub aspect: u64,
321}
322
323/// What [`AspectItems::resolve`] found for one definition.
324#[derive(Debug, Clone, PartialEq, Eq)]
325#[cfg_attr(feature = "serde", derive(serde::Serialize))]
326#[non_exhaustive]
327pub struct Resolution {
328    /// The `#id` asked about.
329    pub definition: u64,
330    /// Every item reached, each once, in the order found (nearest first).
331    pub items: Vec<ResolvedItem>,
332    /// Every point where a route stopped short of an item, with the reason.
333    pub unresolved: Vec<Unresolved>,
334}
335
336impl Resolution {
337    /// True if no route stopped short: [`items`](Self::items) are all the
338    /// definition stands for.
339    pub fn is_complete(&self) -> bool {
340        self.unresolved.is_empty()
341    }
342
343    /// The `#id`s of the items some route reaches using only steps of the
344    /// `allowed` kinds, each once, in the order found. Items a usage names
345    /// directly are always included; `StepKinds::NONE` gives only those.
346    pub fn item_ids(&self, allowed: StepKinds) -> Vec<u64> {
347        self.items
348            .iter()
349            .filter(|item| {
350                item.route_kinds
351                    .iter()
352                    .any(|kinds| kinds.is_subset(allowed))
353            })
354            .map(|item| item.item)
355            .collect()
356    }
357}
358
359/// One item a definition stands for.
360#[derive(Debug, Clone, PartialEq, Eq)]
361#[cfg_attr(feature = "serde", derive(serde::Serialize))]
362#[non_exhaustive]
363pub struct ResolvedItem {
364    /// The item's `#id`.
365    pub item: u64,
366    /// Its upper-cased entity types, joined with `+`, such as
367    /// `ADVANCED_FACE`; empty if it is not defined.
368    pub entity: String,
369    /// The usage that names it at the end of [`via`](Self::via).
370    pub usage: u64,
371    /// One shortest route from the definition to the aspect that usage
372    /// names; empty if it names the definition itself.
373    pub via: Vec<Step>,
374    /// The kinds of step each route to the item takes, each distinct set
375    /// once, in a fixed order: the empty set if a usage names the definition
376    /// itself. A value stated on a composite applies to the group, and an
377    /// axis's derived-from faces are not what it tolerances, so a caller
378    /// keeps these apart.
379    pub route_kinds: Vec<StepKinds>,
380}
381
382/// Where a route stopped short of an item.
383#[derive(Debug, Clone, PartialEq, Eq)]
384#[cfg_attr(feature = "serde", derive(serde::Serialize))]
385#[non_exhaustive]
386pub struct Unresolved {
387    /// The aspect where it stopped.
388    pub aspect: u64,
389    /// Its upper-cased entity types, joined with `+`; empty if it is not
390    /// defined.
391    pub entity: String,
392    /// One shortest route to it.
393    pub via: Vec<Step>,
394    /// Why it stopped.
395    pub reason: UnresolvedReason,
396}
397
398/// Why a route stopped; see [`Unresolved`].
399#[derive(Debug, Clone, PartialEq, Eq)]
400#[cfg_attr(feature = "serde", derive(serde::Serialize))]
401#[cfg_attr(feature = "serde", serde(tag = "kind", rename_all = "snake_case"))]
402#[non_exhaustive]
403pub enum UnresolvedReason {
404    /// No followed usage names the aspect, and no rule leads on from it.
405    NoUsage,
406    /// A `product_definition_shape`: the whole shape of a product, not a
407    /// part of it.
408    WholeShape,
409    /// A plain `shape_aspect_relationship` from here, or into a datum from
410    /// something that is neither a datum feature nor a datum target, which
411    /// no rule gives a meaning to; only a description string says what it
412    /// is.
413    NotFollowed {
414        /// The relationship.
415        relationship: u64,
416        /// The aspect on its other side.
417        related: u64,
418    },
419    /// A relationship of another subtype, or a complex one, from here, or
420    /// into a datum.
421    UnsupportedRelationship {
422        /// The relationship.
423        relationship: u64,
424        /// Its upper-cased entity types, joined with `+`.
425        entity: String,
426    },
427    /// A usage of kind [`Other`](ItemUsageKind::Other) names the aspect.
428    UnsupportedUsage {
429        /// The usage.
430        usage: u64,
431    },
432    /// A definition stepq does not resolve: a dimension, or a relationship,
433    /// as a tolerance's target.
434    UnsupportedDefinition,
435    /// A `component_path_shape_aspect`, which names another product's
436    /// aspect through an assembly occurrence.
437    ComponentPath,
438    /// A usage names an item that is not defined.
439    MissingItem {
440        /// The usage.
441        usage: u64,
442        /// The item.
443        item: u64,
444    },
445    /// The aspect is not defined.
446    Missing,
447    /// The relationships lead back to an aspect already on a route to here.
448    Cycle,
449    /// The aspect lies 64 relationships from the definition by the
450    /// shortest route, and its steps on are not followed.
451    TooDeep,
452}
453
454impl fmt::Display for UnresolvedReason {
455    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
456        match self {
457            Self::NoUsage => f.write_str("nothing names its items"),
458            Self::WholeShape => f.write_str("the whole shape of a product"),
459            Self::NotFollowed {
460                relationship,
461                related,
462            } => write!(
463                f,
464                "relationship #{relationship} to #{related} has no stated meaning"
465            ),
466            Self::UnsupportedRelationship {
467                relationship,
468                entity,
469            } => write!(f, "relationship #{relationship} ({entity}) is not read"),
470            Self::UnsupportedUsage { usage } => write!(f, "usage #{usage} is not read"),
471            Self::UnsupportedDefinition => f.write_str("a dimension or relationship as a target"),
472            Self::ComponentPath => f.write_str("an aspect of another product, by assembly path"),
473            Self::MissingItem { usage, item } => {
474                write!(f, "usage #{usage} names #{item}, which is not defined")
475            }
476            Self::Missing => f.write_str("not defined"),
477            Self::Cycle => f.write_str("the relationships lead back to it"),
478            Self::TooDeep => f.write_str("64 relationships away, not followed further"),
479        }
480    }
481}
482
483/// A definition whose [`AspectItems::resolve`] lists an item, from
484/// [`AspectItems::naming`].
485#[derive(Debug, Clone, PartialEq, Eq)]
486#[cfg_attr(feature = "serde", derive(serde::Serialize))]
487#[non_exhaustive]
488pub struct Naming {
489    /// The definition's `#id`.
490    pub definition: u64,
491    /// The kinds of step each of its routes to the item takes, as in
492    /// [`ResolvedItem::route_kinds`].
493    pub route_kinds: Vec<StepKinds>,
494}
495
496impl Naming {
497    /// True if a usage names the item for the definition itself.
498    pub fn is_direct(&self) -> bool {
499        self.route_kinds.contains(&StepKinds::NONE)
500    }
501}
502
503/// What a relationship is to the walk.
504#[derive(Debug, Clone, Copy, PartialEq, Eq)]
505enum RelationshipKind {
506    /// A simple `shape_aspect_relationship` of no subtype.
507    Plain,
508    /// A simple `shape_aspect_deriving_relationship`.
509    Deriving,
510    /// A simple `feature_for_datum_target_relationship`.
511    TargetFeature,
512    /// A dimension: a `dimensional_location`, of any subtype.
513    Location,
514    /// Any other subtype, or a complex instance.
515    Other,
516}
517
518#[derive(Debug, Clone)]
519struct Relationship {
520    instance: u64,
521    kind: RelationshipKind,
522    relating: u64,
523    /// `None` if it is not a reference: the relationship is reported.
524    related: Option<u64>,
525}
526
527/// What an aspect is, for the rules.
528#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
529struct Class(u8);
530
531impl Class {
532    const COMPOSITE: u8 = 1;
533    const DERIVED: u8 = 2;
534    const DATUM_FEATURE: u8 = 4;
535    const DATUM_TARGET: u8 = 8;
536    const DATUM: u8 = 16;
537    const BETWEEN: u8 = 32;
538
539    fn of(names: &[String]) -> Self {
540        let has = |set: &[&str]| names.iter().any(|name| set.contains(&name.as_str()));
541        let mut class = 0;
542        for (set, bit) in [
543            (COMPOSITES, Self::COMPOSITE),
544            (DERIVED, Self::DERIVED),
545            (DATUM_FEATURES, Self::DATUM_FEATURE),
546            (DATUM_TARGETS, Self::DATUM_TARGET),
547            (DATUMS, Self::DATUM),
548            (&["BETWEEN_SHAPE_ASPECT"], Self::BETWEEN),
549        ] {
550            if has(set) {
551                class |= bit;
552            }
553        }
554        Self(class)
555    }
556
557    fn is(self, bit: u8) -> bool {
558        self.0 & bit != 0
559    }
560}
561
562/// The representation items shape aspects stand for, read once per file
563/// from every `item_identified_representation_usage` and every
564/// `shape_aspect_relationship`.
565///
566/// [`resolve`](Self::resolve) follows only links whose meaning the schema
567/// fixes, from a definition (a shape aspect, datum, or dimension with its
568/// own usage) to the items the file names for it:
569///
570/// * a simple `geometric_item_specific_usage` or plain
571///   `item_identified_representation_usage`, to its `identified_item` (one
572///   reference, or the members of a typed `set_representation_item` or
573///   `list_representation_item`);
574/// * [`Component`](StepKind::Component), [`DerivedFrom`](StepKind::DerivedFrom),
575///   [`DatumFeature`](StepKind::DatumFeature),
576///   [`DatumTarget`](StepKind::DatumTarget) and
577///   [`TargetFeature`](StepKind::TargetFeature) steps between aspects.
578///
579/// Presentation usages are listed in [`usages`](Self::usages) and never
580/// followed. Everything else that could lead to items is reported in
581/// [`Resolution::unresolved`] with a reason: nothing is guessed, and
582/// nothing is skipped. Each aspect is expanded once per resolution, so a
583/// resolution takes time linear in the file however its aspects share
584/// components. The index owns its data; `resolve` takes the graph again to
585/// name entity types.
586///
587/// stepq does not say which face of a group a value measures, does not
588/// check that items lie in `used_representation`, and does not follow
589/// aspect shapes given through `property_definition` (the same pattern
590/// carries property values such as a centroid).
591#[derive(Debug, Clone)]
592pub struct AspectItems {
593    usages: Vec<ItemUsage>,
594    /// Each usage's items, each once, for resolving.
595    distinct: Vec<Vec<u64>>,
596    /// Followed usages, by definition.
597    by_definition: HashMap<u64, Vec<usize>>,
598    /// Followed usages, by item.
599    by_item: HashMap<u64, Vec<usize>>,
600    /// Usages of kind Other, by definition.
601    unsupported: HashMap<u64, Vec<u64>>,
602    relationships: Vec<Relationship>,
603    /// Relationships by relating aspect.
604    from: HashMap<u64, Vec<usize>>,
605    /// Relationships by related aspect.
606    to: HashMap<u64, Vec<usize>>,
607    /// What each aspect a usage or relationship names is.
608    classes: HashMap<u64, Class>,
609    /// The aspects `resolve` stops at without reading their usages: not
610    /// defined, a whole shape, an assembly path, or a definition it does
611    /// not resolve.
612    stops: HashSet<u64>,
613}
614
615fn names(exchange: &Exchange<'_>, instance: &Instance) -> Vec<String> {
616    exchange
617        .records(instance)
618        .map(|record| record::upper(record.name()))
619        .collect()
620}
621
622fn entity(exchange: &Exchange<'_>, id: u64) -> String {
623    exchange
624        .get(id)
625        .map(|instance| record::entity(exchange, instance))
626        .unwrap_or_default()
627}
628
629/// The members of an `identified_item`: one reference, or a typed set or
630/// list of them.
631fn identified_items(param: Option<Param<'_>>) -> Option<Vec<u64>> {
632    match param? {
633        Param::Reference(item) => Some(vec![item]),
634        Param::Typed(typed)
635            if typed.is("SET_REPRESENTATION_ITEM") || typed.is("LIST_REPRESENTATION_ITEM") =>
636        {
637            let items = typed
638                .param(0)?
639                .list()?
640                .map(|member| member.reference())
641                .collect::<Option<Vec<u64>>>()?;
642            (!items.is_empty()).then_some(items)
643        }
644        _ => None,
645    }
646}
647
648impl AspectItems {
649    /// Reads every usage and relationship of the file behind `graph`, built
650    /// with [`Graph::new`] or [`Graph::build`]. Never fails: a usage or
651    /// relationship that cannot be read is reported where a resolution
652    /// meets it.
653    pub fn new(graph: &Graph<'_>) -> Self {
654        let exchange = graph.exchange();
655        let mut index = Self {
656            usages: Vec::new(),
657            distinct: Vec::new(),
658            by_definition: HashMap::new(),
659            by_item: HashMap::new(),
660            unsupported: HashMap::new(),
661            relationships: Vec::new(),
662            from: HashMap::new(),
663            to: HashMap::new(),
664            classes: HashMap::new(),
665            stops: HashSet::new(),
666        };
667        for instance in exchange.instances() {
668            let names = names(exchange, instance);
669            if names.iter().any(|name| USAGES.contains(&name.as_str())) {
670                index.usage(exchange, instance, &names);
671            } else if names
672                .iter()
673                .any(|name| RELATIONSHIPS.contains(&name.as_str()))
674            {
675                index.relationship(exchange, instance, &names);
676            }
677        }
678        let mut aspects: HashSet<u64> = index.by_definition.keys().copied().collect();
679        aspects.extend(index.unsupported.keys());
680        for relationship in &index.relationships {
681            aspects.insert(relationship.relating);
682            aspects.extend(relationship.related);
683        }
684        for aspect in aspects {
685            let Some(instance) = exchange.get(aspect) else {
686                index.stops.insert(aspect);
687                continue;
688            };
689            let names = names(exchange, instance);
690            if stop(&names).is_some() {
691                index.stops.insert(aspect);
692            }
693            index.classes.insert(aspect, Class::of(&names));
694        }
695        index
696            .by_item
697            .retain(|&item, _| exchange.get(item).is_some());
698        index
699    }
700
701    fn usage(&mut self, exchange: &Exchange<'_>, instance: &Instance, names: &[String]) {
702        let record: Option<Record<'_>> = if instance.is_complex() {
703            record::partial(exchange, instance, "ITEM_IDENTIFIED_REPRESENTATION_USAGE")
704        } else {
705            exchange.records(instance).next()
706        };
707        let Some(record) = record else {
708            return;
709        };
710        let Some(definition) = record::reference(record.param(2).as_ref()) else {
711            return;
712        };
713        let items = identified_items(record.param(4));
714        let simple = |name: &str| !instance.is_complex() && names == [name];
715        let kind = if names
716            .iter()
717            .any(|name| PRESENTATION.contains(&name.as_str()))
718        {
719            ItemUsageKind::Presentation
720        } else if items.is_none() {
721            ItemUsageKind::Other
722        } else if simple("GEOMETRIC_ITEM_SPECIFIC_USAGE") {
723            ItemUsageKind::GeometricItemSpecific
724        } else if simple("ITEM_IDENTIFIED_REPRESENTATION_USAGE") {
725            ItemUsageKind::ItemIdentified
726        } else {
727            ItemUsageKind::Other
728        };
729        let index = self.usages.len();
730        let mut seen = HashSet::new();
731        let distinct: Vec<u64> = items
732            .iter()
733            .flatten()
734            .copied()
735            .filter(|&item| seen.insert(item))
736            .collect();
737        match kind {
738            ItemUsageKind::GeometricItemSpecific | ItemUsageKind::ItemIdentified => {
739                self.by_definition
740                    .entry(definition)
741                    .or_default()
742                    .push(index);
743                for &item in &distinct {
744                    self.by_item.entry(item).or_default().push(index);
745                }
746            }
747            ItemUsageKind::Other => {
748                self.unsupported
749                    .entry(definition)
750                    .or_default()
751                    .push(instance.id);
752            }
753            ItemUsageKind::Presentation => {}
754        }
755        self.distinct.push(distinct);
756        self.usages.push(ItemUsage {
757            instance: instance.id,
758            kind,
759            entity: names.join("+"),
760            name: text(record.param(0)),
761            description: text(record.param(1)),
762            definition,
763            used_representation: record::reference(record.param(3).as_ref()),
764            items: items.unwrap_or_default(),
765        });
766    }
767
768    fn relationship(&mut self, exchange: &Exchange<'_>, instance: &Instance, names: &[String]) {
769        let (record, offset) = if instance.is_complex() {
770            (
771                record::partial(exchange, instance, "SHAPE_ASPECT_RELATIONSHIP"),
772                0,
773            )
774        } else {
775            let offset = RELATIONSHIP_OFFSETS
776                .iter()
777                .find(|(name, _)| names == [*name])
778                .map_or(0, |(_, offset)| *offset);
779            (exchange.records(instance).next(), offset)
780        };
781        let Some(record) = record else {
782            return;
783        };
784        // A relationship whose relating aspect cannot be read belongs to no
785        // aspect; one whose related aspect cannot be read is reported from
786        // its relating one.
787        let Some(relating) = record::reference(record.param(offset + 2).as_ref()) else {
788            return;
789        };
790        let related = record::reference(record.param(offset + 3).as_ref());
791        let simple = |name: &str| !instance.is_complex() && names == [name];
792        let kind = if related.is_none() {
793            RelationshipKind::Other
794        } else if names.iter().any(|name| LOCATIONS.contains(&name.as_str())) {
795            RelationshipKind::Location
796        } else if simple("SHAPE_ASPECT_RELATIONSHIP") {
797            RelationshipKind::Plain
798        } else if simple("SHAPE_ASPECT_DERIVING_RELATIONSHIP") {
799            RelationshipKind::Deriving
800        } else if simple("FEATURE_FOR_DATUM_TARGET_RELATIONSHIP") {
801            RelationshipKind::TargetFeature
802        } else {
803            RelationshipKind::Other
804        };
805        let index = self.relationships.len();
806        self.relationships.push(Relationship {
807            instance: instance.id,
808            kind,
809            relating,
810            related,
811        });
812        self.from.entry(relating).or_default().push(index);
813        if let Some(related) = related {
814            self.to.entry(related).or_default().push(index);
815        }
816    }
817
818    /// Every `item_identified_representation_usage` whose `definition` is a
819    /// reference, in file order, presentation links included.
820    pub fn usages(&self) -> &[ItemUsage] {
821        &self.usages
822    }
823
824    fn class(&self, aspect: u64) -> Class {
825        self.classes.get(&aspect).copied().unwrap_or_default()
826    }
827
828    /// The steps from `#aspect`, the reasons it stops there, and the
829    /// relationships from it that are not read.
830    fn steps(&self, aspect: u64, class: Class) -> (Vec<Step>, Vec<UnresolvedReason>, Vec<u64>) {
831        let mut steps = Vec::new();
832        let mut refused = Vec::new();
833        let mut others = Vec::new();
834        for &index in self.from.get(&aspect).into_iter().flatten() {
835            let relationship = &self.relationships[index];
836            let Some(related) = relationship.related else {
837                others.push(relationship.instance);
838                continue;
839            };
840            let basis = (class.is(Class::DATUM_FEATURE) || class.is(Class::DATUM_TARGET))
841                && self.class(related).is(Class::DATUM);
842            match relationship.kind {
843                // A datum feature's or target's basis; a between aspect's
844                // start and end features, which bound its region.
845                RelationshipKind::Plain if basis || class.is(Class::BETWEEN) => {}
846                RelationshipKind::Plain if class.is(Class::COMPOSITE) => steps.push(Step {
847                    relationship: relationship.instance,
848                    kind: StepKind::Component,
849                    aspect: related,
850                }),
851                RelationshipKind::Plain => refused.push(UnresolvedReason::NotFollowed {
852                    relationship: relationship.instance,
853                    related,
854                }),
855                RelationshipKind::Deriving if class.is(Class::DERIVED) => steps.push(Step {
856                    relationship: relationship.instance,
857                    kind: StepKind::DerivedFrom,
858                    aspect: related,
859                }),
860                // Read from the target's side, and dimensions.
861                RelationshipKind::TargetFeature | RelationshipKind::Location => {}
862                RelationshipKind::Deriving | RelationshipKind::Other => {
863                    others.push(relationship.instance);
864                }
865            }
866        }
867        for &index in self.to.get(&aspect).into_iter().flatten() {
868            let relationship = &self.relationships[index];
869            let relating = relationship.relating;
870            let into_datum = class.is(Class::DATUM);
871            match relationship.kind {
872                RelationshipKind::Plain if into_datum => {
873                    let from = self.class(relating);
874                    let kind = if from.is(Class::DATUM_FEATURE) {
875                        Some(StepKind::DatumFeature)
876                    } else if from.is(Class::DATUM_TARGET) {
877                        Some(StepKind::DatumTarget)
878                    } else {
879                        None
880                    };
881                    match kind {
882                        Some(kind) => steps.push(Step {
883                            relationship: relationship.instance,
884                            kind,
885                            aspect: relating,
886                        }),
887                        // A common datum's component: read from its side.
888                        None if from.is(Class::COMPOSITE) => {}
889                        None => refused.push(UnresolvedReason::NotFollowed {
890                            relationship: relationship.instance,
891                            related: relating,
892                        }),
893                    }
894                }
895                RelationshipKind::TargetFeature if class.is(Class::DATUM_TARGET) => {
896                    steps.push(Step {
897                        relationship: relationship.instance,
898                        kind: StepKind::TargetFeature,
899                        aspect: relating,
900                    });
901                }
902                RelationshipKind::Other if into_datum || class.is(Class::DATUM_TARGET) => {
903                    others.push(relationship.instance);
904                }
905                _ => {}
906            }
907        }
908        (steps, refused, others)
909    }
910
911    /// What `#definition` (a shape aspect, datum, or dimension with its own
912    /// usage) stands for: each item it reaches, once, with one shortest
913    /// route and the kinds of step every route takes; and each point where a
914    /// route stopped, with the reason. `graph` must be the graph the index
915    /// was read from.
916    pub fn resolve(&self, graph: &Graph<'_>, definition: u64) -> Resolution {
917        let exchange = graph.exchange();
918        let walked = self.walk(exchange, definition);
919        let routes = routes(definition, &walked.edges);
920        let mut out = Resolution {
921            definition,
922            items: Vec::new(),
923            unresolved: Vec::new(),
924        };
925        let mut items: HashMap<u64, (usize, Routes)> = HashMap::new();
926        for &aspect in &walked.order {
927            let aspect_routes = routes.get(&aspect).copied().unwrap_or_default();
928            for &index in self.by_definition.get(&aspect).into_iter().flatten() {
929                let usage = &self.usages[index];
930                for &item in &self.distinct[index] {
931                    if exchange.get(item).is_none() {
932                        continue;
933                    }
934                    if let Some((_, found)) = items.get_mut(&item) {
935                        found.0 |= aspect_routes.0;
936                        continue;
937                    }
938                    items.insert(item, (out.items.len(), aspect_routes));
939                    out.items.push(ResolvedItem {
940                        item,
941                        entity: entity(exchange, item),
942                        usage: usage.instance,
943                        via: walked.via(aspect),
944                        route_kinds: Vec::new(),
945                    });
946                }
947            }
948        }
949        for (index, found) in items.into_values() {
950            out.items[index].route_kinds = found.sets();
951        }
952        out.unresolved = walked
953            .stops
954            .iter()
955            .map(|(aspect, reason)| Unresolved {
956                aspect: *aspect,
957                entity: entity(exchange, *aspect),
958                via: walked.via(*aspect),
959                reason: reason.clone(),
960            })
961            .collect();
962        // Cycles: a step back to an aspect on the current depth-first path.
963        for (from, step) in back_edges(definition, &walked.edges) {
964            let mut via = walked.via(from);
965            via.push(step);
966            out.unresolved.push(Unresolved {
967                aspect: step.aspect,
968                entity: entity(exchange, step.aspect),
969                via,
970                reason: UnresolvedReason::Cycle,
971            });
972        }
973        out
974    }
975
976    /// Walks from `#definition` breadth first, each aspect once: the
977    /// aspects whose items it lists, how each was first reached, the steps
978    /// on from each, and where it stopped.
979    fn walk(&self, exchange: &Exchange<'_>, definition: u64) -> Walked {
980        let mut walked = Walked {
981            order: Vec::new(),
982            reached: HashMap::from([(definition, (0, None))]),
983            edges: HashMap::new(),
984            stops: Vec::new(),
985        };
986        let mut queue = VecDeque::from([definition]);
987        while let Some(aspect) = queue.pop_front() {
988            let depth = walked.reached[&aspect].0;
989            // An aspect it stops at lists none of its items, as `naming`
990            // does not.
991            let Some(instance) = exchange.get(aspect) else {
992                walked.stops.push((aspect, UnresolvedReason::Missing));
993                continue;
994            };
995            let names = names(exchange, instance);
996            if let Some(reason) = stop(&names) {
997                walked.stops.push((aspect, reason));
998                continue;
999            }
1000            walked.order.push(aspect);
1001            let steps = self.facts(exchange, aspect, &names, &mut walked.stops);
1002            if steps.is_empty() {
1003                continue;
1004            }
1005            if depth >= MAX_DEPTH {
1006                walked.stops.push((aspect, UnresolvedReason::TooDeep));
1007                continue;
1008            }
1009            for step in &steps {
1010                if let Entry::Vacant(entry) = walked.reached.entry(step.aspect) {
1011                    entry.insert((depth + 1, Some((aspect, *step))));
1012                    queue.push_back(step.aspect);
1013                }
1014            }
1015            walked.edges.insert(aspect, steps);
1016        }
1017        walked
1018    }
1019
1020    /// What `#aspect` states: its stops, pushed to `stops`, and its steps
1021    /// on, returned.
1022    fn facts(
1023        &self,
1024        exchange: &Exchange<'_>,
1025        aspect: u64,
1026        names: &[String],
1027        stops: &mut Vec<(u64, UnresolvedReason)>,
1028    ) -> Vec<Step> {
1029        let mut stated = false;
1030        for &index in self.by_definition.get(&aspect).into_iter().flatten() {
1031            stated = true;
1032            let usage = &self.usages[index];
1033            for &item in &self.distinct[index] {
1034                if exchange.get(item).is_none() {
1035                    stops.push((
1036                        aspect,
1037                        UnresolvedReason::MissingItem {
1038                            usage: usage.instance,
1039                            item,
1040                        },
1041                    ));
1042                }
1043            }
1044        }
1045        for &usage in self.unsupported.get(&aspect).into_iter().flatten() {
1046            stated = true;
1047            stops.push((aspect, UnresolvedReason::UnsupportedUsage { usage }));
1048        }
1049        let (onward, reasons, others) = self.steps(aspect, Class::of(names));
1050        stated |= !reasons.is_empty() || !others.is_empty();
1051        stops.extend(reasons.into_iter().map(|reason| (aspect, reason)));
1052        for relationship in others {
1053            stops.push((
1054                aspect,
1055                UnresolvedReason::UnsupportedRelationship {
1056                    relationship,
1057                    entity: entity(exchange, relationship),
1058                },
1059            ));
1060        }
1061        if !stated && onward.is_empty() {
1062            stops.push((aspect, UnresolvedReason::NoUsage));
1063        }
1064        onward
1065    }
1066
1067    /// The definitions whose [`resolve`](Self::resolve) lists `#item`, in
1068    /// ascending order of `#id`, each with the kinds of step its routes
1069    /// take: walked back from the usages that name the item, each aspect
1070    /// once. Empty if no followed usage names it. Both limit routes to 64
1071    /// relationships, `resolve` counting from the definition and this from
1072    /// the item, so for a route longer than that the kinds can differ;
1073    /// which definitions are listed does not.
1074    pub fn naming(&self, item: u64) -> Vec<Naming> {
1075        let mut routes: HashMap<u64, Routes> = HashMap::new();
1076        let mut depth: HashMap<u64, usize> = HashMap::new();
1077        let mut queue: VecDeque<u64> = VecDeque::new();
1078        for &index in self.by_item.get(&item).into_iter().flatten() {
1079            let aspect = self.usages[index].definition;
1080            if !self.stops.contains(&aspect) && routes.insert(aspect, Routes::DIRECT).is_none() {
1081                depth.insert(aspect, 0);
1082                queue.push_back(aspect);
1083            }
1084        }
1085        // Breadth first, back from the item, for the depth limit: each
1086        // aspect's steps into it, once.
1087        let mut into: HashMap<u64, Vec<(u64, StepKind)>> = HashMap::new();
1088        while let Some(aspect) = queue.pop_front() {
1089            let here = depth[&aspect];
1090            if here >= MAX_DEPTH {
1091                continue;
1092            }
1093            let steps: Vec<(u64, StepKind)> = self
1094                .steps_into(aspect)
1095                .into_iter()
1096                .filter(|(from, _)| !self.stops.contains(from))
1097                .collect();
1098            for &(from, _) in &steps {
1099                if let Entry::Vacant(entry) = depth.entry(from) {
1100                    entry.insert(here + 1);
1101                    queue.push_back(from);
1102                }
1103            }
1104            into.insert(aspect, steps);
1105        }
1106        // Then the kinds of every route, to a fixed point, as `resolve` does
1107        // forward.
1108        let mut work: Vec<u64> = routes.keys().copied().collect();
1109        while let Some(aspect) = work.pop() {
1110            let here = routes.get(&aspect).copied().unwrap_or_default();
1111            for &(from, kind) in into.get(&aspect).into_iter().flatten() {
1112                let there = routes.entry(from).or_default();
1113                let grown = Routes(there.0 | here.then(kind).0);
1114                if grown != *there {
1115                    *there = grown;
1116                    work.push(from);
1117                }
1118            }
1119        }
1120        let mut naming: Vec<Naming> = routes
1121            .into_iter()
1122            .map(|(definition, routes)| Naming {
1123                definition,
1124                route_kinds: routes.sets(),
1125            })
1126            .collect();
1127        naming.sort_by_key(|naming| naming.definition);
1128        naming
1129    }
1130
1131    /// The aspects with a step to `#aspect`, and the kind of each.
1132    fn steps_into(&self, aspect: u64) -> Vec<(u64, StepKind)> {
1133        let class = self.class(aspect);
1134        let mut found = Vec::new();
1135        for &index in self.to.get(&aspect).into_iter().flatten() {
1136            let relationship = &self.relationships[index];
1137            let from = self.class(relationship.relating);
1138            let basis = (from.is(Class::DATUM_FEATURE) || from.is(Class::DATUM_TARGET))
1139                && class.is(Class::DATUM);
1140            match relationship.kind {
1141                RelationshipKind::Plain
1142                    if from.is(Class::COMPOSITE) && !basis && !from.is(Class::BETWEEN) =>
1143                {
1144                    found.push((relationship.relating, StepKind::Component));
1145                }
1146                RelationshipKind::Deriving if from.is(Class::DERIVED) => {
1147                    found.push((relationship.relating, StepKind::DerivedFrom));
1148                }
1149                _ => {}
1150            }
1151        }
1152        for &index in self.from.get(&aspect).into_iter().flatten() {
1153            let relationship = &self.relationships[index];
1154            let Some(related) = relationship.related else {
1155                continue;
1156            };
1157            let to = self.class(related);
1158            match relationship.kind {
1159                RelationshipKind::Plain if to.is(Class::DATUM) => {
1160                    if class.is(Class::DATUM_FEATURE) {
1161                        found.push((related, StepKind::DatumFeature));
1162                    } else if class.is(Class::DATUM_TARGET) {
1163                        found.push((related, StepKind::DatumTarget));
1164                    }
1165                }
1166                RelationshipKind::TargetFeature if to.is(Class::DATUM_TARGET) => {
1167                    found.push((related, StepKind::TargetFeature));
1168                }
1169                _ => {}
1170            }
1171        }
1172        found
1173    }
1174}
1175
1176/// What [`AspectItems::walk`] found.
1177struct Walked {
1178    /// The aspects whose items the resolution lists, nearest first.
1179    order: Vec<u64>,
1180    /// Each aspect reached: its depth, and the aspect and step that first
1181    /// reached it.
1182    reached: HashMap<u64, (usize, Option<(u64, Step)>)>,
1183    /// The steps on from each aspect expanded.
1184    edges: HashMap<u64, Vec<Step>>,
1185    /// Where routes stopped, and why.
1186    stops: Vec<(u64, UnresolvedReason)>,
1187}
1188
1189impl Walked {
1190    /// One shortest route to `#aspect`.
1191    fn via(&self, aspect: u64) -> Vec<Step> {
1192        let mut route = Vec::new();
1193        let mut at = aspect;
1194        while let Some(&(_, Some((from, step)))) = self.reached.get(&at) {
1195            route.push(step);
1196            at = from;
1197        }
1198        route.reverse();
1199        route
1200    }
1201}
1202
1203/// The kinds of every route from `#root` to each aspect, to a fixed point:
1204/// each aspect's set of subsets only grows, and has 32 bits.
1205fn routes(root: u64, edges: &HashMap<u64, Vec<Step>>) -> HashMap<u64, Routes> {
1206    let mut routes: HashMap<u64, Routes> = HashMap::from([(root, Routes::DIRECT)]);
1207    let mut work: Vec<u64> = vec![root];
1208    while let Some(aspect) = work.pop() {
1209        let here = routes[&aspect];
1210        for step in edges.get(&aspect).into_iter().flatten() {
1211            let there = routes.entry(step.aspect).or_default();
1212            let grown = Routes(there.0 | here.then(step.kind).0);
1213            if grown != *there {
1214                *there = grown;
1215                work.push(step.aspect);
1216            }
1217        }
1218    }
1219    routes
1220}
1221
1222/// Why `resolve` stops at an aspect of these entity types without reading
1223/// its usages, if it does.
1224fn stop(names: &[String]) -> Option<UnresolvedReason> {
1225    let has = |set: &[&str]| names.iter().any(|name| set.contains(&name.as_str()));
1226    if has(&["PRODUCT_DEFINITION_SHAPE"]) {
1227        Some(UnresolvedReason::WholeShape)
1228    } else if has(&["COMPONENT_PATH_SHAPE_ASPECT"]) {
1229        Some(UnresolvedReason::ComponentPath)
1230    } else if (has(SIZES) || has(RELATIONSHIPS)) && !has(DATUM_FEATURES) {
1231        Some(UnresolvedReason::UnsupportedDefinition)
1232    } else {
1233        None
1234    }
1235}
1236
1237/// The steps of `edges`, each with the aspect it leaves, that lead back to
1238/// an aspect on the depth-first path from `root`: one per cycle entry.
1239fn back_edges(root: u64, edges: &HashMap<u64, Vec<Step>>) -> Vec<(u64, Step)> {
1240    #[derive(Clone, Copy, PartialEq, Eq)]
1241    enum Colour {
1242        Grey,
1243        Black,
1244    }
1245    let mut colour: HashMap<u64, Colour> = HashMap::from([(root, Colour::Grey)]);
1246    let mut stack: Vec<(u64, usize)> = vec![(root, 0)];
1247    let mut found = Vec::new();
1248    while let Some(&mut (aspect, ref mut next)) = stack.last_mut() {
1249        let steps = edges.get(&aspect).map_or(&[][..], Vec::as_slice);
1250        if let Some(step) = steps.get(*next) {
1251            *next += 1;
1252            match colour.get(&step.aspect) {
1253                Some(Colour::Grey) => found.push((aspect, *step)),
1254                Some(Colour::Black) => {}
1255                None => {
1256                    colour.insert(step.aspect, Colour::Grey);
1257                    stack.push((step.aspect, 0));
1258                }
1259            }
1260        } else {
1261            colour.insert(aspect, Colour::Black);
1262            stack.pop();
1263        }
1264    }
1265    found
1266}
1267
1268#[cfg(test)]
1269mod tests {
1270    use std::fmt::Write as _;
1271
1272    use super::*;
1273    use crate::p21::parse;
1274
1275    fn read(data: &str) -> (&'static Graph<'static>, AspectItems) {
1276        let src = format!(
1277            "ISO-10303-21;HEADER;FILE_SCHEMA(('AP242'));ENDSEC;DATA;\n{data}\nENDSEC;END-ISO-10303-21;"
1278        );
1279        let src: &'static [u8] = Box::leak(src.into_bytes().into_boxed_slice());
1280        // build, not new: some cases refer to instances that are not defined.
1281        let graph: &'static Graph<'static> = Box::leak(Box::new(Graph::build(parse(src).unwrap())));
1282        let index = AspectItems::new(graph);
1283        (graph, index)
1284    }
1285
1286    /// Faces #1 to #9, a representation and a shape.
1287    const BASE: &str = "#1=ADVANCED_FACE('',(),#90,.T.);#2=ADVANCED_FACE('',(),#90,.T.);\
1288#3=ADVANCED_FACE('',(),#90,.T.);#4=ADVANCED_FACE('',(),#90,.T.);#5=TRIMMED_CURVE('',#91,(),(),.T.,.UNSPECIFIED.);\
1289#6=CARTESIAN_POINT('',(0.,0.,0.));#20=SHAPE_REPRESENTATION('',(#1),#92);#21=PRODUCT_DEFINITION_SHAPE('','',#93);";
1290
1291    fn ids(resolution: &Resolution) -> Vec<u64> {
1292        resolution.items.iter().map(|item| item.item).collect()
1293    }
1294
1295    fn reasons(resolution: &Resolution) -> Vec<(u64, UnresolvedReason)> {
1296        resolution
1297            .unresolved
1298            .iter()
1299            .map(|u| (u.aspect, u.reason.clone()))
1300            .collect()
1301    }
1302
1303    fn gisu(id: u64, aspect: u64, item: u64) -> String {
1304        format!("#{id}=GEOMETRIC_ITEM_SPECIFIC_USAGE('','',#{aspect},#20,#{item});")
1305    }
1306
1307    #[test]
1308    fn usages_name_items_directly() {
1309        let data = format!(
1310            "{BASE}#30=SHAPE_ASPECT('','',#21,.T.);{}\
1311             #41=ITEM_IDENTIFIED_REPRESENTATION_USAGE('','',#31,#20,SET_REPRESENTATION_ITEM((#2,#3)));\
1312             #42=ITEM_IDENTIFIED_REPRESENTATION_USAGE('','',#32,#20,LIST_REPRESENTATION_ITEM((#4,#3)));\
1313             #43=ITEM_IDENTIFIED_REPRESENTATION_USAGE('','',#33,#20,(#1,#2));\
1314             #44=ITEM_IDENTIFIED_REPRESENTATION_USAGE('','',#33,#20,'x');\
1315             #31=SHAPE_ASPECT('','',#21,.T.);#32=SHAPE_ASPECT('','',#21,.T.);#33=SHAPE_ASPECT('','',#21,.T.);",
1316            gisu(40, 30, 1)
1317        );
1318        let (graph, index) = read(&data);
1319        let one = index.resolve(graph, 30);
1320        assert_eq!(ids(&one), [1]);
1321        assert!(one.is_complete());
1322        assert_eq!(one.items[0].entity, "ADVANCED_FACE");
1323        assert_eq!(one.items[0].usage, 40);
1324        assert_eq!(one.items[0].via, []);
1325        assert_eq!(one.items[0].route_kinds, [StepKinds::NONE]);
1326        assert_eq!(ids(&index.resolve(graph, 31)), [2, 3]);
1327        assert_eq!(
1328            ids(&index.resolve(graph, 32)),
1329            [4, 3],
1330            "a list keeps its order"
1331        );
1332        let kinds: Vec<ItemUsageKind> = index.usages().iter().map(|u| u.kind).collect();
1333        assert_eq!(
1334            kinds,
1335            [
1336                ItemUsageKind::GeometricItemSpecific,
1337                ItemUsageKind::ItemIdentified,
1338                ItemUsageKind::ItemIdentified,
1339                ItemUsageKind::Other,
1340                ItemUsageKind::Other,
1341            ]
1342        );
1343        assert_eq!(
1344            reasons(&index.resolve(graph, 33)),
1345            [
1346                (33, UnresolvedReason::UnsupportedUsage { usage: 43 }),
1347                (33, UnresolvedReason::UnsupportedUsage { usage: 44 }),
1348            ]
1349        );
1350    }
1351
1352    /// A group of a composite and an aspect, with an all-around: two
1353    /// component steps, each item once, by its shortest route.
1354    #[test]
1355    fn composites_and_their_components() {
1356        let data = format!(
1357            "{BASE}#30=COMPOSITE_GROUP_SHAPE_ASPECT('','',#21,.T.);#31=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);\
1358             #32=SHAPE_ASPECT('','',#21,.T.);#33=SHAPE_ASPECT('','',#21,.T.);#34=ALL_AROUND_SHAPE_ASPECT('','',#21,.T.);\
1359             #50=SHAPE_ASPECT_RELATIONSHIP('','',#30,#31);#51=SHAPE_ASPECT_RELATIONSHIP('','',#31,#32);\
1360             #52=SHAPE_ASPECT_RELATIONSHIP('','',#31,#33);#53=SHAPE_ASPECT_RELATIONSHIP('','',#30,#33);\
1361             #54=SHAPE_ASPECT_RELATIONSHIP('','',#34,#32);{}{}{}",
1362            gisu(40, 32, 1),
1363            gisu(41, 33, 2),
1364            gisu(42, 30, 3)
1365        );
1366        let (graph, index) = read(&data);
1367        let group = index.resolve(graph, 30);
1368        assert!(group.is_complete(), "{:?}", group.unresolved);
1369        assert_eq!(ids(&group), [3, 2, 1], "nearest first, each once");
1370        let component = StepKinds::NONE.with(StepKind::Component);
1371        assert_eq!(group.items[0].route_kinds, [StepKinds::NONE]);
1372        assert_eq!(
1373            group.items[1].route_kinds,
1374            [component],
1375            "two routes, one kind"
1376        );
1377        assert_eq!(group.items[1].via.len(), 1, "the shorter route");
1378        assert_eq!(group.items[2].via.len(), 2);
1379        assert_eq!(group.item_ids(StepKinds::NONE), [3]);
1380        assert_eq!(group.item_ids(component), [3, 2, 1]);
1381        assert_eq!(ids(&index.resolve(graph, 34)), [1]);
1382        let naming = index.naming(2);
1383        let definitions: Vec<u64> = naming.iter().map(|n| n.definition).collect();
1384        assert_eq!(definitions, [30, 31, 33]);
1385        assert!(naming[2].is_direct() && !naming[0].is_direct());
1386    }
1387
1388    /// A datum feature that is also a composite: its relationship to its
1389    /// datum is its basis, not a component, so the datum reaches its faces
1390    /// by a datum-feature step and nothing cycles.
1391    #[test]
1392    fn datum_features_targets_and_derived_aspects() {
1393        let data = format!(
1394            "{BASE}#30=DATUM('',$,#21,.F.,'A');\
1395             #31=(COMPOSITE_SHAPE_ASPECT()DATUM_FEATURE()SHAPE_ASPECT('','',#21,.T.));\
1396             #32=SHAPE_ASPECT('','',#21,.T.);#50=SHAPE_ASPECT_RELATIONSHIP('','',#31,#30);\
1397             #51=SHAPE_ASPECT_RELATIONSHIP('','',#31,#32);{}\
1398             #33=DATUM('',$,#21,.F.,'B');#34=PLACED_DATUM_TARGET_FEATURE('','point',#21,.T.,'1');\
1399             #35=SHAPE_ASPECT('','',#21,.T.);#52=SHAPE_ASPECT_RELATIONSHIP('','',#34,#33);\
1400             #53=FEATURE_FOR_DATUM_TARGET_RELATIONSHIP('','',#35,#34);{}{}\
1401             #36=CENTRE_OF_SYMMETRY('','',#21,.T.);#54=SHAPE_ASPECT_DERIVING_RELATIONSHIP('','',#36,#32);{}",
1402            gisu(40, 32, 1),
1403            gisu(41, 34, 6),
1404            gisu(42, 35, 2),
1405            gisu(43, 36, 5)
1406        );
1407        let (graph, index) = read(&data);
1408        let a = index.resolve(graph, 30);
1409        assert!(a.is_complete(), "{:?}", a.unresolved);
1410        assert_eq!(ids(&a), [1]);
1411        assert_eq!(
1412            a.items[0].via.iter().map(|s| s.kind).collect::<Vec<_>>(),
1413            [StepKind::DatumFeature, StepKind::Component]
1414        );
1415        let b = index.resolve(graph, 33);
1416        assert_eq!(ids(&b), [6, 2]);
1417        assert_eq!(b.items[1].via[1].kind, StepKind::TargetFeature);
1418        let axis = index.resolve(graph, 36);
1419        assert_eq!(ids(&axis), [5, 1]);
1420        assert_eq!(
1421            axis.items[1].route_kinds,
1422            [StepKinds::NONE.with(StepKind::DerivedFrom)]
1423        );
1424        assert_eq!(
1425            axis.item_ids(StepKinds::NONE),
1426            [5],
1427            "the axis, not the faces"
1428        );
1429    }
1430
1431    #[test]
1432    fn stops_are_reported() {
1433        let data = format!(
1434            "{BASE}#30=DATUM_FEATURE('','',#21,.T.);#31=SHAPE_ASPECT('','',#21,.T.);\
1435             #50=SHAPE_ASPECT_RELATIONSHIP('datum feature','',#30,#31);{}\
1436             #32=SHAPE_ASPECT('','',#21,.T.);#33=COMPONENT_PATH_SHAPE_ASPECT('','',#21,.T.,#94,#95);\
1437             #34=SHAPE_ASPECT('','',#21,.T.);\
1438             #44=CHAIN_BASED_ITEM_IDENTIFIED_REPRESENTATION_USAGE('','',#34,#20,#1,(#20),$);\
1439             #45=DRAUGHTING_MODEL_ITEM_ASSOCIATION('','',#32,#96,#97);\
1440             #46=DRAUGHTING_MODEL_ITEM_ASSOCIATION_WITH_EXTERNAL_IMAGE_PLACEMENT('','',#32,#96,#97,#98);\
1441             #35=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);#36=SHAPE_ASPECT('','',#21,.T.);\
1442             #55=(SHAPE_ASPECT_RELATIONSHIP('','',#35,#36)SHAPE_DEFINING_RELATIONSHIP());\
1443             #56=FEATURE_COMPONENT_RELATIONSHIP('','',#35,#31);\
1444             #37=DIMENSIONAL_SIZE(#31,'diameter');{}{}",
1445            gisu(40, 31, 1),
1446            gisu(41, 36, 2),
1447            gisu(42, 33, 3)
1448        );
1449        let (graph, index) = read(&data);
1450        let datum_feature = index.resolve(graph, 30);
1451        assert_eq!(
1452            reasons(&datum_feature),
1453            [(
1454                30,
1455                UnresolvedReason::NotFollowed {
1456                    relationship: 50,
1457                    related: 31
1458                }
1459            )]
1460        );
1461        assert_eq!(datum_feature.items, []);
1462        assert_eq!(
1463            reasons(&index.resolve(graph, 21)),
1464            [(21, UnresolvedReason::WholeShape)]
1465        );
1466        assert_eq!(
1467            reasons(&index.resolve(graph, 32)),
1468            [(32, UnresolvedReason::NoUsage)]
1469        );
1470        assert_eq!(
1471            reasons(&index.resolve(graph, 33)),
1472            [(33, UnresolvedReason::ComponentPath)]
1473        );
1474        assert_eq!(
1475            reasons(&index.resolve(graph, 34)),
1476            [(34, UnresolvedReason::UnsupportedUsage { usage: 44 })]
1477        );
1478        let presentation: Vec<ItemUsageKind> = index
1479            .usages()
1480            .iter()
1481            .filter(|u| u.definition == 32)
1482            .map(|u| u.kind)
1483            .collect();
1484        assert_eq!(presentation, [ItemUsageKind::Presentation; 2]);
1485        let composite = index.resolve(graph, 35);
1486        assert_eq!(
1487            reasons(&composite),
1488            [
1489                (
1490                    35,
1491                    UnresolvedReason::UnsupportedRelationship {
1492                        relationship: 55,
1493                        entity: "SHAPE_ASPECT_RELATIONSHIP+SHAPE_DEFINING_RELATIONSHIP".to_owned()
1494                    }
1495                ),
1496                (
1497                    35,
1498                    UnresolvedReason::UnsupportedRelationship {
1499                        relationship: 56,
1500                        entity: "FEATURE_COMPONENT_RELATIONSHIP".to_owned()
1501                    }
1502                ),
1503            ]
1504        );
1505        assert_eq!(
1506            reasons(&index.resolve(graph, 37)),
1507            [(37, UnresolvedReason::UnsupportedDefinition)]
1508        );
1509        assert_eq!(
1510            reasons(&index.resolve(graph, 99)),
1511            [(99, UnresolvedReason::Missing)]
1512        );
1513        assert_eq!(index.naming(3), [], "a component path names nothing");
1514    }
1515
1516    #[test]
1517    fn cycles_depth_and_missing_items() {
1518        // A component that is not defined, though a usage names it, lists
1519        // nothing (found by fuzzing: resolve listed its items, naming not).
1520        let (graph, index) = read(&format!(
1521            "{BASE}#30=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);\
1522             #50=SHAPE_ASPECT_RELATIONSHIP('','',#30,#32);{}",
1523            gisu(40, 32, 1)
1524        ));
1525        let undefined = index.resolve(graph, 30);
1526        assert_eq!(undefined.items, []);
1527        assert_eq!(reasons(&undefined), [(32, UnresolvedReason::Missing)]);
1528        assert_eq!(index.naming(1), []);
1529
1530        let (graph, index) = read(&format!(
1531            "{BASE}#30=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);#31=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);\
1532             #50=SHAPE_ASPECT_RELATIONSHIP('','',#30,#31);#51=SHAPE_ASPECT_RELATIONSHIP('','',#31,#30);{}{}",
1533            gisu(40, 31, 1),
1534            gisu(41, 30, 99)
1535        ));
1536        let cycle = index.resolve(graph, 30);
1537        assert_eq!(ids(&cycle), [1]);
1538        assert_eq!(
1539            reasons(&cycle),
1540            [
1541                (
1542                    30,
1543                    UnresolvedReason::MissingItem {
1544                        usage: 41,
1545                        item: 99
1546                    }
1547                ),
1548                (30, UnresolvedReason::Cycle),
1549            ]
1550        );
1551
1552        let mut chain = BASE.to_owned();
1553        for k in 0..70u64 {
1554            write!(
1555                chain,
1556                "#{}=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);#{}=SHAPE_ASPECT_RELATIONSHIP('','',#{},#{});",
1557                1000 + k,
1558                2000 + k,
1559                1000 + k,
1560                1001 + k
1561            )
1562            .unwrap();
1563        }
1564        chain += &gisu(40, 1070, 1);
1565        let (graph, index) = read(&chain);
1566        let deep = index.resolve(graph, 1000);
1567        assert_eq!(deep.items, []);
1568        assert_eq!(reasons(&deep), [(1064, UnresolvedReason::TooDeep)]);
1569    }
1570
1571    /// What the review of this resolver found: a between aspect's bounds, a
1572    /// common datum's components, a complex target feature relationship, a
1573    /// relationship whose related side cannot be read, and a cycle's route.
1574    #[test]
1575    fn review_cases() {
1576        let data = format!(
1577            "{BASE}#30=BETWEEN_SHAPE_ASPECT('','',#21,.T.);#31=SHAPE_ASPECT('','',#21,.T.);\
1578             #32=SHAPE_ASPECT('','',#21,.T.);#50=SHAPE_ASPECT_RELATIONSHIP('start feature','',#30,#31);\
1579             #51=SHAPE_ASPECT_RELATIONSHIP('end feature','',#30,#32);{}{}{}\
1580             #33=DATUM('',$,#21,.F.,'A');#34=DATUM('',$,#21,.F.,'B');#35=COMMON_DATUM('',$,#21,.F.,'A-B');\
1581             #36=DATUM_FEATURE('','',#21,.T.);#37=DATUM_FEATURE('','',#21,.T.);\
1582             #52=SHAPE_ASPECT_RELATIONSHIP('','',#36,#33);#53=SHAPE_ASPECT_RELATIONSHIP('','',#37,#34);\
1583             #54=SHAPE_ASPECT_RELATIONSHIP('','',#35,#33);#55=SHAPE_ASPECT_RELATIONSHIP('','',#35,#34);{}{}\
1584             #38=DATUM('',$,#21,.F.,'C');#39=PLACED_DATUM_TARGET_FEATURE('','point',#21,.T.,'1');\
1585             #40=SHAPE_ASPECT('','',#21,.T.);#56=SHAPE_ASPECT_RELATIONSHIP('','',#39,#38);\
1586             #57=(FEATURE_FOR_DATUM_TARGET_RELATIONSHIP()SHAPE_ASPECT_RELATIONSHIP('','',#40,#39));{}{}\
1587             #41=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);#58=SHAPE_ASPECT_RELATIONSHIP('','',#41,$);{}",
1588            gisu(60, 30, 3),
1589            gisu(61, 31, 1),
1590            gisu(62, 32, 2),
1591            gisu(63, 36, 1),
1592            gisu(64, 37, 2),
1593            gisu(65, 39, 6),
1594            gisu(66, 40, 4),
1595            gisu(67, 41, 3)
1596        );
1597        let (graph, index) = read(&data);
1598        // The region between the start and end features, not the features.
1599        let between = index.resolve(graph, 30);
1600        assert_eq!(ids(&between), [3]);
1601        assert!(between.is_complete());
1602        // A common datum's components are datums, each with its feature;
1603        // neither datum reports the link from the common datum.
1604        let common = index.resolve(graph, 35);
1605        assert!(common.is_complete(), "{:?}", common.unresolved);
1606        assert_eq!(ids(&common), [1, 2]);
1607        assert_eq!(
1608            common.items[0].route_kinds,
1609            [StepKinds::NONE
1610                .with(StepKind::Component)
1611                .with(StepKind::DatumFeature)]
1612        );
1613        assert!(index.resolve(graph, 33).is_complete());
1614        // A complex target feature relationship is reported, not dropped.
1615        let target = index.resolve(graph, 38);
1616        assert_eq!(ids(&target), [6]);
1617        assert_eq!(
1618            reasons(&target),
1619            [(
1620                39,
1621                UnresolvedReason::UnsupportedRelationship {
1622                    relationship: 57,
1623                    entity: "FEATURE_FOR_DATUM_TARGET_RELATIONSHIP+SHAPE_ASPECT_RELATIONSHIP"
1624                        .to_owned()
1625                }
1626            )]
1627        );
1628        // So is a relationship whose related side is not a reference.
1629        assert_eq!(
1630            reasons(&index.resolve(graph, 41)),
1631            [(
1632                41,
1633                UnresolvedReason::UnsupportedRelationship {
1634                    relationship: 58,
1635                    entity: "SHAPE_ASPECT_RELATIONSHIP".to_owned()
1636                }
1637            )]
1638        );
1639        // naming lists the same, with the same kinds of route.
1640        for aspect in 30..=41 {
1641            for item in index.resolve(graph, aspect).items {
1642                let naming = index.naming(item.item);
1643                let found = naming.iter().find(|n| n.definition == aspect);
1644                assert_eq!(
1645                    found.map(|n| &n.route_kinds),
1646                    Some(&item.route_kinds),
1647                    "#{aspect}"
1648                );
1649            }
1650        }
1651
1652        // A cycle's route ends at the aspect it returns to.
1653        let (graph, index) = read(&format!(
1654            "{BASE}#30=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);#31=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);\
1655             #50=SHAPE_ASPECT_RELATIONSHIP('','',#30,#31);#51=SHAPE_ASPECT_RELATIONSHIP('','',#31,#30);{}",
1656            gisu(40, 31, 1)
1657        ));
1658        let cycle = index.resolve(graph, 30);
1659        let back = cycle
1660            .unresolved
1661            .iter()
1662            .find(|u| u.reason == UnresolvedReason::Cycle)
1663            .unwrap();
1664        assert_eq!(back.aspect, 30);
1665        assert_eq!(back.via.last().map(|step| step.aspect), Some(30));
1666    }
1667
1668    /// Layers of two composites, each relating to both below: 2^22 routes,
1669    /// read in milliseconds, each item once.
1670    #[test]
1671    fn diamonds_take_linear_time() {
1672        let mut data = BASE.to_owned();
1673        let layers = 22u64;
1674        for layer in 0..layers {
1675            for side in 0..2 {
1676                let aspect = 1000 + layer * 2 + side;
1677                write!(data, "#{aspect}=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);").unwrap();
1678                for below in 0..2 {
1679                    // The last layer relates to the one aspect at the bottom.
1680                    let to = if layer + 1 == layers {
1681                        1000 + layers * 2
1682                    } else {
1683                        1002 + layer * 2 + below
1684                    };
1685                    write!(
1686                        data,
1687                        "#{}=SHAPE_ASPECT_RELATIONSHIP('','',#{aspect},#{to});",
1688                        5000 + layer * 4 + side * 2 + below
1689                    )
1690                    .unwrap();
1691                }
1692            }
1693        }
1694        write!(data, "#{}=SHAPE_ASPECT('','',#21,.T.);", 1000 + layers * 2).unwrap();
1695        data += &gisu(40, 1000 + layers * 2, 1);
1696        let (graph, index) = read(&data);
1697        let start = std::time::Instant::now();
1698        let top = index.resolve(graph, 1000);
1699        assert_eq!(ids(&top), [1]);
1700        assert!(top.is_complete());
1701        assert_eq!(index.naming(1).len(), 2 * 22 + 1);
1702        assert!(start.elapsed().as_millis() < 500, "{:?}", start.elapsed());
1703    }
1704
1705    /// `naming` is the inverse of `resolve` over every aspect of the
1706    /// samples above.
1707    #[test]
1708    fn naming_inverts_resolve() {
1709        let data = format!(
1710            "{BASE}#30=COMPOSITE_GROUP_SHAPE_ASPECT('','',#21,.T.);#31=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);\
1711             #32=SHAPE_ASPECT('','',#21,.T.);#33=DATUM('',$,#21,.F.,'A');#34=DATUM_FEATURE('','',#21,.T.);\
1712             #50=SHAPE_ASPECT_RELATIONSHIP('','',#30,#31);#51=SHAPE_ASPECT_RELATIONSHIP('','',#31,#32);\
1713             #52=SHAPE_ASPECT_RELATIONSHIP('','',#34,#33);#35=CENTRE_OF_SYMMETRY('','',#21,.T.);\
1714             #53=SHAPE_ASPECT_DERIVING_RELATIONSHIP('','',#35,#30);{}{}{}",
1715            gisu(40, 32, 1),
1716            gisu(41, 34, 2),
1717            gisu(42, 35, 5)
1718        );
1719        let (graph, index) = read(&data);
1720        let mut forward = std::collections::BTreeSet::new();
1721        for aspect in 30..=35 {
1722            for item in index.resolve(graph, aspect).items {
1723                forward.insert((item.item, aspect, item.route_kinds));
1724            }
1725        }
1726        let mut backward = std::collections::BTreeSet::new();
1727        for item in [1, 2, 5] {
1728            for naming in index.naming(item) {
1729                backward.insert((item, naming.definition, naming.route_kinds));
1730            }
1731        }
1732        assert_eq!(forward, backward);
1733    }
1734
1735    /// Every list of types is exactly that type and its subtypes in the
1736    /// four schemas, and every relationship type keeps its relating and
1737    /// related aspects where the walk reads them (`tools/fetch-schemas.sh`;
1738    /// skipped without them, failed with `STEPQ_REQUIRE_FIXTURES=1`).
1739    #[test]
1740    fn type_lists_and_positions_match_the_schemas() {
1741        use crate::express::Schema;
1742        let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/schemas");
1743        let lists: &[(&str, &[&str])] = &[
1744            ("SHAPE_ASPECT_RELATIONSHIP", RELATIONSHIPS),
1745            ("DIMENSIONAL_LOCATION", LOCATIONS),
1746            ("DIMENSIONAL_SIZE", SIZES),
1747            ("ITEM_IDENTIFIED_REPRESENTATION_USAGE", USAGES),
1748            ("DRAUGHTING_MODEL_ITEM_ASSOCIATION", PRESENTATION),
1749            ("COMPOSITE_SHAPE_ASPECT", COMPOSITES),
1750            ("DERIVED_SHAPE_ASPECT", DERIVED),
1751            ("DATUM_FEATURE", DATUM_FEATURES),
1752            ("DATUM_TARGET", DATUM_TARGETS),
1753            ("DATUM", DATUMS),
1754        ];
1755        let mut found: Vec<HashSet<String>> = vec![HashSet::new(); lists.len()];
1756        let mut read = 0;
1757        for file in [
1758            "ap242e4_mim_lf.exp",
1759            "ap214e3.exp",
1760            "ap203e2_mim_lf.exp",
1761            "ap203.exp",
1762        ] {
1763            let Ok(src) = std::fs::read(dir.join(file)) else {
1764                continue;
1765            };
1766            read += 1;
1767            let schema = Schema::parse(&src).unwrap();
1768            for ((root, _), found) in lists.iter().zip(&mut found) {
1769                if schema.entity(root).is_none() {
1770                    continue;
1771                }
1772                let mut seen = HashSet::from([(*root).to_owned()]);
1773                let mut stack = vec![(*root).to_owned()];
1774                while let Some(name) = stack.pop() {
1775                    for entity in schema.entities() {
1776                        if entity
1777                            .supertypes
1778                            .iter()
1779                            .any(|s| s.eq_ignore_ascii_case(&name))
1780                            && seen.insert(entity.name.clone())
1781                        {
1782                            stack.push(entity.name.clone());
1783                        }
1784                    }
1785                }
1786                found.extend(seen);
1787            }
1788            for name in RELATIONSHIPS {
1789                let Some(slots) = schema.slots(name) else {
1790                    continue;
1791                };
1792                let offset = RELATIONSHIP_OFFSETS
1793                    .iter()
1794                    .find(|(entity, _)| entity == name)
1795                    .map_or(0, |(_, offset)| *offset);
1796                let at = |i: usize| slots.get(offset + i).map(|slot| slot.name.as_str());
1797                assert_eq!(
1798                    (at(2), at(3)),
1799                    (Some("RELATING_SHAPE_ASPECT"), Some("RELATED_SHAPE_ASPECT")),
1800                    "{file}: {name}"
1801                );
1802            }
1803        }
1804        let required =
1805            std::env::var_os("STEPQ_REQUIRE_FIXTURES").is_some_and(|v| v != "0" && !v.is_empty());
1806        if read < 4 {
1807            assert!(
1808                !required,
1809                "{read} of 4 schemas (run tools/fetch-schemas.sh)"
1810            );
1811            return;
1812        }
1813        for ((root, list), found) in lists.iter().zip(&found) {
1814            let listed: HashSet<String> = list.iter().map(|&name| name.to_owned()).collect();
1815            assert_eq!(&listed, found, "{root}");
1816        }
1817    }
1818
1819    #[cfg(feature = "serde")]
1820    #[test]
1821    fn resolutions_have_unique_keys() {
1822        use crate::testing::unique;
1823        let (graph, index) = read(&format!(
1824            "{BASE}#30=COMPOSITE_SHAPE_ASPECT('','',#21,.T.);#31=SHAPE_ASPECT('','',#21,.T.);\
1825             #50=SHAPE_ASPECT_RELATIONSHIP('','',#30,#31);#51=SHAPE_ASPECT_RELATIONSHIP('','',#31,#30);{}",
1826            gisu(40, 31, 1)
1827        ));
1828        let json = unique(&index.resolve(graph, 30));
1829        assert!(json.contains("\"route_kinds\":[[\"component\"]]"), "{json}");
1830        assert!(json.contains("\"kind\":\"not_followed\""), "{json}");
1831        unique(&index.usages()[0]);
1832        unique(&index.naming(1));
1833        for reason in [
1834            UnresolvedReason::UnsupportedRelationship {
1835                relationship: 1,
1836                entity: "X".to_owned(),
1837            },
1838            UnresolvedReason::MissingItem { usage: 1, item: 2 },
1839        ] {
1840            assert!(unique(&reason).starts_with("{\"kind\":"));
1841        }
1842    }
1843}