Trait Manager 

pub unsafe trait Manager: Sized {
    type Edge: Edge<Tag = Self::EdgeTag>;
    type EdgeTag: Tag;
    type InnerNode: InnerNode<Self::Edge>;
    type Terminal: Eq + Hash;
    type TerminalRef<'a>: Borrow<Self::Terminal> + Copy
       where Self: 'a;
    type Rules: DiagramRules<Self::Edge, Self::InnerNode, Self::Terminal>;
    type TerminalIterator<'a>: Iterator<Item = Self::Edge>
       where Self: 'a;
    type NodeSet: NodeSet<Self::Edge>;
    type LevelView<'a>: LevelView<Self::Edge, Self::InnerNode>
       where Self: 'a;
    type LevelIterator<'a>: DoubleEndedIterator<Item = Self::LevelView<'a>> + ExactSizeIterator
       where Self: 'a;

    // Required methods
    fn get_node(&self, edge: &Self::Edge) -> Node<'_, Self>;
    fn clone_edge(&self, edge: &Self::Edge) -> Self::Edge;
    fn drop_edge(&self, edge: Self::Edge);
    fn try_remove_node(&self, edge: Self::Edge, level: LevelNo) -> bool;
    fn num_inner_nodes(&self) -> usize;
    fn num_levels(&self) -> LevelNo;
    fn num_named_vars(&self) -> VarNo;
    fn add_vars(&mut self, additional: VarNo) -> Range<VarNo>;
    fn add_named_vars<S: Into<String>>(
        &mut self,
        names: impl IntoIterator<Item = S>,
    ) -> Result<Range<VarNo>, DuplicateVarName>;
    fn var_name(&self, var: VarNo) -> &str;
    fn set_var_name(
        &mut self,
        var: VarNo,
        name: impl Into<String>,
    ) -> Result<(), DuplicateVarName>;
    fn name_to_var(&self, name: impl AsRef<str>) -> Option<VarNo>;
    fn var_to_level(&self, var: VarNo) -> LevelNo;
    fn level_to_var(&self, level: LevelNo) -> VarNo;
    fn level(&self, no: LevelNo) -> Self::LevelView<'_>;
    fn levels(&self) -> Self::LevelIterator<'_>;
    fn get_terminal(&self, terminal: Self::Terminal) -> AllocResult<Self::Edge>;
    fn num_terminals(&self) -> usize;
    fn terminals(&self) -> Self::TerminalIterator<'_>;
    fn gc(&self) -> usize;
    fn reorder<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T;
    fn gc_count(&self) -> u64;
    fn reorder_count(&self) -> u64;

    // Provided methods
    fn approx_num_inner_nodes(&self) -> usize { ... }
    fn num_vars(&self) -> VarNo { ... }
    fn add_named_vars_from_map(
        &mut self,
        map: VarNameMap,
    ) -> Result<Range<VarNo>, DuplicateVarName> { ... }
}

Manager for nodes in a decision diagram

In the basic formulation, a decision diagram is a directed acyclic graph where all inner nodes are associated with a level, and each level in turn is associated with a variable. A decision diagram can represent functions Dⁿ → T, where n is the number of variables. Every inner node has |D| outgoing edges, pointing to child nodes. The semantics of an inner node depends on the value of its associated variable. If the variable has value d ∈ D, then the node’s semantics is the semantics of the child referenced by the edge corresponding to d. Every terminal node is associated with a value t ∈ T, and the node’s semantics is just that value t. Some kinds of decision diagrams deviate from this formulation in one way or the other, but still fit into the framework.

The manager’s responsibility is to store nodes and provide edges to identify them. Internally, it has a unique table to ensure uniqueness of nodes (typically, there should be no two nodes with the same children at the same level). The manager supports some kind of garbage collection: If there are no more edges pointing to a node, the node does not necessarily have to be deleted immediately. It may well be that the node revives. But from time to time it may make sense to remove all currently dead nodes. The manager also supports a levelized view on the diagram (via LevelViews).

Note that we are way more concerned about levels than about variables here. This is because variables can easily be handled externally. For many kinds of diagrams, we can just use the function representation of a variable and get the mapping between variables and levels “for free”. This is especially nice as there are reordering operations which change the mapping between levels and variables but implicitly update the function representations accordingly.

Safety

The implementation must ensure that every inner node only refers to nodes stored in this manager.

Every level view is associated with a manager and a level number. Manager::level() must always return the level view associated to this manager with the given level number.

Required Associated Types

type Edge: Edge<Tag = Self::EdgeTag>

Type of edge

type EdgeTag: Tag

Type of edge tags

type InnerNode: InnerNode<Self::Edge>

Type of inner nodes

type Terminal: Eq + Hash

Type of terminals

type TerminalRef<'a>: Borrow<Self::Terminal> + Copy where Self: 'a

References to Self::Terminals

Should either be a &'a Self::Terminal or just Self::Terminal. The latter is useful for “static terminal managers” which don’t actually store terminal nodes but can map between edges and terminal nodes on the fly. In this case, it would be hard to hand out node references.

type Rules: DiagramRules<Self::Edge, Self::InnerNode, Self::Terminal>

Diagram rules, see DiagramRules for more details

type TerminalIterator<'a>: Iterator<Item = Self::Edge> where Self: 'a

Iterator over all terminals

The actual items are edges pointing to terminals since this allows us to get a NodeID.

type NodeSet: NodeSet<Self::Edge>

Node set type, possibly more efficient than a HashSet<NodeID>

type LevelView<'a>: LevelView<Self::Edge, Self::InnerNode> where Self: 'a

A view on a single level of the unique table.

type LevelIterator<'a>: DoubleEndedIterator<Item = Self::LevelView<'a>> + ExactSizeIterator where Self: 'a

Iterator over levels

Required Methods

fn get_node(&self, edge: &Self::Edge) -> Node<'_, Self>

Get a reference to the node to which edge points

fn clone_edge(&self, edge: &Self::Edge) -> Self::Edge

Clone edge

fn drop_edge(&self, edge: Self::Edge)

Drop edge

fn try_remove_node(&self, edge: Self::Edge, level: LevelNo) -> bool

Drop edge and try to remove the node it points to

level is the node’s level. This is required because nodes do not necessarily store their level, but the lookup in a unique table split by levels needs the level.

Returns whether the node has been removed. There are multiple reasons why removing the node can fail. Obviously, it could still be referenced by other edges. It might also be that removing nodes is currently not possible, e.g., because the manager is not prepared for it. Also, if level does not match the node’s actual level, the node referenced by edge may not be removed. In this case, the method might even remove another node with the same children which is only referenced from the unique table.

Passing the wrong level is considered to be a programming mistake. To aid debugging, the implementation is allowed (but not required) to panic if it can diagnose such a mistake.

fn num_inner_nodes(&self) -> usize

Get the count of inner nodes

fn num_levels(&self) -> LevelNo

Get the number of levels

Same as Self::num_vars()

fn num_named_vars(&self) -> VarNo

Get the number of named variables

fn add_vars(&mut self, additional: VarNo) -> Range<VarNo>

Add additional unnamed variables to the decision diagram

The new variables are added at the bottom of the variable order. More precisely, the level number equals the variable number for each new variable.

Note that some algorithms may assume that the domain of a function represented by a decision diagram is just the set of all variables. In this regard, adding variables can change the semantics of decision diagram nodes.

Returns the range of new variable numbers.

Panics if self.num_vars() plus additional is greater than to VarNo::MAX.

fn add_named_vars<S: Into<String>>( &mut self, names: impl IntoIterator<Item = S>, ) -> Result<Range<VarNo>, DuplicateVarName>

Add named variables to the decision diagram

This is a shorthand for Self::add_vars() and respective Self::set_var_name() calls. More details can be found there.

Returns the range of new variable numbers on success. In case a name is not unique (and not ""), only the first variables with unique names are added, and a DuplicateVarName error provides more details.

Panics if there would be more than VarNo::MAX variables after adding the ones from names.

fn var_name(&self, var: VarNo) -> &str

Get var’s name

For unnamed variables, this will return the empty string.

Panics if var is greater or equal to the number of variables in this manager.

fn set_var_name( &mut self, var: VarNo, name: impl Into<String>, ) -> Result<(), DuplicateVarName>

Label var as name

An empty name means that the variable will become unnamed, and cannot be retrieved via Self::name_to_var() anymore.

Returns a DuplicateVarName error if name is not unique (and not "").

Panics if var is greater or equal to the number of variables in this manager.

fn name_to_var(&self, name: impl AsRef<str>) -> Option<VarNo>

Get the variable number for the given variable name, if present

Note that you cannot retrieve unnamed variables. manager.name_to_var("") always returns None.

fn var_to_level(&self, var: VarNo) -> LevelNo

Get the level for the given variable

Panics if level >= self.num_vars().

fn level_to_var(&self, level: LevelNo) -> VarNo

Get the variable for the given level

Panics if level >= self.num_levels().

fn level(&self, no: LevelNo) -> Self::LevelView<'_>

Get the level given by no

Implementations may or may not acquire a lock here.

Panics if no >= self.num_levels().

fn levels(&self) -> Self::LevelIterator<'_>

Iterate over the levels from top to bottom

fn get_terminal(&self, terminal: Self::Terminal) -> AllocResult<Self::Edge>

Get an edge for the given terminal

Locking behavior: May acquire a lock for the internal terminal unique table. In particular, this means that calling this function while holding a terminal iterator (Manager::terminals()) may cause a deadlock.

fn num_terminals(&self) -> usize

Get the number of terminals

Should agree with the length of the iterator returned by Manager::terminals().

Locking behavior: May acquire a lock for the internal terminal unique table. In particular, this means that calling this function while holding a terminal iterator (Manager::terminals()) may cause a deadlock.

fn terminals(&self) -> Self::TerminalIterator<'_>

Iterator over all terminals

Locking behavior: May acquire a lock for the internal terminal unique table.

fn gc(&self) -> usize

Perform garbage collection

This method looks for nodes that are neither referenced by a Function nor another node and removes them. The method works from top to bottom, so if a node is only referenced by nodes that can be removed, this node will be removed as well.

Returns the number of nodes removed.

The implementation should emit the ManagerEventSubscriber::pre_gc() and ManagerEventSubscriber::post_gc() events unless called from the closure passed to Self::reorder().

fn reorder<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T

Prepare and postprocess a reordering operation. The reordering itself is performed in f.

Returns the value returned by f.

In case of a recursive call (i.e., the closure passed to this method calls this method again), the implementation should just call f and return.

Otherwise, the implementation should emit events in the following order:

1. pre_gc. This enables node removal during the pre_reorder events.
2. pre_reorder and pre_reorder_mut
3. Call f
4. post_reorder and post_reorder_mut
5. post_gc

fn gc_count(&self) -> u64

Get the count of garbage collections

This counter should monotonically increase to ensure that caches are invalidated accordingly.

fn reorder_count(&self) -> u64

Get the count of reordering operations

This counter should monotonically increase to ensure that caches are invalidated accordingly.

Provided Methods

fn approx_num_inner_nodes(&self) -> usize

Get an approximate count of inner nodes

For concurrent implementations, it may be much less costly to determine an approximation of the inner node count than an accurate count (Self::num_inner_nodes()).

fn num_vars(&self) -> VarNo

Get the number of variables

Same as Self::num_levels()

fn add_named_vars_from_map( &mut self, map: VarNameMap, ) -> Result<Range<VarNo>, DuplicateVarName>

Add named variables to the decision diagram

This is a possibly specialized version of Self::add_named_vars().

Panics if there would be more than VarNo::MAX variables after adding the ones from names.

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