add indexing to the database

idk man i wrote most of this in a fugue state whilst high on the couch
with my cat

4 files changed, 147 insertions, 20 deletions

diff --git a/src/database/include/database.hpp b/src/database/include/database.hpp
index 8fecc5f6..77a17b75 100644
--- a/src/database/include/database.hpp
+++ b/src/database/include/database.hpp
@@ -16,6 +16,7 @@
 #include <vector>
 
 #include "file_gatherer.hpp"
+#include "index.hpp"
 #include "leveldb/cache.h"
 #include "leveldb/db.h"
 #include "leveldb/iterator.h"
@@ -23,6 +24,7 @@
 #include "leveldb/slice.h"
 #include "records.hpp"
 #include "result.hpp"
+#include "shared_string.h"
 #include "tag_parser.hpp"
 #include "tasks.hpp"
 #include "track.hpp"
@@ -66,6 +68,20 @@ class Result {
   std::optional<Continuation<T>> prev_page_;
 };
 
+class IndexRecord {
+ public:
+  explicit IndexRecord(const IndexKey&, std::optional<Track>);
+
+  auto text() const -> std::optional<shared_string>;
+  auto track() const -> std::optional<Track>;
+
+  auto Expand(std::size_t) const -> std::optional<Continuation<IndexRecord>>;
+
+ private:
+  IndexKey key_;
+  std::optional<Track> track_;
+};
+
 class Database {
  public:
   enum DatabaseError {
@@ -84,6 +100,9 @@ class Database {
 
   auto GetTrackPath(TrackId id) -> std::future<std::optional<std::string>>;
 
+  auto GetIndexes() -> std::vector<IndexInfo>;
+  auto GetTracksByIndex(const IndexInfo& index, std::size_t page_size)
+      -> std::future<Result<IndexRecord>*>;
   auto GetTracks(std::size_t page_size) -> std::future<Result<Track>*>;
   auto GetDump(std::size_t page_size) -> std::future<Result<std::string>*>;
 
@@ -118,8 +137,7 @@ class Database {
   auto dbGetTrackData(TrackId id) -> std::optional<TrackData>;
   auto dbPutHash(const uint64_t& hash, TrackId i) -> void;
   auto dbGetHash(const uint64_t& hash) -> std::optional<TrackId>;
-  auto dbPutTrack(TrackId id, const std::string& path, const uint64_t& hash)
-      -> void;
+  auto dbCreateIndexesForTrack(Track track) -> void;
 
   template <typename T>
   auto dbGetPage(const Continuation<T>& c) -> Result<T>*;
@@ -130,6 +148,10 @@ class Database {
 };
 
 template <>
+auto Database::ParseRecord<IndexRecord>(const leveldb::Slice& key,
+                                        const leveldb::Slice& val)
+    -> std::optional<IndexRecord>;
+template <>
 auto Database::ParseRecord<Track>(const leveldb::Slice& key,
                                   const leveldb::Slice& val)
     -> std::optional<Track>;
diff --git a/src/database/include/index.hpp b/src/database/include/index.hpp
new file mode 100644
index 00000000..17229164
--- /dev/null
+++ b/src/database/include/index.hpp
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <stdint.h>
+
+#include <cstdint>
+#include <string>
+#include <variant>
+#include <vector>
+
+#include "leveldb/db.h"
+#include "leveldb/slice.h"
+
+#include "leveldb/write_batch.h"
+#include "shared_string.h"
+#include "track.hpp"
+
+namespace database {
+
+typedef uint8_t IndexId;
+
+struct IndexInfo {
+  // Unique id for this index
+  IndexId id;
+  // Localised, user-friendly description of this index. e.g. "Albums by Artist"
+  // or "All Tracks".
+  std::string name;
+  // Specifier for how this index breaks down the database.
+  std::vector<Tag> components;
+};
+
+struct IndexKey {
+  struct Header {
+    // The index that this key was created for.
+    IndexId id;
+    // The number of components of IndexInfo that have already been filtered.
+    // For example, if an index consists of { kGenre, kArtist }, and this key
+    // represents an artist, then depth = 1.
+    std::uint8_t depth;
+    // The cumulative hash of all filtered components, in order. For example, if
+    // an index consists of { kArtist, kAlbum, kTitle }, and we are at depth = 2
+    // then this may contain hash(hash("Jacqueline"), "My Cool Album").
+    std::uint64_t components_hash;
+  };
+  Header header;
+
+  // The filterable / selectable item that this key represents. "Jacqueline" for
+  // kArtist, "My Cool Album" for kAlbum, etc.
+  std::optional<std::string> item;
+  // If this is a leaf component, the track id for this record.
+  // This could reasonably be the value for a record, but we keep it as a part
+  // of the key to help with disambiguation.
+  std::optional<TrackId> track;
+};
+
+auto Index(const IndexInfo&, const Track&, leveldb::WriteBatch*) -> bool;
+auto ExpandHeader(const IndexKey::Header&, const std::optional<std::string>&)
+    -> IndexKey::Header;
+
+// Predefined indexes
+// TODO(jacqueline): Make these defined at runtime! :)
+
+extern const IndexInfo kAlbumsByArtist;
+extern const IndexInfo kTracksByGenre;
+extern const IndexInfo kAllTracks;
+
+}  // namespace database
diff --git a/src/database/include/records.hpp b/src/database/include/records.hpp
index 95a1a1e8..58f29b20 100644
--- a/src/database/include/records.hpp
+++ b/src/database/include/records.hpp
@@ -9,10 +9,14 @@
 #include <stdint.h>
 
 #include <string>
+#include <variant>
+#include <vector>
 
 #include "leveldb/db.h"
 #include "leveldb/slice.h"
 
+#include "index.hpp"
+#include "shared_string.h"
 #include "track.hpp"
 
 namespace database {
@@ -34,39 +38,49 @@ class OwningSlice {
  * Returns the prefix added to every TrackData key. This can be used to iterate
  * over every data record in the database.
  */
-auto CreateDataPrefix() -> OwningSlice;
+auto EncodeDataPrefix() -> OwningSlice;
 
-/* Creates a data key for a track with the specified id. */
-auto CreateDataKey(const TrackId& id) -> OwningSlice;
+/* Encodes a data key for a track with the specified id. */
+auto EncodeDataKey(const TrackId& id) -> OwningSlice;
 
 /*
  * Encodes a TrackData instance into bytes, in preparation for storing it within
  * the database. This encoding is consistent, and will remain stable over time.
  */
-auto CreateDataValue(const TrackData& track) -> OwningSlice;
+auto EncodeDataValue(const TrackData& track) -> OwningSlice;
 
 /*
- * Parses bytes previously encoded via CreateDataValue back into a TrackData.
+ * Parses bytes previously encoded via EncodeDataValue back into a TrackData.
  * May return nullopt if parsing fails.
  */
 auto ParseDataValue(const leveldb::Slice& slice) -> std::optional<TrackData>;
 
-/* Creates a hash key for the specified hash. */
-auto CreateHashKey(const uint64_t& hash) -> OwningSlice;
+/* Encodes a hash key for the specified hash. */
+auto EncodeHashKey(const uint64_t& hash) -> OwningSlice;
 
 /*
  * Encodes a hash value (at this point just a track id) into bytes, in
  * preparation for storing within the database. This encoding is consistent, and
  * will remain stable over time.
  */
-auto CreateHashValue(TrackId id) -> OwningSlice;
+auto EncodeHashValue(TrackId id) -> OwningSlice;
 
 /*
- * Parses bytes previously encoded via CreateHashValue back into a track id. May
+ * Parses bytes previously encoded via EncodeHashValue back into a track id. May
  * return nullopt if parsing fails.
  */
 auto ParseHashValue(const leveldb::Slice&) -> std::optional<TrackId>;
 
+/* Encodes a prefix that matches all index keys, of all ids and depths. */
+auto EncodeAllIndexesPrefix() -> OwningSlice;
+
+/*
+ */
+auto EncodeIndexPrefix(const IndexKey::Header&) -> OwningSlice;
+
+auto EncodeIndexKey(const IndexKey&) -> OwningSlice;
+auto ParseIndexKey(const leveldb::Slice&) -> std::optional<IndexKey>;
+
 /* Encodes a TrackId as bytes. */
 auto TrackIdToBytes(TrackId id) -> OwningSlice;
 
diff --git a/src/database/include/track.hpp b/src/database/include/track.hpp
index 5a0c0ca8..e3f94db4 100644
--- a/src/database/include/track.hpp
+++ b/src/database/include/track.hpp
@@ -8,11 +8,14 @@
 
 #include <stdint.h>
 
+#include <map>
+#include <memory>
 #include <optional>
 #include <string>
 #include <utility>
 
 #include "leveldb/db.h"
+#include "shared_string.h"
 #include "span.hpp"
 
 namespace database {
@@ -41,25 +44,33 @@ enum class Encoding {
   kFlac = 4,
 };
 
+enum class Tag {
+  kTitle = 0,
+  kArtist = 1,
+  kAlbum = 2,
+  kAlbumTrack = 3,
+  kGenre = 4,
+};
+
 /*
  * Owning container for tag-related track metadata that was extracted from a
  * file.
  */
-struct TrackTags {
-  Encoding encoding;
-  std::optional<std::string> title;
-
-  // TODO(jacqueline): It would be nice to use shared_ptr's for the artist and
-  // album, since there's likely a fair number of duplicates for each
-  // (especially the former).
+class TrackTags {
+ public:
+  auto encoding() const -> Encoding { return encoding_; };
+  auto encoding(Encoding e) -> void { encoding_ = e; };
 
-  std::optional<std::string> artist;
-  std::optional<std::string> album;
+  TrackTags() : encoding_(Encoding::kUnsupported) {}
 
   std::optional<int> channels;
   std::optional<int> sample_rate;
   std::optional<int> bits_per_sample;
 
+  auto set(const Tag& key, const std::string& val) -> void;
+  auto at(const Tag& key) const -> std::optional<shared_string>;
+  auto operator[](const Tag& key) const -> std::optional<shared_string>;
+
   /*
    * Returns a hash of the 'identifying' tags of this track. That is, a hash
    * that can be used to determine if one track is likely the same as another,
@@ -69,6 +80,12 @@ struct TrackTags {
   auto Hash() const -> uint64_t;
 
   bool operator==(const TrackTags&) const = default;
+  TrackTags& operator=(const TrackTags&) = default;
+  TrackTags(const TrackTags&) = default;
+
+ private:
+  Encoding encoding_;
+  std::map<Tag, shared_string> tags_;
 };
 
 /*
@@ -156,6 +173,8 @@ class Track {
   auto data() const -> const TrackData& { return data_; }
   auto tags() const -> const TrackTags& { return tags_; }
 
+  auto TitleOrFilename() const -> shared_string;
+
   bool operator==(const Track&) const = default;
   Track operator=(const Track& other) const { return Track(other); }