Changeset 167920 in webkit


Ignore:
Timestamp:
Apr 28, 2014 6:58:38 PM (10 years ago)
Author:
commit-queue@webkit.org
Message:

CSS JIT: backtracking with current / parent element for child
​https://bugs.webkit.org/show_bug.cgi?id=132057

Patch by Yusuke Suzuki <Yusuke Suzuki> on 2014-04-28
Reviewed by Benjamin Poulain.

Calculate appropriate backtracking start height from the closest
descendant. And at first, we use it for a simple optimization.

  1. When backtracking start height equals to current height, we

can simply jump to a descendant element check phase.

  1. When backtracking start height equals to current height + 1, we

can simply jump to a descendant element traversing phase.

We can apply this optimization to fragments with adjacent combinators.
But, in the meantime, we start to implement it for a fragment with
child combinator.

Source/WebCore:

  • cssjit/SelectorCompiler.cpp:

(WebCore::SelectorCompiler::SelectorFragment::SelectorFragment):
(WebCore::SelectorCompiler::TagNamePattern::TagNamePattern):
(WebCore::SelectorCompiler::solveDescendantBacktrackingActionForChild):
(WebCore::SelectorCompiler::solveBacktrackingAction):
(WebCore::SelectorCompiler::equalTagNames):
(WebCore::SelectorCompiler::equalTagNamePatterns):
(WebCore::SelectorCompiler::computeBacktrackingStartHeightFromDescendant):
(WebCore::SelectorCompiler::computeBacktrackingHeightFromDescendant):
(WebCore::SelectorCompiler::requiresAdjacentTail):
(WebCore::SelectorCompiler::requiresDescendantTail):
(WebCore::SelectorCompiler::SelectorCodeGenerator::computeBacktrackingInformation):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateSelectorChecker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentNode):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentElement):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateParentElementTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateAncestorTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateDirectAdjacentTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateIndirectAdjacentTreeWalker):
(WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):

LayoutTests:

  • fast/selectors/backtracking-child-combinator-with-tail-expected.txt: Added.
  • fast/selectors/backtracking-child-combinator-with-tail.html: Added.
  • fast/selectors/backtracking-child-combinator-without-tail-expected.txt: Added.
  • fast/selectors/backtracking-child-combinator-without-tail.html: Added.
Location:
trunk
Files:
4 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r167915 r167920  
     12014-04-28  Yusuke Suzuki  <utatane.tea@gmail.com>
     2
     3        CSS JIT: backtracking with current / parent element for child
     4        https://bugs.webkit.org/show_bug.cgi?id=132057
     5
     6        Reviewed by Benjamin Poulain.
     7
     8        Calculate appropriate backtracking start height from the closest
     9        descendant. And at first, we use it for a simple optimization.
     10
     11        1. When backtracking start height equals to current height, we
     12        can simply jump to a descendant element check phase.
     13        2. When backtracking start height equals to current height + 1, we
     14        can simply jump to a descendant element traversing phase.
     15
     16        We can apply this optimization to fragments with adjacent combinators.
     17        But, in the meantime, we start to implement it for a fragment with
     18        child combinator.
     19
     20        * fast/selectors/backtracking-child-combinator-with-tail-expected.txt: Added.
     21        * fast/selectors/backtracking-child-combinator-with-tail.html: Added.
     22        * fast/selectors/backtracking-child-combinator-without-tail-expected.txt: Added.
     23        * fast/selectors/backtracking-child-combinator-without-tail.html: Added.
     24
    1252014-04-28  Ryuan Choi  <ryuan.choi@samsung.com>
    226

  • trunk/Source/WebCore/ChangeLog

    r167916 r167920  
     12014-04-28  Yusuke Suzuki  <utatane.tea@gmail.com>
     2
     3        CSS JIT: backtracking with current / parent element for child
     4        https://bugs.webkit.org/show_bug.cgi?id=132057
     5
     6        Reviewed by Benjamin Poulain.
     7
     8        Calculate appropriate backtracking start height from the closest
     9        descendant. And at first, we use it for a simple optimization.
     10
     11        1. When backtracking start height equals to current height, we
     12        can simply jump to a descendant element check phase.
     13        2. When backtracking start height equals to current height + 1, we
     14        can simply jump to a descendant element traversing phase.
     15
     16        We can apply this optimization to fragments with adjacent combinators.
     17        But, in the meantime, we start to implement it for a fragment with
     18        child combinator.
     19
     20        * cssjit/SelectorCompiler.cpp:
     21        (WebCore::SelectorCompiler::SelectorFragment::SelectorFragment):
     22        (WebCore::SelectorCompiler::TagNamePattern::TagNamePattern):
     23        (WebCore::SelectorCompiler::solveDescendantBacktrackingActionForChild):
     24        (WebCore::SelectorCompiler::solveBacktrackingAction):
     25        (WebCore::SelectorCompiler::equalTagNames):
     26        (WebCore::SelectorCompiler::equalTagNamePatterns):
     27        (WebCore::SelectorCompiler::computeBacktrackingStartHeightFromDescendant):
     28        (WebCore::SelectorCompiler::computeBacktrackingHeightFromDescendant):
     29        (WebCore::SelectorCompiler::requiresAdjacentTail):
     30        (WebCore::SelectorCompiler::requiresDescendantTail):
     31        (WebCore::SelectorCompiler::SelectorCodeGenerator::computeBacktrackingInformation):
     32        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateSelectorChecker):
     33        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentNode):
     34        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateWalkToParentElement):
     35        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateParentElementTreeWalker):
     36        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateAncestorTreeWalker):
     37        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateDirectAdjacentTreeWalker):
     38        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateIndirectAdjacentTreeWalker):
     39        (WebCore::SelectorCompiler::SelectorCodeGenerator::generateElementMatching):
     40
    1412014-04-28  Benjamin Poulain  <bpoulain@apple.com>
    242

  • trunk/Source/WebCore/cssjit/SelectorCompiler.cpp

    r167585 r167920  
    11/*
    22 * Copyright (C) 2013, 2014 Apple Inc. All rights reserved.
     3 * Copyright (C) 2014 Yusuke Suzuki <utatane.tea@gmail.com>
    34 *
    45 * Redistribution and use in source and binary forms, with or without
    … …  
    4849#include <JavaScriptCore/MacroAssembler.h>
    4950#include <JavaScriptCore/VM.h>
     51#include <limits>
    5052#include <wtf/HashMap.h>
    5153#include <wtf/HashSet.h>
    … …  
    111113};
    112114
     115static const unsigned invalidHeight = std::numeric_limits<unsigned>::max();
     116
    113117struct SelectorFragment {
    114118    SelectorFragment()
    115119        : traversalBacktrackingAction(BacktrackingAction::NoBacktracking)
    116         , matchingBacktrackingAction(BacktrackingAction::NoBacktracking)
     120        , matchingTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
     121        , matchingPostTagNameBacktrackingAction(BacktrackingAction::NoBacktracking)
    117122        , backtrackingFlags(0)
     123        , tagNameMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
     124        , tagNameNotMatchedBacktrackingStartHeightFromDescendant(invalidHeight)
     125        , heightFromDescendant(0)
    118126        , tagName(nullptr)
    119127        , id(nullptr)
    … …  
    124132
    125133    BacktrackingAction traversalBacktrackingAction;
    126     BacktrackingAction matchingBacktrackingAction;
     134    BacktrackingAction matchingTagNameBacktrackingAction;
     135    BacktrackingAction matchingPostTagNameBacktrackingAction;
    127136    unsigned char backtrackingFlags;
     137    unsigned tagNameMatchedBacktrackingStartHeightFromDescendant;
     138    unsigned tagNameNotMatchedBacktrackingStartHeightFromDescendant;
     139    unsigned heightFromDescendant;
    128140
    129141    const QualifiedName* tagName;
    … …  
    136148};
    137149
     150struct TagNamePattern {
     151    TagNamePattern()
     152        : tagName(nullptr)
     153        , inverted(false)
     154    {
     155    }
     156    const QualifiedName* tagName;
     157    bool inverted;
     158};
     159
    138160typedef JSC::MacroAssembler Assembler;
    139161typedef Vector<SelectorFragment, 8> SelectorFragmentList;
     162typedef Vector<TagNamePattern, 8> TagNameList;
    140163
    141164class SelectorCodeGenerator {
    … …  
    153176
    154177    // Element relations tree walker.
     178    void generateWalkToParentNode(Assembler::RegisterID targetRegister);
    155179    void generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister);
    156180    void generateParentElementTreeWalker(Assembler::JumpList& failureCases, const SelectorFragment&);
    … …  
    171195
    172196    // Element properties matchers.
    173     void generateElementMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
     197    void generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment&);
    174198    void generateElementDataMatching(Assembler::JumpList& failureCases, const SelectorFragment&);
    175199    void generateElementFunctionCallTest(Assembler::JumpList& failureCases, JSC::FunctionPtr);
    … …  
    574598}
    575599
     600static BacktrackingAction solveDescendantBacktrackingActionForChild(const SelectorFragment& fragment, unsigned backtrackingStartHeightFromDescendant)
     601{
     602    // If height is invalid (e.g. There's no tag name).
     603    if (backtrackingStartHeightFromDescendant == invalidHeight)
     604        return BacktrackingAction::NoBacktracking;
     605
     606    // Start backtracking from the current element.
     607    if (backtrackingStartHeightFromDescendant == fragment.heightFromDescendant)
     608        return BacktrackingAction::JumpToDescendantEntryPoint;
     609
     610    // Start backtracking from the parent of current element.
     611    if (backtrackingStartHeightFromDescendant == (fragment.heightFromDescendant + 1))
     612        return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
     613
     614    return BacktrackingAction::JumpToDescendantTail;
     615}
     616
    576617static inline void solveBacktrackingAction(SelectorFragment& fragment, bool hasDescendantRelationOnTheRight, unsigned ancestorPositionSinceDescendantRelation, bool hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, unsigned adjacentPositionSinceIndirectAdjacentTreeWalk)
    577618{
    … …  
    583624        // Failure to match the element should resume matching at the nearest ancestor/descendant entry point.
    584625        if (hasDescendantRelationOnTheRight) {
    585             if (isFirstAncestor(ancestorPositionSinceDescendantRelation))
    586                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantEntryPoint;
    587             else
    588                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
     626            fragment.matchingTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant);
     627            fragment.matchingPostTagNameBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
    589628        }
    590629        break;
    … …  
    610649        // Otherwise, we resume from the latest ancestor/descendant if any.
    611650        if (hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain) {
    612             if (isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk))
    613                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
    614             else
    615                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
     651            if (isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
     652                fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
     653                fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToIndirectAdjacentEntryPoint;
     654            } else {
     655                fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
     656                fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDirectAdjacentTail;
     657            }
    616658        } else if (hasDescendantRelationOnTheRight) {
    617             if (isAfterChildRelation(ancestorPositionSinceDescendantRelation))
    618                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
    619             else
    620                 fragment.matchingBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
     659            if (isAfterChildRelation(ancestorPositionSinceDescendantRelation)) {
     660                fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
     661                fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTail;
     662            } else {
     663                fragment.matchingTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
     664                fragment.matchingPostTagNameBacktrackingAction = BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;
     665            }
    621666        }
    622667        break;
    … …  
    634679}
    635680
     681enum class TagNameEquality {
     682    StrictlyNotEqual,
     683    MaybeEqual,
     684    StrictlyEqual
     685};
     686
     687static inline TagNameEquality equalTagNames(const QualifiedName* lhs, const QualifiedName* rhs)
     688{
     689    if (!lhs || *lhs == anyQName())
     690        return TagNameEquality::MaybeEqual;
     691
     692    if (!rhs || *rhs == anyQName())
     693        return TagNameEquality::MaybeEqual;
     694
     695    ASSERT(lhs && rhs);
     696
     697    const AtomicString& lhsLocalName = lhs->localName();
     698    const AtomicString& rhsLocalName = rhs->localName();
     699    if (lhsLocalName != starAtom && rhsLocalName != starAtom) {
     700        if (lhsLocalName != rhsLocalName)
     701            return TagNameEquality::StrictlyNotEqual;
     702        return TagNameEquality::StrictlyEqual;
     703    }
     704
     705    const AtomicString& lhsNamespaceURI = lhs->namespaceURI();
     706    const AtomicString& rhsNamespaceURI = rhs->namespaceURI();
     707    if (lhsNamespaceURI != starAtom && rhsNamespaceURI != starAtom) {
     708        if (lhsNamespaceURI != rhsNamespaceURI)
     709            return TagNameEquality::StrictlyNotEqual;
     710        return TagNameEquality::StrictlyEqual;
     711    }
     712
     713    return TagNameEquality::MaybeEqual;
     714}
     715
     716static inline bool equalTagNamePatterns(const TagNamePattern& lhs, const QualifiedName* rhs)
     717{
     718    TagNameEquality result = equalTagNames(lhs.tagName, rhs);
     719    if (result == TagNameEquality::MaybeEqual)
     720        return true;
     721
     722    // If both rhs & lhs have actual localName (or NamespaceURI),
     723    // TagNameEquality result becomes StrictlyEqual or StrictlyNotEqual Since inverted lhs never matches on rhs.
     724    bool equal = result == TagNameEquality::StrictlyEqual;
     725    if (lhs.inverted)
     726        return !equal;
     727    return equal;
     728}
     729
     730// Find the largest matching prefix from already known tagNames.
     731// And by using this, compute an appropriate height of backtracking start element from the closest descendant.
     732static inline unsigned computeBacktrackingStartHeightFromDescendant(const TagNameList& tagNames)
     733{
     734    RELEASE_ASSERT(!tagNames.isEmpty());
     735
     736    unsigned largestPrefixSize = tagNames.size();
     737    while (--largestPrefixSize) {
     738        unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
     739        bool matched = true;
     740        // Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
     741        for (unsigned i = 0; i < largestPrefixSize; ++i) {
     742            unsigned lastIndex = tagNames.size() - 1;
     743            unsigned currentIndex = lastIndex - i;
     744            if (!equalTagNamePatterns(tagNames[currentIndex], tagNames[currentIndex - offsetToLargestPrefix].tagName)) {
     745                matched = false;
     746                break;
     747            }
     748        }
     749        if (matched)
     750            return offsetToLargestPrefix;
     751    }
     752    return tagNames.size();
     753}
     754
     755static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNames, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragmentInDescendantBacktrackingChain)
     756{
     757    if (!hasDescendantRelationOnTheRight)
     758        return;
     759
     760    if (fragment.relationToRightFragment == FragmentRelation::Descendant) {
     761        tagNames.clear();
     762
     763        TagNamePattern pattern;
     764        pattern.tagName = fragment.tagName;
     765        tagNames.append(pattern);
     766        fragment.heightFromDescendant = 0;
     767        previousChildFragmentInDescendantBacktrackingChain = nullptr;
     768    } else if (fragment.relationToRightFragment == FragmentRelation::Child) {
     769        TagNamePattern pattern;
     770        pattern.tagName = fragment.tagName;
     771        tagNames.append(pattern);
     772
     773        if (pattern.tagName) {
     774            // Compute height from descendant in the case that tagName is not matched.
     775            tagNames.last().inverted = true;
     776            fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames);
     777        }
     778
     779        // Compute height from descendant in the case that tagName is matched.
     780        tagNames.last().inverted = false;
     781        fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames);
     782        fragment.heightFromDescendant = tagNames.size() - 1;
     783        previousChildFragmentInDescendantBacktrackingChain = &fragment;
     784    } else {
     785        if (previousChildFragmentInDescendantBacktrackingChain) {
     786            fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInDescendantBacktrackingChain->tagNameNotMatchedBacktrackingStartHeightFromDescendant;
     787            fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = previousChildFragmentInDescendantBacktrackingChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
     788            fragment.heightFromDescendant = previousChildFragmentInDescendantBacktrackingChain->heightFromDescendant;
     789        } else {
     790            fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = tagNames.size();
     791            fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = tagNames.size();
     792            fragment.heightFromDescendant = 0;
     793        }
     794    }
     795}
     796
    636797static bool requiresAdjacentTail(const SelectorFragment& fragment)
    637798{
    638799    ASSERT(fragment.traversalBacktrackingAction != BacktrackingAction::JumpToDirectAdjacentTail);
    639     return fragment.matchingBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
     800    return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDirectAdjacentTail;
    640801}
    641802
    642803static bool requiresDescendantTail(const SelectorFragment& fragment)
    643804{
    644     return fragment.matchingBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
     805    return fragment.matchingTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.matchingPostTagNameBacktrackingAction == BacktrackingAction::JumpToDescendantTail || fragment.traversalBacktrackingAction == BacktrackingAction::JumpToDescendantTail;
    645806}
    646807
    … …  
    654815    bool needsAdjacentTail = false;
    655816    bool needsDescendantTail = false;
     817    unsigned saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
     818
     819    TagNameList tagNames;
     820    const SelectorFragment* previousChildFragmentInDescendantBacktrackingChain = nullptr;
    656821
    657822    for (unsigned i = 0; i < m_selectorFragments.size(); ++i) {
    … …  
    659824
    660825        updateChainStates(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
     826
     827        computeBacktrackingHeightFromDescendant(fragment, tagNames, hasDescendantRelationOnTheRight, previousChildFragmentInDescendantBacktrackingChain);
     828
     829#if CSS_SELECTOR_JIT_DEBUGGING
     830        dataLogF("Computing fragment[%d] backtracking height %u. NotMatched %u / Matched %u\n", i, fragment.heightFromDescendant, fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);
     831#endif
    661832
    662833        solveBacktrackingAction(fragment, hasDescendantRelationOnTheRight, ancestorPositionSinceDescendantRelation, hasIndirectAdjacentRelationOnTheRightOfDirectAdjacentChain, adjacentPositionSinceIndirectAdjacentTreeWalk);
    … …  
    673844        if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::IndirectAdjacent)
    674845            fragment.backtrackingFlags |= BacktrackingFlag::IndirectAdjacentEntryPoint;
    675         if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation))
    676             fragment.backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
     846        if (fragment.relationToLeftFragment != FragmentRelation::Descendant && fragment.relationToRightFragment == FragmentRelation::Child && isFirstAncestor(ancestorPositionSinceDescendantRelation)) {
     847            ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max());
     848            saveDescendantBacktrackingStartFragmentIndex = i;
     849        }
    677850        if (fragment.relationToLeftFragment == FragmentRelation::DirectAdjacent && fragment.relationToRightFragment == FragmentRelation::DirectAdjacent && isFirstAdjacent(adjacentPositionSinceIndirectAdjacentTreeWalk)) {
    678851            fragment.backtrackingFlags |= BacktrackingFlag::SaveAdjacentBacktrackingStart;
    … …  
    684857            needsAdjacentTail = false;
    685858        }
    686         if (fragment.relationToLeftFragment == FragmentRelation::Descendant && needsDescendantTail) {
    687             fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
    688             needsDescendantTail = false;
     859        if (fragment.relationToLeftFragment == FragmentRelation::Descendant) {
     860            if (needsDescendantTail) {
     861                ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max());
     862                fragment.backtrackingFlags |= BacktrackingFlag::DescendantTail;
     863                m_selectorFragments[saveDescendantBacktrackingStartFragmentIndex].backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
     864                needsDescendantTail = false;
     865                for (unsigned j = saveDescendantBacktrackingStartFragmentIndex; j <= i; ++j)
     866                    m_selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;
     867            }
     868            saveDescendantBacktrackingStartFragmentIndex = std::numeric_limits<unsigned>::max();
    689869        }
    690870    }
    … …  
    715895        switch (fragment.relationToRightFragment) {
    716896        case FragmentRelation::Rightmost:
    717             generateElementMatching(failureCases, fragment);
     897            generateElementMatching(failureCases, failureCases, fragment);
    718898            break;
    719899        case FragmentRelation::Descendant:
    … …  
    789969}
    790970
     971void SelectorCodeGenerator::generateWalkToParentNode(Assembler::RegisterID targetRegister)
     972{
     973    m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
     974}
     975
    791976void SelectorCodeGenerator::generateWalkToParentElement(Assembler::JumpList& failureCases, Assembler::RegisterID targetRegister)
    792977{
    … …  
    794979    //    if (!parent || !parent->isElementNode())
    795980    //         failure
    796     m_assembler.loadPtr(Assembler::Address(elementAddressRegister, Node::parentNodeMemoryOffset()), targetRegister);
     981    generateWalkToParentNode(targetRegister);
    797982    failureCases.append(m_assembler.branchTestPtr(Assembler::Zero, targetRegister));
    798983    failureCases.append(testIsElementFlagOnNode(Assembler::Zero, m_assembler, targetRegister));
    … …  
    805990    linkFailures(failureCases, fragment.traversalBacktrackingAction, traversalFailureCases);
    806991
    807     Assembler::JumpList matchingFailureCases;
    808     generateElementMatching(matchingFailureCases, fragment);
    809     linkFailures(failureCases, fragment.matchingBacktrackingAction, matchingFailureCases);
     992    Assembler::JumpList matchingTagNameFailureCases;
     993    Assembler::JumpList matchingPostTagNameFailureCases;
     994    generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
     995    linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
     996    linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
    810997
    811998    if (fragment.backtrackingFlags & BacktrackingFlag::SaveDescendantBacktrackingStart) {
    … …  
    8281015        m_descendantEntryPoint = m_assembler.label();
    8291016
    830     Assembler::JumpList tagMatchingLocalFailureCases;
    831     generateElementMatching(tagMatchingLocalFailureCases, fragment);
    832     tagMatchingLocalFailureCases.linkTo(loopStart, &m_assembler);
     1017    Assembler::JumpList matchingFailureCases;
     1018    generateElementMatching(matchingFailureCases, matchingFailureCases, fragment);
     1019    matchingFailureCases.linkTo(loopStart, &m_assembler);
    8331020}
    8341021
    … …  
    8851072    generateWalkToPreviousAdjacent(failureCases, fragment);
    8861073
    887     Assembler::JumpList matchingFailureCases;
    888     generateElementMatching(matchingFailureCases, fragment);
    889     linkFailures(failureCases, fragment.matchingBacktrackingAction, matchingFailureCases);
     1074    Assembler::JumpList matchingTagNameFailureCases;
     1075    Assembler::JumpList matchingPostTagNameFailureCases;
     1076    generateElementMatching(matchingTagNameFailureCases, matchingPostTagNameFailureCases, fragment);
     1077    linkFailures(failureCases, fragment.matchingTagNameBacktrackingAction, matchingTagNameFailureCases);
     1078    linkFailures(failureCases, fragment.matchingPostTagNameBacktrackingAction, matchingPostTagNameFailureCases);
    8901079
    8911080    if (fragment.backtrackingFlags & BacktrackingFlag::SaveAdjacentBacktrackingStart) {
    … …  
    9071096
    9081097    Assembler::JumpList localFailureCases;
    909     generateElementMatching(localFailureCases, fragment);
     1098    generateElementMatching(localFailureCases, localFailureCases, fragment);
    9101099    localFailureCases.linkTo(loopStart, &m_assembler);
    9111100}
    … …  
    11621351}
    11631352
    1164 void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& failureCases, const SelectorFragment& fragment)
    1165 {
     1353void SelectorCodeGenerator::generateElementMatching(Assembler::JumpList& matchingTagNameFailureCases, Assembler::JumpList& matchingPostTagNameFailureCases, const SelectorFragment& fragment)
     1354{
     1355    if (fragment.tagName)
     1356        generateElementHasTagName(matchingTagNameFailureCases, *(fragment.tagName));
     1357
    11661358    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLink))
    1167         generateElementIsLink(failureCases);
     1359        generateElementIsLink(matchingPostTagNameFailureCases);
    11681360
    11691361    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassRoot))
    1170         generateElementIsRoot(failureCases);
     1362        generateElementIsRoot(matchingPostTagNameFailureCases);
    11711363
    11721364    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassTarget))
    1173         generateElementIsTarget(failureCases);
    1174 
    1175     if (fragment.tagName)
    1176         generateElementHasTagName(failureCases, *(fragment.tagName));
     1365        generateElementIsTarget(matchingPostTagNameFailureCases);
    11771366
    11781367    for (unsigned i = 0; i < fragment.unoptimizedPseudoClasses.size(); ++i)
    1179         generateElementFunctionCallTest(failureCases, fragment.unoptimizedPseudoClasses[i]);
    1180 
    1181     generateElementDataMatching(failureCases, fragment);
     1368        generateElementFunctionCallTest(matchingPostTagNameFailureCases, fragment.unoptimizedPseudoClasses[i]);
     1369
     1370    generateElementDataMatching(matchingPostTagNameFailureCases, fragment);
    11821371
    11831372    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassOnlyChild))
    1184         generateElementIsOnlyChild(failureCases, fragment);
     1373        generateElementIsOnlyChild(matchingPostTagNameFailureCases, fragment);
    11851374    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassFirstChild))
    1186         generateElementIsFirstChild(failureCases, fragment);
     1375        generateElementIsFirstChild(matchingPostTagNameFailureCases, fragment);
    11871376    if (fragment.pseudoClasses.contains(CSSSelector::PseudoClassLastChild))
    1188         generateElementIsLastChild(failureCases, fragment);
     1377        generateElementIsLastChild(matchingPostTagNameFailureCases, fragment);
    11891378    if (!fragment.nthChildfilters.isEmpty())
    1190         generateElementIsNthChild(failureCases, fragment);
     1379        generateElementIsNthChild(matchingPostTagNameFailureCases, fragment);
    11911380}
    11921381
Note: See TracChangeset for help on using the changeset viewer.