Open upsuper opened 6 years ago
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?
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.
Even disallowing more than 6 levels won’t stop the possible explosion using large ‘:matches()’ lists at each of the possible 6 levels?
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.
(Specificity handling is also hard for :matches()
in implementation I guess.)
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.
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.
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)
.
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.
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.
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?
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.
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.
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.
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.
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?
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.
It doesn't grow at all if you use :matches() internally, per the desugaring.
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 & {
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.
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
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.
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]).
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.
@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.
I could see capping at 6 deep being reasonable. I agree it's uncommon to see nesting deeper than that. Does seem like a limit should be present though, just like with custom properties and the billion laughs attack it can produce without the limit.
Agenda+ to discuss if we want to:
Following the same reasoning as in https://github.com/w3c/csswg-drafts/issues/3462, I'm fine with
Going ahead and tagging this for f2f discussion, as it seems good to hash this out.
For completeness, WebKit imposes a limit of 128 nesting levels: https://github.com/WebKit/WebKit/commit/c9ac90f8cbfa0ae54a296168fe0c517826ff6757
Lol that is way higher than the minimum I'd add, so that's fine. (I was considering, like, 10 or something.)
@sesse Correct me if I'm wrong, but my understanding of https://github.com/w3c/csswg-drafts/issues/8310#issuecomment-1383810771 is that Blink doesn't expand &
so it's not affected by this problem. Couldn't other implementations use the same approach?
WebKit expands &
to :is(parent_selector_list)
, which grows to something like O(average_number_of_nesting_selectors_at_each_level^depth)
Also, we indeed have a maximum rule nesting level, but not specifically for style rule nesting.
@Loirooriol I'm on vacation, but Blink does indeed store & as just a pointer to the parent selector (no combinatorial explosion), and I do not (personally) know of any reason why WebKit could not do the same.
This testcase has 25 levels:
<!DOCTYPE html>
<script>
let t = performance.now();
</script>
<style>
& e1a, & e1b {
& e2a, & e2b {
& e3a, & e3b {
& e4a, & e4b {
& e5a, & e5b {
& e6a, & e6b {
& e7a, & e7b {
& e8a, & e8b {
& e9a, & e9b {
& e10a, & e10b {
& e11a, & e11b {
& e12a, & e12b {
& e13a, & e13b {
& e14a, & e14b {
& e15a, & e15b {
& e16a, & e16b {
& e17a, & e17b {
& e18a, & e18b {
& e19a, & e19b {
& e20a, & e20b {
& e21a, & e21b {
& e22a, & e22b {
& e23a, & e23b {
& e24a, & e24b {
& e25a, & e25b {
background: lime;
</style>
<e1a><e2a><e3a><e4a><e5a><e6a><e7a><e8a><e9a><e10a><e11a><e12a><e13a><e14a><e15a><e16a><e17a><e18a><e19a><e20a><e21a><e22a><e23a><e24a><e25a>
text
<script>
document.body.offsetLeft;
document.body.append(performance.now() - t + "ms");
</script>
Blink takes ~10 seconds, WebKit crashes after a long freeze. So Blink is better but it still seems affected by this problem.
Live test-case: http://crisal.io/tmp/lots-of-nesting.html
Firefox Nightly takes ~4s on my machine fwiw :P
I was wrongly getting few ms in Nightly, I have moved let t = performance.now();
to the very top, then I get like 6s.
Note that Chrome has the same timing if each rule is a single selector wrapped in :is()
(that is, :is(& e1a, & e1b) {...}
, so the perf issues are introduced by something other than the branching itself. (This also means we can't base it on a complexity budget depending on the length of the selector lists.)
And Chrome has different timing if you collapse away the nesting. That is, :is(a, b) { :is(c, d) {...}}
and :is(a, b) :is(c, d) ... {...}
are at least a 10x difference in timing (with the 25 :is()
functions, i got 0.8s vs 13s on my laptop). So it's still slow, but there's something else also contributing to the blowup.
Just a tangential side note on this: When UAs hit a selector/nesting limit, their DevTools should give the authors a hint noting that.
Sebastian
And Chrome has different timing if you collapse away the nesting. That is,
:is(a, b) { :is(c, d) {...}}
and:is(a, b) :is(c, d) ... {...}
are at least a 10x difference in timing (with the 25:is()
functions, i got 0.8s vs 13s on my laptop). So it's still slow, but there's something else also contributing to the blowup.
That seems to indicate that there is a design choice in Chrome's implementation that is causing this to be an issue at levels lower than it could in theory. Maybe once that root cause is identified, it would be possible to agree on a very large limit and call it a day.
Also +1 that maybe a warning in the DevTools would go a long way in discouraging author abuse, but if the concern is malicious code injection (to trigger DoS), that doesn't solve the problem.
The CSS Working Group just discussed [css-nesting] Concern about combinatorial explosion
, and agreed to the following:
RESOLVED: limits on nesting is ua-defined
We already have this kind of "not obvious for author" exponential expansion with --var
. The css-variables spec warns about this, maybe the css-nesting spec could have a similar paragraph.
To avoid this sort of attack, UAs must impose a UA-defined limit on the allowed length of the token stream that a var() function expands into. If a var() would expand into a longer token stream than this limit, it instead makes the property it’s expanding into invalid at computed-value time.
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
It's only 300+ bytes, but can be expanded into 67M selectors. It's probably not good.
Potential solutions includes: