Topological sort

Topological sort arranges attributes so every dependency is initialized before an attribute that refers to it. It solves generated initialization code that follows declaration order even when that order is unsafe: if attribute1 starts as attribute2, attribute2 must receive its value first. section 9.3.4 section 9.4

class Rental { 
    // ...initializing assignments for other attributes... 
    attribute1 = this.attribute2
    attribute2 = 42
    constructor() { 
        makeAutoObservable(this) 
    } 
}

This out-of-order output reads attribute2 before attribute2 is initialized. Reordering assignments, rather than restricting how domain experts define attributes, preserves their control over attribute order. section 9.3.4

Model each attribute reference as a directed dependency relation. The notation a1 → a2 means that a1 depends on a2 because a1’s initial value refers to a2. Dependency chains follow these arrows: a1 → a2 → … → an. The arrow therefore points from the dependent attribute to the attribute it needs. section 9.3.4

Figure 9.12 The attributes of the Rental record type, in shorthand notation

The shorthand graph strips away record details and makes the reference relations that determine initialization order visible. section 9.3.4

First, extract an attribute’s referenced dependencies from its initial value. An initial value counts only when it is an Attribute Reference with a resolved reference; otherwise it contributes no dependency. This query gives the sorter a uniform way to traverse reference edges. section 9.3.4

const { isAstObject, isAstReference } =   #1
     require("../common/ast")

const referencedAttributesInValueOf = (attribute) => {
    const initialValue = attribute.settings["initial value"]
    if (isAstObject(initialValue)                              #2
             && initialValue.concept === "Attribute Reference") {
        const refObject =
             initialValue.settings["attribute"]      #3
        return isAstReference(refObject)    #4
            ? [ refObject.ref ]
            : []
    }
    return []    #5
}
module.exports.referencedAttributesInValueOf = referencedAttributesInValueOf

The query inspects an initial value, recognizes an Attribute Reference, and returns its target attribute as a one-element dependency list when resolved. section 9.3.4

A dependency-order traversal works as follows:

• Start a visit for each attribute so disconnected attributes are included. section 9.3.4
• Skip an attribute already placed in the ordered result. section 9.3.4
• Extend the current dependency chain and recursively visit every referenced attribute before the current one. section 9.3.4
• Append the current attribute only after its dependencies have been visited. section 9.3.4

const { referencedAttributesInValueOf } = require("../language/queries")

const dependencyOrderOf = (attributes) => {
    const ordered = []           #1

    const visit = (current, chain) => {     #2
        if (ordered.indexOf(current) > -1) {    #3
            return
        }
        const extendedChain = [ ...chain, current ]      #4
        referencedAttributesInValueOf(current).forEach(
            (dependency) =>
                 visit(dependency, extendedChain)   #5
        )
        ordered.push(current)          #6
    }

    attributes.forEach(
        (attribute) => visit(attribute, [])    #7
    )

    return ordered
}
module.exports.dependencyOrderOf = dependencyOrderOf

The implementation keeps an ordered list, recursively visits dependencies, and pushes each attribute after those visits, producing dependency-first output. section 9.3.4

Dependency chains can also contain cycles. Detecting such cycles identifies attribute-reference chains that cannot supply a valid dependency order, while acyclic relations can be arranged for working generated code. section 9.4