What algorithm does Django use to resolve circular imports when creating models?

Question

When defining models with foreign keys, Django asks the user to specify them as strings in order to avoid issues with circular dependencies.

What's the algorithm it uses to create the related models after parsing the strings? I've looked through Django's source code but haven't been able to understand it.

I thought it'd create a graph out of the models, topologically sort it and start by instantiating the models that don't depend on the rest. This, however, seems too simplistic since the graph may not be a DAG, as in the following example:

class ModelA:
    b = ForeignKey(ModelB)

class ModelB:
    c = ForeignKey(ModelC)

class ModelC:
    a = ForeignKey(ModelA)

Thank you!

Answer 1

When you pass a string, Django first tries to look up the model. If it exists and it is registered, it is replaced immediately.

It the model isn't registered yet, a lazy operation is added to the app registry. For example, this method is used to solve the to part of a relation. The to attribute is replaced in-place with the actual model, and the reverse relation is added to the to model.

Whenever a new model class is defined, the metaclass registers the model in the app registry. The app registry the goes through the list of pending operations for that model, and fires each of them.

So, for each valid string reference, when the field is instantiated, the target either exists and the string is immediately replaced with the model class, or the target doesn't exist yet, but a lazy operation is used to replace the string with the model class when that model class is created and registered.

If you have a circular reference of, say, 2 models, the first model class will add a lazy operation. The second model class can immediately resolve its reference to the first model class, and then activates the lazy operation to resolve the reference from the first model class to the second model class.