// Copyright 2013 The Flutter 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 FLUTTER_FLOW_DISPLAY_LIST_COMPLEXITY_HELPER_H_
#define FLUTTER_FLOW_DISPLAY_LIST_COMPLEXITY_HELPER_H_

#include "flutter/display_list/display_list_blend_mode.h"
#include "flutter/display_list/display_list_complexity.h"
#include "flutter/display_list/display_list_dispatcher.h"
#include "flutter/display_list/display_list_utils.h"

namespace flutter {

// The Metal and OpenGL complexity calculators use benchmark data gathered
// using the display_list_benchmarks test suite on real devices.
//
// Constants of proportionality and trends were chosen to better match
// larger numbers rather than smaller ones. This may turn out to be the
// wrong decision, but the rationale here is that with the smaller numbers,
// we have:
//
// a) More noise.
// b) Less absolute difference. If the constant we've chosen is out by 50%
//    on a measurement that is 0.001ms, that's less of an issue than if
//    the measurement is 15ms.
// c) Smaller numbers affect the caching decision negligibly; the caching
//    decision is likely to be driven by slower ops rather than faster ones.
//
// In some cases, a cost penalty is used to figure out the cost of an
// attribute such as anti-aliasing or fill style. In some of these, the
// penalty is proportional to some other value such as the radius of
// a circle. In these cases, we ensure that the penalty is never smaller
// than 1.0f.
//
// The error bars in measurement are likely quite large and will
// vary from device to device, so the goal here is not to provide a
// perfectly accurate representation of a given DisplayList's
// complexity but rather a very rough estimate that improves upon our
// previous cache admission policy (op_count > 5).
//
// There will likely be future work that will improve upon the figures
// in here. Notably, we do not take matrices or clips into account yet.
//
// The scoring is based around a baseline score of 100 being roughly
// equivalent to 0.0005ms of time. With a 32-bit unsigned integer, this
// would set the maximum time estimate associated with the complexity score
// at about 21 seconds, which far exceeds what we would ever expect a
// DisplayList to take rasterising.
//
// Finally, care has been taken to keep the computations as cheap as possible.
// We need to be able to calculate the complexity as quickly as possible
// so that we don't end up wasting too much time figuring out if something
// should be cached or not and eat into the time we could have just spent
// rasterising the DisplayList.
//
// In order to keep the computations cheap, the following tradeoffs were made:
//
// a) Limit all computations to simple division, multiplication, addition
//    and subtraction.
// b) Try and use integer arithmetic as much as possible.
// c) If a specific draw op is logarithmic in complexity, do a best fit
//    onto a linear equation within the range we expect to see the variables
//    fall within.
//
// As an example of the above, let's say we have some data that looks like the
// complexity is something like O(n^1/3). We would like to avoid anything too
// expensive to calculate, so taking the cube root of the value to try and
// calculate the time cost should be avoided.
//
// In this case, the approach would be to take a straight line approximation
// that maps closely in the range of n where we feel it is most likely to occur.
// For example, if this were drawLine, and n were the line length, and we
// expected the line lengths to typically be between 50 and 100, then we would
// figure out the equation of the straight line graph that approximates the
// n^1/3 curve, and if possible try and choose an approximation that is more
// representative in the range of [50, 100] for n.
//
// Once that's done, we can develop the formula as follows:
//
// Take y = mx + c (straight line graph chosen as per guidelines above).
// Divide by however many ops the benchmark ran for a single pass.
// Multiply by 200,000 to normalise 0.0005ms = 100.
// Simplify down the formula.
//
// So if we had m = 1/5 and c = 0, and the drawLines benchmark ran 10,000
// drawLine calls per iteration:
//
//   y (time taken) = x (line length) / 5
//   y = x / 5 * 200,000 / 10,000
//   y = x / 5 * 20
//   y = 4x

class ComplexityCalculatorHelper
    : public virtual Dispatcher,
      public virtual IgnoreClipDispatchHelper,
      public virtual IgnoreTransformDispatchHelper {
 public:
  ComplexityCalculatorHelper(unsigned int ceiling)
      : is_complex_(false), ceiling_(ceiling), complexity_score_(0) {}

  virtual ~ComplexityCalculatorHelper() = default;

  void setDither(bool dither) override {}
  void setInvertColors(bool invert) override {}
  void setStrokeCap(SkPaint::Cap cap) override {}
  void setStrokeJoin(SkPaint::Join join) override {}
  void setStrokeMiter(SkScalar limit) override {}
  void setColor(SkColor color) override {}
  void setBlendMode(DlBlendMode mode) override {}
  void setBlender(sk_sp<SkBlender> blender) override {}
  void setColorSource(const DlColorSource* source) override {}
  void setImageFilter(const DlImageFilter* filter) override {}
  void setColorFilter(const DlColorFilter* filter) override {}
  void setPathEffect(sk_sp<SkPathEffect> effect) override {}
  void setMaskFilter(const DlMaskFilter* filter) override {}

  void save() override {}
  // We accumulate the cost of restoring a saveLayer() in saveLayer()
  void restore() override {}

  void setAntiAlias(bool aa) override { current_paint_.setAntiAlias(aa); }

  void setStyle(SkPaint::Style style) override {
    current_paint_.setStyle(style);
  }

  void setStrokeWidth(SkScalar width) override {
    current_paint_.setStrokeWidth(width);
  }

  void drawColor(SkColor color, DlBlendMode mode) override {
    if (IsComplex()) {
      return;
    }
    // Placeholder value here. This is a relatively cheap operation.
    AccumulateComplexity(50);
  }

  void drawPaint() override {
    if (IsComplex()) {
      return;
    }
    // Placeholder value here. This can be cheap (e.g. effectively a drawColor),
    // or expensive (e.g. a bitmap shader with an image filter)
    AccumulateComplexity(50);
  }

  void drawImageRect(const sk_sp<DlImage> image,
                     const SkRect& src,
                     const SkRect& dst,
                     const SkSamplingOptions& sampling,
                     bool render_with_attributes,
                     SkCanvas::SrcRectConstraint constraint) override {
    if (IsComplex()) {
      return;
    }
    ImageRect(image->dimensions(), image->isTextureBacked(),
              render_with_attributes, constraint);
  }

  void drawImageLattice(const sk_sp<DlImage> image,
                        const SkCanvas::Lattice& lattice,
                        const SkRect& dst,
                        SkFilterMode filter,
                        bool render_with_attributes) override {
    if (IsComplex()) {
      return;
    }
    // This is not currently called from Flutter code, and this API is likely
    // to be removed in the future. For now, just return what drawImageNine
    // would
    ImageRect(image->dimensions(), image->isTextureBacked(),
              render_with_attributes,
              SkCanvas::SrcRectConstraint::kStrict_SrcRectConstraint);
  }

  void drawAtlas(const sk_sp<DlImage> atlas,
                 const SkRSXform xform[],
                 const SkRect tex[],
                 const SkColor colors[],
                 int count,
                 DlBlendMode mode,
                 const SkSamplingOptions& sampling,
                 const SkRect* cull_rect,
                 bool render_with_attributes) override {
    if (IsComplex()) {
      return;
    }
    // This API just does a series of drawImage calls from the atlas
    // This is equivalent to calling drawImageRect lots of times
    for (int i = 0; i < count; i++) {
      ImageRect(SkISize::Make(tex[i].width(), tex[i].height()), true,
                render_with_attributes,
                SkCanvas::SrcRectConstraint::kStrict_SrcRectConstraint);
    }
  }

  void drawPicture(const sk_sp<SkPicture> picture,
                   const SkMatrix* matrix,
                   bool render_with_attributes) override {
    // This API shouldn't be used, but for now just take the
    // approximateOpCount() and multiply by 50 as a placeholder.
    AccumulateComplexity(picture->approximateOpCount() * 50);
  }

  // This method finalizes the complexity score calculation and returns it
  unsigned int ComplexityScore() {
    // We hit our ceiling, so return that
    if (IsComplex()) {
      return Ceiling();
    }

    // Calculate the impact of any draw ops where the complexity is dependent
    // on the number of calls made.
    unsigned int batched_complexity = BatchedComplexity();

    // Check for overflow
    if (Ceiling() - complexity_score_ < batched_complexity) {
      return Ceiling();
    }

    return complexity_score_ + batched_complexity;
  }

 protected:
  void AccumulateComplexity(unsigned int complexity) {
    // Check to see if we will overflow by accumulating this complexity score
    if (ceiling_ - complexity_score_ < complexity) {
      is_complex_ = true;
      return;
    }

    complexity_score_ += complexity;
  }

  inline bool IsAntiAliased() { return current_paint_.isAntiAlias(); }
  inline bool IsHairline() { return current_paint_.getStrokeWidth() == 0.0f; }
  inline SkPaint::Style Style() { return current_paint_.getStyle(); }
  inline bool IsComplex() { return is_complex_; }
  inline unsigned int Ceiling() { return ceiling_; }
  inline unsigned int CurrentComplexityScore() { return complexity_score_; }

  unsigned int CalculatePathComplexity(const SkPath& path,
                                       unsigned int line_verb_cost,
                                       unsigned int quad_verb_cost,
                                       unsigned int conic_verb_cost,
                                       unsigned int cubic_verb_cost) {
    int verb_count = path.countVerbs();
    uint8_t verbs[verb_count];
    path.getVerbs(verbs, verb_count);

    unsigned int complexity = 0;
    for (int i = 0; i < verb_count; i++) {
      switch (verbs[i]) {
        case SkPath::Verb::kLine_Verb:
          complexity += line_verb_cost;
          break;
        case SkPath::Verb::kQuad_Verb:
          complexity += quad_verb_cost;
          break;
        case SkPath::Verb::kConic_Verb:
          complexity += conic_verb_cost;
          break;
        case SkPath::Verb::kCubic_Verb:
          complexity += cubic_verb_cost;
          break;
      }
    }
    return complexity;
  }

  virtual void ImageRect(const SkISize& size,
                         bool texture_backed,
                         bool render_with_attributes,
                         SkCanvas::SrcRectConstraint constraint) = 0;

  // This calculates and returns the cost of draw calls which are batched and
  // thus have a time cost proportional to the number of draw calls made, such
  // as saveLayer and drawTextBlob.
  virtual unsigned int BatchedComplexity() = 0;

 private:
  SkPaint current_paint_;

  // If we exceed the ceiling (defaults to the largest number representable
  // by unsigned int), then set the is_complex_ bool and we no longer
  // accumulate.
  bool is_complex_;
  unsigned int ceiling_;

  unsigned int complexity_score_;
};

}  // namespace flutter

#endif  // FLUTTER_FLOW_DISPLAY_LIST_COMPLEXITY_HELPER_H_