Skip to content

Lattice

oqd_compiler_infrastructure.lattice

LatticeTop

Base class representing the top element of the lattice. In LatticeBase, nodes are classes that inherit from LatticeTop.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
22
23
24
25
26
27
class LatticeTop:
    """
    Base class representing the top element of the lattice.
    In `LatticeBase`, nodes are classes that inherit from `LatticeTop`.
    """
    pass

LatticeBottom

Bases: LatticeTop

Base class representing the bottom element of the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
30
31
32
33
34
class LatticeBottom(LatticeTop):
    """
    Base class representing the bottom element of the lattice.
    """
    pass

Lattice

Bases: ABC, Generic[LatticeType]

Abstract base class for a lattice interface.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Lattice(ABC, Generic[LatticeType]):
    """
    Abstract base class for a lattice interface.
    """
    @abstractmethod
    def leq(self, t1: LatticeType, t2: LatticeType) -> bool:
        """Returns True if `t1 <= t2` in the lattice."""
        pass

    @abstractmethod
    def join(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
        """Returns the least upper bound of `t1` and `t2`."""
        pass

    @abstractmethod
    def meet(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
        """Returns the greatest lower bound of `t1` and `t2`."""
        pass

leq(t1: LatticeType, t2: LatticeType) -> bool abstractmethod

Returns True if t1 <= t2 in the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
44
45
46
47
@abstractmethod
def leq(self, t1: LatticeType, t2: LatticeType) -> bool:
    """Returns True if `t1 <= t2` in the lattice."""
    pass

join(t1: LatticeType, t2: LatticeType) -> LatticeType abstractmethod

Returns the least upper bound of t1 and t2.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
49
50
51
52
@abstractmethod
def join(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
    """Returns the least upper bound of `t1` and `t2`."""
    pass

meet(t1: LatticeType, t2: LatticeType) -> LatticeType abstractmethod

Returns the greatest lower bound of t1 and t2.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
54
55
56
57
@abstractmethod
def meet(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
    """Returns the greatest lower bound of `t1` and `t2`."""
    pass

LatticeBase

Bases: Lattice[LatticeType]

Concrete implementation of a lattice interface.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
class LatticeBase(Lattice[LatticeType]):
    """
    Concrete implementation of a lattice interface.
    """


    def __init__(self):
        """
        Initializes lattice with top and bottom nodes.
        The map is a dictionary that maps each node of the lattice to its immediate parent(s).
        """
        self.map_node_to_parents = {
            LatticeBottom: (),
            LatticeTop: (),
        }


    def is_class_node(self, t: object) -> bool:
        """Returns True if `t` is a valid lattice node."""
        return isinstance(t, type) and issubclass(t, LatticeTop)


    def add_node(self, t, parent):
        """Adds a node to the lattice, by tracking the parent(s) of the node."""
        self.map_node_to_parents[t] = (parent,)


    def atomic_ancestors(self, t):
        """Returns the atomic ancestors of a given node."""
        if not self.is_class_node(t):
            raise TypeError(f"Expected lattice class node, got {t}")
        out = {t}
        stack = [t]
        while stack:
            curr = stack.pop()
            for parent in self.map_node_to_parents.get(curr, ()):
                if parent not in out:
                    out.add(parent)
                    stack.append(parent)
        return out


    def leq(self, t1: LatticeType, t2: LatticeType) -> bool:
        """Returns True if `t1 <= t2` in the lattice."""
        if t1 is LatticeBottom:
            return True
        if not self.is_class_node(t1) or not self.is_class_node(t2):
            return False
        if t1 is t2:
            return True
        return t2 in self.atomic_ancestors(t1)


    def join(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
        """Returns the least upper bound of `t1` and `t2`."""
        if self.leq(t1, t2):
            return t2
        if self.leq(t2, t1):
            return t1
        if not self.is_class_node(t1) or not self.is_class_node(t2):
            return LatticeTop
        common_ancestors = self.atomic_ancestors(t1).intersection(self.atomic_ancestors(t2))
        if not common_ancestors:
            return LatticeTop

        minimal_ancestors = set()
        for candidate in common_ancestors:
            smaller = any(
                other is not candidate and self.leq(other, candidate)
                for other in common_ancestors
            )
            if not smaller:
                minimal_ancestors.add(candidate)
        if len(minimal_ancestors) != 1:
            return LatticeTop
        return next(iter(minimal_ancestors))


    def meet(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
        """Returns the greatest lower bound of `t1` and `t2`."""
        if self.leq(t1, t2):
            return t1
        if self.leq(t2, t1):
            return t2
        return LatticeBottom

__init__()

Initializes lattice with top and bottom nodes. The map is a dictionary that maps each node of the lattice to its immediate parent(s).

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
66
67
68
69
70
71
72
73
74
def __init__(self):
    """
    Initializes lattice with top and bottom nodes.
    The map is a dictionary that maps each node of the lattice to its immediate parent(s).
    """
    self.map_node_to_parents = {
        LatticeBottom: (),
        LatticeTop: (),
    }

is_class_node(t: object) -> bool

Returns True if t is a valid lattice node.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
77
78
79
def is_class_node(self, t: object) -> bool:
    """Returns True if `t` is a valid lattice node."""
    return isinstance(t, type) and issubclass(t, LatticeTop)

add_node(t, parent)

Adds a node to the lattice, by tracking the parent(s) of the node.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
82
83
84
def add_node(self, t, parent):
    """Adds a node to the lattice, by tracking the parent(s) of the node."""
    self.map_node_to_parents[t] = (parent,)

atomic_ancestors(t)

Returns the atomic ancestors of a given node.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
87
88
89
90
91
92
93
94
95
96
97
98
99
def atomic_ancestors(self, t):
    """Returns the atomic ancestors of a given node."""
    if not self.is_class_node(t):
        raise TypeError(f"Expected lattice class node, got {t}")
    out = {t}
    stack = [t]
    while stack:
        curr = stack.pop()
        for parent in self.map_node_to_parents.get(curr, ()):
            if parent not in out:
                out.add(parent)
                stack.append(parent)
    return out

leq(t1: LatticeType, t2: LatticeType) -> bool

Returns True if t1 <= t2 in the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
102
103
104
105
106
107
108
109
110
def leq(self, t1: LatticeType, t2: LatticeType) -> bool:
    """Returns True if `t1 <= t2` in the lattice."""
    if t1 is LatticeBottom:
        return True
    if not self.is_class_node(t1) or not self.is_class_node(t2):
        return False
    if t1 is t2:
        return True
    return t2 in self.atomic_ancestors(t1)

join(t1: LatticeType, t2: LatticeType) -> LatticeType

Returns the least upper bound of t1 and t2.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
def join(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
    """Returns the least upper bound of `t1` and `t2`."""
    if self.leq(t1, t2):
        return t2
    if self.leq(t2, t1):
        return t1
    if not self.is_class_node(t1) or not self.is_class_node(t2):
        return LatticeTop
    common_ancestors = self.atomic_ancestors(t1).intersection(self.atomic_ancestors(t2))
    if not common_ancestors:
        return LatticeTop

    minimal_ancestors = set()
    for candidate in common_ancestors:
        smaller = any(
            other is not candidate and self.leq(other, candidate)
            for other in common_ancestors
        )
        if not smaller:
            minimal_ancestors.add(candidate)
    if len(minimal_ancestors) != 1:
        return LatticeTop
    return next(iter(minimal_ancestors))

meet(t1: LatticeType, t2: LatticeType) -> LatticeType

Returns the greatest lower bound of t1 and t2.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
138
139
140
141
142
143
144
def meet(self, t1: LatticeType, t2: LatticeType) -> LatticeType:
    """Returns the greatest lower bound of `t1` and `t2`."""
    if self.leq(t1, t2):
        return t1
    if self.leq(t2, t1):
        return t2
    return LatticeBottom