Infinite loop after squashing migrations

[Stephane "Twidi" Angel]

Take a "complex" dependency graph:

app_a:        0001 <-
                     \
app_b:        0001 <- x 0002 <-
               /               \
app_c:   0001<-  <------------- x 0002

And squash migrations on on app_c.

Now we should have a CircularDependencyError.

But we have an infinite loop.

Note that if "app_a" was named "app_d", the CircularDependencyError would have been raised.

It's because of the "sorted" on the dfs function, in django.db.migrations.graph.

Note that without this "sorted", the infinite loop could happen randomely because we have a set. The problem is not here.

Condition to reproduce this bug: having a circular loop, and an node in this loop having a dependency that has no dependency, which will reset the "path" list.

Indeed, if you remove the dependency of app_b.0002 on app_a, the CircularDependencyError is raised.

You can see the test case here: ​https://github.com/twidi/django/compare/squashing-infinite-loop

[Danilo Bargen]

I can confirm this.

[Stephane "Twidi" Angel]

I just updated my branch with a process that is killed if the loop in the test is taking more than 1 second

[Andrew Godwin <andrew@…>]

In c5def493d0993d65bf7d96f0a204006cbeaa6178:

Fixed #23835: Changed circular dependency in DFS to be less infinite

[Andrew Godwin]

This was broken when we moved from a recursive to stack-based DFS; the path variable wasn't correctly managed. I've fixed it so (I think) it's now correctly wound back as the stack is unwound rather than being cleared if there's no children.