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 
25
26
27
28
29
30
31
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 
34
35
36
37
38
39
class LatticeBottom(LatticeTop):
    """
    Base class representing the bottom element of the lattice.
    """

    pass

Lattice

Bases: ABC, Generic[LatticeValue]

Abstract base class for a lattice interface.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
class Lattice(ABC, Generic[LatticeValue], metaclass=Singleton):
    """
    Abstract base class for a lattice interface.
    """

    @abstractmethod
    def top(self) -> LatticeValue:
        """Returns the top element of the lattice."""
        pass

    @abstractmethod
    def bottom(self) -> LatticeValue:
        """Returns the bottom element of the lattice."""
        pass

    @abstractmethod
    def leq(self, t1: LatticeValue, t2: LatticeValue) -> bool:
        """Returns True if `t1 <= t2` in the lattice."""
        pass

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

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

    def equal(self, t1: LatticeValue, t2: LatticeValue) -> bool:
        """Returns True if two values are equal in the lattice."""
        return self.leq(t1, t2) and self.leq(t2, t1)

top() -> LatticeValue abstractmethod

Returns the top element of the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
50
51
52
53
@abstractmethod
def top(self) -> LatticeValue:
    """Returns the top element of the lattice."""
    pass

bottom() -> LatticeValue abstractmethod

Returns the bottom element of the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
55
56
57
58
@abstractmethod
def bottom(self) -> LatticeValue:
    """Returns the bottom element of the lattice."""
    pass

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

Returns True if t1 <= t2 in the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
60
61
62
63
@abstractmethod
def leq(self, t1: LatticeValue, t2: LatticeValue) -> bool:
    """Returns True if `t1 <= t2` in the lattice."""
    pass

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

Returns the least upper bound of t1 and t2.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
65
66
67
68
@abstractmethod
def join(self, t1: LatticeValue, t2: LatticeValue) -> LatticeValue:
    """Returns the least upper bound of `t1` and `t2`."""
    pass

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

Returns the greatest lower bound of t1 and t2.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
70
71
72
73
@abstractmethod
def meet(self, t1: LatticeValue, t2: LatticeValue) -> LatticeValue:
    """Returns the greatest lower bound of `t1` and `t2`."""
    pass

equal(t1: LatticeValue, t2: LatticeValue) -> bool

Returns True if two values are equal in the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
75
76
77
def equal(self, t1: LatticeValue, t2: LatticeValue) -> bool:
    """Returns True if two values are equal in the lattice."""
    return self.leq(t1, t2) and self.leq(t2, t1)

LatticeBase

Bases: Lattice[LatticeValue]

Concrete implementation of a lattice interface.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
 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
145
class LatticeBase(Lattice[LatticeValue]):
    """
    Concrete implementation of a lattice interface.
    """

    def top(self) -> LatticeValue:
        """Returns the top element of the lattice."""
        return LatticeTop

    def bottom(self) -> LatticeValue:
        """Returns the bottom element of the lattice."""
        return LatticeBottom

    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 atomic_ancestors(self, t: object) -> set[object]:
        """Returns the atomic ancestors of a given node."""
        if not self.is_class_node(t):
            raise TypeError(f"Expected lattice class node, got {t}")
        return {c for c in t.__mro__ if self.is_class_node(c)}

    def leq(self, t1: LatticeValue, t2: LatticeValue) -> 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: LatticeValue, t2: LatticeValue) -> LatticeValue:
        """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: LatticeValue, t2: LatticeValue) -> LatticeValue:
        """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

top() -> LatticeValue

Returns the top element of the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
85
86
87
def top(self) -> LatticeValue:
    """Returns the top element of the lattice."""
    return LatticeTop

bottom() -> LatticeValue

Returns the bottom element of the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
89
90
91
def bottom(self) -> LatticeValue:
    """Returns the bottom element of the lattice."""
    return LatticeBottom

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 
93
94
95
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)

atomic_ancestors(t: object) -> set[object]

Returns the atomic ancestors of a given node.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
 97
 98
 99
100
101
def atomic_ancestors(self, t: object) -> set[object]:
    """Returns the atomic ancestors of a given node."""
    if not self.is_class_node(t):
        raise TypeError(f"Expected lattice class node, got {t}")
    return {c for c in t.__mro__ if self.is_class_node(c)}

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

Returns True if t1 <= t2 in the lattice.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
103
104
105
106
107
108
109
110
111
def leq(self, t1: LatticeValue, t2: LatticeValue) -> 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: LatticeValue, t2: LatticeValue) -> LatticeValue

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
136
137
def join(self, t1: LatticeValue, t2: LatticeValue) -> LatticeValue:
    """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: LatticeValue, t2: LatticeValue) -> LatticeValue

Returns the greatest lower bound of t1 and t2.

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
139
140
141
142
143
144
145
def meet(self, t1: LatticeValue, t2: LatticeValue) -> LatticeValue:
    """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

maplattice(lattice: Type[Lattice]) -> Type[Lattice]

Builds a map lattice class from a lattice class for map based analysis

Source code in oqd-compiler-infrastructure/src/oqd_compiler_infrastructure/lattice.py 
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
def maplattice(lattice: Type[Lattice]) -> Type[Lattice]:
    """Builds a map lattice class from a lattice class for map based analysis"""
    name = f"Map{lattice.__name__}"

    def wraps(f):
        f.__qualname__ = f"{name}.{f.__name__}"
        return f

    @wraps
    def top(self) -> LatticeValue:
        """Returns the top element of the lattice."""
        return LatticeTop

    @wraps
    def bottom(self) -> LatticeValue:
        """Returns the bottom element of the lattice."""
        return LatticeBottom

    @wraps
    def leq(self, t1: LatticeValue, t2: LatticeValue) -> bool:
        """Returns True if `t1 <= t2` in the lattice."""

        if t1 is LatticeBottom or t2 is LatticeTop:
            return True
        if t1 is LatticeTop:
            return t2 is LatticeTop
        if t2 is LatticeBottom:
            return self.leq(t1, {})
        v = self._element_lattice()
        b = v.bottom()
        for k in set(t1).union(t2):
            if not v.leq(t1.get(k, b), t2.get(k, b)):
                return False
        return True

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

        if t1 is LatticeTop or t2 is LatticeTop:
            return LatticeTop
        if t1 is LatticeBottom:
            return t2
        if t2 is LatticeBottom:
            return t1
        v = self._element_lattice()
        b = v.bottom()
        return {k: v.join(t1.get(k, b), t2.get(k, b)) for k in set(t1).union(t2)}

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

        if t1 is LatticeBottom or t2 is LatticeBottom:
            return LatticeBottom
        if t1 is LatticeTop:
            return t2
        if t2 is LatticeTop:
            return t1
        v = self._element_lattice()
        b = v.bottom()
        return {k: v.meet(t1.get(k, b), t2.get(k, b)) for k in set(t1).union(t2)}

    def update_ns(ns):
        ns.update(
            {
                "__module__": lattice.__module__,
                "top": top,
                "bottom": bottom,
                "leq": leq,
                "join": join,
                "meet": meet,
                "_element_lattice": lattice,
            }
        )
        return ns

    cls = types.new_class(name, (Lattice[Dict[str, LatticeValue]],), None, update_ns)
    return cls