Summary

Add a graph for managing dependencies between evolutions and migrations.

Review Request #11231 — Created Oct. 19, 2020 and submitted Oct. 30, 2020, 3:28 p.m.

Information

Owner

chipx86

Repository

Django Evolution

Branch

master

Bugs

Depends On

Reviewers

Groups

django-evolution

People

Description

This introduces two new classes: DependencyGraph and EvolutionGraph.

DependencyGraph is a generic class for managing dependencies between
nodes and returning an order using a topological sort. Each node
stores a key, an insertion order (the order in which it was added
to the graph), a dictionary of state, and lists of nodes that it depends
on or that depend on it.

Dependencies are lazily-added through the graph, and can be removed.
When all manipulations of the graph are complete, a caller will call
finalize() to record dependencies, validate the graph, and allow
fetching the sorted order of nodes.

The previously-mentioned insertion order is an important implementation
detail in this graph. These work as a sort of loose dependency between
nodes. If two nodes don't define explicit dependencies to specify their
order, the insertion order will be used. This helps keep the order
generally consistent with the evolution ordering that we've used in the
past.

EvolutionGraph specializes this to manage dependencies
between evolutions, migrations, and model creations. An entire list of
evolutions and model creations for an app can be added at once, or an
entire migration plan. The graph will take care of determining the
correct dependencies for these and apply them. It then allows the caller
to retrieve batches of evolutions/migrations/model creations, grouped by
type and in the order indicated by dependencies.

As of this change, the graph isn't used outside of unit tests. Upcoming
changes will switch Evolver over to using the graph to apply
evolutions and migrations in the correct order.

Testing Done

Unit tests pass on all supported versions of Python and Django.

Commits

Summary	ID
Add a graph for managing dependencies between evolutions and migrations. This introduces two new classes: `DependencyGraph` and `EvolutionGraph`. `DependencyGraph` is a generic class for managing dependencies between nodes and returning an order using a topological sort. Each node stores a key, an insertion order (the order in which it was added to the graph), a dictionary of state, and lists of nodes that it depends on or that depend on it. Dependencies are lazily-added through the graph, and can be removed. When all manipulations of the graph are complete, a caller will call `finalize()` to record dependencies, validate the graph, and allow fetching the sorted order of nodes. The previously-mentioned insertion order is an important implementation detail in this graph. These work as a sort of loose dependency between nodes. If two nodes don't define explicit dependencies to specify their order, the insertion order will be used. This helps keep the order generally consistent with the evolution ordering that we've used in the past. `EvolutionGraph` specializes this to manage dependencies between evolutions, migrations, and model creations. An entire list of evolutions and model creations for an app can be added at once, or an entire migration plan. The graph will take care of determining the correct dependencies for these and apply them. It then allows the caller to retrieve batches of evolutions/migrations/model creations, grouped by type and in the order indicated by dependencies. As of this change, the graph isn't used outside of unit tests. Upcoming changes will switch `Evolver` over to using the graph to apply evolutions and migrations in the correct order.	f5846d8506fefe49d5bce93adb91cb984ee445a5

Summary

Add a graph for managing dependencies between evolutions and migrations.

This introduces two new classes: `DependencyGraph` and `EvolutionGraph`. `DependencyGraph` is a generic class for managing dependencies between nodes and returning an order using a topological sort. Each node stores a key, an insertion order (the order in which it was added to the graph), a dictionary of state, and lists of nodes that it depends on or that depend on it. Dependencies are lazily-added through the graph, and can be removed. When all manipulations of the graph are complete, a caller will call `finalize()` to record dependencies, validate the graph, and allow fetching the sorted order of nodes. The previously-mentioned insertion order is an important implementation detail in this graph. These work as a sort of loose dependency between nodes. If two nodes don't define explicit dependencies to specify their order, the insertion order will be used. This helps keep the order generally consistent with the evolution ordering that we've used in the past. `EvolutionGraph` specializes this to manage dependencies between evolutions, migrations, and model creations. An entire list of evolutions and model creations for an app can be added at once, or an entire migration plan. The graph will take care of determining the correct dependencies for these and apply them. It then allows the caller to retrieve batches of evolutions/migrations/model creations, grouped by type and in the order indicated by dependencies. As of this change, the graph isn't used outside of unit tests. Upcoming changes will switch `Evolver` over to using the graph to apply evolutions and migrations in the correct order.

f5846d8506fefe49d5bce93adb91cb984ee445a5

Issues

Description	From	Last Updated
F841 local variable 'migrations_app' is assigned to but never used	reviewbot	Oct. 20, 2020, 6:47 p.m.
F841 local variable 'migrations_app2' is assigned to but never used	reviewbot	Oct. 20, 2020, 6:47 p.m.
F401 'collections.OrderedDict' imported but unused	reviewbot	Oct. 20, 2020, 6:48 p.m.
Maybe say set of Node here like you do for dependencies?	david	Oct. 25, 2020, 2:11 a.m.

flake8 failed.

JSHint passed.

flake8

django_evolution/tests/test_evolution_graph.py (Diff revision 1)
The issue has been resolved. Show all issues
```
F841 local variable 'migrations_app' is assigned to but never used
```
django_evolution/tests/test_evolution_graph.py (Diff revision 1)
The issue has been resolved. Show all issues
```
F841 local variable 'migrations_app2' is assigned to but never used
```
django_evolution/utils/graph.py (Diff revision 1)
The issue has been resolved. Show all issues
```
F401 'collections.OrderedDict' imported but unused
```

Change Summary:


Removed unused variables and imports.
Defaulted the graph's processing of migration dependencies based on the supports_migrations flag.
Improved some assertion error messages, to aid debugging.

Commits:

	Summary	ID
	Add a graph for managing dependencies between evolutions and migrations. This introduces two new classes: `DependencyGraph` and `EvolutionGraph`. `DependencyGraph` is a generic class for managing dependencies between nodes and returning an order using a topological sort. Each node stores a key, an insertion order (the order in which it was added to the graph), a dictionary of state, and lists of nodes that it depends on or that depend on it. Dependencies are lazily-added through the graph, and can be removed. When all manipulations of the graph are complete, a caller will call `finalize()` to record dependencies, validate the graph, and allow fetching the sorted order of nodes. The previously-mentioned insertion order is an important implementation detail in this graph. These work as a sort of loose dependency between nodes. If two nodes don't define explicit dependencies to specify their order, the insertion order will be used. This helps keep the order generally consistent with the evolution ordering that we've used in the past. `EvolutionGraph` specializes this to manage dependencies between evolutions, migrations, and model creations. An entire list of evolutions and model creations for an app can be added at once, or an entire migration plan. The graph will take care of determining the correct dependencies for these and apply them. It then allows the caller to retrieve batches of evolutions/migrations/model creations, grouped by type and in the order indicated by dependencies. As of this change, the graph isn't used outside of unit tests. Upcoming changes will switch `Evolver` over to using the graph to apply evolutions and migrations in the correct order.	ad2b27f461c65b86bdf742f4310eac116d9a618b
	Add a graph for managing dependencies between evolutions and migrations. This introduces two new classes: `DependencyGraph` and `EvolutionGraph`. `DependencyGraph` is a generic class for managing dependencies between nodes and returning an order using a topological sort. Each node stores a key, an insertion order (the order in which it was added to the graph), a dictionary of state, and lists of nodes that it depends on or that depend on it. Dependencies are lazily-added through the graph, and can be removed. When all manipulations of the graph are complete, a caller will call `finalize()` to record dependencies, validate the graph, and allow fetching the sorted order of nodes. The previously-mentioned insertion order is an important implementation detail in this graph. These work as a sort of loose dependency between nodes. If two nodes don't define explicit dependencies to specify their order, the insertion order will be used. This helps keep the order generally consistent with the evolution ordering that we've used in the past. `EvolutionGraph` specializes this to manage dependencies between evolutions, migrations, and model creations. An entire list of evolutions and model creations for an app can be added at once, or an entire migration plan. The graph will take care of determining the correct dependencies for these and apply them. It then allows the caller to retrieve batches of evolutions/migrations/model creations, grouped by type and in the order indicated by dependencies. As of this change, the graph isn't used outside of unit tests. Upcoming changes will switch `Evolver` over to using the graph to apply evolutions and migrations in the correct order.	f5846d8506fefe49d5bce93adb91cb984ee445a5

Diff:

Revision 2 (+3468 -6)

Show changes

	django_evolution/tests/test_dependency_graph.py
	django_evolution/tests/test_evolution_graph.py
	django_evolution/tests/evolutions_app/models.py
	django_evolution/tests/evolutions_app2/models.py
	django_evolution/tests/migrations_app2/migrations/0001_initial.py
	django_evolution/utils/graph.py
	docs/coderef/index.rst

Checks run (2 succeeded)

flake8 passed.

JSHint passed.

Ship it!

django_evolution/utils/graph.py (Diff revision 2)
The issue has been resolved. Show all issues
```
Maybe say set of Node here like you do for dependencies?
```

Status: Closed (submitted)

Change Summary:

Pushed to master (0d14b38)