summaryrefslogtreecommitdiff
path: root/django/db/migrations/graph.py
AgeCommit message (Collapse)Author
2026-01-19Fixed #36869 -- Optimized MigrationGraph._generate_plan membership checks.James Fysh
Previously, `_generate_plan()` relied on list membership checks, resulting in quadratic behavior as the plan grew. On large migration graphs this became a significant performance bottleneck. This change uses `OrderedSet` for the plan, reducing the complexity to linear while preserving insertion order and behavior. Co-authored-by: Nick Pope <nick@nickpope.me.uk>
2025-07-23Refs #36500 -- Rewrapped long docstrings and block comments via a script.django-bot
Rewrapped long docstrings and block comments to 79 characters + newline using script from https://github.com/medmunds/autofix-w505.
2022-02-07Refs #33476 -- Reformatted code with Black.django-bot
2021-07-27Refs #32956 -- Changed "afterwards" to "afterward" in docs and comments.David Smith
This also removes unnecessary comments with the previous spelling. AP Stylebook has a short entry to advise the preferred spelling for "en-us". "Afterwards" is preferred in British English.
2018-09-26Refs #29784 -- Switched to https:// links where available.Jon Dufresne
2018-09-10Fixed #29243 -- Improved efficiency of migration graph algorithm.Krzysztof Gogolewski
2018-03-09Fixed #29180 -- Fixed a regression where migrations already in the plan were ↵Carlton Gibson
readded. Regression in a38ae914d89809aed6d79337b74a8b31b6d3849a.
2018-03-09Refs #29180 -- Added MigrationGraph._generate_plan() for testing.Carlton Gibson
2018-01-12Fixed #28996 -- Simplified some boolean constructs and removed trivial ↵Дилян Палаузов
continue statements.
2018-01-03Fixed #28984 -- Made assorted code simplifications.Tim Graham
2017-12-28Removed unnecessary trailing commas and spaces in various code.Mariusz Felisiak
2017-12-04Fixed #28860 -- Removed unnecessary len() calls.Дилян Палаузов
2017-08-23Simplified migrations.graph.Node.iterative_dfs(), ancestors(), and ↵Sergey Fedoseev
descendants().
2017-02-28Refs #27656 -- Updated django.db docstring verbs according to PEP 257.Anton Samarchyan
2017-02-04Refs #27546 -- Removed hardcoded class names in __repr__() methods.Mads Jensen
2017-01-25Refs #23919 -- Replaced super(ClassName, self) with super().chillaranand
2017-01-22Refs #23919 -- Replaced six.reraise by raiseClaude Paroz
2017-01-19Refs #23919 -- Stopped inheriting from object to define new style classes.Simon Charette
2017-01-18Refs #23919 -- Removed python_2_unicode_compatible decorator usageClaude Paroz
2017-01-18Refs #23919 -- Removed encoding preambles and future importsClaude Paroz
2016-05-08Fixed #25945, #26292 -- Refactored MigrationLoader.build_graph()Jarek Glowacki
2016-04-04Fixed W503 flake8 warnings.Tim Graham
2015-06-15Removed django.utils.functional.total_ordering()Tim Graham
2015-06-01Fixed #24883 -- Added MigrationGraph.__repr__()Yoong Kang Lim
2015-05-02Moved migration exception classes to shared moduleMarkus Holtermann
Thanks Aymeric Augustin for the review.
2015-04-01Fixed #24554 -- Sped up migrations by rendering initial apps when they are ↵Markus Holtermann
first needed Calling Migration.mutate_state() now also allows to do in_place mutations in case an intermediate state is thrown away later. Thanks Anssi Kääriäinen for the idea, Ryan Hall for parts of the patch, and Claude Paroz and Tim Graham for the review
2015-03-29Refs #24366 -- Fixed recursion depth error in migration graphMarten Kenbeek
Made MigrationGraph forwards_plan() and backwards_plan() fall back to an iterative approach in case the recursive approach exceeds the recursion depth limit.
2015-03-29Refs #24366 -- Renamed arguments in MigrationGraph, renamed testsMarten Kenbeek
2015-02-23Fixed #24366 -- Optimized traversal of large migration dependency graphs.Marten Kenbeek
Switched from an adjancency list and uncached, iterative depth-first search to a Node-based design with direct parent/child links and a cached, recursive depth-first search. With this change, calculating a migration plan for a large graph takes several seconds instead of several hours. Marked test `migrations.test_graph.GraphTests.test_dfs` as an expected failure due to reaching the maximum recursion depth.
2015-02-06Sorted imports with isort; refs #23860.Tim Graham
2014-12-21Fixed #24017 -- Added python_2_unicode_compatible in db/migrationsJosh Schneier
2014-11-25Fixed bug in circular dependency algo for migration dependencies.Luke Plant
Previous algo only worked if the first item was a part of the loop, and you would get an infinite loop otherwise (see test). To fix this, it was much easier to do a pre-pass. A bonus is that you now get an error message that actually helps you debug the dependency problem.
2014-11-15Merge pull request #3536 from Zweedeend/ticket_23837Carl Meyer
Fixes #23837: Replace list with deque in migration-planner for improved performance.
2014-11-15Fixed #23835: Changed circular dependency in DFS to be less infiniteAndrew Godwin
2014-11-15Fixes #23837: Replace list.pop(0) by deque.popleft() in dfs function in ↵Niels Kouwenhoven
migrations
2014-10-30Fixed #23556 -- Raised a more meaningful error message when migrations refer ↵Markus Holtermann
to an unavailable node
2014-10-29Limited lines to 119 characters in django/{contrib,db}.Berker Peksag
Refs #23395.
2014-09-10Corrected grammar in migrations error message.Markus Bertheau
2014-09-05 switch out recursive dfs for stack based approach, to avoid possibly ↵Ben Reilly
hitting the recursion limit
2014-08-23Fixed #23341 -- Added migration name to nonexistent migration error in ↵Raffaele Salmaso
makemigrations.
2014-06-17Fixed #22861: Internal migrations done first so __first__ worksAndrew Godwin
Thanks to Chris Beaven.
2014-05-06Added a bunch of missing unicode_literalsClaude Paroz
Refs #22564.
2014-04-30Fixed #22485: Include all unmigrated apps in project state by default.Andrew Godwin
2014-01-08Fixed #21142: Dependency failures on unmigrated apps.Andrew Godwin
2013-10-23Fixed #21298 -- Fixed E301 pep8 warningsAlasdair Nicol
2013-09-06Add --list option to migrate commandAndrew Godwin
2013-08-10Docs tweaks (thanks timgraham)Andrew Godwin
2013-07-26Fix Python 3 supportAndrew Godwin
2013-06-19First stab at some migration creation commandsAndrew Godwin
2013-06-07Auto-naming for migrations and some writer fixesAndrew Godwin