liveBook · Manning

Cycle detection

As explained in Building User-Friendly DSLs

Cycle detection is a graph-analysis technique that determines whether a path or dependency chain returns to a previously visited node.

Cycle detection checks whether attribute dependencies eventually return to an already visited attribute. Without it, dependency ordering can recurse forever, grow its chain, exhaust memory, and terminate Node.js with a fatal error. section 9.3.5

A depth-first visit carries the current dependency chain. Encountering an attribute already in that chain identifies a cycle; returning the repeated path exposes the attributes involved, including self-references. section 9.3.5

Rejecting a cyclic dependency

If attributes 1, 2, and 3 reference one another through their initial values, the diagnostic reports their quoted names as a path and points back to the first attribute. A self-reference forms a one-attribute cycle.

How Building User-Friendly DSLs covers it

How deep it goes
Implements recursive chain tracking and diagnostic reporting, while deferring cycle repair to a separate fault-handling strategy.
Examples
Uses mutually dependent attributes, a self-referencing attribute, cycle diagrams, and JavaScript diagnostic listings.
What it assumes
Assumes dependency ordering and topological sorting, then applies recursive graph traversal to attribute initial values.
What you can do after
Diagnoses cyclic attribute references and prevents dependency ordering from producing unsafe generated initialization code.
How it connects
Connects dependency ordering, topological sorting, attribute references, recursion, and DSL constraints.

Also explained in

Compare how 2 books explain cycle detection →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Building User-Friendly DSLs. The section links point to the parts of the book it draws on.