Repository navigation
Commit 92172d3
Canonicalization: avoid exponential collapse when a utility sets many properties (#20558)
## Summary
Fixes #20557.
`canonicalizeCandidates(…, { collapse: true })` took time that doubled
with every class in a group of linked candidates.
`collapseGroup` links two candidates when their `otherUtilities` sets
(possible replacements) share an entry, and then tries every combination
(2^n − n − 1) of each linked group, computing a signature for each. A
static utility that sets many properties ends up in the `otherUtilities`
of every candidate that sets one of those properties. For example
`sr-only` and `not-sr-only` link `relative`, `mt-1`, `w-64`,
`overflow-x-auto`, `whitespace-nowrap`, … and a project `@utility` used
as a component class does the same, even when the class list doesn't use
it.
But such a replacement can never be picked. Its signature can only equal
the signature of a combination if every property it sets is also set by
a candidate in that combination, and each of those candidates has the
replacement in its own `otherUtilities`. `sr-only` also sets `clip-path`
and `border-width`, which none of those candidates set, so no
combination can ever match it.
This PR changes two things:
1. Before linking, drop every replacement whose properties aren't
covered by the candidates that list it. This only uses the property
lookups that are already computed, and it only removes replacements that
can't match, so the replacements that do get used stay the same. With
the impossible ones gone, the giant linked groups split up into the
small groups you'd expect (e.g. `overflow-x-*` + `overflow-y-*` →
`overflow-*`), so the number of combinations stays small.
2. In the combination loop, skip the (expensive) signature computation
for a combination when the intersection of its possible replacements is
empty.
Results with the reproduction from the issue (Node 20, same design
system per row; times are for one `canonicalizeCandidates` call):
| Case | Classes | Before | After |
| --- | --: | --: | --: |
| A: default theme | 10 | 102 ms | 19 ms |
| | 12 | 369 ms | 22 ms |
| | 14 | 1,374 ms | 20 ms |
| B: default theme + `pill` `@utility` | 12 | 348 ms | 19 ms |
| | 14 | 1,709 ms | 24 ms |
| | 15 | 3,487 ms | 29 ms |
| | 16 | 7,278 ms | 26 ms |
The output was the same before and after for every row, including
`text-sm leading-5` → `text-sm/5`, which the issue mentions breaking
when the lookup was restricted to matching values instead.
One limit: if a class list really does cover every property of a big
utility, its candidates are still linked through it, and that group is
still enumerated as before. That's the existing behaviour, and it's much
rarer than the cases above.
## Test plan
- Added a regression test with 23 classes linked through `sr-only`,
`not-sr-only` and a `pill` `@utility`. It checks the collapsed output
(`text-sm leading-5` → `text-sm/5`, everything else untouched) and that
it finishes in under 5 s. It takes ~0.8 s on this branch. Without the
fix I stopped it after more than 3 minutes.
- `pnpm vitest run packages/tailwindcss/src`: 43 files, 5017 tests
passing (this includes all 1805 existing canonicalization tests, whose
outputs are unchanged).
- `prettier --check` on the changed files; `tsc` reports no errors for
the changed files.
---------
Co-authored-by: Robin Malfait <[email protected]>1 parent 374d191 commit 92172d3
3 files changed
Lines changed: 135 additions & 0 deletions
File tree
- packages/tailwindcss/src
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
51 | 51 | | |
52 | 52 | | |
53 | 53 | | |
| 54 | + | |
54 | 55 | | |
55 | 56 | | |
56 | 57 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1588 | 1588 | | |
1589 | 1589 | | |
1590 | 1590 | | |
| 1591 | + | |
| 1592 | + | |
| 1593 | + | |
| 1594 | + | |
| 1595 | + | |
| 1596 | + | |
| 1597 | + | |
| 1598 | + | |
| 1599 | + | |
| 1600 | + | |
| 1601 | + | |
| 1602 | + | |
| 1603 | + | |
| 1604 | + | |
| 1605 | + | |
| 1606 | + | |
| 1607 | + | |
| 1608 | + | |
| 1609 | + | |
| 1610 | + | |
| 1611 | + | |
| 1612 | + | |
| 1613 | + | |
| 1614 | + | |
| 1615 | + | |
| 1616 | + | |
| 1617 | + | |
| 1618 | + | |
| 1619 | + | |
| 1620 | + | |
| 1621 | + | |
| 1622 | + | |
| 1623 | + | |
| 1624 | + | |
| 1625 | + | |
| 1626 | + | |
| 1627 | + | |
| 1628 | + | |
| 1629 | + | |
| 1630 | + | |
| 1631 | + | |
| 1632 | + | |
| 1633 | + | |
| 1634 | + | |
| 1635 | + | |
| 1636 | + | |
| 1637 | + | |
| 1638 | + | |
| 1639 | + | |
| 1640 | + | |
| 1641 | + | |
| 1642 | + | |
| 1643 | + | |
| 1644 | + | |
| 1645 | + | |
| 1646 | + | |
| 1647 | + | |
| 1648 | + | |
| 1649 | + | |
| 1650 | + | |
| 1651 | + | |
| 1652 | + | |
| 1653 | + | |
| 1654 | + | |
| 1655 | + | |
| 1656 | + | |
| 1657 | + | |
| 1658 | + | |
| 1659 | + | |
| 1660 | + | |
1591 | 1661 | | |
1592 | 1662 | | |
1593 | 1663 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
407 | 407 | | |
408 | 408 | | |
409 | 409 | | |
| 410 | + | |
| 411 | + | |
| 412 | + | |
| 413 | + | |
| 414 | + | |
| 415 | + | |
| 416 | + | |
| 417 | + | |
| 418 | + | |
| 419 | + | |
| 420 | + | |
| 421 | + | |
| 422 | + | |
| 423 | + | |
| 424 | + | |
| 425 | + | |
| 426 | + | |
| 427 | + | |
| 428 | + | |
| 429 | + | |
| 430 | + | |
| 431 | + | |
| 432 | + | |
| 433 | + | |
| 434 | + | |
| 435 | + | |
| 436 | + | |
| 437 | + | |
| 438 | + | |
| 439 | + | |
| 440 | + | |
| 441 | + | |
| 442 | + | |
| 443 | + | |
| 444 | + | |
| 445 | + | |
| 446 | + | |
| 447 | + | |
| 448 | + | |
| 449 | + | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
| 460 | + | |
| 461 | + | |
| 462 | + | |
| 463 | + | |
| 464 | + | |
| 465 | + | |
| 466 | + | |
| 467 | + | |
| 468 | + | |
| 469 | + | |
410 | 470 | | |
411 | 471 | | |
412 | 472 | | |
| |||
475 | 535 | | |
476 | 536 | | |
477 | 537 | | |
| 538 | + | |
| 539 | + | |
| 540 | + | |
| 541 | + | |
478 | 542 | | |
479 | 543 | | |
480 | 544 | | |
| |||
0 commit comments