db random sort

5 files changed, 50 insertions, 5 deletions

diff --git a/database/src/kv/index.rs b/database/src/kv/index.rs
index 7a3a5b1..60d291c 100644
--- a/database/src/kv/index.rs
+++ b/database/src/kv/index.rs
@@ -15,6 +15,7 @@ use crate::{
 };
 use anyhow::Result;
 use jellyobject::Object;
+use std::iter::empty;
 
 pub fn update_index(
     txn: &mut dyn jellykv::Transaction,
@@ -37,6 +38,16 @@ pub fn update_index(
                 }
             }
         }
+        SortKey::Random => {
+            for mut k in ks {
+                k.extend(randomize(row).to_be_bytes());
+                if remove {
+                    txn.del(&k)?;
+                } else {
+                    txn.set(&k, &row.to_be_bytes())?;
+                }
+            }
+        }
         SortKey::Count => {
             for k in ks {
                 let mut c = read_counter(txn, &k, 0)?;
@@ -62,7 +73,7 @@ pub fn update_index(
                 }
             }
         }
-        SortKey::Text(path) => {}
+        SortKey::Text(_) => todo!(),
     }
     Ok(())
 }
@@ -91,6 +102,20 @@ pub fn iter_index<'a>(
                 })
             }),
         ),
+        Sort::Random(seed) => {
+            let mut k = prefix.clone();
+            k.extend(randomize(*seed).to_be_bytes());
+            let Some(it) = txn.iter(&k, false)?.next() else {
+                return Ok(Box::new(empty()));
+            };
+            let res = it?;
+            if !res.starts_with(&prefix) {
+                return Ok(Box::new(empty()));
+            }
+            let r = txn.get(&res)?.unwrap();
+            let row = RowNum::from_be_bytes(r.try_into().unwrap());
+            Box::new([Ok((row, vec![]))].into_iter())
+        }
         Sort::Value(value_sort) => {
             assert!(value_sort.offset.is_none(), "TODO");
             Box::new(
@@ -111,7 +136,7 @@ pub fn iter_index<'a>(
                 }),
             )
         }
-        Sort::TextSearch(path, _) => todo!(),
+        Sort::TextSearch(_, _) => todo!(),
     })
 }
 
@@ -125,3 +150,12 @@ fn prefix_end(mut prefix: Vec<u8>) -> Vec<u8> {
     }
     prefix
 }
+
+fn randomize(mut x: u64) -> u64 {
+    for _ in 0..15 {
+        x ^= x << 13;
+        x ^= x >> 7;
+        x ^= x << 17;
+    }
+    x
+}
diff --git a/database/src/kv/index_key.rs b/database/src/kv/index_key.rs
index fae7d4a..ec8f183 100644
--- a/database/src/kv/index_key.rs
+++ b/database/src/kv/index_key.rs
@@ -21,6 +21,7 @@ pub struct IndexKey(pub Binning, pub SortKey);
 pub enum SortKey {
     None,
     Count,
+    Random,
     Value(Path, MultiBehaviour),
     Text(Path),
 }
@@ -29,6 +30,7 @@ impl Sort {
     pub fn key(&self) -> SortKey {
         match self {
             Sort::None => SortKey::None,
+            Sort::Random(_) => SortKey::Random,
             Sort::Value(vs) => SortKey::Value(vs.path.clone(), vs.multi),
             Sort::TextSearch(p, _) => SortKey::Text(p.to_owned()),
         }
@@ -90,6 +92,7 @@ impl SortKey {
         *b = &b[1..];
         match ty {
             0 => SortKey::None,
+            4 => SortKey::Random,
             1 => SortKey::Count,
             2 => SortKey::Value(read_path(b), {
                 let mb = b[0];
@@ -110,6 +113,7 @@ impl SortKey {
     fn write(&self, out: &mut Vec<u8>) {
         match self {
             SortKey::None => out.push(0),
+            SortKey::Random => out.push(4),
             SortKey::Count => out.push(1),
             SortKey::Value(path, multi_behaviour) => {
                 out.push(2);
@@ -158,6 +162,7 @@ impl Display for SortKey {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
             SortKey::None => write!(f, "none"),
+            SortKey::Random => write!(f, "random"),
             SortKey::Count => write!(f, "count"),
             SortKey::Value(path, multi) => write!(f, "value({path}, {multi})"),
             SortKey::Text(path) => write!(f, "text({path})"),
diff --git a/database/src/kv/merge_iterator.rs b/database/src/kv/merge_iterator.rs
index 5658416..8398ba4 100644
--- a/database/src/kv/merge_iterator.rs
+++ b/database/src/kv/merge_iterator.rs
@@ -18,6 +18,7 @@ impl<'a> MergeIterator<'a> {
 impl<'a> Iterator for MergeIterator<'a> {
     type Item = Result<(RowNum, Vec<u8>)>;
     fn next(&mut self) -> Option<Self::Item> {
+        let _ = self.iters;
         todo!()
     }
 }
diff --git a/database/src/lib.rs b/database/src/lib.rs
index 5567020..1f491de 100644
--- a/database/src/lib.rs
+++ b/database/src/lib.rs
@@ -43,6 +43,7 @@ pub struct Query<'a> {
 pub enum Sort {
     #[default]
     None,
+    Random(u64),
     Value(ValueSort),
     TextSearch(Path, String),
 }
diff --git a/database/src/query_syntax.rs b/database/src/query_syntax.rs
index 8720912..b192361 100644
--- a/database/src/query_syntax.rs
+++ b/database/src/query_syntax.rs
@@ -4,10 +4,9 @@
     Copyright (C) 2026 metamuffin <metamuffin.org>
 */
 
-use anyhow::{Error, anyhow, bail};
-use jellyobject::{Path, Tag, Value};
-
 use crate::{Filter, MultiBehaviour, Query, Sort, SortOrder, ValueSort};
+use anyhow::{Error, anyhow, bail};
+use jellyobject::{Path, Value};
 use std::{fmt::Display, str::FromStr};
 
 impl Display for Query<'_> {
@@ -55,6 +54,8 @@ impl Display for Sort {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
             Sort::None => write!(f, "NONE"),
+            Sort::Random(0) => write!(f, "RANDOM"),
+            Sort::Random(seed) => write!(f, "RANDOM WITH SEED {seed}"),
             Sort::Value(ValueSort {
                 multi, order, path, ..
             }) => {
@@ -139,6 +140,8 @@ impl FromStr for Sort {
     fn from_str(s: &str) -> Result<Self, Self::Err> {
         Ok(if s == "NONE" {
             Sort::None
+        } else if s == "RANDOM" {
+            Sort::Random(1)
         } else if let Some(s) = s.strip_prefix("TEXT SEARCH ")
             && let Some((path, value)) = s.split_once(" = ")
         {
@@ -174,6 +177,7 @@ impl FromStr for Sort {
 
 #[test]
 fn test_parse() {
+    use jellyobject::Tag;
     assert_eq!(
         Query::from_str("FILTER (visi = visi AND kind = vide) SORT DESCENDING BY FIRST rldt")
             .unwrap(),