/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "CacheIndex.h"
#include "CacheLog.h"
#include "CacheFileUtils.h"
#include "CacheObserver.h"
#include "LoadContextInfo.h"
#include "mozilla/glean/NetwerkProtocolHttpMetrics.h"
#include "mozilla/Tokenizer.h"
#include "mozilla/Telemetry.h"
#include "nsCOMPtr.h"
#include "nsString.h"
#include <algorithm>

namespace mozilla::net::CacheFileUtils {

// This designates the format for the "alt-data" metadata.
// When the format changes we need to update the version.
static uint32_t const kAltDataVersion = 1;
const char* kAltDataKey = "alt-data";

namespace {

/**
 * A simple recursive descent parser for the mapping key.
 */
class KeyParser : protected Tokenizer {
 public:
  explicit KeyParser(nsACString const& aInput)
      : Tokenizer(aInput),
        isAnonymous(false)
        // Initialize the cache key to a zero length by default
        ,
        lastTag(0) {}

 private:
  // Results
  OriginAttributes originAttribs;
  bool isAnonymous;
  nsCString idEnhance;
  nsDependentCSubstring cacheKey;

  // Keeps the last tag name, used for alphabetical sort checking
  char lastTag;

  // Classifier for the 'tag' character valid range.
  // Explicitly using unsigned char as 127 is -1 when signed and it would only
  // produce a warning.
  static bool TagChar(const char aChar) {
    unsigned char c = static_cast<unsigned char>(aChar);
    return c >= ' ' && c <= '\x7f';
  }

  bool ParseTags() {
    // Expects to be at the tag name or at the end
    if (CheckEOF()) {
      return true;
    }

    char tag;
    if (!ReadChar(&TagChar, &tag)) {
      return false;
    }

    // Check the alphabetical order, hard-fail on disobedience
    if (!(lastTag < tag || tag == ':')) {
      return false;
    }
    lastTag = tag;

    switch (tag) {
      case ':':
        // last possible tag, when present there is the cacheKey following,
        // not terminated with ',' and no need to unescape.
        cacheKey.Rebind(mCursor, mEnd - mCursor);
        return true;
      case 'O': {
        nsAutoCString originSuffix;
        if (!ParseValue(&originSuffix) ||
            !originAttribs.PopulateFromSuffix(originSuffix)) {
          return false;
        }
        break;
      }
      case 'p':
        originAttribs.SyncAttributesWithPrivateBrowsing(true);
        break;
      case 'b':
        // Leaving to be able to read and understand oldformatted entries
        break;
      case 'a':
        isAnonymous = true;
        break;
      case 'i': {
        // Leaving to be able to read and understand oldformatted entries
        uint32_t deprecatedAppId = 0;
        if (!ReadInteger(&deprecatedAppId)) {
          return false;  // not a valid 32-bit integer
        }
        break;
      }
      case '~':
        if (!ParseValue(&idEnhance)) {
          return false;
        }
        break;
      default:
        if (!ParseValue()) {  // skip any tag values, optional
          return false;
        }
        break;
    }

    // We expect a comma after every tag
    if (!CheckChar(',')) {
      return false;
    }

    // Recurse to the next tag
    return ParseTags();
  }

  bool ParseValue(nsACString* result = nullptr) {
    // If at the end, fail since we expect a comma ; value may be empty tho
    if (CheckEOF()) {
      return false;
    }

    Token t;
    while (Next(t)) {
      if (!Token::Char(',').Equals(t)) {
        if (result) {
          result->Append(t.Fragment());
        }
        continue;
      }

      if (CheckChar(',')) {
        // Two commas in a row, escaping
        if (result) {
          result->Append(',');
        }
        continue;
      }

      // We must give the comma back since the upper calls expect it
      Rollback();
      return true;
    }

    return false;
  }

 public:
  already_AddRefed<LoadContextInfo> Parse() {
    RefPtr<LoadContextInfo> info;
    if (ParseTags()) {
      info = GetLoadContextInfo(isAnonymous, originAttribs);
    }

    return info.forget();
  }

  void URISpec(nsACString& result) { result.Assign(cacheKey); }

  void IdEnhance(nsACString& result) { result.Assign(idEnhance); }
};

}  // namespace

already_AddRefed<nsILoadContextInfo> ParseKey(const nsACString& aKey,
                                              nsACString* aIdEnhance,
                                              nsACString* aURISpec) {
  KeyParser parser(aKey);
  RefPtr<LoadContextInfo> info = parser.Parse();

  if (info) {
    if (aIdEnhance) parser.IdEnhance(*aIdEnhance);
    if (aURISpec) parser.URISpec(*aURISpec);
  }

  return info.forget();
}

void AppendKeyPrefix(nsILoadContextInfo* aInfo, nsACString& _retval) {
  /**
   * This key is used to salt file hashes.  When form of the key is changed
   * cache entries will fail to find on disk.
   *
   * IMPORTANT NOTE:
   * Keep the attributes list sorted according their ASCII code.
   */

  if (!aInfo) {
    return;
  }

  OriginAttributes const* oa = aInfo->OriginAttributesPtr();
  nsAutoCString suffix;
  oa->CreateSuffix(suffix);
  if (!suffix.IsEmpty()) {
    AppendTagWithValue(_retval, 'O', suffix);
  }

  if (aInfo->IsAnonymous()) {
    _retval.AppendLiteral("a,");
  }

  if (aInfo->IsPrivate()) {
    _retval.AppendLiteral("p,");
  }
}

void AppendTagWithValue(nsACString& aTarget, char const aTag,
                        const nsACString& aValue) {
  aTarget.Append(aTag);

  // First check the value string to save some memory copying
  // for cases we don't need to escape at all (most likely).
  if (!aValue.IsEmpty()) {
    if (!aValue.Contains(',')) {
      // No need to escape
      aTarget.Append(aValue);
    } else {
      nsAutoCString escapedValue(aValue);
      escapedValue.ReplaceSubstring(","_ns, ",,"_ns);
      aTarget.Append(escapedValue);
    }
  }

  aTarget.Append(',');
}

nsresult KeyMatchesLoadContextInfo(const nsACString& aKey,
                                   nsILoadContextInfo* aInfo, bool* _retval) {
  nsCOMPtr<nsILoadContextInfo> info = ParseKey(aKey);

  if (!info) {
    return NS_ERROR_FAILURE;
  }

  *_retval = info->Equals(aInfo);
  return NS_OK;
}

ValidityPair::ValidityPair(uint32_t aOffset, uint32_t aLen)
    : mOffset(aOffset), mLen(aLen) {}

bool ValidityPair::CanBeMerged(const ValidityPair& aOther) const {
  // The pairs can be merged into a single one if the start of one of the pairs
  // is placed anywhere in the validity interval of other pair or exactly after
  // its end.
  return IsInOrFollows(aOther.mOffset) || aOther.IsInOrFollows(mOffset);
}

bool ValidityPair::IsInOrFollows(uint32_t aOffset) const {
  return mOffset <= aOffset && mOffset + mLen >= aOffset;
}

bool ValidityPair::LessThan(const ValidityPair& aOther) const {
  if (mOffset < aOther.mOffset) {
    return true;
  }

  if (mOffset == aOther.mOffset && mLen < aOther.mLen) {
    return true;
  }

  return false;
}

void ValidityPair::Merge(const ValidityPair& aOther) {
  MOZ_ASSERT(CanBeMerged(aOther));

  uint32_t offset = std::min(mOffset, aOther.mOffset);
  uint32_t end = std::max(mOffset + mLen, aOther.mOffset + aOther.mLen);

  mOffset = offset;
  mLen = end - offset;
}

void ValidityMap::Log() const {
  LOG(("ValidityMap::Log() - number of pairs: %zu", mMap.Length()));
  for (uint32_t i = 0; i < mMap.Length(); i++) {
    LOG(("    (%u, %u)", mMap[i].Offset() + 0, mMap[i].Len() + 0));
  }
}

uint32_t ValidityMap::Length() const { return mMap.Length(); }

void ValidityMap::AddPair(uint32_t aOffset, uint32_t aLen) {
  ValidityPair pair(aOffset, aLen);

  if (mMap.Length() == 0) {
    mMap.AppendElement(pair);
    return;
  }

  // Find out where to place this pair into the map, it can overlap only with
  // one preceding pair and all subsequent pairs.
  uint32_t pos = 0;
  for (pos = mMap.Length(); pos > 0;) {
    --pos;

    if (mMap[pos].LessThan(pair)) {
      // The new pair should be either inserted after pos or merged with it.
      if (mMap[pos].CanBeMerged(pair)) {
        // Merge with the preceding pair
        mMap[pos].Merge(pair);
      } else {
        // They don't overlap, element must be placed after pos element
        ++pos;
        if (pos == mMap.Length()) {
          mMap.AppendElement(pair);
        } else {
          mMap.InsertElementAt(pos, pair);
        }
      }

      break;
    }

    if (pos == 0) {
      // The new pair should be placed in front of all existing pairs.
      mMap.InsertElementAt(0, pair);
    }
  }

  // pos now points to merged or inserted pair, check whether it overlaps with
  // subsequent pairs.
  while (pos + 1 < mMap.Length()) {
    if (mMap[pos].CanBeMerged(mMap[pos + 1])) {
      mMap[pos].Merge(mMap[pos + 1]);
      mMap.RemoveElementAt(pos + 1);
    } else {
      break;
    }
  }
}

void ValidityMap::Clear() { mMap.Clear(); }

size_t ValidityMap::SizeOfExcludingThis(
    mozilla::MallocSizeOf mallocSizeOf) const {
  return mMap.ShallowSizeOfExcludingThis(mallocSizeOf);
}

ValidityPair& ValidityMap::operator[](uint32_t aIdx) {
  return mMap.ElementAt(aIdx);
}

StaticMutex DetailedCacheHitTelemetry::sLock;
uint32_t DetailedCacheHitTelemetry::sRecordCnt = 0;
constinit DetailedCacheHitTelemetry::HitRate
    DetailedCacheHitTelemetry::sHRStats[kNumOfRanges];

void DetailedCacheHitTelemetry::HitRate::AddRecord(ERecType aType) {
  if (aType == HIT) {
    ++mHitCnt;
  } else {
    ++mMissCnt;
  }
}

uint32_t DetailedCacheHitTelemetry::HitRate::GetHitRateBucket() const {
  if (mHitCnt + mMissCnt == 0) {
    return 0;
  }
  return (100 * mHitCnt) / (mHitCnt + mMissCnt);
}

uint32_t DetailedCacheHitTelemetry::HitRate::Count() {
  return mHitCnt + mMissCnt;
}

void DetailedCacheHitTelemetry::HitRate::Reset() {
  mHitCnt = 0;
  mMissCnt = 0;
}

// static
void DetailedCacheHitTelemetry::AddRecord(ERecType aType,
                                          TimeStamp aLoadStart) {
  bool isUpToDate = false;
  CacheIndex::IsUpToDate(&isUpToDate);
  if (!isUpToDate) {
    // Ignore the record when the entry file count might be incorrect
    return;
  }

  uint32_t entryCount;
  nsresult rv = CacheIndex::GetEntryFileCount(&entryCount);
  if (NS_FAILED(rv)) {
    return;
  }

  uint32_t rangeIdx = entryCount / kRangeSize;
  if (rangeIdx >= kNumOfRanges) {  // The last range has no upper limit.
    rangeIdx = kNumOfRanges - 1;
  }

#ifndef ANDROID
  nsAutoCString hitMissValue;
  if (aType == HIT) {
    hitMissValue.AppendLiteral("Hit ");
  } else {
    hitMissValue.AppendLiteral("Miss ");
  }

  uint32_t lowerBound = rangeIdx * kRangeSize;
  if (rangeIdx < kNumOfRanges - 1) {
    uint32_t upperBound = (rangeIdx + 1) * kRangeSize - 1;
    hitMissValue.AppendInt(lowerBound);
    hitMissValue.AppendLiteral("-");
    hitMissValue.AppendInt(upperBound);
  } else {
    // Since no upper limit
    hitMissValue.AppendInt(lowerBound);
    hitMissValue.AppendLiteral("+");
  }
#endif

  StaticMutexAutoLock lock(sLock);

  if (aType == MISS) {
    mozilla::glean::network::cache_miss_time.AccumulateRawDuration(
        TimeStamp::Now() - aLoadStart);
  } else {
    mozilla::glean::network::cache_hit_time.AccumulateRawDuration(
        TimeStamp::Now() - aLoadStart);
  }
#ifndef ANDROID
  mozilla::glean::network::cache_hit_miss_stat_per_cache_size.Get(hitMissValue)
      .Add(1);
#endif

  sHRStats[rangeIdx].AddRecord(aType);
  ++sRecordCnt;

  if (sRecordCnt < kTotalSamplesReportLimit) {
    return;
  }

  sRecordCnt = 0;

  for (uint32_t i = 0; i < kNumOfRanges; ++i) {
    if (sHRStats[i].Count() >= kHitRateSamplesReportLimit) {
#ifndef ANDROID
      nsAutoCString cacheSizeIdx;
      cacheSizeIdx.AppendInt(i);
      uint32_t hitRateBucket = sHRStats[i].GetHitRateBucket();

      mozilla::glean::network::cache_hit_rate_per_cache_size.Get(cacheSizeIdx)
          .AccumulateSingleSample(hitRateBucket);
#endif
      sHRStats[i].Reset();
    }
  }
}

void FreeBuffer(void* aBuf) {
#ifndef NS_FREE_PERMANENT_DATA
  if (CacheObserver::ShuttingDown()) {
    return;
  }
#endif

  free(aBuf);
}

nsresult ParseAlternativeDataInfo(const char* aInfo, int64_t* _offset,
                                  nsACString* _type) {
  // The format is: "1;12345,javascript/binary"
  //         <version>;<offset>,<type>
  mozilla::Tokenizer p(aInfo, nullptr, "/");
  uint32_t altDataVersion = 0;
  int64_t altDataOffset = -1;

  // The metadata format has a wrong version number.
  if (!p.ReadInteger(&altDataVersion) || altDataVersion != kAltDataVersion) {
    LOG(
        ("ParseAlternativeDataInfo() - altDataVersion=%u, "
         "expectedVersion=%u",
         altDataVersion, kAltDataVersion));
    return NS_ERROR_NOT_AVAILABLE;
  }

  if (!p.CheckChar(';') || !p.ReadInteger(&altDataOffset) ||
      !p.CheckChar(',')) {
    return NS_ERROR_NOT_AVAILABLE;
  }

  // The requested alt-data representation is not available
  if (altDataOffset < 0) {
    return NS_ERROR_NOT_AVAILABLE;
  }

  if (_offset) {
    *_offset = altDataOffset;
  }

  if (_type) {
    (void)p.ReadUntil(Tokenizer::Token::EndOfFile(), *_type);
  }

  return NS_OK;
}

void BuildAlternativeDataInfo(const char* aInfo, int64_t aOffset,
                              nsACString& _retval) {
  _retval.Truncate();
  _retval.AppendInt(kAltDataVersion);
  _retval.Append(';');
  _retval.AppendInt(aOffset);
  _retval.Append(',');
  _retval.Append(aInfo);
}

}  // namespace mozilla::net::CacheFileUtils