Struct EGraph

pub struct EGraph {
    pub nodes: IndexMap<NodeId, Node>,
    pub root_eclasses: Vec<ClassId>,
    pub class_data: IndexMap<ClassId, ClassData>,
    /* private fields */
}

Fields

nodes: IndexMap<NodeId, Node>

root_eclasses: Vec<ClassId>

class_data: IndexMap<ClassId, ClassData>

Implementations

impl EGraph

pub fn inline_leaves(&mut self) -> usize

Inline all leaves (e-classes with a single node that has no children) into their parents, so that they are added to the function name like f(10, ·). Returns the number of leaves inlined.

pub fn saturate_inline_leaves(&mut self)

Inline all leaves (e-classes with a single node that has no children) into their parents, recursively.

pub fn split_classes(&mut self, should_split: impl Fn(&NodeId, &Node) -> bool)

Given some function should_split, after calling this method, all nodes where it is true will have at most one other node in their e-class and if they have parents, will no other nodes in their e-class.

All nodes in an e-class shared with a split node will still be in a e-class with that node, but no longer in an e-class with each other.

This is used to help make the visualization easier to parse, by breaking cycles and allowing these split nodes to be later inlined into their parents with inline_leaves, which only applies when there is a single node in an e-class.

For example, if we split on all “primitive” nodes or their wrappers, like Int(1), then those nodes can then be inlined into their parents and are all nodes equal to them are no longer in single e-class, making the graph layout easier to understand.

Note that should_split should only ever be true for either a single node, or no nodes, in an e-class. If it is true for multiple nodes in an e-class, then this method will panic.

Another way to think about it is that any isomporphic function can be split, since if f(a) = f(b) then a = b, in that case.

impl EGraph

pub fn add_node(&mut self, node_id: impl Into<NodeId>, node: Node)

Adds a new node to the egraph

Panics if a node with the same id already exists

pub fn nid_to_cid(&self, node_id: &NodeId) -> &ClassId

pub fn nid_to_class(&self, node_id: &NodeId) -> &Class

pub fn classes(&self) -> &IndexMap<ClassId, Class>

Groups the nodes in the e-graph by their e-class

This is only done once and then the result is cached. Modifications to the e-graph will not be reflected in later calls to this function.

pub fn from_json_file(path: impl AsRef<Path>) -> Result<Self>

pub fn to_json_file(&self, path: impl AsRef<Path>) -> Result<()>

pub fn test_round_trip(&self)

Trait Implementations

impl Clone for EGraph

fn clone(&self) -> EGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for EGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for EGraph

fn default() -> EGraph

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for EGraph

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Index<&ClassId> for EGraph

type Output = Class

The returned type after indexing.

fn index(&self, index: &ClassId) -> &Self::Output

Performs the indexing (container[index]) operation.

impl Index<&NodeId> for EGraph

type Output = Node

The returned type after indexing.

fn index(&self, index: &NodeId) -> &Self::Output

Performs the indexing (container[index]) operation.

impl PartialEq for EGraph

fn eq(&self, other: &EGraph) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for EGraph

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for EGraph

impl StructuralPartialEq for EGraph