What must a decoder do when a reference names a node identifier whose body it has not yet read from the stream?
answer
- the promise arrives before the thing
- a cycle has no safe ordering
- leave a slot, come back later
- fixup list or two passes
- unresolved at end means truncated
basics
~20 sIt records an unresolved slot and fills it once the body arrives, either by backpatching a fixup list at the end or by decoding in two passes. Refusing forward references is impossible for a cyclic graph.
solid answer
~50 sForward references are unavoidable in general: a cycle admits no ordering in which every node precedes its dependents, so some reference will always arrive before its body. The decoder therefore needs a placeholder strategy. The usual one is a fixup list: on meeting an unknown identifier, record the target slot — which object, which field — and move on, then walk the list once the message ends and write the resolved objects into those slots. A two-pass decoder is the alternative: construct an empty shell per node body first, then fill every field, so all references resolve against shells that already exist. The friction is construction style. Nodes built field by field accept either approach; nodes that must be fully constructed in one step, with all their fields, cannot hold a placeholder, and the contract has to either order the graph so it never happens or accept a rebuild after the fact.
go deeper
Recall that a stream is read in order, so a link can point at something that has not been read yet. Something must hold that place until the target appears.
Explain the fixup list and the two-pass alternative, and say why a cycle forces one of them rather than allowing a clever write order instead.
Show the operational edges: the window in which a patched field is still empty, why an unresolved reference at end of stream must fail the message, and how identifier scope confines a map to one payload.
Judge whether a cyclic wire form is worth the decoder contract it imposes on every consumer, including ones whose construction style cannot hold a placeholder at all.
## Why the case exists at all When a graph is written with identifier indirection, each node's body appears once and every repeat encounter becomes a reference to that identifier. Reading such a stream, the decoder can meet a reference in either order relative to its body: - **Backward reference** — the body was read earlier, so the identifier is already in the decoder's map and the field can be filled immediately. - **Forward reference** — the identifier has not been defined yet, and the decoder holds a promise it cannot yet keep. The tempting cure is to make the writer emit every body before any reference to it. That works only for an acyclic graph, where a topological order exists. **A cycle has no such order**: A references B and B references A, so whichever body is written first is referenced before it is defined. Any decoder for a graph-shaped wire form has to tolerate forward references. ## The two standard strategies **Fixup list (backpatching).** On a reference to an unknown identifier, append a record naming the destination — the object and field, or the collection and position — to a pending list, and leave the slot empty. When the stream ends, iterate the list, look up each identifier in the now-complete map, and write the object into its slot. Cheap and single-pass, but the graph is genuinely incomplete until the fixup phase runs, so no decode-time logic may read those fields. **Two-pass construction.** Pass one reads every body and creates an empty shell per identifier, populating only the map. Pass two fills each shell's fields; by then every identifier resolves. This costs a second traversal and a buffered intermediate form, and it pays back by having no half-built window of the sort a fixup list leaves open. | Aspect | Fixup list | Two-pass | |---|---|---| | Passes over the input | one | one plus a fill pass over buffered nodes | | Window where a field is empty | until the fixup phase runs | until the fill pass reaches that node | | Memory held | pending slots only | an intermediate form for every node | | Needs mutable shells | yes, for the patched fields | yes, for the whole fill pass | ## Where it gets hard: construction style Both strategies assume a node can exist before all its fields are known. That is true where fields are assigned after construction; it is not true where a node must be handed every field at the moment it is created, which is exactly the style used for values that are meant to be immutable. A node whose field points into a cycle cannot be fully constructed first, because its target cannot be fully constructed first either. The ways out, in the order most contracts reach for them: 1. **Keep the wire form acyclic.** Declare one direction of the offending edge non-travelling and have the receiver re-attach it after decode. The whole problem disappears with it. 2. **Rebuild in two phases in the application.** Decode into a plain, mutable intermediate representation that tolerates placeholders, then construct the real nodes from it once every target exists — possible for a cycle only if at least one node on the cycle can be built mutably. 3. **Insert an indirection object.** Give the node a small mutable holder that the fixup phase populates, so the node itself is complete at construction and the holder is what is patched. Ecosystems differ in how much of this they hide: some decoding layers construct empty instances and fill them, and some refuse to and require every field at construction. The trade underneath is the same, and it is a reason a deliberately cyclic wire form is a heavier contract than it looks. ## Failure modes worth naming - **Reading a patched field too early.** Logic that runs during decode — a validation hook, a computed cache — can observe an empty slot and make a wrong decision that survives the fixup. - **Unresolved references at end of stream.** A reference whose identifier never appears means a truncated or wrongly cut payload. The decoder should fail loudly at that point; silently leaving the field empty converts a transport bug into a data bug discovered much later. - **Identifier collisions.** Identifiers are scoped to one payload. Merging two payloads into one decoder map silently joins unrelated nodes. ## What an interviewer is listening for That you recognise the case as forced by cycles rather than as a writer's sloppiness, that you can name a placeholder strategy and its window of incompleteness, and that you notice the tension with values that must be fully built at construction. That last point is what separates someone who has implemented a graph decoder from someone who has only used one.
- Why is emitting nodes in dependency order not a general fix?It relies on a topological order, which exists only for an acyclic graph. On a cycle every candidate first node is referenced by something written before it, so some reference is always forward. Ordering helps in the acyclic case — it can remove fixups altogether — but the decoder still needs the forward-reference path for any graph that may contain a cycle.
- What should a decoder do with references still unresolved when the stream ends?Fail the whole message. An identifier that never received a body means the payload was truncated, cut at the wrong boundary, or written by a producer that emitted a reference out of scope. Leaving the field empty turns a transport-level fault into a silent data fault that surfaces far from its cause, usually as a missing relationship nobody can explain.
saying these in an interview costs you the question
- Says a well-behaved writer never emits forward references
- Believes a cycle can be written in dependency order
- Leaves unresolved references empty at end of stream
- Runs validation hooks before the fixup phase completes
- Assumes every node type can be built before its fields are known
- Reuses one identifier map across separate payloads