// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "services/accessibility/android/ax_tree_source_android.h"

#include <memory>
#include <stack>
#include <string>
#include <utility>

#include "base/check.h"
#include "base/containers/adapters.h"
#include "base/dcheck_is_on.h"
#include "base/memory/raw_ptr.h"
#include "services/accessibility/android/accessibility_node_info_data_wrapper.h"
#include "services/accessibility/android/accessibility_window_info_data_wrapper.h"
#include "services/accessibility/android/android_accessibility_util.h"
#include "services/accessibility/android/auto_complete_handler.h"
#include "services/accessibility/android/drawer_layout_handler.h"
#include "services/accessibility/android/pane_title_handler.h"
#include "services/accessibility/android/public/mojom/accessibility_helper.mojom-shared.h"
#include "ui/accessibility/ax_enums.mojom.h"
#include "ui/accessibility/ax_tree_source_checker.h"
#include "ui/gfx/geometry/rect.h"

namespace ax::android {

using AXBooleanProperty = mojom::AccessibilityBooleanProperty;
using AXEventData = mojom::AccessibilityEventData;
using AXEventType = mojom::AccessibilityEventType;
using AXIntProperty = mojom::AccessibilityIntProperty;
using AXIntListProperty = mojom::AccessibilityIntListProperty;
using AXNodeInfoData = mojom::AccessibilityNodeInfoData;
using AXWindowBooleanProperty = mojom::AccessibilityWindowBooleanProperty;
using AXWindowInfoData = mojom::AccessibilityWindowInfoData;
using AXWindowIntListProperty = mojom::AccessibilityWindowIntListProperty;

// TODO(hirokisato): Enable AXTreeAndroidSerializer's |crash_on_error| once
// Android becomes able to send reliable trees.
AXTreeSourceAndroid::AXTreeSourceAndroid(
    Delegate* delegate,
    std::unique_ptr<SerializationDelegate> serialization_delegate,
    aura::Window* window)
    : current_tree_serializer_(
          new AXTreeAndroidSerializer(this, DCHECK_IS_ON())),
      is_notification_(false),
      is_input_method_window_(false),
      window_(window),
      delegate_(delegate),
      serialization_delegate_(std::move(serialization_delegate)) {
  CHECK(serialization_delegate_);
  serialization_delegate_->BindTree(this);
}

AXTreeSourceAndroid::~AXTreeSourceAndroid() {
  Reset();
}

void AXTreeSourceAndroid::NotifyAccessibilityEvent(AXEventData* event_data) {
  root_id_.reset();
  DCHECK(event_data);

  NotifyAccessibilityEventInternal(*event_data);

  // Clear maps in order to prevent invalid access from dead pointers.
  tree_map_.clear();
  parent_map_.clear();
  computed_bounds_.clear();
}

void AXTreeSourceAndroid::NotifyActionResult(const ui::AXActionData& data,
                                             bool result) {
  GetAutomationEventRouter()->DispatchActionResult(data, result);
}

void AXTreeSourceAndroid::NotifyGetTextLocationDataResult(
    const ui::AXActionData& data,
    const std::optional<gfx::Rect>& rect) {
  GetAutomationEventRouter()->DispatchGetTextLocationDataResult(data, rect);
}

bool AXTreeSourceAndroid::UseFullFocusMode() const {
  return delegate_->UseFullFocusMode();
}

void AXTreeSourceAndroid::InvalidateTree() {
  current_tree_serializer_->Reset();
}

bool AXTreeSourceAndroid::IsRootOfNodeTree(int32_t id) const {
  const auto& node_it = tree_map_.find(id);
  if (node_it == tree_map_.end()) {
    return false;
  }

  if (!node_it->second->IsNode()) {
    return false;
  }

  const auto& parent_it = parent_map_.find(id);
  if (parent_it == parent_map_.end()) {
    return true;
  }

  const auto& parent_tree_it = tree_map_.find(parent_it->second);
  CHECK(parent_tree_it != tree_map_.end());
  return !parent_tree_it->second->IsNode();
}

void AXTreeSourceAndroid::SetVirtualNode(
    int32_t parent_id,
    std::unique_ptr<AccessibilityInfoDataWrapper> child) {
  auto* parent_node = GetFromId(parent_id);
  // TODO support any node as a parent, not limiting to a window.
  CHECK(parent_node);
  CHECK(parent_node->GetWindow());

  int32_t node_id = child->GetId();
  tree_map_[node_id] = std::move(child);
  parent_map_[node_id] = parent_node->GetId();
  static_cast<AccessibilityWindowInfoDataWrapper*>(parent_node)
      ->AddVirtualChild(node_id);
}

AccessibilityInfoDataWrapper* AXTreeSourceAndroid::GetFirstImportantAncestor(
    AccessibilityInfoDataWrapper* info_data) const {
  AccessibilityInfoDataWrapper* parent = GetParent(info_data);
  while (parent && parent->IsNode() && !parent->IsImportantInAndroid()) {
    parent = GetParent(parent);
  }
  return parent;
}

AccessibilityInfoDataWrapper*
AXTreeSourceAndroid::GetFirstAccessibilityFocusableAncestor(
    AccessibilityInfoDataWrapper* info_data) const {
  AccessibilityInfoDataWrapper* node = info_data;
  while (node && !node->IsAccessibilityFocusableContainer()) {
    node = GetParent(node);
  }
  return node;
}

bool AXTreeSourceAndroid::GetTreeData(ui::AXTreeData* data) const {
  data->tree_id = ax_tree_id();
  if (android_focused_id_.has_value()) {
    data->focus_id = *android_focused_id_;
  }
  return true;
}

AccessibilityInfoDataWrapper* AXTreeSourceAndroid::GetRoot() const {
  return root_id_.has_value() ? GetFromId(*root_id_) : nullptr;
}

AccessibilityInfoDataWrapper* AXTreeSourceAndroid::GetFromId(int32_t id) const {
  auto it = tree_map_.find(id);
  if (it == tree_map_.end()) {
    return nullptr;
  }
  return it->second.get();
}

AccessibilityInfoDataWrapper* AXTreeSourceAndroid::GetParent(
    AccessibilityInfoDataWrapper* info_data) const {
  if (!info_data) {
    return nullptr;
  }
  auto it = parent_map_.find(info_data->GetId());
  if (it != parent_map_.end()) {
    return GetFromId(it->second);
  }
  return nullptr;
}

void AXTreeSourceAndroid::SerializeNode(AccessibilityInfoDataWrapper* info_data,
                                        ui::AXNodeData* out_data) const {
  if (!info_data) {
    return;
  }

  info_data->Serialize(out_data);

  const auto& itr = hooks_.find(info_data->GetId());
  if (itr != hooks_.end()) {
    itr->second->PostSerializeNode(out_data);
  }
}

void AXTreeSourceAndroid::BuildNodeMap(const AXEventData& event_data) {
  // Prepare the wrapper objects of mojom data from Android.
  CHECK(event_data.window_data);
  root_id_ = event_data.window_data->at(0)->window_id;
  for (const auto& window_ptr : *event_data.window_data) {
    int32_t window_id = window_ptr->window_id;
    int32_t root_node_id = window_ptr->root_node_id;
    AXWindowInfoData* window = window_ptr.get();
    if (root_node_id) {
      parent_map_[root_node_id] = window_id;
    }

    tree_map_[window_id] =
        std::make_unique<AccessibilityWindowInfoDataWrapper>(this, window);

    std::vector<int32_t> children;
    if (GetProperty(window->int_list_properties,
                    AXWindowIntListProperty::CHILD_WINDOW_IDS, &children)) {
      for (const int32_t child : children) {
        DCHECK(child != root_id_);
        parent_map_[child] = window_id;
      }
    }
  }

  for (const auto& node_ptr : event_data.node_data) {
    int32_t node_id = node_ptr->id;
    AXNodeInfoData* node = node_ptr.get();
    tree_map_[node_id] =
        std::make_unique<AccessibilityNodeInfoDataWrapper>(this, node);

    std::vector<int32_t> children;
    if (GetProperty(node_ptr.get()->int_list_properties,
                    AXIntListProperty::CHILD_NODE_IDS, &children)) {
      for (const int32_t child : children) {
        parent_map_[child] = node_id;
      }
    }
  }
}

void AXTreeSourceAndroid::NotifyAccessibilityEventInternal(
    const AXEventData& event_data) {
  if (window_id_ != event_data.window_id) {
    // Root window id is changed. Resetting variables that depends on id.
    android_focused_id_.reset();
    hooks_.clear();
    window_id_ = event_data.window_id;
  }
  is_notification_ = event_data.notification_key.has_value();
  if (is_notification_) {
    notification_key_ = event_data.notification_key;
  }
  is_input_method_window_ = event_data.is_input_method_window;

  BuildNodeMap(event_data);

  // Compute each node's bounds, based on its descendants.
  // Assuming |nodeData| is in pre-order, compute cached bounds in post-order to
  // avoid an O(n^2) amount of work as the computed bounds uses descendant
  // bounds.
  for (int i = event_data.node_data.size() - 1; i >= 0; --i) {
    int32_t id = event_data.node_data[i]->id;
    computed_bounds_[id] = ComputeEnclosingBounds(tree_map_[id].get());
  }
  for (int i = event_data.window_data->size() - 1; i >= 0; --i) {
    int32_t id = event_data.window_data->at(i)->window_id;
    computed_bounds_[id] = ComputeEnclosingBounds(tree_map_[id].get());
  }

  if (!UpdateAndroidFocusedId(event_data)) {
    // Exit this function if the focused node doesn't exist nor isn't visible.
    return;
  }

  AccessibilityInfoDataWrapper* const source_node =
      GetFromId(event_data.source_id);

  std::vector<int32_t> update_ids = ProcessHooksOnEvent(event_data);

  // Prep the event and send it to automation.
  AccessibilityInfoDataWrapper* focused_node =
      android_focused_id_.has_value() ? GetFromId(*android_focused_id_)
                                      : nullptr;
  std::vector<ui::AXEvent> events;
  const std::optional<ax::mojom::Event> event_type =
      ToAXEvent(event_data.event_type, source_node, focused_node);
  if (event_type) {
    ui::AXEvent event;
    event.event_type = event_type.value();
    event.id = event_data.source_id;

    int event_from_action;
    if (GetProperty(event_data.int_properties,
                    ax::android::mojom::AccessibilityEventIntProperty::ACTION,
                    &event_from_action)) {
      event.event_from = ax::mojom::EventFrom::kAction;

      event.event_from_action = ConvertToChromeAction(
          static_cast<mojom::AccessibilityActionType>(event_from_action));
    }

    events.push_back(std::move(event));
  }

  if (event_data.event_type == AXEventType::WINDOW_STATE_CHANGED) {
    // On event type of WINDOW_STATE_CHANGED, update the entire tree so that
    // window location is correctly calculated.
    update_ids.push_back(*root_id_);
  } else if (!UseFullFocusMode()) {
    update_ids.push_back(event_data.source_id);
  } else {
    // Otherwise, update subtree under the event source.
    // If the event source is ignored, it's possible that the name is used by
    // ancestor.
    AccessibilityInfoDataWrapper* parent =
        GetFirstAccessibilityFocusableAncestor(source_node);
    update_ids.push_back(parent ? parent->GetId() : event_data.source_id);
  }

  for (const int32_t update_id : update_ids) {
    current_tree_serializer_->MarkSubtreeDirty(update_id);
  }

  // Serialize updates in the reverse order of |update_ids|.
  // Updates from Android event first as this contains the entire tree
  // information, including focus.
  std::vector<ui::AXTreeUpdate> updates;
  for (const int32_t update_id : base::Reversed(update_ids)) {
    AccessibilityInfoDataWrapper* update_root = GetFromId(update_id);
    if (!update_root) {
      LOG(ERROR) << "Update root node doesn't exist, id=" << update_id;
      continue;
    }
    ui::AXTreeUpdate update;
    if (!current_tree_serializer_->SerializeChanges(update_root, &update)) {
      std::string error_string;
      ui::AXTreeSourceChecker<AccessibilityInfoDataWrapper*> checker(this);
      checker.CheckAndGetErrorString(&error_string);

      LOG(ERROR) << "Unable to serialize accessibility event\n"
                 << "Error: " << error_string << "\n"
                 << "Update: " << update.ToString();
    } else {
      updates.push_back(std::move(update));
    }
  }

  GetAutomationEventRouter()->DispatchAccessibilityEvents(
      ax_tree_id(), std::move(updates), gfx::Point(), std::move(events));
}

extensions::AutomationEventRouterInterface*
AXTreeSourceAndroid::GetAutomationEventRouter() const {
  if (automation_event_router_for_test_) {
    return automation_event_router_for_test_;
  }

  return extensions::AutomationEventRouter::GetInstance();
}

gfx::Rect AXTreeSourceAndroid::ComputeEnclosingBounds(
    AccessibilityInfoDataWrapper* info_data) const {
  DCHECK(info_data);
  gfx::Rect computed_bounds;
  // Exit early if the node or window is invisible.
  if (!info_data->IsVisibleToUser()) {
    return computed_bounds;
  }

  ComputeEnclosingBoundsInternal(info_data, &computed_bounds);
  return computed_bounds;
}

void AXTreeSourceAndroid::ComputeEnclosingBoundsInternal(
    AccessibilityInfoDataWrapper* info_data,
    gfx::Rect* computed_bounds) const {
  DCHECK(computed_bounds);
  auto cached_bounds = computed_bounds_.find(info_data->GetId());
  if (cached_bounds != computed_bounds_.end()) {
    computed_bounds->Union(cached_bounds->second);
    return;
  }

  if (!info_data->IsVisibleToUser()) {
    return;
  }
  // Only consider nodes that can possibly be accessibility focused.
  if (info_data->IsFocusableInFullFocusMode()) {
    computed_bounds->Union(info_data->GetBounds());
  }

  // NOTE: |AXTreeSourceAndroid::GetChildren| depends on ComputeEnclosingBounds.
  // To get children, directly call wrapper's GetChildren here.
  std::vector<raw_ptr<AccessibilityInfoDataWrapper, VectorExperimental>>
      children;
  info_data->GetChildren(&children);
  for (AccessibilityInfoDataWrapper* child : children) {
    ComputeEnclosingBoundsInternal(child, computed_bounds);
  }
  return;
}

AccessibilityInfoDataWrapper*
AXTreeSourceAndroid::FindFirstFocusableNodeInFullFocusMode(
    AccessibilityInfoDataWrapper* info_data) const {
  if (!info_data) {
    return nullptr;
  }

  if (info_data->IsVisibleToUser() && info_data->IsFocusableInFullFocusMode()) {
    return info_data;
  }

  for (AccessibilityInfoDataWrapper* child : GetChildren(info_data)) {
    AccessibilityInfoDataWrapper* candidate =
        FindFirstFocusableNodeInFullFocusMode(child);
    if (candidate) {
      return candidate;
    }
  }

  return nullptr;
}

bool AXTreeSourceAndroid::UpdateAndroidFocusedId(
    const AXEventData& event_data) {
  AccessibilityInfoDataWrapper* source_node = GetFromId(event_data.source_id);
  if (source_node) {
    AccessibilityInfoDataWrapper* source_window =
        GetFromId(source_node->GetWindowId());
    if (!source_window ||
        !GetBooleanProperty(source_window->GetWindow(),
                            AXWindowBooleanProperty::FOCUSED)) {
      // Don't update focus in this task for events from non-focused window.
      return true;
    }
  }

  if (event_data.event_type == AXEventType::VIEW_FOCUSED) {
    if (source_node && source_node->IsVisibleToUser() &&
        GetBooleanProperty(source_node->GetNode(),
                           AXBooleanProperty::FOCUSED)) {
      // Sometimes Android sets focus on unfocusable node, e.g. ListView.
      AccessibilityInfoDataWrapper* adjusted_node =
          UseFullFocusMode()
              ? FindFirstFocusableNodeInFullFocusMode(source_node)
              : source_node;
      if (adjusted_node) {
        android_focused_id_ = adjusted_node->GetId();
      }
    }
  } else if (event_data.event_type == AXEventType::VIEW_ACCESSIBILITY_FOCUSED &&
             UseFullFocusMode()) {
    if (source_node && source_node->IsVisibleToUser()) {
      android_focused_id_ = source_node->GetId();
    }
  } else if (event_data.event_type ==
                 AXEventType::VIEW_ACCESSIBILITY_FOCUS_CLEARED &&
             UseFullFocusMode()) {
    int event_from_action;
    GetProperty(event_data.int_properties,
                mojom::AccessibilityEventIntProperty::ACTION,
                &event_from_action);
    const mojom::AccessibilityActionType action =
        static_cast<mojom::AccessibilityActionType>(event_from_action);
    if (action != mojom::AccessibilityActionType::FOCUS &&
        action != mojom::AccessibilityActionType::ACCESSIBILITY_FOCUS) {
      android_focused_id_.reset();
    }
  } else if (event_data.event_type == AXEventType::VIEW_SELECTED) {
    // In Android, VIEW_SELECTED event is dispatched in the two cases below:
    // 1. Changing a value in ProgressBar or TimePicker in Android P.
    // 2. Selecting an item in the context of an AdapterView.
    if (!source_node || !source_node->IsNode()) {
      return false;
    }

    AXNodeInfoData* node_info = source_node->GetNode();
    DCHECK(node_info);

    bool is_range_change = !node_info->range_info.is_null();
    if (!is_range_change) {
      AccessibilityInfoDataWrapper* selected_node =
          GetSelectedNodeInfoFromAdapterViewEvent(event_data, source_node);
      if (!selected_node || !selected_node->IsVisibleToUser()) {
        return false;
      }

      android_focused_id_ = selected_node->GetId();
    }
  } else if (event_data.event_type == AXEventType::WINDOW_STATE_CHANGED) {
    // When accessibility window changed, a11y event of WINDOW_CONTENT_CHANGED
    // is fired from Android multiple times.
    // The event of WINDOW_STATE_CHANGED is fired only once for each window
    // change and use it as a trigger to move the a11y focus to the first node.
    AccessibilityInfoDataWrapper* new_focus = nullptr;

    // If the current window has ever been visited in the current task, try
    // focus on the last focus node in this window.
    // We do it for WINDOW_STATE_CHANGED event from a window or a root node.
    bool from_root_or_window = (source_node && !source_node->IsNode()) ||
                               IsRootOfNodeTree(event_data.source_id);
    if (from_root_or_window) {
      auto itr = window_id_to_last_focus_node_id_.find(event_data.window_id);
      if (itr != window_id_to_last_focus_node_id_.end()) {
        new_focus = GetFromId(itr->second);
      }
    } else if (UseFullFocusMode()) {
      // Otherwise, try focus on the first focusable node.
      new_focus = FindFirstFocusableNodeInFullFocusMode(
          GetFromId(event_data.source_id));
    }

    if (new_focus) {
      android_focused_id_ = new_focus->GetId();
    }
  }

  if (!android_focused_id_ || !GetFromId(*android_focused_id_)) {
    // Because we only handle events from the focused window, let's reset the
    // focus to the root window.
    AccessibilityInfoDataWrapper* root = GetRoot();
    CHECK(root);
    android_focused_id_ = root_id_;
  }

  if (android_focused_id_.has_value()) {
    window_id_to_last_focus_node_id_[event_data.window_id] =
        *android_focused_id_;
  } else {
    window_id_to_last_focus_node_id_.erase(event_data.window_id);
  }

  AccessibilityInfoDataWrapper* focused_node =
      android_focused_id_.has_value() ? GetFromId(*android_focused_id_)
                                      : nullptr;

  // Ensure that the focused node correctly gets focus.
  while (focused_node && focused_node->IsIgnored()) {
    AccessibilityInfoDataWrapper* parent = GetParent(focused_node);
    if (parent) {
      android_focused_id_ = parent->GetId();
      focused_node = parent;
    } else {
      // Unable to find the appropriate focus. Removing the focused node.
      android_focused_id_.reset();
      focused_node = nullptr;
      break;
    }
  }

  return true;
}

std::vector<int32_t> AXTreeSourceAndroid::ProcessHooksOnEvent(
    const AXEventData& event_data) {
  base::EraseIf(hooks_, [this](const auto& it) {
    return it.second->ShouldDestroy(this);
  });

  std::vector<int32_t> serialization_needed_ids;
  for (const auto& modifier : hooks_) {
    if (modifier.second->PreDispatchEvent(this, event_data)) {
      serialization_needed_ids.push_back(modifier.first);
    }
  }

  // Add new hook implementations if necessary.
  auto drawer_layout_hook =
      DrawerLayoutHandler::CreateIfNecessary(this, event_data);
  if (drawer_layout_hook.has_value()) {
    hooks_.insert(std::move(*drawer_layout_hook));
  }

  auto auto_complete_hooks =
      AutoCompleteHandler::CreateIfNecessary(this, event_data);
  for (auto& modifier : auto_complete_hooks) {
    if (hooks_.count(modifier.first) == 0) {
      hooks_.insert(std::move(modifier));
    }
  }

  auto pane_title_hook = PaneTitleHandler::CreateIfNecessary(this, event_data);
  if (pane_title_hook) {
    hooks_.insert(std::move(*pane_title_hook));
  }

  return serialization_needed_ids;
}

void AXTreeSourceAndroid::Reset() {
  tree_map_.clear();
  parent_map_.clear();
  computed_bounds_.clear();
  current_tree_serializer_ = std::make_unique<AXTreeAndroidSerializer>(this);
  root_id_.reset();
  window_id_.reset();
  android_focused_id_.reset();
  extensions::AutomationEventRouterInterface* router =
      GetAutomationEventRouter();
  if (!router) {
    return;
  }

  router->DispatchTreeDestroyedEvent(ax_tree_id());
}

bool AXTreeSourceAndroid::NeedReorder(
    AccessibilityInfoDataWrapper* left,
    AccessibilityInfoDataWrapper* right) const {
  auto left_bounds = ComputeEnclosingBounds(left);
  auto right_bounds = ComputeEnclosingBounds(right);
  return !CompareBounds(left_bounds, right_bounds) &&
         CompareBounds(left->GetBounds(), right->GetBounds());
}

bool AXTreeSourceAndroid::CompareBounds(const gfx::Rect& left,
                                        const gfx::Rect& right) const {
  if (left.IsEmpty() || right.IsEmpty()) {
    return true;
  }

  // Non-intersecting vertical check.
  if (left.bottom() <= right.y()) {
    return true;
  }

  if (left.y() >= right.bottom()) {
    return false;
  }

  // Vertically overlapping. Left one comes first.
  // TODO consider right-to-left
  int left_difference = left.x() - right.x();
  if (left_difference != 0) {
    return left_difference < 0;
  }

  // Top to bottom.
  int top_difference = left.y() - right.y();
  if (top_difference != 0) {
    return top_difference < 0;
  }

  // Larger to smaller.
  int height_difference = left.height() - right.height();
  if (height_difference != 0) {
    return height_difference > 0;
  }

  int width_difference = left.width() - right.width();
  if (width_difference != 0) {
    return width_difference > 0;
  }

  // The rects are equal. Respect the original order.
  return true;
}

int32_t AXTreeSourceAndroid::GetId(
    AccessibilityInfoDataWrapper* info_data) const {
  if (!info_data) {
    return ui::kInvalidAXNodeID;
  }
  return info_data->GetId();
}

void AXTreeSourceAndroid::CacheChildrenIfNeeded(
    AccessibilityInfoDataWrapper* info_data) {
  ComputeAndCacheChildren(info_data);
}

size_t AXTreeSourceAndroid::GetChildCount(
    AccessibilityInfoDataWrapper* info_data) const {
  if (!info_data) {
    return 0;
  }
  DCHECK(info_data->cached_children_);
  return info_data->cached_children_->size();
}

AccessibilityInfoDataWrapper* AXTreeSourceAndroid::ChildAt(
    AccessibilityInfoDataWrapper* info_data,
    size_t i) const {
  DCHECK(info_data->cached_children_);
  DCHECK(i >= 0 && i < info_data->cached_children_->size());
  return (*info_data->cached_children_)[i];
}

// We don't need to handle cache clearing here, because each
// AccessibilityInfoDataWrapper is created during
// AXTreeSourceAndroid::NotifyAccessibilityEvent(), and destructed at the end of
// it that method.
void AXTreeSourceAndroid::ClearChildCache(
    AccessibilityInfoDataWrapper* info_data) {}

bool AXTreeSourceAndroid::IsIgnored(
    AccessibilityInfoDataWrapper* info_data) const {
  return false;
}

bool AXTreeSourceAndroid::IsEqual(
    AccessibilityInfoDataWrapper* info_data1,
    AccessibilityInfoDataWrapper* info_data2) const {
  if (!info_data1 || !info_data2) {
    return false;
  }
  return info_data1->GetId() == info_data2->GetId();
}

AccessibilityInfoDataWrapper* AXTreeSourceAndroid::GetNull() const {
  return nullptr;
}

void AXTreeSourceAndroid::PerformAction(const ui::AXActionData& data) {
  delegate_->OnAction(data);
}

std::vector<raw_ptr<AccessibilityInfoDataWrapper, VectorExperimental>>&
AXTreeSourceAndroid::GetChildren(
    AccessibilityInfoDataWrapper* info_data) const {
  DCHECK(info_data);
  ComputeAndCacheChildren(info_data);
  return info_data->cached_children_.value();
}

void AXTreeSourceAndroid::ComputeAndCacheChildren(
    AccessibilityInfoDataWrapper* info_data) const {
  if (info_data->cached_children_) {
    return;
  }

  std::vector<raw_ptr<AccessibilityInfoDataWrapper, VectorExperimental>>&
      children = info_data->cached_children_.emplace();

  info_data->GetChildren(&children);
  if (children.size() < 2) {
    return;
  }

  // We sort output nodes only in full focus mode.
  if (!UseFullFocusMode() || info_data->IsWebNode()) {
    return;
  }

  // Also don't sort for virtual nodes (e.g. WebView).
  for (const AccessibilityInfoDataWrapper* child : children) {
    if (child->IsWebNode()) {
      return;
    }
  }

  // This is a kind of bubble sort, but we reorder nodes only when the original
  // node bounds (which is from node->GetBounds()) and child enclosing bounds
  // (which is from ComputeEnclosingBounds()) are different.
  // This algorithm takes O(N^2) time, but we practically don't expect that
  // there's a node that contains hundreds of child nodes that require
  // reordering.
  //
  // The concept here is taken from Android accessibility's similar logic in
  // com.google.android.accessibility.utils.traversal.ReorderedChildrenIterator.
  //
  // Note that NeedReorder method is not transitive, so we cannot sort with it.
  // For example, consider bounds below:
  //   a = (0,11)-(10x10)
  //   b = (20,5)-(10x10)
  //   c = (40,0)-(10x10)
  // Here, NeedReorder(a, b) = false, NeedReorder(b, c) = false, but
  // NeedReorder(a, c) = true.

  for (int i = children.size() - 2; i >= 0; i--) {
    auto original_bounds = children.at(i)->GetBounds();
    auto enclosing_bounds = ComputeEnclosingBounds(children.at(i));
    if (original_bounds == enclosing_bounds) {
      continue;
    }

    // move the current node to be visited later if necessary.
    for (size_t j = i; j + 1 < children.size() &&
                       NeedReorder(children.at(j), children.at(j + 1));
         j++) {
      std::swap(children.at(j), children.at(j + 1));
    }
  }
}

}  // namespace ax::android