Trait oxidd_core::function::Function

pub unsafe trait Function: Clone + Ord + Hash {
    type Manager<'id>: Manager;
    type ManagerRef: for<'id> ManagerRef<Manager<'id> = Self::Manager<'id>>;

    // Required methods
    fn from_edge<'id>(
        manager: &Self::Manager<'id>,
        edge: EdgeOfFunc<'id, Self>,
    ) -> Self;
    fn as_edge<'id>(
        &self,
        manager: &Self::Manager<'id>,
    ) -> &EdgeOfFunc<'id, Self>;
    fn into_edge<'id>(
        self,
        manager: &Self::Manager<'id>,
    ) -> EdgeOfFunc<'id, Self>;
    fn manager_ref(&self) -> Self::ManagerRef;
    fn with_manager_shared<F, T>(&self, f: F) -> T
       where F: for<'id> FnOnce(&Self::Manager<'id>, &EdgeOfFunc<'id, Self>) -> T;
    fn with_manager_exclusive<F, T>(&self, f: F) -> T
       where F: for<'id> FnOnce(&mut Self::Manager<'id>, &EdgeOfFunc<'id, Self>) -> T;

    // Provided methods
    fn from_edge_ref<'id>(
        manager: &Self::Manager<'id>,
        edge: &EdgeOfFunc<'id, Self>,
    ) -> Self { ... }
    fn node_count(&self) -> usize { ... }
}

Function in a decision diagram

A function is some kind of external reference to a node as opposed to Edges, which are diagram internal. A function also includes a reference to the diagram’s manager. So one may view a function as an Edge plus a ManagerRef.

Functions are what the library’s user mostly works with. There may be subtraits such as BooleanFunction in the oxidd-rules-bdd crate which provide more functionality, in this case applying connectives of boolean logic to other functions.

For some methods of this trait, there are notes on locking behavior. In a concurrent setting, a manager has some kind of read/write lock, and Self::with_manager_shared() / Self::with_manager_exclusive() acquire this lock accordingly. In a sequential implementation, a RefCell or the like may be used instead of lock.

Safety

An implementation must ensure that the “Edge part” of the function points to a node that is stored in the manager referenced by the “ManagerRef part” of the function. All functions of this trait must maintain this link accordingly. In particular, Self::as_edge() and Self::into_edge() must panic as specified there.

Required Associated Types

type Manager<'id>: Manager

Type of the associated manager

This type is generic over a lifetime 'id to permit the “lifetime trick” used, e.g., in GhostCell: The idea is to make the Manager, Edge and InnerNode types invariant over 'id. Any call to one of the with_manager_shared() / with_manager_exclusive() functions of the Function or ManagerRef trait, which “generate” a fresh lifetime 'id. Now the type system ensures that every edge or node with 'id comes belongs to the manager from the with_manager_*() call. This means that we can reduce the amount of runtime checks needed to uphold the invariant that the children of a node stored in Manager M are stored in M as well.

Note that Function and ManagerRef are (typically) outside the scope of this lifetime trick to make the library more flexible.

type ManagerRef: for<'id> ManagerRef<Manager<'id> = Self::Manager<'id>>

Manager references for Self::Manager

Required Methods

fn from_edge<'id>( manager: &Self::Manager<'id>, edge: EdgeOfFunc<'id, Self>, ) -> Self

Create a new function from a manager reference and an edge

fn as_edge<'id>(&self, manager: &Self::Manager<'id>) -> &EdgeOfFunc<'id, Self>

Converts this function into the underlying edge (as reference), checking that it belongs to the given manager

Panics if the function does not belong to manager.

fn into_edge<'id>(self, manager: &Self::Manager<'id>) -> EdgeOfFunc<'id, Self>

Converts this function into the underlying edge, checking that it belongs to the given manager

Panics if the function does not belong to manager.

fn manager_ref(&self) -> Self::ManagerRef

Clone the ManagerRef part

fn with_manager_shared<F, T>(&self, f: F) -> T

where F: for<'id> FnOnce(&Self::Manager<'id>, &EdgeOfFunc<'id, Self>) -> T,

Obtain a shared manager reference as well as the underlying edge

Locking behavior: acquires the manager’s lock for shared access.

Example

fn my_eq<F: Function>(f: &F, g: &F) -> bool {
    f.with_manager_shared(|manager, f_edge| {
        // Do something meaningful with `manager` and `edge` (the following
        // is better done using `f == g` without `with_manager_shared()`)
        let g_edge = g.as_edge(manager);
        f_edge == g_edge
    })
}

fn with_manager_exclusive<F, T>(&self, f: F) -> T

where F: for<'id> FnOnce(&mut Self::Manager<'id>, &EdgeOfFunc<'id, Self>) -> T,

Obtain an exclusive manager reference as well as the underlying edge

Locking behavior: acquires the manager’s lock for exclusive access.

Example

/// Adds a binary node on a new level with children `f` and `g`
fn foo<F: Function>(f: &F, g: &F) -> AllocResult<F> {
    f.with_manager_exclusive(|manager, f_edge| {
        let fe = manager.clone_edge(f_edge);
        let ge = manager.clone_edge(g.as_edge(manager));
        let he = manager.add_level(|level| InnerNode::new(level, [fe, ge]))?;
        Ok(F::from_edge(manager, he))
    })
}

Provided Methods

fn from_edge_ref<'id>( manager: &Self::Manager<'id>, edge: &EdgeOfFunc<'id, Self>, ) -> Self

Create a new function from a manager reference and an edge reference

fn node_count(&self) -> usize

Count the number of nodes in this function, including terminal nodes

Locking behavior: acquires the manager’s lock for shared access.

Object Safety

This trait is not object safe.

Implementors