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

#include "ui/gfx/x/x11_crtc_resizer.h"

#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>

#include "base/check.h"
#include "base/containers/adapters.h"
#include "base/containers/contains.h"
#include "base/logging.h"
#include "base/stl_util.h"
#include "ui/gfx/geometry/vector2d.h"
#include "ui/gfx/x/connection.h"
#include "ui/gfx/x/future.h"

namespace {

constexpr auto kInvalidMode = static_cast<x11::RandR::Mode>(0);
constexpr auto kDisabledCrtc = static_cast<x11::RandR::Crtc>(0);

// TODO(jamiewalch): Use the correct DPI for the mode: http://crbug.com/172405.
const int kDefaultDPI = 96;

int PixelsToMillimeters(int pixels, int dpi) {
  DCHECK(dpi != 0);

  const double kMillimetersPerInch = 25.4;

  // (pixels / dpi) is the length in inches. Multiplying by
  // kMillimetersPerInch converts to mm. Multiplication is done first to
  // avoid integer division.
  return static_cast<int>(kMillimetersPerInch * pixels / dpi);
}

}  // namespace

namespace x11 {

X11CrtcResizer::CrtcInfo::CrtcInfo() = default;
X11CrtcResizer::CrtcInfo::CrtcInfo(
    x11::RandR::Crtc crtc,
    int16_t x,
    int16_t y,
    uint16_t width,
    uint16_t height,
    x11::RandR::Mode mode,
    x11::RandR::Rotation rotation,
    const std::vector<x11::RandR::Output>& outputs)
    : crtc(crtc),
      old_x(x),
      x(x),
      old_y(y),
      y(y),
      width(width),
      height(height),
      mode(mode),
      rotation(rotation),
      outputs(outputs) {}
X11CrtcResizer::CrtcInfo::CrtcInfo(const X11CrtcResizer::CrtcInfo&) = default;
X11CrtcResizer::CrtcInfo::CrtcInfo(X11CrtcResizer::CrtcInfo&&) = default;
X11CrtcResizer::CrtcInfo& X11CrtcResizer::CrtcInfo::operator=(
    const X11CrtcResizer::CrtcInfo&) = default;
X11CrtcResizer::CrtcInfo& X11CrtcResizer::CrtcInfo::operator=(
    X11CrtcResizer::CrtcInfo&&) = default;
X11CrtcResizer::CrtcInfo::~CrtcInfo() = default;

bool X11CrtcResizer::CrtcInfo::OffsetsChanged() const {
  return old_x != x || old_y != y;
}

X11CrtcResizer::X11CrtcResizer(
    x11::RandR::GetScreenResourcesCurrentReply* resources,
    x11::Connection* connection)
    : connection_(connection) {
  if (resources != nullptr) {
    resources_ = *resources;
  }
  // Unittests provide nullptr, and do not exercise code-paths that talk to the
  // X server.
  if (connection_) {
    randr_ = &connection_->randr();
    auto atom_reply = connection_->InternAtom({false, "WM_STATE"}).Sync();
    if (atom_reply) {
      wm_state_atom_ = atom_reply->atom;
    } else {
      LOG(ERROR) << "Failed to intern atom for WM_STATE.";
    }
  }
}

X11CrtcResizer::~X11CrtcResizer() = default;

void X11CrtcResizer::FetchActiveCrtcs() {
  active_crtcs_.clear();
  x11::Time config_timestamp = resources_.config_timestamp;
  for (const auto& crtc : resources_.crtcs) {
    auto response = randr_->GetCrtcInfo({crtc, config_timestamp}).Sync();
    if (!response) {
      continue;
    }
    if (response->outputs.empty()) {
      continue;
    }

    AddCrtcFromReply(crtc, *response.reply);
  }
}

x11::RandR::Crtc X11CrtcResizer::GetCrtcForOutput(
    x11::RandR::Output output) const {
  // This implementation assumes an output is attached to only one CRTC. If
  // there are multiple CRTCs for the output, only the first will be returned,
  // but this should never occur with Xorg+video-dummy.
  auto iter =
      std::ranges::find_if(active_crtcs_, [output](const CrtcInfo& crtc_info) {
        return base::Contains(crtc_info.outputs, output);
      });
  if (iter == active_crtcs_.end()) {
    return kDisabledCrtc;
  }
  return iter->crtc;
}

void X11CrtcResizer::DisableCrtc(x11::RandR::Crtc crtc) {
  x11::Time config_timestamp = resources_.config_timestamp;
  randr_->SetCrtcConfig({
      .crtc = crtc,
      .timestamp = x11::Time::CurrentTime,
      .config_timestamp = config_timestamp,
      .x = 0,
      .y = 0,
      .mode = kInvalidMode,
      .rotation = x11::RandR::Rotation::Rotate_0,
      .outputs = {},
  });
}

void X11CrtcResizer::UpdateActiveCrtcs(x11::RandR::Crtc crtc,
                                       x11::RandR::Mode mode,
                                       const gfx::Size& new_size) {
  updated_crtcs_.insert(crtc);

  // Find |crtc| in |active_crtcs_| and adjust its mode and size.
  auto iter = std::ranges::find(active_crtcs_, crtc, &CrtcInfo::crtc);

  // |crtc| was returned by GetCrtcForOutput() so it should definitely be in
  // the list.
  DCHECK(iter != active_crtcs_.end());

  iter->mode = mode;
  RelayoutCrtcs(iter->crtc, new_size);
  NormalizeCrtcs();
}

void X11CrtcResizer::UpdateActiveCrtc(x11::RandR::Crtc crtc,
                                      x11::RandR::Mode mode,
                                      const gfx::Rect& new_rect) {
  updated_crtcs_.insert(crtc);

  // Find |crtc| in |active_crtcs_| and adjust its mode and size.
  auto iter = std::ranges::find(active_crtcs_, crtc, &CrtcInfo::crtc);

  // |crtc| was returned by GetCrtcForOutput() so it should definitely be in
  // the list.
  DCHECK(iter != active_crtcs_.end());

  iter->mode = mode;
  iter->x = new_rect.x();
  iter->y = new_rect.y();
  iter->width = new_rect.width();
  iter->height = new_rect.height();
}

void X11CrtcResizer::AddActiveCrtc(
    x11::RandR::Crtc crtc,
    x11::RandR::Mode mode,
    const std::vector<x11::RandR::Output>& outputs,
    const gfx::Rect& new_rect) {
  // |crtc| is not active so it must not be in |active_crtcs_|.
  DCHECK(std::ranges::find(active_crtcs_, crtc, &CrtcInfo::crtc) ==
         active_crtcs_.end());

  active_crtcs_.emplace_back(crtc, new_rect.x(), new_rect.y(), new_rect.width(),
                             new_rect.height(), mode,
                             x11::RandR::Rotation::Rotate_0, outputs);
  updated_crtcs_.insert(crtc);
}

void X11CrtcResizer::RemoveActiveCrtc(x11::RandR::Crtc crtc) {
  auto to_remove = std::ranges::remove(active_crtcs_, crtc, &CrtcInfo::crtc);
  DCHECK(!to_remove.empty());
  active_crtcs_.erase(to_remove.begin(), to_remove.end());
}

void X11CrtcResizer::RelayoutCrtcs(x11::RandR::Crtc crtc_to_resize,
                                   const gfx::Size& new_size) {
  if (LayoutIsVertical()) {
    PackVertically(new_size, crtc_to_resize);
  } else {
    PackHorizontally(new_size, crtc_to_resize);
  }
}

void X11CrtcResizer::DisableChangedCrtcs() {
  for (const auto& crtc_info : active_crtcs_) {
    // Updated CRTCs are expected to be disabled by the caller.
    if (crtc_info.OffsetsChanged() &&
        !updated_crtcs_.contains(crtc_info.crtc)) {
      DisableCrtc(crtc_info.crtc);
    }
  }
}

void X11CrtcResizer::NormalizeCrtcs() {
  gfx::Rect bounding_box;
  for (const auto& crtc : active_crtcs_) {
    bounding_box.Union(gfx::Rect(crtc.x, crtc.y, crtc.width, crtc.height));
  }
  bounding_box_size_ = bounding_box.size();
  gfx::Vector2d adjustment =
      gfx::Vector2d(-bounding_box.origin().x(), -bounding_box.origin().y());
  if (adjustment.IsZero()) {
    return;
  }
  for (auto& crtc : active_crtcs_) {
    crtc.x += adjustment.x();
    crtc.y += adjustment.y();
  }
}

void X11CrtcResizer::MoveApplicationWindows() {
  if (!connection_) {
    // connection_ is nullptr in unittests.
    return;
  }

  // Only direct descendants of the root window should be moved. Child
  // windows automatically track the location of their parents, and can only
  // be moved within their parent window.
  auto query_response =
      connection_->QueryTree({connection_->default_root()}).Sync();
  if (!query_response) {
    return;
  }
  for (const auto& window : query_response->children) {
    auto attributes_response =
        connection_->GetWindowAttributes({window}).Sync();
    if (!attributes_response) {
      continue;
    }
    if (attributes_response->map_state != x11::MapState::Viewable) {
      // Unmapped or hidden windows can be left alone - their geometries
      // might not be meaningful. If the window later becomes mapped, the
      // window-manager will be responsible for its placement.
      continue;
    }
    auto geometry_response = connection_->GetGeometry(window).Sync();
    if (!geometry_response) {
      continue;
    }

    // Look for any CRTC which contains the window's top-left corner. If the
    // CRTC is being moved, request the window to be moved the same amount.
    for (const auto& crtc_info : active_crtcs_) {
      if (!crtc_info.OffsetsChanged()) {
        continue;
      }

      auto old_rect = gfx::Rect(crtc_info.old_x, crtc_info.old_y,
                                crtc_info.width, crtc_info.height);
      gfx::Vector2d window_top_left(geometry_response->x, geometry_response->y);
      if (!old_rect.Contains(
              gfx::Point(window_top_left.x(), window_top_left.y()))) {
        continue;
      }

      gfx::Vector2d adjustment(crtc_info.x - crtc_info.old_x,
                               crtc_info.y - crtc_info.old_y);
      window_top_left = window_top_left + adjustment;

      MoveWindow(window, *attributes_response.reply,
                 gfx::Point(window_top_left.x(), window_top_left.y()));
      break;
    }
  }
}

gfx::Size X11CrtcResizer::GetBoundingBox() const {
  DCHECK(!bounding_box_size_.IsEmpty());
  return bounding_box_size_;
}

void X11CrtcResizer::ApplyActiveCrtcs() {
  for (const auto& crtc_info : active_crtcs_) {
    if (crtc_info.OffsetsChanged() || updated_crtcs_.contains(crtc_info.crtc)) {
      x11::Time config_timestamp = resources_.config_timestamp;
      randr_->SetCrtcConfig({
          .crtc = crtc_info.crtc,
          .timestamp = x11::Time::CurrentTime,
          .config_timestamp = config_timestamp,
          .x = crtc_info.x,
          .y = crtc_info.y,
          .mode = crtc_info.mode,
          .rotation = crtc_info.rotation,
          .outputs = crtc_info.outputs,
      });
    }
  }
  updated_crtcs_.clear();
}

void X11CrtcResizer::UpdateRootWindow(x11::Window root) {
  // Disable any CRTCs that have been changed, so that the root window can be
  // safely resized to the bounding-box of the new CRTCs.
  // This is non-optimal: the only CRTCs that need disabling are those whose
  // original rectangles don't fit into the new root window - they are the ones
  // that would prevent resizing the root window. But figuring these out would
  // involve keeping track of all the original rectangles as well as the new
  // ones. So, to keep the implementation simple (and working for any arbitrary
  // layout algorithm), all changed CRTCs are disabled here.
  DisableChangedCrtcs();

  // Get the dimensions to resize the root window to.
  auto dimensions = GetBoundingBox();

  // TODO(lambroslambrou): Use the DPI from client size information.
  uint32_t width_mm = PixelsToMillimeters(dimensions.width(), kDefaultDPI);
  uint32_t height_mm = PixelsToMillimeters(dimensions.height(), kDefaultDPI);
  randr_->SetScreenSize({root, static_cast<uint16_t>(dimensions.width()),
                         static_cast<uint16_t>(dimensions.height()), width_mm,
                         height_mm});

  MoveApplicationWindows();

  // Apply the new CRTCs, which will re-enable any that were disabled.
  ApplyActiveCrtcs();
}

void X11CrtcResizer::SetCrtcsForTest(
    std::vector<x11::RandR::GetCrtcInfoReply> crtcs) {
  int id = 1;
  for (const auto& crtc : crtcs) {
    AddCrtcFromReply(static_cast<x11::RandR::Crtc>(id), crtc);
    id++;
  }
}

std::vector<gfx::Rect> X11CrtcResizer::GetCrtcsForTest() const {
  std::vector<gfx::Rect> result;
  for (const auto& crtc_info : active_crtcs_) {
    result.emplace_back(crtc_info.x, crtc_info.y, crtc_info.width,
                        crtc_info.height);
  }
  return result;
}

void X11CrtcResizer::AddCrtcFromReply(
    x11::RandR::Crtc crtc,
    const x11::RandR::GetCrtcInfoReply& reply) {
  active_crtcs_.emplace_back(crtc, reply.x, reply.y, reply.width, reply.height,
                             reply.mode, reply.rotation, reply.outputs);
}

bool X11CrtcResizer::LayoutIsVertical() const {
  if (active_crtcs_.size() <= 1) {
    return false;
  }

  // For simplicity, just pick 2 CRTCs arbitrarily.
  auto iter1 = active_crtcs_.begin();
  auto iter2 = std::next(iter1);

  // The cases:
  // --[---]--------
  // --------[---]--
  // and:
  // --------[---]--
  // --[---]--------
  // are not vertically stacked. The case where the CRTCs are exactly touching
  // is also not vertically stacked, because it comes from a horizontal
  // packing of CRTCs:
  // --[---]-------
  // -------[---]--
  // All other cases have overlapping projections so they are considered
  // vertically stacked.
  auto left1 = iter1->x;
  auto right1 = iter1->x + iter1->width;
  auto left2 = iter2->x;
  auto right2 = iter2->x + iter2->width;

  return right1 > left2 && right2 > left1;
}

void X11CrtcResizer::PackVertically(const gfx::Size& new_size,
                                    x11::RandR::Crtc resized_crtc) {
  // Before applying the new size, test for any current alignments to
  // decide which alignment should be preserved, if any.
  DCHECK(!active_crtcs_.empty());
  bool is_left_aligned = true;
  bool is_middle_aligned = true;
  bool is_right_aligned = true;
  auto first_crtc_left = active_crtcs_.front().x;
  auto first_crtc_middle = first_crtc_left + active_crtcs_.front().width / 2;
  auto first_crtc_right = first_crtc_left + active_crtcs_.front().width;
  for (const auto& crtc_info : active_crtcs_) {
    auto crtc_left = crtc_info.x;
    auto crtc_middle = crtc_info.x + crtc_info.width / 2;
    auto crtc_right = crtc_info.x + crtc_info.width;
    if (crtc_left != first_crtc_left) {
      is_left_aligned = false;
    }
    if (abs(crtc_middle - first_crtc_middle) > 1) {
      is_middle_aligned = false;
    }
    if (crtc_right != first_crtc_right) {
      is_right_aligned = false;
    }
  }

  // Apply the new size.
  for (auto& crtc_info : active_crtcs_) {
    if (crtc_info.crtc == resized_crtc) {
      crtc_info.width = new_size.width();
      crtc_info.height = new_size.height();
      break;
    }
  }

  // Sort vertically before packing.
  std::ranges::sort(active_crtcs_, std::less<>(), &CrtcInfo::y);

  // Pack the CRTCs by setting their y-offsets. If necessary, change the
  // x-offset for right-alignment.
  int current_y = 0;
  for (auto& crtc_info : active_crtcs_) {
    crtc_info.y = current_y;
    current_y += crtc_info.height;

    // Place all monitors, respecting any alignment preference. If there are
    // multiple possible alignments, prioritize left, then right, then middle.
    // TODO(crbug.com/40225767): Implement a more sophisticated algorithm that
    // tries to preserve pairwise alignment. It is not enough to leave the
    // x-offsets unchanged here - this tends to result in the monitors being
    // arranged roughly diagonally, wasting lots of space. Some amount of
    // horizontal compression is needed to prevent this from happening.
    if (is_left_aligned) {
      crtc_info.x = 0;
    } else if (is_right_aligned) {
      crtc_info.x = -crtc_info.width;
    } else if (is_middle_aligned) {
      crtc_info.x = -crtc_info.width / 2;
    } else {
      // The current implementation left-aligns the CRTCs if no other
      // alignment is detected.
      // TODO(crbug.com/40225767): A future enhancement may be to detect and
      // report one of {left, middle, right, none}. The "none" case (for
      // vertical and horizontal layouts) could be treated as a
      // client-controlled layout, where the host does not attempt any
      // repositioning. In this case, the host could still support
      // resize-to-fit, but in a simplified way - resize would be allowed
      // whenever it creates no overlaps.
      crtc_info.x = 0;
    }
  }
}

void X11CrtcResizer::PackHorizontally(const gfx::Size& new_size,
                                      x11::RandR::Crtc resized_crtc) {
  gfx::Size new_size_transposed(new_size.height(), new_size.width());
  Transpose();
  PackVertically(new_size_transposed, resized_crtc);
  Transpose();
}

void X11CrtcResizer::Transpose() {
  for (auto& crtc_info : active_crtcs_) {
    std::swap(crtc_info.x, crtc_info.y);
    std::swap(crtc_info.width, crtc_info.height);
  }
}

void X11CrtcResizer::MoveWindow(x11::Window window,
                                const x11::GetWindowAttributesReply& attributes,
                                gfx::Point top_left) {
  if (!attributes.override_redirect) {
    // Try to locate the original window which was re-parented by the
    // window-manager.
    auto app_window = FindAppWindow(window, attributes);
    if (app_window != x11::Window::None) {
      window = app_window;
    }
  }

  connection_->ConfigureWindow({
      .window = window,
      .x = top_left.x(),
      .y = top_left.y(),
  });
}

x11::Window X11CrtcResizer::FindAppWindow(
    x11::Window window,
    const x11::GetWindowAttributesReply& attributes) {
  // Only descend into visible windows.
  if (attributes.map_state != x11::MapState::Viewable) {
    return x11::Window::None;
  }

  // If the window itself has the WM_STATE property, return it. Otherwise,
  // descend into the window's children recursively.
  auto property_reply = connection_
                            ->GetProperty({
                                .window = window,
                                .property = wm_state_atom_,
                                .long_length = 1,
                            })
                            .Sync();
  if (!property_reply) {
    return x11::Window::None;
  }
  if (property_reply->value_len != 0) {
    // Found window with WM_STATE property.
    return window;
  }

  // Descend into the children of |window| in stacking order. See for example:
  // Find_Client_In_Children() at
  // https://github.com/freedesktop/xorg-xwininfo/blob/master/clientwin.c
  auto query_response = connection_->QueryTree({window}).Sync();
  if (!query_response) {
    return x11::Window::None;
  }

  for (const auto& child_window : base::Reversed(query_response->children)) {
    auto attributes_response =
        connection_->GetWindowAttributes({child_window}).Sync();
    if (!attributes_response) {
      return x11::Window::None;
    }
    auto found_window = FindAppWindow(child_window, *attributes_response.reply);
    if (found_window != x11::Window::None) {
      return found_window;
    }
  }
  return x11::Window::None;
}

}  // namespace x11