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

#include "extensions/browser/api/alarms/alarm_manager.h"

#include <stddef.h>

#include <algorithm>
#include <memory>
#include <utility>
#include <vector>

#include "base/containers/map_util.h"
#include "base/functional/bind.h"
#include "base/json/json_writer.h"
#include "base/json/values_util.h"
#include "base/lazy_instance.h"
#include "base/memory/raw_ptr.h"
#include "base/metrics/histogram_functions.h"
#include "base/numerics/safe_conversions.h"
#include "base/time/clock.h"
#include "base/time/default_clock.h"
#include "base/time/time.h"
#include "base/values.h"
#include "extensions/browser/api/alarms/alarms_api_constants.h"
#include "extensions/browser/event_router.h"
#include "extensions/browser/extension_registry_factory.h"
#include "extensions/browser/extension_system.h"
#include "extensions/browser/state_store.h"
#include "extensions/common/api/alarms.h"
#include "extensions/common/extension_id.h"

namespace extensions {

namespace alarms = api::alarms;

namespace {

// A list of alarms that this extension has set.
const char kRegisteredAlarms[] = "alarms";
const char kAlarmGranularity[] = "granularity";
const char kAlarmPersistAcrossSessions[] = "persistAcrossSessions";

// The minimum period between polling for alarms to run.
const base::TimeDelta kDefaultMinPollPeriod() {
  return base::Days(1);
}

class DefaultAlarmDelegate : public AlarmManager::Delegate {
 public:
  explicit DefaultAlarmDelegate(content::BrowserContext* context)
      : browser_context_(context) {}
  ~DefaultAlarmDelegate() override {}

  void OnAlarm(const ExtensionId& extension_id, const Alarm& alarm) override {
    base::ListValue args;
    args.Append(alarm.js_alarm->ToValue());
    auto event = std::make_unique<Event>(events::ALARMS_ON_ALARM,
                                         alarms::OnAlarm::kEventName,
                                         std::move(args), browser_context_);
    EventRouter::Get(browser_context_)
        ->DispatchEventToExtension(extension_id, std::move(event));
  }

 private:
  raw_ptr<content::BrowserContext> browser_context_;
};

// Creates a TimeDelta from a delay as specified in the API.
base::TimeDelta TimeDeltaFromDelay(double delay_in_minutes) {
  return base::Microseconds(delay_in_minutes *
                            base::Time::kMicrosecondsPerMinute);
}

// Values of histogram "Extensions.AlarmManager.AlarmsMaxNameLength"
// must match enum ExtensionAlarmsNameLength.
enum class AlarmNameLength {
  k0_10,
  k11_25,
  k26_50,
  k51_75,
  k76_100,
  k101_125,
  k126_250,
  k251_500,
  k501_1000,
  k1001_2000,
  k2001_5000,
  k5001_10k,
  k100k,
  k1m,
  k100m,
  kLarge,
  kMaxValue = kLarge,
};

AlarmNameLength AlarmNameLengthToBucket(size_t length) {
  if (length <= 10) {
    return AlarmNameLength::k0_10;
  }
  if (length <= 25) {
    return AlarmNameLength::k11_25;
  }
  if (length <= 50) {
    return AlarmNameLength::k26_50;
  }
  if (length <= 75) {
    return AlarmNameLength::k51_75;
  }
  if (length <= 100) {
    return AlarmNameLength::k76_100;
  }
  if (length <= 125) {
    return AlarmNameLength::k101_125;
  }
  if (length <= 250) {
    return AlarmNameLength::k126_250;
  }
  if (length <= 500) {
    return AlarmNameLength::k251_500;
  }
  if (length <= 1000) {
    return AlarmNameLength::k501_1000;
  }
  if (length <= 2000) {
    return AlarmNameLength::k1001_2000;
  }
  if (length <= 5000) {
    return AlarmNameLength::k2001_5000;
  }
  if (length <= 10000) {
    return AlarmNameLength::k5001_10k;
  }
  if (length <= 100000) {
    return AlarmNameLength::k100k;
  }
  if (length <= 1000000) {
    return AlarmNameLength::k1m;
  }
  if (length <= 100000000) {
    return AlarmNameLength::k100m;
  }
  return AlarmNameLength::kLarge;
}

AlarmManager::AlarmList AlarmsFromValue(base::TimeDelta min_delay,
                                        const base::ListValue& list) {
  AlarmManager::AlarmList alarms;
  const int max_to_create = std::min(base::saturated_cast<int>(list.size()),
                                     AlarmManager::kMaxAlarmsPerExtension);

  size_t max_name_length = 0;
  for (int i = 0; i < max_to_create; ++i) {
    base::DictValue alarm_value = list[i].GetDict().Clone();

    // If this key does not exist, it means the alarm was written to the state
    // store by an older Chrome version before we had support for non-persistent
    // alarms. We should make them persistent by default in this case as the
    // alarm would have been persistent in older Chrome versions.
    // TODO(crbug.com/503787228): Remove this Clone and default value logic once
    // default values are supported on API schema dictionaries.
    if (!alarm_value.Find(kAlarmPersistAcrossSessions)) {
      alarm_value.Set(kAlarmPersistAcrossSessions, true);
    }

    Alarm alarm;
    alarm.js_alarm = alarms::Alarm::FromValue(alarm_value);
    if (alarm.js_alarm) {
      // Find the maximum alarm name for a histogram.
      max_name_length =
          std::max(max_name_length, alarm.js_alarm->name.length());
      std::optional<base::TimeDelta> delta =
          base::ValueToTimeDelta(alarm_value.Find(kAlarmGranularity));
      if (delta) {
        alarm.granularity = *delta;
        // No else branch. It's okay to ignore the failure since we have
        // minimum granularity.
      }
      alarm.minimum_granularity = min_delay;
      if (alarm.granularity < alarm.minimum_granularity) {
        alarm.granularity = alarm.minimum_granularity;
      }
      alarms.emplace_back(std::move(alarm));
    }
  }
  if (max_to_create > 0) {
    base::UmaHistogramEnumeration("Extensions.AlarmManager.AlarmsMaxNameLength",
                                  AlarmNameLengthToBucket(max_name_length));
  }
  return alarms;
}

base::ListValue PersistentAlarmsToValue(const AlarmManager::AlarmList& alarms) {
  base::ListValue list;
  for (const auto& item : alarms) {
    if (!item.js_alarm->persist_across_sessions) {
      continue;
    }
    base::DictValue alarm = item.js_alarm->ToValue();
    alarm.Set(kAlarmGranularity, base::TimeDeltaToValue(item.granularity));
    list.Append(std::move(alarm));
  }
  return list;
}

}  // namespace

// AlarmManager

AlarmManager::AlarmManager(content::BrowserContext* context)
    : browser_context_(context),
      clock_(base::DefaultClock::GetInstance()),
      delegate_(new DefaultAlarmDelegate(context)) {
  extension_registry_observation_.Observe(
      ExtensionRegistry::Get(browser_context_));

  StateStore* storage = ExtensionSystem::Get(browser_context_)->state_store();
  if (storage) {
    storage->RegisterKey(kRegisteredAlarms);
  }
}

AlarmManager::~AlarmManager() = default;

int AlarmManager::GetCountForExtension(const ExtensionId& extension_id) const {
  auto it = alarms_.find(extension_id);
  return it == alarms_.end() ? 0 : it->second.size();
}

void AlarmManager::AddAlarm(const ExtensionId& extension_id,
                            Alarm alarm,
                            AddAlarmCallback callback) {
  RunWhenReady(extension_id,
               base::BindOnce(&AlarmManager::AddAlarmWhenReady,
                              weak_ptr_factory_.GetWeakPtr(), std::move(alarm),
                              std::move(callback)));
}

void AlarmManager::GetAlarm(const ExtensionId& extension_id,
                            const std::string& name,
                            GetAlarmCallback callback) {
  RunWhenReady(extension_id, base::BindOnce(&AlarmManager::GetAlarmWhenReady,
                                            weak_ptr_factory_.GetWeakPtr(),
                                            name, std::move(callback)));
}

void AlarmManager::GetAllAlarms(const ExtensionId& extension_id,
                                GetAllAlarmsCallback callback) {
  RunWhenReady(
      extension_id,
      base::BindOnce(&AlarmManager::GetAllAlarmsWhenReady,
                     weak_ptr_factory_.GetWeakPtr(), std::move(callback)));
}

void AlarmManager::RemoveAlarm(const ExtensionId& extension_id,
                               const std::string& name,
                               RemoveAlarmCallback callback) {
  RunWhenReady(extension_id, base::BindOnce(&AlarmManager::RemoveAlarmWhenReady,
                                            weak_ptr_factory_.GetWeakPtr(),
                                            name, std::move(callback)));
}

void AlarmManager::RemoveAllAlarms(const ExtensionId& extension_id,
                                   RemoveAllAlarmsCallback callback) {
  RunWhenReady(
      extension_id,
      base::BindOnce(&AlarmManager::RemoveAllAlarmsWhenReady,
                     weak_ptr_factory_.GetWeakPtr(), std::move(callback)));
}

void AlarmManager::AddAlarmWhenReady(Alarm alarm,
                                     AddAlarmCallback callback,
                                     const ExtensionId& extension_id) {
  AddAlarmImpl(extension_id, std::move(alarm));
  WriteToStorage(extension_id);
  std::move(callback).Run();
}

void AlarmManager::GetAlarmWhenReady(const std::string& name,
                                     GetAlarmCallback callback,
                                     const ExtensionId& extension_id) {
  AlarmIterator it = GetAlarmIterator(extension_id, name);
  std::move(callback).Run(it.first != alarms_.end() ? &*it.second : nullptr);
}

void AlarmManager::GetAllAlarmsWhenReady(GetAllAlarmsCallback callback,
                                         const ExtensionId& extension_id) {
  auto list = alarms_.find(extension_id);
  std::move(callback).Run(list != alarms_.end() ? &list->second : nullptr);
}

void AlarmManager::RemoveAlarmWhenReady(const std::string& name,
                                        RemoveAlarmCallback callback,
                                        const ExtensionId& extension_id) {
  AlarmIterator it = GetAlarmIterator(extension_id, name);
  if (it.first == alarms_.end()) {
    std::move(callback).Run(false);
    return;
  }

  RemoveAlarmIterator(it);
  WriteToStorage(extension_id);
  std::move(callback).Run(true);
}

void AlarmManager::RemoveAllAlarmsWhenReady(RemoveAllAlarmsCallback callback,
                                            const ExtensionId& extension_id) {
  if (RemoveAllAlarmsInternal(extension_id)) {
    WriteToStorage(extension_id);
  }
  std::move(callback).Run();
}

bool AlarmManager::RemoveAllAlarmsInternal(const ExtensionId& extension_id) {
  auto list = alarms_.find(extension_id);
  if (list != alarms_.end()) {
    // Note: I'm using indices rather than iterators here because
    // RemoveAlarmIterator will delete the list when it becomes empty.
    for (size_t i = 0, size = list->second.size(); i < size; ++i) {
      RemoveAlarmIterator(AlarmIterator(list, list->second.begin()));
    }

    CHECK(alarms_.find(extension_id) == alarms_.end());
    return true;
  }
  return false;
}

AlarmManager::AlarmIterator AlarmManager::GetAlarmIterator(
    const ExtensionId& extension_id,
    const std::string& name) {
  auto list = alarms_.find(extension_id);
  if (list == alarms_.end()) {
    return make_pair(alarms_.end(), AlarmList::iterator());
  }

  for (auto it = list->second.begin(); it != list->second.end(); ++it) {
    if (it->js_alarm->name == name) {
      return make_pair(list, it);
    }
  }

  return make_pair(alarms_.end(), AlarmList::iterator());
}

void AlarmManager::SetClockForTesting(base::Clock* clock) {
  clock_ = clock;
}

static base::LazyInstance<
    BrowserContextKeyedAPIFactory<AlarmManager>>::DestructorAtExit g_factory =
    LAZY_INSTANCE_INITIALIZER;

template <>
void BrowserContextKeyedAPIFactory<AlarmManager>::DeclareFactoryDependencies() {
  DependsOn(ExtensionRegistryFactory::GetInstance());
}

// static
BrowserContextKeyedAPIFactory<AlarmManager>*
AlarmManager::GetFactoryInstance() {
  return g_factory.Pointer();
}

// static
AlarmManager* AlarmManager::Get(content::BrowserContext* browser_context) {
  return BrowserContextKeyedAPIFactory<AlarmManager>::Get(browser_context);
}

void AlarmManager::RemoveAlarmIterator(const AlarmIterator& iter) {
  AlarmList& list = iter.first->second;
  list.erase(iter.second);
  if (list.empty()) {
    alarms_.erase(iter.first);
  }

  // Cancel the timer if there are no more alarms.
  // We don't need to reschedule the poll otherwise, because in
  // the worst case we would just poll one extra time.
  if (alarms_.empty()) {
    timer_.Stop();
    next_poll_time_ = base::Time();
  }
}

void AlarmManager::OnAlarm(AlarmIterator it) {
  CHECK(it.first != alarms_.end());
  Alarm& alarm = *it.second;
  ExtensionId extension_id_copy(it.first->first);
  delegate_->OnAlarm(extension_id_copy, alarm);

  // Update our scheduled time for the next alarm.
  if (alarm.js_alarm->period_in_minutes) {
    // Get the timer's delay in JS time (i.e., convert it from minutes to
    // milliseconds).
    double period_in_js_time = *alarm.js_alarm->period_in_minutes *
                               base::Time::kMicrosecondsPerMinute /
                               base::Time::kMicrosecondsPerMillisecond;
    // Find out how many periods have transpired since the alarm last went off
    // (it's possible that we missed some).
    int transpired_periods = (clock_->Now().InMillisecondsFSinceUnixEpoch() -
                              alarm.js_alarm->scheduled_time) /
                             period_in_js_time;
    // Schedule the alarm for the next period that is in-line with the original
    // scheduling.
    alarm.js_alarm->scheduled_time +=
        period_in_js_time * (transpired_periods + 1);
  } else {
    RemoveAlarmIterator(it);
  }
  WriteToStorage(extension_id_copy);
}

void AlarmManager::AddAlarmImpl(const ExtensionId& extension_id, Alarm alarm) {
  // Override any old alarm with the same name.
  AlarmIterator old_alarm =
      GetAlarmIterator(extension_id, alarm.js_alarm->name);
  if (old_alarm.first != alarms_.end()) {
    RemoveAlarmIterator(old_alarm);
  }

  base::Time alarm_time = base::Time::FromMillisecondsSinceUnixEpoch(
      alarm.js_alarm->scheduled_time);
  alarms_[extension_id].emplace_back(std::move(alarm));
  if (next_poll_time_.is_null() || alarm_time < next_poll_time_) {
    SetNextPollTime(alarm_time);
  }
}

void AlarmManager::WriteToStorage(const ExtensionId& extension_id) {
  StateStore* storage = ExtensionSystem::Get(browser_context_)->state_store();
  if (!storage) {
    return;
  }

  auto list = alarms_.find(extension_id);
  base::Value alarms =
      base::Value(list != alarms_.end() ? PersistentAlarmsToValue(list->second)
                                        : PersistentAlarmsToValue(AlarmList()));
  storage->SetExtensionValue(extension_id, kRegisteredAlarms,
                             std::move(alarms));
}

void AlarmManager::ReadFromStorage(const ExtensionId& extension_id,
                                   base::TimeDelta min_delay,
                                   std::optional<base::Value> value) {
  if (value && value->is_list()) {
    AlarmList alarm_states = AlarmsFromValue(min_delay, value->GetList());
    for (auto& alarm : alarm_states) {
      // We should never read a non-persistent alarm from storage.
      CHECK(alarm.js_alarm->persist_across_sessions);
      AddAlarmImpl(extension_id, std::move(alarm));
    }
  }

  ReadyQueue& extension_ready_queue = ready_actions_[extension_id];
  while (!extension_ready_queue.empty()) {
    std::move(extension_ready_queue.front()).Run(extension_id);
    extension_ready_queue.pop();
  }
  ready_actions_.erase(extension_id);
}

void AlarmManager::SetNextPollTime(const base::Time& time) {
  next_poll_time_ = time;
  timer_.Start(FROM_HERE, time, this, &AlarmManager::PollAlarms);
}

void AlarmManager::ScheduleNextPoll() {
  // If there are no alarms, stop the timer.
  if (alarms_.empty()) {
    timer_.Stop();
    next_poll_time_ = base::Time();
    return;
  }

  // Find the soonest that any alarm is scheduled to run (or at most
  // kDefaultMinPollPeriod from now).
  // alarms_ guarantees that none of its contained lists are empty.
  base::Time soonest_alarm_time = clock_->Now() + kDefaultMinPollPeriod();
  for (const auto& [extension_id, alarm_list] : alarms_) {
    base::Time* last_poll_time =
        base::FindOrNull(last_poll_times_, extension_id);

    for (const auto& alarm : alarm_list) {
      base::Time cur_alarm_time = base::Time::FromMillisecondsSinceUnixEpoch(
          alarm.js_alarm->scheduled_time);
      if (last_poll_time) {
        cur_alarm_time = std::max(cur_alarm_time,
                                  *last_poll_time + alarm.minimum_granularity);
      }
      if (cur_alarm_time < soonest_alarm_time) {
        soonest_alarm_time = cur_alarm_time;
      }
    }
  }

  // Schedule the poll.
  SetNextPollTime(soonest_alarm_time);
}

void AlarmManager::PollAlarms() {
  base::Time now = clock_->Now();

  // Run any alarms scheduled in the past. OnAlarm uses vector::erase to remove
  // elements from the AlarmList, and map::erase to remove AlarmLists from the
  // AlarmMap.
  for (auto m_it = alarms_.begin(), m_end = alarms_.end(); m_it != m_end;) {
    auto cur_extension = m_it++;

    CHECK(!cur_extension->second.empty());

    // Work out the last time this extension fired an alarm.
    base::Time* last_poll_time =
        base::FindOrNull(last_poll_times_, cur_extension->first);

    // Minimum granularity is the same for all alarms in the extension.
    auto min_granularity = cur_extension->second.front().minimum_granularity;

    // The extension should not poll more frequently than the minimum
    // granularity.
    if (last_poll_time && *last_poll_time + min_granularity > now) {
      continue;
    }

    // Iterate (a) backwards so that removing elements doesn't affect
    // upcoming iterations, and (b) with indices so that if the last
    // iteration destroys the AlarmList, I'm not about to use the end
    // iterator that the destruction invalidates.
    for (size_t i = cur_extension->second.size(); i > 0; --i) {
      auto cur_alarm = cur_extension->second.begin() + i - 1;
      base::Time cur_alarm_time = base::Time::FromMillisecondsSinceUnixEpoch(
          cur_alarm->js_alarm->scheduled_time);

      if (cur_alarm_time <= now) {
        last_poll_times_[cur_extension->first] = now;
        OnAlarm(make_pair(cur_extension, cur_alarm));
      }
    }
  }

  ScheduleNextPoll();
}

static void RemoveAllOnUninstallCallback() {
}

void AlarmManager::RunWhenReady(const ExtensionId& extension_id,
                                ReadyAction action) {
  auto it = ready_actions_.find(extension_id);

  if (it == ready_actions_.end()) {
    std::move(action).Run(extension_id);
  } else {
    it->second.push(std::move(action));
  }
}

void AlarmManager::OnExtensionLoaded(content::BrowserContext* browser_context,
                                     const Extension* extension) {
  StateStore* storage = ExtensionSystem::Get(browser_context_)->state_store();
  if (storage) {
    bool is_unpacked = Manifest::IsUnpackedLocation(extension->location());
    ready_actions_.insert(ReadyMap::value_type(extension->id(), ReadyQueue()));
    base::TimeDelta min_delay = alarms_api_constants::GetMinimumDelay(
        is_unpacked, extension->manifest_version());
    storage->GetExtensionValue(extension->id(), kRegisteredAlarms,
                               base::BindOnce(&AlarmManager::ReadFromStorage,
                                              weak_ptr_factory_.GetWeakPtr(),
                                              extension->id(), min_delay));
  }
}

void AlarmManager::OnExtensionUnloaded(content::BrowserContext* browser_context,
                                       const Extension* extension,
                                       UnloadedExtensionReason reason) {
  last_poll_times_.erase(extension->id());
  RemoveAllAlarmsInternal(extension->id());
}

void AlarmManager::OnExtensionUninstalled(
    content::BrowserContext* browser_context,
    const Extension* extension,
    extensions::UninstallReason reason) {
  RemoveAllAlarms(extension->id(),
                  base::BindOnce(RemoveAllOnUninstallCallback));
}

// AlarmManager::Alarm

Alarm::Alarm() : js_alarm(std::in_place) {}

Alarm::Alarm(const alarms::AlarmCreateInfo& create_info,
             base::TimeDelta min_granularity,
             base::Time now)
    : js_alarm(std::in_place) {
  js_alarm->name = *create_info.name;
  minimum_granularity = min_granularity;

  if (create_info.when) {
    // Absolute scheduling.
    js_alarm->scheduled_time = *create_info.when;
    granularity =
        base::Time::FromMillisecondsSinceUnixEpoch(js_alarm->scheduled_time) -
        now;
  } else {
    // Relative scheduling.
    CHECK(create_info.delay_in_minutes || create_info.period_in_minutes)
        << "ValidateAlarmCreateInfo in alarms_api.cc should have "
        << "validated \"create_info\".";
    const double delay_in_minutes = create_info.delay_in_minutes
                                        ? *create_info.delay_in_minutes
                                        : *create_info.period_in_minutes;
    base::TimeDelta delay = TimeDeltaFromDelay(delay_in_minutes);
    js_alarm->scheduled_time = (now + delay).InMillisecondsFSinceUnixEpoch();
    granularity = delay;
  }

  if (granularity < min_granularity) {
    granularity = min_granularity;
  }

  // Check for repetition.
  js_alarm->period_in_minutes = create_info.period_in_minutes;

  // The W3C WebExtensions Community Group decided that the default value is up
  // to the browser (https://github.com/w3c/webextensions/issues/406). In
  // Chrome, this defaults to true to match historical behavior.
  js_alarm->persist_across_sessions =
      create_info.persist_across_sessions.value_or(true);
}

Alarm::~Alarm() = default;

Alarm::Alarm(Alarm&&) noexcept = default;
Alarm& Alarm::operator=(Alarm&&) noexcept = default;

}  // namespace extensions