Trait 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.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors