Bug 266521 – AX: Use cached text runs to compute: next, previous, next line end, previous line start, line range, and string-for-range text marker APIs

• Status: RESOLVED
• Resolution: FIXED
• Component: Accessibility

[Tyler Wilcock]

...

[Radar WebKit Bug Importer]

<rdar://problem/119741911>

[Tyler Wilcock]

Created attachment 469079 [details]
Patch

[chris fleizach]

Comment on attachment 469079 [details]
Patch

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

> Source/WebCore/accessibility/AXCoreObject.cpp:409
> +AXCoreObject* AXCoreObject::nextSibling()

These two methods are mostly the same. Could they be combined

> Source/WebCore/accessibility/AXPosition.h:37
> +    Line,

Character seems like it should be a unit too and then you don't need two methods that finds a positio

> Source/WebCore/accessibility/AccessibilityObject.h:34
> +#include "AXTextRun.h"

Macros around imports are not necessary since it will just import an empty file

[Tyler Wilcock]

Created attachment 469090 [details]
Patch

[Tyler Wilcock]

(In reply to chris fleizach from comment #3)
> Comment on attachment 469079 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=469079&action=review
> 
> > Source/WebCore/accessibility/AXCoreObject.cpp:409
> > +AXCoreObject* AXCoreObject::nextSibling()
> 
> These two methods are mostly the same. Could they be combined
Yes, these could probably be refactored to have some shared implementation. Will do on Monday. Your comment also made me realize we already have `nextSibling` and `previousSibling` methods, so adding new ones with the same names is probably not a good idea. I'll address that on Monday too.
 
> > Source/WebCore/accessibility/AXPosition.h:37
> > +    Line,
> 
> Character seems like it should be a unit too and then you don't need two
> methods that finds a position
Good idea, that makes sense to me. Will address on Monday.

> > Source/WebCore/accessibility/AccessibilityObject.h:34
> > +#include "AXTextRun.h"
> 
> Macros around imports are not necessary since it will just import an empty
> file
Good point, fixed.

[Tyler Wilcock]

Created attachment 469119 [details]
Patch

[Tyler Wilcock]

(In reply to Tyler Wilcock from comment #5)
> (In reply to chris fleizach from comment #3)
> > Comment on attachment 469079 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=469079&action=review
> > 
> > > Source/WebCore/accessibility/AXCoreObject.cpp:409
> > > +AXCoreObject* AXCoreObject::nextSibling()
> > 
> > These two methods are mostly the same. Could they be combined
Made this more simple in the latest patch.

> > > Source/WebCore/accessibility/AXPosition.h:37
> > > +    Line,
> > 
> > Character seems like it should be a unit too and then you don't need two
> > methods that finds a position
Ended up deciding to keep it the way it is. It seems elegant to have a method that is basically just findPosition(next/previous), matching the actual AX API: next-text-marker and previous-text-marker. The AXTextUnitBoundary (start or end) parameter doesn't make any sense when trying to find the next / previous position, making it awkward to try to shoehorn it into that method. But I don't feel super strongly about it and could be convinced to do it that way too.

[Tyler Wilcock]

Created attachment 469122 [details]
Patch

[Tyler Wilcock]

Created attachment 469135 [details]
Patch

[Tyler Wilcock]

Created attachment 469148 [details]
Patch

[Tyler Wilcock]

Created attachment 469221 [details]
Patch

[Joshua Hoffman]

Comment on attachment 469221 [details]
Patch

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

> Source/WebCore/accessibility/AXPosition.cpp:57
> +AXPosition AXPosition::fromTextMarker(const AXTextMarker& marker)

It might be nice for this class to have a constructor that takes in an AXTextMarker as well (but definitely not necessary for this patch).

> Source/WebCore/accessibility/AXPosition.cpp:164
> +    if (textUnit == AXTextUnit::Line) {

We should add a FIXME for the other units that are not implemented yet.

> Source/WebCore/accessibility/AXPosition.cpp:167
> +        const auto* currentRuns = currentObject->textRuns();

This can be null, so I think we need to null check it before using it below?

[Joshua Hoffman]

Comment on attachment 469221 [details]
Patch

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

> Source/WebCore/accessibility/AXPosition.cpp:57
> +AXPosition AXPosition::fromTextMarker(const AXTextMarker& marker)

It might be nice for this class to have a constructor that takes in an AXTextMarker as well (but definitely not necessary for this patch).

> Source/WebCore/accessibility/AXPosition.cpp:164
> +    if (textUnit == AXTextUnit::Line) {

We should add a FIXME for the other units that are not implemented yet.

> Source/WebCore/accessibility/AXPosition.cpp:167
> +        const auto* currentRuns = currentObject->textRuns();

This can be null, so I think we need to null check it before using it below?

[Tyler Wilcock]

Created attachment 469267 [details]
Patch

[Tyler Wilcock]

> > Source/WebCore/accessibility/AXPosition.cpp:167
> > +        const auto* currentRuns = currentObject->textRuns();
> 
> This can be null, so I think we need to null check it before using it below?
Currently, the way this is implemented is that if `isTextLeaf()`, `textRuns()` is guaranteed non-null, and anything else is a bug. So I think this is OK for now, but I imagine this code will continue to evolve and maybe a better design will make this less ambiguous.

Addressed your other two comments, thanks!

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #14)
> Created attachment 469267 [details]
> Patch

diff --git a/Source/WebCore/accessibility/AXPosition.cpp b/Source/WebCore/accessibility/AXPosition.cpp
new file mode 100644
index 000000000000..3a57bd2a4b31
--- /dev/null
+++ b/Source/WebCore/accessibility/AXPosition.cpp
@@ -0,0 +1,296 @@
+/*
+ * Copyright (C) 2023 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "AXPosition.h"
+
+#if ENABLE(AX_THREAD_TEXT_APIS)
+
+#include "AXIsolatedObject.h"
+#include "AXIsolatedTree.h"
+#include "AXObjectCache.h"
+
+namespace WebCore {
+
+AXIsolatedObject* AXPosition::object() const
+{
+    RELEASE_ASSERT(!isMainThread());
+    if (m_cachedObject)
+        return m_cachedObject.get();
+
+    if (!m_treeID.isValid() || !m_objectID.isValid())
+        return nullptr;
+
+    auto tree = std::get<RefPtr<AXIsolatedTree>>(axTreeForID(treeID()));
+    m_cachedObject = tree ? tree->objectForID(objectID()) : nullptr;
+    return m_cachedObject.get();
+}
+
+const AXTextRuns* AXPosition::runs() const
+{
+    auto* object = this->object();
+    return object ? object->textRuns() : nullptr;
+}
+
+String AXPosition::debugDescription() const
+{
+    auto separator = ", ";
+    RefPtr object = this->object();
+    return makeString(
+        "treeID ", treeID().loggingString()
+        , separator, "objectID ", objectID().loggingString()
+        , separator, "role ", object ? accessibilityRoleToString(object->roleValue()) : String("no object"_s)
+        , separator, "offset ", m_offset
+    );
+}
+
+enum class CheckStart : bool { No, Yes };
+// Finds the next object with text runs in the given direction.
+static RefPtr<AXIsolatedObject> findObjectWithRuns(AXIsolatedObject& start, AXDirection direction, CheckStart checkStart = CheckStart::No)
+{
+    if (checkStart == CheckStart::Yes) {
+        if (auto* runs = start.textRuns(); runs && runs->size())
+            return &start;
+    }
+
+    RefPtr current = &start;
+    while (current) {
+        if (current != &start) {
+            auto* runs = current->textRuns();
+            if (runs && runs->size())
+                return current;
+        }
+
+        // FIXME: aria-owns breaks this traversal, as aria-owns causes the AX tree to be changed, affecting
+        // our iteration below, but it doesn't actually change text position on the page. So we need to ignore aria-owns
+        // tree changes here in order to behave correctly.
+        // We also probably need to do something about text within aria-hidden containers, which affects the AX tree.
+
+        const auto& children = current->children();
+        if (children.size()) {
+            size_t childIndex = direction == AXDirection::Next ? 0 : children.size() - 1;
+            RELEASE_ASSERT(children[childIndex]);
+            current = dynamicDowncast<AXIsolatedObject>(children[childIndex].get());
+            continue;
+        }
+
+        // `current` has no children, meaning it's a leaf node (e.g. it's text, which cannot have children).
+        // Check `current`s siblings.
+        if (auto* sibling = current->sibling(direction)) {
+            current = dynamicDowncast<AXIsolatedObject>(sibling);
+            continue;
+        }
+
+        // We have no children, and no next/previous sibling. Try our parent's sibling.
+        if (auto* parent = current->parentObjectUnignored()) {
+            current = dynamicDowncast<AXIsolatedObject>(parent->sibling(direction));
+            continue;
+        }
+
+        break;
+    }
+    return nullptr;
+}
+
+AXPosition AXPosition::findPosition(AXDirection direction) const
+{
+    if (isNull())
+        return nullPosition();
+    if (!isTextLeaf())
+        return asTextLeafPosition().findPosition(direction);
+    RELEASE_ASSERT(isTextLeaf());
+
+    size_t runIndex = runIndexFromOffset();
+    auto hasMoreTextInCurrentRun = [&] {
+        if (direction == AXDirection::Next)
+            return m_offset < runs()->at(runIndex).text.length();
+        return m_offset > 0;
+    };
+    bool hasAnotherRun = runIndex + 1 < runs()->size();
+    // The next run should not have empty text, because we're going to return a position containing m_offset + 1, which would be wrong.
+    RELEASE_ASSERT(direction == AXDirection::Previous || !hasAnotherRun || runs()->runLength(runIndex + 1) > 0);
+    // Checking for the presence of another run is only relevant for moving AXDirection::Next, as just checking that m_offset > 0 is sufficient for AXDirection::Previous.
+    if (hasMoreTextInCurrentRun() || (direction == AXDirection::Next && hasAnotherRun)) {
+        // Return an offset to the next character in the current run.
+        return AXPosition(m_treeID, m_objectID, direction == AXDirection::Next ? m_offset + 1 : m_offset - 1);

AG: Can you use return { ... } syntax?

+    }
+    // m_offset pointed to the last character in the given object's runs, so let's traverse to find the next object with runs.
+    if (RefPtr object = findObjectWithRuns(*this->object(), direction))
+        return AXPosition(object->treeID(), object->objectID(), direction == AXDirection::Next ? 0 : object->textRuns()->lastRunLength());

AG: Same here.
+
+    return nullPosition();
+}
+
+AXPosition AXPosition::findPosition(AXDirection direction, AXTextUnit textUnit, AXTextUnitBoundary boundary) const
+{
+    if (isNull())
+        return nullPosition();
+    if (!isTextLeaf())
+        return asTextLeafPosition().findPosition(direction, textUnit, boundary);
+    RELEASE_ASSERT(isTextLeaf());
+
+    if (textUnit == AXTextUnit::Line) {
+        size_t runIndex = runIndexFromOffset();
+        RefPtr currentObject = object();
+        const auto* currentRuns = currentObject->textRuns();
+
+        auto computeOffset = [&] (size_t runEndOffset, size_t runLength) {
+            // This works because `runEndOffset` is the offset pointing to the end of the given run, which includes the length of all runs preceding it. So subtracting that from the length of the current run gives us an offset to the start of the current run.
+            return boundary == AXTextUnitBoundary::End ? runEndOffset : runEndOffset - runLength;
+        };
+        auto linePosition = AXPosition(m_treeID, m_objectID, computeOffset(currentRuns->runLengthSumTo(runIndex), currentRuns->runLength(runIndex)));
+        auto startLineID = currentRuns->lineID(runIndex);
+        // We found the start run and associated line, now iterate until we find a line boundary.
+        while (currentObject) {
+            RELEASE_ASSERT(currentRuns->size());
+            unsigned cumulativeOffset = 0;
+            for (size_t i = 0; i < currentRuns->size(); i++) {
+                cumulativeOffset += currentRuns->runLength(i);
+                if (currentRuns->lineID(i) != startLineID)
+                    return linePosition;
+                linePosition = AXPosition(currentObject->treeID(), currentObject->objectID(), computeOffset(cumulativeOffset, currentRuns->runLength(i)));
+            }
+            currentObject = findObjectWithRuns(*currentObject, direction);
+            if (currentObject)
+                currentRuns = currentObject->textRuns();
+        }
+        return linePosition;
+    }
+    // FIXME: Implement the other AXTextUnits.
+
+    return nullPosition();
+}
+
+AXPosition AXPosition::asTextLeafPosition() const
+{
+    if (isNull() || isTextLeaf()) {
+        // If something has constructed a leaf position, it should've done so with an in-bounds offset.
+        RELEASE_ASSERT(isNull() || object()->textRuns()->runLengthSum() >= m_offset);
+        return *this;
+    }
+
+    // Find the leaf node our offset points to. For example:
+    // AXPosition { ID 1: Group, Offset 6 }
+    // ID 1: Group
+    //  - ID 2: Foo
+    //  - ID 3: Line1
+    //          Line2
+    // Calling asTextLeafPosition() on the original position should yield new position:
+    // AXPosition { ID 3: StaticText, Offset 3 }
+    // Because we had to walk over ID 2 which had length 3 text.
+    size_t precedingOffset = 0;
+    RefPtr current = findObjectWithRuns(*object(), AXDirection::Next, CheckStart::Yes);
+    while (current) {
+        unsigned currentSum = current->textRuns()->runLengthSum();
+        if (precedingOffset + currentSum >= m_offset)
+            break;
+        precedingOffset += currentSum;
+        current = findObjectWithRuns(*current, AXDirection::Next);
+    }
+
+    if (!current)
+        return nullPosition();
+
+    RELEASE_ASSERT(m_offset >= precedingOffset);
+    return AXPosition(current->treeID(), current->objectID(), m_offset - precedingOffset);

AG: return { ... }

+}
+
+bool AXPosition::isTextLeaf() const
+{
+    auto* object = this->object();
+    // FIXME: Is it possible for non-leaf nodes to have text runs? If so, we don't handle them correctly.
+    return !object || (!object->children().size() && object->textRuns());
+}
+
+size_t AXPosition::runIndexFromOffset() const
+{
+    auto* runs = this->runs();
+    if (!runs)
+        return notFound;
+
+    size_t index = runs->indexForOffset(m_offset);
+    // If we couldn't find a corresponding run, that means m_offset pointed out of bounds of our text runs, which
+    // would only happen if we've constructed an invalid position.
+    RELEASE_ASSERT(index != notFound);
+    return index;
+}
+
+AXTextMarkerRange AXPosition::lineRange(LineRangeType type) const
+{
+    if (isNull())
+        return { nullPosition(), nullPosition() };
+
+    if (type == LineRangeType::Current)
+        return { findPosition(AXDirection::Previous, AXTextUnit::Line, AXTextUnitBoundary::Start), findPosition(AXDirection::Next, AXTextUnit::Line, AXTextUnitBoundary::End) };
+    // The other types aren't implemented yet.

AG: FIXME.

+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+String AXPosition::substring(unsigned start, unsigned length) const
+{
+    if (isNull())
+        return emptyString();
+    if (!isTextLeaf())
+        return asTextLeafPosition().substring(start, length);
+    RELEASE_ASSERT(isTextLeaf());
+    return runs()->substring(start, length);
+}
+
+String AXPosition::stringWithEnd(const AXPosition& endPosition)
+{
+    if (isNull())
+        return emptyString();
+    if (!isTextLeaf())
+        return asTextLeafPosition().stringWithEnd(endPosition);
+    RELEASE_ASSERT(isTextLeaf());
+    auto endLeafPosition = endPosition.asTextLeafPosition();
+
+    if (object() == endLeafPosition.object()) {
+        size_t minOffset = std::min(m_offset, endLeafPosition.offset());
+        size_t maxOffset = std::max(m_offset, endLeafPosition.offset());
+        return substring(minOffset, maxOffset - minOffset);
+    }
+
+    StringBuilder result;
+    result.append(substring(m_offset));
+
+    // FIXME: If we've been given reversed positions, i.e. the end position actually comes before the start position,
+    // we may want to detect this and try searching AXDirection::Previous?
+    RefPtr current = object();
+    while (current->objectID() != endLeafPosition.objectID()) {
+        current = findObjectWithRuns(*current, AXDirection::Next);
+        if (!current)
+            break;
+
+        const auto* runs = current->textRuns();
+        for (unsigned i = 0; i < runs->size(); i++)
+            result.append(runs->at(i).text);
+    }
+    result.append(endLeafPosition.substring(0, endLeafPosition.offset()));
+    return result.toString();
+}
+
+} // namespace WebCore
+#endif // ENABLE(AX_THREAD_TEXT_APIS)
diff --git a/Source/WebCore/accessibility/AXPosition.h b/Source/WebCore/accessibility/AXPosition.h
new file mode 100644
index 000000000000..5e5744ceeb6d
--- /dev/null
+++ b/Source/WebCore/accessibility/AXPosition.h
@@ -0,0 +1,98 @@
+/*
+ * Copyright (C) 2023 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(AX_THREAD_TEXT_APIS)
+#include "AXIsolatedObject.h"
+#include "AXTextMarker.h"
+
+namespace WebCore {
+
+enum class AXTextUnit : uint8_t {
+    Line,
+    Paragraph,
+    Sentence,
+    Word,
+};

AG: should we have Character also?

+enum class AXTextUnitBoundary : bool { Start, End, };
+
+enum class LineRangeType : uint8_t {
+    Current,
+    Left,
+    Right,
+};
+
+class AXPosition {
+public:
+    explicit AXPosition(AXID treeID, AXID objectID, unsigned offset)
+        : m_treeID(treeID)
+        , m_objectID(objectID)
+        , m_offset(offset)
+    { }
+    AXPosition(const AXTextMarker& marker)
+        : m_treeID(marker.treeID())
+        , m_objectID(marker.objectID())
+        , m_offset(marker.characterOffset())
+    { }
+    static AXPosition nullPosition() { return AXPosition(AXID(), AXID(), 0); }

AG: you can define a default contstructor AXPosition() that creates a null object, and then you can use { } where you need a null position.


AG: Can't the compiler handle return { { }, { }, 0}; ?

+
+    operator AXTextMarker() const
+    {
+        return { { treeID(), objectID(), nullptr, m_offset } };
+    }
+    String debugDescription() const;
+
+    // Find the next or previous position.
+    AXPosition findPosition(AXDirection) const;
+    // Starting from this position, creates a new position for the given direction and text unit type.
+    AXPosition findPosition(AXDirection, AXTextUnit, AXTextUnitBoundary) const;
+    AXTextMarkerRange lineRange(LineRangeType) const;
+    String stringWithEnd(const AXPosition&);

AG: what is this method returning?
+
+private:
+    AXID treeID() const { return m_treeID; }
+    AXID objectID() const { return m_objectID; }
+    unsigned offset() const { return m_offset; }
+
+    AXIsolatedObject* object() const;
+    const AXTextRuns* runs() const;
+    String substring(unsigned start, unsigned length = StringImpl::MaxLength) const;

AG: not clear what a substring of a position is. To me a substring would be associated with a range, not with a single position.

+    size_t runIndexFromOffset() const;

AG: shouldn't this be textRunIndexForOffset ? or offsetToRunTextIndex ?

+    bool isNull() const { return !object(); }
+
+    AXPosition asTextLeafPosition() const;

AG: maybe it makes more sense to put this method below the following comment that gives more context.

+    // A "text leaf" position is a leaf node (no children) with non-empty textruns.
+    bool isTextLeaf() const;
+
+    AXID m_treeID;
+    AXID m_objectID;
+    unsigned m_offset { 0 };
+
+    mutable RefPtr<AXIsolatedObject> m_cachedObject;

AG: I wouldn't include the word "cached" in this member name, too many caches already to be any meaningful.
AG: no clear why you need to keep a reference to the object when you can always retrieve it from the tree that in turn is accessible from the AXTreeStore as you do in AXPosition::object().

+};

AG: So essentially, this is a subset of an AXTextMarker data plus additional functionality. It would be good to unify AXTextMarker and AXPosition.

+
+} // namespace WebCore
+#endif // ENABLE(AX_THREAD_TEXT_APIS)

[Tyler Wilcock]

Created attachment 469285 [details]
Patch

[Tyler Wilcock]

> +enum class AXTextUnit : uint8_t {
> +    Line,
> +    Paragraph,
> +    Sentence,
> +    Word,
> +};
> 
> AG: should we have Character also?
I did consider this. But it’s awkward because in `findMarker(AXDirection, AXTextUnit, AXTextUnitBoundary)`, the AXTextUnitBoundary boundary wouldn’t make sense for the character text unit. I decided to just create a `findMarker(AXDirection)` method to service this need (presumably just for AXNextTextMarker and AXPreviousTextMarker). But we could just make AXTextUnitBoundary a defaulted parameter, and not use it when handling AXTextUnit::Character. Let me know which you’d prefer, I’m good with keeping as-is or doing the default parameter or some other idea.

> AG: So essentially, this is a subset of an AXTextMarker data plus additional
> functionality. It would be good to unify AXTextMarker and AXPosition.
Yes, you're spot on with that description. I made this a separate class for simplicity — avoid polluting the "old" text marker logic with this new way of doing things. But doing that just makes it complex in different ways, e.g. requiring conversions between the two. I moved all of AXPosition into AXTextMarker in the latest patch.

> +    String substring(unsigned start, unsigned length =
> StringImpl::MaxLength) const;
> 
> AG: not clear what a substring of a position is. To me a substring would be
> associated with a range, not with a single position.
I added a comment to help clarify this, but let me know if it’s still not a good fit or otherwise doesn’t make sense.

Addressed all your other comments. Thanks!

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #17)
> Created attachment 469285 [details]
> Patch

diff --git a/Source/WebCore/accessibility/AXTextMarker.cpp b/Source/WebCore/accessibility/AXTextMarker.cpp
index 9ad6abf93aac..89a154687ab9 100644
--- a/Source/WebCore/accessibility/AXTextMarker.cpp
+++ b/Source/WebCore/accessibility/AXTextMarker.cpp
@@ -194,6 +194,16 @@ std::optional<BoundaryPoint> AXTextMarker::boundaryPoint() const
     return { { *node, static_cast<unsigned>(offset) } };
 }

+#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
+RefPtr<AXIsolatedObject> AXTextMarker::isolatedObject() const
+{
+    if (isNull() || isMainThread())
+        return nullptr;
+    auto tree = std::get<RefPtr<AXIsolatedTree>>(axTreeForID(treeID()));
+    return tree ? tree->objectForID(objectID()) : nullptr;
+}
+#endif // ENABLE(ACCESSIBILITY_ISOLATED_TREE)

AG: I think this can be just something like:
    return dynamicDowncast<AXIsolatedObject>(object());
AG: We should also add a FIXME (maybe in the header) explaining why we need to differentiate isolated vs. live object in this stage, and that eventually this should be agnostic of the underlying AX object.

+
 RefPtr<AXCoreObject> AXTextMarker::object() const
 {
     if (isNull())
@@ -335,7 +345,7 @@ std::optional<AXTextMarkerRange> AXTextMarkerRange::intersectionWith(const AXTex

 String AXTextMarkerRange::debugDescription() const
 {
-    return makeString("start: {", m_start.debugDescription(), "}\nend: {", m_end.debugDescription(), "}");
+    return makeString("start: {", m_start.debugDescription(), "}\nend:   {", m_end.debugDescription(), "}");
 }

 std::partial_ordering partialOrder(const AXTextMarker& marker1, const AXTextMarker& marker2)
@@ -368,4 +378,240 @@ bool AXTextMarkerRange::isConfinedTo(AXID objectID) const
         && LIKELY(m_start.treeID() == m_end.treeID());
 }

+#if ENABLE(AX_THREAD_TEXT_APIS)
+enum class CheckStart : bool { No, Yes };
+// Finds the next object with text runs in the given direction.
+static RefPtr<AXIsolatedObject> findObjectWithRuns(AXIsolatedObject& start, AXDirection direction, CheckStart checkStart = CheckStart::No)
+{
+    if (checkStart == CheckStart::Yes) {
+        if (auto* runs = start.textRuns(); runs && runs->size())
+            return &start;
+    }
+
+    RefPtr current = &start;
+    while (current) {
+        if (current != &start) {
+            auto* runs = current->textRuns();
+            if (runs && runs->size())
+                return current;
+        }
+
+        // FIXME: aria-owns breaks this traversal, as aria-owns causes the AX tree to be changed, affecting
+        // our iteration below, but it doesn't actually change text position on the page. So we need to ignore aria-owns
+        // tree changes here in order to behave correctly.
+        // We also probably need to do something about text within aria-hidden containers, which affects the AX tree.
+
+        const auto& children = current->children();
+        if (children.size()) {
+            size_t childIndex = direction == AXDirection::Next ? 0 : children.size() - 1;
+            RELEASE_ASSERT(children[childIndex]);
+            current = dynamicDowncast<AXIsolatedObject>(children[childIndex].get());
+            continue;
+        }
+
+        // `current` has no children, meaning it's a leaf node (e.g. it's text, which cannot have children).
+        // Check `current`s siblings.
+        if (auto* sibling = current->sibling(direction)) {
+            current = dynamicDowncast<AXIsolatedObject>(sibling);
+            continue;
+        }
+
+        // We have no children, and no next/previous sibling. Try our parent's sibling.
+        if (auto* parent = current->parentObjectUnignored()) {
+            current = dynamicDowncast<AXIsolatedObject>(parent->sibling(direction));
+            continue;
+        }
+
+        break;
+    }
+    return nullptr;
+}
+
+String AXTextMarkerRange::toString() const
+{
+    RELEASE_ASSERT(!isMainThread());
+
+    auto start = m_start.asTextLeafMarker();
+    if (!start.isValid())
+        return emptyString();
+    auto end = m_end.asTextLeafMarker();
+    if (!end.isValid())
+        return emptyString();
+
+    if (start.isolatedObject() == end.isolatedObject()) {
+        size_t minOffset = std::min(start.offset(), end.offset());
+        size_t maxOffset = std::max(start.offset(), end.offset());
+        return start.substring(minOffset, maxOffset - minOffset);
+    }
+
+    StringBuilder result;
+    result.append(start.substring(start.offset()));
+
+    // FIXME: If we've been given reversed markers, i.e. the end marker actually comes before the start marker,
+    // we may want to detect this and try searching AXDirection::Previous?
+    RefPtr current = start.isolatedObject();
+    while (current->objectID() != end.objectID()) {

AG: could current ever be null here?

+        current = findObjectWithRuns(*current, AXDirection::Next);
+        if (!current)
+            break;
+
+        const auto* runs = current->textRuns();
+        for (unsigned i = 0; i < runs->size(); i++)
+            result.append(runs->at(i).text);
+    }
+    result.append(end.substring(0, end.offset()));
+    return result.toString();
+}
+
+const AXTextRuns* AXTextMarker::runs() const
+{
+    RefPtr object = isolatedObject();
+    return object ? object->textRuns() : nullptr;
+}
+
+AXTextMarker AXTextMarker::findMarker(AXDirection direction) const
+{
+    if (!isValid())
+        return { };
+    if (!isTextLeaf())
+        return asTextLeafMarker().findMarker(direction);
+    RELEASE_ASSERT(isTextLeaf());
+
+    size_t runIndex = textRunIndexForOffset();
+    auto hasMoreTextInCurrentRun = [&] {
+        if (direction == AXDirection::Next)
+            return offset() < runs()->at(runIndex).text.length();
+        return offset() > 0;
+    };
+    bool hasAnotherRun = runIndex + 1 < runs()->size();
+    // The next run should not have empty text, because we're going to return a position containing offset() + 1, which would be wrong.
+    RELEASE_ASSERT(direction == AXDirection::Previous || !hasAnotherRun || runs()->runLength(runIndex + 1) > 0);
+    // Checking for the presence of another run is only relevant for moving AXDirection::Next, as just checking that offset() > 0 is sufficient for AXDirection::Previous.
+    if (hasMoreTextInCurrentRun() || (direction == AXDirection::Next && hasAnotherRun)) {
+        // Return an offset to the next character in the current run.
+        return { treeID(), objectID(), direction == AXDirection::Next ? offset() + 1 : offset() - 1 };
+    }
+    // offset() pointed to the last character in the given object's runs, so let's traverse to find the next object with runs.
+    if (RefPtr object = findObjectWithRuns(*this->isolatedObject(), direction))
+        return { object->treeID(), object->objectID(), direction == AXDirection::Next ? 0 : object->textRuns()->lastRunLength() };
+
+    return { };
+}
+
+AXTextMarker AXTextMarker::findMarker(AXDirection direction, AXTextUnit textUnit, AXTextUnitBoundary boundary) const
+{
+    if (!isValid())
+        return { };
+    if (!isTextLeaf())
+        return asTextLeafMarker().findMarker(direction, textUnit, boundary);
+    RELEASE_ASSERT(isTextLeaf());
+
+    if (textUnit == AXTextUnit::Line) {
+        size_t runIndex = textRunIndexForOffset();
+        RefPtr currentObject = isolatedObject();
+        const auto* currentRuns = currentObject->textRuns();
+
+        auto computeOffset = [&] (size_t runEndOffset, size_t runLength) {
+            // This works because `runEndOffset` is the offset pointing to the end of the given run, which includes the length of all runs preceding it. So subtracting that from the length of the current run gives us an offset to the start of the current run.
+            return boundary == AXTextUnitBoundary::End ? runEndOffset : runEndOffset - runLength;
+        };
+        auto linePosition = AXTextMarker(treeID(), objectID(), computeOffset(currentRuns->runLengthSumTo(runIndex), currentRuns->runLength(runIndex)));
+        auto startLineID = currentRuns->lineID(runIndex);
+        // We found the start run and associated line, now iterate until we find a line boundary.
+        while (currentObject) {
+            RELEASE_ASSERT(currentRuns->size());
+            unsigned cumulativeOffset = 0;
+            for (size_t i = 0; i < currentRuns->size(); i++) {
+                cumulativeOffset += currentRuns->runLength(i);
+                if (currentRuns->lineID(i) != startLineID)
+                    return linePosition;
+                linePosition = AXTextMarker(currentObject->treeID(), currentObject->objectID(), computeOffset(cumulativeOffset, currentRuns->runLength(i)));
+            }
+            currentObject = findObjectWithRuns(*currentObject, direction);
+            if (currentObject)
+                currentRuns = currentObject->textRuns();
+        }
+        return linePosition;
+    }
+    // FIXME: Implement the other AXTextUnits.
+
+    return { };
+}
+
+AXTextMarker AXTextMarker::asTextLeafMarker() const
+{
+    if (!isValid() || isTextLeaf()) {
+        // If something has constructed a leaf marker, it should've done so with an in-bounds offset.
+        RELEASE_ASSERT(!isValid() || isolatedObject()->textRuns()->runLengthSum() >= offset());
+        return *this;
+    }
+
+    // Find the leaf node our offset points to. For example:
+    // AXTextMarker { ID 1: Group, Offset 6 }
+    // ID 1: Group
+    //  - ID 2: Foo
+    //  - ID 3: Line1
+    //          Line2
+    // Calling asTextLeafMarker() on the original marker should yield new marker:
+    // AXTextMarker { ID 3: StaticText, Offset 3 }
+    // Because we had to walk over ID 2 which had length 3 text.
+    size_t precedingOffset = 0;
+    RefPtr current = findObjectWithRuns(*isolatedObject(), AXDirection::Next, CheckStart::Yes);
+    while (current) {
+        unsigned currentSum = current->textRuns()->runLengthSum();
+        if (precedingOffset + currentSum >= offset())
+            break;
+        precedingOffset += currentSum;
+        current = findObjectWithRuns(*current, AXDirection::Next);
+    }
+
+    if (!current)
+        return { };
+
+    RELEASE_ASSERT(offset() >= precedingOffset);
+    return { current->treeID(), current->objectID(), static_cast<unsigned>(offset() - precedingOffset) };
+}
+
+bool AXTextMarker::isTextLeaf() const
+{
+    RefPtr object = this->isolatedObject();
+    // FIXME: Is it possible for non-leaf nodes to have text runs? If so, we don't handle them correctly.
+    return !object || (!object->children().size() && object->textRuns());
+}
+
+size_t AXTextMarker::textRunIndexForOffset() const
+{
+    auto* runs = this->runs();
+    if (!runs)
+        return notFound;
+
+    size_t index = runs->indexForOffset(offset());
+    // If we couldn't find a corresponding run, that means offset() pointed out of bounds of our text runs, which
+    // would only happen if we've constructed an invalid marker.
+    RELEASE_ASSERT(index != notFound);
+    return index;
+}
+
+AXTextMarkerRange AXTextMarker::lineRange(LineRangeType type) const
+{
+    if (!isValid())
+        return { { }, { } };
+
+    if (type == LineRangeType::Current)
+        return { findMarker(AXDirection::Previous, AXTextUnit::Line, AXTextUnitBoundary::Start), findMarker(AXDirection::Next, AXTextUnit::Line, AXTextUnitBoundary::End) };
+    // FIXME: The other types aren't implemented yet.
+    RELEASE_ASSERT_NOT_REACHED();
+}
+
+String AXTextMarker::substring(unsigned start, unsigned length) const
+{
+    if (!isValid())
+        return emptyString();
+    if (!isTextLeaf())
+        return asTextLeafMarker().substring(start, length);
+    RELEASE_ASSERT(isTextLeaf());
+    return runs()->substring(start, length);
+}
+#endif // ENABLE(AX_THREAD_TEXT_APIS)
+
 } // namespace WebCore
diff --git a/Source/WebCore/accessibility/AXTextMarker.h b/Source/WebCore/accessibility/AXTextMarker.h
index 17e9fc0dab98..524376f5bef5 100644
--- a/Source/WebCore/accessibility/AXTextMarker.h
+++ b/Source/WebCore/accessibility/AXTextMarker.h
@@ -28,7 +28,25 @@

 namespace WebCore {

+#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
+class AXIsolatedObject;
+#endif
 struct CharacterOffset;
+struct AXTextRuns;
+
+enum class AXTextUnit : uint8_t {
+    Line,
+    Paragraph,
+    Sentence,
+    Word,
+};
+enum class AXTextUnitBoundary : bool { Start, End, };
+
+enum class LineRangeType : uint8_t {
+    Current,
+    Left,
+    Right,
+};

 struct TextMarkerData {
     unsigned treeID;
@@ -109,6 +127,9 @@ public:
 #if PLATFORM(COCOA)
     AXTextMarker(PlatformTextMarkerData);
 #endif
+    AXTextMarker(AXID treeID, AXID objectID, unsigned offset)
+        : m_data({ treeID, objectID, nullptr, offset })
+    { }
     AXTextMarker() = default;

     operator bool() const { return !isNull(); }
@@ -123,7 +144,11 @@ public:

     AXID treeID() const { return m_data.axTreeID(); }
     AXID objectID() const { return m_data.axObjectID(); }
+    unsigned offset() const { return m_data.offset; }
     bool isNull() const { return !treeID().isValid() || !objectID().isValid(); }
+#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
+    RefPtr<AXIsolatedObject> isolatedObject() const;
+#endif
     RefPtr<AXCoreObject> object() const;
     bool isValid() const { return object(); }

@@ -134,7 +159,28 @@ public:

     // Sets m_data.node when the marker was created with a PlatformTextMarkerData that lacks the node pointer because it was created off the main thread.
     void setNodeIfNeeded() const;
+
+#if ENABLE(AX_THREAD_TEXT_APIS)
+    // Find the next or previous marker.
+    AXTextMarker findMarker(AXDirection) const;
+    // Starting from this text marker, creates a new position for the given direction and text unit type.
+    AXTextMarker findMarker(AXDirection, AXTextUnit, AXTextUnitBoundary) const;
+    // Creates a range for the line this marker points to.
+    AXTextMarkerRange lineRange(LineRangeType) const;
+#endif // ENABLE(AX_THREAD_TEXT_APIS)
+
 private:
+#if ENABLE(AX_THREAD_TEXT_APIS)
+    const AXTextRuns* runs() const;
+    // Substring into the text runs of the object associated with this text marker (if it has any).
+    String substring(unsigned start, unsigned length = StringImpl::MaxLength) const;
+    size_t textRunIndexForOffset() const;

AG: these last two private methods seems to me belong to AXTextRuns, not to this class.

+
+    // A "text leaf" marker is a leaf node (no children) with non-empty text runs.
+    bool isTextLeaf() const;
+    AXTextMarker asTextLeafMarker() const;

AG: shouldn't this be called isInTextLeaf and toTextLeafMarker ? The first one because the marker is in a leaf object, not that the marker is a leaf itself. And the second one to better indicate that is a transformation from one marker to another marker.

+#endif // ENABLE(AX_THREAD_TEXT_APIS)
+
     TextMarkerData m_data;
 };

@@ -171,6 +217,11 @@ public:
     AXTextMarker end() const { return m_end; }
     bool isConfinedTo(AXID) const;

+#if ENABLE(AX_THREAD_TEXT_APIS)
+    // Traverses from m_start to m_end, collecting all text along the way.
+    String toString() const;
+#endif
+
     String debugDescription() const;
 private:
     AXTextMarker m_start;

[Tyler Wilcock]

Created attachment 469341 [details]
Patch

[Tyler Wilcock]

(In reply to Andres Gonzalez from comment #19)
All comments addressed, thanks!

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #20)
> Created attachment 469341 [details]
> Patch

diff --git a/Source/WebCore/accessibility/AXTextRun.cpp b/Source/WebCore/accessibility/AXTextRun.cpp
new file mode 100644
index 000000000000..504fa2472aa6
--- /dev/null
+++ b/Source/WebCore/accessibility/AXTextRun.cpp
@@ -0,0 +1,93 @@
+/*
+ * Copyright (C) 2023 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "AXTextRun.h"
+
+#if ENABLE(AX_THREAD_TEXT_APIS)
+namespace WebCore {
+
+String AXTextRuns::debugDescription() const
+{
+    StringBuilder result;
+    result.append('[');
+    for (unsigned i = 0; i < runs.size(); i++) {
+        result.append(runs[i].debugDescription(containingBlock));
+        if (i != runs.size() - 1)
+            result.append(", ");
+    }
+    result.append(']');
+    return result.toString();
+}
+
+size_t AXTextRuns::indexForOffset(unsigned textOffset) const
+{
+    size_t cumulativeLength = 0;
+    for (size_t i = 0; i < runs.size(); i++) {
+        cumulativeLength += runLength(i);
+        if (cumulativeLength >= textOffset)
+            return i;
+    }
+    return notFound;
+}
+
+unsigned AXTextRuns::runLengthSumTo(size_t index) const
+{
+    unsigned length = 0;
+    for (size_t i = 0; i <= index && i < runs.size(); i++)
+        length += runLength(i);
+    return length;
+}
+
+String AXTextRuns::substring(unsigned start, unsigned length) const
+{
+    if (!length)
+        return emptyString();
+
+    StringBuilder result;
+    size_t charactersSeen = 0;
+    auto remaining = [&] () {
+        return result.length() >= length ? 0 : length - result.length();
+    };
+    for (unsigned i = 0; i < runs.size() && result.length() < length; i++) {
+        size_t runLength = this->runLength(i);
+        if (charactersSeen >= start) {
+            // The start points entirely within bounds of this run.
+            result.append(runs[i].text.left(remaining()));
+        } else if (charactersSeen + runLength > start) {
+            // start points somewhere in the middle of the current run, collect part of the text.
+            unsigned startInRun = start - charactersSeen;
+            RELEASE_ASSERT(startInRun < runLength);
+            result.append(runs[i].text.substring(startInRun, remaining()));
+        }
+        // If charactersSeen + runLength == start, the start points to the end of the run, and there is no text to gather.
+
+        charactersSeen += runLength;
+    }
+    return result.toString();
+}
+
+} // namespace WebCore
+#endif // ENABLE(AX_THREAD_TEXT_APIS)
diff --git a/Source/WebCore/accessibility/AXTextRun.h b/Source/WebCore/accessibility/AXTextRun.h
new file mode 100644
index 000000000000..a099f311f56d
--- /dev/null
+++ b/Source/WebCore/accessibility/AXTextRun.h
@@ -0,0 +1,120 @@
+/*
+ * Copyright (C) 2023 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#if ENABLE(AX_THREAD_TEXT_APIS)
+namespace WebCore {
+
+class RenderBlock;
+
+struct AXTextRunLineID {
+    void* containingBlock { nullptr };
+    size_t lineIndex { 0 };
+
+    AXTextRunLineID(void* containingBlock, size_t lineIndex)
+        : containingBlock(containingBlock)
+        , lineIndex(lineIndex)
+    { }
+    bool operator==(const AXTextRunLineID&) const = default;
+    String debugDescription() const
+    {
+        TextStream stream;
+        stream << "LineID " << containingBlock << " " << lineIndex;
+        return stream.release();
+    }
+};
+
+struct AXTextRun {
+    // The line index of this run within the context of the containing RenderBlock of the main-thread AX object.
+    size_t lineIndex;
+    String text;
+
+    AXTextRun(size_t lineIndex, String&& text)
+        : lineIndex(lineIndex)
+        , text(WTFMove(text))
+    { }
+
+    String debugDescription(void* containingBlock) const
+    {
+        AXTextRunLineID lineID = { containingBlock, lineIndex };
+        return makeString(lineID.debugDescription(), ": |", makeStringByReplacingAll(text, '\n', "{newline}"_s), "|(len ", text.length(), ")");
+    }
+};
+
+struct AXTextRuns {
+    // The containing block for the text runs. This is required because based on the structure
+    // of the AX tree, text runs for different objects can have the same line index but different
+    // containing blocks, meaning they are rendered on different lines.
+    // Do not de-reference. Use for comparison purposes only.
+    void* containingBlock { nullptr };
+    Vector<AXTextRun> runs;
+
+    AXTextRuns() = default;
+    AXTextRuns(RenderBlock* containingBlock, Vector<AXTextRun>&& runs)
+        : containingBlock(containingBlock)
+        , runs(WTFMove(runs))
+    { }
+    String debugDescription() const;
+
+    size_t size() const { return runs.size(); }
+    const AXTextRun& at(size_t index) const
+    {
+        return (*this)[index];
+    }
+    const AXTextRun& operator[](size_t index) const
+    {
+        RELEASE_ASSERT(index < runs.size());
+        return runs[index];
+    }
+
+    unsigned runLength(size_t index) const
+    {
+        RELEASE_ASSERT(index < runs.size());
+        return runs[index].text.length();
+    }
+    unsigned lastRunLength() const
+    {
+        if (runs.isEmpty())
+            return 0;
+        return runs[runs.size() - 1].text.length();
+    }
+    unsigned runLengthSum() const

AG: maybe totalLength ? or just length ?

+    {
+        return runLengthSumTo(runs.size() - 1);
+    }
+    unsigned runLengthSumTo(size_t index) const;
+
+    size_t indexForOffset(unsigned textOffset) const;
+    AXTextRunLineID lineID(size_t index) const
+    {
+        RELEASE_ASSERT(index < runs.size());
+        return { containingBlock, runs[index].lineIndex };
+    }
+    String substring(unsigned start, unsigned length = StringImpl::MaxLength) const;
+};
+
+} // namespace WebCore
+#endif // ENABLE(AX_THREAD_TEXT_APIS)
diff --git a/Source/WebCore/accessibility/AccessibilityObject.cpp b/Source/WebCore/accessibility/AccessibilityObject.cpp
index 29a931c5aa14..f339b3ab0081 100644
--- a/Source/WebCore/accessibility/AccessibilityObject.cpp
+++ b/Source/WebCore/accessibility/AccessibilityObject.cpp
@@ -113,6 +113,12 @@ void AccessibilityObject::init()
     m_role = determineAccessibilityRole();
 }

+AXID AccessibilityObject::treeID() const
+{
+    auto* cache = axObjectCache();
+    return cache ? cache->treeID() : AXID();
+}
+
 inline ProcessID AccessibilityObject::processID() const
 {
     return presentingApplicationPID();
diff --git a/Source/WebCore/accessibility/AccessibilityObject.h b/Source/WebCore/accessibility/AccessibilityObject.h
index e64b6306c08e..c7f28d5c3b55 100644
--- a/Source/WebCore/accessibility/AccessibilityObject.h
+++ b/Source/WebCore/accessibility/AccessibilityObject.h
@@ -30,6 +30,7 @@
 #pragma once

 #include "AXCoreObject.h"
+#include "AXTextRun.h"
 #include "CharacterRange.h"
 #include "FloatQuad.h"
 #include "LayoutRect.h"
@@ -63,6 +64,7 @@ class AccessibilityObject : public AXCoreObject, public CanMakeWeakPtr<Accessibi
 public:
     virtual ~AccessibilityObject();

+    AXID treeID() const final;
     ProcessID processID() const override;
     String dbg() const final;

@@ -382,6 +384,9 @@ public:
     String textUnderElement(AccessibilityTextUnderElementMode = AccessibilityTextUnderElementMode()) const override { return { }; }
     String text() const override { return { }; }
     unsigned textLength() const final;
+#if ENABLE(AX_THREAD_TEXT_APIS)
+    virtual AXTextRuns textRuns() { return { }; }
+#endif
 #if PLATFORM(COCOA)
     // Returns an array of strings and AXObject wrappers corresponding to the
     // textruns and replacement nodes included in the given range.
diff --git a/Source/WebCore/accessibility/AccessibilityRenderObject.cpp b/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
index 39469e690600..f738e89b42aa 100644
--- a/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
+++ b/Source/WebCore/accessibility/AccessibilityRenderObject.cpp
@@ -1403,11 +1403,11 @@ CharacterRange AccessibilityRenderObject::selectedTextRange() const
 }

 #if ENABLE(AX_THREAD_TEXT_APIS)
-Vector<AXTextRun> AccessibilityRenderObject::textRuns()
+AXTextRuns AccessibilityRenderObject::textRuns()
 {
     if (auto* renderLineBreak = dynamicDowncast<RenderLineBreak>(renderer())) {
         auto box = InlineIterator::boxFor(*renderLineBreak);
-        return { { box->lineIndex(), makeString('\n') } };
+        return { renderLineBreak->containingBlock(), { AXTextRun(box->lineIndex(), makeString('\n').isolatedCopy()) } };

AG: shouldn't have to make an isolatedCopy here since this is a main thread object.

     }

     WeakPtr renderText = dynamicDowncast<RenderText>(renderer());
@@ -1460,7 +1460,7 @@ Vector<AXTextRun> AccessibilityRenderObject::textRuns()

     if (!lineString.isEmpty())
         runs.append({ currentLineIndex, lineString.toString().isolatedCopy() });
-    return runs;
+    return { renderText->containingBlock(), WTFMove(runs) };
 }
 #endif // ENABLE(AX_THREAD_TEXT_APIS)

diff --git a/Source/WebCore/accessibility/AccessibilityRenderObject.h b/Source/WebCore/accessibility/AccessibilityRenderObject.h
index ceec6bf3e898..be9ee4f86046 100644
--- a/Source/WebCore/accessibility/AccessibilityRenderObject.h
+++ b/Source/WebCore/accessibility/AccessibilityRenderObject.h
@@ -100,7 +100,7 @@ public:
     String textUnderElement(AccessibilityTextUnderElementMode = AccessibilityTextUnderElementMode()) const override;
     String selectedText() const override;
 #if ENABLE(AX_THREAD_TEXT_APIS)
-    Vector<AXTextRun> textRuns() final;
+    AXTextRuns textRuns() final;
 #endif

     bool isWidget() const override;
diff --git a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp b/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
index 62a1a575ae61..345f2d53df58 100644
--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
+++ b/Source/WebCore/accessibility/isolatedtree/AXIsolatedObject.cpp
@@ -31,6 +31,7 @@
 #include "AXGeometryManager.h"
 #include "AXIsolatedTree.h"
 #include "AXLogger.h"
+#include "AXTextRun.h"

 #if PLATFORM(MAC)
 #import <pal/spi/mac/HIServicesSPI.h>
@@ -464,6 +465,9 @@ void AXIsolatedObject::setProperty(AXPropertyName propertyName, AXPropertyValueV
         [](std::pair<AXID, CharacterRange>& typedValue) {
             return !typedValue.first.isValid() && !typedValue.second.location && !typedValue.second.length;
         },
+#if ENABLE(AX_THREAD_TEXT_APIS)
+        [](AXTextRuns runs) { return !runs.size(); },

AG: shouldn't the param be AXTextRuns& ?

+#endif
         [](auto&) {
             ASSERT_NOT_REACHED();
             return false;
@@ -557,6 +561,19 @@ void AXIsolatedObject::setSelectedChildren(const AccessibilityChildrenVector& se
     });
 }

+AXCoreObject* AXIsolatedObject::sibling(AXDirection direction) const
+{
+    RefPtr parent = parentObjectUnignored();
+    const auto& siblings = parent->children();
+    size_t indexOfThis = siblings.find(this);
+    if (indexOfThis == notFound)
+        return nullptr;
+
+    if (direction == AXDirection::Next)
+        return indexOfThis + 1 < siblings.size() ? siblings[indexOfThis + 1].get() : nullptr;
+    return indexOfThis > 0 ? siblings[indexOfThis - 1].get() : nullptr;
+}
+
 bool AXIsolatedObject::isDetachedFromParent()
 {
     if (parent().isValid())
@@ -971,6 +988,19 @@ int AXIsolatedObject::intAttributeValue(AXPropertyName propertyName) const
     );
 }

+#if ENABLE(AX_THREAD_TEXT_APIS)
+const AXTextRuns* AXIsolatedObject::textRuns() const
+{
+    auto entry = m_propertyMap.find(AXPropertyName::TextRuns);
+    if (entry == m_propertyMap.end())
+        return nullptr;
+    return WTF::switchOn(entry->value,
+        [] (const AXTextRuns& typedValue) -> const AXTextRuns* { return &typedValue; },
+        [] (auto&) -> const AXTextRuns* { return nullptr; }
+    );
+}
+#endif
+
 template<typename T>
 T AXIsolatedObject::getOrRetrievePropertyValue(AXPropertyName propertyName)
 {

[Tyler Wilcock]

Created attachment 469352 [details]
Patch

[Tyler Wilcock]

(In reply to Andres Gonzalez from comment #22)

> +    unsigned lastRunLength() const
> +    {
> +        if (runs.isEmpty())
> +            return 0;
> +        return runs[runs.size() - 1].text.length();
> +    }
> +    unsigned runLengthSum() const
> AG: maybe totalLength ? or just length ?
TW: Fixed, went with totalLength.

> +AXTextRuns AccessibilityRenderObject::textRuns()
>  {
>      if (auto* renderLineBreak = dynamicDowncast<RenderLineBreak>(renderer())) {
>          auto box = InlineIterator::boxFor(*renderLineBreak);
> -        return { { box->lineIndex(), makeString('\n') } };
> +        return { renderLineBreak->containingBlock(), { AXTextRun(box->lineIndex(), makeString('\n').isolatedCopy()) } };
> AG: shouldn't have to make an isolatedCopy here since this is a main thread object.
TW: Right now, every string in this method does an isolatedCopy(), since the only consumer is for caching these runs in the secondary thread.
I have a FIXME lower in this method to make this behavior configurable via parameter to the method, or we could simply not do an isolatedCopy()
here and change AXIsolatedObject::initializeProperties to loop over textRuns() and perform the isolatedCopy() at that point. But I think that's
an extra walk over every string, and an extra copy of every string? So I elected to do it this way.

I envision this might be something we re-evaluate when we introduce our AXTextManager at some point in the future. But if you have a preference
to do something for this now, happy to discuss.

> @@ -464,6 +465,9 @@ void AXIsolatedObject::setProperty(AXPropertyName propertyName, AXPropertyValueV
>          [](std::pair<AXID, CharacterRange>& typedValue) {
>              return !typedValue.first.isValid() && !typedValue.second.location && !typedValue.second.length;
>          },
> +#if ENABLE(AX_THREAD_TEXT_APIS)
> +        [](AXTextRuns runs) { return !runs.size(); },
> AG: shouldn't the param be AXTextRuns& ?
TW: Great catch! Fixed.

[Andres Gonzalez]

(In reply to Tyler Wilcock from comment #23)
> Created attachment 469352 [details]
> Patch

diff --git a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp
index f6f0622abe93..0e7539e3a8c0 100644
--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp
+++ b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp
@@ -30,6 +30,7 @@

 #include "AXIsolatedObject.h"
 #include "AXLogger.h"
+#include "AccessibilityTableRow.h"

AG: why this include ?

 #include "FrameSelection.h"
 #include "LocalFrameView.h"
 #include "Page.h"
@@ -230,22 +231,6 @@ RefPtr<AXIsolatedObject> AXIsolatedTree::objectForID(const AXID axID) const
     return axID.isValid() ? m_readerThreadNodeMap.get(axID) : nullptr;
 }

-template<typename U>
-Vector<RefPtr<AXCoreObject>> AXIsolatedTree::objectsForIDs(const U& axIDs) const
-{
-    AXTRACE("AXIsolatedTree::objectsForIDs"_s);
-    ASSERT(!isMainThread());
-
-    Vector<RefPtr<AXCoreObject>> result;
-    result.reserveInitialCapacity(axIDs.size());
-    for (auto& axID : axIDs) {
-        if (RefPtr object = objectForID(axID))
-            result.append(WTFMove(object));
-    }
-    result.shrinkToFit();
-    return result;
-}
-
 void AXIsolatedTree::generateSubtree(AccessibilityObject& axObject)
 {
     AXTRACE("AXIsolatedTree::generateSubtree"_s);
diff --git a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
index 59f19fa788f5..7e8f6178159b 100644
--- a/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
+++ b/Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.h
@@ -29,6 +29,7 @@

 #include "AXCoreObject.h"
 #include "AXTextMarker.h"
+#include "AXTextRun.h"
 #include "AXTreeStore.h"
 #include "PageIdentifier.h"
 #include "RenderStyleConstants.h"
@@ -47,6 +48,7 @@ class TextStream;
 namespace WebCore {

 class AXIsolatedObject;
+class AXGeometryManager;
 class AXObjectCache;
 class AccessibilityObject;
 class Page;
@@ -255,7 +257,7 @@ using AXPropertyValueVariant = std::variant<std::nullptr_t, AXID, String, bool,
     , RetainPtr<NSAttributedString>
 #endif
 #if ENABLE(AX_THREAD_TEXT_APIS)
-    , Vector<AXTextRun>
+    , AXTextRuns
 #endif
 >;
 using AXPropertyMap = HashMap<AXPropertyName, AXPropertyValueVariant, IntHash<AXPropertyName>, WTF::StrongEnumHashTraits<AXPropertyName>>;
@@ -322,7 +324,20 @@ public:
     WEBCORE_EXPORT RefPtr<AXIsolatedObject> focusedNode();

     RefPtr<AXIsolatedObject> objectForID(const AXID) const;
-    template<typename U> Vector<RefPtr<AXCoreObject>> objectsForIDs(const U&) const;
+    template<typename U>
+    Vector<RefPtr<AXCoreObject>> objectsForIDs(const U& axIDs) const
+    {
+        ASSERT(!isMainThread());
+
+        Vector<RefPtr<AXCoreObject>> result;
+        result.reserveInitialCapacity(axIDs.size());
+        for (const auto& axID : axIDs) {
+            if (RefPtr object = objectForID(axID))
+                result.append(WTFMove(object));
+        }
+        result.shrinkToFit();
+        return result;
+    }

AG: it is better style to have the declaration of the template in the class declaration and the impl down below as an inline if needed. I supposed you had to put it in the header because of cpps being compiled in the different compilation units, right?

     void generateSubtree(AccessibilityObject&);
     void labelCreated(AccessibilityObject&);

[Tyler Wilcock]

(In reply to Andres Gonzalez from comment #25)
> +#include "AccessibilityTableRow.h"
> 
> AG: why this include ?
TW: This include always should've been there (we typecast to AccessibilityTableRow in this file), but it was only exposed as a compilation error by adding a new cpp source file, which caused the unified builds to change and expose this bug.

>      RefPtr<AXIsolatedObject> objectForID(const AXID) const;
> -    template<typename U> Vector<RefPtr<AXCoreObject>> objectsForIDs(const
> U&) const;
> +    template<typename U>
> +    Vector<RefPtr<AXCoreObject>> objectsForIDs(const U& axIDs) const
> +    {
> +        ASSERT(!isMainThread());
> +
> +        Vector<RefPtr<AXCoreObject>> result;
> +        result.reserveInitialCapacity(axIDs.size());
> +        for (const auto& axID : axIDs) {
> +            if (RefPtr object = objectForID(axID))
> +                result.append(WTFMove(object));
> +        }
> +        result.shrinkToFit();
> +        return result;
> +    }
> 
> AG: it is better style to have the declaration of the template in the class
> declaration and the impl down below as an inline if needed. I supposed you
> had to put it in the header because of cpps being compiled in the different
> compilation units, right?
TW: Yes, exactly right! I was getting compilation errors until inlining the definition here. Spent a good while trying to avoid doing this, but was not successful, and reading online suggested this is the only way to resolve it.

[EWS]

Committed 272858@main (ff85ff126cf1): <https://commits.webkit.org/272858@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 469352 [details].