static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector>& parentMatrix, bool mayContainAttributeNodes)
{
    // Should not call this function with less that two nodes to sort.
    ASSERT(from + 1 < to);
    unsigned minDepth = UINT_MAX;
    for (unsigned i = from; i < to; ++i) {
        unsigned depth = parentMatrix[i].size() - 1;
        if (minDepth > depth)
            minDepth = depth;
    }

    // Find the common ancestor.
    unsigned commonAncestorDepth = minDepth;
    Node* commonAncestor;
    while (true) {
        commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);
        if (commonAncestorDepth == 0)
            break;

        bool allEqual = true;
        for (unsigned i = from + 1; i < to; ++i) {
            if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {
                allEqual = false;
                break;
            }
        }
        if (allEqual)
            break;

        --commonAncestorDepth;
    }

    if (commonAncestorDepth == minDepth) {
        // One of the nodes is the common ancestor => it is the first in
        // document order. Find it and move it to the beginning.
        for (unsigned i = from; i < to; ++i) {
            if (commonAncestor == parentMatrix[i][0]) {
                parentMatrix[i].swap(parentMatrix[from]);
                if (from + 2 < to)
                    sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);
                return;
            }
        }
    }

    if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
        // The attribute nodes and namespace nodes of an element occur before
        // the children of the element. The namespace nodes are defined to occur
        // before the attribute nodes. The relative order of namespace nodes is
        // implementation-dependent. The relative order of attribute nodes is
        // implementation-dependent.
        unsigned sortedEnd = from;
        // FIXME: namespace nodes are not implemented.
        for (unsigned i = sortedEnd; i < to; ++i) {
            Node* n = parentMatrix[i][0];
            if (n->isAttributeNode() && toAttr(n)->ownerElement() == commonAncestor)
                parentMatrix[i].swap(parentMatrix[sortedEnd++]);
        }
        if (sortedEnd != from) {
            if (to - sortedEnd > 1)
                sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);
            return;
        }
    }

    // Children nodes of the common ancestor induce a subdivision of our
    // node-set. Sort it according to this subdivision, and recursively sort
    // each group.
    WillBeHeapHashSet<RawPtrWillBeMember<Node> > parentNodes;
    for (unsigned i = from; i < to; ++i)
        parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));

    unsigned previousGroupEnd = from;
    unsigned groupEnd = from;
    for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
        // If parentNodes contains the node, perform a linear search to move its
        // children in the node-set to the beginning.
        if (parentNodes.contains(n)) {
            for (unsigned i = groupEnd; i < to; ++i) {
                if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
                    parentMatrix[i].swap(parentMatrix[groupEnd++]);
            }

            if (groupEnd - previousGroupEnd > 1)
                sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);

            ASSERT(previousGroupEnd != groupEnd);
            previousGroupEnd = groupEnd;
#ifndef NDEBUG
            parentNodes.remove(n);
#endif
        }
    }

    ASSERT(parentNodes.isEmpty());
}

void TableSectionPainter::paintObject(const PaintInfo& paintInfo, const LayoutPoint& paintOffset)
{
    LayoutRect localPaintInvalidationRect = paintInfo.rect;
    localPaintInvalidationRect.moveBy(-paintOffset);

    LayoutRect tableAlignedRect = m_renderTableSection.logicalRectForWritingModeAndDirection(localPaintInvalidationRect);

    CellSpan dirtiedRows = m_renderTableSection.dirtiedRows(tableAlignedRect);
    CellSpan dirtiedColumns = m_renderTableSection.dirtiedColumns(tableAlignedRect);

    WillBeHeapHashSet<RawPtrWillBeMember<RenderTableCell> > overflowingCells = m_renderTableSection.overflowingCells();
    if (dirtiedColumns.start() < dirtiedColumns.end()) {
        if (!m_renderTableSection.hasMultipleCellLevels() && !overflowingCells.size()) {
            if (paintInfo.phase == PaintPhaseCollapsedTableBorders) {
                // Collapsed borders are painted from the bottom right to the top left so that precedence
                // due to cell position is respected.
                for (unsigned r = dirtiedRows.end(); r > dirtiedRows.start(); r--) {
                    unsigned row = r - 1;
                    for (unsigned c = dirtiedColumns.end(); c > dirtiedColumns.start(); c--) {
                        unsigned col = c - 1;
                        RenderTableSection::CellStruct& current = m_renderTableSection.cellAt(row, col);
                        RenderTableCell* cell = current.primaryCell();
                        if (!cell || (row > dirtiedRows.start() && m_renderTableSection.primaryCellAt(row - 1, col) == cell) || (col > dirtiedColumns.start() && m_renderTableSection.primaryCellAt(row, col - 1) == cell))
                            continue;
                        LayoutPoint cellPoint = m_renderTableSection.flipForWritingModeForChild(cell, paintOffset);
                        TableCellPainter(*cell).paintCollapsedBorders(paintInfo, cellPoint);
                    }
                }
            } else {
                // Draw the dirty cells in the order that they appear.
                for (unsigned r = dirtiedRows.start(); r < dirtiedRows.end(); r++) {
                    RenderTableRow* row = m_renderTableSection.rowRendererAt(r);
                    if (row && !row->hasSelfPaintingLayer())
                        TableRowPainter(*row).paintOutlineForRowIfNeeded(paintInfo, paintOffset);
                    for (unsigned c = dirtiedColumns.start(); c < dirtiedColumns.end(); c++) {
                        RenderTableSection::CellStruct& current = m_renderTableSection.cellAt(r, c);
                        RenderTableCell* cell = current.primaryCell();
                        if (!cell || (r > dirtiedRows.start() && m_renderTableSection.primaryCellAt(r - 1, c) == cell) || (c > dirtiedColumns.start() && m_renderTableSection.primaryCellAt(r, c - 1) == cell))
                            continue;
                        paintCell(cell, paintInfo, paintOffset);
                    }
                }
            }
        } else {
            // The overflowing cells should be scarce to avoid adding a lot of cells to the HashSet.
#if ENABLE(ASSERT)
            unsigned totalRows = m_renderTableSection.numRows();
            unsigned totalCols = m_renderTableSection.table()->columns().size();
            ASSERT(overflowingCells.size() < totalRows * totalCols * gMaxAllowedOverflowingCellRatioForFastPaintPath);
#endif

            // To make sure we properly paint invalidate the section, we paint invalidated all the overflowing cells that we collected.
            Vector<RenderTableCell*> cells;
            copyToVector(overflowingCells, cells);

            HashSet<RenderTableCell*> spanningCells;

            for (unsigned r = dirtiedRows.start(); r < dirtiedRows.end(); r++) {
                RenderTableRow* row = m_renderTableSection.rowRendererAt(r);
                if (row && !row->hasSelfPaintingLayer())
                    TableRowPainter(*row).paintOutlineForRowIfNeeded(paintInfo, paintOffset);
                for (unsigned c = dirtiedColumns.start(); c < dirtiedColumns.end(); c++) {
                    RenderTableSection::CellStruct& current = m_renderTableSection.cellAt(r, c);
                    if (!current.hasCells())
                        continue;
                    for (unsigned i = 0; i < current.cells.size(); ++i) {
                        if (overflowingCells.contains(current.cells[i]))
                            continue;

                        if (current.cells[i]->rowSpan() > 1 || current.cells[i]->colSpan() > 1) {
                            if (!spanningCells.add(current.cells[i]).isNewEntry)
                                continue;
                        }

                        cells.append(current.cells[i]);
                    }
                }
            }

            // Sort the dirty cells by paint order.
            if (!overflowingCells.size())
                std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
            else
                std::sort(cells.begin(), cells.end(), compareCellPositionsWithOverflowingCells);

            if (paintInfo.phase == PaintPhaseCollapsedTableBorders) {
                for (unsigned i = cells.size(); i > 0; --i) {
                    LayoutPoint cellPoint = m_renderTableSection.flipForWritingModeForChild(cells[i - 1], paintOffset);
                    TableCellPainter(*cells[i - 1]).paintCollapsedBorders(paintInfo, cellPoint);
                }
            } else {
                for (unsigned i = 0; i < cells.size(); ++i)
                    paintCell(cells[i], paintInfo, paintOffset);
            }
        }
    }
}

SMILTime SMILTimeContainer::updateAnimations(SMILTime elapsed, bool seekToTime)
{
    SMILTime earliestFireTime = SMILTime::unresolved();

#if ENABLE(ASSERT)
    // This boolean will catch any attempts to schedule/unschedule scheduledAnimations during this critical section.
    // Similarly, any elements removed will unschedule themselves, so this will catch modification of animationsToApply.
    m_preventScheduledAnimationsChanges = true;
#endif

    if (m_documentOrderIndexesDirty)
        updateDocumentOrderIndexes();

    WillBeHeapHashSet<ElementAttributePair> invalidKeys;
    using AnimationsVector = WillBeHeapVector<RefPtrWillBeMember<SVGSMILElement>>;
    AnimationsVector animationsToApply;
    for (const auto& entry : m_scheduledAnimations) {
        if (!entry.key.first || entry.value->isEmpty()) {
            invalidKeys.add(entry.key);
            continue;
        }

        AnimationsLinkedHashSet* scheduled = entry.value.get();

        // Sort according to priority. Elements with later begin time have higher priority.
        // In case of a tie, document order decides.
        // FIXME: This should also consider timing relationships between the elements. Dependents
        // have higher priority.
        AnimationsVector scheduledAnimations;
        copyToVector(*scheduled, scheduledAnimations);
        std::sort(scheduledAnimations.begin(), scheduledAnimations.end(), PriorityCompare(elapsed));

        SVGSMILElement* resultElement = nullptr;
        for (const auto& itAnimation : scheduledAnimations) {
            SVGSMILElement* animation = itAnimation.get();
            ASSERT(animation->timeContainer() == this);
            ASSERT(animation->targetElement());
            ASSERT(animation->hasValidAttributeName());

            // Results are accumulated to the first animation that animates and contributes to a particular element/attribute pair.
            // FIXME: we should ensure that resultElement is of an appropriate type.
            if (!resultElement) {
                if (!animation->hasValidAttributeType())
                    continue;
                resultElement = animation;
            }

            // This will calculate the contribution from the animation and add it to the resultsElement.
            if (!animation->progress(elapsed, resultElement, seekToTime) && resultElement == animation)
                resultElement = nullptr;

            SMILTime nextFireTime = animation->nextProgressTime();
            if (nextFireTime.isFinite())
                earliestFireTime = std::min(nextFireTime, earliestFireTime);
        }

        if (resultElement)
            animationsToApply.append(resultElement);
    }
    m_scheduledAnimations.removeAll(invalidKeys);

    std::sort(animationsToApply.begin(), animationsToApply.end(), PriorityCompare(elapsed));

    unsigned animationsToApplySize = animationsToApply.size();
    if (!animationsToApplySize) {
#if ENABLE(ASSERT)
        m_preventScheduledAnimationsChanges = false;
#endif
        return earliestFireTime;
    }

    // Apply results to target elements.
    for (unsigned i = 0; i < animationsToApplySize; ++i)
        animationsToApply[i]->applyResultsToTarget();

#if ENABLE(ASSERT)
    m_preventScheduledAnimationsChanges = false;
#endif

    for (unsigned i = 0; i < animationsToApplySize; ++i) {
        if (animationsToApply[i]->inDocument() && animationsToApply[i]->isSVGDiscardElement()) {
            RefPtrWillBeRawPtr<SVGSMILElement> animDiscard = animationsToApply[i];
            RefPtrWillBeRawPtr<SVGElement> targetElement = animDiscard->targetElement();
            if (targetElement && targetElement->inDocument()) {
                targetElement->remove(IGNORE_EXCEPTION);
                ASSERT(!targetElement->inDocument());
            }

            if (animDiscard->inDocument()) {
                animDiscard->remove(IGNORE_EXCEPTION);
                ASSERT(!animDiscard->inDocument());
            }
        }
    }
    return earliestFireTime;
}

bool RadioButtonGroup::contains(HTMLInputElement* button) const
{
    return m_members.contains(button);
}