2 files changed, 158 insertions, 0 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)
+    }
+}