Lesson 15 · Cycles

Four problems wearing one hat

Question 11 was blank: two non-nullable foreign keys pointing at each other, write the two lines of fake(). The reason it is worth a whole lesson is that “cycles” names four different problems in this backend, they have four different fixes, and only one of the four is fixed by the thing everyone reaches for first.

Terms

Problem 1 · Definition order — and why you should not sort

The obvious first worry: User mentions Company, so Company must be defined first, so the backend needs a topological sort of the models before emitting them.

Don't write it. Two reasons, and the second is the one that matters.

The weak reason is that it cannot work in general: a topological order exists only for an acyclic graph, and mutual references are legitimate domain designs, so the sort has no answer for exactly the inputs you built it to handle.

The strong reason is that the problem does not exist. Django's first positional argument to ForeignKey may be a lazy reference — the string "core.Company" — resolved against the app registry once every model in every installed app has been imported. Emit the string and definition order within the module is irrelevant, cycles included. There is nothing to sort.

# both of these are fine, in either order, in one file
class User(models.Model):
    company = models.ForeignKey("core.Company", on_delete=models.PROTECT,
                                related_name="user_company")

class Company(models.Model):
    owner = models.ForeignKey("core.User", on_delete=models.PROTECT,
                              related_name="company_owner")

So the rule is always emit the lazy form, even for a target that is defined earlier in the same file and would have worked as a bare name. This is the third time in three lessons the same shape has come up, and it is worth naming as a policy rather than rediscovering it: a generator should prefer the uniform construction that cannot fail over the conditional one that is prettier when it works. Explicit related_name in lesson 14, canonical annotations in lesson 12, lazy references here. Each time, the conditional version requires a global analysis to decide, and the analysis is the bug.

Problem 2 · Circular imports

The previous section assumed one module. If you emit one module per model — and for a large domain you will want to — then a mutual reference becomes a genuine Python-level cycle:

# core/models/user.py
from core.models.company import Company     # company.py imports user.py
class User(models.Model): ...

# core/models/company.py
from core.models.user import User           # ImportError: partially initialised module

The lazy reference fixes this too, and more completely than it fixed problem 1: a string needs no import at all, so the edge stops being an import edge. That is the whole reason "core.Company" exists in Django rather than being a convenience.

Where it bites is everything that is not the foreign key argument. The moment lesson 13's user methods land, a body or a signature can mention the other model:

from __future__ import annotations
from typing import TYPE_CHECKING

if TYPE_CHECKING:
    from core.models.company import Company

class User(models.Model):
    company = models.ForeignKey("core.Company", on_delete=models.PROTECT,
                                related_name="user_company")

    def parent_company(self) -> Company:      # a string at runtime, thanks to the future import
        return self.company.parent

Two facts make that work, and both are import-collection decisions rather than rendering ones — which means they belong to whatever built bindings.py, not to the renderer:

• from __future__ import annotations makes every annotation a string, so an annotation can name a type that is never imported at runtime. Emit it in every generated module unconditionally — same uniformity argument as above.
• An import used only in annotations goes under if TYPE_CHECKING:. An import used in a method body cannot, and if that body creates a cycle you have a real problem that no annotation trick solves — the honest fix is a function-local import, and the honest diagnostic is to say so.

So the import collector now has to distinguish where a name is used, not just that it is used. That is a strictly finer question than lesson 8 asked, and it is the concrete diff this section implies.

Problem 3 · The cycle that is not a codegen problem

Question 11. User.company is a non-nullable foreign key to Company; Company.owner is a non-nullable foreign key to User. Both models emit cleanly, Django starts, the migration applies. Then:

company = Company.objects.create(owner=???)   # needs a User
user = User.objects.create(company=???)       # needs a Company

There is no order. The argument is one line and worth being able to give from memory: any first insert must satisfy its own non-null foreign key, and the row it points at does not exist yet. This is not a limitation of Django, of your generator, or of fake(). The domain model describes a database that cannot be populated.

Which settles ownership, in the sense of session 1's question 9: this is the user's problem, and your job is to tell them immediately rather than to work around it. The check is precise:

// a cycle in the required subgraph is unsatisfiable.
// a cycle with at least one optional edge is fine — that edge starts as null.
const unsatisfiable = sccs(relations.filter(r => !r.optional)).filter(c => c.length > 1 || selfEdge(c))

Two things about that snippet are the lesson. First, it runs on the required subgraph — a cycle in the full graph is not an error, and rejecting one would reject Employee.manager, which is a perfectly good self-relation that happens to be optional. Second, it returns components, because the diagnostic has to name the whole cycle: “User.company → Company.owner → User.company: every edge is required, so no row can be created first. Make one of them optional.” A message naming a single field would be blaming an arbitrary member of the cycle.

Problem 4 · fake() across a relation

Lesson 5 gave fake() a depth budget, which was the right answer to a recursive type — a tree that could nest forever. A relation graph is a different problem and the budget alone gets it wrong, because the question is no longer “how deep” but “in what order, and does an order exist”.

Three cases, and only the third is interesting:

# Employee.manager is optional and self-referential
def fake_employee(manager: Employee | None = None) -> Employee:
    return Employee(id=EmployeeId(...), manager=manager)

boss = fake_employee()
report = fake_employee(manager=boss)

And the split that has to be decided rather than derived: does fake() return unsaved instances or saved rows? An unsaved Django instance can hold an unsaved related object in memory, so ordering barely matters and cycles are almost free; a saved row must satisfy the constraint at INSERT, so ordering is everything. Lesson 5 assumed the pure-value case because pydantic models have no other case. Django gives you two, they have different correctness conditions, and fake() emitting one of them silently is the bug — the answer here is two generated constructors with names that say which.

Exercise A · Six inputs

Each is a domain model set, written as edges. Decide what the generator should do. ? marks an optional reference.

Exercise B · Generated output

Click the line that breaks, or say clean. Two are clean.

Exercise C · From memory

The diff

1. Every emitted relation uses the lazy string form, unconditionally. No topological sort of models — the sort you were going to write is dead code.
2. from __future__ import annotations in every generated module. The import collector learns to distinguish annotation-only uses (which go under TYPE_CHECKING) from body uses (which cannot).
3. A pass computing SCCs of the required subgraph. A non-trivial component is a diagnostic naming every edge in the cycle, accumulated with the rest (lesson 6).
4. fake() builds in reverse topological order of the required subgraph, returns None for optional references rather than recursing, and comes in two flavours — unsaved and saved — because they have different correctness conditions.
5. The property, in lesson 9's terms: for any domain package that passes the SCC check, calling every generated saved-fake() in dependency order raises no IntegrityError. That is a metamorphic relation with T = permute the model definition order and R = equality, since neither the check nor the build order may depend on file order.

What this unlocks

Everything in this lesson took optional as a given — the SCC check reads it, and fake() branches on it. But null=True is a Django attribute, and the only reason your backend knows a relation is optional is that the domain wrote CompanyId | None. That is a fact being lowered, and the next lesson is about the difference between lowering it and inventing it — because on_delete and db_index are invented, max_length looks invented and isn't, and getting that line wrong is how a constraint the user wrote silently disappears.

status · resources · mission