psmatcher 0.4.0-alpha.0

// Copyright (c) Subzero Labs, Inc.
// SPDX-License-Identifier: Apache-2.0

use crate::{
    collections::HashSet,
    error::MatcherError,
    event::Event,
    subscription::{Subscription, SubscriptionKey},
    tree::MatchingTree,
};

/// The main matcher API for pub/sub matching
///
/// This implementation is based on the tree-based algorithm described in:
///
/// Marcos K. Aguilera, Robert E. Strom, Daniel C. Sturman, Mark Astley, and Tushar D. Chandra. 1999.
/// Matching events in a content-based subscription system. In Proceedings of the eighteenth annual
/// ACM symposium on Principles of distributed computing (PODC '99). Association for Computing Machinery,
/// New York, NY, USA, 53–61. <https://doi.org/10.1145/301308.301326>
///
/// ## Algorithm Overview
///
/// The algorithm uses a tree-based approach to efficiently match events against subscriptions:
///
/// 1. **Pre-processing**: Subscriptions are organized into a matching tree during the addition phase.
///    Each node in the tree represents a predicate test, with branches for both positive and negative
///    evaluation results.
///
/// 2. **Tree Structure**: The tree is structured such that common predicates among subscriptions are
///    shared, reducing the total number of predicate evaluations needed during matching.
///
/// 3. **Matching Process**: When an event arrives, the algorithm traverses the tree, evaluating
///    predicates at each node and following the appropriate branches based on the results.
///    Subscriptions stored at the reached leaf nodes are potential matches.
///
/// 4. **Final Verification**: To ensure correctness, the algorithm performs a final verification step
///    where each potential match is checked to confirm that all its predicates are satisfied by the event.
///
/// This approach significantly reduces the computational complexity of matching events against
/// a large number of subscriptions, especially when subscriptions share common predicates.
#[derive(Debug, Clone)]
pub struct Matcher<T: SubscriptionKey> {
    /// The matching tree used for efficient event matching
    tree: MatchingTree<T>,
}

impl<T: SubscriptionKey> Matcher<T> {
    /// Creates a new matcher
    pub fn new() -> Self {
        Self {
            tree: MatchingTree::new(),
        }
    }

    /// Adds a subscription to the matcher
    ///
    /// The subscription is processed and integrated into the matching tree structure.
    /// This operation may reorganize the tree for optimal matching performance.
    pub fn add_subscription(&mut self, subscription: Subscription<T>) {
        self.tree.add_subscription(subscription)
    }

    /// Removes a subscription from the matcher
    ///
    /// The subscription is removed from all nodes in the matching tree.
    pub fn remove_subscription(&mut self, subscription_id: &T) -> Result<(), MatcherError> {
        self.tree.remove_subscription(subscription_id)
    }

    /// Matches an event against all subscriptions and returns the IDs of matching subscriptions
    ///
    /// This method traverses the matching tree, evaluating predicates at each node and following
    /// the appropriate branches based on the results. The final set of matching subscriptions
    /// is verified to ensure all predicates are satisfied.
    pub fn match_event(&self, event: &impl Event) -> Result<HashSet<T>, MatcherError> {
        self.tree.match_event(event)
    }

    /// Returns the number of subscriptions in the matcher
    pub fn subscription_count(&self) -> usize {
        self.tree.subscriptions.len()
    }

    /// Returns a reference to the underlying matching tree
    pub fn tree(&self) -> &MatchingTree<T> {
        &self.tree
    }

    /// Returns a mutable reference to the underlying matching tree
    pub fn tree_mut(&mut self) -> &mut MatchingTree<T> {
        &mut self.tree
    }

    /// Optimizes the matching tree for more efficient matching
    ///
    /// This method reorganizes the tree structure to improve matching performance.
    /// It may reorder predicates based on selectivity, merge nodes with the same predicate,
    /// remove redundant nodes, and balance the tree.
    pub fn optimize(&mut self) -> Result<(), MatcherError> {
        self.tree.optimize()
    }

    /// Returns a list of all subscription IDs
    pub fn subscription_ids(&self) -> Vec<T> {
        self.tree.subscriptions.keys().cloned().collect()
    }

    /// Returns a reference to a subscription by ID
    pub fn get_subscription(&self, subscription_id: &T) -> Option<&Subscription<T>> {
        self.tree.subscriptions.get(subscription_id)
    }

    #[cfg(feature = "testing")]
    pub fn get_subscriptions_for_testing(
        &self,
    ) -> &crate::collections::HashMap<T, Subscription<T>> {
        &self.tree.subscriptions
    }
}

impl<T: SubscriptionKey> Default for Matcher<T> {
    fn default() -> Self {
        Self::new()
    }
}