// Copyright 2014 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.

#include <utility>

#include "cc/tiles/tiling_set_eviction_queue.h"

namespace cc {

TilingSetEvictionQueue::TilingSetEvictionQueue(
    PictureLayerTilingSet* tiling_set)
    : tree_(tiling_set->tree()), phase_(EVENTUALLY_RECT) {
  // Early out if the layer has no tilings.
  if (!tiling_set->num_tilings())
    return;
  GenerateTilingOrder(tiling_set);
  eventually_iterator_ = EventuallyTilingIterator(&tilings_, tree_);
  if (eventually_iterator_.done()) {
    AdvancePhase();
    return;
  }
  current_tile_ = *eventually_iterator_;
}

TilingSetEvictionQueue::~TilingSetEvictionQueue() {
}

void TilingSetEvictionQueue::GenerateTilingOrder(
    PictureLayerTilingSet* tiling_set) {
  tilings_.reserve(tiling_set->num_tilings());
  // Generate all of the tilings in the order described in the header comment
  // for this class.
  PictureLayerTilingSet::TilingRange range =
      tiling_set->GetTilingRange(PictureLayerTilingSet::HIGHER_THAN_HIGH_RES);
  for (size_t index = range.start; index < range.end; ++index) {
    PictureLayerTiling* tiling = tiling_set->tiling_at(index);
    if (tiling->has_tiles())
      tilings_.push_back(tiling);
  }

  range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOWER_THAN_LOW_RES);
  for (size_t i = range.start; i < range.end; ++i) {
    size_t index = range.start + (range.end - 1 - i);
    PictureLayerTiling* tiling = tiling_set->tiling_at(index);
    if (tiling->has_tiles())
      tilings_.push_back(tiling);
  }

  range = tiling_set->GetTilingRange(
      PictureLayerTilingSet::BETWEEN_HIGH_AND_LOW_RES);
  for (size_t i = range.start; i < range.end; ++i) {
    size_t index = range.start + (range.end - 1 - i);
    PictureLayerTiling* tiling = tiling_set->tiling_at(index);
    if (tiling->has_tiles())
      tilings_.push_back(tiling);
  }

  range = tiling_set->GetTilingRange(PictureLayerTilingSet::LOW_RES);
  for (size_t index = range.start; index < range.end; ++index) {
    PictureLayerTiling* tiling = tiling_set->tiling_at(index);
    if (tiling->has_tiles())
      tilings_.push_back(tiling);
  }

  range = tiling_set->GetTilingRange(PictureLayerTilingSet::HIGH_RES);
  for (size_t index = range.start; index < range.end; ++index) {
    PictureLayerTiling* tiling = tiling_set->tiling_at(index);
    if (tiling->has_tiles())
      tilings_.push_back(tiling);
  }
  DCHECK_GE(tiling_set->num_tilings(), tilings_.size());
}

void TilingSetEvictionQueue::AdvancePhase() {
  current_tile_ = PrioritizedTile();
  while (!current_tile_.tile() &&
         phase_ != VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED) {
    phase_ = static_cast<Phase>(phase_ + 1);
    switch (phase_) {
      case EVENTUALLY_RECT:
        NOTREACHED();
        break;
      case SOON_BORDER_RECT:
        soon_iterator_ = SoonBorderTilingIterator(&tilings_, tree_);
        if (!soon_iterator_.done())
          current_tile_ = *soon_iterator_;
        break;
      case SKEWPORT_RECT:
        skewport_iterator_ = SkewportTilingIterator(&tilings_, tree_);
        if (!skewport_iterator_.done())
          current_tile_ = *skewport_iterator_;
        break;
      case PENDING_VISIBLE_RECT:
        pending_visible_iterator_ = PendingVisibleTilingIterator(
            &tilings_, tree_, false /* return required for activation tiles */);
        if (!pending_visible_iterator_.done())
          current_tile_ = *pending_visible_iterator_;
        break;
      case PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION:
        pending_visible_iterator_ = PendingVisibleTilingIterator(
            &tilings_, tree_, true /* return required for activation tiles */);
        if (!pending_visible_iterator_.done())
          current_tile_ = *pending_visible_iterator_;
        break;
      case VISIBLE_RECT_OCCLUDED:
        visible_iterator_ = VisibleTilingIterator(
            &tilings_, tree_, true /* return occluded tiles */,
            false /* return required for activation tiles */);
        if (!visible_iterator_.done())
          current_tile_ = *visible_iterator_;
        break;
      case VISIBLE_RECT_UNOCCLUDED:
        visible_iterator_ = VisibleTilingIterator(
            &tilings_, tree_, false /* return occluded tiles */,
            false /* return required for activation tiles */);
        if (!visible_iterator_.done())
          current_tile_ = *visible_iterator_;
        break;
      case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
        visible_iterator_ = VisibleTilingIterator(
            &tilings_, tree_, true /* return occluded tiles */,
            true /* return required for activation tiles */);
        if (!visible_iterator_.done())
          current_tile_ = *visible_iterator_;
        break;
      case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
        visible_iterator_ = VisibleTilingIterator(
            &tilings_, tree_, false /* return occluded tiles */,
            true /* return required for activation tiles */);
        if (!visible_iterator_.done())
          current_tile_ = *visible_iterator_;
        break;
    }
  }
}

bool TilingSetEvictionQueue::IsEmpty() const {
  return !current_tile_.tile();
}

const PrioritizedTile& TilingSetEvictionQueue::Top() const {
  DCHECK(!IsEmpty());
  return current_tile_;
}

void TilingSetEvictionQueue::Pop() {
  DCHECK(!IsEmpty());
  current_tile_ = PrioritizedTile();
  switch (phase_) {
    case EVENTUALLY_RECT:
      ++eventually_iterator_;
      if (!eventually_iterator_.done())
        current_tile_ = *eventually_iterator_;
      break;
    case SOON_BORDER_RECT:
      ++soon_iterator_;
      if (!soon_iterator_.done())
        current_tile_ = *soon_iterator_;
      break;
    case SKEWPORT_RECT:
      ++skewport_iterator_;
      if (!skewport_iterator_.done())
        current_tile_ = *skewport_iterator_;
      break;
    case PENDING_VISIBLE_RECT:
    case PENDING_VISIBLE_RECT_REQUIRED_FOR_ACTIVATION:
      ++pending_visible_iterator_;
      if (!pending_visible_iterator_.done())
        current_tile_ = *pending_visible_iterator_;
      break;
    case VISIBLE_RECT_OCCLUDED:
    case VISIBLE_RECT_UNOCCLUDED:
    case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_OCCLUDED:
    case VISIBLE_RECT_REQUIRED_FOR_ACTIVATION_UNOCCLUDED:
      ++visible_iterator_;
      if (!visible_iterator_.done())
        current_tile_ = *visible_iterator_;
      break;
  }
  if (!current_tile_.tile())
    AdvancePhase();
}

// EvictionRectIterator
TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator()
    : tilings_(nullptr), tree_(ACTIVE_TREE), tiling_index_(0) {
}

TilingSetEvictionQueue::EvictionRectIterator::EvictionRectIterator(
    std::vector<PictureLayerTiling*>* tilings,
    WhichTree tree,
    PictureLayerTiling::PriorityRectType priority_rect_type)
    : tilings_(tilings),
      tree_(tree),
      priority_rect_type_(priority_rect_type),
      tiling_index_(0) {
}

template <typename TilingIteratorType>
bool TilingSetEvictionQueue::EvictionRectIterator::AdvanceToNextTile(
    TilingIteratorType* iterator) {
  bool found_tile = false;
  while (!found_tile) {
    ++(*iterator);
    if (!(*iterator)) {
      prioritized_tile_ = PrioritizedTile();
      break;
    }
    found_tile = GetFirstTileAndCheckIfValid(iterator);
  }
  return found_tile;
}

template <typename TilingIteratorType>
bool TilingSetEvictionQueue::EvictionRectIterator::GetFirstTileAndCheckIfValid(
    TilingIteratorType* iterator) {
  PictureLayerTiling* tiling = (*tilings_)[tiling_index_];
  Tile* tile = tiling->TileAt(iterator->index_x(), iterator->index_y());
  prioritized_tile_ = PrioritizedTile();
  // If there's nothing to evict, return false.
  if (!tile || !tile->draw_info().has_resource())
    return false;
  // After the pending visible rect has been processed, we must return false
  // for pending visible rect tiles as tiling iterators do not ignore those
  // tiles.
  if (priority_rect_type_ > PictureLayerTiling::PENDING_VISIBLE_RECT) {
    gfx::Rect tile_rect = tiling->tiling_data()->TileBounds(
        tile->tiling_i_index(), tile->tiling_j_index());
    if (tiling->pending_visible_rect().Intersects(tile_rect))
      return false;
  }
  (*tilings_)[tiling_index_]->UpdateRequiredStatesOnTile(tile);
  prioritized_tile_ = (*tilings_)[tiling_index_]->MakePrioritizedTile(
      tile, priority_rect_type_);
  // In other cases, the tile we got is a viable candidate, return true.
  return true;
}

// EventuallyTilingIterator
TilingSetEvictionQueue::EventuallyTilingIterator::EventuallyTilingIterator(
    std::vector<PictureLayerTiling*>* tilings,
    WhichTree tree)
    : EvictionRectIterator(tilings, tree, PictureLayerTiling::EVENTUALLY_RECT) {
  // Find the first tiling with a tile.
  while (tiling_index_ < tilings_->size()) {
    if (!(*tilings_)[tiling_index_]->has_eventually_rect_tiles()) {
      ++tiling_index_;
      continue;
    }
    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_eventually_rect(),
        (*tilings_)[tiling_index_]->current_skewport_rect(),
        (*tilings_)[tiling_index_]->current_soon_border_rect());
    if (!iterator_) {
      ++tiling_index_;
      continue;
    }
    break;
  }
  if (tiling_index_ >= tilings_->size())
    return;
  if (!GetFirstTileAndCheckIfValid(&iterator_))
    ++(*this);
}

TilingSetEvictionQueue::EventuallyTilingIterator&
    TilingSetEvictionQueue::EventuallyTilingIterator::
    operator++() {
  bool found_tile = AdvanceToNextTile(&iterator_);
  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
    ++tiling_index_;
    if (!(*tilings_)[tiling_index_]->has_eventually_rect_tiles())
      continue;
    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_eventually_rect(),
        (*tilings_)[tiling_index_]->current_skewport_rect(),
        (*tilings_)[tiling_index_]->current_soon_border_rect());
    if (!iterator_)
      continue;
    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
    if (!found_tile)
      found_tile = AdvanceToNextTile(&iterator_);
  }
  return *this;
}

// SoonBorderTilingIterator
TilingSetEvictionQueue::SoonBorderTilingIterator::SoonBorderTilingIterator(
    std::vector<PictureLayerTiling*>* tilings,
    WhichTree tree)
    : EvictionRectIterator(tilings,
                           tree,
                           PictureLayerTiling::SOON_BORDER_RECT) {
  // Find the first tiling with a tile.
  while (tiling_index_ < tilings_->size()) {
    if (!(*tilings_)[tiling_index_]->has_soon_border_rect_tiles()) {
      ++tiling_index_;
      continue;
    }
    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_soon_border_rect(),
        (*tilings_)[tiling_index_]->current_skewport_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect());
    if (!iterator_) {
      ++tiling_index_;
      continue;
    }
    break;
  }
  if (tiling_index_ >= tilings_->size())
    return;
  if (!GetFirstTileAndCheckIfValid(&iterator_))
    ++(*this);
}

TilingSetEvictionQueue::SoonBorderTilingIterator&
    TilingSetEvictionQueue::SoonBorderTilingIterator::
    operator++() {
  bool found_tile = AdvanceToNextTile(&iterator_);
  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
    ++tiling_index_;
    if (!(*tilings_)[tiling_index_]->has_soon_border_rect_tiles())
      continue;
    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_soon_border_rect(),
        (*tilings_)[tiling_index_]->current_skewport_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect());
    if (!iterator_)
      continue;
    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
    if (!found_tile)
      found_tile = AdvanceToNextTile(&iterator_);
  }
  return *this;
}

// SkewportTilingIterator
TilingSetEvictionQueue::SkewportTilingIterator::SkewportTilingIterator(
    std::vector<PictureLayerTiling*>* tilings,
    WhichTree tree)
    : EvictionRectIterator(tilings, tree, PictureLayerTiling::SKEWPORT_RECT) {
  // Find the first tiling with a tile.
  while (tiling_index_ < tilings_->size()) {
    if (!(*tilings_)[tiling_index_]->has_skewport_rect_tiles()) {
      ++tiling_index_;
      continue;
    }
    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_skewport_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect());
    if (!iterator_) {
      ++tiling_index_;
      continue;
    }
    break;
  }
  if (tiling_index_ >= tilings_->size())
    return;
  if (!GetFirstTileAndCheckIfValid(&iterator_))
    ++(*this);
}

TilingSetEvictionQueue::SkewportTilingIterator&
    TilingSetEvictionQueue::SkewportTilingIterator::
    operator++() {
  bool found_tile = AdvanceToNextTile(&iterator_);
  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
    ++tiling_index_;
    if (!(*tilings_)[tiling_index_]->has_skewport_rect_tiles())
      continue;
    iterator_ = TilingData::ReverseSpiralDifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_skewport_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect());
    if (!iterator_)
      continue;
    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
    if (!found_tile)
      found_tile = AdvanceToNextTile(&iterator_);
  }
  return *this;
}

// PendingVisibleIterator
TilingSetEvictionQueue::PendingVisibleTilingIterator::
    PendingVisibleTilingIterator(std::vector<PictureLayerTiling*>* tilings,
                                 WhichTree tree,
                                 bool return_required_for_activation_tiles)
    : EvictionRectIterator(tilings,
                           tree,
                           PictureLayerTiling::PENDING_VISIBLE_RECT),
      return_required_for_activation_tiles_(
          return_required_for_activation_tiles) {
  // Find the first tiling with a tile.
  while (tiling_index_ < tilings_->size()) {
    iterator_ = TilingData::DifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->pending_visible_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect());
    if (!iterator_) {
      ++tiling_index_;
      continue;
    }
    break;
  }
  if (tiling_index_ >= tilings_->size())
    return;
  if (!GetFirstTileAndCheckIfValid(&iterator_)) {
    ++(*this);
    return;
  }
  if (!TileMatchesRequiredFlags(prioritized_tile_)) {
    ++(*this);
    return;
  }
}

TilingSetEvictionQueue::PendingVisibleTilingIterator&
    TilingSetEvictionQueue::PendingVisibleTilingIterator::
    operator++() {
  bool found_tile = AdvanceToNextTile(&iterator_);
  while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
    found_tile = AdvanceToNextTile(&iterator_);

  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
    ++tiling_index_;
    iterator_ = TilingData::DifferenceIterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->pending_visible_rect(),
        (*tilings_)[tiling_index_]->current_visible_rect());
    if (!iterator_)
      continue;
    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
    if (!found_tile)
      found_tile = AdvanceToNextTile(&iterator_);
    while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
      found_tile = AdvanceToNextTile(&iterator_);
  }
  return *this;
}

bool TilingSetEvictionQueue::PendingVisibleTilingIterator::
    TileMatchesRequiredFlags(const PrioritizedTile& tile) const {
  bool activation_flag_matches = tile.tile()->required_for_activation() ==
                                 return_required_for_activation_tiles_;
  return activation_flag_matches;
}

// VisibleTilingIterator
TilingSetEvictionQueue::VisibleTilingIterator::VisibleTilingIterator(
    std::vector<PictureLayerTiling*>* tilings,
    WhichTree tree,
    bool return_occluded_tiles,
    bool return_required_for_activation_tiles)
    : EvictionRectIterator(tilings, tree, PictureLayerTiling::VISIBLE_RECT),
      return_occluded_tiles_(return_occluded_tiles),
      return_required_for_activation_tiles_(
          return_required_for_activation_tiles) {
  // Find the first tiling with a tile.
  while (tiling_index_ < tilings_->size()) {
    if (!(*tilings_)[tiling_index_]->has_visible_rect_tiles()) {
      ++tiling_index_;
      continue;
    }
    iterator_ = TilingData::Iterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_visible_rect(), false);
    if (!iterator_) {
      ++tiling_index_;
      continue;
    }
    break;
  }
  if (tiling_index_ >= tilings_->size())
    return;
  if (!GetFirstTileAndCheckIfValid(&iterator_)) {
    ++(*this);
    return;
  }
  if (!TileMatchesRequiredFlags(prioritized_tile_)) {
    ++(*this);
    return;
  }
}

TilingSetEvictionQueue::VisibleTilingIterator&
    TilingSetEvictionQueue::VisibleTilingIterator::
    operator++() {
  bool found_tile = AdvanceToNextTile(&iterator_);
  while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
    found_tile = AdvanceToNextTile(&iterator_);

  while (!found_tile && (tiling_index_ + 1) < tilings_->size()) {
    ++tiling_index_;
    if (!(*tilings_)[tiling_index_]->has_visible_rect_tiles())
      continue;
    iterator_ = TilingData::Iterator(
        (*tilings_)[tiling_index_]->tiling_data(),
        (*tilings_)[tiling_index_]->current_visible_rect(), false);
    if (!iterator_)
      continue;
    found_tile = GetFirstTileAndCheckIfValid(&iterator_);
    if (!found_tile)
      found_tile = AdvanceToNextTile(&iterator_);
    while (found_tile && !TileMatchesRequiredFlags(prioritized_tile_))
      found_tile = AdvanceToNextTile(&iterator_);
  }
  return *this;
}

bool TilingSetEvictionQueue::VisibleTilingIterator::TileMatchesRequiredFlags(
    const PrioritizedTile& tile) const {
  bool activation_flag_matches = tile.tile()->required_for_activation() ==
                                 return_required_for_activation_tiles_;
  bool occluded_flag_matches = tile.is_occluded() == return_occluded_tiles_;
  return activation_flag_matches && occluded_flag_matches;
}

}  // namespace cc