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

#ifndef UI_ACCESSIBILITY_AX_RANGE_H_
#define UI_ACCESSIBILITY_AX_RANGE_H_

#include <memory>
#include <ostream>
#include <string>
#include <utility>
#include <vector>

#include "base/strings/string16.h"
#include "base/strings/utf_string_conversions.h"
#include "ui/accessibility/ax_enums.mojom.h"
#include "ui/accessibility/ax_offscreen_result.h"
#include "ui/accessibility/ax_role_properties.h"
#include "ui/accessibility/ax_tree_manager_map.h"

namespace ui {

// Specifies how AXRange::GetText treats line breaks introduced by layout.
// For example, consider the following HTML snippet: "A<div>B</div>C".
enum class AXTextConcatenationBehavior {
  // Preserve any introduced line breaks, e.g. GetText = "A\nB\nC".
  kAsInnerText,
  // Ignore any introduced line breaks, e.g. GetText = "ABC".
  kAsTextContent
};

class AXRangeRectDelegate {
 public:
  virtual gfx::Rect GetInnerTextRangeBoundsRect(
      AXTreeID tree_id,
      AXNode::AXID node_id,
      int start_offset,
      int end_offset,
      AXOffscreenResult* offscreen_result) = 0;
  virtual gfx::Rect GetBoundsRect(AXTreeID tree_id,
                                  AXNode::AXID node_id,
                                  AXOffscreenResult* offscreen_result) = 0;
};

// A range delimited by two positions in the AXTree.
//
// In order to avoid any confusion regarding whether a deep or a shallow copy is
// being performed, this class can be moved, but not copied.
template <class AXPositionType>
class AXRange {
 public:
  using AXPositionInstance = std::unique_ptr<AXPositionType>;

  AXRange()
      : anchor_(AXPositionType::CreateNullPosition()),
        focus_(AXPositionType::CreateNullPosition()) {}

  AXRange(AXPositionInstance anchor, AXPositionInstance focus) {
    anchor_ = anchor ? std::move(anchor) : AXPositionType::CreateNullPosition();
    focus_ = focus ? std::move(focus) : AXPositionType::CreateNullPosition();
  }

  AXRange(const AXRange& other) = delete;

  AXRange(AXRange&& other) : AXRange() {
    anchor_.swap(other.anchor_);
    focus_.swap(other.focus_);
  }

  virtual ~AXRange() = default;

  AXPositionType* anchor() const {
    DCHECK(anchor_);
    return anchor_.get();
  }

  AXPositionType* focus() const {
    DCHECK(focus_);
    return focus_.get();
  }

  AXRange& operator=(const AXRange& other) = delete;

  AXRange& operator=(AXRange&& other) {
    if (this != &other) {
      anchor_ = AXPositionType::CreateNullPosition();
      focus_ = AXPositionType::CreateNullPosition();
      anchor_.swap(other.anchor_);
      focus_.swap(other.focus_);
    }
    return *this;
  }

  bool operator==(const AXRange& other) const {
    if (IsNull())
      return other.IsNull();
    return !other.IsNull() && *anchor_ == *other.anchor() &&
           *focus_ == *other.focus();
  }

  bool operator!=(const AXRange& other) const { return !(*this == other); }

  // Given a pair of AXPosition, determines how the first compares with the
  // second, relative to the order they would be iterated over by using
  // AXRange::Iterator to traverse all leaf text ranges in a tree.
  //
  // Notice that this method is different from using AXPosition::CompareTo since
  // the following logic takes into account BOTH tree pre-order traversal and
  // text offsets when both positions are located within the same anchor.
  //
  // Returns:
  //         0 - If both positions are equivalent.
  //        <0 - If the first position would come BEFORE the second.
  //        >0 - If the first position would come AFTER the second.
  //   nullopt - If positions are not comparable (see AXPosition::CompareTo).
  static base::Optional<int> CompareEndpoints(const AXPositionType* first,
                                              const AXPositionType* second) {
    base::Optional<int> tree_position_comparison =
        first->AsTreePosition()->CompareTo(*second->AsTreePosition());

    // When the tree comparison is nullopt, using value_or(1) forces a default
    // value of 1, making the following statement return nullopt as well.
    return (tree_position_comparison.value_or(1) != 0)
               ? tree_position_comparison
               : first->CompareTo(*second);
  }

  AXRange AsForwardRange() const {
    return (CompareEndpoints(anchor(), focus()).value_or(0) > 0)
               ? AXRange(focus_->Clone(), anchor_->Clone())
               : AXRange(anchor_->Clone(), focus_->Clone());
  }

  bool IsCollapsed() const { return !IsNull() && *anchor_ == *focus_; }

  // We define a "leaf text range" as an AXRange whose endpoints are leaf text
  // positions located within the same anchor of the AXTree.
  bool IsLeafTextRange() const {
    return !IsNull() && anchor_->GetAnchor() == focus_->GetAnchor() &&
           anchor_->IsLeafTextPosition() && focus_->IsLeafTextPosition();
  }

  bool IsNull() const {
    DCHECK(anchor_ && focus_);
    return anchor_->IsNullPosition() || focus_->IsNullPosition();
  }

  std::string ToString() const {
    return "Range\nAnchor:" + anchor_->ToString() +
           "\nFocus:" + focus_->ToString();
  }

  // We can decompose any given AXRange into multiple "leaf text ranges".
  // As an example, consider the following HTML code:
  //
  //   <p>line with text<br><input type="checkbox">line with checkbox</p>
  //
  // It will produce the following AXTree; notice that the leaf text nodes
  // (enclosed in parenthesis) compose its text representation:
  //
  //   paragraph
  //     staticText name='line with text'
  //       (inlineTextBox name='line with text')
  //     lineBreak name='<newline>'
  //       (inlineTextBox name='<newline>')
  //     (checkBox)
  //     staticText name='line with checkbox'
  //       (inlineTextBox name='line with checkbox')
  //
  // Suppose we have an AXRange containing all elements from the example above.
  // The text representation of such range, with AXRange's endpoints marked by
  // opening and closing brackets, will look like the following:
  //
  //   "[line with text\n{checkBox}line with checkbox]"
  //
  // Note that in the text representation {checkBox} is not visible, but it is
  // effectively a "leaf text range", so we include it in the example above only
  // to visualize how the iterator should work.
  //
  // Decomposing the AXRange above into its "leaf text ranges" would result in:
  //
  //   "[line with text][\n][{checkBox}][line with checkbox]"
  //
  // This class allows AXRange to be iterated through all "leaf text ranges"
  // contained between its endpoints, composing the entire range.
  class Iterator : public std::iterator<std::input_iterator_tag, AXRange> {
   public:
    Iterator()
        : current_start_(AXPositionType::CreateNullPosition()),
          iterator_end_(AXPositionType::CreateNullPosition()) {}

    Iterator(AXPositionInstance start, AXPositionInstance end) {
      if (end && !end->IsNullPosition()) {
        current_start_ = !start ? AXPositionType::CreateNullPosition()
                                : start->AsLeafTextPosition();
        iterator_end_ = end->AsLeafTextPosition();
      } else {
        current_start_ = AXPositionType::CreateNullPosition();
        iterator_end_ = AXPositionType::CreateNullPosition();
      }
    }

    Iterator(const Iterator& other) = delete;

    Iterator(Iterator&& other)
        : current_start_(std::move(other.current_start_)),
          iterator_end_(std::move(other.iterator_end_)) {}

    ~Iterator() = default;

    bool operator==(const Iterator& other) const {
      return current_start_->GetAnchor() == other.current_start_->GetAnchor() &&
             iterator_end_->GetAnchor() == other.iterator_end_->GetAnchor() &&
             *current_start_ == *other.current_start_ &&
             *iterator_end_ == *other.iterator_end_;
    }

    bool operator!=(const Iterator& other) const { return !(*this == other); }

    // Only forward iteration is supported, so operator-- is not implemented.
    Iterator& operator++() {
      DCHECK(!current_start_->IsNullPosition());
      if (current_start_->GetAnchor() == iterator_end_->GetAnchor()) {
        current_start_ = AXPositionType::CreateNullPosition();
      } else {
        current_start_ = current_start_->CreateNextLeafTreePosition();
        DCHECK_LE(*current_start_, *iterator_end_);
      }
      return *this;
    }

    AXRange operator*() const {
      DCHECK(!current_start_->IsNullPosition());
      AXPositionInstance current_end =
          (current_start_->GetAnchor() != iterator_end_->GetAnchor())
              ? current_start_->CreatePositionAtEndOfAnchor()
              : iterator_end_->Clone();
      DCHECK_LE(*current_end, *iterator_end_);

      AXRange current_leaf_text_range(current_start_->AsTextPosition(),
                                      current_end->AsTextPosition());
      DCHECK(current_leaf_text_range.IsLeafTextRange());
      return std::move(current_leaf_text_range);
    }

   private:
    AXPositionInstance current_start_;
    AXPositionInstance iterator_end_;
  };

  Iterator begin() const {
    if (IsNull())
      return Iterator(nullptr, nullptr);
    AXRange forward_range = AsForwardRange();
    return Iterator(std::move(forward_range.anchor_),
                    std::move(forward_range.focus_));
  }

  Iterator end() const {
    if (IsNull())
      return Iterator(nullptr, nullptr);
    AXRange forward_range = AsForwardRange();
    return Iterator(nullptr, std::move(forward_range.focus_));
  }

  // Returns the concatenation of the accessible names of all text nodes
  // contained between this AXRange's endpoints.
  // Pass a |max_count| of -1 to retrieve all text in the AXRange.
  // Note that if this AXRange has its anchor or focus located at an ignored
  // position, we shrink the range to the closest unignored positions.
  base::string16 GetText(AXTextConcatenationBehavior concatenation_behavior =
                             AXTextConcatenationBehavior::kAsTextContent,
                         int max_count = -1,
                         bool include_ignored = false,
                         size_t* appended_newlines_count = nullptr) const {
    if (max_count == 0 || IsNull())
      return base::string16();

    base::Optional<int> endpoint_comparison =
        CompareEndpoints(anchor(), focus());
    if (!endpoint_comparison)
      return base::string16();

    AXPositionInstance start = (endpoint_comparison.value() < 0)
                                   ? anchor_->AsLeafTextPosition()
                                   : focus_->AsLeafTextPosition();
    AXPositionInstance end = (endpoint_comparison.value() < 0)
                                 ? focus_->AsLeafTextPosition()
                                 : anchor_->AsLeafTextPosition();

    base::string16 range_text;
    size_t computed_newlines_count = 0;
    bool is_first_non_whitespace_leaf = true;
    bool crossed_paragraph_boundary = false;
    bool is_first_unignored_leaf = true;
    bool found_trailing_newline = false;

    while (!start->IsNullPosition()) {
      DCHECK(start->IsLeafTextPosition());
      DCHECK_GE(start->text_offset(), 0);

      if (include_ignored || !start->IsIgnored()) {
        if (concatenation_behavior ==
                AXTextConcatenationBehavior::kAsInnerText &&
            !start->IsInWhiteSpace()) {
          if (is_first_non_whitespace_leaf) {
            // The first non-whitespace leaf in the range could be preceded by
            // whitespace spanning even before the start of this range, we need
            // to check such positions in order to correctly determine if this
            // is a paragraph's start (see |AXPosition::AtStartOfParagraph|).
            crossed_paragraph_boundary =
                !is_first_unignored_leaf && start->AtStartOfParagraph();
          }

          // When preserving layout line breaks, don't append `\n` next if the
          // previous leaf position was a <br> (already ending with a newline).
          if (crossed_paragraph_boundary && !found_trailing_newline) {
            range_text += base::ASCIIToUTF16("\n");
            computed_newlines_count++;
          }

          is_first_non_whitespace_leaf = false;
          crossed_paragraph_boundary = false;
        }

        int current_end_offset = (start->GetAnchor() != end->GetAnchor())
                                     ? start->MaxTextOffset()
                                     : end->text_offset();

        if (current_end_offset > start->text_offset()) {
          int characters_to_append =
              (max_count > 0)
                  ? std::min(max_count - int{range_text.length()},
                             current_end_offset - start->text_offset())
                  : current_end_offset - start->text_offset();

          range_text += start->GetText().substr(start->text_offset(),
                                                characters_to_append);

          // Collapse all whitespace following any line break.
          found_trailing_newline =
              start->IsInLineBreak() ||
              (found_trailing_newline && start->IsInWhiteSpace());
        }

        DCHECK(max_count < 0 || int{range_text.length()} <= max_count);
        is_first_unignored_leaf = false;
      }

      if (start->GetAnchor() == end->GetAnchor() ||
          int{range_text.length()} == max_count) {
        break;
      } else if (concatenation_behavior ==
                     AXTextConcatenationBehavior::kAsInnerText &&
                 !crossed_paragraph_boundary && !is_first_non_whitespace_leaf) {
        start = start->CreateNextLeafTextPosition(&crossed_paragraph_boundary);
      } else {
        start = start->CreateNextLeafTextPosition();
      }
    }

    if (appended_newlines_count)
      *appended_newlines_count = computed_newlines_count;
    return range_text;
  }

  // Appends rects of all anchor nodes that span between anchor_ and focus_.
  // Rects outside of the viewport are skipped.
  // Coordinate system is determined by the passed-in delegate.
  std::vector<gfx::Rect> GetRects(AXRangeRectDelegate* delegate) const {
    std::vector<gfx::Rect> rects;

    for (const AXRange& leaf_text_range : *this) {
      DCHECK(leaf_text_range.IsLeafTextRange());
      AXPositionType* current_line_start = leaf_text_range.anchor();
      AXPositionType* current_line_end = leaf_text_range.focus();

      // For text anchors, we retrieve the bounding rectangles of its text
      // content. For non-text anchors (such as checkboxes, images, etc.), we
      // want to directly retrieve their bounding rectangles.
      AXOffscreenResult offscreen_result;
      gfx::Rect current_rect =
          (current_line_start->IsInLineBreak() ||
           current_line_start->IsInTextObject())
              ? delegate->GetInnerTextRangeBoundsRect(
                    current_line_start->tree_id(),
                    current_line_start->anchor_id(),
                    current_line_start->text_offset(),
                    current_line_end->text_offset(), &offscreen_result)
              : delegate->GetBoundsRect(current_line_start->tree_id(),
                                        current_line_start->anchor_id(),
                                        &offscreen_result);

      // If the bounding box of the current range is clipped because it lies
      // outside an ancestor’s bounds, then the bounding box is pushed to the
      // nearest edge of such ancestor's bounds, with its width and height
      // forced to be 1, and the node will be marked as "offscreen".
      //
      // Only add rectangles that are not empty and not marked as "offscreen".
      //
      // See the documentation for how bounding boxes are calculated in AXTree:
      // https://chromium.googlesource.com/chromium/src/+/HEAD/docs/accessibility/offscreen.md
      if (!current_rect.IsEmpty() &&
          offscreen_result == AXOffscreenResult::kOnscreen)
        rects.push_back(current_rect);
    }
    return rects;
  }

 private:
  AXPositionInstance anchor_;
  AXPositionInstance focus_;
};

template <class AXPositionType>
std::ostream& operator<<(std::ostream& stream,
                         const AXRange<AXPositionType>& range) {
  return stream << range.ToString();
}

}  // namespace ui

#endif  // UI_ACCESSIBILITY_AX_RANGE_H_