Csswg-drafts: [css-nesting] Concern about combinatorial explosion

[upsuper]

The most intuitive way to implement nesting rules is probably just expand them internally as their complete form, just like what preprocessors do nowadays.

But this has a problem that it means the number of selectors to match can grow exponentially as the nesting get deeper. This is less a concern when it was handled by preprocessors, because authors would see the exponential result from the generated file. If they see a generated CSS sized hundreds of megabytes or even gigabytes, they know there is a problem. But with nesting rules, they can hand to browsers a CSS file with just a handful of kilobytes which can be expanded to millions of rules, that would be problematic.

Consider something like

.a1, .a2 {
&.b1, &.b2 {
&.c1, &.c2 {
&.d1, &.d2 {
&.e1, &.e2 {
&.f1, &.f2 {
&.g1, &.g2 {
&.h1, &.h2 {
&.i1, &.i2 {
&.j1, &.j2 {
&.k1, &.k2 {
&.l1, &.l2 {
&.m1, &.m2 {
&.n1, &.n2 {
&.o1, &.o2 {
&.p1, &.p2 {
&.q1, &.q2 {
&.r1, &.r2 {
&.s1, &.s2 {
&.t1, &.t2 {
&.u1, &.u2 {
&.v1, &.v2 {
&.w1, &.w2 {
&.x1, &.x2 {
&.y1, &.y2 {
&.z1, &.z2 {

It's only 300+ bytes, but can be expanded into 67M selectors. It's probably not good.

Potential solutions includes:

1. restrict the maximum nesting levels (e.g. at most 3 levels are allowed)
2. allow only a single complex selector, rather than a list in nested rules

[tabatkins]

Allowing selector lists is necessary; the combinatorial explosion is, in large part, the point of nesting.

I'm fine with allowing a max, tho 3 is a little low. Perhaps 5 or 6?

[upsuper]

I have a feeling that shortening selectors is also an important usefulness from nesting, so I don't completely buy that combinatorial explosion is the point, but I'm okay with that argument.

Do we have data on how many levels do people do nowadays with preprocessors? I assume two levels (one top level and one level nested) should cover majority of cases, and three levels should almost cover the rest. Do people use 5 or 6 levels a lot? With 6 level, you just need 10 selectors in each level to get 1M, which feels problematic still.

[jonjohnjohnson]

Even disallowing more than 6 levels won’t stop the possible explosion using large ‘:matches()’ lists at each of the possible 6 levels?

[upsuper]

I don't think anyone wants to expand :matches() at all, and not expanding it has a reasonable matching complexity as well, especially if we don't have to handle specificity. (The hard part of :matches() in implementation is invalidation, not matching.)

Nested rules are different. On the one hand, while a1, a2 { & b1, & b2 { } } is equivalent to :matches(a1, a2) :matches(b1, b2), a b { & c d { } } means just a b c d and nothing else, unlike :matches(a b) :matches(c d). On the other hand, for nested rules, the parent rule can appear in anywhere in child rule, for example you can say a b { c d & { } } which means c d a b (syntax is not going to be this way but that's the idea). This means rewriting nested rules into a single complex selector without repeating anything is basically impossible, so you would need to expand it anyway.

[upsuper]

(Specificity handling is also hard for :matches() in implementation I guess.)

[tabatkins]

Nested rules are different.

No, they're not, you're just desugaring wrong. ^_^ When desugaring, you replace the & with a :matches() containing the parent selector

• a b { & c d { } } desugars to :matches(a b) c d {}.
• a1, a2 { & b1, & b2 { } } desugars to :matches(a1, a2) b1, :matches(a1, a2) b2 {}. (It so happens that this is equivalent to the wrong desugaring you gave.)
• a b { c d & { } } desugars to c d :matches(a b).

(Specificity handling is also hard for :matches() in implementation I guess.)

No, we resolved to use the simpler version of :matches() specificity - it's the specificity of the most specific argument, regardless of matching.

[upsuper]

No, they're not, you're just desugaring wrong. ^_^ When desugaring, you replace the & with a :matches() containing the parent selector

So it's different from what preprocessors do currently? I don't think preprocessors are able to expand c d :matches(a b) to a selector pre-matches, are they?

Anyway, expanding them to :matches would only make them worse than :matches. Still, I don't believe you can expand any nested selector into a single complex selector. Consider for example, a b { & c d { } e f & { } }, what selector would you expand it to?

No, we resolved to use the simpler version of :matches() specificity - it's the specificity of the most specific argument, regardless of matching.

Oh, okay, that's great. Then :matches() is probably not very hard to implement.

[tabatkins]

I don't think preprocessors are able to expand c d :matches(a b) to a selector pre-matches, are they?

They certainly can, but it explodes combinatorially:

c d a b
c da b
c a d b
ca d b
a c d b

In cases like this (like Sass's @extend), they use some heuristics to avoid having to fully expand the possiblities, while making it highly likely that what they do expand to is useful, but that's not strictly necessary.

Consider for example, a b { & c d { } e f & { } }, what selector would you expand it to?

Just run the desugaring twice, man: e f :matches(:matches(a b) c d).

[upsuper]

Just run the desugaring twice, man: e f :matches(:matches(a b) c d).

That's different, no? In your expanded form it requires all of the a, b, c, d, e, f to appear in the path somehow, while in the original form, only a and b must appear, while either c and d, or e and f need to also appear.

[tabatkins]

No, all of them definitely need to appear, in exactly the relationship I described. What makes you think you can skip any of c/d/e/f? Imagine what elements are matched at each level.

[upsuper]

Are you sure? It's a b { & c d, e f & { } }. Shouldn't it be expanded to :matches(a b) c d, e f :matches(a b) according to your rule? Why do all of c/d/e/f need to appear?

[Loirooriol]

From my understanding,

a b {
  & c d { }
  e f & { }
}

should expand to

:matches(a b) c d { }
e f :matches(a b) { }

Sure, the parent part is repeated but there is no combinatorial explosion.

The problem seems indeed when & is used multiple times in an inner selector:

a1, a2 {
  & b1, & b2 {
    & c1, & c2 {}
  }
}

expands to

:matches(:matches(a1, a2) b1, :matches(a1, a2) b2) c1,
:matches(:matches(a1, a2) b1, :matches(a1, a2) b2) c2 {}

but then I think implementations should just not do this, and reuse the parent part without actually duplicating it.

[upsuper]

but then I think implementations should just not do this, and reuse the parent part without actually duplicating it.

I thought it is very tricky to implement nesting without actually expanding them. But after thinking about it further, I think there is a reasonably simple algorithm to implement this without expanding, so I'm going to close this issue.

I'm still a bit concern about its indication of promoting use of :matches, but that's probably a separate issue.

[upsuper]

After thinking a bit more, I think I was wrong in the previous comment, and I still cannot figure out a universal way to implement nesting rules efficiently without exponentially expanding the selectors.

If we can resolve to use one-element-a-time semantic in #2895, and also to require balanced nesting selector in #2896, and maybe to disallow :not() to contain &, there can be a decent approach to implement but I'm not completely sure.

[upsuper]

I guess anything in the latter half of the previous comment doesn't really matter. The only reasonable way to implement it seems to just be running matching exponentially... or alternatively, having a exponential memory usage and do stuff linearly.

[tabatkins]

Oh! I misread your rule, I didn't realize they were two rules nested in the single parent rule.

(Tangent: that's an invalid rule, btw. Can't have a rule like e f & {}, needs to be @nest e f & {}.)

So that expands to the two rules :matches(a b) c d {} e f :matches(a b) {}. Or if you wanted to use your comma-separated one from the last comment, :matches(a b) c d, e f :matches(a b) {}.

What did you think was complicated about desugaring that?

[upsuper]

I don't think it's complicated to desugar that. The problem is the number of selectors after desugaring grow exponentially and I cannot figure out a reasonable algorithm for matching which neither time nor memory is exponential.

[tabatkins]

It doesn't grow at all if you use :matches() internally, per the desugaring.

[upsuper]

Could you desugar the following selectors with :matches()?

a1, a2 {
@nest & b, b & {
@nest & c, c & {
@nest & d, d & {
@nest & e, e & {
@nest & f, f & {

[tabatkins]

The innermost rule desugars down to:

:matches(:matches(:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2))) d, d:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2)))) e, e :matches(:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2))) d, d:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2))))) f, f:matches(:matches(:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2))) d, d:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2)))) e, e :matches(:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2))) d, d:matches(:matches(:matches(a1, a2) b, b :matches(a1, a2)) c, c :matches(:matches(a1, a2) b, b :matches(a1, a2)))))

The higher rules desugar to subsets of that.

[upsuper]

That's exponential to the length of the selectors written above, isn't it? That one has only 6 levels, so you can still list it. If I wrote 26 levels like the previous comment, maybe your desugared rules would get rejected by GitHub as a comment :D

[tabatkins]

Sure. Very deep nesting of selectors is uncommon in the first place, tho (based on preprocessor experience), and deep nesting of selector lists is even less common. When things are deeply nested, they commonly just do appending, like .foo { & .bar { & .baz {..., which is easy to handle.

That said, I'm still okay with a maximum nesting depth set to something reasonable, like 5 or 6.

[pygy]

Wouldn't a limit on the total length of the expanded selector list make more sense?

Not that nesting 6 levels deep is wise, but a hostile style sheet could still do some damage by using a large lists of selectors at every level (oh, you've disabled JavaScript? How's that? [BAM, here comes a selector bomb that would have been unloaded synchronously by a JS script]).

[tabatkins]

The length of the selector list at a given level doesn't cause any explosion in the :matches()-based desugaring; the higher levels gets repeated more, but doubling the length of the top level just approximately doubles the length of the result. It's the nesting level that causes non-linear growth.

[pygy]

@tabatkins Cleanup edit, this went from a tingling feeling that something wasn't right, to a few false starts, to this which seems solid:

&, a &, & b, b & a, and variations thereof using ~, +, > and juxtaposition can still do some damage.

const nested = [...Array(5)].map(
  ()=> ['&', ...['', ' ', '~', '+', '>'].map(
    sigil => 'a &,& b,b & a'.replace(/ /g, sigil)
  )].join(','),
)
nested.join('').length // 335

nested.reduce(
  (r, v) => v.replace(/&/g, `:is(${r})`),
  'b, b b, b b b, b b b b, b b b b b, b b b b b b'
).length // 57,392,051

That's a sweet payout. Not sure if it can be made worse by the fact that combinators and nesting interact in non-trivial ways (i.e. not sure if b~&>a can be flattened with either b~&~a or b>&>a or if it adds to the non-linear expansion).

Contrast that with an iframe bomb that has a linear server cost.