Rust panic when extracting using greedy_dag_cost_model #387
Description
When attempting to extract terms using greedy_dag_cost_model, I often counter a panic that looks something like this:
thread '<unnamed>' panicked at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:491:18:
called `Option::unwrap()` on a `None` value
stack backtrace:
0: 0x1027d6e74 - std::backtrace_rs::backtrace::libunwind::trace::h674dcd02776dcc9c
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/../../backtrace/src/backtrace/libunwind.rs:117:9
1: 0x1027d6e74 - std::backtrace_rs::backtrace::trace_unsynchronized::haccaae8fb80e4531
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/../../backtrace/src/backtrace/mod.rs:66:14
2: 0x1027d6e74 - std::sys::backtrace::_print_fmt::h3191fc6495b0a516
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/sys/backtrace.rs:66:9
3: 0x1027d6e74 - <std::sys::backtrace::BacktraceLock::print::DisplayBacktrace as core::fmt::Display>::fmt::h373e57e2286956dc
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/sys/backtrace.rs:39:26
4: 0x1027ef97c - core::fmt::rt::Argument::fmt::hcee930b009d69e38
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/core/src/fmt/rt.rs:173:76
5: 0x1027ef97c - core::fmt::write::h2c4a0b98b09e3b30
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/core/src/fmt/mod.rs:1465:25
6: 0x1027d5268 - std::io::default_write_fmt::h1b8f25d7cf9c86a4
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/io/mod.rs:639:11
7: 0x1027d5268 - std::io::Write::write_fmt::h00b4007fff731b84
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/io/mod.rs:1954:13
8: 0x1027d6d28 - std::sys::backtrace::BacktraceLock::print::h3eb1535b8d3666ca
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/sys/backtrace.rs:42:9
9: 0x1027d7d54 - std::panicking::default_hook::{{closure}}::hf623c44b740b115f
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/panicking.rs:300:27
10: 0x1027d7ba4 - std::panicking::default_hook::h8875fb31ec87dfad
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/panicking.rs:327:9
11: 0x1027d87dc - std::panicking::rust_panic_with_hook::hdd8ceeeb04975c2b
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/panicking.rs:833:13
12: 0x1027d83e8 - std::panicking::begin_panic_handler::{{closure}}::hdf417b72ab8ffff8
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/panicking.rs:699:13
13: 0x1027d7320 - std::sys::backtrace::__rust_end_short_backtrace::h507d79c50996742e
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/sys/backtrace.rs:168:18
14: 0x1027d80ec - __rustc[5224e6b81cd82a8f]::rust_begin_unwind
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/std/src/panicking.rs:697:5
15: 0x10282ad44 - core::panicking::panic_fmt::h3505bfbec5a0b799
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/core/src/panicking.rs:75:14
16: 0x10282adb4 - core::panicking::panic::he76e9111fdaa2ca0
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/core/src/panicking.rs:145:5
17: 0x10282acdc - core::option::unwrap_failed::h1f788aa856a0b42e
at /rustc/29483883eed69d5fb4db01964cdf2af4d86e9cb2/library/core/src/option.rs:2072:5
18: 0x1021f0f3c - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
19: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
20: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
21: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
22: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
23: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
24: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
25: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
26: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
27: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
28: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
29: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
30: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
31: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
32: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
33: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
34: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
35: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
36: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
37: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
38: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
39: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
40: 0x1021f0acc - egglog::extract::Extractor<C>::reconstruct_termdag_node_helper::hb7164f0c996cef33
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:496:26
41: 0x1021ebf34 - egglog::extract::Extractor<C>::reconstruct_termdag_node::h377fcd0e34ba8f96
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:455:14
42: 0x1021ebf34 - egglog::extract::Extractor<C>::extract_best_with_sort::h3d5061eadd6c7977
at /Users/nelhage/.cargo/git/checkouts/egglog-7c9491f597880af0/ef90b97/src/extract.rs:524:33
43: 0x1021db62c - egglog::extract::Extractor::extract_best::h154a89c8e95cdbf9
at /Users/nelhage/code/egglog-python/src/extract.rs:226:14
44: 0x1021dc53c - egglog::extract::Extractor::__pymethod_extract_best__::h0ac6ee191113a14b
at /Users/nelhage/code/egglog-python/src/extract.rs:173:1
45: 0x1021d7610 - pyo3::impl_::trampoline::fastcall_with_keywords::{{closure}}::h2613ae51cb8b547e
at /Users/nelhage/.cargo/registry/src/artifactory.infra.ant.dev-7db23613d841872b/pyo3-0.27.1/src/impl_/trampoline.rs:44:37
46: 0x1021d7610 - pyo3::impl_::trampoline::trampoline::{{closure}}::h82832ecf7c0517d9
at /Users/nelhage/.cargo/registry/src/artifactory.infra.ant.dev-7db23613d841872b/pyo3-0.27.1/src/impl_/trampoline.rs:190:54
47: 0x1021d7610 - std::panicking::catch_unwind::do_call::h023b9db56221fed1
at /Users/nelhage/.rustup/toolchains/1.89.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panicking.rs:589:40
48: 0x1021d7610 - std::panicking::catch_unwind::hd5d19fccb5f7ae5a
at /Users/nelhage/.rustup/toolchains/1.89.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panicking.rs:552:19
49: 0x1021d7610 - std::panic::catch_unwind::h084f57c7045cd1ab
at /Users/nelhage/.rustup/toolchains/1.89.0-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panic.rs:359:14
50: 0x1021d7610 - pyo3::impl_::trampoline::trampoline::hc92667ce341dfd42
at /Users/nelhage/.cargo/registry/src/artifactory.infra.ant.dev-7db23613d841872b/pyo3-0.27.1/src/impl_/trampoline.rs:190:9
51: 0x1021dbb98 - egglog::extract::<impl pyo3::impl_::pyclass::PyMethods<egglog::extract::Extractor> for pyo3::impl_::pyclass::PyClassImplCollector<egglog::extract::Extractor>>::py_methods::ITEMS::trampoline::h83cf3f84508c5ea0
52: 0x10082b00c - _method_vectorcall_FASTCALL_KEYWORDS
53: 0x10081b978 - _PyObject_Vectorcall
54: 0x100918460 - __PyEval_EvalFrameDefault
55: 0x10091fd8c - __PyEval_Vector
56: 0x100919374 - __PyEval_EvalFrameDefault
57: 0x10091fd8c - __PyEval_Vector
58: 0x10081b7e4 - __PyVectorcall_Call
59: 0x100919374 - __PyEval_EvalFrameDefault
60: 0x10091fd8c - __PyEval_Vector
61: 0x10081b2bc - __PyObject_FastCallDictTstate
62: 0x10081c16c - __PyObject_Call_Prepend
63: 0x100895e7c - _slot_tp_call
64: 0x10081b050 - __PyObject_MakeTpCall
65: 0x100918460 - __PyEval_EvalFrameDefault
66: 0x1009124e8 - _PyEval_EvalCode
67: 0x10090e354 - _builtin_exec
68: 0x1008739e8 - _cfunction_vectorcall_FASTCALL_KEYWORDS
69: 0x10081b978 - _PyObject_Vectorcall
70: 0x100918460 - __PyEval_EvalFrameDefault
71: 0x10091fd8c - __PyEval_Vector
72: 0x10099bf14 - _pymain_run_module
73: 0x10099ba68 - _Py_RunMain
74: 0x10099d040 - _pymain_main
75: 0x1007bd8bc - _main
I unfortunately do not have a small reproducer using greedy_dag_cost_model, and I can't share the internal code for the large reproducer.
However, the attached reproducer triggers a panic on the same unwrap. I produced it by exporting a graph and then minimizing using https://github.com/DRMacIver/shrinkray; the cost model in the code was an approximate port of greedy_dag_cost_model to work at the bindings layer so that I could minimize without bringing the more-expensive Python code into play.
from dataclasses import dataclass, field
from egglog import *
# A cost model, approximately equivalent to, greedy_dag_cost_model,
# which operates purely on the `bindings` level, for the sake of
# minimization.
ENode = tuple[str, tuple[bindings.Value, ...]]
@dataclass
class DAGCostValue:
"""Cost value for DAG-based extraction."""
cost: int
_values: dict[ENode, int]
def __eq__(self, rhs: object) -> bool:
if not isinstance(rhs, DAGCostValue):
return False
return self.cost == rhs.cost
def __lt__(self, other: "DAGCostValue") -> bool:
return self.cost < other.cost
def __le__(self, other: "DAGCostValue") -> bool:
return self.cost <= other.cost
def __gt__(self, other: "DAGCostValue") -> bool:
return self.cost > other.cost
def __ge__(self, other: "DAGCostValue") -> bool:
return self.cost >= other.cost
def __hash__(self) -> int:
return hash(self.cost)
def __str__(self) -> str:
return f"DAGCostValue(cost={self.cost})"
def __repr__(self) -> str:
return f"DAGCostValue(cost={self.cost}, nchildren={len(self._values)})"
@dataclass
class DAGCost:
"""DAG-based cost model for e-graph extraction.
This cost model counts each unique e-node once, implementing
a greedy DAG extraction strategy.
"""
graph: bindings.EGraph
cache: dict[ENode, DAGCostValue] = field(default_factory=dict)
def merge_costs(
self, costs: list[DAGCostValue], node: ENode, self_cost: int = 0
) -> DAGCostValue:
if node in self.cache:
return self.cache[node]
values: dict[ENode, int] = {}
for child in costs:
values.update(child._values)
cost = DAGCostValue(cost=sum(values.values(), start=self_cost), _values=values)
cost._values[node] = self_cost
self.cache[node] = cost
# print(f"merge {costs=} out={cost}")
return cost
def cost_fold(
self, fn: str, enode: ENode, children_costs: list[DAGCostValue]
) -> DAGCostValue:
out = self.merge_costs(children_costs, enode, 1)
# print(f"fold {fn=} {out=}")
return out
def enode_cost(self, name: str, args: list[bindings.Value]) -> ENode:
return (name, tuple(args))
def container_cost(
self, tp: str, value: bindings.Value, element_costs: list[DAGCostValue]
) -> DAGCostValue:
return self.merge_costs(element_costs, (tp, (value,)), 1)
def base_value_cost(self, tp: str, value: bindings.Value) -> DAGCostValue:
return self.merge_costs([], (tp, (value,)), 1)
@property
def egg_cost_model(self) -> bindings.CostModel:
return bindings.CostModel(
fold=self.cost_fold,
enode_cost=self.enode_cost,
container_cost=self.container_cost,
base_value_cost=self.base_value_cost,
)
graph = EGraph()
commands = graph._egraph.parse_program("""
(sort S)
(constructor S0 (S i64) S)
(constructor S1 (S i64 S) S)
(constructor S2 (S) S)
(constructor S3 (S S) S)
(constructor S4 (S S) S)
(constructor S5 (S i64) S)
(constructor S6 (i64) S)
(let b (S6 0))
(let c (S1 b 0 b))
(let x (S2 (S3 (S5 b 0) b)))
(let y (S4 (S2 (S0 c 0)) (S2 b)))
(union x y)
(let victim (S1 c 0 x))
""")
graph._egraph.run_program(*commands)
cost_model = DAGCost(graph._egraph)
extractor = bindings.Extractor(["S"], graph._egraph, cost_model.egg_cost_model)
termdag = bindings.TermDag()
value = graph._egraph.lookup_function("victim", [])
assert value is not None
cost, term = extractor.extract_best(graph._egraph, termdag, value, "S")