Opened 4 years ago

Closed 2 years ago

Last modified 2 years ago

#32528 closed Cleanup/optimization (fixed)

Replace django.utils.topological_sort with graphlib.

Reported by: Nick Pope Owned by: Nick Pope
Component: Utilities Version: dev
Severity: Normal Keywords: backport, graphlib, toposort, topological sort
Cc: Triage Stage: Ready for checkin
Has patch: yes Needs documentation: no
Needs tests: no Patch needs improvement: no
Easy pickings: no UI/UX: no

Description (last modified by Nick Pope)

In Python 3.9 we have a new standard library module, ​graphlib, that includes a topological sort implementation.
Let's use this instead of our custom implementation in django.utils.topological_sort.

This will require a backport for Python 3.8, the minimum supported version for Django 4.0, but when support for Python 3.8 is removed we can simply drop the backport. When using Python 3.9+ we'll just use the module direct from the standard library.

Change History (9)

comment:1 by Nick Pope, 4 years ago

Has patch: set

​PR

comment:2 by Mariusz Felisiak, 4 years ago

Triage Stage: Unreviewed → Someday/Maybe

Thanks for this report, however but I don't think we should backport this feature from Python or use it now. It would be hard to keep graphlib implementation and our backport in sync, it's not worth the maintenance burden. We can reconsider this ticket when Python 3.9 becomes the minimal Python supported by Django.

comment:3 by Nick Pope, 4 years ago

That's fine. Was really just putting this on the radar.

comment:4 by Nick Pope, 2 years ago

Triage Stage: Someday/Maybe → Accepted

Whoop! The time has come. New ​PR.

comment:5 by Nick Pope, 2 years ago

Description: modified (diff)

comment:6 by Carlton Gibson, 2 years ago

Triage Stage: Accepted → Ready for checkin

comment:7 by Mariusz Felisiak <felisiak.mariusz@…>, 2 years ago

Resolution: → fixed
Status: assigned → closed

In 1282b5e:

Fixed #32528 -- Replaced django.utils.topological_sort with graphlib.TopologicalSort().

graphlib.TopologicalSort() is available since Python 3.9.

comment:8 by Mariusz Felisiak <felisiak.mariusz@…>, 2 years ago

In 1e62a642:

Refs #32528 -- Simplified Media.merge().

This avoids building up a second datastructure for the duplicate files
warning case and simply flatten and strip duplicates if that case ever
arises.

comment:9 by Mariusz Felisiak <felisiak.mariusz@…>, 2 years ago

In 39f8376:

Refs #32528 -- Simplified MigrationAutodetector._sort_migrations().

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