uniffi_bindgen: make recursive type detection deterministic and follow custom types by devtechedge · Pull Request #3014 · mozilla/uniffi-rs

devtechedge · 2026-09-28T10:52:09Z

The recursive flag on enums and records, and ComponentInterface::is_recursive which Swift uses to emit indirect, had two problems described in #3005.

Non-deterministic result

find_recursive_enum_names ran a DFS that skipped any node already finished by an earlier traversal, assuming every cycle through it had been found. That does not hold: with T -> {U, V}, U -> T, V -> U, visiting U first from T marks T and U and finishes U, then T -> V -> U stops at U and V is never marked. The graph is a HashMap, so the outcome changed from run to run.

This replaces the DFS with Tarjan's strongly connected components algorithm, written in place with no new dependency. Every node in a component with more than one member is marked, plus any node with a self-edge. Component membership does not depend on visit order. The function keeps its generic signature, so the ComponentInterface path gets the fix too.

Cycles through custom types

Both copies of type_names_in_type (the pipeline one and the one in interface/mod.rs) fell through to _ => vec![] for Type::Custom, so Node -> Wrapped (custom over Inner) -> Inner -> Node had no edge out of Wrapped. Both now follow the builtin type.

Tests

find_recursive_overlapping_cycles_is_order_independent builds the graph above 64 times (each HashMap gets a new seed) and checks that all three nodes are marked. It failed on every one of 10 runs against the old code and passes with this change.
dep_graph_custom_type_propagates_dep (pipeline) checks that a custom type over a record creates the edge.
infer_recursive_through_custom_type runs infer_recursive_types on the Node / Wrapped / Inner example from the issue and checks that Node and Inner are marked.
interface::test::dep_graph_custom_type_propagates_dep covers the ComponentInterface copy through UDL ([Custom] typedef Inner Wrapped;), including is_recursive.

The Python NameError mentioned in the issue (the Wrapped = Inner alias emitted before class Inner) comes from the sort order in pipeline/general/sort.rs and is intentionally left out of this PR.

Fixes #3005

`find_recursive_enum_names` skipped any node that an earlier DFS had already finished, so a node that is on a cycle only through a finished node was never marked. The graph is a `HashMap`, so whether that happened depended on iteration order. Replace the DFS with Tarjan's strongly connected components algorithm and mark every node in a component with more than one member, plus any node with a self-edge. `type_names_in_type` also ignored `Type::Custom`, so a cycle through a custom type was never found. Follow the builtin type in both the pipeline copy and the `ComponentInterface` copy. Fixes #3005

bendk

The custom type fix looks good. The change to Tarjan's strongly connected components algorithm feels overengineered to me. Would switching from HashMap to IndexMap work instead?

bendk · 2026-10-03T14:58:23Z

+    lowlink: HashMap<&'a T, usize>,
+    stack: Vec<&'a T>,
+    on_stack: HashSet<&'a T>,
+    recursive: HashSet<T>,


This feels like extreme overkill to me. Based on the bug description, the only reason that the search is non-deterministic is because we're iterating over a hash map. We could fix that by switching to an IndexMap and keeping everything else the same.

A type is recursive if it can reach itself. Check that with a small DFS per type and no shared visited set, so the result is order independent.

devtechedge · 2026-10-03T20:24:41Z

Fair point, Tarjan was more machinery than this needs.

One catch with IndexMap alone: it makes the result stable, but the visited skip can still miss a cycle member.

With T -> {U, V}, U -> T and V -> U, if T explores U first, U is marked visited, so V -> U returns early and V is never flagged.

So the field order would still decide whether V is marked, just consistently.

I've pushed a simpler version instead: a type is recursive if it can reach itself, checked with a small DFS per type and no shared visited set.

It is order independent, so no map change is needed, and the custom type fix and tests are unchanged.

bendk · 2026-10-04T18:52:42Z

With T -> {U, V}, U -> T and V -> U, if T explores U first, U is marked visited, so V -> U returns early and V is never flagged.

Which seems fine to me, since the V::U field will be marked as indirect and should break any cycles. In general if there's a cycle A -> B -> C -> A -> ... we only need to flag one of those types as cyclic to break cycles.

bendk · 2026-10-04T18:53:50Z

-/// A node is in a cycle if any path of edges leads back to itself.
+/// A node is recursive if some path of edges leads back to it. This is checked
+/// separately for each node, so the result does not depend on the iteration
+/// order of `deps`.


I think this comment change should be reverted now.

bendk · 2026-10-04T18:57:46Z

+            }
+            if seen.insert(node) {
+                stack.extend(deps.get(node).into_iter().flatten());
+            }


I like changing the DFS into a while loop with a stack, it seems simpler overall. However, I'm not sure I like how this is starting a new search for each type. IIUC, this changes it so if we have a cycle A -> B -> C -> A, then the new code will flag A, B, and C while the old code would only flag one of them. I think I prefer the old behavior for the since we only need to flag one to ensure the cycle is broken. I could easily be missing something here though.

bendk · 2026-10-04T18:59:27Z

+            orig_name: name.to_string(),
+            builtin: Box::new(builtin),
+        }
+    }


I'd rather see the type written out than have this helper function. It's not many lines and I think it's easier to understand tests when the level of indirection is low.

bendk · 2026-10-04T19:02:09Z

+- Detection of recursive enums and records is now deterministic. Previously a type in two
+  overlapping cycles was sometimes not marked `recursive`, depending on hash map iteration order,
+  and cycles that pass through a custom type were not detected at all, so the Swift bindings were
+  missing `indirect` and failed to compile (via [#3005](https://github.com/mozilla/uniffi-rs/issues/3005)).


The way I'm understanding this is there were 2 issues:

Custom types weren't detected, which caused compile errors

Cycle detection was non-deterministic, which caused different fields to be marked indirect for different builds. However, it still compiled.

Is this correct? If so, please update the changelog.

Go back to the single DFS from main, with its shared visited set, and make it deterministic by building the dependency graph as an `IndexMap<T, IndexSet<T>>` instead of a `HashMap<T, HashSet<T>>`. Both the pipeline and `ComponentInterface` build the graph from ordered `Vec`s, so the same types are marked recursive on every build. Every cycle still gets at least one member marked, which is enough to break it. Also revert the doc comment on `find_recursive_enum_names`, write the custom type out in the tests instead of using a helper, and split the changelog entry into the two separate fixes.

devtechedge · 2026-10-05T05:52:22Z

I've pushed 67b668a, which keeps the original DFS and switches both dependency graphs to IndexMap/IndexSet, so the same types are marked on every build.

The custom_type helper is gone, the doc comment is back to the original wording, and the changelog entry is now split in two.

Yes, your reading of the two issues is correct.

For what it's worth, the old code already flagged every member of a simple cycle like A -> B -> C -> A, since a back edge marks the whole stack slice, so the per-type search only changed the result for overlapping cycles.

The overlap test now checks that the same graph always gives T and U, which is enough to break both cycles.

I appreciate the careful review on this one.

bendk

This new version looks great, thanks for working through this with me.

devtechedge · 2026-10-05T15:14:11Z

Thanks bendk.

Your review notes were spot on, especially keeping the original DFS and treating one flagged member per overlapping cycle as enough.

Using IndexMap for the dep graph so visit order stays stable taught me a lot about what "deterministic" actually has to mean here.

Really appreciate the careful pass!

devtechedge requested a review from a team as a code owner September 28, 2026 10:52

devtechedge requested review from bendk and removed request for a team September 28, 2026 10:52

bendk requested changes Oct 3, 2026

View reviewed changes

uniffi_bindgen: replace Tarjan with a per-type reachability check

91ed20c

A type is recursive if it can reach itself. Check that with a small DFS per type and no shared visited set, so the result is order independent.

bendk requested changes Oct 4, 2026

View reviewed changes

bendk approved these changes Oct 5, 2026

View reviewed changes

bendk merged commit bc9fb38 into mozilla:main Oct 5, 2026
5 checks passed

Navigation Menu

Repository navigation

uniffi_bindgen: make recursive type detection deterministic and follow custom types - #3014

uniffi_bindgen: make recursive type detection deterministic and follow custom types#3014
bendk merged 3 commits into
mozilla:mainfrom
devtechedge:fix-recursive-type-inference

devtechedge commented Sep 28, 2026

Uh oh!

bendk left a comment

Uh oh!

bendk Oct 3, 2026

Uh oh!

devtechedge commented Oct 3, 2026

Uh oh!

bendk commented Oct 4, 2026

Uh oh!

bendk Oct 4, 2026

Uh oh!

bendk Oct 4, 2026

Uh oh!

bendk Oct 4, 2026

Uh oh!

bendk Oct 4, 2026

Uh oh!

devtechedge commented Oct 5, 2026

Uh oh!

bendk left a comment

Uh oh!

Uh oh!

devtechedge commented Oct 5, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

devtechedge commented Sep 28, 2026

Uh oh!

bendk left a comment

Choose a reason for hiding this comment

Uh oh!

bendk Oct 3, 2026

Choose a reason for hiding this comment

Uh oh!

devtechedge commented Oct 3, 2026

Uh oh!

bendk commented Oct 4, 2026

Uh oh!

bendk Oct 4, 2026

Choose a reason for hiding this comment

Uh oh!

bendk Oct 4, 2026

Choose a reason for hiding this comment

Uh oh!

bendk Oct 4, 2026

Choose a reason for hiding this comment

Uh oh!

bendk Oct 4, 2026

Choose a reason for hiding this comment

Uh oh!

devtechedge commented Oct 5, 2026

Uh oh!

bendk left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

devtechedge commented Oct 5, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants