Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#23835 closed Bug (fixed)

Infinite loop after squashing migrations

Reported by: Stephane "Twidi" Angel Owned by: nobody
Component: Migrations Version: dev
Severity: Normal Keywords:
Cc: mail@… Triage Stage: Accepted
Has patch: no Needs documentation: no
Needs tests: no Patch needs improvement: no
Easy pickings: no UI/UX: no

Description

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

Change History (4)

comment:1 by Danilo Bargen, 10 years ago

Cc: mail@… added
Triage Stage: UnreviewedAccepted

I can confirm this.

comment:2 by Stephane "Twidi" Angel, 10 years ago

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

Version 0, edited 10 years ago by Stephane "Twidi" Angel (next)

comment:3 by Andrew Godwin <andrew@…>, 10 years ago

Resolution: fixed
Status: newclosed

In c5def493d0993d65bf7d96f0a204006cbeaa6178:

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

comment:4 by Andrew Godwin, 10 years ago

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.

Note: See TracTickets for help on using tickets.
Back to Top