third_party/blink/renderer/modules/accessibility/ax_layout_object.cc

/*
 * Copyright (C) 2008 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.
 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
 *     its contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE 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 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 "third_party/blink/renderer/modules/accessibility/ax_layout_object.h"

#include <algorithm>
#include <memory>
#include <string>

#include "third_party/blink/renderer/core/aom/accessible_node.h"
#include "third_party/blink/renderer/core/css/counter_style_map.h"
#include "third_party/blink/renderer/core/css/css_property_names.h"
#include "third_party/blink/renderer/core/css/properties/longhands.h"
#include "third_party/blink/renderer/core/display_lock/display_lock_utilities.h"
#include "third_party/blink/renderer/core/dom/element_traversal.h"
#include "third_party/blink/renderer/core/dom/node_computed_style.h"
#include "third_party/blink/renderer/core/dom/range.h"
#include "third_party/blink/renderer/core/dom/shadow_root.h"
#include "third_party/blink/renderer/core/editing/editing_utilities.h"
#include "third_party/blink/renderer/core/events/event_util.h"
#include "third_party/blink/renderer/core/frame/frame_owner.h"
#include "third_party/blink/renderer/core/frame/local_frame.h"
#include "third_party/blink/renderer/core/frame/local_frame_view.h"
#include "third_party/blink/renderer/core/frame/settings.h"
#include "third_party/blink/renderer/core/html/canvas/html_canvas_element.h"
#include "third_party/blink/renderer/core/html/forms/html_input_element.h"
#include "third_party/blink/renderer/core/html/forms/html_label_element.h"
#include "third_party/blink/renderer/core/html/forms/html_option_element.h"
#include "third_party/blink/renderer/core/html/forms/html_select_element.h"
#include "third_party/blink/renderer/core/html/forms/html_text_area_element.h"
#include "third_party/blink/renderer/core/html/forms/labels_node_list.h"
#include "third_party/blink/renderer/core/html/html_frame_owner_element.h"
#include "third_party/blink/renderer/core/html/html_image_element.h"
#include "third_party/blink/renderer/core/html/media/html_media_element.h"
#include "third_party/blink/renderer/core/html/shadow/shadow_element_names.h"
#include "third_party/blink/renderer/core/input_type_names.h"
#include "third_party/blink/renderer/core/layout/geometry/transform_state.h"
#include "third_party/blink/renderer/core/layout/hit_test_location.h"
#include "third_party/blink/renderer/core/layout/hit_test_result.h"
#include "third_party/blink/renderer/core/layout/inline/inline_cursor.h"
#include "third_party/blink/renderer/core/layout/inline/inline_node.h"
#include "third_party/blink/renderer/core/layout/layout_box.h"
#include "third_party/blink/renderer/core/layout/layout_image.h"
#include "third_party/blink/renderer/core/layout/layout_inline.h"
#include "third_party/blink/renderer/core/layout/layout_replaced.h"
#include "third_party/blink/renderer/core/layout/layout_view.h"
#include "third_party/blink/renderer/core/layout/list/layout_list_item.h"
#include "third_party/blink/renderer/core/layout/list/list_marker.h"
#include "third_party/blink/renderer/core/layout/table/layout_table.h"
#include "third_party/blink/renderer/core/layout/table/layout_table_cell.h"
#include "third_party/blink/renderer/core/layout/table/layout_table_row.h"
#include "third_party/blink/renderer/core/layout/table/layout_table_section.h"
#include "third_party/blink/renderer/core/loader/progress_tracker.h"
#include "third_party/blink/renderer/core/mathml/mathml_element.h"
#include "third_party/blink/renderer/core/page/page.h"
#include "third_party/blink/renderer/core/paint/paint_layer.h"
#include "third_party/blink/renderer/core/paint/paint_layer_scrollable_area.h"
#include "third_party/blink/renderer/core/style/computed_style_constants.h"
#include "third_party/blink/renderer/core/svg/graphics/svg_image.h"
#include "third_party/blink/renderer/core/svg/svg_document_extensions.h"
#include "third_party/blink/renderer/core/svg/svg_g_element.h"
#include "third_party/blink/renderer/core/svg/svg_svg_element.h"
#include "third_party/blink/renderer/modules/accessibility/ax_image_map_link.h"
#include "third_party/blink/renderer/modules/accessibility/ax_inline_text_box.h"
#include "third_party/blink/renderer/modules/accessibility/ax_mock_object.h"
#include "third_party/blink/renderer/modules/accessibility/ax_object_cache_impl.h"
#include "third_party/blink/renderer/platform/bindings/exception_state.h"
#include "third_party/blink/renderer/platform/text/platform_locale.h"
#include "third_party/blink/renderer/platform/wtf/std_lib_extras.h"
#include "ui/accessibility/ax_role_properties.h"

namespace blink {

namespace {

// Return the first LayoutTableSection if maybe_table is a non-anonymous
// table. If non-null, set table_out to the containing table.
LayoutTableSection* FirstTableSection(LayoutObject* maybe_table,
                                      LayoutTable** table_out = nullptr) {
  if (auto* table = DynamicTo<LayoutTable>(maybe_table)) {
    if (table->GetNode()) {
      if (table_out) {
        *table_out = table;
      }
      return table->FirstSection();
    }
  }
  if (table_out) {
    *table_out = nullptr;
  }
  return nullptr;
}

}  // anonymous namespace

AXLayoutObject::AXLayoutObject(LayoutObject* layout_object,
                               AXObjectCacheImpl& ax_object_cache)
    : AXNodeObject(layout_object->GetNode(), ax_object_cache),
      layout_object_(layout_object) {
// TODO(aleventhal) Get correct current state of autofill.
#if DCHECK_IS_ON()
  DCHECK(layout_object_);
  layout_object_->SetHasAXObject(true);
#endif
}

AXLayoutObject::~AXLayoutObject() {
  DCHECK(IsDetached());
}

void AXLayoutObject::Trace(Visitor* visitor) const {
  visitor->Trace(layout_object_);
  AXNodeObject::Trace(visitor);
}

LayoutObject* AXLayoutObject::GetLayoutObject() const {
  return layout_object_.Get();
}

ScrollableArea* AXLayoutObject::GetScrollableAreaIfScrollable() const {
  if (IsA<Document>(GetNode())) {
    return DocumentFrameView()->LayoutViewport();
  }

  if (auto* box = DynamicTo<LayoutBox>(GetLayoutObject())) {
    PaintLayerScrollableArea* scrollable_area = box->GetScrollableArea();
    if (scrollable_area && scrollable_area->HasOverflow())
      return scrollable_area;
  }

  return nullptr;
}

static bool IsImageOrAltText(LayoutObject* layout_object, Node* node) {
  DCHECK(layout_object);
  if (layout_object->IsImage())
    return true;
  if (IsA<HTMLImageElement>(node))
    return true;
  auto* html_input_element = DynamicTo<HTMLInputElement>(node);
  if (html_input_element && html_input_element->HasFallbackContent())
    return true;
  return false;
}

static bool ShouldIgnoreListItem(Node* node) {
  DCHECK(node);

  // http://www.w3.org/TR/wai-aria/complete#presentation
  // A list item is presentational if its parent is a native list but
  // it has an explicit ARIA role set on it that's anything other than "list".
  Element* parent = FlatTreeTraversal::ParentElement(*node);
  if (!parent)
    return false;

  if (IsA<HTMLMenuElement>(*parent) || IsA<HTMLUListElement>(*parent) ||
      IsA<HTMLOListElement>(*parent)) {
    AtomicString role = AccessibleNode::GetPropertyOrARIAAttribute(
        parent, AOMStringProperty::kRole);
    if (!role.empty() && role != "list" && role != "directory")
      return true;
  }
  return false;
}

ax::mojom::blink::Role AXLayoutObject::RoleFromLayoutObjectOrNode() const {
  DCHECK(layout_object_);

  Node* node = GetNode();  // Can be null in the case of pseudo content.

  if (IsA<HTMLLIElement>(node)) {
    if (ShouldIgnoreListItem(node))
      return ax::mojom::blink::Role::kNone;
    return ax::mojom::blink::Role::kListItem;
  }

  if (layout_object_->IsListMarker()) {
    Node* list_item = layout_object_->GeneratingNode();
    if (list_item && ShouldIgnoreListItem(list_item))
      return ax::mojom::blink::Role::kNone;
    return ax::mojom::blink::Role::kListMarker;
  }

  if (layout_object_->IsListItemIncludingNG())
    return ax::mojom::blink::Role::kListItem;
  if (layout_object_->IsBR())
    return ax::mojom::blink::Role::kLineBreak;
  if (layout_object_->IsText())
    return ax::mojom::blink::Role::kStaticText;

  // Chrome exposes both table markup and table CSS as a tables, letting
  // the screen reader determine what to do for CSS tables. If this line
  // is reached, then it is not an HTML table, and therefore will only be
  // considered a data table if ARIA markup indicates it is a table.
  // Additionally, as pseudo elements don't have any structure it doesn't make
  // sense to report their table-related layout roles that could be set via the
  // display property.
  if (node && !node->IsPseudoElement()) {
    if (layout_object_->IsTable())
      return ax::mojom::blink::Role::kLayoutTable;
    if (layout_object_->IsTableSection())
      return DetermineTableSectionRole();
    if (layout_object_->IsTableRow())
      return DetermineTableRowRole();
    if (layout_object_->IsTableCell())
      return DetermineTableCellRole();
  }

  if (IsImageOrAltText(layout_object_, node)) {
    if (IsA<HTMLInputElement>(node))
      return ButtonRoleType();
    return ax::mojom::blink::Role::kImage;
  }

  if (IsA<HTMLCanvasElement>(node))
    return ax::mojom::blink::Role::kCanvas;

  if (IsA<LayoutView>(*layout_object_)) {
    return ParentObject() ? ax::mojom::blink::Role::kGroup
                          : ax::mojom::blink::Role::kRootWebArea;
  }

  if (node && node->IsSVGElement()) {
    if (layout_object_->IsSVGImage())
      return ax::mojom::blink::Role::kImage;
    if (IsA<SVGSVGElement>(node)) {
      // Exposing a nested <svg> as a group (rather than a generic container)
      // increases the likelihood that an author-provided name will be presented
      // by assistive technologies. Note that this mapping is not yet in the
      // SVG-AAM, which currently maps all <svg> elements as graphics-document.
      // See https://github.com/w3c/svg-aam/issues/18.
      return layout_object_->IsSVGRoot() ? ax::mojom::blink::Role::kSvgRoot
                                         : ax::mojom::blink::Role::kGroup;
    }
    if (layout_object_->IsSVGShape())
      return ax::mojom::blink::Role::kGraphicsSymbol;
    if (layout_object_->IsSVGForeignObject() || IsA<SVGGElement>(node)) {
      return ax::mojom::blink::Role::kGroup;
    }
    if (IsA<SVGUseElement>(node))
      return ax::mojom::blink::Role::kGraphicsObject;
  }

  if (layout_object_->IsHR())
    return ax::mojom::blink::Role::kSplitter;

  // Minimum role:
  // TODO(aleventhal) Implement all of https://github.com/w3c/html-aam/pull/454.
  if (GetElement() && !GetElement()->FastHasAttribute(html_names::kRoleAttr)) {
    if (IsPopup() != ax::mojom::blink::IsPopup::kNone) {
      return ax::mojom::blink::Role::kGroup;
    }
  }

  // Anything that needs to be exposed but doesn't have a more specific role
  // should be considered a generic container. Examples are layout blocks with
  // no node, in-page link targets, and plain elements such as a <span> with
  // an aria- property.
  return ax::mojom::blink::Role::kGenericContainer;
}

Node* AXLayoutObject::GetNodeOrContainingBlockNode() const {
  if (IsDetached())
    return nullptr;

  if (auto* list_marker = ListMarker::Get(layout_object_)) {
    // Return the originating list item node.
    return list_marker->ListItem(*layout_object_)->GetNode();
  }

  return GetNode();
}

void AXLayoutObject::Detach() {
  AXNodeObject::Detach();

#if DCHECK_IS_ON()
  if (layout_object_)
    layout_object_->SetHasAXObject(false);
#endif
  layout_object_ = nullptr;
}

bool AXLayoutObject::IsAXLayoutObject() const {
  return true;
}

//
// Check object role or purpose.
//

static bool IsLinkable(const AXObject& object) {
  if (!object.GetLayoutObject())
    return false;

  // See https://wiki.mozilla.org/Accessibility/AT-Windows-API for the elements
  // Mozilla considers linkable.
  return object.IsLink() || object.IsImage() ||
         object.GetLayoutObject()->IsText();
}

bool AXLayoutObject::IsLinked() const {
  if (!IsLinkable(*this))
    return false;

  if (auto* anchor = DynamicTo<HTMLAnchorElement>(AnchorElement()))
    return !anchor->Href().IsEmpty();
  return false;
}

bool AXLayoutObject::IsOffScreen() const {
  DCHECK(layout_object_);
  gfx::Rect content_rect =
      ToPixelSnappedRect(layout_object_->VisualRectInDocument());
  LocalFrameView* view = layout_object_->GetFrame()->View();
  gfx::Rect view_rect(gfx::Point(), view->Size());
  view_rect.Intersect(content_rect);
  return view_rect.IsEmpty();
}

bool AXLayoutObject::IsVisited() const {
  // FIXME: Is it a privacy violation to expose visited information to
  // accessibility APIs?
  return layout_object_->Style()->IsLink() &&
         layout_object_->Style()->InsideLink() ==
             EInsideLink::kInsideVisitedLink;
}

//
// Check object state.
//

// Returns true if the object is marked user-select:none
bool AXLayoutObject::IsNotUserSelectable() const {
  if (!GetLayoutObject())
    return false;

  const ComputedStyle* style = GetLayoutObject()->Style();
  if (!style)
    return false;

  return (style->UsedUserSelect() == EUserSelect::kNone);
}

//
// Whether objects are ignored, i.e. not included in the tree.
//

// Is this the anonymous placeholder for a text control?
bool AXLayoutObject::IsPlaceholder() const {
  AXObject* parent_object = ParentObject();
  if (!parent_object)
    return false;

  LayoutObject* parent_layout_object = parent_object->GetLayoutObject();
  if (!parent_layout_object || !parent_layout_object->IsTextControl()) {
    return false;
  }

  const auto* text_control_element =
      To<TextControlElement>(parent_layout_object->GetNode());
  HTMLElement* placeholder_element = text_control_element->PlaceholderElement();

  return GetElement() == placeholder_element;
}

//
// Properties of static elements.
//

ax::mojom::blink::ListStyle AXLayoutObject::GetListStyle() const {
  const LayoutObject* layout_object = GetLayoutObject();
  if (!layout_object)
    return AXNodeObject::GetListStyle();

  const ComputedStyle* computed_style = layout_object->Style();
  if (!computed_style)
    return AXNodeObject::GetListStyle();

  const StyleImage* style_image = computed_style->ListStyleImage();
  if (style_image && !style_image->ErrorOccurred())
    return ax::mojom::blink::ListStyle::kImage;

  if (RuntimeEnabledFeatures::CSSAtRuleCounterStyleSpeakAsDescriptorEnabled()) {
    if (!computed_style->ListStyleType())
      return ax::mojom::blink::ListStyle::kNone;
    if (computed_style->ListStyleType()->IsString())
      return ax::mojom::blink::ListStyle::kOther;

    DCHECK(computed_style->ListStyleType()->IsCounterStyle());
    const CounterStyle& counter_style =
        ListMarker::GetCounterStyle(*GetDocument(), *computed_style);
    switch (counter_style.EffectiveSpeakAs()) {
      case CounterStyleSpeakAs::kBullets: {
        // See |ua_counter_style_map.cc| for predefined symbolic counter styles.
        UChar symbol = counter_style.GenerateTextAlternative(0)[0];
        switch (symbol) {
          case 0x2022:
            return ax::mojom::blink::ListStyle::kDisc;
          case 0x25E6:
            return ax::mojom::blink::ListStyle::kCircle;
          case 0x25A0:
            return ax::mojom::blink::ListStyle::kSquare;
          default:
            return ax::mojom::blink::ListStyle::kOther;
        }
      }
      case CounterStyleSpeakAs::kNumbers:
        return ax::mojom::blink::ListStyle::kNumeric;
      case CounterStyleSpeakAs::kWords:
        return ax::mojom::blink::ListStyle::kOther;
      case CounterStyleSpeakAs::kAuto:
      case CounterStyleSpeakAs::kReference:
        NOTREACHED();
        return ax::mojom::blink::ListStyle::kOther;
    }
  }

  switch (ListMarker::GetListStyleCategory(*GetDocument(), *computed_style)) {
    case ListMarker::ListStyleCategory::kNone:
      return ax::mojom::blink::ListStyle::kNone;
    case ListMarker::ListStyleCategory::kSymbol: {
      const AtomicString& counter_style_name =
          computed_style->ListStyleType()->GetCounterStyleName();
      if (counter_style_name == keywords::kDisc) {
        return ax::mojom::blink::ListStyle::kDisc;
      }
      if (counter_style_name == keywords::kCircle) {
        return ax::mojom::blink::ListStyle::kCircle;
      }
      if (counter_style_name == keywords::kSquare) {
        return ax::mojom::blink::ListStyle::kSquare;
      }
      return ax::mojom::blink::ListStyle::kOther;
    }
    case ListMarker::ListStyleCategory::kLanguage: {
      const AtomicString& counter_style_name =
          computed_style->ListStyleType()->GetCounterStyleName();
      if (counter_style_name == keywords::kDecimal) {
        return ax::mojom::blink::ListStyle::kNumeric;
      }
      if (counter_style_name == "decimal-leading-zero") {
        // 'decimal-leading-zero' may be overridden by custom counter styles. We
        // return kNumeric only when we are using the predefined counter style.
        if (ListMarker::GetCounterStyle(*GetDocument(), *computed_style)
                .IsPredefined())
          return ax::mojom::blink::ListStyle::kNumeric;
      }
      return ax::mojom::blink::ListStyle::kOther;
    }
    case ListMarker::ListStyleCategory::kStaticString:
      return ax::mojom::blink::ListStyle::kOther;
  }
}

static bool ShouldUseLayoutNG(const LayoutObject& layout_object) {
  return layout_object.IsInline() &&
         layout_object.IsInLayoutNGInlineFormattingContext();
}

AXObject* AXLayoutObject::GetFirstInlineBlockOrDeepestInlineAXChildInLayoutTree(
    AXObject* start_object,
    bool first) const {
  if (!start_object)
    return nullptr;

  // Return the deepest last child that is included.
  // Uses LayoutTreeBuildTraversaler to get children, in order to avoid getting
  // children unconnected to the line, e.g. via aria-owns. Doing this first also
  // avoids the issue that |start_object| may not be included in the tree.
  AXObject* result = start_object;
  Node* current_node = start_object->GetNode();
  while (current_node) {
    // If we find a node that is inline-block, we want to return it rather than
    // getting the deepest child for that. This is because these are now always
    // being included in the tree and the Next/PreviousOnLine could be set on
    // the inline-block element. We exclude list markers since those technically
    // fulfill the inline-block condition.
    AXObject* ax_object = start_object->AXObjectCache().Get(current_node);
    if (ax_object && ax_object->AccessibilityIsIncludedInTree() &&
        !current_node->IsMarkerPseudoElement()) {
      if (ax_object->GetLayoutObject() &&
          ax_object->GetLayoutObject()->IsInline() &&
          ax_object->GetLayoutObject()->IsAtomicInlineLevel()) {
        return ax_object;
      }
    }

    current_node = first ? LayoutTreeBuilderTraversal::FirstChild(*current_node)
                         : LayoutTreeBuilderTraversal::LastChild(*current_node);
    if (!current_node)
      break;

    AXObject* tentative_child = start_object->AXObjectCache().Get(current_node);

    if (tentative_child && tentative_child->AccessibilityIsIncludedInTree()) {
      result = tentative_child;
    }
  }

  // Have reached the end of LayoutTreeBuilderTraversal. From here on, traverse
  // AXObjects to get deepest descendant of pseudo element or static text,
  // such as an AXInlineTextBox.

  // Relevant static text or pseudo element is always included.
  if (!result->AccessibilityIsIncludedInTree())
    return nullptr;

  // Already a leaf: return current result.
  if (!result->ChildCountIncludingIgnored())
    return result;

  // Get deepest AXObject descendant.
  return first ? result->DeepestFirstChildIncludingIgnored()
               : result->DeepestLastChildIncludingIgnored();
}

AXObject* AXLayoutObject::NextOnLine() const {
  // If this is the last object on the line, nullptr is returned. Otherwise, all
  // AXLayoutObjects, regardless of role and tree depth, are connected to the
  // next inline text box on the same line. If there is no inline text box, they
  // are connected to the next leaf AXObject.
  DCHECK(!IsDetached());

  const LayoutObject* layout_object = GetLayoutObject();
  DCHECK(layout_object);

  if (DisplayLockUtilities::LockedAncestorPreventingPaint(*layout_object)) {
    return nullptr;
  }

  if (layout_object->IsBoxListMarkerIncludingNG()) {
    // A list marker should be followed by a list item on the same line.
    // Note that pseudo content is always included in the tree, so
    // NextSiblingIncludingIgnored() will succeed.
    if (AccessibilityIsIncludedInTree()) {
      return GetFirstInlineBlockOrDeepestInlineAXChildInLayoutTree(
          NextSiblingIncludingIgnored(), true);
    }
    return nullptr;
  }

  if (!ShouldUseLayoutNG(*layout_object)) {
    return nullptr;
  }

  if (!layout_object->IsInLayoutNGInlineFormattingContext()) {
    return nullptr;
  }

  InlineCursor cursor;
  while (true) {
    // Try to get cursor for layout_object.
    cursor.MoveToIncludingCulledInline(*layout_object);
    if (cursor)
      break;

    // No cursor found: will try getting the cursor from the last layout child.
    // This can happen on an inline element.
    LayoutObject* layout_child = layout_object->SlowLastChild();
    if (!layout_child)
      break;

    layout_object = layout_child;
  }

  // Found cursor: use it to find next inline leaf.
  if (cursor) {
    cursor.MoveToNextInlineLeafOnLine();
    while (cursor) {
      LayoutObject* runner_layout_object = cursor.CurrentMutableLayoutObject();
      DCHECK(runner_layout_object);
      AXObject* result = AXObjectCache().Get(runner_layout_object);

      // We want to continue searching for the next inline leaf if the
      // current one is inert or aria-hidden.
      // We don't necessarily want to keep searching in the case of any ignored
      // node, because we anticipate that there might be scenarios where a
      // descendant of the ignored node is not ignored and would be returned by
      // the call to `GetFirstInlineBlockOrDeepestInlineAXChildInLayoutTree`
      bool should_keep_looking =
          result ? result->IsInert() || result->IsAriaHidden() : false;

      result =
          GetFirstInlineBlockOrDeepestInlineAXChildInLayoutTree(result, true);
      if (result && !should_keep_looking) {
        return result;
      }

      if (!should_keep_looking) {
        break;
      }
      cursor.MoveToNextInlineLeafOnLine();
    }
  }

  // We need to ensure that we are at the end of our parent layout object
  // before attempting to connect to the next AXObject that is on the same
  // line as its first line.
  if (layout_object->NextSibling())
    return nullptr;  // Not at end of parent layout object.
  // Fallback: Use AX parent's next on line.
  AXObject* ax_parent = ParentObject();
  DCHECK(ax_parent);
  AXObject* ax_result = ax_parent->NextOnLine();
  if (!ax_result)
    return nullptr;

  if (!AXObjectCache().IsAriaOwned(this) && ax_result->ParentObject() == this) {
    // NextOnLine() must not point to a child of the current object.
    // Because inline objects try to return a result from their
    // parents, using a descendant can cause a previous position to be
    // reused, which appears as a loop in the nextOnLine data, and
    // can cause an infinite loop in consumers of the nextOnLine data.
    return nullptr;
  }

  return ax_result;
}

AXObject* AXLayoutObject::PreviousOnLine() const {
  // If this is the first object on the line, nullptr is returned. Otherwise,
  // all AXLayoutObjects, regardless of role and tree depth, are connected to
  // the previous inline text box on the same line. If there is no inline text
  // box, they are connected to the previous leaf AXObject.
  DCHECK(!IsDetached());

  const LayoutObject* layout_object = GetLayoutObject();
  DCHECK(layout_object);
  if (!ShouldUseLayoutNG(*layout_object)) {
    return nullptr;
  }

  if (DisplayLockUtilities::LockedAncestorPreventingPaint(*layout_object)) {
    return nullptr;
  }

  AXObject* previous_sibling = AccessibilityIsIncludedInTree()
                                   ? PreviousSiblingIncludingIgnored()
                                   : nullptr;
  if (previous_sibling && previous_sibling->GetLayoutObject() &&
      previous_sibling->GetLayoutObject()->IsLayoutOutsideListMarker()) {
    // A list item should be preceded by a list marker on the same line.
    return GetFirstInlineBlockOrDeepestInlineAXChildInLayoutTree(
        previous_sibling, false);
  }

  if (layout_object->IsBoxListMarkerIncludingNG() ||
      !layout_object->IsInLayoutNGInlineFormattingContext()) {
    return nullptr;
  }

  InlineCursor cursor;
  while (true) {
    // Try to get cursor for layout_object.
    cursor.MoveToIncludingCulledInline(*layout_object);
    if (cursor)
      break;

    // No cursor found: will try get cursor from first layout child.
    // This can happen on an inline element.
    LayoutObject* layout_child = layout_object->SlowFirstChild();
    if (!layout_child)
      break;

    layout_object = layout_child;
  }

  // Found cursor: use it to find previous inline leaf.
  if (cursor) {
    cursor.MoveToPreviousInlineLeafOnLine();
    while (cursor) {
      LayoutObject* runner_layout_object = cursor.CurrentMutableLayoutObject();
      DCHECK(runner_layout_object);
      AXObject* result = AXObjectCache().Get(runner_layout_object);

      // We want to continue searching for the next inline leaf if the
      // current one is inert or aria-hidden.
      // We don't necessarily want to keep searching in the case of any ignored
      // node, because we anticipate that there might be scenarios where a
      // descendant of the ignored node is not ignored and would be returned by
      // the call to `GetFirstInlineBlockOrDeepestInlineAXChildInLayoutTree`
      bool should_keep_looking =
          result ? result->IsInert() || result->IsAriaHidden() : false;

      result =
          GetFirstInlineBlockOrDeepestInlineAXChildInLayoutTree(result, false);
      if (result && !should_keep_looking) {
        return result;
      }

      // We want to continue searching for the previous inline leaf if the
      // current one is inert.
      if (!should_keep_looking) {
        break;
      }
      cursor.MoveToPreviousInlineLeafOnLine();
    }
  }

  // We need to ensure that we are at the start of our parent layout object
  // before attempting to connect to the previous AXObject that is on the same
  // line as its first line.
  if (layout_object->PreviousSibling())
    return nullptr;  // Not at start of parent layout object.

  // Fallback: Use AX parent's previous on line.
  AXObject* ax_parent = ParentObject();
  DCHECK(ax_parent);
  AXObject* ax_result = ax_parent->PreviousOnLine();
  if (!ax_result)
    return nullptr;

  if (!AXObjectCache().IsAriaOwned(this) && ax_result->ParentObject() == this) {
    // PreviousOnLine() must not point to a child of the current object.
    // Because inline objects without try to return a result from their
    // parents, using a descendant can cause a previous position to be
    // reused, which appears as a loop in the previousOnLine data, and
    // can cause an infinite loop in consumers of the previousOnLine data.
    return nullptr;
  }

  return ax_result;
}

//
// Properties of interactive elements.
//

String AXLayoutObject::TextAlternative(
    bool recursive,
    const AXObject* aria_label_or_description_root,
    AXObjectSet& visited,
    ax::mojom::blink::NameFrom& name_from,
    AXRelatedObjectVector* related_objects,
    NameSources* name_sources) const {
  if (layout_object_) {
    std::optional<String> text_alternative = GetCSSAltText(GetElement());
    bool found_text_alternative = false;
    if (text_alternative) {
      if (name_sources) {
        name_sources->push_back(NameSource(false));
        name_sources->back().type = ax::mojom::blink::NameFrom::kAttribute;
        name_sources->back().text = text_alternative.value();
      }
      return text_alternative.value();
    }
    if (layout_object_->IsBR()) {
      text_alternative = String("\n");
      found_text_alternative = true;
    } else if (layout_object_->IsText() &&
               (!recursive || !layout_object_->IsCounter())) {
      auto* layout_text = To<LayoutText>(layout_object_.Get());
      String visible_text = layout_text->PlainText();  // Actual rendered text.
      // If no text boxes we assume this is unrendered end-of-line whitespace.
      // TODO find robust way to deterministically detect end-of-line space.
      if (visible_text.empty()) {
        // No visible rendered text -- must be whitespace.
        // Either it is useful whitespace for separating words or not.
        if (layout_text->IsAllCollapsibleWhitespace()) {
          if (LastKnownIsIgnoredValue())
            return "";
          // If no textboxes, this was whitespace at the line's end.
          text_alternative = " ";
        } else {
          text_alternative = layout_text->TransformedText();
        }
      } else {
        text_alternative = visible_text;
      }
      found_text_alternative = true;
    } else if (!recursive) {
      if (ListMarker* marker = ListMarker::Get(layout_object_)) {
        text_alternative = marker->TextAlternative(*layout_object_);
        found_text_alternative = true;
      }
    }

    if (found_text_alternative) {
      name_from = ax::mojom::blink::NameFrom::kContents;
      if (name_sources) {
        name_sources->push_back(NameSource(false));
        name_sources->back().type = name_from;
        name_sources->back().text = text_alternative.value();
      }
      // Ensure that text nodes count toward
      // kMaxDescendantsForTextAlternativeComputation when calculating the name
      // for their direct parent (see AXNodeObject::TextFromDescendants).
      visited.insert(this);
      return text_alternative.value();
    }
  }

  return AXNodeObject::TextAlternative(
      recursive, aria_label_or_description_root, visited, name_from,
      related_objects, name_sources);
}

//
// Hit testing.
//

AXObject* AXLayoutObject::AccessibilityHitTest(const gfx::Point& point) const {
  // Must be called for the document's root or a popup's root.
  if (!IsA<Document>(GetNode()) || !layout_object_) {
    return nullptr;
  }

  // Must be called with lifecycle >= pre-paint clean
  DCHECK_GE(GetDocument()->Lifecycle().GetState(),
            DocumentLifecycle::kPrePaintClean);

  DCHECK(layout_object_->IsLayoutView());
  PaintLayer* layer = To<LayoutBox>(layout_object_.Get())->Layer();
  DCHECK(layer);

  HitTestRequest request(HitTestRequest::kReadOnly | HitTestRequest::kActive);
  HitTestLocation location(point);
  HitTestResult hit_test_result = HitTestResult(request, location);
  layer->HitTest(location, hit_test_result, PhysicalRect(InfiniteIntRect()));

  Node* node = hit_test_result.InnerNode();
  if (!node)
    return nullptr;

  if (auto* area = DynamicTo<HTMLAreaElement>(node))
    return AccessibilityImageMapHitTest(area, point);

  if (auto* option = DynamicTo<HTMLOptionElement>(node)) {
    node = option->OwnerSelectElement();
    if (!node)
      return nullptr;
  }

  // If |node| is in a user-agent shadow tree, reassign it as the host to hide
  // details in the shadow tree. Previously this was implemented by using
  // Retargeting (https://dom.spec.whatwg.org/#retarget), but this caused
  // elements inside regular shadow DOMs to be ignored by screen reader. See
  // crbug.com/1111800 and crbug.com/1048959.
  const TreeScope& tree_scope = node->GetTreeScope();
  if (auto* shadow_root = DynamicTo<ShadowRoot>(tree_scope.RootNode())) {
    if (shadow_root->IsUserAgent())
      node = &shadow_root->host();
  }

  LayoutObject* obj = node->GetLayoutObject();
  AXObject* result = AXObjectCache().Get(obj);
  if (!result)
    return nullptr;
  result->UpdateChildrenIfNecessary();

  // Allow the element to perform any hit-testing it might need to do to reach
  // non-layout children.
  result = result->ElementAccessibilityHitTest(point);

  while (result && result->AccessibilityIsIgnored()) {
    // If this element is the label of a control, a hit test should return the
    // control. The label is ignored because it's already reflected in the name.
    if (auto* label = DynamicTo<HTMLLabelElement>(result->GetNode())) {
      if (HTMLElement* control = label->control()) {
        if (AXObject* ax_control = AXObjectCache().Get(control)) {
          return ax_control;
        }
      }
    }

    result = result->ParentObject();
  }

  return result;
}

//
// DOM and layout tree access.
//

Document* AXLayoutObject::GetDocument() const {
  if (!GetLayoutObject())
    return nullptr;
  return &GetLayoutObject()->GetDocument();
}

void AXLayoutObject::HandleAutofillSuggestionAvailabilityChanged(
    WebAXAutofillSuggestionAvailability suggestion_availability) {
  // Autofill suggestion availability is stored in AXObjectCache.
  AXObjectCache().SetAutofillSuggestionAvailability(AXObjectID(),
                                                    suggestion_availability);
}

unsigned AXLayoutObject::ColumnCount() const {
  if (AriaRoleAttribute() != ax::mojom::blink::Role::kUnknown)
    return AXNodeObject::ColumnCount();

  if (const auto* table = DynamicTo<LayoutTable>(GetLayoutObject())) {
    return table->EffectiveColumnCount();
  }

  return AXNodeObject::ColumnCount();
}

unsigned AXLayoutObject::RowCount() const {
  if (AriaRoleAttribute() != ax::mojom::blink::Role::kUnknown)
    return AXNodeObject::RowCount();

  LayoutTable* table;
  auto* table_section = FirstTableSection(GetLayoutObject(), &table);
  if (!table_section)
    return AXNodeObject::RowCount();

  unsigned row_count = 0;
  while (table_section) {
    row_count += table_section->NumRows();
    table_section = table->NextSection(table_section, kSkipEmptySections);
  }
  return row_count;
}

unsigned AXLayoutObject::ColumnIndex() const {
  auto* cell = DynamicTo<LayoutTableCell>(GetLayoutObject());
  if (cell && cell->GetNode()) {
    return cell->Table()->AbsoluteColumnToEffectiveColumn(
        cell->AbsoluteColumnIndex());
  }

  return AXNodeObject::ColumnIndex();
}

unsigned AXLayoutObject::RowIndex() const {
  LayoutObject* layout_object = GetLayoutObject();
  if (!layout_object || !layout_object->GetNode())
    return AXNodeObject::RowIndex();

  unsigned row_index = 0;
  const LayoutTableSection* row_section = nullptr;
  const LayoutTable* table = nullptr;
  if (const auto* row = DynamicTo<LayoutTableRow>(layout_object)) {
    row_index = row->RowIndex();
    row_section = row->Section();
    table = row->Table();
  } else if (const auto* cell = DynamicTo<LayoutTableCell>(layout_object)) {
    row_index = cell->RowIndex();
    row_section = cell->Section();
    table = cell->Table();
  } else {
    return AXNodeObject::RowIndex();
  }

  if (!table || !row_section)
    return AXNodeObject::RowIndex();

  // Since our table might have multiple sections, we have to offset our row
  // appropriately.
  const LayoutTableSection* section = table->FirstSection();
  while (section && section != row_section) {
    row_index += section->NumRows();
    section = table->NextSection(section, kSkipEmptySections);
  }

  return row_index;
}

unsigned AXLayoutObject::ColumnSpan() const {
  auto* cell = DynamicTo<LayoutTableCell>(GetLayoutObject());
  if (!cell) {
    return AXNodeObject::ColumnSpan();
  }

  LayoutTable* table = cell->Table();
  unsigned absolute_first_col = cell->AbsoluteColumnIndex();
  unsigned absolute_last_col = absolute_first_col + cell->ColSpan() - 1;
  unsigned effective_first_col =
      table->AbsoluteColumnToEffectiveColumn(absolute_first_col);
  unsigned effective_last_col =
      table->AbsoluteColumnToEffectiveColumn(absolute_last_col);
  return effective_last_col - effective_first_col + 1;
}

unsigned AXLayoutObject::RowSpan() const {
  auto* cell = DynamicTo<LayoutTableCell>(GetLayoutObject());
  return cell ? cell->ResolvedRowSpan() : AXNodeObject::RowSpan();
}

ax::mojom::blink::SortDirection AXLayoutObject::GetSortDirection() const {
  if (RoleValue() != ax::mojom::blink::Role::kRowHeader &&
      RoleValue() != ax::mojom::blink::Role::kColumnHeader) {
    return ax::mojom::blink::SortDirection::kNone;
  }

  const AtomicString& aria_sort =
      GetAOMPropertyOrARIAAttribute(AOMStringProperty::kSort);
  if (aria_sort.empty())
    return ax::mojom::blink::SortDirection::kNone;
  if (EqualIgnoringASCIICase(aria_sort, "none"))
    return ax::mojom::blink::SortDirection::kNone;
  if (EqualIgnoringASCIICase(aria_sort, "ascending"))
    return ax::mojom::blink::SortDirection::kAscending;
  if (EqualIgnoringASCIICase(aria_sort, "descending"))
    return ax::mojom::blink::SortDirection::kDescending;

  // Technically, illegal values should be exposed as is, but this does
  // not seem to be worth the implementation effort at this time.
  return ax::mojom::blink::SortDirection::kOther;
}

AXObject* AXLayoutObject::CellForColumnAndRow(unsigned target_column_index,
                                              unsigned target_row_index) const {
  LayoutTable* table;
  auto* table_section = FirstTableSection(GetLayoutObject(), &table);
  if (!table_section) {
    return AXNodeObject::CellForColumnAndRow(target_column_index,
                                             target_row_index);
  }

  unsigned row_offset = 0;
  while (table_section) {
    // Iterate backwards through the rows in case the desired cell has a rowspan
    // and exists in a previous row.
    for (LayoutTableRow* row = table_section->LastRow(); row;
         row = row->PreviousRow()) {
      unsigned row_index = row->RowIndex() + row_offset;
      for (LayoutTableCell* cell = row->LastCell(); cell;
           cell = cell->PreviousCell()) {
        unsigned absolute_first_col = cell->AbsoluteColumnIndex();
        unsigned absolute_last_col = absolute_first_col + cell->ColSpan() - 1;
        unsigned effective_first_col =
            table->AbsoluteColumnToEffectiveColumn(absolute_first_col);
        unsigned effective_last_col =
            table->AbsoluteColumnToEffectiveColumn(absolute_last_col);
        unsigned row_span = cell->ResolvedRowSpan();
        if (target_column_index >= effective_first_col &&
            target_column_index <= effective_last_col &&
            target_row_index >= row_index &&
            target_row_index < row_index + row_span) {
          return AXObjectCache().Get(cell);
        }
      }
    }

    row_offset += table_section->NumRows();
    table_section = table->NextSection(table_section, kSkipEmptySections);
  }

  return nullptr;
}

bool AXLayoutObject::FindAllTableCellsWithRole(ax::mojom::blink::Role role,
                                               AXObjectVector& cells) const {
  LayoutTable* table;
  auto* table_section = FirstTableSection(GetLayoutObject(), &table);
  if (!table_section) {
    return false;
  }

  while (table_section) {
    for (LayoutTableRow* row = table_section->FirstRow(); row;
         row = row->NextRow()) {
      for (LayoutTableCell* cell = row->FirstCell(); cell;
           cell = cell->NextCell()) {
        AXObject* ax_cell = AXObjectCache().Get(cell);
        if (ax_cell && ax_cell->RoleValue() == role)
          cells.push_back(ax_cell);
      }
    }

    table_section = table->NextSection(table_section, kSkipEmptySections);
  }

  return true;
}

void AXLayoutObject::ColumnHeaders(AXObjectVector& headers) const {
  if (!FindAllTableCellsWithRole(ax::mojom::blink::Role::kColumnHeader,
                                 headers)) {
    AXNodeObject::ColumnHeaders(headers);
  }
}

void AXLayoutObject::RowHeaders(AXObjectVector& headers) const {
  if (!FindAllTableCellsWithRole(ax::mojom::blink::Role::kRowHeader, headers))
    AXNodeObject::RowHeaders(headers);
}

AXObject* AXLayoutObject::HeaderObject() const {
  auto* row = DynamicTo<LayoutTableRow>(GetLayoutObject());
  if (!row) {
    return nullptr;
  }

  for (LayoutTableCell* cell = row->FirstCell(); cell;
       cell = cell->NextCell()) {
    AXObject* ax_cell = cell ? AXObjectCache().Get(cell) : nullptr;
    if (ax_cell && ax_cell->RoleValue() == ax::mojom::blink::Role::kRowHeader)
      return ax_cell;
  }

  return nullptr;
}

void AXLayoutObject::GetWordBoundaries(Vector<int>& word_starts,
                                       Vector<int>& word_ends) const {
  if (!layout_object_ || !layout_object_->IsListMarker()) {
    return;
  }

  String text_alternative;
  if (ListMarker* marker = ListMarker::Get(layout_object_)) {
    text_alternative = marker->TextAlternative(*layout_object_);
  }
  if (text_alternative.ContainsOnlyWhitespaceOrEmpty())
    return;

  Vector<AbstractInlineTextBox::WordBoundaries> boundaries;
  AbstractInlineTextBox::GetWordBoundariesForText(boundaries, text_alternative);
  word_starts.reserve(boundaries.size());
  word_ends.reserve(boundaries.size());
  for (const auto& boundary : boundaries) {
    word_starts.push_back(boundary.start_index);
    word_ends.push_back(boundary.end_index);
  }
}

//
// Private.
//

AXObject* AXLayoutObject::AccessibilityImageMapHitTest(
    HTMLAreaElement* area,
    const gfx::Point& point) const {
  if (!area)
    return nullptr;

  AXObject* parent = AXObjectCache().Get(area->ImageElement());
  if (!parent)
    return nullptr;

  PhysicalOffset physical_point(point);
  for (const auto& child : parent->ChildrenIncludingIgnored()) {
    if (child->GetBoundsInFrameCoordinates().Contains(physical_point)) {
      return child.Get();
    }
  }

  return nullptr;
}

}  // namespace blink