Make dataclass attr collection no longer worst-case quadratic #13539
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
While working on #13531, I noticed that DataclassTransformer's
collect_attributes
method was doing basically this:Constantly searching through and removing items from
all_attrs
, then pre-pending the superclass attrs will result in worst-case quadratic behavior in the edge case where subtype is overriding every attribute defined in the supertype.This edge case is admittedly pretty unlikely to happen, but I wanted to clean up the code a bit by reversing the order in which we process everything so we naturally record attrs in the correct order. The code now looks more like this:
One quirk of the old implementation I found was that we only move kw-only attrs to the end of the attrs list when we find at least one dataclass supertype. I tried changing this logic so we unconditionally sort/do not sort the list, but both alternatives ended up breaking some tests. I'm not sure I really understand what's supposed to happen here, so opted to just keep this part of mypy as-is.