Skip to content

Commit 92172d3

Browse files
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

‎CHANGELOG.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
5151
- Ensure `@tailwindcss/postcss` rewrites relative `url(…)`s of stylesheets that are inlined before it runs (e.g. `@import`s in Vite) in optimized builds ([#20576](https://github.com/tailwindlabs/tailwindcss/pull/20576))
5252
- Drop nested rules that put a combinator after a pseudo-element when using pseudo-element variants (e.g. `selection:*` on a utility with a nested `& > *` rule) ([#20575](https://github.com/tailwindlabs/tailwindcss/pull/20575))
5353
- Don't generate CSS for arbitrary values with unbalanced parentheses or brackets (e.g. `w-[calc(1px]` or `[--x:a[b]`) ([#20577](https://github.com/tailwindlabs/tailwindcss/pull/20577))
54+
- Canonicalization: prevent `collapse: true` from taking exponentially longer when classes are linked through a utility that sets many properties (e.g. `sr-only`) ([#20558](https://github.com/tailwindlabs/tailwindcss/pull/20558))
5455

5556
## [4.3.3] - 2026-07-16
5657

‎packages/tailwindcss/src/canonicalize-candidates.test.ts‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1588,6 +1588,76 @@ describe('regressions', () => {
15881588
})
15891589
}
15901590

1591+
// https://github.com/tailwindlabs/tailwindcss/issues/20557
1592+
test(
1593+
'collapse does not try every combination of candidates linked by a utility that sets many properties',
1594+
{ timeout },
1595+
async () => {
1596+
let designSystem = await designSystems.get(__dirname).get(css`
1597+
@import 'tailwindcss';
1598+
1599+
@utility pill {
1600+
position: relative;
1601+
display: inline-flex;
1602+
align-items: center;
1603+
gap: 0.5rem;
1604+
height: 2rem;
1605+
padding: 0.25rem 0.75rem;
1606+
margin: 0;
1607+
border-radius: 9999px;
1608+
font-size: 0.875rem;
1609+
line-height: 1.25rem;
1610+
font-weight: 500;
1611+
color: white;
1612+
background-color: black;
1613+
white-space: nowrap;
1614+
overflow: hidden;
1615+
cursor: pointer;
1616+
}
1617+
`)
1618+
1619+
// Every candidate sets a property that `sr-only`, `not-sr-only` or
1620+
// `pill` also sets, so they used to end up in one group of linked
1621+
// candidates. Trying every combination of 2^n candidates of that group
1622+
// took tens of seconds.
1623+
let candidates = [
1624+
'relative',
1625+
'mt-1',
1626+
'mr-2',
1627+
'mb-3',
1628+
'ml-4',
1629+
'pt-1',
1630+
'pr-2',
1631+
'pb-3',
1632+
'pl-4',
1633+
'w-64',
1634+
'h-10',
1635+
'overflow-x-auto',
1636+
'overflow-y-hidden',
1637+
'whitespace-nowrap',
1638+
'flex',
1639+
'items-center',
1640+
'gap-2.5',
1641+
'rounded-full',
1642+
'bg-white',
1643+
'cursor-pointer',
1644+
'font-normal',
1645+
'text-sm',
1646+
'leading-5',
1647+
]
1648+
1649+
let start = performance.now()
1650+
let result = designSystem.canonicalizeCandidates(candidates, DEFAULT_CANONICALIZATION_OPTIONS)
1651+
let duration = performance.now() - start
1652+
1653+
expect(result).toEqual([
1654+
...candidates.filter((candidate) => candidate !== 'text-sm' && candidate !== 'leading-5'),
1655+
'text-sm/5',
1656+
])
1657+
expect(duration).toBeLessThan(5_000)
1658+
},
1659+
)
1660+
15911661
// https://github.com/tailwindlabs/tailwindcss/pull/19727
15921662
test(
15931663
'collapse does not crash when utilities with no standard properties are present',

‎packages/tailwindcss/src/canonicalize-candidates.ts‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -407,6 +407,66 @@ function collapseCandidates(options: InternalCanonicalizeOptions, candidates: st
407407
return result ?? new Set<string>()
408408
})
409409

410+
// A replacement can only ever have the same signature as a combination of
411+
// candidates if every property it sets is also set by one of the
412+
// candidates in that combination. Each candidate in such a combination
413+
// also lists that replacement in its `otherUtilities`, so a replacement
414+
// whose properties are not covered by all the candidates that list it can
415+
// never be used.
416+
//
417+
// Dropping those replacements up front is important for performance: some
418+
// utilities set a lot of properties (e.g.: `sr-only`, or a project
419+
// `@utility` used as a component class). Without this step they link
420+
// almost every candidate to every other candidate, and since we try every
421+
// combination of linked candidates, the work doubles with every candidate
422+
// in such a group.
423+
//
424+
// E.g.: `relative` and `mt-1` are both covered by `sr-only` (it sets
425+
// `position` and `margin-top`), but `sr-only` also sets properties like
426+
// `clip-path` that none of the candidates set, so it can never be a valid
427+
// replacement and should not link them.
428+
//
429+
// A replacement that is listed by a single candidate can't link candidates
430+
// or replace a combination either, so we can drop those without computing
431+
// their coverage. This keeps the common case of unrelated candidates fast.
432+
let seen = new Set<string>()
433+
let shared = new Set<string>()
434+
for (let replacements of otherUtilities) {
435+
for (let replacement of replacements) {
436+
if (seen.has(replacement)) shared.add(replacement)
437+
else seen.add(replacement)
438+
}
439+
}
440+
441+
let coveredProperties = new DefaultMap((_replacement: string) => new Set<string>())
442+
for (let [idx, replacements] of otherUtilities.entries()) {
443+
for (let replacement of replacements) {
444+
if (!shared.has(replacement)) continue
445+
let covered = coveredProperties.get(replacement)
446+
for (let property of candidatePropertiesValues[idx].keys()) {
447+
covered.add(property)
448+
}
449+
}
450+
}
451+
452+
let isPossibleReplacement = new DefaultMap((replacement: string) => {
453+
let covered = coveredProperties.get(replacement)
454+
for (let property of computeUtilitiesPropertiesLookup.get(replacement).keys()) {
455+
if (!covered.has(property)) return false
456+
}
457+
return true
458+
})
459+
460+
otherUtilities = otherUtilities.map((replacements) => {
461+
let result = new Set<string>()
462+
for (let replacement of replacements) {
463+
if (shared.has(replacement) && isPossibleReplacement.get(replacement)) {
464+
result.add(replacement)
465+
}
466+
}
467+
return result
468+
})
469+
410470
// Link each candidate that could be linked via another utility
411471
// (intersection). This way we can reduce the amount of required combinations.
412472
//
@@ -475,6 +535,10 @@ function collapseCandidates(options: InternalCanonicalizeOptions, candidates: st
475535

476536
let potentialReplacements = combo.flatMap((idx) => otherUtilities[idx]).reduce(intersection)
477537

538+
// Computing the signature of the combination is expensive, so skip it
539+
// when there is nothing to compare it against.
540+
if (potentialReplacements.size === 0) continue
541+
478542
let collapsed = combo
479543
.map((idx) => candidates[idx])
480544
.sort((a, z) => a.localeCompare(z)) // Sort to increase cache hits

0 commit comments

Comments
 (0)