Skip to content

bug(quake): validate_topology rejects connected manifests where bridges form a cycle (e.g. triangle A-B-C) #492

Open

Description

@kriss39

What

Subnets::validate_topology() (crates/quake/src/manifest/subnets.rs:148) rejects a connected
topology when subnets are bridged in a cycle. Three bridge nodes forming a triangle:

[nodes.bridge_bc]
subnets = ["B", "C"]

[nodes.bridge_ac]
subnets = ["A", "C"]

[nodes.bridge_ab]
subnets = ["A", "B"]

Every subnet is reachable from every other one, but Manifest::validate() (manifest.rs:1059) fails
with Destination subnet B not found; cannot merge subnets, so the manifest cannot be used at all.

Why

Walking the merge loop for the manifest above:

  1. bridge_bc: C is merged into B; removed_subnets = {C → B}, working_map = {B, A}.
  2. bridge_ac: C is already gone, so the else branch resolves C → B and A → A, moves A
    into B; removed_subnets = {C → B, A → B}, working_map = {B}.
  3. bridge_ab: working_map.swap_remove("B") succeeds, because B is the surviving destination
    of the merged component, not a removed subnet. The code then computes
    destination = find_destination("A") = B, inserts B → B, and
    working_map.get_mut("B") is None (it was just removed), so it bails at line 211.

The swap_remove(subnet) fast path assumes that a subnet still present in working_map is in a
different component from first_subnet. That holds for chains and stars (the existing tests), but not
once a later bridge connects two subnets that are already in the same component through earlier
merges.

Repro

Adding this next to the existing tests in subnets.rs fails on main @ 6e76402:

#[test]
fn triangle_topology_is_connected() {
    let node_subnets: IndexMap<NodeName, Vec<SubnetName>> = [
        ("bridge_bc".to_string(), vec!["B".to_string(), "C".to_string()]),
        ("bridge_ac".to_string(), vec!["A".to_string(), "C".to_string()]),
        ("bridge_ab".to_string(), vec!["A".to_string(), "B".to_string()]),
    ]
    .into();

    assert!(Subnets::new(&node_subnets).validate_topology().is_ok());
}

cargo test -p quake --bins triangle_topology_is_connected → assertion failed: ...validate_topology().is_ok().

Suggested fix

Resolve both ends to their current representative before merging, and skip when they are equal,
i.e. a small union-find over subnet names instead of the swap_remove fast path plus the separate
"already merged" branch. Count the remaining roots at the end; more than one means the topology is
disconnected, same error as today. This also makes the result independent of node order. The
existing chain/star/disconnected tests stay as they are, plus the triangle test above.

Environment: main @ 6e76402.


(Opening as an issue first per CONTRIBUTING.md; happy to be assigned and submit the fix + test.)

Activity

  1. nenadmilosevic95 commented on Oct 24, 2026

    @nenadmilosevic95

    Thanks for the report! We reproduced it and are looking into a fix.

  2. added
    tracked internallyThis issue is already tracked internally by the Arc team.
    and removed on Oct 26, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    tracked internallyThis issue is already tracked internally by the Arc team.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions