Skip to main content

nsi_intermediate/scene/
mod.rs

1//! Node and attribute tables.
2//!
3//! `IndexMap` throughout: replaying a scene in a different order than it
4//! was recorded would make the `.nsi` stream diff against 3Delight
5//! meaningless.
6
7use crate::{
8    ALL, Edge, EdgeKind, HashMap, HashSet, OwnedArgument, RecordError,
9    classify,
10    handle::{self, Handle},
11};
12use core::{cmp::Ordering, mem};
13use indexmap::{IndexMap, IndexSet};
14use std::sync::LazyLock;
15
16/// One node's static attributes, by name.
17pub(crate) type AttributeTable = IndexMap<Handle, OwnedArgument>;
18
19/// Every `set_attribute_at_time` call for one node, per attribute, in
20/// call order.
21pub(crate) type SampleTable = IndexMap<Handle, Vec<(f64, OwnedArgument)>>;
22
23/// One ɴsɪ node.
24#[derive(Debug, Clone, Default)]
25#[non_exhaustive]
26pub struct Node {
27    /// The ɴsɪ node type this handle was created with. Read it with
28    /// [`Node::node_type`].
29    ///
30    /// Stored rather than public so `ustr_handles` can intern it: a
31    /// production scene says `"mesh"` a million times.
32    pub(crate) node_type: Handle,
33    /// Attributes set with `set_attribute`, keyed by name.
34    ///
35    /// Boxed and absent until one is set, for the same reason
36    /// [`Node::samples`] is: a scene is mostly nodes that hold
37    /// connections rather than values -- sets, groups, the transforms
38    /// above an asset -- and an inline `IndexMap` cost every one of
39    /// them a header it never filled.
40    pub(crate) attributes: Option<Box<AttributeTable>>,
41    /// Every `set_attribute_at_time` call, per attribute, **in call
42    /// order**.
43    ///
44    /// A call log rather than a timeline, because that is what ɴsɪ's
45    /// rules are stated over. 3Delight applies the last *call*, and a
46    /// table keyed by time cannot say which call that was: rendered,
47    /// with `visibility` set only at times, `t=1 -> 0` then `t=0 -> 1`
48    /// leaves the object **visible** while `t=1 -> 1` then `t=0 -> 0`
49    /// hides it. The same two times, opposite answers.
50    ///
51    /// The order is equally what decides the reach of an unreadable
52    /// sample: 3Delight rejects the argument at the call, so what
53    /// survives is what was set *after* it, not what sits later on the
54    /// timeline. And a same-time re-set is a call of its own here --
55    /// keeping the superseded value is the difference between `good`
56    /// replacing `good`, which sweeps, and `good` replacing an
57    /// unreadable one, which does not.
58    ///
59    /// Read it through [`Node::effective`] or the resolver rather than
60    /// walking it: they apply that rule. Setting an attribute
61    /// statically clears its entry, as ɴsɪ says it should.
62    ///
63    /// One entry per call, so a caller that re-sets one time in a loop
64    /// grows it. That is the record ɴsɪ's rules need, and for any
65    /// scene an exporter writes -- each time set once -- it is the
66    /// same values a table keyed by time would hold.
67    ///
68    /// Boxed and absent until something is set at a time: most nodes
69    /// in a scene never move, and an inline `IndexMap` cost every one
70    /// of them the header whether or not it held anything.
71    pub(crate) samples: Option<Box<SampleTable>>,
72}
73
74/// An empty table, for a node that has no attributes.
75static NO_ATTRIBUTES: LazyLock<AttributeTable> = LazyLock::new(IndexMap::new);
76
77/// An empty table, for a node that has no samples.
78static NO_SAMPLES: LazyLock<SampleTable> = LazyLock::new(IndexMap::new);
79
80/// Two nodes are equal when they say the same thing, which an absent
81/// table and an emptied one both do -- `delete_attribute` leaves the
82/// second, and a scene compared against a replay of itself must not
83/// hinge on which one it holds.
84impl PartialEq for Node {
85    fn eq(&self, other: &Self) -> bool {
86        self.node_type == other.node_type
87            && self.attribute_table() == other.attribute_table()
88            && self.sample_table() == other.sample_table()
89    }
90}
91
92impl Node {
93    /// This node's static attributes, by name.
94    pub fn attributes(&self) -> impl Iterator<Item = (&str, &OwnedArgument)> {
95        self.attribute_table()
96            .iter()
97            .map(|(name, arg)| (name.as_str(), arg))
98    }
99
100    /// One static attribute by name.
101    ///
102    /// **Use [`Node::effective`] unless you mean the static one
103    /// specifically**: an attribute set with `SetAttributeAtTime` is
104    /// not here, and the renderer honours it.
105    pub fn attribute(&self, name: &str) -> Option<&OwnedArgument> {
106        handle::map_get(self.attribute_table(), name)
107    }
108
109    pub(crate) fn attribute_table(&self) -> &AttributeTable {
110        self.attributes.as_deref().unwrap_or(&NO_ATTRIBUTES)
111    }
112
113    pub(crate) fn attribute_table_mut(&mut self) -> &mut AttributeTable {
114        self.attributes.get_or_insert_with(Box::default)
115    }
116
117    /// This node's sampled attributes, by name, each in call order.
118    pub fn samples(
119        &self,
120    ) -> impl Iterator<Item = (&str, &[(f64, OwnedArgument)])> {
121        self.sample_table()
122            .iter()
123            .map(|(name, calls)| (name.as_str(), calls.as_slice()))
124    }
125
126    /// The calls that set one attribute at a time, in call order.
127    pub fn sample_calls(&self, name: &str) -> Option<&[(f64, OwnedArgument)]> {
128        handle::map_get(self.sample_table(), name).map(Vec::as_slice)
129    }
130
131    pub(crate) fn sample_table(&self) -> &SampleTable {
132        self.samples.as_deref().unwrap_or(&NO_SAMPLES)
133    }
134
135    pub(crate) fn sample_table_mut(&mut self) -> &mut SampleTable {
136        self.samples.get_or_insert_with(Box::default)
137    }
138
139    /// One attribute as a single `f32`.
140    ///
141    /// Reads the **effective** value -- static or the last call at a
142    /// time -- and yields `None` when the attribute is absent or is not
143    /// exactly one `f32`. A backend pulling one number out of a node
144    /// wrote `node.effective(name).and_then(OwnedArgument::as_f32)`
145    /// before this existed; twenty such sites in one backend's flush
146    /// path is what asked for these.
147    pub fn f32(&self, name: &str) -> Option<f32> {
148        self.effective(name)?.as_f32()
149    }
150
151    /// One attribute as a single `f64`, on the same terms.
152    pub fn f64(&self, name: &str) -> Option<f64> {
153        match self.effective(name)?.as_f64s()? {
154            [value] => Some(*value),
155            _ => None,
156        }
157    }
158
159    /// One attribute as a single `i32`, on the same terms.
160    pub fn i32(&self, name: &str) -> Option<i32> {
161        self.effective(name)?.as_i32()
162    }
163
164    /// One attribute as an ɴsɪ integer flag.
165    ///
166    /// ɴsɪ writes booleans as `int` with `0` and `1` -- `withalpha`,
167    /// `dithering`, `clockwisewinding` -- so this is the shape those
168    /// are read in. Anything other than a single integer is `None`,
169    /// which a caller replaces with the attribute's documented
170    /// default rather than with `false`.
171    pub fn flag(&self, name: &str) -> Option<bool> {
172        Some(self.i32(name)? != 0)
173    }
174
175    /// One attribute as a single string.
176    ///
177    /// **`None` for a value that is not UTF-8**, which is not the same
178    /// as absent: an ɴsɪ string is bytes, and a file name on Linux need
179    /// not be UTF-8. Use [`Node::bytes`] where the value may be a path;
180    /// this is for the enumerants -- `"shader"`, `"uint8"`, `"color"`
181    /// -- where UTF-8 is the whole vocabulary.
182    pub fn string(&self, name: &str) -> Option<&str> {
183        core::str::from_utf8(self.bytes(name)?).ok()
184    }
185
186    /// One attribute as a single string's raw bytes.
187    pub fn bytes(&self, name: &str) -> Option<&[u8]> {
188        match self.effective(name)?.as_strings()? {
189            [value] => Some(value),
190            _ => None,
191        }
192    }
193
194    /// The ɴsɪ node type this handle was created with.
195    pub fn node_type(&self) -> &str {
196        &self.node_type
197    }
198
199    /// This node's effective value for an attribute.
200    ///
201    /// **Use this, not [`Node::attributes`].** `SetAttributeAtTime` on an
202    /// attribute
203    /// that is not motion data sets it for the whole shutter, exactly
204    /// as `SetAttribute` would: rendered, an `attributes` node whose
205    /// `visibility` is set only through `SetAttributeAtTime` hides the
206    /// object, identically to the static form. Reading [`Node::attributes`]
207    /// alone answers "not set" for an attribute the renderer honours,
208    /// which is a silent wrong answer -- and was one here until it was
209    /// rendered.
210    ///
211    /// Static first, then the **last call**, which is not the sample
212    /// at the greatest time -- see [`Node::samples`] for the render
213    /// that separates the two. The static value and the samples never
214    /// coexist: `set_attribute` clears that name from the log and
215    /// `set_attribute_at_time` clears the static value, which is ɴsɪ's
216    /// own rule and 3Delight's behaviour.
217    ///
218    /// This is what the resolver reads, so a backend asking a node
219    /// directly gets the same answer the resolver would.
220    pub fn effective(&self, name: &str) -> Option<&OwnedArgument> {
221        if let Some(arg) = handle::map_get(self.attribute_table(), name) {
222            return Some(arg);
223        }
224        handle::map_get(self.sample_table(), name)?
225            .last()
226            .map(|(_, arg)| arg)
227    }
228}
229
230/// The value standing at each time, once a same-time re-set has
231/// replaced what it superseded, ascending by time.
232///
233/// One statement of it, read by [`Scene::attribute_samples`] and by
234/// the resolver's typing rule -- which runs it over the calls that
235/// survived an unreadable one rather than over all of them. Two copies
236/// of a resolution rule have drifted apart in this crate four times.
237pub(crate) fn latest_per_time(
238    calls: &[(f64, OwnedArgument)],
239) -> Vec<(f64, &OwnedArgument)> {
240    // Sorted by time, and by **call order** within one time -- the
241    // call index is part of the key rather than a stability the sort
242    // happens to give. A reviewer switched this to `sort_unstable_by`
243    // and nothing went red; no fixture had enough same-time calls to
244    // make an unstable sort actually reorder, so the guarantee the
245    // rule rested on was one no test could see. With the index in the
246    // key the order is total and any correct sort gives this answer.
247    let mut standing: Vec<(f64, usize, &OwnedArgument)> = calls
248        .iter()
249        .enumerate()
250        .map(|(index, (time, arg))| (*time, index, arg))
251        .collect();
252    standing.sort_by(|a, b| a.0.total_cmp(&b.0).then(a.1.cmp(&b.1)));
253    standing.dedup_by(|later, earlier| {
254        // `dedup_by` keeps the *earlier* of a matching pair, and the
255        // later call is the one that stands, so its value moves down
256        // before the earlier one is dropped.
257        if later.0.total_cmp(&earlier.0) == Ordering::Equal {
258            earlier.2 = later.2;
259            true
260        } else {
261            false
262        }
263    });
264
265    standing
266        .into_iter()
267        .map(|(time, _, arg)| (time, arg))
268        .collect()
269}
270
271/// What changed since the last [`Scene::take_changes`].
272///
273/// A **net** record, not a log of calls: re-setting one attribute
274/// forty times is one entry, connecting and reconnecting one edge is
275/// one entry, and a handle created and then deleted in the same
276/// interval appears only in [`Changes::deleted`] -- the create is
277/// undone by the delete, and a consumer that never saw the node has
278/// nothing to undo. A consumer synchronising a live renderer wants the
279/// set of things to look at again, and coalescing a call log into that
280/// set would be its work rather than ours.
281///
282/// It carries **no values**. The scene holds the current one --
283/// [`Node::effective`] answers it -- so an entry names an attribute
284/// rather than copying a vertex buffer per edit.
285///
286/// This is the raw record, and it is deliberately in ɴsɪ's domain: a
287/// `transform` and an `attributes` node have no counterpart in a
288/// renderer's scene, and one geometry under two parents is several
289/// objects there. [`Scene::affected`] turns "this transform moved"
290/// into "these nodes may have moved", which is the question a backend
291/// actually asks.
292#[derive(Debug, Clone, Default, PartialEq)]
293#[non_exhaustive]
294pub struct Changes {
295    /// Handles created during this interval and not since deleted.
296    ///
297    /// Read it with [`Changes::created`]. Stored as handles so that
298    /// `ustr_handles` interns them: a frame that touches ten thousand
299    /// nodes copied ten thousand strings out of the scene otherwise,
300    /// on the one path an interactive host walks every frame.
301    pub(crate) created: IndexSet<Handle>,
302    /// Handles deleted, with the node type they had.
303    ///
304    /// The type is kept because the handle is gone from the scene: a
305    /// consumer that has to undo whatever it built for a node cannot
306    /// ask what kind of node it was any more. Read it with
307    /// [`Changes::deleted`].
308    pub(crate) deleted: IndexMap<Handle, Handle>,
309    /// `(handle, attribute)` pairs set, re-set or deleted. Read it
310    /// with [`Changes::attributes`].
311    pub(crate) attributes: IndexSet<(Handle, Handle)>,
312    /// Connections made.
313    pub edges_added: Vec<Edge>,
314    /// Connections removed, **in full**.
315    ///
316    /// The endpoints and kind are kept because the graph no longer has
317    /// them: working out what a severed `objects` edge orphaned means
318    /// walking down from a node the edge no longer points at. A
319    /// `disconnect` naming `.all` is expanded here into the edges it
320    /// actually removed, since the pattern cannot be re-expanded once
321    /// they are gone.
322    pub edges_removed: Vec<Edge>,
323    /// Connections whose arguments a repeated `connect` replaced in
324    /// place.
325    ///
326    /// No edge appeared or disappeared, so a record keyed on additions
327    /// and removals misses this entirely -- and ɴsɪ's `"priority"`
328    /// rides on these arguments, which decides which of two shaders
329    /// wins. This is the quietest way for a scene to change meaning.
330    pub edges_rearmed: Vec<Edge>,
331}
332
333impl Changes {
334    /// The handles created and not since deleted.
335    pub fn created(&self) -> impl Iterator<Item = &str> {
336        self.created.iter().map(|handle| handle.as_str())
337    }
338
339    /// Whether one handle was created in this interval.
340    pub fn was_created(&self, handle: &str) -> bool {
341        handle::set_contains(&self.created, handle)
342    }
343
344    /// The handles deleted, each with the node type it had.
345    pub fn deleted(&self) -> impl Iterator<Item = (&str, &str)> {
346        self.deleted
347            .iter()
348            .map(|(handle, node_type)| (handle.as_str(), node_type.as_str()))
349    }
350
351    /// The node type a deleted handle had, if it was deleted here.
352    pub fn deleted_type(&self, handle: &str) -> Option<&str> {
353        handle::map_get(&self.deleted, handle)
354            .map(|node_type| node_type.as_str())
355    }
356
357    /// The `(handle, attribute)` pairs set, re-set or deleted.
358    pub fn attributes(&self) -> impl Iterator<Item = (&str, &str)> {
359        self.attributes
360            .iter()
361            .map(|(handle, name)| (handle.as_str(), name.as_str()))
362    }
363
364    /// Nothing changed since the last [`Scene::take_changes`].
365    pub fn is_empty(&self) -> bool {
366        self.created.is_empty()
367            && self.deleted.is_empty()
368            && self.attributes.is_empty()
369            && self.edges_added.is_empty()
370            && self.edges_removed.is_empty()
371            && self.edges_rearmed.is_empty()
372    }
373}
374
375/// What a [`Changes`] batch may have moved.
376///
377/// **Candidates, not a minimal set.** An entry means "resolve this
378/// again", not "this definitely differs": ɴsɪ's precedence rules can
379/// make an edit invisible -- a re-armed `surfaceshader` at a lower
380/// priority than a nearer one changes nothing -- and deciding that
381/// here would mean remembering every previous answer this crate ever
382/// gave, which is the consumer's own record to keep.
383///
384/// Keyed by **handle**, not by placement path. One geometry under two
385/// parents is several objects to a renderer, and editing one parent
386/// moves only one of them; a handle-level answer makes the consumer
387/// re-resolve both. Correct, and coarse for a crowd -- path-precision
388/// is an optimisation to ask for with a measurement.
389/// # Why it borrows
390///
391/// Every handle in here already lives in the [`Scene`] or in the
392/// [`Changes`] it was computed from, so owning them meant a `String`
393/// clone per named node on a path an interactive host walks every
394/// frame. Measured, one transform with *n* children, debug build,
395/// best of ten: 1000 nodes 2.08 ms, 10 000 27.3 ms, 50 000 88.9 ms --
396/// about 2 us a node, four to five allocations of it. Borrowing costs
397/// a lifetime on the type and nothing else.
398#[derive(Debug, Clone, Default, PartialEq, Eq)]
399#[non_exhaustive]
400pub struct Affected<'a> {
401    /// The **roots** of what may have moved: these nodes and
402    /// everything below them on the `objects` chain.
403    ///
404    /// Roots rather than an enumeration, because enumerating is
405    /// O(scene) for the edit that matters least -- moving one
406    /// transform near the top of a production scene names every
407    /// geometry under it, and a set-dressing scene has millions. The
408    /// consumer walks its own objects anyway;
409    /// [`Scene::descendants`] expands a root when it wants the list.
410    pub roots: IndexSet<&'a str>,
411    /// Shader nodes whose own attributes or network changed.
412    ///
413    /// Kept apart because they map one-to-one onto a renderer's
414    /// material parameters and cost no geometry work: only the *root*
415    /// shader's identity reaches geometry, and that is a
416    /// `surfaceshader` edge, which lands in `nodes`.
417    pub shaders: IndexSet<&'a str>,
418    /// Whether the camera/screen/layer/driver chain changed, so the
419    /// outputs need re-reading.
420    pub outputs: bool,
421    /// Whether something global changed -- an attribute on `.root` or
422    /// `.global` -- and the whole scene is a candidate.
423    ///
424    /// When this is set, `nodes` is not filled: the answer is
425    /// everything, and listing it would be a copy of the scene.
426    pub everything: bool,
427}
428
429/// Name a root of the affected set.
430///
431/// A root stands for itself and everything below it, so a handle that
432/// is already named needs no second entry -- and a caller expanding
433/// two overlapping roots gets the union either way.
434fn insert_root<'a>(roots: &mut IndexSet<&'a str>, handle: &'a str) {
435    roots.insert(handle);
436}
437
438/// Record an edge in one of [`Changes`]'s lists, at most once.
439///
440/// Keyed on `(from, to, kind)`, which is an edge's identity to ɴsɪ --
441/// `args` carry the priority and are what a re-arm replaces. Without
442/// this the lists were logs: a host that re-`connect`s the same edge
443/// every frame grew the record by a full `Edge`, arguments included,
444/// on every one of them, and the record is supposed to be net.
445fn record_edge(list: &mut Vec<Edge>, edge: Edge) {
446    match list.iter_mut().find(|recorded| {
447        recorded.from == edge.from
448            && recorded.to == edge.to
449            && recorded.kind == edge.kind
450    }) {
451        Some(recorded) => *recorded = edge,
452        None => list.push(edge),
453    }
454}
455
456/// The recorded scene graph.
457#[derive(Debug, Clone, Default)]
458#[non_exhaustive]
459pub struct Scene {
460    /// Nodes by handle, in creation order.
461    nodes: IndexMap<Handle, Node>,
462    /// Classified connections, in connection order.
463    edges: Vec<Edge>,
464    /// `Evaluate` calls, in call order, each with the node count at the
465    /// time so replay can put them back where they were.
466    ///
467    /// ɴsɪ's `Evaluate` "includes a block of interface calls from an
468    /// external source" -- an archive, a Lua script or a compiled
469    /// procedural. This crate does not execute one, so whatever it
470    /// would have produced is absent from the scene; recording the call
471    /// at least means a stream carrying one is not silently reduced to
472    /// a scene missing its geometry, with no error and no trace.
473    evaluations: Vec<Vec<OwnedArgument>>,
474    /// Edge positions keyed by source handle, and by destination.
475    ///
476    /// Resolution walks the graph per object, so without these every
477    /// hop of every walk scanned every edge -- quadratic in the scene,
478    /// which a production asset feels immediately. Rebuilt on removal
479    /// (rare) and appended to on `connect` (common).
480    by_from: HashMap<Handle, Vec<usize>>,
481    by_to: HashMap<Handle, Vec<usize>>,
482    /// Edge positions keyed by destination *and* destination attribute.
483    ///
484    /// `by_to` alone is not enough: a transform with twenty thousand
485    /// children has twenty thousand incoming `objects` edges, and
486    /// gathering attributes there would scan all of them once per
487    /// child. Keying on the attribute too makes that lookup
488    /// proportional to the matches rather than to the scene.
489    by_to_attr: HashMap<(Handle, Handle), Vec<usize>>,
490    /// What has changed since the last [`Scene::take_changes`].
491    ///
492    /// Private, and not part of [`Scene`]'s equality: two scenes with
493    /// the same nodes and edges are the same scene whether or not one
494    /// of them has been synchronised since.
495    changes: Changes,
496}
497
498/// Two scenes are equal when they describe the same thing.
499///
500/// Written out rather than derived because of what it must *exclude*:
501/// the pending [`Changes`], which say what happened to a scene rather
502/// than what it is -- a scene that has just been synchronised would
503/// otherwise stop being equal to the identical scene that has not --
504/// and the three edge indexes, which are a function of the edges they
505/// index.
506impl PartialEq for Scene {
507    fn eq(&self, other: &Self) -> bool {
508        self.nodes == other.nodes
509            && self.edges == other.edges
510            && self.evaluations == other.evaluations
511    }
512}
513
514impl Scene {
515    /// What has changed since this was last called, clearing the
516    /// record.
517    ///
518    /// ɴsɪ's `NSIRenderControl "synchronize"` is where a host asks a
519    /// renderer to catch up: the specification says "apply all the
520    /// **buffered** calls to scene's state", so the interval between
521    /// two synchronises is exactly one batch of edits. Observed on
522    /// 3Delight: edits made without synchronising change nothing and
523    /// report nothing; the synchronise then reports `Restarted`
524    /// followed by `Synchronized`, once, for the whole batch.
525    ///
526    /// Taking clears, because the alternative is a record that grows
527    /// for the life of an interactive session and a caller that must
528    /// remember where it read up to.
529    ///
530    /// Pass it to [`Scene::affected`] for the nodes to re-resolve.
531    /// This is the half that cannot be reconstructed after the fact --
532    /// a delete takes its edges with it, and a re-armed connection
533    /// leaves the graph looking exactly as it did.
534    pub fn take_changes(&mut self) -> Changes {
535        mem::take(&mut self.changes)
536    }
537
538    /// What has changed, without clearing it.
539    pub fn changes(&self) -> &Changes {
540        &self.changes
541    }
542
543    /// The nodes a [`Changes`] batch may have moved.
544    ///
545    /// Every rule here is the **inverse** of a walk this crate already
546    /// does upward. Resolution asks "what applies to this geometry" by
547    /// climbing `objects` to `.root` and gathering containers on the
548    /// way; a synchronise asks the same question backwards -- "given
549    /// this node changed, whose answers depended on it" -- so the
550    /// indexes that make the climb cheap (`by_to_attr`) make the
551    /// descent cheap too, and no new index is needed.
552    ///
553    /// The rules, and what each inverts:
554    ///
555    /// - a `transform`'s attribute, or an `objects` edge: everything
556    ///   below it, and any instancer drawing a prototype found there.
557    ///   Inverts the chain walk. Cameras and lights hang off `objects`
558    ///   like geometry, so they come along.
559    /// - an `attributes` node's attribute, or a shader edge into one:
560    ///   everything below each node it is bound to. Inverts the
561    ///   container gather. A binding onto a `set` reaches the set's
562    ///   members.
563    /// - a shader's own attribute, or a shader-network edge: the
564    ///   shader alone. Nothing about geometry changed.
565    /// - `.root` or `.global`: everything.
566    ///
567    /// Over-approximate on purpose -- see [`Affected`].
568    pub fn affected<'a>(&'a self, changes: &'a Changes) -> Affected<'a> {
569        let mut affected = Affected::default();
570
571        for (handle, _) in &changes.attributes {
572            if crate::is_reserved(handle) {
573                affected.everything = true;
574                continue;
575            }
576            match handle::map_get(&self.nodes, handle) {
577                Some(node) if node.node_type == "shader" => {
578                    affected.shaders.insert(handle.as_str());
579                }
580                Some(node) if node.node_type == "attributes" => {
581                    self.through_bindings(handle, &mut affected.roots);
582                }
583                // Anything else is a scene node: it may be the thing
584                // that moved, and it may be a transform with a subtree
585                // under it. The descent answers both.
586                _ => insert_root(&mut affected.roots, handle),
587            }
588            if self.is_output_node(handle) {
589                affected.outputs = true;
590            }
591        }
592
593        for handle in &changes.created {
594            insert_root(&mut affected.roots, handle);
595        }
596
597        // A deleted handle is gone from the graph, so there is nothing
598        // left to descend *from*: what it orphaned is reached through
599        // the edges the delete took with it, which is why they are
600        // recorded in full.
601        for handle in changes.deleted.keys() {
602            affected.roots.insert(handle.as_str());
603        }
604
605        for edge in changes
606            .edges_added
607            .iter()
608            .chain(&changes.edges_removed)
609            .chain(&changes.edges_rearmed)
610        {
611            // On `EdgeKind`, with no wildcard. Matching the
612            // *destination attribute string* let a new variant land
613            // silently in whatever arm the `_` was, and a
614            // `ShaderNetwork` whose port happens to be named `objects`
615            // took the child arm -- the resolver already carries a
616            // comment about that hazard, and this had re-learned it.
617            // Exhaustive here means the compiler asks the question.
618            match &edge.kind {
619                // A child, a set member: whatever hung below the
620                // source now hangs somewhere else.
621                EdgeKind::SceneMember | EdgeKind::SetMember => {
622                    insert_root(&mut affected.roots, &edge.from);
623                    if self.is_output_node(&edge.from)
624                        || self.is_output_node(&edge.to)
625                    {
626                        affected.outputs = true;
627                    }
628                }
629                // A prototype joining or leaving an instancer. The
630                // node whose answer moves is the **instancer**, and it
631                // is not below the prototype -- it is the other end of
632                // this edge, which is exactly why a walk that only
633                // descends from `edge.from` missed it: rendered, a
634                // severed `sourcemodels` leaves the instancer drawing
635                // a prototype the scene no longer has.
636                EdgeKind::InstanceSource => {
637                    insert_root(&mut affected.roots, &edge.from);
638                    affected.roots.insert(edge.to.as_str());
639                }
640                // A container bound to something, or unbound from it.
641                EdgeKind::AttributeBinding | EdgeKind::ShaderAttributes => {
642                    insert_root(&mut affected.roots, &edge.to);
643                    self.set_members(&edge.to, &mut affected.roots);
644                }
645                // A shader reaching an `attributes` node -- including a
646                // repeated `connect` that only changed `"priority"`,
647                // which is why re-armed edges are here.
648                EdgeKind::SurfaceShader
649                | EdgeKind::DisplacementShader
650                | EdgeKind::VolumeShader => {
651                    affected.shaders.insert(edge.from.as_str());
652                    self.through_bindings(&edge.to, &mut affected.roots);
653                }
654                // The output chain, and the things hung off it. A
655                // light set and a background layer belong to an
656                // `outputlayer`, and a lens shader to a camera: none
657                // of them is a material parameter, and filing them
658                // under `shaders` told a backend honouring light sets
659                // nothing at all.
660                EdgeKind::Screen
661                | EdgeKind::OutputLayer
662                | EdgeKind::OutputDriver
663                | EdgeKind::LightSet
664                | EdgeKind::BackgroundLayer
665                | EdgeKind::LensShader => {
666                    affected.outputs = true;
667                }
668                // `.global`'s own membership: it applies to the whole
669                // render, so the whole scene is the candidate.
670                EdgeKind::ExclusiveShading => {
671                    affected.everything = true;
672                }
673                // Bounds, subsurface sets and face sets attach to a
674                // geometry or a set and change what it resolves to.
675                EdgeKind::Bounds
676                | EdgeKind::SubsurfaceSet
677                | EdgeKind::FaceSet => {
678                    insert_root(&mut affected.roots, &edge.to);
679                    self.set_members(&edge.to, &mut affected.roots);
680                }
681                // A shader network edge is between shaders, and a
682                // carried connection this crate does not resolve is
683                // not known to reach geometry. Only ends that really
684                // are shader nodes go in `shaders`.
685                EdgeKind::ShaderNetwork { .. } | EdgeKind::Other { .. } => {
686                    for handle in [&edge.from, &edge.to] {
687                        if self.is_shader_node(handle) {
688                            affected.shaders.insert(handle.as_str());
689                        } else {
690                            insert_root(&mut affected.roots, handle);
691                        }
692                    }
693                }
694            }
695        }
696
697        if affected.everything {
698            affected.roots.clear();
699        }
700
701        affected
702    }
703
704    /// Everything at or below `handle` on the `objects` chain, plus any
705    /// instancer that draws a prototype found there.
706    ///
707    /// This is what an [`Affected`] root stands for. Call it when the
708    /// list is actually wanted -- a backend that is walking its own
709    /// objects can compare against the roots instead and never build
710    /// it.
711    ///
712    /// Iterative with an explicit stack: an ɴsɪ scene's depth is the
713    /// caller's, not ours, and a recursive walk here would overflow on
714    /// a deep chain. The `insert` doubles as the visited set, so a
715    /// cycle terminates.
716    pub fn descendants<'a>(&'a self, handle: &'a str) -> IndexSet<&'a str> {
717        let mut out = IndexSet::new();
718        self.descend(handle, &mut out);
719        out
720    }
721
722    fn descend<'a>(&'a self, handle: &'a str, out: &mut IndexSet<&'a str>) {
723        let mut stack = vec![handle];
724        while let Some(node) = stack.pop() {
725            if !out.insert(node) {
726                continue;
727            }
728            for edge in self.edges_to_attribute(node, "objects") {
729                stack.push(&edge.from);
730            }
731            // A prototype's mover moves every instancer drawing it, and
732            // the instancer is not below the transform that moved --
733            // it is reached the other way, through `sourcemodels`.
734            for edge in self.edges_from(node) {
735                if edge.kind.to_attribute() == "sourcemodels" {
736                    stack.push(&edge.to);
737                }
738            }
739        }
740    }
741
742    /// Everything an `attributes` node is bound to, and below that.
743    fn through_bindings<'a>(
744        &'a self,
745        handle: &str,
746        out: &mut IndexSet<&'a str>,
747    ) {
748        for edge in self.edges_from(handle) {
749            if matches!(
750                edge.kind.to_attribute(),
751                "geometryattributes" | "shaderattributes"
752            ) {
753                insert_root(out, &edge.to);
754                self.set_members(&edge.to, out);
755            }
756        }
757    }
758
759    /// If `handle` is a `set`, everything its members carry.
760    ///
761    /// One hop, not a recursion: a `set` inside a `set` contributes
762    /// nothing to what a geometry inherits -- rendered, and pinned by
763    /// `a_nested_sets_attributes_are_not_inherited` -- so descending
764    /// through nested sets would name nodes the renderer never reaches.
765    fn set_members<'a>(&'a self, handle: &str, out: &mut IndexSet<&'a str>) {
766        for edge in self.edges_to_attribute(handle, "members") {
767            insert_root(out, &edge.from);
768        }
769    }
770
771    /// Whether this handle is a shader node.
772    ///
773    /// Asked before filing anything under [`Affected::shaders`], whose
774    /// documented meaning is "maps one-to-one onto a renderer's
775    /// material parameters". A `set` reached through a `lightset` edge
776    /// is not that, and neither is a camera reached through a lens
777    /// shader.
778    fn is_shader_node(&self, handle: &str) -> bool {
779        handle::map_get(&self.nodes, handle)
780            .is_some_and(|node| node.node_type() == "shader")
781    }
782
783    /// Whether this handle is part of the camera/screen/layer/driver
784    /// chain, whose answers come from [`Scene::render_outputs`] rather
785    /// than from a geometry walk.
786    fn is_output_node(&self, handle: &str) -> bool {
787        handle::map_get(&self.nodes, handle).is_some_and(|node| {
788            node.node_type().ends_with("camera")
789                || matches!(
790                    node.node_type(),
791                    "screen" | "outputlayer" | "outputdriver"
792                )
793        })
794    }
795
796    /// The nodes, by handle, in creation order.
797    pub fn nodes(&self) -> impl Iterator<Item = (&str, &Node)> {
798        self.nodes
799            .iter()
800            .map(|(handle, node)| (handle.as_str(), node))
801    }
802
803    /// The recorded `Evaluate` calls, in call order.
804    ///
805    /// Each is the argument list as given. A backend that wants
806    /// archives or procedurals has to execute them itself: this crate
807    /// records the call and does not define an execution model for it.
808    pub fn evaluations(&self) -> impl Iterator<Item = &[OwnedArgument]> {
809        self.evaluations.iter().map(Vec::as_slice)
810    }
811
812    /// Record an `Evaluate`.
813    ///
814    /// Only the call, not where it fell among the nodes: replay emits
815    /// every `Evaluate` first, nothing reads a position, and a node
816    /// count kept here would be wrong the moment a `delete` shifted
817    /// it.
818    pub(crate) fn evaluate(&mut self, args: Vec<OwnedArgument>) {
819        self.evaluations.push(args);
820    }
821
822    /// One node by handle.
823    pub fn node(&self, handle: &str) -> Option<&Node> {
824        handle::map_get(&self.nodes, handle)
825    }
826
827    /// A node together with the scene's own copy of its handle.
828    ///
829    /// Resolution returns borrowed handles that outlive the `&str` a
830    /// caller passed in, so it needs the stored key, not the argument.
831    pub(crate) fn node_entry(&self, handle: &str) -> Option<(&str, &Node)> {
832        handle::map_entry(&self.nodes, handle)
833    }
834
835    /// The classified connections, in connection order.
836    pub fn edges(&self) -> impl Iterator<Item = &Edge> {
837        self.edges.iter()
838    }
839
840    /// How many nodes the scene holds.
841    pub fn len(&self) -> usize {
842        self.nodes.len()
843    }
844
845    /// Whether the scene holds no nodes.
846    pub fn is_empty(&self) -> bool {
847        self.nodes.is_empty()
848    }
849
850    /// The connections *out of* `handle`, in connection order.
851    ///
852    /// Indexed, so this does not scan the scene.
853    pub fn edges_from<'a>(
854        &'a self,
855        handle: &str,
856    ) -> impl Iterator<Item = &'a Edge> + use<'a> {
857        self.indexed(&self.by_from, handle)
858    }
859
860    /// The connections *into* `handle`, in connection order.
861    ///
862    /// Indexed, so this does not scan the scene.
863    pub fn edges_to<'a>(
864        &'a self,
865        handle: &str,
866    ) -> impl Iterator<Item = &'a Edge> + use<'a> {
867        self.indexed(&self.by_to, handle)
868    }
869
870    /// The connections into `handle` through `to_attribute`, in connection
871    /// order.
872    ///
873    /// Indexed on both, so this is proportional to the matches rather
874    /// than to the scene.
875    pub fn edges_to_attribute<'a>(
876        &'a self,
877        handle: &str,
878        to_attribute: &str,
879    ) -> impl Iterator<Item = &'a Edge> + use<'a> {
880        // Without `ustr_handles` this allocates two `String`s to probe
881        // the map, on what is the hot path's key: a `HashMap<(String,
882        // String), _>` cannot be probed with a pair of `&str`.
883        // Interned, the probe allocates nothing.
884        handle::get_pair(&self.by_to_attr, handle, to_attribute)
885            .into_iter()
886            .flatten()
887            .map(|position| &self.edges[*position])
888    }
889
890    fn indexed<'a>(
891        &'a self,
892        index: &'a HashMap<Handle, Vec<usize>>,
893        handle: &str,
894    ) -> impl Iterator<Item = &'a Edge> + use<'a> {
895        crate::handle::get(index, handle)
896            .into_iter()
897            .flatten()
898            .map(|position| &self.edges[*position])
899    }
900
901    /// Rebuild both edge indexes.
902    ///
903    /// Called after a removal, which shifts every later position.
904    fn reindex(&mut self) {
905        self.by_from.clear();
906        self.by_to.clear();
907        self.by_to_attr.clear();
908        for (position, edge) in self.edges.iter().enumerate() {
909            self.by_from
910                .entry(handle::handle(&edge.from))
911                .or_default()
912                .push(position);
913            self.by_to
914                .entry(handle::handle(&edge.to))
915                .or_default()
916                .push(position);
917            self.by_to_attr
918                .entry((
919                    handle::handle(&edge.to),
920                    handle::handle(edge.kind.to_attribute()),
921                ))
922                .or_default()
923                .push(position);
924        }
925    }
926
927    /// Create a node.
928    ///
929    /// # Errors
930    ///
931    /// [`RecordError::TypeMismatch`] when the handle exists with a
932    /// different type. ɴsɪ: "the function does nothing if all other
933    /// parameters match the call which created that node. Otherwise, it
934    /// emits an error." Re-creating with the *same* type is a no-op, as
935    /// ɴsɪ says.
936    pub fn create(
937        &mut self,
938        handle: &str,
939        node_type: &str,
940    ) -> Result<(), RecordError> {
941        // ɴsɪ's reserved handles exist already. 3Delight answers a
942        // `create` on one with "already exists"; accepting it here kept
943        // a node that replay then drops, so the scene changed on its
944        // own first round trip.
945        if crate::is_reserved(handle) {
946            return Err(RecordError::Reserved {
947                handle: handle.to_string(),
948            });
949        }
950
951        match handle::map_get(&self.nodes, handle) {
952            Some(existing) if existing.node_type() != node_type => {
953                Err(RecordError::TypeMismatch {
954                    handle: handle.to_string(),
955                    existing: existing.node_type().to_string(),
956                    requested: node_type.to_string(),
957                })
958            }
959            Some(_) => Ok(()),
960            None => {
961                self.nodes.insert(
962                    crate::handle::handle(handle),
963                    Node {
964                        node_type: crate::handle::handle(node_type),
965                        ..Node::default()
966                    },
967                );
968                self.changes.created.insert(handle::handle(handle));
969                Ok(())
970            }
971        }
972    }
973
974    /// Delete a node and every edge that touches it.
975    ///
976    /// `shift_remove` rather than `swap_remove`: insertion order is the
977    /// replay order and must survive a delete.
978    ///
979    /// # Errors
980    ///
981    /// [`RecordError::Reserved`] for `.root` or `.global`. ɴsɪ: "it is
982    /// not possible to delete the root or the global node." Deleting
983    /// `.root` here would strip every membership edge in the scene.
984    pub fn delete(&mut self, handle: &str) -> Result<(), RecordError> {
985        if crate::is_reserved(handle) {
986            Err(RecordError::Reserved {
987                handle: handle.to_string(),
988            })
989        } else {
990            // Recorded *before* the removal: afterwards the type is
991            // gone and the edges that named this handle cannot be
992            // found, and a consumer working out what the delete
993            // orphaned needs both.
994            if let Some(node) = handle::map_remove(&mut self.nodes, handle) {
995                handle::set_remove(&mut self.changes.created, handle);
996                self.changes
997                    .deleted
998                    .insert(handle::handle(handle), node.node_type);
999            }
1000            for edge in self
1001                .edges
1002                .iter()
1003                .filter(|e| e.from == handle || e.to == handle)
1004            {
1005                record_edge(&mut self.changes.edges_removed, edge.clone());
1006            }
1007            self.edges.retain(|e| e.from != handle && e.to != handle);
1008            self.reindex();
1009            Ok(())
1010        }
1011    }
1012
1013    /// Whether `handle` names something a connection may refer to.
1014    ///
1015    /// ɴsɪ's `.root` and `.global` are reserved and "don't need to be
1016    /// created", so they count as known without appearing in `nodes`.
1017    fn is_known(&self, handle: &str) -> bool {
1018        handle == crate::ROOT
1019            || handle == crate::GLOBAL
1020            || handle::map_get(&self.nodes, handle).is_some()
1021    }
1022
1023    /// Delete a node and, recursively, the nodes that only fed it.
1024    ///
1025    /// ɴsɪ: "nodes which connect to the specified node are recursively
1026    /// removed, unless they meet one of the following conditions: they
1027    /// also have connections which do not eventually lead to the
1028    /// specified node; their connection to the deleted node was created
1029    /// with a strength greater than 0." That is what makes deleting a
1030    /// whole shader network one call.
1031    ///
1032    /// # Errors
1033    ///
1034    /// [`RecordError::Reserved`] for `.root` or `.global`.
1035    pub fn delete_recursive(
1036        &mut self,
1037        handle: &str,
1038    ) -> Result<(), RecordError> {
1039        if crate::is_reserved(handle) {
1040            return Err(RecordError::Reserved {
1041                handle: handle.to_string(),
1042            });
1043        }
1044
1045        let mut doomed = HashSet::new();
1046        doomed.insert(handle.to_string());
1047
1048        // Grow the set until it stops growing: a node joins when every
1049        // connection it makes leads into the set, and none of those is
1050        // strong enough to block.
1051        loop {
1052            let candidates = doomed
1053                .iter()
1054                .flat_map(|node| self.edges_to(node))
1055                .filter(|edge| edge.strength() <= 0)
1056                .map(|edge| edge.from().to_string())
1057                .filter(|from| !doomed.contains(from.as_str()))
1058                .collect::<Vec<_>>();
1059
1060            let mut grew = false;
1061            for candidate in candidates {
1062                let leads_elsewhere = self
1063                    .edges_from(&candidate)
1064                    .any(|edge| !doomed.contains(edge.to()));
1065
1066                // The strength rule is about *this* node's connection to
1067                // anything being deleted, not only about how it was
1068                // first reached. Checking it at discovery alone let a
1069                // node be swept in through a second, weak path.
1070                let held = self.edges_from(&candidate).any(|edge| {
1071                    doomed.contains(edge.to()) && edge.strength() > 0
1072                });
1073
1074                if !leads_elsewhere && !held && doomed.insert(candidate) {
1075                    grew = true;
1076                }
1077            }
1078
1079            if !grew {
1080                break;
1081            }
1082        }
1083
1084        for handle in &doomed {
1085            if let Some(node) = handle::map_get(&self.nodes, handle) {
1086                let node_type = handle::copy(&node.node_type);
1087                handle::set_remove(&mut self.changes.created, handle);
1088                self.changes
1089                    .deleted
1090                    .insert(handle::handle(handle), node_type);
1091            }
1092        }
1093        for edge in self.edges.iter().filter(|edge| {
1094            doomed.contains(edge.from()) || doomed.contains(edge.to())
1095        }) {
1096            record_edge(&mut self.changes.edges_removed, edge.clone());
1097        }
1098
1099        self.nodes
1100            .retain(|handle, _| !doomed.contains(handle.as_str()));
1101        self.edges.retain(|edge| {
1102            !doomed.contains(edge.from()) && !doomed.contains(edge.to())
1103        });
1104        self.reindex();
1105
1106        Ok(())
1107    }
1108
1109    /// Set static attributes, overwriting by name.
1110    ///
1111    /// ɴsɪ: "Setting an attribute using this function replaces any value
1112    /// previously set by `NSISetAttribute` or `NSISetAttributeAtTime`."
1113    /// So this also clears every motion sample of the same name --
1114    /// otherwise a node set static after being sampled would still look
1115    /// motion-blurred to the resolver.
1116    ///
1117    /// # Errors
1118    ///
1119    /// [`RecordError::UnknownHandle`] when the node does not exist.
1120    /// 3Delight answers the same call with "unknown node handle". A
1121    /// fabricated node is worse than a rejected one: it joins the scene,
1122    /// satisfies later `connect` calls, and replays as a `Create` the
1123    /// renderer never wrote.
1124    pub fn set_attribute(
1125        &mut self,
1126        handle: &str,
1127        args: Vec<OwnedArgument>,
1128    ) -> Result<(), RecordError> {
1129        // Existence first, so a rejected call records nothing.
1130        self.node_mut(handle)?;
1131        let node_handle = handle::handle(handle);
1132        // `nodes` and `changes` are separate fields, so the node and
1133        // the journal are borrowed at once. Through `node_mut` they
1134        // are not, and carrying the names out of the loop in a `Vec`
1135        // to record them afterwards cost a clone of every one.
1136        // SAFETY: `node_mut` above returned `Ok`, which means it
1137        // either found this handle or created it, and nothing since
1138        // could have removed it.
1139        let node = self
1140            .nodes
1141            .get_mut(&node_handle)
1142            .expect("node_mut found or created it");
1143        for arg in args {
1144            let name = handle::handle(&arg.name);
1145            // Only when the node has samples: reaching for the table
1146            // through `sample_table_mut` would allocate one for every
1147            // node that has an attribute, which is most of a scene.
1148            if let Some(table) = node.samples.as_mut() {
1149                table.shift_remove(&name);
1150            }
1151            self.changes
1152                .attributes
1153                .insert((handle::copy(&node_handle), handle::copy(&name)));
1154            node.attribute_table_mut().insert(name, arg);
1155        }
1156        Ok(())
1157    }
1158
1159    /// A node to mutate, or [`RecordError::UnknownHandle`].
1160    ///
1161    /// ɴsɪ's reserved handles are created on demand: they "don't need to
1162    /// be created using NSICreate", but they do carry attributes.
1163    fn node_mut(&mut self, handle: &str) -> Result<&mut Node, RecordError> {
1164        if crate::is_reserved(handle) {
1165            Ok(self.nodes.entry(crate::handle::handle(handle)).or_default())
1166        } else {
1167            handle::map_get_mut(&mut self.nodes, handle).ok_or_else(|| {
1168                RecordError::UnknownHandle {
1169                    handle: handle.to_string(),
1170                }
1171            })
1172        }
1173    }
1174
1175    /// Set attributes at one motion sample, keeping samples time-sorted.
1176    ///
1177    /// # Errors
1178    ///
1179    /// [`RecordError::UnknownHandle`] when the node does not exist.
1180    pub fn set_attribute_at_time(
1181        &mut self,
1182        handle: &str,
1183        time: f64,
1184        args: Vec<OwnedArgument>,
1185    ) -> Result<(), RecordError> {
1186        // 3Delight answers a non-finite time with `E6026 invalid time`.
1187        if !time.is_finite() {
1188            return Err(RecordError::InvalidTime {
1189                handle: handle.to_string(),
1190            });
1191        }
1192
1193        // `-0.0` and `0.0` are one sample to the renderer, which reads a
1194        // `-0` time as `+0`. Keeping them apart handed a backend two
1195        // matrices at times that compare equal -- a zero-length motion
1196        // segment.
1197        let time = time + 0.0;
1198
1199        // Existence first, so a rejected call records nothing.
1200        self.node_mut(handle)?;
1201        let node_handle = handle::handle(handle);
1202        // See `set_attribute` for why the node is reached for by
1203        // field rather than through `node_mut`.
1204        // SAFETY: `node_mut` above returned `Ok`, which means it
1205        // either found this handle or created it, and nothing since
1206        // could have removed it.
1207        let node = self
1208            .nodes
1209            .get_mut(&node_handle)
1210            .expect("node_mut found or created it");
1211        for arg in args {
1212            let name = handle::handle(&arg.name);
1213            // ɴsɪ: setting at a time "replaces any value previously set
1214            // by NSISetAttribute", so the static value goes.
1215            if let Some(table) = node.attributes.as_mut() {
1216                table.shift_remove(&name);
1217            }
1218            self.changes
1219                .attributes
1220                .insert((handle::copy(&node_handle), handle::copy(&name)));
1221
1222            // Appended, never merged: a re-set at a time already
1223            // recorded is another call, and what it superseded is part
1224            // of the record. `Node::samples` says why.
1225            node.sample_table_mut()
1226                .entry(name)
1227                .or_default()
1228                .push((time, arg));
1229        }
1230
1231        Ok(())
1232    }
1233
1234    /// Remove one attribute by name, from static and every time sample.
1235    /// Silent when absent, as ɴsɪ is.
1236    pub fn delete_attribute(&mut self, handle: &str, name: &str) {
1237        // Recorded whether or not it was set: ɴsɪ is silent about
1238        // deleting an absent attribute, and a consumer asking "what
1239        // should I look at again" is not harmed by one extra name.
1240        self.changes
1241            .attributes
1242            .insert((handle::handle(handle), handle::handle(name)));
1243        if let Some(node) = handle::map_get_mut(&mut self.nodes, handle) {
1244            if let Some(table) = node.attributes.as_mut() {
1245                table.shift_remove(&handle::handle(name));
1246            }
1247            if let Some(table) = node.samples.as_mut() {
1248                table.shift_remove(&handle::handle(name));
1249            }
1250        }
1251    }
1252
1253    /// Classify and record a connection at the default priority.
1254    ///
1255    /// An unmapped destination propagates rather than being recorded as
1256    /// a guess.
1257    pub fn connect(
1258        &mut self,
1259        from: &str,
1260        from_attribute: Option<&str>,
1261        to: &str,
1262        to_attribute: &str,
1263    ) -> Result<(), RecordError> {
1264        self.connect_with_arguments(
1265            from,
1266            from_attribute,
1267            to,
1268            to_attribute,
1269            Vec::new(),
1270        )
1271    }
1272
1273    /// Classify and record a connection carrying its ɴsɪ arguments.
1274    ///
1275    /// ɴsɪ: "It is not an error to create a connection which already
1276    /// exists." A repeat therefore updates the existing edge's arguments
1277    /// rather than adding a second one. Recording both would make the
1278    /// node look like it had two parents, which would fail resolution
1279    /// for it and everything beneath it.
1280    pub fn connect_with_arguments(
1281        &mut self,
1282        from: &str,
1283        from_attribute: Option<&str>,
1284        to: &str,
1285        to_attribute: &str,
1286        args: Vec<OwnedArgument>,
1287    ) -> Result<(), RecordError> {
1288        let kind = classify(from_attribute, to_attribute);
1289
1290        // ɴsɪ: "the nodes on which the connection is performed must
1291        // exist." `.root` and `.global` are reserved and need no
1292        // `create`.
1293        for handle in [from, to] {
1294            if !self.is_known(handle) {
1295                return Err(RecordError::UnknownHandle {
1296                    handle: handle.to_string(),
1297                });
1298            }
1299        }
1300
1301        // Through the index, not over every edge in the scene. A
1302        // repeated `connect` has to be detected before one is appended,
1303        // and scanning `edges` for it made recording **quadratic**:
1304        // measured, one transform with 1000 children took 67 ms to
1305        // build, 4000 took 749 ms and 16 000 took 17 s. An interactive
1306        // host connects per edit, so it paid that on every one.
1307        let existing = handle::get(&self.by_from, from).and_then(|positions| {
1308            positions.iter().copied().find(|&at| {
1309                let edge = &self.edges[at];
1310                edge.to == to && edge.kind == kind
1311            })
1312        });
1313
1314        let mut rearmed = None;
1315        match existing.map(|at| &mut self.edges[at]) {
1316            Some(existing) => {
1317                // No edge appears or disappears here, and ɴsɪ's
1318                // `"priority"` rides on these arguments -- so a record
1319                // keyed on additions and removals would miss a scene
1320                // changing which shader wins.
1321                existing.args = args;
1322                rearmed = Some(existing.clone());
1323            }
1324            None => {
1325                self.by_from
1326                    .entry(handle::handle(from))
1327                    .or_default()
1328                    .push(self.edges.len());
1329                self.by_to
1330                    .entry(handle::handle(to))
1331                    .or_default()
1332                    .push(self.edges.len());
1333                self.by_to_attr
1334                    .entry((
1335                        handle::handle(to),
1336                        handle::handle(kind.to_attribute()),
1337                    ))
1338                    .or_default()
1339                    .push(self.edges.len());
1340                let edge = Edge {
1341                    from: handle::handle(from),
1342                    to: handle::handle(to),
1343                    kind,
1344                    args,
1345                };
1346                record_edge(&mut self.changes.edges_added, edge.clone());
1347                self.edges.push(edge);
1348            }
1349        }
1350
1351        if let Some(edge) = rearmed {
1352            record_edge(&mut self.changes.edges_rearmed, edge);
1353        }
1354
1355        Ok(())
1356    }
1357
1358    /// Remove a connection. Silent when absent, as ɴsɪ is.
1359    ///
1360    /// ɴsɪ: "the handle for either node, as well as any or all of the
1361    /// attributes, may be the special value `.all`. This will remove all
1362    /// connections which match the other parameters." So each of the
1363    /// four positions matches everything when it is [`ALL`].
1364    ///
1365    /// The connection *arguments* are not part of an edge's identity:
1366    /// ɴsɪ's disconnect names four things and priority is not one.
1367    pub fn disconnect(
1368        &mut self,
1369        from: &str,
1370        from_attribute: Option<&str>,
1371        to: &str,
1372        to_attribute: &str,
1373    ) -> Result<(), RecordError> {
1374        // `.all` matches every class, so there is nothing to classify.
1375        let kind = if to_attribute == ALL {
1376            None
1377        } else {
1378            Some(classify(from_attribute, to_attribute))
1379        };
1380
1381        let from_port = from_attribute.unwrap_or_default();
1382        let any_port = from_port == ALL;
1383
1384        let mut removed = Vec::new();
1385        self.edges.retain(|edge| {
1386            let port_matches = any_port
1387                || match &edge.kind {
1388                    EdgeKind::ShaderNetwork {
1389                        from_port: port, ..
1390                    } => port == from_port,
1391                    _ => from_port.is_empty(),
1392                };
1393
1394            let attr_matches = match &kind {
1395                // A named `to_attribute` fixes the class outright, unless the
1396                // source port is `.all` -- then only the destination
1397                // attribute is being matched.
1398                Some(kind) if !any_port => &edge.kind == kind,
1399                Some(kind) => edge.kind.to_attribute() == kind.to_attribute(),
1400                None => true,
1401            };
1402
1403            let matches = (from == ALL || edge.from == from)
1404                && (to == ALL || edge.to == to)
1405                && port_matches
1406                && attr_matches;
1407
1408            if matches {
1409                // Kept in full, because a `.all` pattern cannot be
1410                // re-expanded once the edges it named are gone.
1411                removed.push(edge.clone());
1412            }
1413
1414            !matches
1415        });
1416        for edge in removed {
1417            record_edge(&mut self.changes.edges_removed, edge);
1418        }
1419        self.reindex();
1420
1421        Ok(())
1422    }
1423}
1424
1425#[cfg(test)]
1426mod tests;