// Copyright (C) 2023 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

import {BigintMath} from '../base/bigint_math';
import {Duration, duration} from '../base/time';
import {globals} from '../frontend/globals';

// We choose 100000 as the table size to cache as this is roughly the point
// where SQLite sorts start to become expensive.
const MIN_TABLE_SIZE_TO_CACHE = 100000;

// Decides, based on the length of the trace and the number of rows
// provided whether a TrackController subclass should cache its quantized
// data. Returns the bucket size (in ns) if caching should happen and
// undefined otherwise.
export function calcCachedBucketSize(numRows: number): duration | undefined {
  // Ensure that we're not caching when the table size isn't even that big.
  if (numRows < MIN_TABLE_SIZE_TO_CACHE) {
    return undefined;
  }

  const traceDuration = globals.stateTraceTimeTP().duration;

  // For large traces, going through the raw table in the most zoomed-out
  // states can be very expensive as this can involve going through O(millions
  // of rows). The cost of this becomes high even for just iteration but is
  // especially slow as quantization involves a SQLite sort on the quantized
  // timestamp (for the group by).
  //
  // To get around this, we can cache a pre-quantized table which we can then
  // in zoomed-out situations and fall back to the real table when zoomed in
  // (which naturally constrains the amount of data by virtue of the window
  // covering a smaller timespan)
  //
  // This method computes that cached table by computing an approximation for
  // the bucket size we would use when totally zoomed out and then going a few
  // resolution levels down which ensures that our cached table works for more
  // than the literally most zoomed out state. Moving down a resolution level
  // is defined as moving down a power of 2; this matches the logic in
  // |globals.getCurResolution|.
  //
  // TODO(lalitm): in the future, we should consider having a whole set of
  // quantized tables each of which cover some portion of resolution lvel
  // range. As each table covers a large number of resolution levels, even 3-4
  // tables should really cover the all concievable trace sizes. This set
  // could be computed by looking at the number of events being processed one
  // level below the cached table and computing another layer of caching if
  // that count is too high (with respect to MIN_TABLE_SIZE_TO_CACHE).

  // 4k monitors have 3840 horizontal pixels so use that for a worst case
  // approximation of the window width.
  const approxWidthPx = 3840n;

  // Compute the outermost bucket size. This acts as a starting point for
  // computing the cached size.
  const outermostBucketSize = BigintMath.bitCeil(traceDuration / approxWidthPx);
  const outermostResolutionLevel = BigintMath.log2(outermostBucketSize);

  // This constant decides how many resolution levels down from our outermost
  // bucket computation we want to be able to use the cached table.
  // We've chosen 7 as it empirically seems to be a good fit for trace data.
  const resolutionLevelsCovered = 7n;

  // If we've got less resolution levels in the trace than the number of
  // resolution levels we want to go down, bail out because this cached
  // table is really not going to be used enough.
  if (outermostResolutionLevel < resolutionLevelsCovered) {
    return Duration.MAX;
  }

  // Another way to look at moving down resolution levels is to consider how
  // many sub-intervals we are splitting the bucket into.
  const bucketSubIntervals = 1n << resolutionLevelsCovered;

  // Calculate the smallest bucket we want our table to be able to handle by
  // dividing the outermsot bucket by the number of subintervals we should
  // divide by.
  const cachedBucketSize = outermostBucketSize / bucketSubIntervals;

  return cachedBucketSize;
}