db binning and sorts

10 files changed, 344 insertions, 154 deletions

diff --git a/database/src/filter/binning.rs b/database/src/filter/binning.rs
new file mode 100644
index 0000000..977d5d7
--- /dev/null
+++ b/database/src/filter/binning.rs
@@ -0,0 +1,52 @@
+/*
+    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+    Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use jellycommon::jellyobject::{Object, path::Path};
+
+/// Sorted list of components to bin objects by filterable values.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub struct Binning(Vec<BinningComponent>);
+
+#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord)]
+pub enum BinningComponent {
+    Has(Path),
+    Match(Path),
+}
+
+impl Binning {
+    pub fn new(mut comps: Vec<BinningComponent>) -> Self {
+        comps.sort();
+        Self(comps)
+    }
+    pub fn apply(&self, ob: Object<'_>, keys: &mut Vec<Vec<u8>>) {
+        for f in &self.0 {
+            f.apply(ob, keys);
+        }
+    }
+}
+impl BinningComponent {
+    pub fn apply(&self, ob: Object<'_>, keys: &mut Vec<Vec<u8>>) {
+        match self {
+            BinningComponent::Has(path) => {
+                let has = path.get_matching_value(ob).is_some();
+                for co in keys {
+                    co.push(has as u8)
+                }
+            }
+            BinningComponent::Match(path) => {
+                let mut new_out = Vec::new();
+                for value in path.get_matching_values(ob) {
+                    for mut co in keys.clone() {
+                        co.extend((co.len() as u32).to_be_bytes());
+                        co.extend(value);
+                        new_out.push(co);
+                    }
+                }
+                *keys = new_out;
+            }
+        }
+    }
+}
diff --git a/database/src/filter/mod.rs b/database/src/filter/mod.rs
new file mode 100644
index 0000000..30a22de
--- /dev/null
+++ b/database/src/filter/mod.rs
@@ -0,0 +1,106 @@
+/*
+    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+    Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+pub mod binning;
+
+use crate::{
+    filter::binning::{Binning, BinningComponent},
+    query::Filter,
+};
+
+impl Filter {
+    pub fn get_bins(&self) -> Vec<Binning> {
+        fn recurse(f: &Filter) -> Vec<Vec<BinningComponent>> {
+            match f {
+                Filter::All(filters) => {
+                    let mut o = vec![vec![]];
+                    for filter in filters {
+                        let mut new_o = Vec::new();
+                        for par in recurse(filter) {
+                            for mut prev in o.clone() {
+                                prev.extend(par.clone());
+                                new_o.push(prev);
+                            }
+                        }
+                        o = new_o;
+                    }
+                    o
+                }
+                Filter::Any(filters) => filters.iter().flat_map(|f| recurse(f)).collect(),
+                Filter::Match(path, _) => vec![vec![BinningComponent::Match(path.to_owned())]],
+                Filter::Has(path) => vec![vec![BinningComponent::Has(path.to_owned())]],
+            }
+        }
+        recurse(self).into_iter().map(Binning::new).collect()
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use crate::{
+        filter::binning::{Binning, BinningComponent},
+        query::Filter,
+    };
+    use jellycommon::jellyobject::{Tag, path::Path};
+
+    #[test]
+    fn all() {
+        let f = Filter::All(vec![
+            Filter::Has(Path(vec![Tag(0)])),
+            Filter::Has(Path(vec![Tag(1)])),
+        ]);
+        let bins = vec![Binning::new(vec![
+            BinningComponent::Has(Path(vec![Tag(0)])),
+            BinningComponent::Has(Path(vec![Tag(1)])),
+        ])];
+        assert_eq!(f.get_bins(), bins)
+    }
+
+    #[test]
+    fn any() {
+        let f = Filter::Any(vec![
+            Filter::Has(Path(vec![Tag(0)])),
+            Filter::Has(Path(vec![Tag(1)])),
+        ]);
+        let bins = vec![
+            Binning::new(vec![BinningComponent::Has(Path(vec![Tag(0)]))]),
+            Binning::new(vec![BinningComponent::Has(Path(vec![Tag(1)]))]),
+        ];
+        assert_eq!(f.get_bins(), bins)
+    }
+
+    #[test]
+    fn nested() {
+        let f = Filter::All(vec![
+            Filter::Any(vec![
+                Filter::Has(Path(vec![Tag(0)])),
+                Filter::Has(Path(vec![Tag(1)])),
+            ]),
+            Filter::Any(vec![
+                Filter::Has(Path(vec![Tag(2)])),
+                Filter::Has(Path(vec![Tag(3)])),
+            ]),
+        ]);
+        let bins = vec![
+            Binning::new(vec![
+                BinningComponent::Has(Path(vec![Tag(0)])),
+                BinningComponent::Has(Path(vec![Tag(2)])),
+            ]),
+            Binning::new(vec![
+                BinningComponent::Has(Path(vec![Tag(1)])),
+                BinningComponent::Has(Path(vec![Tag(2)])),
+            ]),
+            Binning::new(vec![
+                BinningComponent::Has(Path(vec![Tag(0)])),
+                BinningComponent::Has(Path(vec![Tag(3)])),
+            ]),
+            Binning::new(vec![
+                BinningComponent::Has(Path(vec![Tag(1)])),
+                BinningComponent::Has(Path(vec![Tag(3)])),
+            ]),
+        ];
+        assert_eq!(f.get_bins(), bins)
+    }
+}
diff --git a/database/src/indices/rating.rs b/database/src/indices/rating.rs
deleted file mode 100644
index 003d327..0000000
--- a/database/src/indices/rating.rs
+++ /dev/null
@@ -1,41 +0,0 @@
-/*
-    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
-    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
-    Copyright (C) 2026 metamuffin <metamuffin.org>
-*/
-
-use crate::{
-    backends::WriteTransaction,
-    indices::Index,
-    table::{RowNum, TableNum},
-};
-use anyhow::Result;
-use bytemuck::NoUninit;
-use jellycommon::jellyobject::{Object, Tag, TypedTag};
-
-#[derive(Clone)]
-pub struct RatingIndex {
-    id: TableNum,
-    tag: TypedTag<Object<'static>>,
-}
-
-#[repr(C)]
-#[derive(NoUninit, Clone, Copy)]
-struct Key(TableNum, Tag, u32, u64, RowNum);
-
-impl RatingIndex {
-    pub fn new(id: TableNum, tag: TypedTag<Object<'static>>) -> Self {
-        Self { id, tag }
-    }
-}
-impl Index for RatingIndex {
-    fn add(&self, db: &mut dyn WriteTransaction, id: RowNum, val: Object) -> Result<()> {
-        todo!()
-    }
-    fn remove(&self, db: &mut dyn WriteTransaction, id: RowNum, val: Object) -> Result<()> {
-        todo!()
-    }
-    fn compare(&self, before: Object, after: Object) -> bool {
-        todo!()
-    }
-}
diff --git a/database/src/indices/reference.rs b/database/src/indices/reference.rs
deleted file mode 100644
index 66efa24..0000000
--- a/database/src/indices/reference.rs
+++ /dev/null
@@ -1,71 +0,0 @@
-/*
-    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
-    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
-    Copyright (C) 2026 metamuffin <metamuffin.org>
-*/
-
-use crate::{
-    backends::{ReadTransaction, WriteTransaction},
-    indices::Index,
-    prefix_iterator::PrefixIterator,
-    table::{RowNum, TableNum},
-};
-use anyhow::Result;
-use bytemuck::{NoUninit, bytes_of};
-use jellycommon::jellyobject::{Object, TypedTag};
-
-pub struct ReferenceIndex {
-    id: TableNum,
-    tag: TypedTag<RowNum>,
-}
-
-#[repr(C)]
-#[derive(NoUninit, Clone, Copy)]
-pub struct Key(TableNum, RowNum, RowNum);
-
-impl ReferenceIndex {
-    pub fn new(id: TableNum, tag: TypedTag<RowNum>) -> Self {
-        Self { id, tag }
-    }
-    pub fn lookup<'a>(
-        &self,
-        db: &'a dyn ReadTransaction,
-        to: RowNum,
-    ) -> Result<PrefixIterator<'a>> {
-        let mut prefix = Vec::new();
-        prefix.extend(self.id.to_be_bytes());
-        prefix.extend(to.to_be_bytes());
-        Ok(PrefixIterator {
-            inner: db.iter(&prefix, false)?,
-            prefix: prefix.into(),
-        })
-    }
-}
-impl Index for ReferenceIndex {
-    fn add(&self, db: &mut dyn WriteTransaction, id: RowNum, val: Object) -> Result<()> {
-        for to in val.iter(self.tag) {
-            db.set(bytes_of(&Key(self.id, to, id)), &[])?;
-        }
-        Ok(())
-    }
-    fn remove(&self, db: &mut dyn WriteTransaction, id: RowNum, val: Object) -> Result<()> {
-        for to in val.iter(self.tag) {
-            db.del(bytes_of(&Key(self.id, to, id)))?;
-        }
-        Ok(())
-    }
-    fn compare(&self, before: Object, after: Object) -> bool {
-        let mut before = before.iter(self.tag);
-        let mut after = after.iter(self.tag);
-        loop {
-            let b = before.next();
-            let a = after.next();
-            if a.is_none() && b.is_none() {
-                break true;
-            }
-            if a != b {
-                break false;
-            }
-        }
-    }
-}
diff --git a/database/src/lib.rs b/database/src/lib.rs
index df314b6..9c372b4 100644
--- a/database/src/lib.rs
+++ b/database/src/lib.rs
@@ -4,46 +4,10 @@
     Copyright (C) 2026 metamuffin <metamuffin.org>
 */
 pub mod backends;
-pub mod indices;
+pub mod sort;
 pub mod prefix_iterator;
 pub mod table;
+pub mod query;
+pub mod filter;
 
 pub type Pad32 = u32;
-
-use jellycommon::jellyobject::Tag;
-
-pub struct Query {
-    pub filter: Filter,
-    pub sort: Sort,
-}
-
-pub enum Sort {
-    None,
-    Value(Vec<ValueSortComponent>),
-    TextSearch(Path, String),
-}
-pub struct ValueSortComponent {
-    pub order: SortOrder,
-    pub path: Path,
-    pub multi: MultiBehaviour,
-    pub offset: Option<Vec<u8>>,
-}
-pub enum MultiBehaviour {
-    First,
-    ForEach,
-    Max,
-    Min,
-    Count,
-}
-pub enum SortOrder {
-    Ascending,
-    Descending,
-}
-pub enum Filter {
-    And(Vec<Filter>),
-    Or(Vec<Filter>),
-    Match(Path, Vec<u8>),
-    Has(Path),
-}
-
-pub struct Path(pub Vec<Tag>);
diff --git a/database/src/query.rs b/database/src/query.rs
new file mode 100644
index 0000000..7d5c11c
--- /dev/null
+++ b/database/src/query.rs
@@ -0,0 +1,43 @@
+/*
+    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+    Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use jellycommon::jellyobject::path::Path;
+
+pub struct Query {
+    pub filter: Filter,
+    pub sort: Sort,
+}
+
+pub enum Sort {
+    None,
+    Value(ValueSortComponent),
+    TextSearch(Path, String),
+}
+pub struct ValueSortComponent {
+    pub order: SortOrder,
+    pub path: Path,
+    pub multi: MultiBehaviour,
+    pub offset: Option<Vec<u8>>,
+}
+pub enum MultiBehaviour {
+    First,
+    ForEach,
+    Max,
+    Min,
+    Count,
+}
+pub enum SortOrder {
+    Ascending,
+    Descending,
+}
+
+#[derive(Debug, Clone)]
+pub enum Filter {
+    All(Vec<Filter>),
+    Any(Vec<Filter>),
+    Match(Path, Vec<u8>),
+    Has(Path),
+}
diff --git a/database/src/indices/mod.rs b/database/src/sort/mod.rs
index 2d8642a..6473f5d 100644
--- a/database/src/indices/mod.rs
+++ b/database/src/sort/mod.rs
@@ -8,12 +8,13 @@ use crate::{backends::WriteTransaction, table::RowNum};
 use anyhow::Result;
 use jellycommon::jellyobject::Object;
 
-pub mod reference;
-pub mod rating;
+pub mod none;
+pub mod value;
 
 pub trait Index {
     fn add(&self, db: &mut dyn WriteTransaction, row: RowNum, val: Object) -> Result<()>;
     fn remove(&self, db: &mut dyn WriteTransaction, row: RowNum, val: Object) -> Result<()>;
+    /// Might return true if objects are identical for this index; false if not or uncertain
     fn compare(&self, before: Object, after: Object) -> bool {
         let _ = (before, after);
         false
diff --git a/database/src/sort/none.rs b/database/src/sort/none.rs
new file mode 100644
index 0000000..b17cb29
--- /dev/null
+++ b/database/src/sort/none.rs
@@ -0,0 +1,50 @@
+/*
+    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+    Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use crate::{
+    backends::WriteTransaction,
+    filter::binning::Binning,
+    sort::Index,
+    table::{RowNum, TableNum},
+};
+use anyhow::Result;
+use jellycommon::jellyobject::Object;
+
+pub struct UnsortedIndex {
+    id: TableNum,
+    binning: Binning,
+}
+
+impl UnsortedIndex {
+    pub fn new(id: TableNum, binning: Binning) -> Self {
+        Self { id, binning }
+    }
+    fn keys(&self, id: RowNum, ob: Object) -> Vec<Vec<u8>> {
+        let mut keys = vec![self.id.to_be_bytes().to_vec()];
+        self.binning.apply(ob, &mut keys);
+        for k in &mut keys {
+            k.extend(id.to_ne_bytes());
+        }
+        keys
+    }
+}
+impl Index for UnsortedIndex {
+    fn add(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+        for key in self.keys(id, ob) {
+            db.set(&key, &[])?;
+        }
+        Ok(())
+    }
+    fn remove(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+        for key in self.keys(id, ob) {
+            db.del(&key)?;
+        }
+        Ok(())
+    }
+    fn compare(&self, before: Object, after: Object) -> bool {
+        self.keys(0, before) == self.keys(0, after)
+    }
+}
diff --git a/database/src/sort/value.rs b/database/src/sort/value.rs
new file mode 100644
index 0000000..0381fe0
--- /dev/null
+++ b/database/src/sort/value.rs
@@ -0,0 +1,86 @@
+/*
+    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+    Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use crate::{
+    backends::WriteTransaction,
+    filter::binning::Binning,
+    query::{MultiBehaviour, ValueSortComponent},
+    sort::Index,
+    table::{RowNum, TableNum},
+};
+use anyhow::Result;
+use jellycommon::jellyobject::Object;
+
+pub struct ValueIndex {
+    id: TableNum,
+    binning: Binning,
+    sort: ValueSortComponent,
+}
+
+impl ValueIndex {
+    pub fn new(id: TableNum, binning: Binning, sort: ValueSortComponent) -> Self {
+        Self { id, binning, sort }
+    }
+    fn keys(&self, id: RowNum, ob: Object) -> Vec<Vec<u8>> {
+        let mut keys = vec![self.id.to_be_bytes().to_vec()];
+        self.binning.apply(ob, &mut keys);
+        self.sort.apply(ob, &mut keys);
+        for k in &mut keys {
+            k.extend(id.to_ne_bytes());
+        }
+        keys
+    }
+}
+impl Index for ValueIndex {
+    fn add(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+        for key in self.keys(id, ob) {
+            db.set(&key, &[])?;
+        }
+        Ok(())
+    }
+    fn remove(&self, db: &mut dyn WriteTransaction, id: RowNum, ob: Object) -> Result<()> {
+        for key in self.keys(id, ob) {
+            db.del(&key)?;
+        }
+        Ok(())
+    }
+    fn compare(&self, before: Object, after: Object) -> bool {
+        self.keys(0, before) == self.keys(0, after)
+    }
+}
+impl ValueSortComponent {
+    fn apply(&self, ob: Object, keys: &mut Vec<Vec<u8>>) {
+        match self.multi {
+            MultiBehaviour::First => {
+                if let Some(val) = self.path.get_matching_value(ob) {
+                    for k in keys.iter_mut() {
+                        k.extend(val);
+                    }
+                } else {
+                    keys.clear();
+                }
+            }
+            MultiBehaviour::ForEach => {
+                let mut keys_out = Vec::new();
+                for val in self.path.get_matching_values(ob) {
+                    for mut k in keys.clone() {
+                        k.extend(val);
+                        keys_out.push(k);
+                    }
+                }
+                *keys = keys_out
+            }
+            MultiBehaviour::Max => todo!(),
+            MultiBehaviour::Min => todo!(),
+            MultiBehaviour::Count => {
+                let count = self.path.get_matching_values(ob).len() as u32;
+                for k in keys.iter_mut() {
+                    k.extend(count.to_be_bytes());
+                }
+            }
+        }
+    }
+}
diff --git a/database/src/table.rs b/database/src/table.rs
index 16b9ed5..a48dd7e 100644
--- a/database/src/table.rs
+++ b/database/src/table.rs
@@ -6,7 +6,7 @@
 
 use crate::{
     backends::{ReadTransaction, WriteTransaction},
-    indices::Index,
+    sort::Index,
 };
 use anyhow::Result;
 use jellycommon::jellyobject::ObjectBuffer;