skip to content

How does reflect.DeepEqual terminate on a cyclic structure instead of recursing forever?

level: middleimportance: nice to knowfreq 24%

answer

  1. a walk that must not loop forever
  2. remember where you have already been
  3. keyed on a pair, not a single value
  4. addresses, not values
  5. revisiting a pair means assume equal

basics

~20 s

reflect.DeepEqual records each pair of addresses it is already comparing and returns true when it meets the same pair again, so a cycle terminates instead of recursing forever. Identical pointers, map objects and slice backing arrays short-circuit the same way.

solid answer

~40 s

The traversal keeps a visited set of address pairs for the kinds that can form cycles — pointers, maps, slices and interfaces. Before descending into such a pair it checks whether that exact pair is already on the path; if so it returns true and stops. So two self-referential nodes with matching labels compare equal, and the walk finishes. Layered under that are cheaper identity shortcuts taken before any element comparison: two pointers equal under `==` are deeply equal without dereferencing, two slices with the same backing-array start and length are equal without touching elements, and the same map object is equal to itself. That is why `reflect.DeepEqual(s, s)` is true for a slice holding NaN — the shortcut fires first — while the same NaN inside a plain struct makes the comparison false.

code

go · 11 lines
go
type node struct {
	Label string
	Next  *node
}

a := &node{Label: "a"}
a.Next = a
b := &node{Label: "a"}
b.Next = b

fmt.Println(reflect.DeepEqual(a, b)) // true

go deeper

for a junior

Know that comparing cyclic data does not hang or crash, and that the reason is a record of what has already been visited rather than a recursion limit.

for a middle

Explain the visited set of address pairs, which kinds get recorded, and the identity fast paths for pointers, slices and maps. Be ready to say why the same NaN can give two different verdicts.

for a senior

Bring the consequence: a true verdict on cyclic data is optimistic, so when cycles are load-bearing, compare a canonical serialisation or write a walk whose treatment of repeated pairs you control.

for a principal

Frame it as a guarantee question. Decide what your comparison is allowed to assume before it becomes the gate on a release, and make that assumption explicit rather than inherited from a helper's fine print.

## The problem a naive implementation has Deep equality is a recursive tree walk, but Go values are not trees. A pointer can point back at its own container, two nodes can point at each other, a slice can hold a pointer to the struct holding the slice. A naive recursive comparison of such a structure never returns: it follows the cycle forever and blows the stack. `reflect.DeepEqual` handles this with a technique standard in graph traversal — remember where you have already been — but with a Go-specific twist about what "where" means. ## The visited set As it walks, `reflect.DeepEqual` maintains a set of visits. Each entry identifies a *pair*: the address reached on the left, the address reached on the right, and the type being compared at that point. Entries are recorded only for the kinds that can create cycles — pointer, map, slice and interface — since those are the only ones that carry an indirection. Before descending into such a pair, the comparison asks whether that exact triple has been seen. If it has, the answer is **true** and it stops descending. If not, it records the pair and continues. Two consequences follow. First, **termination is guaranteed for cycles**: a cycle by definition returns to the same pair of addresses, and the second arrival short-circuits. Second, **the shortcut is optimistic**. It assumes equal, rather than proving it. Two cyclic structures that revisit the same pair are reported equal on the strength of having been visited before, so `reflect.DeepEqual` can return true for structures that a fully expanded comparison would never finish deciding about. That is a deliberate trade: an answer that terminates in place of a proof that does not. ## The identity shortcuts underneath Independently of the cycle machinery, several kinds have an identity fast path that fires before any recursion at all: - **Pointers**: deeply equal if `==` says so — same address, done, no dereference. Otherwise the pointed-to values are compared. - **Slices**: after the nil check and the length check, if both headers point at the same backing-array start the answer is true immediately, with no element comparison. - **Maps**: after the nil check and the length check, the same map object is equal to itself without walking keys. - **Interfaces**: both nil, or the concrete values inside them are compared. These are performance shortcuts, but they are also observable semantics, and they explain a result that otherwise looks impossible. Take `s := []float64{math.NaN()}`. `reflect.DeepEqual(s, s)` is **true**: same nilness, same length, same backing array — the answer arrives before any element is examined. `reflect.DeepEqual(s, []float64{math.NaN()})` is **false**: two separate backing arrays force element comparison, and NaN fails `==`. Put the same NaN in a plain struct compared with a copy of itself and the result is false again, because a struct has no identity to short-circuit on; every field goes to the leaf rules. So the same data gives different verdicts depending on how it is packaged. If you take one thing from this: `reflect.DeepEqual` compares *values as reached*, and identity is part of what it can reach. ## Cycles in practice Cyclic values are less exotic than they sound. A doubly linked list, a parent pointer in a tree, a graph node's adjacency, a struct that caches a pointer back to its owner, or a recorded structure where an element points at the container it came from — all produce cycles. Recorded golden structures are a common home for them, because they tend to be built by walking a live object graph and writing down what was found. The practical advice is unchanged by the shortcut: `reflect.DeepEqual` on cyclic data will terminate and will not lie about *inequality* — if it returns false, something genuinely differed on a path it fully explored. It is the *true* results on cyclic structures that carry an assumption. When cycles matter to correctness, compare a canonical serialisation of the structure instead, or write a comparison that walks with your own visited set and your own definition of what a repeated pair means. ## What this is not Two misconceptions worth naming. The visited set is keyed on **addresses**, not on values, so structurally identical but separately allocated nodes are compared properly rather than being collapsed. And there is no depth limit or iteration budget — the mechanism is exact revisit detection, not a bail-out after N levels, which is why a very deep but acyclic structure is walked in full and can still be slow. The summary an interviewer wants: a visited set of address pairs makes it terminate, identity shortcuts make it fast, and both of those mean a `true` answer sometimes rests on identity rather than on element-by-element proof.

  • What does that short-circuit cost you in correctness?
    A true answer on cyclic data can rest on identity rather than proof: once the same address pair reappears, the rest of the cycle is assumed equal instead of being expanded. False answers are still trustworthy, because they come from a path that was fully compared.
  • Why is DeepEqual(s, s) true for a slice holding NaN but false for a struct holding NaN?
    The slice case short-circuits on identical nilness, length and backing-array start, so no element is ever compared. A struct has no identity to compare, so every field reaches the leaf rules, and NaN fails the `==` used for numbers.
  • Is the visited set keyed on values or on addresses?
    On addresses, together with the type — the pair of locations reached on each side. That is why two structurally identical but separately allocated nodes are still compared properly instead of being collapsed into one visit.
  • Does DeepEqual give up after a fixed depth?
    No. There is no depth limit or iteration budget; termination comes only from exact revisit detection. A very deep acyclic structure is walked in full, which is one reason deep comparison of large graphs is slow.

saying these in an interview costs you the question

  • Says DeepEqual overflows the stack on cyclic data
  • Thinks it bails out after a fixed recursion depth
  • Believes the visited set is keyed on values, not addresses
  • Assumes two pointers are always dereferenced and compared
  • Claims a shared backing array is still compared element by element