Crate tola_caps 

tola-caps

Capability system using 16-ary type-level trie with hash-stream routing.

Type-level capability system for Rust.

Architecture

tola-caps allows types to act as sets of keys (Capabilities).

1. Routing

We use a 64-bit FNV-1a Hash of the capability’s name to route it into a 16-ary Radix Trie.

Type Name -> FNV Hash (u64) -> Nibble Stream -> Trie Path (Node16)

2. Identity (Finger Tree)

Hash collisions are resolved via Finger Tree Identities. Each capability encodes its full path (Name@file:line:col) as a Finger Tree:

FDeep<Measure, Prefix, Spine, Suffix>
  |        |        |        |
  XOR hash  First   Middle    Last
  (O(1))   1-4 B    bytes    1-4 B

3. Comparison

Three-layer comparison: Measure (O(1)) -> Prefix -> Suffix -> Spine (O(log n))

4. Fallback Tricks

We use Autoref/Method Priority to achieve trait detection and stable specialization.

+-------------------------------------------------------------------+
|  Layer 0: Primitives                                              |
|  - Nibble (X0-XF), Stream, Identity (Byte/Char), Finger Tree      |
+-------------------------------------------------------------------+
                               |
                               v
+-------------------------------------------------------------------+
|  Layer 1: Trie Core                                               |
|  - Node16, Leaf, Bucket (Storage)                                 |
|  - InsertAt, RemoveAt, Evaluate (Logic)                           |
+-------------------------------------------------------------------+
                               |
                               v
+-------------------------------------------------------------------+
|  Layer 2: User API                                                |
|  - macros (caps!, caps_check!), AutoCaps, Feature Detection       |
+-------------------------------------------------------------------+

Features

• O(1) Compile-time Lookup: Type-level hash-based routing via 16-ary radix trie
• Zero Runtime Overhead: All capability checks happen at compile time
• Infinite Extensibility: Define capabilities anywhere, no central registry needed
• Clean API: No _ placeholders or turbofish in function signatures

Quick Start

use tola_caps::prelude::*;

// Define capabilities with derive (auto-generates hash stream)
#[derive(Capability)]
struct CanRead;

#[derive(Capability)]
struct CanWrite;

// Build capability set
type MyCaps = caps![CanRead, CanWrite];

// Function with capability requirements
fn process<C>()
where
    C: Evaluate<CanRead, Out = Present>,
{ }

// Call with explicit type
process::<MyCaps>();

Re-exports

pub use primitives::bool::Bool;

pub use primitives::bool::Present;

pub use primitives::bool::Absent;

pub use primitives::bool::BoolAnd;

pub use primitives::bool::BoolOr;

pub use primitives::bool::BoolNot;

pub use primitives::nibble::Nibble;

pub use primitives::nibble::NibbleEq;

pub use primitives::nibble::X0;

pub use primitives::nibble::X1;

pub use primitives::nibble::X2;

pub use primitives::nibble::X3;

pub use primitives::nibble::X4;

pub use primitives::nibble::X5;

pub use primitives::nibble::X6;

pub use primitives::nibble::X7;

pub use primitives::nibble::X8;

pub use primitives::nibble::X9;

pub use primitives::nibble::XA;

pub use primitives::nibble::XB;

pub use primitives::nibble::XC;

pub use primitives::nibble::XD;

pub use primitives::nibble::XE;

pub use primitives::nibble::XF;

pub use primitives::stream::HashStream;

pub use primitives::stream::GetTail;

pub use primitives::stream::ConstStream;

pub use primitives::stream::AltStream;

pub use primitives::stream::Cons;

pub use primitives::stream::Z;

pub use primitives::stream::S;

pub use primitives::stream::DefaultMaxDepth;

pub use primitives::stream::StreamEq;

pub use primitives::stream::StreamEqDispatch;

pub use primitives::stream::D0;

pub use primitives::stream::D16;

pub use primitives::stream::Peano;

pub use primitives::stream::HashStream16;

pub use paste;

pub use trie::*;

Modules

capability

detect

Layer 2: Std Trait Detection

prelude

Common items for the capability system.

primitives

Layer 0: Primitives

spec

Layer 3: Specialization Sugar

std_caps

syntax_macros

Nightly Specialization Syntax Simulation Macros

trie

Layer 1: Trie Core

Macros

__internal_make_identity

Internal: Convert a path string to a Finger Tree identity type. Used by #[derive(Capability)] to create stable, reproducible identities. The input must be: concat!(module_path!(), “::”, stringify!(TypeName))

all

Macro for All query

any

Macro for Any query

caps

Create a capability set type from a list of capabilities.

caps_check

Check if types satisfy trait constraints with boolean expression support.

capset

Macro to build a CapSet from multiple capabilities Usage: capset![CapA, CapB, CapC]

define_trait_cap

Define a capability marker for a user trait.

define_type_cap

Define a type capability marker.

derive_trait_cap

Generate capability marker and detection for a custom trait.

dispatch

Inline compile-time dispatch based on capability.

for_distinct_pairs

Generate impls for all distinct pairs (A, B) and (B, A) where A != B.

for_each_nibble

Iterate over all 16 nibbles (X0..XF).

for_each_nibble_pair

Iterate over all 16 (Nibble, SlotName) pairs.

has_impl

Check if a concrete type implements a trait at compile time.

hlist

Build HList for All/Any queries

impl_capability

Macro to implement Capability for a struct manually (testing only)

impl_specialized

Implement a trait with automatic specialization based on capabilities.

intersect

Macro to compute intersection of two capability sets Usage: intersect![SetA, SetB]

make_identity_bytes

Internal: Generate IdentityBytes type from module path string. Uses const fn pack_str_bytes for const evaluation after concat!() expansion.

make_routing_stream

Internal: Compute routing hash stream from a full module path string. Input must be a string literal (e.g. from concat!).

name_stream

Generate a type-level nibble stream from an identifier name.

specialization

Nightly-like specialization block syntax on Stable Rust.

specialize_inherent

Alias for specialization_inherent! (backwards compatibility)

specialize_trait

Define a trait with default implementation that can be specialized.

union

Macro to compute union of two capability sets Usage: union![SetA, SetB]

with

Macro to add a capability to a set Usage:

without

Macro to remove a capability from a set Usage:

Attribute Macros

cap

Unified capability attribute macro.

caps_bound

Unified capability constraint macro with boolean expression support.

specialize

#[specialize] attribute macro for distributed specialization across files.

trait_autocaps

Attribute macro to enable a trait for the caps system.

Derive Macros

AutoCaps

Derive macro to auto-detect standard trait implementations.

Capability

Derive macro to automatically implement the Capability trait.