flow

Documentation

Overview

Package flow implements a monotone flow analysis framework.

Index

• type Analysis
  • func Forward[L Semilattice[Fact], Fact any, NodeID comparable](g graph.Graph[NodeID], entry map[NodeID]Fact, ...) *Analysis[Fact, NodeID]
  • func (a *Analysis[Fact, NodeID]) Edge(from, to NodeID) Fact
  • func (a *Analysis[Fact, NodeID]) In(nid NodeID) Fact
• type MapLattice
  • func (m MapLattice[Key, Elem, L]) Equals(a, b map[Key]Elem) bool
  • func (m MapLattice[Key, Elem, L]) Ident() map[Key]Elem
  • func (m MapLattice[Key, Elem, L]) Merge(a, b map[Key]Elem) map[Key]Elem
• type Semilattice

Types

type Analysis

type Analysis[Fact any, NodeID comparable] struct {
	// contains filtered or unexported fields
}

Analysis is the result of a monotone analysis. Fact is the type of elements in the analysis semilattice, and represents the outcome of the analysis at every node and edge.

func Forward

func Forward[L Semilattice[Fact], Fact any, NodeID comparable](g graph.Graph[NodeID], entry map[NodeID]Fact, transfer func(from, to NodeID, fact Fact) Fact) *Analysis[Fact, NodeID]

Forward performs a forward monotone analysis over a control flow graph.

The entry map provides initial state for entry blocks (blocks with zero predecessors). For each edge, it calls transfer(fact, edge), where fact is the analysis state on entry to edge.Pred. The transfer function must return the outgoing analysis state of the edge (which may be fact, if the edge has no effect on the analysis state).

func (*Analysis[Fact, NodeID]) Edge

func (a *Analysis[Fact, NodeID]) Edge(from, to NodeID) Fact

Edge returns the analysis fact propagated on edge from ==> to.

func (*Analysis[Fact, NodeID]) In

func (a *Analysis[Fact, NodeID]) In(nid NodeID) Fact

In returns the analysis fact on entry to nid. This is the merge of the facts on all incoming edges.

type MapLattice

type MapLattice[Key comparable, Elem any, L Semilattice[Elem]] struct {
	// contains filtered or unexported fields
}

A MapLattice implements Semilattice[map[Key]Elem]. The values in the map are themselves defined by Semilattice L.

Any elements missing from the map are implicitly L's identity element, and L's identity element never appears as a value in the map.

func (MapLattice[Key, Elem, L]) Equals

func (m MapLattice[Key, Elem, L]) Equals(a, b map[Key]Elem) bool

func (MapLattice[Key, Elem, L]) Ident

func (m MapLattice[Key, Elem, L]) Ident() map[Key]Elem

func (MapLattice[Key, Elem, L]) Merge

func (m MapLattice[Key, Elem, L]) Merge(a, b map[Key]Elem) map[Key]Elem

type Semilattice

type Semilattice[Elem any] interface {
	// Ident returns the identity element of this lattice, that is the unit of
	// the Merge operation.
	Ident() Elem

	// Equals returns whether a and b are the same element.
	Equals(a, b Elem) bool

	// Merge combines two lattice values, such as the two possible values of a
	// variable at the end of an if/else statement.
	//
	// Merge must satisfy the following identities, where we use ∧ for Merge, =
	// for Equals, and 𝟏 for Ident:
	//
	// - Associativity: x ∧ (y ∧ z) = (x ∧ y) ∧ z
	// - Commutativity: x ∧ y = y ∧ x
	// - Idempotency: x ∧ x = x
	// - Identity: x ∧ 𝟏 = x
	Merge(a, b Elem) Elem
}

A Semilattice describes a bounded semilattice over Elem. That is, a partial order over values of type Elem, with a binary Merge operator and an identity element.

This is typically implemented by a stateless type, and acts as a factory for lattice elements.