Skip to content

Lattice

Lattice for constant analysis.

Bottom dataclass

Bottom()

Bases: Result

Bottom element of the lattice.

is_subseteq

is_subseteq(other: Result) -> bool

Subseteq operation.

Source code in src/kirin/analysis/const/lattice.py
60
61
def is_subseteq(self, other: Result) -> bool:
    return True

PartialConst dataclass

PartialConst()

Bases: Result

Base class for partial constant values.

PartialLambda dataclass

PartialLambda(
    argnames: list[str],
    code: ir.Statement,
    captured: tuple[Result, ...],
)

Bases: PartialConst

Partial lambda constant value.

This represents a closure with captured variables.

join

join(other: Result) -> Result

Join operation.

Source code in src/kirin/analysis/const/lattice.py
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
def join(self, other: Result) -> Result:
    if other is other.bottom():
        return self

    if not isinstance(other, PartialLambda):
        return Unknown().join(other)  # widen self

    if self.code is not other.code:
        return Unknown()  # lambda stmt is pure

    if len(self.captured) != len(other.captured):
        return self.bottom()  # err

    return PartialLambda(
        self.argnames,
        self.code,
        tuple(x.join(y) for x, y in zip(self.captured, other.captured)),
    )

meet

meet(other: Result) -> Result

Meet operation.

Source code in src/kirin/analysis/const/lattice.py
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
def meet(self, other: Result) -> Result:
    if not isinstance(other, PartialLambda):
        return Unknown().meet(other)

    if self.code is not other.code:
        return self.bottom()

    if len(self.captured) != len(other.captured):
        return Unknown()

    return PartialLambda(
        self.argnames,
        self.code,
        tuple(x.meet(y) for x, y in zip(self.captured, other.captured)),
    )

PartialTuple dataclass

PartialTuple(data: tuple[Result, ...])

Bases: PartialConst

Partial tuple constant value.

is_equal

is_equal(other: Result) -> bool

Check if two lattices are equal.

Source code in src/kirin/analysis/const/lattice.py
143
144
145
146
147
148
def is_equal(self, other: Result) -> bool:
    if isinstance(other, PartialTuple):
        return all(x.is_equal(y) for x, y in zip(self.data, other.data))
    elif isinstance(other, Value) and isinstance(other.data, tuple):
        return all(x.is_equal(Value(y)) for x, y in zip(self.data, other.data))
    return False

join

join(other: Result) -> Result

Join operation.

Source code in src/kirin/analysis/const/lattice.py
117
118
119
120
121
122
123
124
125
126
127
128
def join(self, other: Result) -> Result:
    if other.is_subseteq(self):
        return self
    elif self.is_subseteq(other):
        return other
    elif isinstance(other, PartialTuple):
        return PartialTuple(tuple(x.join(y) for x, y in zip(self.data, other.data)))
    elif isinstance(other, Value) and isinstance(other.data, tuple):
        return PartialTuple(
            tuple(x.join(Value(y)) for x, y in zip(self.data, other.data))
        )
    return Unknown()

meet

meet(other: Result) -> Result

Meet operation.

Source code in src/kirin/analysis/const/lattice.py
130
131
132
133
134
135
136
137
138
139
140
141
def meet(self, other: Result) -> Result:
    if self.is_subseteq(other):
        return self
    elif other.is_subseteq(self):
        return other
    elif isinstance(other, PartialTuple):
        return PartialTuple(tuple(x.meet(y) for x, y in zip(self.data, other.data)))
    elif isinstance(other, Value) and isinstance(other.data, tuple):
        return PartialTuple(
            tuple(x.meet(Value(y)) for x, y in zip(self.data, other.data))
        )
    return self.bottom()

PartialTupleMeta

Bases: LatticeAttributeMeta

Metaclass for PartialTuple.

This metaclass canonicalizes PartialTuple instances with all Value elements into a single Value instance.

Result dataclass

Result()

Bases: Attribute, IsSubsetEqMixin['Result'], SimpleJoinMixin['Result'], SimpleMeetMixin['Result'], BoundedLattice['Result'], _ElemVisitor

Base class for constant analysis results.

Unknown dataclass

Unknown()

Bases: Result

Unknown constant value. This is the top element of the lattice.

is_subseteq

is_subseteq(other: Result) -> bool

Subseteq operation.

Source code in src/kirin/analysis/const/lattice.py
48
49
def is_subseteq(self, other: Result) -> bool:
    return isinstance(other, Unknown)

Value dataclass

Value(data: Any)

Bases: Result

Constant value. Wraps any hashable Python value.

is_equal

is_equal(other: Result) -> bool

Check if two lattices are equal.

Source code in src/kirin/analysis/const/lattice.py
77
78
79
80
def is_equal(self, other: Result) -> bool:
    if isinstance(other, Value):
        return self.data == other.data
    return False