sv_sim_sim/analysis/

graph.rs

//! Task 8 (NL-007, NL-063): the `{net,process}` driver-dependency graph and
//! the WOCB partitioning pass over it (netlist-analysis.md §C.1;
//! ARCHITECTURE §2/§6.5).
//!
//! **Load-bearing finding, TDD'd against real `sv-lang` output (verified
//! this task): two anonymous members of the SAME kind in one scope
//! (e.g. two `assign` statements, or an `assign` and a `ProceduralBlock`)
//! all share the identical `SymbolId` — the scope's own hierarchical path**
//! (confirmed empirically: `module m; assign x=a; assign y=b; endmodule`
//! gives BOTH `ContinuousAssign` members `id() == SymbolId("m")`, and a
//! module with one `assign` and one anonymous `always_ff` gives the
//! `ContinuousAssign` AND the `ProceduralBlock` the SAME `id() ==
//! SymbolId("m")` too). This makes the `SymbolId`-keyed
//! `netlist::symbol_key_map` table (last-write-wins) UNSAFE for resolving a
//! `DriverInfo::containing_symbol()`/`AnalyzedProcedure::symbol()` handle
//! back to its owning member's `SymbolKey` — exactly the identity this
//! module needs to build a `{net,process}` graph node for "the process a
//! driver/read belongs to". This module therefore resolves a containing/
//! procedure symbol to its `SymbolKey` via [`member_position_key`]: a
//! direct positional scan of `scope.members()` using `Symbol`'s own
//! pointer-identity `PartialEq` (`ast.rs:22589-22595`, "Symbol identity is
//! its address"), which distinguishes two colliding-`id()` members
//! correctly since it never touches `id()` at all. Net/variable resolution
//! (which never collides — every named net's own `id()` is a real,
//! unique hierarchical path) keeps using `netlist::symbol_key_map`, reused
//! rather than re-derived, per this workspace's "never re-derived a second,
//! independently-reasoned way" posture.

use crate::symid::SymbolUid;
use std::collections::{HashMap, HashSet};

use crate::netlist::{
    DriverEntry, InstanceId, InstantiatedSignalId, Netlist, NetlistView, StaticSensitivity,
    SymbolKey, TemplateId,
};

use super::{ClockDomainId, RegionId};

/// Whether a graph node is a net (a `Template.signals` member) or a process
/// (a `ProceduralBlock`/`ContinuousAssign`/sub-`Instance` boundary driver).
/// Crate-private: external consumers only ever see the resulting
/// [`Partition::nets`]/[`Partition::processes`] split, never this tag
/// itself.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum NodeKind {
    Net,
    Process,
}

/// One WOCB partition: a set of `{net,process}` graph nodes that must be
/// evaluated together (netlist-analysis.md's `Partition`). `clock_domain`
/// is `None` for a purely combinational/mixed region.
#[derive(Clone, Debug)]
pub struct Partition {
    pub id: RegionId,
    pub processes: Vec<InstantiatedSignalId>,
    pub nets: Vec<InstantiatedSignalId>,
    pub clock_domain: Option<ClockDomainId>,
}

/// The `{net,process}` driver-dependency graph (NL-063): `write_edges()` is
/// `(process) -write-> (net)` for every real (non-input-port-boundary)
/// `DriverInfo`; `read_edges()` is `(net) -read-> (process)` for every
/// `AnalyzedProcedure::read_set()` entry whose net has at least one
/// internal (non-input-port) driver somewhere in this graph — a pure
/// top-level input has no driver of its own to synchronize with, so a read
/// of it is never a partition-membership-relevant dependency (see
/// [`build_driver_graph`]'s own doc comment for the fixture that pins this
/// exact filter).
#[derive(Default)]
pub struct DriverGraph {
    write_edges: Vec<(InstantiatedSignalId, InstantiatedSignalId)>,
    read_edges: Vec<(InstantiatedSignalId, InstantiatedSignalId)>,
    node_kinds: HashMap<InstantiatedSignalId, NodeKind>,
    /// (Task 10, NL-117.) Every node this graph knows about (every
    /// `Template.signals` member and every `Template.processes` member, fanned
    /// out per instance), in first-seen, fully deterministic order (per-
    /// `Template` declaration order, then `registration_order()`) — NOT
    /// filtered to nodes that happen to appear in `write_edges`/`read_edges`.
    /// [`partition`] seeds its node set from this list before walking edges,
    /// so a net or process with zero write/read edges (e.g. a bare,
    /// never-driven/never-read `interconnect` net) still gets its own
    /// singleton `Partition` rather than silently vanishing from the graph
    /// entirely — the concrete regression this field exists to fix (a
    /// declared-but-unconnected signal is not the same thing as "does not
    /// exist," and dropping it from partitioning outright is itself a form
    /// of misclassifying it, which NL-117's own acceptance rules out).
    all_nodes: Vec<InstantiatedSignalId>,
    /// Every clocked process's own intrinsic clock domain (from its
    /// `StaticSensitivity::Explicit`'s first edge) — the union-find's
    /// starting point for domain propagation in [`partition`]. A node not
    /// present here has no intrinsic domain of its own (combinational, or a
    /// sub-instance boundary).
    process_domain: HashMap<InstantiatedSignalId, ClockDomainId>,
    /// `ClockDomainId(i)` names `domain_registry[i]` — `(clock signal,
    /// edge)` — interned in first-discovered order (`registration_order()`,
    /// then each instance's own `Template.processes` order): deterministic,
    /// never a `HashMap`-iteration-order accident.
    domain_registry: Vec<(InstantiatedSignalId, crate::state::EdgeKind)>,
}

impl DriverGraph {
    /// `(process, net)` pairs — one per real `DriverEntry`.
    pub fn write_edges(&self) -> &[(InstantiatedSignalId, InstantiatedSignalId)] {
        &self.write_edges
    }

    /// `(net, process)` pairs — one per read-set entry (see this module's
    /// own doc comment for the input-port exclusion).
    pub fn read_edges(&self) -> &[(InstantiatedSignalId, InstantiatedSignalId)] {
        &self.read_edges
    }

    /// The interned clock-signal registry (`analysis::analyze`'s own
    /// source for `StaticAnalysisResult.clock_domains`) — crate-internal,
    /// not part of this module's public surface (mirrors
    /// `Netlist::member_symbol`'s own "internal handle no external
    /// `NetlistView` consumer needs" reasoning).
    pub(crate) fn clock_domain_registry(
        &self,
    ) -> &[(InstantiatedSignalId, crate::state::EdgeKind)] {
        &self.domain_registry
    }
}

/// Resolves a raw `sv_lang::Symbol` (a `DriverInfo::containing_symbol()` or
/// an `AnalyzedProcedure::symbol()`) to its `SymbolKey` within `members` —
/// the flat, position-ordered `scope.members()` list `SymbolKey`
/// assignment is defined over everywhere else in this crate — via pointer
/// identity, never `SymbolId` (see this module's own doc comment on why the
/// latter is unsafe for a `ProceduralBlock`/`ContinuousAssign` container).
fn member_position_key(
    members: &[sv_lang::Symbol<'_>],
    target: sv_lang::Symbol<'_>,
) -> Option<SymbolKey> {
    members
        .iter()
        .position(|&m| m == target)
        .map(|i| SymbolKey(i as u32))
}

/// Resolves every real (non-input-port) driver of `net_symbol` to
/// `(containing construct's SymbolKey, DriverKind)`. An input-port driver
/// (`DriverInfo::is_input_port()`) is the parent-scope boundary case —
/// already modeled by this pass's own synthetic port-connection machinery
/// (`netlist::elaborate`'s `ContAssignTemplate`/`SubInstanceSlot`), never a
/// node in THIS per-instance `{net,process}` graph — so it is filtered out
/// here, the ONE place this decision is made (both [`build_driver_graph`]
/// and [`populate_driver_kinds`] call this, never a second,
/// independently-reasoned driver walk). A driver whose containing symbol
/// cannot be positionally resolved within `members` (a construct this
/// wave's graph does not model, e.g. a driver inside a different instance
/// reached through an interface) is defensively skipped too — never a
/// panic, and not a `sv_lang`/`sv_lang_kinds` kind-match this workspace's
/// exhaustive-match rule binds (it's a symbol-identity lookup, not a kind
/// dispatch).
fn resolve_net_drivers<'d>(
    slang_analysis: &sv_lang::Analysis<'d>,
    net_symbol: sv_lang::Symbol<'d>,
    members: &[sv_lang::Symbol<'d>],
) -> Vec<(SymbolKey, sv_lang::DriverKind)> {
    slang_analysis
        .drivers(net_symbol)
        .filter(|d| !d.is_input_port())
        .filter_map(|d| {
            member_position_key(members, d.containing_symbol()).map(|key| (key, d.kind()))
        })
        .collect()
}

/// **Second load-bearing finding, TDD'd against real `sv-lang` output
/// (verified this task): `sv_lang::Analysis` (`slang::analysis::
/// AnalysisManager`) tracks driver/procedure data per CANONICAL instance
/// only** — confirmed empirically against a fixture with two instances
/// (`i0`, `i1`) of one shared module: `slang_analysis.procedures(i0_body)
/// .count() == 3` (i0 happened to be canonical) while
/// `slang_analysis.procedures(i1_body).count() == 0`, even though Task 2's
/// own `DisableInstanceCaching` finding already established `i0`'s and
/// `i1`'s own AST bodies are genuinely distinct `Symbol`s (never pointer-
/// shared). This is `AnalysisManager.h`'s own documented behavior ("driver
/// state tracked PER CANONICAL INSTANCE") — a SEPARATE, analysis-layer-only
/// canonicalization from `DisableInstanceCaching`'s elaboration-layer
/// pointer-identity guarantee. Consequence: `Analysis::drivers`/
/// `Analysis::procedures` can only ever be queried against ONE
/// representative instance per deduped `Template` — never a genuinely
/// per-instance call — so this function computes the write/read STRUCTURAL
/// PATTERN (as `(SymbolKey, SymbolKey)` pairs) once per `Template`, against
/// its own canonical instance (found by [`representative_instance_of`],
/// which — unlike `populate_driver_kinds`' "any instance is correct,
/// Decision 4 guarantees identical shape" reasoning — must specifically
/// locate the one instance `Analysis` actually populated data for, not
/// merely the lowest `InstanceId`), then FANS that pattern OUT onto every
/// instance sharing the `Template`, using each instance's own `InstanceId`.
/// Clock-domain seeding stays genuinely per-instance regardless (NL-076: it
/// never calls `Analysis` at all — it reads `Template.processes`, already
/// derived directly from raw `sv_lang` in `elaborate()`, so `i0`'s and
/// `i1`'s own distinct `InstantiatedSignalId`s for their `clk` port already
/// differ correctly with no canonicalization pitfall).
///
/// **Deviation from the plan's literal "built by zipping
/// `Analysis::drivers()`/`Analysis::driver_handles()`" wording:** this
/// implementation uses `Analysis::drivers()` (`DriverInfo`) alone —
/// `DriverInfo` already exposes both `.kind()` (`DriverEntry.driver_kind`)
/// and `.containing_symbol()` (the process-identity resolution this graph
/// needs); `Analysis::driver_handles()`'s `ValueDriver` adds
/// `.source()`/`.is_unidirectional_port()`/bit-range/override-range data no
/// test in this task's plan section exercises, so it is not fetched. Adapts
/// minimally, keeps the specified edge set.
pub fn build_driver_graph<'d>(
    netlist: &Netlist<'d>,
    slang_analysis: &sv_lang::Analysis<'d>,
) -> DriverGraph {
    let mut graph = DriverGraph::default();
    let mut domain_ids: HashMap<InstantiatedSignalId, ClockDomainId> = HashMap::new();

    for template_index in 0..netlist.templates.len() {
        let tmpl_id = TemplateId(template_index as u32);
        let template = netlist.template(tmpl_id);
        // Declaration order (NL-028), never a `HashSet`-iteration-order
        // accident.
        let net_key_order: Vec<SymbolKey> = template.signals.iter().map(|s| s.key).collect();
        let net_key_set: HashSet<SymbolKey> = net_key_order.iter().copied().collect();

        let Some(rep_instance) = representative_instance_of(netlist, slang_analysis, tmpl_id)
        else {
            continue;
        };
        let Some(body) = netlist.instance_symbol(rep_instance).instance_body() else {
            continue;
        };
        let members: Vec<sv_lang::Symbol<'_>> = crate::netlist::module_items(&body);
        let scope_keys = crate::netlist::symbol_key_map(body);

        // Structural write pattern (SymbolKey -> SymbolKey), computed ONCE
        // against the canonical representative.
        let mut write_pattern: Vec<(SymbolKey, SymbolKey)> = Vec::new();
        let mut has_internal_driver: HashSet<SymbolKey> = HashSet::new();
        for &net_key in &net_key_order {
            let net_symbol = netlist.member_symbol(rep_instance, net_key);
            let drivers = resolve_net_drivers(slang_analysis, net_symbol, &members);
            if !drivers.is_empty() {
                has_internal_driver.insert(net_key);
            }
            for (proc_key, _kind) in drivers {
                write_pattern.push((proc_key, net_key));
            }
        }

        // Structural read pattern (SymbolKey -> SymbolKey), same
        // canonical-representative restriction, filtered to nets with at
        // least one internal driver (see this module's own doc comment on
        // `DriverGraph`).
        let mut read_pattern: Vec<(SymbolKey, SymbolKey)> = Vec::new();
        for proc in slang_analysis.procedures(body) {
            let Some(proc_key) = member_position_key(&members, proc.symbol()) else {
                continue;
            };
            for r in proc.read_set() {
                let Some(&net_key) = scope_keys.get(&r.symbol().uid()) else {
                    continue;
                };
                if !net_key_set.contains(&net_key) || !has_internal_driver.contains(&net_key) {
                    continue;
                }
                read_pattern.push((net_key, proc_key));
            }
        }

        // Fan the structural pattern out onto every instance sharing this
        // Template, in deterministic `registration_order()`.
        for instance_id in netlist.registration_order() {
            if netlist.instance(instance_id).template != tmpl_id {
                continue;
            }

            for &net_key in &net_key_order {
                let net_sig = InstantiatedSignalId {
                    instance: instance_id,
                    member: net_key,
                };
                graph.node_kinds.insert(net_sig, NodeKind::Net);
                graph.all_nodes.push(net_sig);
            }
            for proc in &template.processes {
                let proc_sig = InstantiatedSignalId {
                    instance: instance_id,
                    member: proc.key,
                };
                graph
                    .node_kinds
                    .entry(proc_sig)
                    .or_insert(NodeKind::Process);
                graph.all_nodes.push(proc_sig);
            }
            for &(proc_key, net_key) in &write_pattern {
                let proc_sig = InstantiatedSignalId {
                    instance: instance_id,
                    member: proc_key,
                };
                let net_sig = InstantiatedSignalId {
                    instance: instance_id,
                    member: net_key,
                };
                graph
                    .node_kinds
                    .entry(proc_sig)
                    .or_insert(NodeKind::Process);
                graph.write_edges.push((proc_sig, net_sig));
            }
            for &(net_key, proc_key) in &read_pattern {
                let proc_sig = InstantiatedSignalId {
                    instance: instance_id,
                    member: proc_key,
                };
                let net_sig = InstantiatedSignalId {
                    instance: instance_id,
                    member: net_key,
                };
                graph
                    .node_kinds
                    .entry(proc_sig)
                    .or_insert(NodeKind::Process);
                graph.read_edges.push((net_sig, proc_sig));
            }

            // Clock-domain seeding: genuinely per-instance (NL-076), never
            // Analysis-dependent — see this function's own doc comment.
            for proc in &template.processes {
                if let StaticSensitivity::Explicit { edges } = &proc.sensitivity
                    && let Some(&(clk_key, edge_kind)) = edges.first()
                {
                    let proc_sig = InstantiatedSignalId {
                        instance: instance_id,
                        member: proc.key,
                    };
                    let clk_sig = InstantiatedSignalId {
                        instance: instance_id,
                        member: clk_key,
                    };
                    let domain_id = *domain_ids.entry(clk_sig).or_insert_with(|| {
                        let id = ClockDomainId(graph.domain_registry.len() as u32);
                        graph.domain_registry.push((clk_sig, edge_kind));
                        id
                    });
                    graph.process_domain.insert(proc_sig, domain_id);
                }
            }
        }
    }

    graph
}

/// Finds the one instance of `tmpl` that `sv_lang::Analysis` actually
/// populated driver/procedure data for (see [`build_driver_graph`]'s own
/// doc comment on why this is NOT simply "the lowest `InstanceId`" in
/// general — it happens to coincide with DFS-first-visited in the fixtures
/// this task's tests use, but this function verifies it directly against
/// `Analysis` itself rather than assuming that correlation holds). A
/// `Template` with no processes AND no continuous assigns has nothing for
/// `Analysis` to canonicalize differently across its instances, so the
/// first one (`registration_order()`) is used without probing. Returns
/// `None` only if `tmpl` has zero instances, which cannot happen for a
/// `Netlist` this crate's own `elaborate()` produced (defensive only).
///
/// `pub(crate)` (Task 9): `analysis::dpi::collect_call_tags` needs the
/// SAME canonical-representative resolution to enumerate `Analysis`-backed
/// call sites (`Analysis::procedures(scope).call_expressions()`) — reused
/// rather than re-derived, per this workspace's "never a second,
/// independently-reasoned way" posture.
pub(crate) fn representative_instance_of<'d>(
    netlist: &Netlist<'d>,
    slang_analysis: &sv_lang::Analysis<'d>,
    tmpl: TemplateId,
) -> Option<InstanceId> {
    let template = netlist.template(tmpl);
    let template_has_analyzable_members =
        !template.processes.is_empty() || !template.continuous_assigns.is_empty();

    let mut fallback = None;
    for instance_id in netlist.registration_order() {
        if netlist.instance(instance_id).template != tmpl {
            continue;
        }
        if fallback.is_none() {
            fallback = Some(instance_id);
        }
        if !template_has_analyzable_members {
            return Some(instance_id);
        }
        let Some(body) = netlist.instance_symbol(instance_id).instance_body() else {
            continue;
        };
        if slang_analysis.procedures(body).count() > 0 {
            return Some(instance_id);
        }
    }
    fallback
}

/// Task 5's driver-set backfill (NL-063's classification clause): populates
/// `SignalDecl.driver_set` for every net across every `Template`, against
/// ONE representative instance per `Template` (Decision 4 guarantees every
/// deduped instance has an identical `DriverEntry` shape for the same
/// member, so classifying via any one of them is correct). Mutates
/// `netlist` in place — the one mutation this whole pipeline performs on an
/// already-elaborated `Netlist`.
///
/// Implemented as two passes (an immutable read pass collecting every
/// update, then a mutation pass applying them) rather than one interleaved
/// pass: `Netlist::instance`/`instance_symbol`/`member_symbol` are
/// `NetlistView`/inherent methods taking `&self` (the whole struct), so
/// they cannot be called while `netlist.templates[i]` is borrowed
/// mutably — a plain, standard borrow-checker-driven split, not a
/// correctness-relevant design decision.
pub(crate) fn populate_driver_kinds<'d>(
    netlist: &mut Netlist<'d>,
    slang_analysis: &sv_lang::Analysis<'d>,
) {
    let mut updates: Vec<(usize, usize, Vec<DriverEntry>)> = Vec::new();

    for template_index in 0..netlist.templates.len() {
        let tmpl_id = TemplateId(template_index as u32);
        // Reuses `build_driver_graph`'s own canonical-instance resolution
        // (never a second, independently-reasoned "pick a representative"
        // rule) — required for correctness here too: `Analysis::drivers`
        // only has real data against the SAME canonical instance `Analysis`
        // itself chose (see `build_driver_graph`'s doc comment).
        let Some(rep_instance) = representative_instance_of(netlist, slang_analysis, tmpl_id)
        else {
            // A `Template` with zero instances cannot happen post-elaborate
            // (every `Template` is created because at least one instance's
            // body deduped to it) — defensive only.
            continue;
        };

        let Some(body) = netlist.instance_symbol(rep_instance).instance_body() else {
            continue;
        };
        let members: Vec<sv_lang::Symbol<'_>> = crate::netlist::module_items(&body);

        for (signal_index, signal) in netlist.templates[template_index].signals.iter().enumerate() {
            let net_symbol = netlist.member_symbol(rep_instance, signal.key);
            let entries: Vec<DriverEntry> =
                resolve_net_drivers(slang_analysis, net_symbol, &members)
                    .into_iter()
                    .map(|(containing, driver_kind)| DriverEntry {
                        driver_kind,
                        containing,
                    })
                    .collect();
            if !entries.is_empty() {
                updates.push((template_index, signal_index, entries));
            }
        }
    }

    for (template_index, signal_index, entries) in updates {
        netlist.templates[template_index].signals[signal_index].driver_set = entries;
    }
}

/// The WOCB partitioning pass (Decision-record union-find): every write
/// edge always unions process with net (LRM multi-driver atomicity falls
/// out for free — two processes that both write one net both union with
/// it, hence transitively with each other, with no special-casing). A read
/// edge unions net with reader UNLESS both sides already carry a resolved,
/// DIFFERING clock domain — a genuine cross-domain register-to-register
/// read, which [`crate::analysis::clock::classify_cdc_edges`] turns into a
/// `CdcEdge` instead (never a merge, per NL-082). Two same-domain clocked
/// nodes (NL-076's fixture) also do NOT union on a read alone — finer
/// partition granularity, still correct (each register independently reads
/// old values within one clock domain) and not required to merge by
/// anything this pass's tests assert. Iterated to a fixed point (a merge
/// can turn a group's domain from `None` to `Some`, unblocking a
/// previously-skipped union later in the same or a later pass), bounded by
/// `max_passes`.
pub fn partition(graph: &DriverGraph, max_passes: u32) -> Vec<Partition> {
    // Deterministic node discovery: first-seen order across `all_nodes`
    // (every net/process `build_driver_graph` knows about, declaration- then
    // registration-ordered — NL-117: this is what guarantees a
    // never-driven/never-read net, e.g. a bare `interconnect` declaration,
    // still gets its own singleton `Partition` below instead of silently
    // never becoming a node at all), THEN write_edges, THEN read_edges (both
    // already declaration-ordered by `build_driver_graph`) — never a
    // `HashMap`/`HashSet`-iteration-order accident. The edge scan after
    // `all_nodes` is defensive-only in the common case (every edge endpoint
    // is already one of `all_nodes`) but kept so this function still behaves
    // correctly even against a `DriverGraph` built some other way.
    let mut nodes: Vec<InstantiatedSignalId> = Vec::new();
    let mut seen: HashSet<InstantiatedSignalId> = HashSet::new();
    for &n in &graph.all_nodes {
        if seen.insert(n) {
            nodes.push(n);
        }
    }
    for &(a, b) in graph.write_edges.iter().chain(graph.read_edges.iter()) {
        for n in [a, b] {
            if seen.insert(n) {
                nodes.push(n);
            }
        }
    }
    let index_of: HashMap<InstantiatedSignalId, usize> =
        nodes.iter().enumerate().map(|(i, &n)| (n, i)).collect();

    let mut parent: Vec<usize> = (0..nodes.len()).collect();
    let mut domain: Vec<Option<ClockDomainId>> = nodes
        .iter()
        .map(|n| graph.process_domain.get(n).copied())
        .collect();

    fn find(parent: &mut [usize], x: usize) -> usize {
        if parent[x] != x {
            parent[x] = find(parent, parent[x]);
        }
        parent[x]
    }
    fn union(parent: &mut [usize], domain: &mut [Option<ClockDomainId>], a: usize, b: usize) {
        let ra = find(parent, a);
        let rb = find(parent, b);
        if ra == rb {
            return;
        }
        parent[rb] = ra;
        if domain[ra].is_none() {
            domain[ra] = domain[rb];
        }
    }

    // Phase 1: write edges always union.
    for &(proc_sig, net_sig) in &graph.write_edges {
        let (Some(&pi), Some(&ni)) = (index_of.get(&proc_sig), index_of.get(&net_sig)) else {
            continue;
        };
        union(&mut parent, &mut domain, pi, ni);
    }

    // Phase 2: read edges union to a fixed point, unless both sides already
    // have a resolved (possibly-differing) clock domain.
    for _pass in 0..max_passes.max(1) {
        let mut changed = false;
        for &(net_sig, proc_sig) in &graph.read_edges {
            let (Some(&ni), Some(&pi)) = (index_of.get(&net_sig), index_of.get(&proc_sig)) else {
                continue;
            };
            let rn = find(&mut parent, ni);
            let rp = find(&mut parent, pi);
            if rn == rp {
                continue;
            }
            if domain[rn].is_none() || domain[rp].is_none() {
                union(&mut parent, &mut domain, rn, rp);
                changed = true;
            }
        }
        if !changed {
            break;
        }
    }

    // Assign RegionIds to the final distinct roots, in first-seen node
    // order, and classify each node into its partition's `.nets`/
    // `.processes`.
    let mut region_of_root: HashMap<usize, RegionId> = HashMap::new();
    let mut partitions: Vec<Partition> = Vec::new();
    for (i, &sig) in nodes.iter().enumerate() {
        let root = find(&mut parent, i);
        let region_id = *region_of_root.entry(root).or_insert_with(|| {
            let id = RegionId(partitions.len() as u32);
            partitions.push(Partition {
                id,
                processes: Vec::new(),
                nets: Vec::new(),
                clock_domain: domain[root],
            });
            id
        });
        let kind = graph.node_kinds.get(&sig).copied().unwrap_or(NodeKind::Net);
        let p = &mut partitions[region_id.0 as usize];
        match kind {
            NodeKind::Net => p.nets.push(sig),
            NodeKind::Process => p.processes.push(sig),
        }
    }

    partitions
}