Bloom filters

use bloom.qweruse bloom_create, bloom_open from bloom      // Quillo 0.6: only these

bloomfilter = "3"

// A sign-up form that refuses passwords from a leaked list, kept as a 12 KB Bloom filter.////   quillo run bloom.qwe      then open http://localhost:8080/password?p=123456use "bloom.qwer"let FILTER = "data/leaked-passwords.bloom"fn load_filter() {    if bloom_open(FILTER, 10000, 0.01)? {        bloom_add(FILTER, ["123456", "password", "qwerty", "111111", "letmein", "iloveyou", "dragon", "monkey"])?    }}route GET /password ? { p: str } {    load_filter()    { leaked: bloom_check(FILTER, p)? }}route GET /batch {    load_filter()    { checks: bloom_check_many(FILTER, ["qwerty", "correct horse battery staple", "dragon"])?, info: bloom_info(FILTER)?, again: bloom_add(FILTER, ["qwerty"])? }}

//! Bloom filters saved to a file: "have we seen this before?" for millions of emails, URLs or leaked passwords in a few megabytes, never a false "no", rarely a false "maybe".//! version: 1.0.0//!//! [dependencies]//! bloomfilter = "3"use bloomfilter::Bloom;use serde_json::{json, Value};use std::collections::HashMap;use std::sync::Mutex;/// Filters in use, by path, kept in memory between calls.static OPEN: Mutex<Option<HashMap<String, Bloom<str>>>> = Mutex::new(None);fn save(path: &str, b: &Bloom<str>) -> Result<(), String> {    if let Some(dir) = std::path::Path::new(path).parent() {        if !dir.as_os_str().is_empty() {            std::fs::create_dir_all(dir).map_err(|e| format!("{}: {}", dir.display(), e))?;        }    }    // Written aside, then moved over the old file: a crash never leaves half a filter.    let tmp = format!("{}.tmp", path);    std::fs::write(&tmp, b.to_bytes()).map_err(|e| format!("{}: {}", tmp, e))?;    std::fs::rename(&tmp, path).map_err(|e| format!("{}: {}", path, e))}fn with<T>(path: &str, f: impl FnOnce(&mut Bloom<str>) -> T) -> Result<T, String> {    let mut g = OPEN.lock().unwrap_or_else(|e| e.into_inner());    let open = g.get_or_insert_with(HashMap::new);    if !open.contains_key(path) {        let bytes = std::fs::read(path).map_err(|e| format!("{}: {} (make it with bloom_create)", path, e))?;        open.insert(path.to_string(), Bloom::from_bytes(bytes).map_err(|e| format!("{}: {}", path, e))?);    }    Ok(f(open.get_mut(path).ok_or("filter missing")?))}/// Makes an empty filter at `path` (its folders too, replacing any filter there) for up to `expected_items` items (up to 100 million) with a false "maybe" rate of `false_positive_rate` (0.01 is 1 in 100). Gives its size in bytes: about 1.2 MB for a million items at 1%.pub fn bloom_create(path: &str, expected_items: i64, false_positive_rate: f64) -> Result<i64, String> {    if !(1..=100_000_000).contains(&expected_items) {        return Err("expected_items from 1 to 100 million".into());    }    if !(0.000_001..0.5).contains(&false_positive_rate) {        return Err("false_positive_rate from 0.000001 to 0.5".into());    }    let b: Bloom<str> = Bloom::new_for_fp_rate(expected_items as usize, false_positive_rate).map_err(|e| e.to_string())?;    save(path, &b)?;    let n = b.as_slice().len() as i64;    OPEN.lock().unwrap_or_else(|e| e.into_inner()).get_or_insert_with(HashMap::new).insert(path.to_string(), b);    Ok(n)}/// The filter at `path` when there is one, else a new one made as `bloom_create` makes it: true when it was just made, so the caller fills it once.pub fn bloom_open(path: &str, expected_items: i64, false_positive_rate: f64) -> Result<bool, String> {    if std::path::Path::new(path).exists() {        with(path, |_| ())?;        return Ok(false);    }    bloom_create(path, expected_items, false_positive_rate)?;    Ok(true)}/// Adds `items` (up to 100,000 a call) to the filter at `path` and saves it; gives how many were new (not already "maybe" in it).pub fn bloom_add(path: &str, items: Vec<String>) -> Result<i64, String> {    if items.len() > 100_000 {        return Err("up to 100,000 items a call".into());    }    let (n, snapshot) = with(path, |b| {        let n = items.iter().filter(|i| !b.check_and_set(i.as_str())).count() as i64;        (n, b.to_bytes())    })?;    if n > 0 {        let b = Bloom::<str>::from_bytes(snapshot).map_err(|e| e.to_string())?;        save(path, &b)?;    }    Ok(n)}/// Whether `item` may be in the filter: false means certainly not; true means probably (wrong at the rate the filter was made for).pub fn bloom_check(path: &str, item: &str) -> Result<bool, String> {    with(path, |b| b.check(item))}/// `bloom_check` for each of `items`, in order.pub fn bloom_check_many(path: &str, items: Vec<String>) -> Result<Vec<bool>, String> {    with(path, |b| items.iter().map(|i| b.check(i.as_str())).collect())}/// The filter's `{ bytes, hashes }`: its size and how many hash functions each item sets.pub fn bloom_info(path: &str) -> Result<Value, String> {    with(path, |b| json!({ "bytes": b.as_slice().len(), "hashes": b.number_of_hash_functions() }))}