Bug 135293 – CSS JIT: Implement :visited pseudo class

• Component: CSS
• Status: RESOLVED FIXED

[Yusuke Suzuki]

Implement :visited pseudo class for CSS JIT.

[Yusuke Suzuki]

Implementation notes.

* preset VisitedMatchDisabled only when mode is QueryingRules (security issue)
* inside :not, :link and :visited are treated with tricky path
* handle :visited tricks

Seeing the dbaron's post about this[1] and WebKit code,

1. like :visited + span 
2. nested link elements

are affected.

[1]: http://dbaron.org/mozilla/visited-privacy

[Yusuke Suzuki]

Created attachment 235945 [details]
Patch

WIP

[Yusuke Suzuki]

Created attachment 235946 [details]
Patch

WIP

[WebKit Commit Bot]

Attachment 235946 [details] did not pass style-queue:


ERROR: Source/WebCore/ChangeLog:8:  You should remove the 'No new tests' and either add and list tests, or explain why no new tests were possible.  [changelog/nonewtests] [5]
Total errors found: 1 in 3 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Benjamin Poulain]

Wow, this is quite crazy.

I guess the state tracking is made necessary by the isLink() check of SelectorChecker? Do we know what kind of leak that guard is actually protecting? The blog post by David Baron is not exactly clear about that. Maybe it is something we should address during style resolution instead of the SelectorMatching.

[Yusuke Suzuki]

(In reply to comment #5)
> I guess the state tracking is made necessary by the isLink() check of SelectorChecker?

Yes!!! That's correct.

> Do we know what kind of leak that guard is actually protecting? The blog post by David Baron is not exactly clear about that. Maybe it is something we should address during style resolution instead of the SelectorMatching.

Yeah, your question is right!!
Investigating the WebKit :visited implementation, I have some questions and I suspect that this dynamic visitedMatchType is really necessary.
Maybe I miss some WebKit internals, so I'd like to hear your opinions :)

1.
Seeting linkMatchType & adjacent's VisitedMatchTypeDisable protection combo, I think attacks by using getComputedStyle are already protected by them.
So I think that regardless of the result of SelectorChecker#match with isLink() check, getComputedStyle always returns the conservative (assumed as :link) style. Is it correct?

Currently, by using visitedMatchType in SelectorChecker, we disable the actual web pages' view (visual, not programmably readable) for special :visited links, nested and adjacent. But since they are already protected from getComputedStyle attacks by using linkMatchType, personally, I think it's not necessary. Showing :visited view to users is safe because these values are not readable.

I think we can remove visitedMatchType special handling from SelectorChecker by extending determineLinkMatchType to support adjacent case correctly. Do you think about this?
If so, I think we can clean up SelectorChecker and the SelectorCompiler becomes more simple :D

2.
And seeing the SelectorChecker's implementation, I found some edge cases, so I have one concern that current SelectorChecker's protection is already broken.
Currently, SelectorChecker only checks isLink() to the matched element for the fragment. But I think there's curious edge cases.

For example, a selector ":visited .mid .rightmost" is provided, the following ".rightmost"
<p>
  <a href="visited">
    <span class="mid">
      <a class="rightmost">TARGET</a>
    </span>
  </a>
</p>

won't match to this selector. However, the following ".rightmost"

<p>
  <a href="visited">
    <span class="mid">
      <a href="xxx">
        <span class="rightmost">TARGET</span>
      </a>
    </span>
  </a>
</p>

will match to this selector I think. Is it correct, and the expected behavior?

[Yusuke Suzuki]

%s/that this dynamic visitedMatchType is really necessary/that this dynamic visitedMatchType is not necessary/
sorry, mis-typed...

[Benjamin Poulain]

> Currently, by using visitedMatchType in SelectorChecker, we disable the actual web pages' view (visual, not programmably readable) for special :visited links, nested and adjacent. But since they are already protected from getComputedStyle attacks by using linkMatchType, personally, I think it's not necessary. Showing :visited view to users is safe because these values are not readable.

Note that visual aspect are programmatically observable. For example you could change the layout size and observe the size of the document.

--

But I tend to agree with you. Some checks just don't seem to make sense like in the example you posted.

Adding Antti for comment, I believe he rewrote :visited's style resolution a while ago.

Antti: do you know why SelectorChecker's visitedMatchType exists? What cases is it supposed to protect?

[Antti Koivisto]

> Antti: do you know why SelectorChecker's visitedMatchType exists? What cases is it supposed to protect?

It isn't supposed to protect anything. In terms of security the trick is that selector checker (or style resolver in general) never looks into the  actual visited state so can't leak any information (decision to use visited style is done at paint time only).

What it does is to make :visited never match (as opposed to always matching) when doing querySelectorAll or other non-style queries. Any code that achieves the same result is fine.

[Antti Koivisto]

It is also used for some semantics (no idea where these come from or whether they match other browsers):

        // Disable :visited matching when we see the first link or try to match anything else than an ancestors.
        if (context.element->isLink() || (relation != CSSSelector::Descendant && relation != CSSSelector::Child))
            nextContext.visitedMatchType = VisitedMatchDisabled;

[Benjamin Poulain]

It seems simplifying SelectorChecker is a viable path forward. Refactoring this will make it easier to implement the JIT part.

We should make sure to test the hell out of it.

[Yusuke Suzuki]

Antti, Benjamin: Thank you for your clarification.

> It seems simplifying SelectorChecker is a viable path forward. Refactoring this will make it easier to implement the JIT part.
> We should make sure to test the hell out of it.

Agreed. So I've opened the bug 135639 to refactor SelectorChecker and test to ensure there's no security issues :D

[Yusuke Suzuki]

Created attachment 238718 [details]
Patch

[Yusuke Suzuki]

Created attachment 238719 [details]
Patch

[Benjamin Poulain]

Comment on attachment 238719 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238719&action=review

The part about :visited in top level selectors look good to me.

There is code related to :not() on which I would like more information:
    Wouldn't it be possible to handle :not(:link) with the generic path by adding discarding the :not() and adding :visited to the fragment's pseudo classes?

I r- to do a second round with your explanations for :not().

Your changes to StackAllocator looks correct. Feel free to land that separately as reviewed by me.

> Source/WebCore/ChangeLog:8
> +        This patch implements CSS JIT for :visited. And maake :not(:link) JIT-ed.

Typo: maake

> Source/WebCore/ChangeLog:23
> +        Edge cases are tested by the existing tests.
> +        :not(:link)
> +            fast/history/link-inside-not.html
> +        :not(:visited)
> +            fast/history/visited-inside-not.html
> +        :-webkit-any(:link)
> +            fast/history/link-inside-any.html
> +        :-webkit-any(:visited)
> +            fast/history/visited-inside-any.html

Mentioning this in the changelog is absolutely awesome, I wish more authors did that.

> Source/WebCore/cssjit/SelectorCompiler.cpp:616
> +            // And when :visited is inside :not (:not(:visited)), it returns CannotMatchAnything and it always passes this filter.

This comment is not necessary, the explanation in PseudoClassVisited is enough.

> Source/WebCore/cssjit/SelectorCompiler.cpp:630
> +                ASSERT_WITH_MESSAGE(selectorContext != SelectorContext::QuerySelector, "When visitedMatchEnabled is true, selector context is never QuerySelector.");

The message repeats the condition IMHO. Maybe: "QuerySelector should never match :visited link because it would be a privacy issue." or something like that?

> Source/WebCore/cssjit/SelectorCompiler.cpp:723
> +    bool visitedMatchEnabled = true;
> +    if (selectorContext == SelectorContext::QuerySelector)
> +        visitedMatchEnabled = false;

Could be:
bool visitedMatchEnabled = selectorContext != SelectorContext::QuerySelector;

> Source/WebCore/cssjit/SelectorCompiler.cpp:1431
> +    // Remember the stack base of the temporary variables.

This comment is superfluous, the code below is clear.

> Source/WebCore/cssjit/SelectorCompiler.cpp:1460
> +    // Invalidate temporaryStackBase if there's no temporary variables.
> +    if (temporaryStackBase == m_stackAllocator.stackTop())
> +        temporaryStackBase = StackAllocator::StackReference();

Instead of this, couldn't we check "temporaryStackBase == m_stackAllocator.stackTop()" instead of temporaryStackBase.isValid() when discarding the stack?

> Source/WebCore/cssjit/SelectorCompiler.cpp:1558
> +void SelectorCodeGenerator::generateRightmostTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
> +{
> +    generateElementMatching(failureCases, failureCases, fragment);
> +}
> +

Why do you need this?

[Yusuke Suzuki]

Committed r174142: <http://trac.webkit.org/changeset/174142>

[Yusuke Suzuki]

Comment on attachment 238719 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=238719&action=review

Thank you for your detailed review. And your idea is quite coooooooool! I've missed the point. By leveraging your idea, we can implement this much simpler!!

:not(:link) behaves like the following

+ When the visited matche is enabled, always pass
+ Otherwise, :not(:any-link)

In the current implementation, :visited check is deferred until the matching is finished. So even if the fragment inside :not has PseudoClassVisited, it doesn't cause :not(visited match enabled) behavior. This completely matches to the behavior of :not(:link).

I'll upload the revised patch!

>> Source/WebCore/ChangeLog:8
>> +        This patch implements CSS JIT for :visited. And maake :not(:link) JIT-ed.
> 
> Typo: maake

oops, thx!

>> Source/WebCore/cssjit/SelectorCompiler.cpp:616
>> +            // And when :visited is inside :not (:not(:visited)), it returns CannotMatchAnything and it always passes this filter.
> 
> This comment is not necessary, the explanation in PseudoClassVisited is enough.

ok I'll remove it.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:630
>> +                ASSERT_WITH_MESSAGE(selectorContext != SelectorContext::QuerySelector, "When visitedMatchEnabled is true, selector context is never QuerySelector.");
> 
> The message repeats the condition IMHO. Maybe: "QuerySelector should never match :visited link because it would be a privacy issue." or something like that?

Sounds nice! I'll replace it with your suggestion.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:723
>> +        visitedMatchEnabled = false;
> 
> Could be:
> bool visitedMatchEnabled = selectorContext != SelectorContext::QuerySelector;

done.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:1431
>> +    // Remember the stack base of the temporary variables.
> 
> This comment is superfluous, the code below is clear.

Removed.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:1460
>> +        temporaryStackBase = StackAllocator::StackReference();
> 
> Instead of this, couldn't we check "temporaryStackBase == m_stackAllocator.stackTop()" instead of temporaryStackBase.isValid() when discarding the stack?

Your suggestion is nice. Agreed, `temporaryStackBase == m_stackAllocator.stackTop()` clearly states the meaning of the code.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:1558
>> +
> 
> Why do you need this?

I added it to maintain the one on one corresponding between the methods and combinators.

Rightmost => generateRightmostTreeWalker
Descendant => generateAncestorTreeWalker
Child => generateParentElementTreeWalker
DirectAdjacent => generateDirectAdjacentTreeWalker
IndirectAdjacent => generateIndirectAdjacentTreeWalker


Is it preferable to use generateElementMatching directly?

[Yusuke Suzuki]

Comment on attachment 238719 [details]
Patch

Ah, oops.

In the following example,

*:not(link)

it matches the following <a>

<a href='xxx'>toplevel</a>

since visited match type is enabled.
To find it, when the :link is matched (normal :not failed), we need to pass the filter with storing the element as the last visited element.
It requires additional non-generic path in the :not.

And there's another edge case, `:-webkit-any(:not(:link), a) a` and the tree

<a>
  <a target></a>
</a>

If we choose :not(:link) as matched and storing it to the last visited element, the selector will fail since the last visited element is not the first encountered link.
However, if we choose a in the any's choices, the selector will succeed.
So to solve this, we should check whether it is the first encountered link when :not(:link) is used.

[Yusuke Suzuki]

Created attachment 239050 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 239050 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=239050&action=review

I've updated the patch.
Because of :-webkit-any(:not(:link)), the non-generic path is required in the :not filter check.

> Source/WebCore/cssjit/SelectorCompiler.cpp:3153
> +        }

To cover :-webkit-any(:not(:link)) case, we need to check whether the element is the first encountered link.
This check is needed only when the :not filter predicate passes (so, the whole filter failed).

And there's some room for optimization. The immediate check is only needed in the case of :-webkit-any(:not(:link)).
So in the normal cases (:not(:link)), we can leverage :visited check system; Inserting

if (:not(:link) and not inside :-webkit-any) {
    generateStoreLastVisitedElement(elementAddressRegister);
    localFailureCases.append(m_assembler.jump())
}

But it brings some more complexity. What do you think? I think it depends on whether :not(:link) is popular or not.

> LayoutTests/ChangeLog:9
> +        * fast/history/link-inside-not-inside-any.html: Added.

Added new tests for :-webkit-any(:not(:link)).
:not(:-webkit-any(:link)) is syntax error.

[Benjamin Poulain]

(In reply to comment #17)
> (From update of attachment 238719 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=238719&action=review
> 
> Thank you for your detailed review. And your idea is quite coooooooool! I've missed the point. By leveraging your idea, we can implement this much simpler!!
> 
> :not(:link) behaves like the following
> 
> + When the visited matche is enabled, always pass
> + Otherwise, :not(:any-link)
> 
> In the current implementation, :visited check is deferred until the matching is finished. So even if the fragment inside :not has PseudoClassVisited, it doesn't cause :not(visited match enabled) behavior. This completely matches to the behavior of :not(:link).

Rather:

:not(:link) would be:
-adding :visited to the parent selector if visited matching is enabled.
-always failing otherwise.

:not(:visited) would be:
-always passing in all cases.

The problem is the new :not() and :matches() but that is something we can deal with later.

[Benjamin Poulain]

(In reply to comment #21)
> (In reply to comment #17)
> > (From update of attachment 238719 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=238719&action=review
> > 
> > Thank you for your detailed review. And your idea is quite coooooooool! I've missed the point. By leveraging your idea, we can implement this much simpler!!
> > 
> > :not(:link) behaves like the following
> > 
> > + When the visited matche is enabled, always pass
> > + Otherwise, :not(:any-link)
> > 
> > In the current implementation, :visited check is deferred until the matching is finished. So even if the fragment inside :not has PseudoClassVisited, it doesn't cause :not(visited match enabled) behavior. This completely matches to the behavior of :not(:link).
> 
> Rather:
> 
> :not(:link) would be:
> -adding :visited to the parent selector if visited matching is enabled.
> -always failing otherwise.
> 
> :not(:visited) would be:
> -always passing in all cases.
> 
> The problem is the new :not() and :matches() but that is something we can deal with later.

Ok, reading your next comments explained everything...

Reading the edge cases, I am in favor of dropping :visited, and make :link a synonym of :any-link for any functional pseudo class.

The short term future is :matches() and :not() taking selector list. Those are critical use case to improve CSS. Since we do not have a clear path forward for :link and :visited in those, I am in favor of deferring the problem.

If you feel strongly about :not(:visited) and :not(:link), I'll review your latest patch. Otherwise let's cut the complexity.

[Yusuke Suzuki]

(In reply to comment #22)
> 
> Ok, reading your next comments explained everything...
> 
> Reading the edge cases, I am in favor of dropping :visited, and make :link a synonym of :any-link for any functional pseudo class.
> 
> The short term future is :matches() and :not() taking selector list. Those are critical use case to improve CSS. Since we do not have a clear path forward for :link and :visited in those, I am in favor of deferring the problem.
> 
> If you feel strongly about :not(:visited) and :not(:link), I'll review your latest patch. Otherwise let's cut the complexity.

Thanks for your comment.
Does dropping :visited mean deferring implementing/considering the complex semantics of :visited/:link with functional pseudo classes and taking the simple way, correct?

+ :not(:visited) accepts all, and :-webkit-any(:visited) rejects all.
+ :link becomes :-any-link inside the functional pseudo classes
If so, agree with you :)

[Benjamin Poulain]

(In reply to comment #23)
> (In reply to comment #22)
> > 
> > Ok, reading your next comments explained everything...
> > 
> > Reading the edge cases, I am in favor of dropping :visited, and make :link a synonym of :any-link for any functional pseudo class.
> > 
> > The short term future is :matches() and :not() taking selector list. Those are critical use case to improve CSS. Since we do not have a clear path forward for :link and :visited in those, I am in favor of deferring the problem.
> > 
> > If you feel strongly about :not(:visited) and :not(:link), I'll review your latest patch. Otherwise let's cut the complexity.
> 
> Thanks for your comment.
> Does dropping :visited mean deferring implementing/considering the complex semantics of :visited/:link with functional pseudo classes and taking the simple way, correct?
> 
> + :not(:visited) accepts all, and :-webkit-any(:visited) rejects all.

That sounds good. We assume ":visited" always fail in those cases.

> + :link becomes :-any-link inside the functional pseudo classes
> If so, agree with you :)

That sounds good too.

[Yusuke Suzuki]

Created attachment 239709 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 239709 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=239709&action=review

Sorry for the further late reply. I've updated the patch for the latest CSS JIT :)

> Source/WebCore/css/SelectorChecker.cpp:549
> +                    if (subcontext.selector->pseudoClassType() == CSSSelector::PseudoClassVisited)

Drop `:not(:link))` special path. Simplify it for further selectors extensions.

> Source/WebCore/cssjit/SelectorCompiler.cpp:629
> +                    ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");

When the fragment level is `InFunctionalPseudoType`, :visited doesn't require any :visited checks.
As the result, the visited mode of the sub fragments always becomes VisitedMode::None.

> Source/WebCore/cssjit/SelectorCompiler.cpp:666
> +            ASSERT_WITH_MESSAGE(ignoreVisitedMode == VisitedMode::None, ":visited is disabled in the functional pseudo classes");

ditto

> Source/WebCore/cssjit/SelectorCompiler.cpp:-652
> -                return FunctionType::CannotCompile;

Drop the :not(:link) restrictions.

> Source/WebCore/cssjit/SelectorCompiler.cpp:1042
> +        rootBacktrackingMemoryRequirement.stackCount += 2;

When the visited mode is Visited, we allocate 2 more stack references in the root fragment.
In the current simplified semantics, visited is only effective on the root fragments.

[Benjamin Poulain]

Comment on attachment 239709 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=239709&action=review

Looks good to me. Sorry I changed my mind so many time on the processing of :visited. Thanks for keeping up with the updates.

It believe we should revisit our options after :matches() is implemented, including multiple matching.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:1042
>> +    // Allocate the stack references for the last visited element and the start element.
>> +    if (visitedMode == VisitedMode::Visited)
>> +        rootBacktrackingMemoryRequirement.stackCount += 2;
> 
> When the visited mode is Visited, we allocate 2 more stack references in the root fragment.
> In the current simplified semantics, visited is only effective on the root fragments.

I would put this branch outside computeBacktrackingMemoryRequirements().

Those two registers are unaffected by backtracking. Having the check in generateSelectorChecker() would also put the branch in the same scope where the stack references are assigned.

> Source/WebCore/cssjit/SelectorCompiler.cpp:1561
> +    if (m_visitedMode == VisitedMode::Visited) {
> +        m_lastVisitedElement = m_backtrackingStack.takeLast();
> +        m_startElement = m_backtrackingStack.takeLast();
> +        unsigned offsetToStartElement = m_stackAllocator.offsetToStackReference(m_startElement);
> +        m_assembler.storePtr(elementAddressRegister, Assembler::Address(Assembler::stackPointerRegister, offsetToStartElement));
> +        unsigned offsetToLastVisitedElement = m_stackAllocator.offsetToStackReference(m_lastVisitedElement);
> +        m_assembler.storePtr(Assembler::TrustedImmPtr(nullptr), Assembler::Address(Assembler::stackPointerRegister, offsetToLastVisitedElement));
> +    }
> +

I would prefer this allocation to be more explicit.

First, allocate allocateUninitialized(). Then take two out of the vector for :visited. The assign the remaining vector to m_backtrackingStack.

> LayoutTests/TestExpectations:221
> -fast/history/link-inside-not.html [ Failure ]
> +# fast/history/link-inside-not.html [ Failure ]

Let's remove those lines entirely.

[Yusuke Suzuki]

Comment on attachment 239709 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=239709&action=review

No problem :) Your review is so helpful. Sorry for my late reply since I needed to implement my research project code...

> It believe we should revisit our options after :matches() is implemented, including multiple matching.

Yup

>>> Source/WebCore/cssjit/SelectorCompiler.cpp:1042
>>> +        rootBacktrackingMemoryRequirement.stackCount += 2;
>> 
>> When the visited mode is Visited, we allocate 2 more stack references in the root fragment.
>> In the current simplified semantics, visited is only effective on the root fragments.
> 
> I would put this branch outside computeBacktrackingMemoryRequirements().
> 
> Those two registers are unaffected by backtracking. Having the check in generateSelectorChecker() would also put the branch in the same scope where the stack references are assigned.

OK, that sounds nice.
I've put this in generateSelectorChecker, it's near to the use of :visited's stack reference allocation code.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:1561
>> +
> 
> I would prefer this allocation to be more explicit.
> 
> First, allocate allocateUninitialized(). Then take two out of the vector for :visited. The assign the remaining vector to m_backtrackingStack.

It looks very nice to me.
So creating the variable, `temporaryStack`, allocating the stack references as this vector, taking 2 reference out of it and assigns the remaining vector to m_backtrackingStack. It makes the code clear.

>> LayoutTests/TestExpectations:221
>> +# fast/history/link-inside-not.html [ Failure ]
> 
> Let's remove those lines entirely.

done :)

[Yusuke Suzuki]

Committed r174663: <http://trac.webkit.org/changeset/174663>