### Visual Example of Shard Splitting

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Illustrates the concept of splitting a shard into two smaller shards, showing the distribution of documents and their sizes before and after the split.

```ascii
Before Split:
    Shard 0 [0-200]
    +---------------+ 
    | Doc1  [50]    |
    | Doc2  [75]    |
    | Doc3  [125]   |
    | Doc4  [175]   |
    +---------------+ 

After Split:
    Shard 0 [0-100]     Shard 1 [101-200]
    +---------------+   +----------------+
    | Doc1  [50]    |   | Doc3  [125]    |
    | Doc2  [75]    |   | Doc4  [175]    |
    +---------------+   +----------------+
```

--------------------------------

### Accessing and Writing to a File in Browser JavaScript

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Demonstrates how to get the root directory, open a file with create option, and write encoded data to it using the File System API in JavaScript.

```javascript
// we get access to the isolated directory for our page
const root = await navigator.storage.getDirectory();
// we open a file
const draftHandle = await root.getFileHandle("draft.txt", { create: true });
// we write to the file
const encoder = new TextEncoder();
const encodedMessage = encoder.encode(message);
const writeBuffer = accessHandle.write(encodedMessage, { at: readBuffer });
```

--------------------------------

### Configure Git-Metrics Budget Rules

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202408041030-git-metrics.md

Define rules in a .git-metrics.toml file to enforce metric budgets. This example shows rules for binary size (max increase, max value) and code coverage (minimum percentage).

```toml
# fails when increase size is above 10%
[[metrics.binary-size.rules]]
type = "max-increase"
ratio = 0.1

# fails when the size increases by more that 1MB
[[metrics.binary-size.rules]]
type = "max-increase"
value = 1048576.0

# fails when binary size is more than 10MB
[[metrics.binary-size.rules]]
type = "max"
value = 10485760.0

# fails when the code coverage goes below 80%
[[metrics."coverage.lines.percentage".rules]]
type = "min"
value = 0.8

```

--------------------------------

### Getting the Root Directory in Rust using Web-sys

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Shows how to obtain the isolated root directory handle for the browser's File System API using Rust and the web-sys crate.

```rust
// getting the worker scope
let scope = js_sys::global().unchecking_into::<WorkerGlobalScope>();
// getting the storage manager
let manager = scope.navigator().storage();
// getting the root directory
let root = JsFuture::from(manager.get_directory())
    .await
    .unwrap()
    .dyn_into::<FileSystemDirectoryHandle>()
    .unwrap();
```

--------------------------------

### Implement TrieNode Search Method

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Searches the Trie for words starting with a given prefix. It first finds the relevant node and then uses TrieNodeTermIterator to collect all matching terms.

```rust
impl TrieNode {
    fn search(&self, prefix: &str) -> impl Iterator<Item = Box<str>> {
        if let Some(found) = self.find_starts_with(prefix.chars()) {
            TrieNodeTermIterator::new(found)
        } else {
            TrieNodeTermIterator::default()
        }
    }
}
```

--------------------------------

### Implement TrieNode Find Starts With Method

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Recursively traverses the Trie to find the node corresponding to the end of a given prefix string.

```rust
impl TrieNode {
    fn find_starts_with(&self, mut value: Chars<'_>) -> Option<&TrieNode> {
        let character = value.next()?;
        self.children
            .get(&character)
            .and_then(|child| child.find_starts_with(value))
    }
}
```

--------------------------------

### Cached Encrypted File Implementation

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Provides a mechanism to cache deserialized index data. The `get` method ensures that the file is deserialized only on the first access and subsequent accesses retrieve the cached data.

```rust
struct CachedEncryptedFile<T> {
    file: EncryptedFile,
    cache: async_lock::OnceCell<T>,
}

impl<T: serde::de::DeserializedOwned> CachedEncryptedFile<T> {
    async fn get(&self) -> std::io::Result<&T> {
        self.cache
            // here we only deserialize the file when we need to access it
            // and it remains cached
            .get_or_try_init(|| async { self.file.deserialize::<T>().await })
            .await
    }
}
```

--------------------------------

### Creating and Writing to a File in Rust using Web-sys

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Illustrates how to create a file, obtain a synchronous access handle, and prepare for writing operations using the File System API in Rust.

```rust
// definiting the options for opening the file
// surprisingly, no need to be mutable
let opts = FileSystemGetFileOptions::new();
opts.set_create(true);
let promise = root.get_file_handle_with_options("draft.txt", &opts);
let file = JsFuture::from(promise)
    .await
    .unwrap()
    .dyn_into::<FileSystemFileHandle>()
    .unwrap();
// creating an access handle
let promise = file.create_sync_access_handle();
let access = JsFuture::from(promise)
    .await
    .unwrap()
    .dyn_into::<FileSystemSyncAccessHandle<>()
    .unwrap();
```

--------------------------------

### Directory Operations: Create, List, Delete

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Implements asynchronous methods for the `Directory` struct to create the directory, list its files, and delete the directory and its contents.

```rust
impl Directory {
    /// creates the directory if not exists
    async fn create(&self) -> std::io::Result<()> {
        fs::create_dir_all(&self.path).await
    }

    /// list all the files in the current directory
    async fn files(&self) -> std::io::Result<Vec<PathBuf>> {
        use futures_lite::StreamExt;

        let mut result = Vec::new();
        if let Ok(mut res) = fs::read_dir(&self.path).await {
            while let Ok(Some(item)) = res.try_next().await {
                let filepath = item.path();
                if filepath.is_file() {
                    result.push(filepath);
                }
            }
        }

        Ok(result)
    }

    /// removes the current directory and all its content
    async fn delete(&self) -> std::io::Result<()> {
        fs::remove_dir_all(&self.path).await
    }
}
```

--------------------------------

### Conditional Imports for Filesystem Implementations in Rust

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Demonstrates how to conditionally import either the browser-fs or async-fs crate based on the target architecture, enabling cross-platform filesystem access.

```rust
#[cfg(target_arch = "wasm32")]
use browser_fs::*;
#[cfg(not(target_arch = "wasm32"))]
use async_fs::*;
```

--------------------------------

### Initialize Cipher from Key

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Provides a method to create a new Cipher instance from a byte slice representing the encryption key. Handles invalid key lengths.

```rust
impl Cipher {
    pub fn from_key(input: &[u8]) -> Result<Self, Error> {
        aes_gcm::Aes256Gcm::new_from_slice(input)
            .map(|inner| Self(Arc::new(inner)))
            .map_err(|_| Error::InvalidKeyLength)
    }
}
```

--------------------------------

### Execute Search Expression Iteratively with RPN

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

This snippet demonstrates the sequential execution of a search expression using an iterator and a stack, suitable for Reverse Polish Notation (RPN) evaluation. It processes conditions and aggregates results iteratively.

```rust
impl Expression {
    async fn execute(&self, shard: &Shard) -> HashMap<EntryIndex, f64> {
        let mut stack = Vec::new();

        for item in self.iter() {
            match item {
                Item::Condition(cond) => {
                    let result = condition.execute(shard).await?;
                    stack.push(result);
                }
                // kind is AND/OR
                Item::Expression(kind) => {
                    let right = stack.pop().unwrap();
                    let left = stack.pop().unwrap();
                    stack.push(aggregate(kind, left, right));
                }
            }
        }

        Ok(stack.pop().unwrap_or_default())
    }
}
```

--------------------------------

### Import LCOV File for Code Coverage Metrics

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202408041030-git-metrics.md

Use this bash command to import code coverage data from an lcov.info file into git-metrics. This populates metrics like coverage.lines.count and coverage.branches.percentage.

```bash
git-metrics import lcov ./lcov.info
```

--------------------------------

### Shard Data Organization (Conceptual)

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Illustrates the hierarchical structure of a sharded search engine, from the manifest to individual shard data ranges and their associated collection indexes.

```ascii
                 Manifest
                +--------+
                | shards |
                +--------+
                     |
          +----------+-----------+
          v          v           v
    +---------+ +---------+ +---------+
    | Shard 0 | | Shard 1 | | Shard 2 |
    |---------| |---------| |---------|
    | 0 - 100 | | 101-200 | | 201-300 |
    +---------+ +---------+ +---------+
        |           |           |
    Collection  Collection  Collection
     Indexes     Indexes     Indexes
```

--------------------------------

### Add a Metric with Tags

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202408041030-git-metrics.md

Use this command to attach a new metric with specific tags to the current commit. Ensure the metric name and tag format are correct.

```bash
$ git-metrics add my-metric-name --tag "foo: bar" 1024.0
```

--------------------------------

### Define Schema and Create Document

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Defines a schema with various attribute types and then creates a document adhering to that schema. Supports text, tags, integers, and booleans, with tags allowing multiple values.

```rust
let schema = Schema::builder()
    .attribute("content", Kind::Text)
    .attribute("sender", Kind::Tag)
    .attribute("recipient", Kind::Tag)
    .attribute("timestamp", Kind::Integer)
    .attribute("encrypted", Kind::Boolean)
    .build();

let message = Document::new("message_id")
    .attribute("content", "Hello World!") // text
    .attribute("sender", "Alice") // tag
    .attribute("recipient", "Bob") // tag
    .attribute("recipient", "Charles") // multiple times the same attribute
    .attribute("timestamp", 123456789) // integer
    .attribute("encrypted", true); // boolean
```

--------------------------------

### Show Metrics for a Commit

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202408041030-git-metrics.md

Retrieve and display metrics associated with a specific commit SHA. The output format shows the metric name, tags, and value.

```bash
$ git metrics show <commit-sha>
my-metric-name{foo="bar"} 1024.0
```

--------------------------------

### Manifest and Shard with Filenames (Scalable)

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Introduces a scalable design where Manifest and Shard structs store filenames instead of direct data, enabling lazy loading and disk persistence.

```rust
struct Manifest {
    shards: BTreeMap<u64, Shard>,
}

struct Shard {
    collection: Filename,
    indexes: HashMap<Kind, Filename>,
}
```

--------------------------------

### Fetch GitHub Repositories with Token

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/templates/shortcodes/projects.md

Fetches GitHub repository data using the GitHub API, including authentication with a GITHUB_TOKEN. Use this when private repository access is needed.

```html
{% set token = get_env(name="GITHUB_TOKEN", default="") %}
{% for repo_name in page.extra.repo_names %}
  {% set url = "https://api.github.com/repos/" ~ config.extra.github.username ~ "/" ~ repo_name %}
  {% if token %}
    {% set repository = load_data(url=url, format="json", headers=["Authorization=Bearer " ~ token]) %}
  {% else %}
    {% set repository = load_data(url=url, format="json") %}
  {% endif %}
  {% if repository %}
  * [{{ repository.name }}]({{ repository.html_url }})<br>{{ repository.description }}<br><br>
  {% endif %}
{% endfor %}
```

--------------------------------

### Manager for Multiple Shards (Initial)

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Represents a collection of shards, mapping shard identifiers to Shard structs. This initial version implies loading all shards into memory.

```rust
struct Manager {
    shards: BTreeMap<u64, Shard>,
}
```

--------------------------------

### Main Search Function Implementation

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Orchestrates the search process by first identifying matching terms based on the filter, then reducing these matches to relevant entries, and finally computing scores for those entries.

```rust
    /// search through the index
    fn search(
        &self,
        attribute: Option<AttributeIndex>,
        filter: &TextFilter,
    ) -> HashMap<EntryIndex, f64> {
        let matching_terms = match filter {
            TextFilter::StartsWith { prefix } => self.trienodes().search(prefix),
            TextFilter::Matches { value } => self.trigrams().search(value),
            TextFilter::Equals { value } => self.inner.get_term(value).into_iter(),
        };
        let matching_entries = self.reduce_matches(attribute, matching_terms)
        self.compute_scores(attribute, matchings)
    }
}

```

--------------------------------

### Show Metric Differences Between Commits

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202408041030-git-metrics.md

Compare metrics between a range of commits to see additions, removals, and percentage changes. This is useful for tracking metric evolution over time.

```bash
$ git metrics diff HEAD~2..HEAD
- my-metric-name{foo="bar"} 512.0
+ my-metric-name{foo="bar"} 1024.0 (+200.00 %)
```

--------------------------------

### Robots.txt Jinja Template

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/templates/robots.txt

A Jinja template for generating a robots.txt file. It dynamically lists disallowed paths and specifies the sitemap location.

```jinja
{%-
set disallows = [
  "/404.html",
  "/files/*"
] -%}
User-agent: *
{%- for disallowed in disallows %}
Disallow: {{ disallowed }}
{%- endfor %}
Allow: /
Sitemap: {{ get_url(path="sitemap.xml") }}
```

--------------------------------

### Implementing TextIndex Insert Method

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Provides the `insert` method for the `TextIndex` struct, which adds term postings including token index and position. This method handles the creation of nested HashMaps if entries do not yet exist.

```rust
impl TextIndex {
    fn insert(
        &mut self,
        entry_index: EntryIndex,
        attribute_index: AttributeIndex,
        value_index: ValueIndex,
        term: &str,
        token_index: TokenIndex,
        position: Position,
    ) -> bool {
        let term_postings = self.content.entry(term).or_default();
        let attribute_postings = term_postings.entry(attribute_index).or_default();
        let entry_postings = entry_postings.entry(entry_index).or_default();
        let value_postings = attr_postings.entry(value_index).or_default();
        value_postings.insert((token_index, position))
    }
}
```

--------------------------------

### Complete Encryption Layer Implementation

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Combines all components of the Cipher struct, including error handling, key initialization, encryption, and decryption.

```rust
use std::sync::Arc;

use aes_gcm::aead::consts::U12;
use aes_gcm::aead::{Aead, OsRng};
use aes_gcm::{AeadCore, KeyInit};

pub enum Error {
    InvalidKeyLength,
    EncryptionFailed,
    DecryptionFailed,
}

#[derive(Clone)]
pub struct Cipher(Arc<aes_gcm::Aes256Gcm>);

impl Cipher {
    pub fn from_key(input: &[u8]) -> Result<Self, Error> {
        aes_gcm::Aes256Gcm::new_from_slice(input)
            .map(|inner| Self(Arc::new(inner)))
            .map_err(|_| Error::InvalidKeyLength)
    }

    pub fn encrypt(&self, input: &[u8]) -> std::io::Result<Vec<u8>> {
        // Each encryption gets its own 96-bit nonce
        let nonce = aes_gcm::Aes256Gcm::generate_nonce(&mut OsRng);
        let ciphertext = self.0.encrypt(&nonce, input)
            .map_err(|_| Error::EncryptionFailed)?;
        // We pack the nonce with the encrypted data
        let mut result = nonce.to_vec();
        result.extend(ciphertext);
        Ok(result)
    }

    pub fn decrypt(&self, input: &[u8]) -> Result<Vec<u8>> {
        // First 12 bytes are our nonce
        let Some((nonce, payload)) = input.split_at_checked(12) else {
            return Err(Error::DecryptionFailed);
        };

        let nonce = aes_gcm::Nonce::<U12>::from_slice(nonce);
        self.0.decrypt(nonce, payload)
            .map_err(|_| Error::DecryptionFailed)
    }
}
```

--------------------------------

### On-Disk Entry and Collection Representation

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Defines structs for representing collection entries and the entire collection on disk. This structure optimizes storage by including necessary fields for each entry.

```rust
type EntryIndex = u32;
type ShardingValue = u64;
type DocumentIdentifier = Arc<str>;

/// Representation on disk of an entry
struct Entry {
    index: EntryIndex,
    name: DocumentIdentifier,
    shard: ShardingValue,
}

/// Representation on disk of a collection
struct PersistedCollection {
    entries: Vec<Entry>
}
```

--------------------------------

### In-Memory Collection Structure

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Details the in-memory structure of the Collection, emphasizing bidirectional mappings for efficient lookups and the use of BTreeMap for ordered sharding operations. This structure is optimized for runtime performance.

```rust
/// Manages document identifiers and sharding information
struct Collection {
    /// Maps numeric indexes to document identifiers
    /// Uses u32 to optimize memory usage while supporting large datasets
    entries_by_index: HashMap<EntryIndex, DocumentIdentifier>,
    /// Reverse mapping for quick document lookups
    entries_by_name: HashMap<DocumentIdentifier, EntryIndex>,
    /// Maps sharding values to sets of document indexes
    /// Using BTreeMap for ordered access during shard splitting
    sharding: BTreeMap<ShardingValue, HashSet<EntryIndex>>,
}
```

--------------------------------

### Tokenizing and Stemming Text Input

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Extracts words from input text, converts them to lowercase, applies stemming, and assigns an index and position to each token. This process prepares text for full-text indexing.

```rust
let input = "Hello World! Do you want tomatoes?";
// extracting the words
let tokens = capture_all(r"(\w{3,20})", input)
    // lowercase them
    .map(|(position, term)| (position, term.to_lower_case()))
    // keep track of the token index
    .enumerate()
    // stemming
    .map(|(index, (position, term))| Token {
        index,
        position,
        term: stem(term),
    })
    .collect::<Vec<_>>();
// should return
// { term: "hello", index: 0, position: 0 }
// { term: "world", index: 1, position: 6 }
// { term: "you", index: 2, position: 16 }
// { term: "want", index: 3, position: 20 }
// { term: "tomato", index: 4, position: 25 }
```

--------------------------------

### Execute Search Expression Recursively

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

This snippet shows the initial recursive implementation for executing a search expression. It directly calls async methods for conditions and sub-expressions.

```rust
impl Shard {
    async fn search(&self, expression: &Expression) -> HashMap<EntryIndex, f64> {
        expression.execute(self).await
    }
}

impl Expression {
    async fn execute(&self, shard: &Shard) -> HashMap<EntryIndex, f64> {
        match self {
            Expression::Condition(condition) => condition.execute(shard).await,
            Expression::And(left, right) => {
                let left_res = left.execute(shard).await?;
                let right_res = right.execute(shard).await?;
                reduce_and(left_res, right_res)
            },
            Expression::Or(left, right) => {
                let left_res = left.execute(shard).await?;
                let right_res = right.execute(shard).await?;
                reduce_or(left_res, right_res)
            }
        }
    }
}
```

--------------------------------

### Document Struct and Builder

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Represents a document to be indexed, containing an ID and a map of attributes to their values. Includes a builder pattern for easy construction.

```rust
/// Represents a document to be indexed
struct Document {
    /// Unique identifier for the document
    id: String,
    /// Maps attribute names to their values
    /// A single attribute can have multiple values
    attributes: HashMap<String, Vec<Value>>,
}

impl Document {
    pub fn new(id: impl Into<String>) -> Self {
        Self {
            id: id.into(),
            attributes: Default::default(),
        }
    }

    pub fn attribute(mut self, name: impl Into<String>, value: impl Into<Value>) -> Self {
        self.attributes.entry(name.into()).or_default().push(value.into());
        self
    }
}
```

--------------------------------

### Schema Builder Implementation

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

This Rust code defines the `Schema` builder, including methods to set sharding attributes and build the final `Schema` object. It handles validation for the sharding attribute.

```rust
impl Schema {
    pub fn new() -> Self {
        Schema {
            attributes: HashMap::new(),
            shard_by: None,
        }
    }

    pub fn attribute(mut self, name: impl Into<String>, values: Vec<Value>) -> Self {
        self.attributes.insert(name.into(), values);
        self
    }

    pub fn shard_by(mut self, name: impl Into<String>) -> Self {
        self.shard_by = Some(name.into());
        self
    }

    pub fn build(self) -> Result<Schema, Error> {
        let Some(shard_by) = self.shard_by else {
            return Err(Error::ShardingAttributeNotSet);
        };
        if !self.attributes.contains_key(&shard_by) {
            return Err(Error::UnknownShardingAttribute);
        }

        Ok(Schema {
            attributes: self.attributes,
            shard_by,
        })
    }
}
```

--------------------------------

### Schema Builder Pattern

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Implements the builder pattern for creating Schema instances, allowing for a fluent API to define attributes and sharding configurations.

```rust
impl Schema {
    // let's follow the builder pattern
    pub fn builder() -> SchemaBuilder {
        SchemaBuilder::default()
    }
}

enum Error {
    /// when the user didn't specify a sharding attribute
    ShardingAttributeNotSet,
    /// when the user specified how to shard but the attribute is not defined
    UnknownShardingAttribute
}

#[derive(Default)]
struct SchemaBuilder {
    attributes: HashMap<String, Kind>,
    shard_by: Option<String>,
}

impl SchemaBuilder {
    pub fn attribute(mut self, name: impl Into<String>, kind: Kind) -> Self {
        self.attributes.insert(name.into(), kind);
        self
    }

    pub fn shard_by(mut self, name: impl Into<String>) -> Self {

```

--------------------------------

### Display Page Timestamp Macro

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/templates/macros.html

Formats and displays the posting date of a page. Uses configured time format and timezone.

```html
{%- macro page_timestamp(page) -%}
  Posted on {{ page.date | date(format=config.extra.timeformat | default(value="%B %e, %Y"), timezone=config.extra.timezone | default(value="Europe/Paris")) }}
{%- endmacro page_timestamp %}
```

--------------------------------

### Implement ClearFile for File Trait

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Provides a concrete implementation of the `File` trait for unencrypted files. It uses standard asynchronous file system operations.

```rust
struct ClearFile {
    path: std::path::PathBuf,
}

impl File for ClearFile {
    async fn write(&self, payload: &[u8]) -> std::io::Result<()> {
        fs::write(&self.path, payload).await
    }

    async fn read(&self) -> std::io::Result<Vec<u8>> {
        fs::read(&self.path).await
    }

    async fn delete(self) -> std::io::Result<()> {
        fs::delete(&self.path).await
    }
}
```

--------------------------------

### Transaction Manifest Management

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Manages the state of all shards during a transaction, using a BTreeMap for ordered shard keys. This is essential for maintaining consistency across multiple shards during updates.

```rust
/// manages the state of all shards during a transaction
struct TxManifest {
    /// maps shard keys to their transaction state
    /// uses BTreeMap to maintain order for efficient splits
    shards: BTreeMap<u64, TxShard>,
}
```

--------------------------------

### Encrypt Data with Nonce Prefix

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Encrypts input data using AES-GCM. Generates a unique nonce for each encryption and prefixes it to the ciphertext for easy decryption.

```rust
impl Cipher {
    pub fn encrypt(&self, input: &[u8]) -> std::io::Result<Vec<u8>> {
        // Each encryption gets its own 96-bit nonce
        let nonce = aes_gcm::Aes256Gcm::generate_nonce(&mut OsRng);
        let ciphertext = self.0
            .encrypt(&nonce, input)
            .map_err(|_| Error::EncryptionFailed)?;

        // We pack the nonce with the encrypted data
        let mut result = nonce.to_vec();
        result.extend(ciphertext);
        Ok(result)
    }
}
```

--------------------------------

### Generate GitHub Edit URL Macro

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/templates/macros.html

Creates a URL to suggest improvements on a GitHub page. Requires GitHub username and repository to be configured.

```html
{% macro get_edit_url(page) %}
  {%- set url = ["https://github.com", config.extra.github.username, config.extra.github.repo, "blob/main/content" , page.relative_path] | join(sep="/" ) %}
  [Suggest improvements]({{ url ~  "Help improve page {{ page.permalink | safe }}")
{% endmacro get_edit_url %}
```

--------------------------------

### SEO Meta Tags Macro

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/templates/macros.html

Generates SEO meta tags for a page, including title, description, and Open Graph tags. Handles different page types like home, 404, and regular pages.

```html
{%- macro seo( title="", title_addition="", description="", type="website", is_home=false, is_404=false, is_page=false ) -%}
  {%- if page.date %}
    {%- set created_date = page.date | date(format="%+") %}
  {%- endif %}
  {%- if is_404 %}
    {%- else %}
    {%- endif %}
  {%- if current_url %}
    {%- set page_url = current_url %}
  {%- else %}
    {%- set page_url = get_url(path="404.html") %}
  {%- endif %}
  {%- if current_path %}
    {%- set page_path = current_path %}
  {%- else %}
    {%- set page_path = "/404.html" %}
  {%- endif %}
  {%- if title_addition %}
    {{ title ~ " > " ~ title_addition }}
  {%- else %}
    {{ title }}
  {%- endif %}
    {%- if config.extra.opengraph %}
    {%- if page.extra.images %}
      {%- for image in page.extra.images %}
      {%- endfor %}
    {%- elif section.extra.images %}
      {%- for image in section.extra.images %}
      {%- endfor %}
    {%- elif config.extra.logo %}
    {%- endif %}
  {%- if page.date %}
  {%- endif %}
{%- endif %}
{%- endmacro %}
```

--------------------------------

### Collection Struct with Sharding

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Introduces a Collection struct that includes sharding information, mapping sharding values to document entry indexes. This structure facilitates efficient shard splitting.

```rust
type EntryIndex = u32;
type ShardingValue = u64;

struct Collection {
    entries: HashMap<EntryIndex, DocumentIdentifier>,
    sharding: BTreeMap<ShardingValue, HashSet<EntryIndex>>,
}
```

--------------------------------

### Search Engine Core Interface

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503161800-search-engine-intro.md

Defines the main trait for the search engine, outlining essential operations like indexing, searching, and deleting documents. This interface serves as the contract for different search engine implementations.

```rust
/// The main search engine interface
pub trait SearchEngine {
    /// Index a new document
    async fn index(&mut self, document: Document) -> Result<()>;
    /// Search through indexed documents
    async fn search(&self, query: &str) -> Result<SearchResults>;
    /// Delete a document from the index
    async fn delete(&mut self, id: &str) -> Result<()>;
}
```

--------------------------------

### Directory Management Structure

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Defines a `Directory` struct that holds a cipher and path, providing methods to create `ClearFile` and `EncryptedFile` instances relative to its path.

```rust
struct Directory {
    cipher: Cipher,
    path: std::path::PathBuf,
}

impl Directory {
    /// creates a new instance of a ClearFile, without creating it on the filesystem
    fn clear_file(&self, relative: impl AsRef<Path>) -> ClearFile {
        ClearFile {
            path: self.path.join(relative),
        }
    }

    /// creates a new instance of a EncryptedFile, without creating it on the filesystem
    fn encrypted_file(&self, relative: impl AsRef<Path>) -> EncryptedFile {
        EncryptedFile {
            path: self.path.join(relative),
            cipher: self.cipher.clone(),
        }
    }
}
```

--------------------------------

### Implement EncryptedFile for File Trait

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Provides a concrete implementation of the `File` trait for encrypted files. It integrates a `Cipher` for encrypting and decrypting data before file operations.

```rust
struct EncryptedFile {
    path: std::path::PathBuf,
    cipher: Cipher,
}

impl File for ClearFile {
    async fn write(&self, payload: &[u8]) -> std::io::Result<()> {
        let payload = self.cipher.encrypt(payload)
            .map_err(std::io::Error::other)?;
        fs::write(&self.path, &payload).await
    }

    async fn read(&self) -> std::io::Result<Vec<u8>> {
        let content = fs::read(&self.path).await?;
        self.cipher.decrypt(&content)
            .map_err(std::io::Error::other)
    }

    async fn delete(self) -> std::io::Result<()> {
        fs::delete(&self.path).await
    }
}
```

--------------------------------

### Implement Integer Index Filtering

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Provides methods for filtering content within an IntegerIndex based on different IntegerFilter variants. It uses BTreeMap's range query capabilities for efficient filtering.

```rust
impl IntegerIndex {
    fn filter_content(&self, filter: &IntegerFilter) -> impl Iterator<Item = &HashMap<AttributeIndex, HashMap<EntryIndex, HashSet<ValueIndex>>>> {
        match filter {
            IntegerFilter::Equals { value } => self.content.range(*value..=*value),
            IntegerFilter::GreaterThan { value } => self.content.range((*value + 1)..),
            IntegerFilter::LowerThan { value } => self.content.range(..*value),
        }
    }

    fn search(&self, attribute: Option<AttributeIndex>, filter: &IntegerFilter) -> HashSet<EntryIndex> {
        if let Some(attribute) = attribute {
            self.filter_content(filter)
                // here we filter for the given attribute
                .flat_map(|postings| postings.get(&attribute).iter())
                .flat_map(|entries| entries.keys().copied())
                .collect()
        } else {
            self.filter_content(filter)
                // here we take all the attributes
                .flat_map(|postings| postings.values())
                .flat_map(|entries| entries.keys().copied())
                .collect()
        }
    }
}
```

--------------------------------

### Delete from BooleanIndex (Initial)

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Provides an initial implementation for deleting an entry from the BooleanIndex by iterating through all postings and removing the entry index.

```rust
impl BooleanIndex {
    fn delete(&mut self, entry_index: EntryIndex) -> bool {
        let mut changed = false;
        for (term, term_postings) in self.content.iter_mut() {
            for (attribute, attribute_postings) in term_postings.iter_mut() {
                changed |= attribute_postings.remove(&entry_index).is_some();
            }
        }
        changed
    }
}
```

--------------------------------

### Aggregate Search Results (AND/OR)

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Aggregates two sets of search results based on the specified Kind (AND or OR). For AND, it calculates the intersection of entries and multiplies their normalized scores. For OR, it calculates the union and sums the normalized scores.

```rust
fn aggregate(kind: Kind, mut left: HashMap<EntryIndex, f64>, mut right: HashMap<EntryIndex, f64>) -> HashMap<EntryIndex, f64> {
    let left = normalise(left);
    let right = normalise(right);
    match kind {
        // we want the intersection
        Kind::And => left.into_iter()
            .filter_map(|(entry_index, score_left)| {
                right
                    .remove(&entry_index)
                    // we use a multiplication to join scores
                    .map(|score_right| (entry_index, score_left * score_right))
            })
            .collect(),
        // we want the union
        Kind::Or => {
            right.drain().for_each(|(entry_index, right_score)| {
                left.entry(entry_index)
                    .and_modify(|left_score| {
                        // we use the addition to join scores
                        *left_score += right_score;
                    })
                    .or_insert(right_score);
            });
            left
        },
    }
}
```

--------------------------------

### Extend File Trait with Serialization Support

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Extends the `File` trait with asynchronous methods for serializing and deserializing data using `serde_cbor`. This allows for easy storage and retrieval of structured data.

```rust
trait File {
    // keep the other trait functions here

    // Serialize and write a value to the file
    async fn serialize<V: serde::Serialize>(&self, value: &V) -> std::io::Result<()> {
        let payload = serde_cbor::to_vec(value).map_err(|err| {
            std::io::Error::new(std::io::ErrorKind::InvalidData, err)
        })?;
        self.write(&payload).await
    }

    /// Read and deserialize a value from the file
    async fn deserialize<V: serde::de::DeserializeOwned>(&self) -> std::io::Result<V> {
        let content = self.read().await?;
        serde_cbor::from_slice(&content).map_err(|err| {
            std::io::Error::new(std::io::ErrorKind::InvalidData, err)
        })
    }
}
```

--------------------------------

### Attribute and Collection Structures

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Defines Rust structs for managing attributes and collections, including indexing strategies for efficient lookups and memory optimization.

```rust
/// Let's keep a fairly low number of attributes, 256 attributes should be enough
type AttributeIndex = u8;

struct Attribute {
    index: AttributeIndex,
    name: Arc<str>,
}

struct PersistedCollection {
    attributes: Vec<Attribute>,
    entries: Vec<Entry>
}

struct Collection {
    attributes_by_index: HashMap<AttributeIndex, Arc<str>>,
    attributes_by_name: HashMap<Arc<str>, AttributeIndex>,
    // ...other fields
}
```

--------------------------------

### Execute Search Across Shards

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

This function iterates through all shards, executes a search on each, and aggregates the results. A callback function is used to process results as they become available from each shard.

```rust
impl SearchEngine {
    async fn search<Cb>(&self, expression: &Expression, callback: Cb) -> std::io::Result<usize>
    where
        Cb: Fn(HashMap<EntryIndex, f64>)
    {
        let mut found = 0;
        for (_shard_key, shard) in self.shards {
            let result = shard.search(expression).await?;
            found += result.len();
            callback(result);
        }
        Ok(found)
    }
}
```

--------------------------------

### ContentSize Trait and Implementations

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Defines a trait for estimating the size of data structures for sharding optimization. Includes implementations for primitive types, strings, and HashMaps.

```rust
/// provides size estimation for optimizing shard splits
trait ContentSize {
    /// returns estimated size in bytes when serialized
    fn estimate_size(&self) -> usize;
}

// for constant value sizes
macro_rules! const_size {
    ($name:ident) => {
        impl ContentSize for $name {
            fn estimate_size(&self) -> usize {
                std::mem::size_of::<$name>()
            }
        }
    }
}

// and for other types like u16, u32, u64 and bool
const_size!(u8);

// let's consider a string just for its content size
impl<T: AsRef<str>> ContentSize for T {
    /// estimates string size based on character count
    /// note: This is an approximation and doesn't account for encoding overhead
    fn estimate_size(&self) -> usize {
        self.as_ref().len()
    }
}

// for maps, similar
impl<K: ContentSize, V: ContentSize> for HashMap<K, V> {
    /// recursively estimates size of all keys and values
    /// used to determine when to split shards
    fn estimate_size(&self) -> usize {
        self.iter().fold(0, |acc, (key, value)| acc + key.estimate_size() + value.estimate_size())
    }
}
```

--------------------------------

### Decrypt Data Using Prefixed Nonce

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Decrypts input data by first extracting the 12-byte nonce from the beginning of the data, then using it to decrypt the remaining payload.

```rust
impl Cipher {
    pub fn decrypt(&self, input: &[u8]) -> Result<Vec<u8>> {
        // First 12 bytes are our nonce
        let Some((nonce, payload)) = input.split_at_checked(12) else {
            return Err(Error::DecryptionFailed);
        };

        let nonce = aes_gcm::Nonce::<U12>::from_slice(nonce);
        self.0.decrypt(nonce, payload)
            .map_err(|_| Error::DecryptionFailed)
    }
}
```

--------------------------------

### Shard Manifest Structure

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Defines the metadata for a shard, including the mandatory collection name and optional paths to different types of indexes (boolean, integer, tag, text).

```rust
struct ShardManifest {
    /// the collection is mandatory, it's the index of all the entries
    /// if it's none, there's no entry, so there's no shard
    collection: Box<str>,
    /// then every index is optional (except the integer index, but we'll keep the same idea)
    boolean: Option<Box<str>>,
    integer: Option<Box<str>>,
    tag: Option<Box<str>>,
    text: Option<Box<str>>,
}
```

--------------------------------

### Build Trigram Index

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Defines the `Trigrams` struct and its `insert` method for building an index of trigrams from a given string. This is used to efficiently store and retrieve words based on their trigram subsets. It requires the `HashMap` and `HashSet` collections.

```Rust
#[derive(Default)]
struct Trigrams<'a>(HashMap<[char; 3], HashSet<&'a str>>);

impl<'a> Trigrams<'a> {
    fn insert(&mut self, value: &str) {
        TrigramIter::from(value).for_each(|trigram| {
            let set: &mut HashSet<usize> = self.0.entry(trigram).or_default();
            set.insert(value);
        });
    }
}
```

--------------------------------

### Collection Splitting Mechanism

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Implements a method to split a `Collection` into two roughly equal parts based on document count. Handles cases where splitting is not possible.

```rust
impl Collection {
    /// attempts to split the collection into two roughly equal parts
    /// returns None if splitting is not possible (e.g., all documents have same shard value)
    fn split(&mut self) -> Option<Collection> {
        // if all the entries have the same sharding value, it's not possible to split considering
        // a sharding value can only be in one shard.
        if self.sharding < 2 {
            return None;
        }

        // calculate target size for new collection
        let total_count = self.entries_by_name.len();
        let half_count = total_count / 2;

        let mut new_collection = Collection::default();

        // keep moving entries until we reach approximately half size
        while new_collection.entries_by_name.len() < half_count && self.sharding.len() > 1 {
            // if this happens, it means we moved everything from the old shard, which shouldn't be possible
            // which shouldn't happen considering that we check the number of shards
            let Some((shard_value, entries)) = self.sharding.pop_last() {
                return new_collection;
            }
            // moving from the old collection to the new collection one by one
            for entry_index in entries {
                if let Some(name) = self.entries_by_index.remove(&entry_index) {
                    self.entries_by_name.remove(&name);
                    new_collection.entries_by_index.insert(entry_index, name.clone());
                    new_collection.entries_by_name.insert(name, entry_index);
                }
            }
        }
        Some(new_collection)
    }
}
```

--------------------------------

### Building Collection from Persisted State

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Implements the `From` trait to construct an in-memory `Collection` from its `PersistedCollection` representation. This function populates the necessary HashMaps and BTreeMap from disk data.

```rust
/// Let's build the collection from the persisted state
impl From<PersistedCollection> for Collection {
    fn from(value: PersistedCollection) -> Collection {
        let mut entries_by_index = HashMap::with_capacity(value.entries.len());
        let mut entries_by_name = HashMap::with_capacity(value.entries.len());
        let mut sharding = BTreeMap::default();
        for entry in value.entries {
            entries_by_index.insert(entry.index, entry.name.clone());
            entries_by_name.insert(entry.name.clone(), entry.index);
            sharding.entry(entry.shard).or_default().insert(entry.index);
        }
        Collection {
            entries_by_index,
            entries_by_name,
            sharding,
        }
    }
}
```

--------------------------------

### Define Max Decrease Rule for Code Coverage

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202408041030-git-metrics.md

This TOML snippet defines a rule for code coverage percentage, specifying that it should not decrease by more than 5%. This is useful for maintaining a minimum code quality standard.

```toml
[[metrics."coverage.lines.percentage".rules]]
type = "max-decrease"
ratio = 0.05
```

--------------------------------

### Define Search Engine Index Structure

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Defines the basic data structure for a search engine index using a map from terms to document identifiers and their counts. This structure is fundamental for mapping query terms to relevant documents.

```Rust
type Index = Map<Term, Map<DocumentIdentifier, Count>>;
```

--------------------------------

### Define Schema with Sharding

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Extends the schema definition to include a sharding strategy based on a specific integer attribute. This ensures documents are distributed based on the 'timestamp' field.

```rust
let schema = Schema::builder()
    .attribute("content", Kind::Text)
    .attribute("sender", Kind::Tag)
    .attribute("recipient", Kind::Tag)
    .attribute("timestamp", Kind::Integer)
    .attribute("encrypted", Kind::Boolean)
    .shard_by("timestamp")
    .build()?;
```

--------------------------------

### Shard Structure with Caching

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Represents a shard, holding the main collection and optional cached index files. This structure ensures that index files are loaded and deserialized only once.

```rust
struct Shard {
    /// this is loaded anyway
    collection: Collection,
    /// then we create a cache
    boolean: Option<CachedEncryptedFile<BooleanIndex>>,
    integer: Option<CachedEncryptedFile<IntegerIndex>>,
    tag: Option<CachedEncryptedFile<TagIndex>>,
    text: Option<CachedEncryptedFile<TextIndex>>,
}
```

--------------------------------

### Define the File Trait

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503170800-search-engine-part-1.md

Defines the core asynchronous operations for file interaction: write, read, and delete. This trait serves as a blueprint for different file types.

```rust
trait File {
    fn write(&self, payload: &[u8]) -> impl Future<Output = std::io::Result<()>>;
    fn read(&self) -> impl Future<Output = std::io::Result<Vec<u8>>>;
    fn delete(self) -> impl Future<Output = std::io::Result<()>>;
}
```

--------------------------------

### Basic Collection Type Definitions

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Defines fundamental types for document indexing and collection management within a sharded search engine. These types are used to represent entries, collections, and indexes.

```rust
type EntryIndex = u32;
/// the collection file in each shard
type Collection = Map<EntryIndex, DocumentIdentifier>;
/// for each index type
type Index = Map<Term, Map<EntryIndex, Count>>;
```

--------------------------------

### Kind Enum Definition

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503191700-search-engine-part-2.md

Defines the possible data types for attributes within the search engine schema. Includes Boolean, Integer (for numeric queries and sharding), Tag (for exact matches), and Text (for full-text search).

```rust
/// Represents the possible data types that can be indexed
enum Kind {
    /// Simple true/false values
    Boolean,
    /// Unsigned 64-bit integers, used for numeric queries and sharding
    Integer,
    /// Single tokens that require exact matching (e.g. email addresses, IDs)
    Tag,
    /// Full-text content that will be tokenized and stemmed
    Text,
}
```

--------------------------------

### Define TrieNode Structure for Prefix Search

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Defines a TrieNode used for efficient prefix searching. Each node can have children mapped by characters and optionally stores a complete term.

```rust
#[derive(Debug, Default)]
pub(super) struct TrieNode {
    children: BTreeMap<char, TrieNode>,
    term: Option<Box<str>>,
}
```

--------------------------------

### Transaction File State

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Represents a file's state during a transaction, tracking original and next file paths. Use this to manage individual file changes within a transaction.

```rust
/// represents a file during a transaction
struct TxFile {
    /// original file path, if it exists
    // a shard can not have any boolean index but it can be created after an update
    base: Option<Filename>,
    /// new file path after changes, if modified
    // the filename once the transaction is committed
    next: Option<Filename>,
}
```

--------------------------------

### Single Shard Representation (Initial)

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503231000-search-engine-part-3.md

Defines a Rust struct for a single shard, including a collection and a map of various index types.

```rust
// an abstraction to be able to map the indexes
enum AnyIndex {
    Boolean(BooleanIndex),
    Integer(IntegerIndex),
    Tag(TagIndex),
    Text(TextIndex),
}

struct Shard {
    collection: Collection,
    indexes: HashMap<Kind, AnyIndex>,
}
```

--------------------------------

### Reduce Matches to Entries and Term Frequencies

Source: https://github.com/jdrouet/jdrouet.github.io/blob/main/content/posts/202503311500-search-engine-part-4.md

Aggregates matching terms to identify entries that contain them and counts the frequency of each term within those entries. This prepares data for the scoring function.

```rust
    /// reduce the list of terms and return the entries matching the terms
    fn reduce_matches(
        &self,
        attribute: Option<AttributeIndex>,
        terms: impl Iterator<Item = &str>,
    ) -> HashMap<EntryIndex, HashMap<&str, usize>> {
        let mut res = HashMap::default();
        for term in terms {
            for entry_index in self.find_entries_for_term(term) {
                let entry = res.entry(entry_index).or_default();
                // count the occurences of that term in the entry
                entry.entry(term).and_modify(|v| {
                    *v += 1;
                }).or_insert(1);
            }
        }
        res
    }

```