<commit_before>//! Customisable, user-implementable traversals for tries.
//!
//! This module contains 4 traits that allow you to write your own recursive trie traversals. Each
//! trait handles the key-splitting logic and result handling required to write a traversal. All of
//! the library's important operations are implemented as traversals (insert, remove, get_ancestor,
//! etc).
//!
//! The trait is basically a massively higher-order function. The `Input` type allows you
//! to define values to be passed down the traversal as it proceeds, while the `Output` type
//! allows you to propogate a value back up the call stack. Look at the source for `run`.
//!
//! # Which Trait?
//!
//! * `Traversal` - immutable trie, references not allowed in `Output` type.
//! * `RefTraversal` - immutable trie, references allowed in `Output` type.
//! * `TraversalMut` - mutable trie, references not allowed in `Output` type.
//! * `RefTraversalMut` - mutable trie, references allowed in `Output` type.

use {Trie, TrieKey, NibbleVec};
use keys::{match_keys, KeyMatch};

/// Identity macro to allow expansion of the "mutability" token tree.
#[macro_export]
macro_rules! id {
    ($e:item) => { $e }
}

macro_rules! if_else {
    (false, $x:expr, $y:expr) => { $y };
    (true, $x:expr, $y:expr) => { $x };
}

// FIXME: Use () default input type once 1.2/1.3 lands.
macro_rules! make_traversal_trait {
    (
        name: $name:ident,
        trie_type: $trie_type:ty,
        with_action: $with_action:tt,
        mutability: $($mut_:tt)*
    ) => { id! {
pub trait $name<'a, K: 'a, V: 'a> where K: TrieKey {
    type Input: 'a;
    type Output;

    fn default_result() -> Self::Output;

    #[allow(unused)]
    fn match_fn(trie: $trie_type, input: Self::Input) -> Self::Output {
        Self::default_result()
    }

    #[allow(unused)]
    fn no_child_fn
    (
        trie: $trie_type, input: Self::Input,
        nv: NibbleVec, bucket: usize
    ) -> Self::Output {
        Self::default_result()
    }

    #[doc = "Defaults to `match_fn`."]
    #[allow(unused)]
    fn child_match_fn(child: $trie_type, input: Self::Input, nv: NibbleVec) -> Self::Output {
        Self::match_fn(child, input)
    }

    #[allow(unused)]
    fn partial_match_fn(child: $trie_type, input: Self::Input, nv: NibbleVec, idx: usize)
    -> Self::Output {
        Self::default_result()
    }

    #[allow(unused)]
    fn first_prefix_fn(trie: $trie_type, input: Self::Input, nv: NibbleVec) -> Self::Output {
        Self::default_result()
    }

    // FIXME: Don't generate action_fn at all (cf. Rust issue #4621).
    #[doc = "Note: this function isn't called in a `RefTraversal`/`RefTraversalMut`."]
    #[allow(unused)]
    fn action_fn(trie: $trie_type, intermediate: Self::Output, bucket: usize) -> Self::Output {
        intermediate
    }

    #[doc = "Run the traversal, returning the result."]
    fn run(trie: $trie_type, input: Self::Input, mut key_fragments: NibbleVec) -> Self::Output {
        if key_fragments.len() == 0 {
            return Self::match_fn(trie, input);
        }

        let bucket = key_fragments.get(0) as usize;

        let intermediate = match trie.children[bucket] {
            None => return Self::no_child_fn(trie, input, key_fragments, bucket),
            Some(ref $($mut_)* child) => {
                match match_keys(&key_fragments, &child.key) {
                    KeyMatch::Full =>
                        Self::child_match_fn(child, input, key_fragments),
                    KeyMatch::Partial(i) =>
                        Self::partial_match_fn(child, input, key_fragments, i),
                    KeyMatch::FirstPrefix =>
                        Self::first_prefix_fn(child, input, key_fragments),
                    KeyMatch::SecondPrefix => {
                        let new_key = key_fragments.split(child.key.len());
                        Self::run(child, input, new_key)
                    }
                }
            }
        };

        if_else!($with_action, Self::action_fn(trie, intermediate, bucket), intermediate)
    }
} // end trait.
}} // end macro body.
}

make_traversal_trait!(name: Traversal, trie_type: &Trie<K, V>, with_action: true, mutability: );
make_traversal_trait!(name: RefTraversal, trie_type: &'a Trie<K, V>, with_action: true, mutability: );

make_traversal_trait!(name: TraversalMut, trie_type: &mut Trie<K, V>, with_action: true, mutability: mut);
make_traversal_trait!(name: RefTraversalMut, trie_type: &'a mut Trie<K, V>, with_action: false, mutability: mut);
<commit_msg>Fix docs for `RefTraversal` (thanks @Nashenas88).<commit_after>//! Customisable, user-implementable traversals for tries.
//!
//! This module contains 4 traits that allow you to write your own recursive trie traversals. Each
//! trait handles the key-splitting logic and result handling required to write a traversal. All of
//! the library's important operations are implemented as traversals (insert, remove, get_ancestor,
//! etc).
//!
//! The trait is basically a massively higher-order function. The `Input` type allows you
//! to define values to be passed down the traversal as it proceeds, while the `Output` type
//! allows you to propogate a value back up the call stack. Look at the source for `run`.
//!
//! # Which Trait?
//!
//! * `Traversal` - immutable trie, references not allowed in `Output` type.
//! * `RefTraversal` - immutable trie, references allowed in `Output` type.
//! * `TraversalMut` - mutable trie, references not allowed in `Output` type.
//! * `RefTraversalMut` - mutable trie, references allowed in `Output` type, no `action_fn`.

use {Trie, TrieKey, NibbleVec};
use keys::{match_keys, KeyMatch};

/// Identity macro to allow expansion of the "mutability" token tree.
#[macro_export]
macro_rules! id {
    ($e:item) => { $e }
}

macro_rules! if_else {
    (false, $x:expr, $y:expr) => { $y };
    (true, $x:expr, $y:expr) => { $x };
}

// FIXME: Use () default input type once 1.2/1.3 lands.
macro_rules! make_traversal_trait {
    (
        name: $name:ident,
        trie_type: $trie_type:ty,
        with_action: $with_action:tt,
        mutability: $($mut_:tt)*
    ) => { id! {
pub trait $name<'a, K: 'a, V: 'a> where K: TrieKey {
    type Input: 'a;
    type Output;

    fn default_result() -> Self::Output;

    #[allow(unused)]
    fn match_fn(trie: $trie_type, input: Self::Input) -> Self::Output {
        Self::default_result()
    }

    #[allow(unused)]
    fn no_child_fn
    (
        trie: $trie_type, input: Self::Input,
        nv: NibbleVec, bucket: usize
    ) -> Self::Output {
        Self::default_result()
    }

    #[doc = "Defaults to `match_fn`."]
    #[allow(unused)]
    fn child_match_fn(child: $trie_type, input: Self::Input, nv: NibbleVec) -> Self::Output {
        Self::match_fn(child, input)
    }

    #[allow(unused)]
    fn partial_match_fn(child: $trie_type, input: Self::Input, nv: NibbleVec, idx: usize)
    -> Self::Output {
        Self::default_result()
    }

    #[allow(unused)]
    fn first_prefix_fn(trie: $trie_type, input: Self::Input, nv: NibbleVec) -> Self::Output {
        Self::default_result()
    }

    // FIXME: Don't generate action_fn at all (cf. Rust issue #4621).
    #[doc = "Note: this function isn't called in a `RefTraversalMut`."]
    #[allow(unused)]
    fn action_fn(trie: $trie_type, intermediate: Self::Output, bucket: usize) -> Self::Output {
        intermediate
    }

    #[doc = "Run the traversal, returning the result."]
    fn run(trie: $trie_type, input: Self::Input, mut key_fragments: NibbleVec) -> Self::Output {
        if key_fragments.len() == 0 {
            return Self::match_fn(trie, input);
        }

        let bucket = key_fragments.get(0) as usize;

        let intermediate = match trie.children[bucket] {
            None => return Self::no_child_fn(trie, input, key_fragments, bucket),
            Some(ref $($mut_)* child) => {
                match match_keys(&key_fragments, &child.key) {
                    KeyMatch::Full =>
                        Self::child_match_fn(child, input, key_fragments),
                    KeyMatch::Partial(i) =>
                        Self::partial_match_fn(child, input, key_fragments, i),
                    KeyMatch::FirstPrefix =>
                        Self::first_prefix_fn(child, input, key_fragments),
                    KeyMatch::SecondPrefix => {
                        let new_key = key_fragments.split(child.key.len());
                        Self::run(child, input, new_key)
                    }
                }
            }
        };

        if_else!($with_action, Self::action_fn(trie, intermediate, bucket), intermediate)
    }
} // end trait.
}} // end macro body.
}

make_traversal_trait!(name: Traversal, trie_type: &Trie<K, V>, with_action: true, mutability: );
make_traversal_trait!(name: RefTraversal, trie_type: &'a Trie<K, V>, with_action: true, mutability: );

make_traversal_trait!(name: TraversalMut, trie_type: &mut Trie<K, V>, with_action: true, mutability: mut);
make_traversal_trait!(name: RefTraversalMut, trie_type: &'a mut Trie<K, V>, with_action: false, mutability: mut);

{'fraction_non_alphanumeric': 0.13949928938449765, 'fraction_numerical': 0.0026238110856018366, 'mean_word_length': 2.821219715956558, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 49, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4845933', 'n_tokens_mistral': 3020, 'n_tokens_neox': 2938, 'n_words': 803}