Rewrite the track queue to work directly with database iterators

3 files changed, 214 insertions, 201 deletions

diff --git a/src/audio/audio_fsm.cpp b/src/audio/audio_fsm.cpp
index e33a2cab..ce610abb 100644
--- a/src/audio/audio_fsm.cpp
+++ b/src/audio/audio_fsm.cpp
@@ -143,7 +143,7 @@ void Standby::react(const internal::InputFileOpened& ev) {
 }
 
 void Standby::react(const QueueUpdate& ev) {
-  auto current_track = sServices->track_queue().GetCurrent();
+  auto current_track = sServices->track_queue().Current();
   if (!current_track || (sCurrentTrack && *sCurrentTrack == *current_track)) {
     return;
   }
@@ -187,7 +187,7 @@ void Playback::react(const QueueUpdate& ev) {
   if (!ev.current_changed) {
     return;
   }
-  auto current_track = sServices->track_queue().GetCurrent();
+  auto current_track = sServices->track_queue().Current();
   if (!current_track) {
     sFileSource->SetPath();
     sCurrentTrack.reset();
@@ -220,8 +220,9 @@ void Playback::react(const internal::InputFileClosed& ev) {}
 
 void Playback::react(const internal::InputFileFinished& ev) {
   ESP_LOGI(kTag, "finished playing file");
-  sServices->track_queue().Next();
-  if (!sServices->track_queue().GetCurrent()) {
+  auto editor = sServices->track_queue().Edit();
+  sServices->track_queue().Next(editor);
+  if (!sServices->track_queue().Current()) {
     transit<Standby>();
   }
 }
diff --git a/src/audio/include/track_queue.hpp b/src/audio/include/track_queue.hpp
index 0be2384a..9d5ef5b2 100644
--- a/src/audio/include/track_queue.hpp
+++ b/src/audio/include/track_queue.hpp
@@ -11,6 +11,7 @@
 #include <mutex>
 #include <vector>
 
+#include "database.hpp"
 #include "source.hpp"
 #include "track.hpp"
 
@@ -27,67 +28,78 @@ namespace audio {
  *
  * Instances of this class are broadly safe to use from multiple tasks; each
  * method represents an atomic operation. No guarantees are made about
- * consistency between calls however. For example, there may be data changes
- * between consecutive calls to AddNext() and GetUpcoming();
+ * consistency between calls however.
  */
 class TrackQueue {
  public:
   TrackQueue();
 
+  class Editor {
+   public:
+    ~Editor();
+
+    // Cannot be copied or moved.
+    Editor(const Editor&) = delete;
+    Editor& operator=(const Editor&) = delete;
+
+   private:
+    friend TrackQueue;
+
+    Editor(TrackQueue&);
+
+    std::lock_guard<std::recursive_mutex> lock_;
+    bool has_current_changed_;
+  };
+
+  auto Edit() -> Editor;
+
   /* Returns the currently playing track. */
-  auto GetCurrent() const -> std::optional<database::TrackId>;
+  auto Current() const -> std::optional<database::TrackId>;
+
   /* Returns, in order, tracks that have been queued to be played next. */
-  auto GetUpcoming(std::size_t limit) const -> std::vector<database::TrackId>;
+  auto PeekNext(std::size_t limit) const -> std::vector<database::TrackId>;
 
   /*
-   * Enqueues a track, placing it immediately after the current track and
-   * before anything already queued.
-   *
-   * If there is no current track, the given track will begin playback.
+   * Returns the tracks in the queue that have already been played, ordered
+   * most recently played first.
    */
-  auto AddNext(database::TrackId) -> void;
-  auto AddNext(std::shared_ptr<playlist::ISource>) -> void;
+  auto PeekPrevious(std::size_t limit) const -> std::vector<database::TrackId>;
 
-  auto IncludeNext(std::shared_ptr<playlist::IResetableSource>) -> void;
+  auto GetCurrentPosition() const -> size_t;
+  auto GetTotalSize() const -> size_t;
 
-  /*
-   * Enqueues a track, placing it the end of all enqueued tracks.
-   *
-   * If there is no current track, the given track will begin playback.
-   */
-  auto AddLast(database::TrackId) -> void;
-  auto AddLast(std::shared_ptr<playlist::ISource>) -> void;
-
-  auto IncludeLast(std::shared_ptr<playlist::IResetableSource>) -> void;
+  using Item = std::variant<database::TrackId, database::TrackIterator>;
+  auto Insert(Editor&, Item, size_t) -> void;
+  auto Append(Editor&, Item i) -> void;
 
   /*
    * Advances to the next track in the queue, placing the current track at the
    * front of the 'played' queue.
    */
-  auto Next() -> void;
-  auto Previous() -> void;
+  auto Next(Editor&) -> std::optional<database::TrackId>;
+  auto Previous(Editor&) -> std::optional<database::TrackId>;
+
+  auto SkipTo(Editor&, database::TrackId) -> void;
 
   /*
    * Removes all tracks from all queues, and stops any currently playing track.
    */
-  auto Clear() -> void;
-
-  auto Position() -> size_t;
-  auto Size() -> size_t;
+  auto Clear(Editor&) -> void;
 
+  // Cannot be copied or moved.
   TrackQueue(const TrackQueue&) = delete;
   TrackQueue& operator=(const TrackQueue&) = delete;
 
  private:
-  mutable std::mutex mutex_;
-
-  std::list<std::variant<database::TrackId,
-                         std::shared_ptr<playlist::IResetableSource>>>
-      played_;
-  std::list<std::variant<database::TrackId,
-                         std::shared_ptr<playlist::ISource>,
-                         std::shared_ptr<playlist::IResetableSource>>>
-      enqueued_;
+  // FIXME: Make this a shared_mutex so that multithread reads don't block.
+  mutable std::recursive_mutex mutex_;
+
+  std::optional<database::TrackId> current_;
+
+  // Note: stored in reverse order, i.e. most recent played it at the *back* of
+  // this vector.
+  std::pmr::vector<database::TrackId> played_;
+  std::pmr::vector<Item> enqueued_;
 };
 
 }  // namespace audio
diff --git a/src/audio/track_queue.cpp b/src/audio/track_queue.cpp
index c400e66a..b3a128b2 100644
--- a/src/audio/track_queue.cpp
+++ b/src/audio/track_queue.cpp
@@ -15,6 +15,7 @@
 #include "audio_fsm.hpp"
 #include "database.hpp"
 #include "event_queue.hpp"
+#include "memory_resource.hpp"
 #include "source.hpp"
 #include "track.hpp"
 #include "ui_fsm.hpp"
@@ -23,208 +24,207 @@ namespace audio {
 
 [[maybe_unused]] static constexpr char kTag[] = "tracks";
 
-TrackQueue::TrackQueue() {}
+TrackQueue::Editor::Editor(TrackQueue& queue)
+    : lock_(queue.mutex_), has_current_changed_(false) {}
 
-auto TrackQueue::GetCurrent() const -> std::optional<database::TrackId> {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  if (enqueued_.empty()) {
-    return {};
-  }
-  auto item = enqueued_.front();
-  if (std::holds_alternative<database::TrackId>(item)) {
-    return std::get<database::TrackId>(item);
-  }
-  if (std::holds_alternative<std::shared_ptr<playlist::ISource>>(item)) {
-    return std::get<std::shared_ptr<playlist::ISource>>(item)->Current();
-  }
-  if (std::holds_alternative<std::shared_ptr<playlist::IResetableSource>>(
-          item)) {
-    return std::get<std::shared_ptr<playlist::IResetableSource>>(item)
-        ->Current();
-  }
-  return {};
+TrackQueue::Editor::~Editor() {
+  QueueUpdate ev{.current_changed = has_current_changed_};
+  events::Audio().Dispatch(ev);
+  events::Ui().Dispatch(ev);
 }
 
-auto TrackQueue::GetUpcoming(std::size_t limit) const
-    -> std::vector<database::TrackId> {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  std::vector<database::TrackId> ret;
+TrackQueue::TrackQueue()
+    : mutex_(),
+      current_(),
+      played_(&memory::kSpiRamResource),
+      enqueued_(&memory::kSpiRamResource) {}
 
-  auto it = enqueued_.begin();
-  if (it == enqueued_.end()) {
-    return ret;
-  }
+auto TrackQueue::Edit() -> Editor {
+  return Editor(*this);
+}
 
-  // Don't include the current track. This is only relevant to raw track ids,
-  // since sources include multiple tracks.
-  if (std::holds_alternative<database::TrackId>(*it)) {
-    it++;
-  }
+auto TrackQueue::Current() const -> std::optional<database::TrackId> {
+  const std::lock_guard<std::recursive_mutex> lock(mutex_);
+  return current_;
+}
+
+auto TrackQueue::PeekNext(std::size_t limit) const
+    -> std::vector<database::TrackId> {
+  const std::lock_guard<std::recursive_mutex> lock(mutex_);
+  std::vector<database::TrackId> ret;
 
-  while (limit > 0 && it != enqueued_.end()) {
-    auto item = *it;
-    if (std::holds_alternative<database::TrackId>(item)) {
-      ret.push_back(std::get<database::TrackId>(item));
-      limit--;
-    } else if (std::holds_alternative<std::shared_ptr<playlist::ISource>>(
-                   item)) {
-      limit -=
-          std::get<std::shared_ptr<playlist::ISource>>(item)->Peek(limit, &ret);
-    } else if (std::holds_alternative<
-                   std::shared_ptr<playlist::IResetableSource>>(item)) {
-      limit -=
-          std::get<std::shared_ptr<playlist::IResetableSource>>(item)->Peek(
-              limit, &ret);
-    }
-    it++;
+  for (auto it = enqueued_.begin(); it != enqueued_.end() && limit > 0; it++) {
+    std::visit(
+        [&](auto&& arg) {
+          using T = std::decay_t<decltype(arg)>;
+          if constexpr (std::is_same_v<T, database::TrackId>) {
+            ret.push_back(arg);
+            limit--;
+          } else if constexpr (std::is_same_v<T, database::TrackIterator>) {
+            auto copy = arg;
+            while (limit > 0) {
+              auto next = copy.Next();
+              if (!next) {
+                break;
+              }
+              ret.push_back(*next);
+              limit--;
+            }
+          }
+        },
+        *it);
   }
 
   return ret;
 }
 
-auto TrackQueue::AddNext(database::TrackId t) -> void {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  enqueued_.push_front(t);
-
-  QueueUpdate ev{.current_changed = enqueued_.size() < 2};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
-}
+auto TrackQueue::PeekPrevious(std::size_t limit) const
+    -> std::vector<database::TrackId> {
+  const std::lock_guard<std::recursive_mutex> lock(mutex_);
+  std::vector<database::TrackId> ret;
+  ret.reserve(limit);
 
-auto TrackQueue::AddNext(std::shared_ptr<playlist::ISource> src) -> void {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  enqueued_.push_front(src);
+  for (auto it = played_.rbegin(); it != played_.rend(); it++, limit--) {
+    ret.push_back(*it);
+  }
 
-  QueueUpdate ev{.current_changed = enqueued_.size() < 2};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
+  return ret;
 }
 
-auto TrackQueue::IncludeNext(std::shared_ptr<playlist::IResetableSource> src)
-    -> void {
-  assert(src.get() != nullptr);
-  const std::lock_guard<std::mutex> lock(mutex_);
-  enqueued_.push_front(src);
-
-  QueueUpdate ev{.current_changed = enqueued_.size() < 2};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
+auto TrackQueue::GetCurrentPosition() const -> size_t {
+  const std::lock_guard<std::recursive_mutex> lock(mutex_);
+  size_t played = played_.size();
+  if (current_) {
+    played += 1;
+  }
+  return played;
 }
 
-auto TrackQueue::AddLast(database::TrackId t) -> void {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  enqueued_.push_back(t);
+auto TrackQueue::GetTotalSize() const -> size_t {
+  const std::lock_guard<std::recursive_mutex> lock(mutex_);
+  size_t total = GetCurrentPosition();
+
+  for (const auto& item : enqueued_) {
+    std::visit(
+        [&](auto&& arg) {
+          using T = std::decay_t<decltype(arg)>;
+          if constexpr (std::is_same_v<T, database::TrackId>) {
+            total++;
+          } else if constexpr (std::is_same_v<T, database::TrackIterator>) {
+            total += arg.Size();
+          }
+        },
+        item);
+  }
 
-  QueueUpdate ev{.current_changed = enqueued_.size() < 2};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
+  return total;
 }
 
-auto TrackQueue::AddLast(std::shared_ptr<playlist::ISource> src) -> void {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  enqueued_.push_back(src);
+auto TrackQueue::Insert(Editor& ed, Item i, size_t index) -> void {
+  if (index == 0) {
+    enqueued_.insert(enqueued_.begin(), i);
+  }
 
-  QueueUpdate ev{.current_changed = enqueued_.size() < 2};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
-}
+  // We can't insert halfway through an iterator, so we need to ensure that the
+  // first `index` items in the queue are reified into track ids.
+  size_t current_index = 0;
+  while (current_index < index && current_index < enqueued_.size()) {
+    std::visit(
+        [&](auto&& arg) {
+          using T = std::decay_t<decltype(arg)>;
+          if constexpr (std::is_same_v<T, database::TrackId>) {
+            // This item is already a track id; nothing to do.
+            current_index++;
+          } else if constexpr (std::is_same_v<T, database::TrackIterator>) {
+            // This item is an iterator. Push it back one, replacing its old
+            // index with the next value from it.
+            auto next = arg.Next();
+            auto iterator_index = enqueued_.begin() + current_index;
+            if (!next) {
+              // Out of values. Remove the iterator completely.
+              enqueued_.erase(iterator_index);
+              // Don't increment current_index, since the next item in the
+              // queue will have been moved down.
+            } else {
+              enqueued_.insert(iterator_index, *next);
+              current_index++;
+            }
+          }
+        },
+        enqueued_[current_index]);
+  }
 
-auto TrackQueue::IncludeLast(std::shared_ptr<playlist::IResetableSource> src)
-    -> void {
-  assert(src.get() != nullptr);
-  const std::lock_guard<std::mutex> lock(mutex_);
-  enqueued_.push_back(src);
+  // Double check the previous loop didn't run out of items.
+  if (index > enqueued_.size()) {
+    ESP_LOGE(kTag, "insert index was out of bounds");
+    return;
+  }
 
-  QueueUpdate ev{.current_changed = enqueued_.size() < 2};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
+  // Finally, we can now do the actual insertion.
+  enqueued_.insert(enqueued_.begin() + index, i);
 }
 
-auto TrackQueue::Next() -> void {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  if (enqueued_.empty()) {
-    return;
+auto TrackQueue::Append(Editor& ed, Item i) -> void {
+  enqueued_.push_back(i);
+  if (!current_) {
+    Next(ed);
   }
+}
 
-  auto item = enqueued_.front();
-  if (std::holds_alternative<database::TrackId>(item)) {
-    played_.push_front(std::get<database::TrackId>(item));
-    enqueued_.pop_front();
+auto TrackQueue::Next(Editor& ed) -> std::optional<database::TrackId> {
+  if (current_) {
+    ed.has_current_changed_ = true;
+    played_.push_back(*current_);
   }
-  if (std::holds_alternative<std::shared_ptr<playlist::ISource>>(item)) {
-    auto src = std::get<std::shared_ptr<playlist::ISource>>(item);
-    played_.push_front(*src->Current());
-    if (!src->Advance()) {
-      enqueued_.pop_front();
-    }
-  }
-  if (std::holds_alternative<std::shared_ptr<playlist::IResetableSource>>(
-          item)) {
-    auto src = std::get<std::shared_ptr<playlist::IResetableSource>>(item);
-    if (!src->Advance()) {
-      played_.push_back(src);
-      enqueued_.pop_front();
-    }
+  current_.reset();
+
+  while (!current_ && !enqueued_.empty()) {
+    ed.has_current_changed_ = true;
+    std::visit(
+        [&](auto&& arg) {
+          using T = std::decay_t<decltype(arg)>;
+          if constexpr (std::is_same_v<T, database::TrackId>) {
+            current_ = arg;
+            enqueued_.erase(enqueued_.begin());
+          } else if constexpr (std::is_same_v<T, database::TrackIterator>) {
+            auto next = arg.Next();
+            if (!next) {
+              enqueued_.erase(enqueued_.begin());
+            } else {
+              current_ = *next;
+            }
+          }
+        },
+        enqueued_.front());
   }
 
-  QueueUpdate ev{.current_changed = true};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
+  return current_;
 }
 
-auto TrackQueue::Previous() -> void {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  if (!enqueued_.empty() &&
-      std::holds_alternative<std::shared_ptr<playlist::IResetableSource>>(
-          enqueued_.front())) {
-    auto src = std::get<std::shared_ptr<playlist::IResetableSource>>(
-        enqueued_.front());
-    if (src->Previous()) {
-      QueueUpdate ev{.current_changed = false};
-      events::Audio().Dispatch(ev);
-      events::Ui().Dispatch(ev);
-      return;
-    }
-  }
-
+auto TrackQueue::Previous(Editor& ed) -> std::optional<database::TrackId> {
   if (played_.empty()) {
-    return;
+    return current_;
   }
-
-  auto item = played_.front();
-  if (std::holds_alternative<database::TrackId>(item)) {
-    enqueued_.push_front(std::get<database::TrackId>(item));
-  } else if (std::holds_alternative<
-                 std::shared_ptr<playlist::IResetableSource>>(item)) {
-    enqueued_.push_front(
-        std::get<std::shared_ptr<playlist::IResetableSource>>(item));
+  ed.has_current_changed_ = true;
+  if (current_) {
+    enqueued_.insert(enqueued_.begin(), *current_);
   }
-  played_.pop_front();
-
-  QueueUpdate ev{.current_changed = true};
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
+  current_ = played_.back();
+  played_.pop_back();
+  return current_;
 }
 
-auto TrackQueue::Clear() -> void {
-  const std::lock_guard<std::mutex> lock(mutex_);
-  if (enqueued_.empty() && played_.empty()) {
-    return;
+auto TrackQueue::SkipTo(Editor& ed, database::TrackId id) -> void {
+  while ((!current_ || *current_ != id) && !enqueued_.empty()) {
+    Next(ed);
   }
-  QueueUpdate ev{.current_changed = !enqueued_.empty()};
-  played_.clear();
-  enqueued_.clear();
-
-  events::Audio().Dispatch(ev);
-  events::Ui().Dispatch(ev);
 }
 
-auto TrackQueue::Position() -> size_t {
-  return played_.size() + (enqueued_.empty() ? 0 : 1);
-}
-
-auto TrackQueue::Size() -> size_t {
-  return played_.size() + enqueued_.size();
+auto TrackQueue::Clear(Editor& ed) -> void {
+  ed.has_current_changed_ = current_.has_value();
+  current_.reset();
+  played_.clear();
+  enqueued_.clear();
 }
 
 }  // namespace audio