Rewrite the track queue to work directly with database iterators

8 files changed, 392 insertions, 316 deletions

diff --git a/src/app_console/app_console.cpp b/src/app_console/app_console.cpp
index 4a57853c..7f576a01 100644
--- a/src/app_console/app_console.cpp
+++ b/src/app_console/app_console.cpp
@@ -123,7 +123,8 @@ int CmdPlayFile(int argc, char** argv) {
 
   if (is_id) {
     database::TrackId id = std::atoi(argv[1]);
-    AppConsole::sServices->track_queue().AddLast(id);
+    auto editor = AppConsole::sServices->track_queue().Edit();
+    AppConsole::sServices->track_queue().Append(editor, id);
   } else {
     std::pmr::string path{&memory::kSpiRamResource};
     path += '/';
@@ -214,89 +215,6 @@ void RegisterDbTracks() {
   esp_console_cmd_register(&cmd);
 }
 
-int CmdDbIndex(int argc, char** argv) {
-  std::cout << std::endl;
-  vTaskDelay(1);
-  static const std::pmr::string usage = "usage: db_index [id] [choices ...]";
-
-  auto db = AppConsole::sServices->database().lock();
-  if (!db) {
-    std::cout << "no database open" << std::endl;
-    return 1;
-  }
-
-  auto indexes = db->GetIndexes();
-  if (argc <= 1) {
-    std::cout << usage << std::endl;
-    std::cout << "available indexes:" << std::endl;
-    std::cout << "id\tname" << std::endl;
-    for (const database::IndexInfo& info : indexes) {
-      std::cout << static_cast<int>(info.id) << '\t' << info.name << std::endl;
-    }
-    return 0;
-  }
-
-  int index_id = std::atoi(argv[1]);
-  auto index = std::find_if(indexes.begin(), indexes.end(),
-                            [=](const auto& i) { return i.id == index_id; });
-  if (index == indexes.end()) {
-    std::cout << "bad index id" << std::endl;
-    return -1;
-  }
-
-  std::shared_ptr<database::Result<database::IndexRecord>> res(
-      db->GetTracksByIndex(index->id, 20).get());
-  int choice_index = 2;
-
-  if (res->values().empty()) {
-    std::cout << "no entries for this index" << std::endl;
-    return 1;
-  }
-
-  while (choice_index < argc) {
-    int choice = std::atoi(argv[choice_index]);
-    if (choice >= res->values().size()) {
-      std::cout << "choice out of range" << std::endl;
-      return -1;
-    }
-    if (res->values().at(choice)->track()) {
-      AppConsole::sServices->track_queue().IncludeLast(
-          std::make_shared<playlist::IndexRecordSource>(
-              AppConsole::sServices->database(), res, 0, res, choice));
-    }
-    auto cont = res->values().at(choice)->Expand(20);
-    if (!cont) {
-      std::cout << "more choices than levels" << std::endl;
-      return 0;
-    }
-    res.reset(db->GetPage<database::IndexRecord>(&*cont).get());
-    choice_index++;
-  }
-
-  for (const auto& r : res->values()) {
-    std::cout << r->text().value_or("<unknown>");
-    if (r->track()) {
-      std::cout << "\t(id:" << *r->track() << ")";
-    }
-    std::cout << std::endl;
-  }
-
-  if (res->next_page()) {
-    std::cout << "(more results not shown)" << std::endl;
-  }
-
-  return 0;
-}
-
-void RegisterDbIndex() {
-  esp_console_cmd_t cmd{.command = "db_index",
-                        .help = "queries the database by index",
-                        .hint = NULL,
-                        .func = &CmdDbIndex,
-                        .argtable = NULL};
-  esp_console_cmd_register(&cmd);
-}
-
 int CmdDbDump(int argc, char** argv) {
   static const std::pmr::string usage = "usage: db_dump";
   if (argc != 1) {
@@ -726,7 +644,6 @@ auto AppConsole::RegisterExtraComponents() -> void {
   */
   RegisterDbInit();
   RegisterDbTracks();
-  RegisterDbIndex();
   RegisterDbDump();
   RegisterTasks();
 
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
diff --git a/src/database/database.cpp b/src/database/database.cpp
index 76d3a2ab..03451c05 100644
--- a/src/database/database.cpp
+++ b/src/database/database.cpp
@@ -756,6 +756,18 @@ auto Database::dbGetPage(const Continuation& c) -> Result<T>* {
   return new Result<T>(std::move(records), next_page, prev_page);
 }
 
+auto Database::dbCount(const Continuation& c) -> size_t {
+  std::unique_ptr<leveldb::Iterator> it{
+      db_->NewIterator(leveldb::ReadOptions{})};
+  size_t count = 0;
+  for (it->Seek({c.start_key.data(), c.start_key.size()});
+       it->Valid() && it->key().starts_with({c.prefix.data(), c.prefix.size()});
+       it->Next()) {
+    count++;
+  }
+  return count;
+}
+
 template auto Database::dbGetPage<Track>(const Continuation& c)
     -> Result<Track>*;
 template auto Database::dbGetPage<std::pmr::string>(const Continuation& c)
@@ -880,6 +892,12 @@ Iterator::Iterator(const Iterator& other)
       current_pos_(other.current_pos_),
       prev_pos_(other.prev_pos_) {}
 
+Iterator& Iterator::operator=(const Iterator& other) {
+  current_pos_ = other.current_pos_;
+  prev_pos_ = other.prev_pos_;
+  return *this;
+}
+
 auto Iterator::Next(Callback cb) -> void {
   auto db = db_.lock();
   if (!db) {
@@ -910,24 +928,35 @@ auto Iterator::NextSync() -> std::optional<IndexRecord> {
   if (!db) {
     return {};
   }
-  return db->worker_task_
-      ->Dispatch<std::optional<IndexRecord>>(
-          [=]() -> std::optional<IndexRecord> {
-            std::lock_guard lock{pos_mutex_};
-            if (!current_pos_) {
-              return {};
-            }
-            std::unique_ptr<Result<IndexRecord>> res{
-                db->dbGetPage<IndexRecord>(*current_pos_)};
-            prev_pos_ = current_pos_;
-            current_pos_ = res->next_page();
-            if (!res || res->values().empty() || !res->values()[0]) {
-              ESP_LOGI(kTag, "dropping empty result");
-              return {};
-            }
-            return *res->values()[0];
-          })
-      .get();
+  std::lock_guard lock{pos_mutex_};
+  if (!current_pos_) {
+    return {};
+  }
+  std::unique_ptr<Result<IndexRecord>> res{
+      db->dbGetPage<IndexRecord>(*current_pos_)};
+  prev_pos_ = current_pos_;
+  current_pos_ = res->next_page();
+  if (!res || res->values().empty() || !res->values()[0]) {
+    ESP_LOGI(kTag, "dropping empty result");
+    return {};
+  }
+  return *res->values()[0];
+}
+
+auto Iterator::PeekSync() -> std::optional<IndexRecord> {
+  auto db = db_.lock();
+  if (!db) {
+    return {};
+  }
+  auto pos = current_pos_;
+  if (!pos) {
+    return {};
+  }
+  std::unique_ptr<Result<IndexRecord>> res{db->dbGetPage<IndexRecord>(*pos)};
+  if (!res || res->values().empty() || !res->values()[0]) {
+    return {};
+  }
+  return *res->values()[0];
 }
 
 auto Iterator::Prev(Callback cb) -> void {
@@ -950,8 +979,82 @@ auto Iterator::Prev(Callback cb) -> void {
   });
 }
 
+auto Iterator::Size() const -> size_t {
+  auto db = db_.lock();
+  if (!db) {
+    return {};
+  }
+  std::optional<Continuation> pos = current_pos_;
+  if (!pos) {
+    return 0;
+  }
+  return db->dbCount(*pos);
+}
+
 auto Iterator::InvokeNull(Callback cb) -> void {
   std::invoke(cb, std::optional<IndexRecord>{});
 }
 
+TrackIterator::TrackIterator(const Iterator& it) : db_(it.db_), levels_() {
+  if (it.current_pos_) {
+    levels_.push_back(it);
+  }
+  NextLeaf();
+}
+
+TrackIterator::TrackIterator(const TrackIterator& other)
+    : db_(other.db_), levels_(other.levels_) {}
+
+TrackIterator& TrackIterator::operator=(TrackIterator&& other) {
+  levels_ = std::move(other.levels_);
+  return *this;
+}
+
+auto TrackIterator::Next() -> std::optional<TrackId> {
+  std::optional<TrackId> next{};
+  while (!next && !levels_.empty()) {
+    auto next_record = levels_.back().NextSync();
+    if (!next_record) {
+      levels_.pop_back();
+      NextLeaf();
+      continue;
+    }
+    // May still be nullopt_t; hence the loop.
+    next = next_record->track();
+  }
+  return next;
+}
+
+auto TrackIterator::Size() const -> size_t {
+  size_t size = 0;
+  TrackIterator copy{*this};
+  while (!copy.levels_.empty()) {
+    size += copy.levels_.back().Size();
+    copy.levels_.pop_back();
+    copy.NextLeaf();
+  }
+  return size;
+}
+
+auto TrackIterator::NextLeaf() -> void {
+  while (!levels_.empty()) {
+    ESP_LOGI(kTag, "check next candidate");
+    Iterator& candidate = levels_.back();
+    auto next = candidate.PeekSync();
+    if (!next) {
+      ESP_LOGI(kTag, "candidate is empty");
+      levels_.pop_back();
+      continue;
+    }
+    if (!next->track()) {
+      ESP_LOGI(kTag, "candidate is a branch");
+      candidate.NextSync();
+      levels_.push_back(Iterator{db_, next->Expand(1).value()});
+      continue;
+    }
+    ESP_LOGI(kTag, "candidate is a leaf");
+    break;
+  }
+}
+
 }  // namespace database
diff --git a/src/database/include/database.hpp b/src/database/include/database.hpp
index 36f734b8..263153fb 100644
--- a/src/database/include/database.hpp
+++ b/src/database/include/database.hpp
@@ -12,6 +12,7 @@
 #include <future>
 #include <memory>
 #include <optional>
+#include <stack>
 #include <string>
 #include <utility>
 #include <vector>
@@ -168,6 +169,8 @@ class Database {
   template <typename T>
   auto dbGetPage(const Continuation& c) -> Result<T>*;
 
+  auto dbCount(const Continuation& c) -> size_t;
+
   template <typename T>
   auto ParseRecord(const leveldb::Slice& key, const leveldb::Slice& val)
       -> std::shared_ptr<T>;
@@ -193,7 +196,9 @@ class Iterator {
  public:
   Iterator(std::weak_ptr<Database>, const IndexInfo&);
   Iterator(std::weak_ptr<Database>, const Continuation&);
-  Iterator(const Iterator &);
+  Iterator(const Iterator&);
+
+  Iterator& operator=(const Iterator& other);
 
   auto database() const { return db_; }
 
@@ -204,8 +209,13 @@ class Iterator {
 
   auto Prev(Callback) -> void;
 
+  auto PeekSync() -> std::optional<IndexRecord>;
+
+  auto Size() const -> size_t;
 
  private:
+  friend class TrackIterator;
+
   auto InvokeNull(Callback) -> void;
 
   std::weak_ptr<Database> db_;
@@ -215,4 +225,21 @@ class Iterator {
   std::optional<Continuation> prev_pos_;
 };
 
+class TrackIterator {
+ public:
+  TrackIterator(const Iterator&);
+  TrackIterator(const TrackIterator&);
+
+  TrackIterator& operator=(TrackIterator&& other);
+
+  auto Next() -> std::optional<TrackId>;
+  auto Size() const -> size_t;
+
+ private:
+  auto NextLeaf() -> void;
+
+  std::weak_ptr<Database> db_;
+  std::vector<Iterator> levels_;
+};
+
 }  // namespace database
diff --git a/src/lua/lua_queue.cpp b/src/lua/lua_queue.cpp
index 929a7159..fadcb51c 100644
--- a/src/lua/lua_queue.cpp
+++ b/src/lua/lua_queue.cpp
@@ -22,6 +22,8 @@
 #include "property.hpp"
 #include "service_locator.hpp"
 #include "source.hpp"
+#include "track.hpp"
+#include "track_queue.hpp"
 #include "ui_events.hpp"
 
 namespace lua {
@@ -32,11 +34,19 @@ static auto queue_add(lua_State* state) -> int {
   Bridge* instance = Bridge::Get(state);
 
   if (lua_isinteger(state, 1)) {
-    instance->services().track_queue().AddLast(luaL_checkinteger(state, 1));
+    database::TrackId id = luaL_checkinteger(state, 1);
+    instance->services().bg_worker().Dispatch<void>([=]() {
+      audio::TrackQueue& queue = instance->services().track_queue();
+      auto editor = queue.Edit();
+      queue.Append(editor, id);
+    });
   } else {
-    database::Iterator* it = db_check_iterator(state, 1);
-    instance->services().track_queue().IncludeLast(
-        std::make_shared<playlist::IteratorSource>(*it));
+    database::Iterator it = *db_check_iterator(state, 1);
+    instance->services().bg_worker().Dispatch<void>([=]() {
+      audio::TrackQueue& queue = instance->services().track_queue();
+      auto editor = queue.Edit();
+      queue.Append(editor, database::TrackIterator{it});
+    });
   }
 
   return 0;
@@ -44,7 +54,9 @@ static auto queue_add(lua_State* state) -> int {
 
 static auto queue_clear(lua_State* state) -> int {
   Bridge* instance = Bridge::Get(state);
-  instance->services().track_queue().Clear();
+  audio::TrackQueue& queue = instance->services().track_queue();
+  auto editor = queue.Edit();
+  queue.Clear(editor);
   return 0;
 }
 
diff --git a/src/ui/ui_fsm.cpp b/src/ui/ui_fsm.cpp
index 539cbc9b..3c57f573 100644
--- a/src/ui/ui_fsm.cpp
+++ b/src/ui/ui_fsm.cpp
@@ -118,9 +118,7 @@ void UiState::react(const audio::PlaybackUpdate& ev) {}
 
 void UiState::react(const audio::QueueUpdate&) {
   auto& queue = sServices->track_queue();
-  bool had_queue = sPlaybackModel.current_track.get().has_value();
-  sPlaybackModel.current_track.set(queue.GetCurrent());
-  sPlaybackModel.upcoming_tracks.set(queue.GetUpcoming(10));
+  sPlaybackModel.current_track.set(queue.Current());
 }
 
 void UiState::react(const internal::ControlSchemeChanged&) {
@@ -283,9 +281,15 @@ void Lua::react(const system_fsm::BatteryStateChanged& ev) {
 }
 
 void Lua::react(const audio::QueueUpdate&) {
-  auto& queue = sServices->track_queue();
-  queue_size_->Update(static_cast<int>(queue.Size()));
-  queue_position_->Update(static_cast<int>(queue.Position()));
+  sServices->bg_worker().Dispatch<void>([=]() {
+    auto& queue = sServices->track_queue();
+    size_t total_size = queue.GetTotalSize();
+    size_t current_pos = queue.GetCurrentPosition();
+    events::Ui().RunOnTask([=]() {
+      queue_size_->Update(static_cast<int>(total_size));
+      queue_position_->Update(static_cast<int>(current_pos));
+    });
+  });
 }
 
 void Lua::react(const audio::PlaybackStarted& ev) {