ldap-acis 0.2.1

//! DN-scope based trie index for fast ACI candidate selection.
//!
//! Instead of checking every ACI against a query DN, the trie organizes
//! ACIs by their target DN in a tree structure. For a query, only ACIs
//! whose target DN scope covers the query DN are returned as candidates.

use ahash::AHashMap;
use smallvec::SmallVec;

use crate::dn::ParsedDn;
use crate::operation::{OperationSet, OperationType, NUM_CONCRETE_OPS};

pub(crate) struct AciIndexInfo<'a> {
    pub target_dn: Option<&'a str>,
    pub scope: crate::aci::Scope,
    pub op_set: OperationSet,
    pub grant: bool,
    pub include_attrs: Option<&'a [String]>,
    pub objectclass_filter: Option<&'a str>,
    pub userdn_bind: Option<&'a str>,
}

#[derive(Debug, Clone, Default)]
struct AttrPartitioned {
    general: Vec<usize>,
    by_attr: AHashMap<String, Vec<usize>>,
    by_objectclass: AHashMap<String, Vec<usize>>,
    by_userdn: AHashMap<String, Vec<usize>>,
}

#[derive(Clone, Copy)]
struct PartitionInsert<'a> {
    aci_idx: usize,
    attr_info: Option<&'a [String]>,
    objectclass_filter: Option<&'a str>,
    userdn_bind: Option<&'a str>,
}

impl AttrPartitioned {
    fn insert(&mut self, ins: PartitionInsert<'_>) {
        if let Some(oc) = ins.objectclass_filter {
            self.by_objectclass
                .entry(oc.to_lowercase())
                .or_default()
                .push(ins.aci_idx);
            return;
        }
        if let Some(dn) = ins.userdn_bind {
            self.by_userdn
                .entry(dn.to_lowercase())
                .or_default()
                .push(ins.aci_idx);
            return;
        }
        match ins.attr_info {
            None => self.general.push(ins.aci_idx),
            Some(attrs) => {
                for attr in attrs {
                    self.by_attr
                        .entry(attr.to_lowercase())
                        .or_default()
                        .push(ins.aci_idx);
                }
            }
        }
    }

    fn collect_into<'a>(
        &'a self,
        candidates: &mut CandidateSet<'a>,
        request_attrs: &[String],
        entry_objectclasses: &[String],
        user_dn: Option<&str>,
    ) {
        candidates.push_slice(&self.general);
        if request_attrs.is_empty() {
            for slot in self.by_attr.values() {
                candidates.push_slice(slot);
            }
        } else {
            for attr in request_attrs {
                if let Some(slot) = self.by_attr.get(attr.as_str()) {
                    candidates.push_slice(slot);
                }
            }
        }
        for oc in entry_objectclasses {
            if let Some(slot) = self.by_objectclass.get(oc.as_str()) {
                candidates.push_slice(slot);
            }
        }
        if let Some(dn) = user_dn {
            if let Some(slot) = self.by_userdn.get(dn) {
                candidates.push_slice(slot);
            }
        }
    }
}

#[derive(Debug, Clone, Default)]
struct DnTrieNode {
    subtree_grant_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    subtree_deny_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    onelevel_grant_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    onelevel_deny_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    base_grant_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    base_deny_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    children: AHashMap<String, DnTrieNode>,
}

struct TrieInsert<'a> {
    scope: crate::aci::Scope,
    aci_idx: usize,
    op_set: OperationSet,
    grant: bool,
    attr_info: Option<&'a [String]>,
    objectclass_filter: Option<&'a str>,
    userdn_bind: Option<&'a str>,
}

impl DnTrieNode {
    fn insert(&mut self, components: &[String], ins: TrieInsert<'_>) {
        if components.is_empty() {
            let bucket = match (ins.scope, ins.grant) {
                (crate::aci::Scope::Base, true) => &mut self.base_grant_by_op,
                (crate::aci::Scope::Base, false) => &mut self.base_deny_by_op,
                (crate::aci::Scope::OneLevel, true) => &mut self.onelevel_grant_by_op,
                (crate::aci::Scope::OneLevel, false) => &mut self.onelevel_deny_by_op,
                (crate::aci::Scope::Subtree, true) => &mut self.subtree_grant_by_op,
                (crate::aci::Scope::Subtree, false) => &mut self.subtree_deny_by_op,
            };
            let part_ins = PartitionInsert {
                aci_idx: ins.aci_idx,
                attr_info: ins.attr_info,
                objectclass_filter: ins.objectclass_filter,
                userdn_bind: ins.userdn_bind,
            };
            let bits = ins.op_set.raw_bits();
            for (pos, slot) in bucket.iter_mut().enumerate().take(NUM_CONCRETE_OPS) {
                if bits & (1 << pos) != 0 {
                    slot.insert(PartitionInsert { ..part_ins });
                }
            }
            if bits & (1 << OperationType::SelfWrite.bit_index().unwrap()) != 0 {
                let modify_idx = OperationType::Modify.bit_index().unwrap();
                if bits & (1 << modify_idx) == 0 {
                    bucket[modify_idx].insert(part_ins);
                }
            }
            return;
        }

        let child = self.children.entry(components[0].clone()).or_default();
        child.insert(&components[1..], ins);
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum CandidateFilter {
    All,
    DenyOnly,
    GrantOnly,
}

#[derive(Debug, Clone)]
pub(crate) struct DnScopeIndex {
    root: DnTrieNode,
    unrestricted_grant_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    unrestricted_deny_by_op: [AttrPartitioned; NUM_CONCRETE_OPS],
    wildcard: Vec<usize>,
}

const ATTR_PARTITION_THRESHOLD: usize = 5_000;

impl DnScopeIndex {
    /// Build the index from a list of ACIs.
    ///
    /// Each ACI is identified by its index in the provided slice.
    /// The `get_aci_info` closure extracts the target DN (Option), scope,
    /// operation set, and grant flag from each ACI.
    pub(crate) fn build<'a, F>(count: usize, get_aci_info: F) -> Self
    where
        F: Fn(usize) -> AciIndexInfo<'a>,
    {
        Self::build_inner(count, get_aci_info, count >= ATTR_PARTITION_THRESHOLD)
    }

    fn build_inner<'a, F>(count: usize, get_aci_info: F, use_partitioning: bool) -> Self
    where
        F: Fn(usize) -> AciIndexInfo<'a>,
    {
        let mut index = Self {
            root: DnTrieNode::default(),
            unrestricted_grant_by_op: Default::default(),
            unrestricted_deny_by_op: Default::default(),
            wildcard: Vec::new(),
        };

        for i in 0..count {
            let info = get_aci_info(i);
            let attr_info = if use_partitioning {
                info.include_attrs
            } else {
                None
            };
            let oc_filter = if use_partitioning {
                info.objectclass_filter
            } else {
                None
            };
            let ud_bind = if use_partitioning {
                info.userdn_bind
            } else {
                None
            };
            let part_ins = PartitionInsert {
                aci_idx: i,
                attr_info,
                objectclass_filter: oc_filter,
                userdn_bind: ud_bind,
            };
            match info.target_dn {
                None => {
                    let bucket = if info.grant {
                        &mut index.unrestricted_grant_by_op
                    } else {
                        &mut index.unrestricted_deny_by_op
                    };
                    let bits = info.op_set.raw_bits();
                    for (pos, slot) in bucket.iter_mut().enumerate().take(NUM_CONCRETE_OPS) {
                        if bits & (1 << pos) != 0 {
                            slot.insert(part_ins);
                        }
                    }
                    if bits & (1 << OperationType::SelfWrite.bit_index().unwrap()) != 0 {
                        let modify_idx = OperationType::Modify.bit_index().unwrap();
                        if bits & (1 << modify_idx) == 0 {
                            bucket[modify_idx].insert(part_ins);
                        }
                    }
                }
                Some(dn) if crate::dn::has_wildcard(dn) => {
                    index.wildcard.push(i);
                }
                Some(dn) => {
                    let parsed = ParsedDn::parse(dn);
                    index.root.insert(
                        &parsed.components,
                        TrieInsert {
                            scope: info.scope,
                            aci_idx: i,
                            op_set: info.op_set,
                            grant: info.grant,
                            attr_info,
                            objectclass_filter: oc_filter,
                            userdn_bind: ud_bind,
                        },
                    );
                }
            }
        }

        index
    }

    pub(crate) fn find_candidates(
        &self,
        query_dn: &str,
        op_type: OperationType,
        filter: CandidateFilter,
        request_attrs: &[String],
        entry_objectclasses: &[String],
        user_dn: Option<&str>,
    ) -> CandidateSet<'_> {
        let parsed = ParsedDn::parse(query_dn);
        let op_idx = op_type
            .bit_index()
            .expect("OperationType::All should not be used in find_candidates");
        let include_grants = filter != CandidateFilter::DenyOnly;
        let include_denies = filter != CandidateFilter::GrantOnly;
        let lowered_user_dn = user_dn.map(|u| u.to_lowercase());
        let lowered_ref = lowered_user_dn.as_deref();

        let mut candidates = CandidateSet::new();

        if include_grants {
            self.unrestricted_grant_by_op[op_idx].collect_into(
                &mut candidates,
                request_attrs,
                entry_objectclasses,
                lowered_ref,
            );
        }
        if include_denies {
            self.unrestricted_deny_by_op[op_idx].collect_into(
                &mut candidates,
                request_attrs,
                entry_objectclasses,
                lowered_ref,
            );
        }

        candidates.push_slice(&self.wildcard);

        let mut node = &self.root;

        if include_grants {
            node.subtree_grant_by_op[op_idx].collect_into(
                &mut candidates,
                request_attrs,
                entry_objectclasses,
                lowered_ref,
            );
        }
        if include_denies {
            node.subtree_deny_by_op[op_idx].collect_into(
                &mut candidates,
                request_attrs,
                entry_objectclasses,
                lowered_ref,
            );
        }

        for (depth, component) in parsed.components.iter().enumerate() {
            let is_last = depth == parsed.components.len() - 1;
            let is_penultimate = depth == parsed.components.len().saturating_sub(2);

            match node.children.get(component.as_str()) {
                Some(child) => {
                    if include_grants {
                        child.subtree_grant_by_op[op_idx].collect_into(
                            &mut candidates,
                            request_attrs,
                            entry_objectclasses,
                            lowered_ref,
                        );
                    }
                    if include_denies {
                        child.subtree_deny_by_op[op_idx].collect_into(
                            &mut candidates,
                            request_attrs,
                            entry_objectclasses,
                            lowered_ref,
                        );
                    }

                    if is_penultimate && !is_last {
                        if include_grants {
                            child.onelevel_grant_by_op[op_idx].collect_into(
                                &mut candidates,
                                request_attrs,
                                entry_objectclasses,
                                lowered_ref,
                            );
                        }
                        if include_denies {
                            child.onelevel_deny_by_op[op_idx].collect_into(
                                &mut candidates,
                                request_attrs,
                                entry_objectclasses,
                                lowered_ref,
                            );
                        }
                    }

                    if is_last {
                        if include_grants {
                            child.base_grant_by_op[op_idx].collect_into(
                                &mut candidates,
                                request_attrs,
                                entry_objectclasses,
                                lowered_ref,
                            );
                        }
                        if include_denies {
                            child.base_deny_by_op[op_idx].collect_into(
                                &mut candidates,
                                request_attrs,
                                entry_objectclasses,
                                lowered_ref,
                            );
                        }
                    }

                    node = child;
                }
                None => {
                    break;
                }
            }
        }

        candidates
    }

    pub(crate) fn find_candidates_split(
        &self,
        query_dn: &str,
        op_type: OperationType,
        request_attrs: &[String],
        entry_objectclasses: &[String],
        user_dn: Option<&str>,
    ) -> (CandidateSet<'_>, CandidateSet<'_>) {
        let parsed = ParsedDn::parse(query_dn);
        let op_idx = op_type
            .bit_index()
            .expect("OperationType::All should not be used in find_candidates_split");
        let lowered_user_dn = user_dn.map(|u| u.to_lowercase());
        let lowered_ref = lowered_user_dn.as_deref();

        let mut grants = CandidateSet::new();
        let mut denies = CandidateSet::new();

        self.unrestricted_grant_by_op[op_idx].collect_into(
            &mut grants,
            request_attrs,
            entry_objectclasses,
            lowered_ref,
        );
        self.unrestricted_deny_by_op[op_idx].collect_into(
            &mut denies,
            request_attrs,
            entry_objectclasses,
            lowered_ref,
        );

        grants.push_slice(&self.wildcard);
        denies.push_slice(&self.wildcard);

        let mut node = &self.root;
        node.subtree_grant_by_op[op_idx].collect_into(
            &mut grants,
            request_attrs,
            entry_objectclasses,
            lowered_ref,
        );
        node.subtree_deny_by_op[op_idx].collect_into(
            &mut denies,
            request_attrs,
            entry_objectclasses,
            lowered_ref,
        );

        for (depth, component) in parsed.components.iter().enumerate() {
            let is_last = depth == parsed.components.len() - 1;
            let is_penultimate = depth == parsed.components.len().saturating_sub(2);

            match node.children.get(component.as_str()) {
                Some(child) => {
                    child.subtree_grant_by_op[op_idx].collect_into(
                        &mut grants,
                        request_attrs,
                        entry_objectclasses,
                        lowered_ref,
                    );
                    child.subtree_deny_by_op[op_idx].collect_into(
                        &mut denies,
                        request_attrs,
                        entry_objectclasses,
                        lowered_ref,
                    );

                    if is_penultimate && !is_last {
                        child.onelevel_grant_by_op[op_idx].collect_into(
                            &mut grants,
                            request_attrs,
                            entry_objectclasses,
                            lowered_ref,
                        );
                        child.onelevel_deny_by_op[op_idx].collect_into(
                            &mut denies,
                            request_attrs,
                            entry_objectclasses,
                            lowered_ref,
                        );
                    }

                    if is_last {
                        child.base_grant_by_op[op_idx].collect_into(
                            &mut grants,
                            request_attrs,
                            entry_objectclasses,
                            lowered_ref,
                        );
                        child.base_deny_by_op[op_idx].collect_into(
                            &mut denies,
                            request_attrs,
                            entry_objectclasses,
                            lowered_ref,
                        );
                    }

                    node = child;
                }
                None => {
                    break;
                }
            }
        }

        (grants, denies)
    }
}

/// Zero-copy set of candidate ACI indices returned by the DN index.
///
/// Holds references to slices within the trie nodes rather than copying
/// indices into a new Vec. Typically 9-16 slice references (~144-256 bytes
/// on the stack) instead of tens of thousands of copied indices.
#[derive(Debug)]
pub(crate) struct CandidateSet<'a> {
    slices: SmallVec<[&'a [usize]; 16]>,
}

impl<'a> CandidateSet<'a> {
    fn new() -> Self {
        Self {
            slices: SmallVec::new(),
        }
    }

    fn push_slice(&mut self, slice: &'a [usize]) {
        if !slice.is_empty() {
            self.slices.push(slice);
        }
    }

    /// Iterate over all candidate indices.
    #[inline]
    pub(crate) fn iter(&self) -> SliceChainIter<'_> {
        SliceChainIter {
            slices: &self.slices,
            slice_idx: 0,
            elem_idx: 0,
        }
    }
}

pub(crate) struct SliceChainIter<'a> {
    slices: &'a [&'a [usize]],
    slice_idx: usize,
    elem_idx: usize,
}

impl Iterator for SliceChainIter<'_> {
    type Item = usize;

    #[inline]
    fn next(&mut self) -> Option<usize> {
        loop {
            let slice = self.slices.get(self.slice_idx)?;
            if let Some(&val) = slice.get(self.elem_idx) {
                self.elem_idx += 1;
                return Some(val);
            }
            self.slice_idx += 1;
            self.elem_idx = 0;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::aci::Scope;

    fn all_ops() -> OperationSet {
        OperationSet::all()
    }

    fn info<'a>(
        target_dn: Option<&'a str>,
        scope: Scope,
        op_set: OperationSet,
        grant: bool,
        include_attrs: Option<&'a [String]>,
    ) -> AciIndexInfo<'a> {
        AciIndexInfo {
            target_dn,
            scope,
            op_set,
            grant,
            include_attrs,
            objectclass_filter: None,
            userdn_bind: None,
        }
    }

    #[test]
    fn unrestricted_aci_always_candidate() {
        let index = DnScopeIndex::build(1, |_| info(None, Scope::Subtree, all_ops(), true, None));
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn subtree_at_ancestor_matches() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("ou=people,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn subtree_at_exact_matches() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("uid=alice,ou=people,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn subtree_at_child_does_not_match_parent() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("uid=alice,ou=people,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(!candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn base_at_exact_matches() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("uid=alice,ou=people,dc=example,dc=com"),
                Scope::Base,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn base_does_not_match_child() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("ou=people,dc=example,dc=com"),
                Scope::Base,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(!candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn onelevel_at_parent_matches_child() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("ou=people,dc=example,dc=com"),
                Scope::OneLevel,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn onelevel_does_not_match_grandchild() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("dc=example,dc=com"),
                Scope::OneLevel,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(!candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn onelevel_does_not_match_self() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("ou=people,dc=example,dc=com"),
                Scope::OneLevel,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(!candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn different_subtree_not_candidate() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("ou=groups,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(!candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn multiple_acis_mixed_scopes() {
        let acis: Vec<(Option<&str>, Scope, OperationSet, bool)> = vec![
            (None, Scope::Subtree, all_ops(), true), // 0: unrestricted grant
            (
                Some("ou=people,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                true,
            ), // 1: subtree at people
            (
                Some("ou=people,dc=example,dc=com"),
                Scope::OneLevel,
                all_ops(),
                true,
            ), // 2: onelevel at people
            (
                Some("ou=groups,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                true,
            ), // 3: subtree at groups
            (
                Some("uid=alice,ou=people,dc=example,dc=com"),
                Scope::Base,
                all_ops(),
                true,
            ), // 4: base at alice
        ];
        let index = DnScopeIndex::build(acis.len(), |i| {
            info(acis[i].0, acis[i].1, acis[i].2, acis[i].3, None)
        });

        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        let indices: Vec<usize> = candidates.iter().collect();

        assert!(indices.contains(&0), "unrestricted should match");
        assert!(indices.contains(&1), "subtree at people should match");
        assert!(indices.contains(&2), "onelevel at people should match");
        assert!(!indices.contains(&3), "subtree at groups should NOT match");
        assert!(indices.contains(&4), "base at alice should match");
    }

    #[test]
    fn wildcard_acis_always_included() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("uid=*,ou=people,dc=example,dc=com"),
                Scope::Base,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn case_insensitive() {
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("OU=People,DC=Example,DC=Com"),
                Scope::Subtree,
                all_ops(),
                true,
                None,
            )
        });
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(candidates.iter().any(|i| i == 0));
    }

    #[test]
    fn empty_index() {
        let index = DnScopeIndex::build(0, |_| unreachable!());
        let candidates = index.find_candidates(
            "dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert_eq!(candidates.iter().count(), 0);
    }

    #[test]
    fn unrestricted_op_partitioning() {
        let read_ops = OperationSet::from(OperationType::Read);
        let modify_ops = OperationSet::from(OperationType::Modify);
        let index = DnScopeIndex::build(2, |i| match i {
            0 => info(None, Scope::Subtree, read_ops, true, None),
            1 => info(None, Scope::Subtree, modify_ops, true, None),
            _ => unreachable!(),
        });

        let read_candidates = index.find_candidates(
            "dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        let modify_candidates = index.find_candidates(
            "dc=example,dc=com",
            OperationType::Modify,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );

        assert!(
            read_candidates.iter().any(|i| i == 0),
            "read ACI in read candidates"
        );
        assert!(
            !read_candidates.iter().any(|i| i == 1),
            "modify ACI not in read candidates"
        );
        assert!(
            !modify_candidates.iter().any(|i| i == 0),
            "read ACI not in modify candidates"
        );
        assert!(
            modify_candidates.iter().any(|i| i == 1),
            "modify ACI in modify candidates"
        );
    }

    #[test]
    fn selfwrite_subsumes_modify_in_unrestricted() {
        let selfwrite_ops = OperationSet::from(OperationType::SelfWrite);
        let index =
            DnScopeIndex::build(1, |_| info(None, Scope::Subtree, selfwrite_ops, true, None));

        let modify_candidates = index.find_candidates(
            "dc=example,dc=com",
            OperationType::Modify,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(
            modify_candidates.iter().any(|i| i == 0),
            "SelfWrite ACI appears in Modify candidates"
        );

        let selfwrite_candidates = index.find_candidates(
            "dc=example,dc=com",
            OperationType::SelfWrite,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(
            selfwrite_candidates.iter().any(|i| i == 0),
            "SelfWrite ACI appears in SelfWrite candidates"
        );

        let read_candidates = index.find_candidates(
            "dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(
            !read_candidates.iter().any(|i| i == 0),
            "SelfWrite ACI not in Read candidates"
        );
    }

    #[test]
    fn deny_only_excludes_grants() {
        let index = DnScopeIndex::build(3, |i| match i {
            0 => info(None, Scope::Subtree, all_ops(), true, None), // unrestricted grant
            1 => info(None, Scope::Subtree, all_ops(), false, None), // unrestricted deny
            2 => info(
                Some("ou=people,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                true,
                None,
            ), // trie grant
            _ => unreachable!(),
        });

        let all = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        let deny = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::DenyOnly,
            &[],
            &[],
            None,
        );

        assert_eq!(all.iter().count(), 3, "all mode returns grants + denies");
        assert_eq!(deny.iter().count(), 1, "deny_only returns only denies");
        assert!(
            deny.iter().any(|i| i == 1),
            "deny_only includes the deny ACI"
        );
    }

    #[test]
    fn trie_op_partitioning() {
        let read_ops = OperationSet::from(OperationType::Read);
        let modify_ops = OperationSet::from(OperationType::Modify);
        let index = DnScopeIndex::build(2, |i| match i {
            0 => info(
                Some("ou=people,dc=example,dc=com"),
                Scope::Subtree,
                read_ops,
                true,
                None,
            ),
            1 => info(
                Some("ou=people,dc=example,dc=com"),
                Scope::Subtree,
                modify_ops,
                true,
                None,
            ),
            _ => unreachable!(),
        });

        let read = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        let modify = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Modify,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );

        assert!(read.iter().any(|i| i == 0), "read ACI in read candidates");
        assert!(
            !read.iter().any(|i| i == 1),
            "modify ACI not in read candidates"
        );
        assert!(
            !modify.iter().any(|i| i == 0),
            "read ACI not in modify candidates"
        );
        assert!(
            modify.iter().any(|i| i == 1),
            "modify ACI in modify candidates"
        );
    }

    #[test]
    fn selfwrite_subsumes_modify_in_trie() {
        let selfwrite_ops = OperationSet::from(OperationType::SelfWrite);
        let index = DnScopeIndex::build(1, |_| {
            info(
                Some("ou=people,dc=example,dc=com"),
                Scope::OneLevel,
                selfwrite_ops,
                true,
                None,
            )
        });

        let modify = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Modify,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(
            modify.iter().any(|i| i == 0),
            "SelfWrite ACI appears in Modify candidates via trie"
        );

        let selfwrite = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::SelfWrite,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(
            selfwrite.iter().any(|i| i == 0),
            "SelfWrite ACI in SelfWrite candidates"
        );

        let read = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert!(
            !read.iter().any(|i| i == 0),
            "SelfWrite ACI not in Read candidates"
        );
    }

    #[test]
    fn grant_only_excludes_denies() {
        let index = DnScopeIndex::build(3, |i| match i {
            0 => info(None, Scope::Subtree, all_ops(), true, None),
            1 => info(None, Scope::Subtree, all_ops(), false, None),
            2 => info(
                Some("ou=people,dc=example,dc=com"),
                Scope::Subtree,
                all_ops(),
                false,
                None,
            ),
            _ => unreachable!(),
        });

        let grants = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::GrantOnly,
            &[],
            &[],
            None,
        );
        assert_eq!(grants.iter().count(), 1, "grant_only returns only grants");
        assert!(
            grants.iter().any(|i| i == 0),
            "grant_only includes the grant ACI"
        );
    }

    // --- Attribute pre-filtering tests ---

    #[test]
    fn attr_prefilter_include_skips_non_matching() {
        let password_attrs = vec!["userpassword".to_string()];
        let index = DnScopeIndex::build_inner(
            1,
            |_| {
                info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    false,
                    Some(password_attrs.as_slice()),
                )
            },
            true,
        );
        let cn_attr = vec!["cn".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &cn_attr,
            &[],
            None,
        );
        assert_eq!(
            candidates.iter().count(),
            0,
            "Include(userpassword) not returned for cn request"
        );
    }

    #[test]
    fn attr_prefilter_include_matches() {
        let password_attrs = vec!["userpassword".to_string()];
        let index = DnScopeIndex::build_inner(
            1,
            |_| {
                info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    false,
                    Some(password_attrs.as_slice()),
                )
            },
            true,
        );
        let pw_attr = vec!["userpassword".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &pw_attr,
            &[],
            None,
        );
        assert!(
            candidates.iter().any(|i| i == 0),
            "Include(userpassword) returned for userpassword request"
        );
    }

    #[test]
    fn attr_prefilter_empty_request_returns_all() {
        let password_attrs = vec!["userpassword".to_string()];
        let index = DnScopeIndex::build_inner(
            2,
            |i| match i {
                0 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    true,
                    None,
                ),
                1 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    false,
                    Some(password_attrs.as_slice()),
                ),
                _ => unreachable!(),
            },
            true,
        );
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        let indices: Vec<usize> = candidates.iter().collect();
        assert!(indices.contains(&0), "general ACI returned");
        assert!(
            indices.contains(&1),
            "Include ACI returned when request_attrs empty"
        );
    }

    #[test]
    fn attr_prefilter_general_always_included() {
        let password_attrs = vec!["userpassword".to_string()];
        let index = DnScopeIndex::build_inner(
            2,
            |i| match i {
                0 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    true,
                    None,
                ),
                1 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    false,
                    Some(password_attrs.as_slice()),
                ),
                _ => unreachable!(),
            },
            true,
        );
        let cn_attr = vec!["cn".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &cn_attr,
            &[],
            None,
        );
        let indices: Vec<usize> = candidates.iter().collect();
        assert!(
            indices.contains(&0),
            "general (All/Exclude) ACI always included"
        );
        assert!(
            !indices.contains(&1),
            "Include(userpassword) excluded for cn request"
        );
    }

    #[test]
    fn attr_prefilter_case_insensitive() {
        let mixed_case_attrs = vec!["UserPassword".to_string()];
        let index = DnScopeIndex::build_inner(
            1,
            |_| {
                info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    false,
                    Some(mixed_case_attrs.as_slice()),
                )
            },
            true,
        );
        let lower_attr = vec!["userpassword".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &lower_attr,
            &[],
            None,
        );
        assert!(
            candidates.iter().any(|i| i == 0),
            "case-insensitive attr match"
        );
    }

    #[test]
    fn attr_prefilter_unrestricted() {
        let password_attrs = vec!["userpassword".to_string()];
        let index = DnScopeIndex::build_inner(
            2,
            |i| match i {
                0 => info(None, Scope::Subtree, all_ops(), true, None),
                1 => info(
                    None,
                    Scope::Subtree,
                    all_ops(),
                    false,
                    Some(password_attrs.as_slice()),
                ),
                _ => unreachable!(),
            },
            true,
        );
        let cn_attr = vec!["cn".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &cn_attr,
            &[],
            None,
        );
        let indices: Vec<usize> = candidates.iter().collect();
        assert!(indices.contains(&0), "unrestricted general always included");
        assert!(
            !indices.contains(&1),
            "unrestricted Include(userpassword) excluded for cn"
        );
    }

    #[test]
    fn attr_prefilter_split() {
        let password_attrs = vec!["userpassword".to_string()];
        let index = DnScopeIndex::build_inner(
            3,
            |i| match i {
                0 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    true,
                    None,
                ),
                1 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    false,
                    Some(password_attrs.as_slice()),
                ),
                2 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    false,
                    None,
                ),
                _ => unreachable!(),
            },
            true,
        );
        let cn_attr = vec!["cn".to_string()];
        let (grants, denies) = index.find_candidates_split(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            &cn_attr,
            &[],
            None,
        );
        let grant_indices: Vec<usize> = grants.iter().collect();
        let deny_indices: Vec<usize> = denies.iter().collect();
        assert!(grant_indices.contains(&0), "grant returned");
        assert!(
            !deny_indices.contains(&1),
            "Include(userpassword) deny excluded for cn"
        );
        assert!(deny_indices.contains(&2), "general deny included");
    }

    // --- ObjectClass pre-filtering tests ---

    #[test]
    fn objectclass_prefilter_skips_non_matching() {
        let index = DnScopeIndex::build_inner(
            1,
            |_| AciIndexInfo {
                target_dn: Some("ou=people,dc=example,dc=com"),
                scope: Scope::Subtree,
                op_set: all_ops(),
                grant: true,
                include_attrs: None,
                objectclass_filter: Some("person"),
                userdn_bind: None,
            },
            true,
        );
        let ocs = vec!["groupofnames".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &ocs,
            None,
        );
        assert_eq!(
            candidates.iter().count(),
            0,
            "ObjectClass(person) not returned for groupofnames entry"
        );
    }

    #[test]
    fn objectclass_prefilter_matches() {
        let index = DnScopeIndex::build_inner(
            1,
            |_| AciIndexInfo {
                target_dn: Some("ou=people,dc=example,dc=com"),
                scope: Scope::Subtree,
                op_set: all_ops(),
                grant: true,
                include_attrs: None,
                objectclass_filter: Some("person"),
                userdn_bind: None,
            },
            true,
        );
        let ocs = vec!["person".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &ocs,
            None,
        );
        assert!(
            candidates.iter().any(|i| i == 0),
            "ObjectClass(person) returned for person entry"
        );
    }

    #[test]
    fn objectclass_prefilter_empty_entry_skips() {
        let index = DnScopeIndex::build_inner(
            1,
            |_| AciIndexInfo {
                target_dn: Some("ou=people,dc=example,dc=com"),
                scope: Scope::Subtree,
                op_set: all_ops(),
                grant: true,
                include_attrs: None,
                objectclass_filter: Some("person"),
                userdn_bind: None,
            },
            true,
        );
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert_eq!(
            candidates.iter().count(),
            0,
            "ObjectClass ACI skipped when entry has no objectclasses"
        );
    }

    #[test]
    fn objectclass_prefilter_general_unaffected() {
        let index = DnScopeIndex::build_inner(
            2,
            |i| match i {
                0 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    true,
                    None,
                ),
                1 => AciIndexInfo {
                    target_dn: Some("ou=people,dc=example,dc=com"),
                    scope: Scope::Subtree,
                    op_set: all_ops(),
                    grant: true,
                    include_attrs: None,
                    objectclass_filter: Some("person"),
                    userdn_bind: None,
                },
                _ => unreachable!(),
            },
            true,
        );
        let ocs = vec!["groupofnames".to_string()];
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &ocs,
            None,
        );
        let indices: Vec<usize> = candidates.iter().collect();
        assert!(indices.contains(&0), "general ACI always returned");
        assert!(
            !indices.contains(&1),
            "ObjectClass(person) not returned for groupofnames entry"
        );
    }

    // --- UserDn pre-filtering tests ---

    #[test]
    fn userdn_prefilter_skips_non_matching() {
        let index = DnScopeIndex::build_inner(
            1,
            |_| AciIndexInfo {
                target_dn: Some("ou=people,dc=example,dc=com"),
                scope: Scope::Subtree,
                op_set: all_ops(),
                grant: true,
                include_attrs: None,
                objectclass_filter: None,
                userdn_bind: Some("uid=bob,ou=people,dc=example,dc=com"),
            },
            true,
        );
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            Some("uid=alice,ou=people,dc=example,dc=com"),
        );
        assert_eq!(
            candidates.iter().count(),
            0,
            "UserDn(bob) not returned for alice"
        );
    }

    #[test]
    fn userdn_prefilter_matches() {
        let index = DnScopeIndex::build_inner(
            1,
            |_| AciIndexInfo {
                target_dn: Some("ou=people,dc=example,dc=com"),
                scope: Scope::Subtree,
                op_set: all_ops(),
                grant: true,
                include_attrs: None,
                objectclass_filter: None,
                userdn_bind: Some("uid=alice,ou=people,dc=example,dc=com"),
            },
            true,
        );
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            Some("uid=alice,ou=people,dc=example,dc=com"),
        );
        assert!(
            candidates.iter().any(|i| i == 0),
            "UserDn(alice) returned for alice"
        );
    }

    #[test]
    fn userdn_prefilter_no_user_skips() {
        let index = DnScopeIndex::build_inner(
            1,
            |_| AciIndexInfo {
                target_dn: Some("ou=people,dc=example,dc=com"),
                scope: Scope::Subtree,
                op_set: all_ops(),
                grant: true,
                include_attrs: None,
                objectclass_filter: None,
                userdn_bind: Some("uid=alice,ou=people,dc=example,dc=com"),
            },
            true,
        );
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            None,
        );
        assert_eq!(
            candidates.iter().count(),
            0,
            "UserDn ACIs skipped when user_dn is None"
        );
    }

    #[test]
    fn userdn_prefilter_general_unaffected() {
        let index = DnScopeIndex::build_inner(
            2,
            |i| match i {
                0 => info(
                    Some("ou=people,dc=example,dc=com"),
                    Scope::Subtree,
                    all_ops(),
                    true,
                    None,
                ),
                1 => AciIndexInfo {
                    target_dn: Some("ou=people,dc=example,dc=com"),
                    scope: Scope::Subtree,
                    op_set: all_ops(),
                    grant: true,
                    include_attrs: None,
                    objectclass_filter: None,
                    userdn_bind: Some("uid=bob,ou=people,dc=example,dc=com"),
                },
                _ => unreachable!(),
            },
            true,
        );
        let candidates = index.find_candidates(
            "uid=alice,ou=people,dc=example,dc=com",
            OperationType::Read,
            CandidateFilter::All,
            &[],
            &[],
            Some("uid=alice,ou=people,dc=example,dc=com"),
        );
        let indices: Vec<usize> = candidates.iter().collect();
        assert!(indices.contains(&0), "general ACI always returned");
        assert!(!indices.contains(&1), "UserDn(bob) not returned for alice");
    }
}