id	summary	reporter	owner	description	type	status	component	version	severity	resolution	keywords	cc	stage	has_patch	needs_docs	needs_tests	needs_better_patch	easy	ui_ux
24266	Change `get_parent_list` to return a list of parents ordered by __mro__ instead of a set	Simon Charette	nobody	"The `get_parent_list()` method was introduced [https://github.com/django/django/blame/a53541852d5601232899e54d66e623bc163c6dc2/django/db/models/options.py#L647-L656 more than 6 years ago] and has been returning an unordered `set()` since then.

From the method name suffix and the misleading `__doc__` I guess the returned data type was changed late in the process of merging [https://github.com/django/django/commit/9c52d56f6f8a9cdafb231adf9f4110473099c9b5 Malcom's queryset refactor] in order to deal with the multiple ORM's ancestors existence checks by reducing [https://wiki.python.org/moin/TimeComplexity time complexity].

While working on fixing a field shadowing issue in multi-inheritance scenarios (#24249) it was discovered that [https://github.com/django/django/pull/4018#issuecomment-72201349 `get_parent_list()` actually returns] an unordered `set()` which might causes non-deterministic behaviors. For example, another patch working on making sure unique checks take multi-inheritance into account (#15321) could result in different validation errors being raised from the same input based on the non-deterministic ordering of ancestors.

Since the undocumented `get_parent_list()` method seems to be [https://github.com/search?utf8=%E2%9C%93&q=get_parent_list+language%3Apython&type=Code&ref=searchresults used in the wild] I suggest we deprecate and replace it by a `get_ancestors()` one with the following properties:

* A more significant name given it returns ancestors regardless of lineage.
* A return value ordered by the `__mro__` of the model.
* A return value with `in` operations with similar time complexity.

One of the available data structure with the required return value properties is `django.utils.datastructures.OrderedSet` but I wonder if the whole time complexity argument is not moot given multi-inheritance scenarios involving many ancestors shouldn't be that common.

In this case, given we don't mind about backward compatibility of such a private API, we could also fix `get_parent_list()` to actually return a list of unique ancestors ordered by `__mro__`."	Cleanup/optimization	closed	Database layer (models, ORM)	dev	Normal	fixed			Ready for checkin	1	0	0	0	0	0