Bug 207816 – Follow up element iterator work by reducing includes and using is<> in a few more places

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Darin Adler]

Revise DOM iterators implementation and usage

[Darin Adler]

Created attachment 390872 [details]
Patch

[Darin Adler]

Created attachment 390874 [details]
Patch

[Darin Adler]

Created attachment 390875 [details]
Patch

[Darin Adler]

Created attachment 390882 [details]
Patch

[Antti Koivisto]

It would also be nice to get rid of the clunky OfType suffix, though children<> might be too generic.

[Darin Adler]

(In reply to Antti Koivisto from comment #5)
> It would also be nice to get rid of the clunky OfType suffix, though
> children<> might be too generic.

I love that idea; I will explore it a bit.

[Darin Adler]

Created attachment 390890 [details]
Patch

[Darin Adler]

Created attachment 390902 [details]
Patch

[Darin Adler]

Created attachment 391132 [details]
Patch

[Darin Adler]

Created attachment 391250 [details]
Patch

[Darin Adler]

Created attachment 391253 [details]
Patch

[Darin Adler]

Created attachment 391374 [details]
Patch

[Darin Adler]

OK, all tests pass now so I’m ready to have someone review

[Antti Koivisto]

Comment on attachment 391374 [details]
Patch

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

> Source/WebCore/ChangeLog:97
> +        another even if the root element is not the same. Deleted ElementConstIterator.

Why? We'll lose a significant amount compile time checking against serious programming errors (allowing mutations of elements that are not supposed to be mutated in the context).

[Antti Koivisto]

Comment on attachment 391374 [details]
Patch

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

While this patch has lot of good I don't think we want to regress in const correctness in WebKit. I know I'm not the only one who feels it is a valuable tool that we should be using more, not less.

> Source/WebCore/dom/TypedElementDescendantIterator.h:65
> -    const ElementType* first() const;
> -    const ElementType* last() const;
> +    ElementType* first() const;
> +    ElementType* last() const;

Gross.

[Darin Adler]

Comment on attachment 391374 [details]
Patch

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

>> Source/WebCore/ChangeLog:97
>> +        another even if the root element is not the same. Deleted ElementConstIterator.
> 
> Why? We'll lose a significant amount compile time checking against serious programming errors (allowing mutations of elements that are not supposed to be mutated in the context).

Everything is still const-correct. We just don’t need a separate template to do it. We use ElementIterator<const HTMLElement>. The ElementType itself has const in it.

>> Source/WebCore/dom/TypedElementDescendantIterator.h:65
>> +    ElementType* last() const;
> 
> Gross.

We are not regressing in const-correctness! This diff is giving you the wrong impression.

[Darin Adler]

Comment on attachment 391374 [details]
Patch

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

>>> Source/WebCore/dom/TypedElementDescendantIterator.h:65
>>> +    ElementType* last() const;
>> 
>> Gross.
> 
> We are not regressing in const-correctness! This diff is giving you the wrong impression.

There is a const version of Range, Range<HTMLElement> that gives you iterators with const pointers, and a non-const version of Range, Range<const HTMLElement> that gives you iterators with non-const pointers. In both of those, the begin/end/first/last functions are const because they don’t modify the *Range*.

[Darin Adler]

Antti, I hope you have a chance to take another look. I did not get rid of const-correctness. I got rid of unneeded duplicate copies of many class templates while keeping all the const-correctness.

[Darin Adler]

Comment on attachment 391374 [details]
Patch

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

I’m going to change this back to review?, since the only reason you gave for review- is a misunderstanding. I hope you will take another look.

> Source/WebCore/dom/ElementAncestorIterator.h:114
> +        return ElementAncestorRange<const ElementType>(&downcast<ElementType>(first));

Here’s where we make a code change for lineageOfType so we retain the const correctness. Note here that because the argument is const, the template argument for the range (and indirectly for the iterator) is a const type. This is what makes the const correctness work.

> Source/WebCore/dom/ElementAncestorIterator.h:127
> +    return ElementAncestorRange<const ElementType>(findElementAncestorOfType<const ElementType>(descendant));

And here is where we do it for ancestorsOfType.

> Source/WebCore/dom/ElementChildIterator.h:129
> +    return ElementChildRange<const ElementType>(parent);

Here is where we do it for childrenOfType.

> Source/WebCore/dom/TypedElementDescendantIterator.h:256
> +    return ElementDescendantRange<const ElementType>(root);

Here’s where we make a code change so we retain the const correctness. Note here that because the argument is const, the template argument for the range (and indirectly for the iterator) is a const type. This is what makes the const correctness work.

[Antti Koivisto]

Comment on attachment 391374 [details]
Patch

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

> Source/WebCore/ChangeLog:84
> +        * dom/ElementAncestorIterator.h: Moved the declarations of the functions
> +        to the top of the file, since the classes are really implementation details.
> +        Removed the separate "Const" versions of everything since we can just use
> +        const in the template argument type instead. Use the term "Range" instead
> +        of the term "IteratorAdapter" for the class templates for use in range-based
> +        for loops since that's closer to modern C++ terminology. Use nullptr as a
> +        sentinel for end, which works well with range-based for loops. Made many function
> +        members const where appropriate. Specialized lineageOfType and ancestorsOfType
> +        for Element to slightly optimize that case. Use downcast instead of static_cast.
> +        Deleted elementLineage and elementAncestors.
> +
> +        * dom/ElementAndTextDescendantIterator.h: Renamed IteratorAdapter to Range.
> +        Made more function members const.
> +
> +        * dom/ElementChildIterator.h: Moved the declarations of the functions
> +        to the top of the file, since the classes are really implementation details.
> +        Removed the separate "Const" versions of everything since we can just use
> +        const in the template argument type instead. Use the term "Range" instead
> +        of the term "IteratorAdapter" for the class templates for use in range-based
> +        for loops since that's closer to modern C++ terminology. Use nullptr as a
> +        sentinel for end, which works well with range-based for loops. Made many
> +        function members const where appropriate. Deleted elementChildren.

Can you reorganize the ChangeLog so that interesting design issues (like how const correctness is maintained without separate const iterators) are on the top section instead of being mixed (repeatedly!) with the minutiae? 

In general I don't think is is helpful to describe mechanical code changes obviously falling out from design changes.

> Source/WebCore/ChangeLog:254
> +        * html/HTMLOptionsCollection.idl: Specify [RequiresExistingAtomString] on

The patch is pretty large. Could for example some of these collection changes be done separately?

[Darin Adler]

Comment on attachment 391374 [details]
Patch

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

>> Source/WebCore/ChangeLog:84
>> +        function members const where appropriate. Deleted elementChildren.
> 
> Can you reorganize the ChangeLog so that interesting design issues (like how const correctness is maintained without separate const iterators) are on the top section instead of being mixed (repeatedly!) with the minutiae? 
> 
> In general I don't think is is helpful to describe mechanical code changes obviously falling out from design changes.

Sure, happy to.

>> Source/WebCore/ChangeLog:254
>> +        * html/HTMLOptionsCollection.idl: Specify [RequiresExistingAtomString] on
> 
> The patch is pretty large. Could for example some of these collection changes be done separately?

Yes. This could be broken in smaller pieces. It’s hard for me to decide how many to break it into. It’s a lot of work but I would be happy to do it.

For example the “RequiresExistingAtomString” changes are completely separable. I just need some guidance how much to break this down; how many different pieces.

[Darin Adler]

Comment on attachment 391374 [details]
Patch

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

>> Source/WebCore/ChangeLog:84
>> +        function members const where appropriate. Deleted elementChildren.
> 
> Can you reorganize the ChangeLog so that interesting design issues (like how const correctness is maintained without separate const iterators) are on the top section instead of being mixed (repeatedly!) with the minutiae? 
> 
> In general I don't think is is helpful to describe mechanical code changes obviously falling out from design changes.

Sure, happy to.

>> Source/WebCore/ChangeLog:254
>> +        * html/HTMLOptionsCollection.idl: Specify [RequiresExistingAtomString] on
> 
> The patch is pretty large. Could for example some of these collection changes be done separately?

Yes. This could be broken in smaller pieces. It’s hard for me to decide how many to break it into. It’s a lot of work but I would be happy to do it.

For example the “RequiresExistingAtomString” changes are completely separable. I just need some guidance how much to break this down; how many different pieces.

[Darin Adler]

Comment on attachment 391374 [details]
Patch

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

>> Source/WebCore/ChangeLog:84
>> +        function members const where appropriate. Deleted elementChildren.
> 
> Can you reorganize the ChangeLog so that interesting design issues (like how const correctness is maintained without separate const iterators) are on the top section instead of being mixed (repeatedly!) with the minutiae? 
> 
> In general I don't think is is helpful to describe mechanical code changes obviously falling out from design changes.

Sure, happy to.

>> Source/WebCore/ChangeLog:254
>> +        * html/HTMLOptionsCollection.idl: Specify [RequiresExistingAtomString] on
> 
> The patch is pretty large. Could for example some of these collection changes be done separately?

Yes. This could be broken in smaller pieces. It’s hard for me to decide how many to break it into. It’s a lot of work but I would be happy to do it.

For example the “RequiresExistingAtomString” changes are completely separable. I just need some guidance how much to break this down; how many different pieces.

[Darin Adler]

I broke out a piece as bug 208092. Also planning to write better change log as per Antti’s suggestion. Not sure how many pieces to break this into. Would appreciate other specific suggestions for things to land separately.

[Darin Adler]

Created attachment 391461 [details]
Patch

[Darin Adler]

OK, uploaded a new patch with a WebCore change log that puts the interesting stuff on the top.

I didn't yet go down to the rest of the per-file comments and cut them all down. Not sure how much to shorten them. I suppose I could just not mention the specific changes at all since they're all at the top now. Seems like a lot of work. Just leaving it alone for now.

Open to suggestions about splitting more parts of the patch separately.

I am happy to do whatever it takes to make this better and get it landed so I can move on to something else.

[Antti Koivisto]

Comment on attachment 391461 [details]
Patch

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

I like red patches.

> Source/WebCore/ChangeLog:39
> +        - Removed the duplicate descendant iterator, keeping the one that matches
> +          the style of the ancestor and child iterators.
> +        - Removed the non-template elementAncestors, elementChildren, elementDescendants,
> +          and elementLineage functions and changed callers to use xxxOfType<Element> instead.
> +        - Renamed "IteratorAdapter" templates to "Range", choosing that term to match the
> +          upcoming C++20 Ranges library and range-based for loops.
> +        - Changed the iterators to use an actual "nullptr" for end, following the "sentinel"
> +          design pattern from the Ranges library. Still kept a tiny bit of using an iterator
> +          for end around, only so we can use iterator library functions like std::distance
> +          while waiting for std::ranges::distance, which is compatible with sentinels.
> +        - Implemented const correctness by using const types instead of separate "Const"
> +          class templates. This cut down on source code size a lot. These element iterators
> +          don't need whole separate templates to implement the const correctness the way
> +          collection classes like HashMap do.
> +        - Improved some other details, like using more const and constexpr on members.
> +          All the functions on a range are const, because the range itself doesn't ever
> +          get modified, and all functions on an iterator are also const, because only
> +          operations like ++ and -- actually modify the iterator.
> +        - For now at least, removed extra code we don't need in practice. We never need to
> +          compare iterators to each other except when iterating a range, for example, so
> +          kept the != used for range iteration but not ==.
> +        - Simplified the HTMLCollection implementations by taking advantage of the null-
> +          based and sentinel designs. There are various places where we can write
> +          simpler code and pass around fewer arguments.
> +        - Added a new descendantsOfType template that takes a predicate and filters to only
> +          the elements that match that predicate. Similar concept to how we implement HTML
> +          collections, and possibly could be used even more eventually.
> +        - Use std::iterator in ElementIterator so we don't need to do that in derived
> +          classes. Also made more of ElementIterator protected to make it more explicit
> +          that it's an abstract class template and not something to be used directly.

This is informative!

> Source/WebCore/dom/CollectionIndexCache.h:45
> -    explicit CollectionIndexCache(const Collection&);
> +    CollectionIndexCache();
>  
>      typedef typename std::iterator_traits<Iterator>::value_type NodeType;
>  
>      unsigned nodeCount(const Collection&);
>      NodeType* nodeAt(const Collection&, unsigned index);
>  
> -    bool hasValidCache(const Collection& collection) const { return m_current != collection.collectionEnd() || m_nodeCountValid || m_listValid; }
> -    void invalidate(const Collection&);
> +    bool hasValidCache() const { return m_current || m_nodeCountValid || m_listValid; }
> +    void invalidate();

This sort of work that builds on top of the refactoring would be better done as an incremental step (making the patch less unwieldy).

> Source/WebCore/dom/ElementAncestorIterator.h:54
> +    static constexpr std::nullptr_t end() { return nullptr; }

This is a nice C++17 feature.

> Source/WebCore/html/HTMLTableElement.h:98
> -    RefPtr<StyleProperties> m_sharedCellStyle;
> +    mutable RefPtr<StyleProperties> m_sharedCellStyle;

Could probably be mutable RefPtr<const StyleProperties>

> Source/WebCore/xml/parser/XMLDocumentParser.cpp:296
> +    if (contextElement) {
> +        bool stopLookingForDefaultNamespaceURI = false;
> +
> +        for (auto& element : lineageOfType<Element>(*contextElement)) {
> +            if (is<SVGForeignObjectElement>(element))
> +                stopLookingForDefaultNamespaceURI = true;
> +            else if (!stopLookingForDefaultNamespaceURI)
> +                defaultNamespaceURI = element.namespaceURI();
> +
> +            if (!element.hasAttributes())
> +                continue;
> +
> +            for (const Attribute& attribute : element.attributesIterator()) {
> +                if (attribute.prefix() == xmlnsAtom())
> +                    prefixToNamespaceMap.set(attribute.localName(), attribute.value());
> +                else if (!stopLookingForDefaultNamespaceURI && attribute.prefix() == xmlnsAtom())
> +                    defaultNamespaceURI = attribute.value();
> +            }
>          }
>      }

This looks likea good candidate for a lambda.

[Antti Koivisto]

Comment on attachment 391461 [details]
Patch

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

> Source/WebCore/dom/TypedElementDescendantIterator.h:42
> +// Range that skips elements where the filter returns false.
> +template<typename ElementType, bool filter(const ElementType&)> FilteredElementDescendantRange<const ElementType, filter> descendantsOfType(const ContainerNode&);

filteredDescendants(OfType)?

The filter template would have been another separable feature.

[Darin Adler]

I’ll follow up on all those comments. A few specific things:

- I’ll keep breaking up the patch more and land in smaller pieces. For example, I think the next one will be more adoption of the element iterators but no changes to the iterator implementation. Given they are all excerpts of this one, I might not wait for separate review of all pieces, just claim Antti reviewed. Judgement call depending on if they seem obvious or complex.

- I will use the name filteredDescendants instead of descendantsOfType.

- I plan to follow up afterwards and rename descendantsOfType to just descendants, same for lineageOfType and ancestryOfType, but I'll use the do-webcore-rename script to do it. I’ll wait on childrenOfType for now.

[Darin Adler]

Landed another piece as bug 208097, covering more adoption of the element iterators.

Separated out a third piece as bug 208098, covering a small change in behavior, where a piece of the datalist element implementation was outside ENABLE(DATALIST_ELEMENT), and I had to move it in so I could use the element iterator in its implementation.

More separate pieces to come.

[Darin Adler]

Broke out a fourth pieces as bug 208099, covering the changes outside WebCore.

[Darin Adler]

Broke out a fifth piece as bug 208100; this has the new revised versions of the implementations of the iterators. That pretty much covers what the title of this bug takes about, but still leaves some non-trivial parts of the patch attached here once these are all landed.

[Darin Adler]

Now that most of this has landed, using this bug for the last bit, and retitling accordingly. These bits are not identical to when Antti reviewed, but I still think I can probably land it without another round of review.

[Darin Adler]

Created attachment 391490 [details]
Patch

[Darin Adler]

Created attachment 391491 [details]
Patch

[Darin Adler]

Committed r257196: <https://trac.webkit.org/changeset/257196>

[Radar WebKit Bug Importer]

<rdar://problem/59709547>