[Specbot] Specbot Crash Analyzer — Run §23922549667

[github-actions[bot]]

Workflow run: §23922549667 · Branch: c3 · Build: Debug (CMake + Ninja)

Summary

Item	Value
Build	✅ Debug, CMake + Ninja, c3 branch
Test suites compiled	2 (test_specbot_seq, test_deeptest_seq)
Tests run	59 (16 specbot_seq + 43 deeptest_seq)
Tests passed	58
Tests crashed	1
Tests timed out	0

---

Crash Findings

test_substr_extract

Test file: specbot/test_deeptest_seq.c (line 790)

Observed failure: ASSERTION VIOLATION — VERIFY(ext) failed at src/smt/seq/seq_nielsen.cpp:1444

Test body (summarized):

Z3_ast x   = mk_svar(ctx, "x");
Z3_ast sub = Z3_mk_seq_extract(ctx, x, mk_int(ctx, 1), mk_int(ctx, 3));
Z3_solver_assert(ctx, sol, Z3_mk_eq(ctx, sub, mk_str(ctx, "ell")));
Z3_solver_assert(ctx, sol, Z3_mk_seq_prefix(ctx, mk_str(ctx, "h"), x));
Z3_solver_assert(ctx, sol, Z3_mk_eq(ctx, mk_len(ctx, x), mk_int(ctx, 5)));
Z3_solver_check(ctx, sol);

The test encodes: str.substr(x, 1, 3) == "ell", "h" is a prefix of x, |x| == 5. Expected result: sat (the unique witness is x = "hello").

Root cause hypothesis:

The assertion at line 1444 is:

bool ext = generate_extensions(node);
// ...
VERIFY(ext);   // asserts ext == true; kills the process if false

generate_extensions returns false when none of its 14 extension rules (deterministic modifiers, power rules, Nielsen splits, regex factorizations, etc.) can fire on the current node. The VERIFY then aborts the process.

The trigger is the interaction of str.substr with a string-prefix constraint. Z3 expands str.substr(x, 1, 3) into internal str.at cells and tail variables: x = h · seq.p.suffix1, str.substr2 = str.at3 · str.at4 · str.at5, etc. After this expansion is complete and the integer lengths are constrained (|str.at3|=|str.at4|=|str.at5|=1, |diseq.u'0|=0, …), the Nielsen graph reaches a node whose string-equality component still contains a residual diseq.u' variable arising from the internal disequality encoding of the str.at cells. The node is neither detected as a conflict nor as satisfiable, and none of the current extension rules recognises or matches this residual shape, so generate_extensions exhausts all priorities and returns false.

In short: the Nielsen solver has no extension rule that handles the fully-expanded str.substr / str.at residual node, causing it to reach an unhandled state and panic instead of either producing a model or reporting satisfiability.

The final HTML dump (emitted just before the abort) shows the solver correctly reduced all diseq.w widths to 0 and all diseq.u' suffixes to 0 in all four str.at expansion equations, but then stalled. This suggests the node is actually satisfiable at that point and the missing piece is a rule that recognises a "fully-ground, all-lengths-fixed" node as immediately SAT (or a rule that finalises the disequality/suffix cleanup and emits a SAT witness).

Suggested fix:

In src/smt/seq/seq_nielsen.cpp, nielsen_graph::search (around line 1440), replace the hard VERIFY(ext) with a graceful fallback:

bool ext = generate_extensions(node);
IF_VERBOSE(1, display(verbose_stream(), node));
CTRACE(seq, !ext, display(tout, node) << to_dot() << "\n");
if (!ext) {
    node->to_html(std::cout, m);
    std::cout << std::endl;
    // No extension rule fired — treat this as unknown so the outer
    // solver can fall back rather than crashing.
    return search_result::unknown;
}
```

The `VERIFY` should become either a soft fallback (`return unknown`) or the preferred long-term fix: add a terminal "all-lengths-determined" rule inside `generate_extensions` that recognises a node where every string variable has a fully-determined length-1 (or length-0) chain of `str.at` cells and returns `true` by marking the node SAT directly (or by emitting the explicit character constraints to the underlying integer/character solver).

---

### Tests Passed

**`test_specbot_seq`** (16/16):
`test_simple_eq`, `test_concat_eq`, `test_unsat_eq`, `test_multi_var_eq`, `test_empty_string`, `test_regex_basic`, `test_regex_combined`, `test_length_eq`, `test_length_sum`, `test_quadratic_eq`, `test_many_vars`, `test_push_pop`, `test_incremental_many`, `test_contains`, `test_replace`, `test_long_string_eq`

**`test_deeptest_seq`** (42/43):
`test_prefix_cancel`, `test_suffix_cancel`, `test_prefix_suffix_cancel`, `test_long_prefix_cancel`, `test_partial_prefix_clash`, `test_symbol_clash_ab`, `test_symbol_clash_same_suffix`, `test_const_clash`, `test_multi_clash`, `test_clash_with_length`, `test_deep_chain_10`, `test_linear_subst_chain`, `test_diamond_subst`, `test_wide_fan`, `test_commutative_eq`, `test_triple_double`, `test_quadratic_interleaved`, `test_var_both_sides`, `test_power_eq`, `test_regex_star_len`, `test_regex_phone`, `test_regex_intersect`, `test_regex_multi_member`, `test_regex_complement`, `test_regex_plus_eq`, `test_power_bounded_loop`, `test_power_double_eq`, `test_power_multichar_loop`, `test_power_four_repeat`, `test_power_mixed_ranges`, `test_incremental_simple_50`, `test_incremental_concat_varying`, `test_incremental_regex`, `test_incremental_nested`, `test_unsat_direct`, `test_unsat_length_regex`, `test_unsat_length_impossible`, `test_unsat_empty_regex`, `test_unsat_negation`, `test_unsat_concat_mismatch`, `test_contains_exact`, `test_replace_known`

---

<details>
<summary><b>Full Test Output — test_specbot_seq</b></summary>

```
[SPECBOT] Starting Z3 c3 seq solver invariant tests
[TEST] Running test_simple_eq
[TEST] PASS test_simple_eq
[TEST] Running test_concat_eq
[TEST] PASS test_concat_eq
[TEST] Running test_unsat_eq
[TEST] PASS test_unsat_eq
[TEST] Running test_multi_var_eq
[TEST] PASS test_multi_var_eq
[TEST] Running test_empty_string
[TEST] PASS test_empty_string
[TEST] Running test_regex_basic
[TEST] PASS test_regex_basic
[TEST] Running test_regex_combined
[TEST] PASS test_regex_combined
[TEST] Running test_length_eq
[TEST] PASS test_length_eq
[TEST] Running test_length_sum
[TEST] PASS test_length_sum
[TEST] Running test_quadratic_eq
[TEST] PASS test_quadratic_eq
[TEST] Running test_many_vars
[TEST] PASS test_many_vars
[TEST] Running test_push_pop
[TEST] PASS test_push_pop
[TEST] Running test_incremental_many
[TEST] PASS test_incremental_many
[TEST] Running test_contains
[TEST] PASS test_contains
[TEST] Running test_replace
[TEST] PASS test_replace
[TEST] Running test_long_string_eq
[TEST] PASS test_long_string_eq
=== SpecBot Z3-c3 Seq Tests: 16/16 passed ===
```

</details>

<details>
<summary><b>Full Test Output — test_deeptest_seq (last lines before crash)</b></summary>

```
[SPECBOT] Starting DeepTest Z3-c3 seq solver tests
[TEST] Running test_prefix_cancel
[TEST] PASS test_prefix_cancel
... (42 tests pass) ...
[TEST] Running test_replace_known
[TEST] PASS test_replace_known
[TEST] Running test_substr_extract
  <HTML node dump omitted — ~40 KB of constraint state>
ASSERTION VIOLATION
File: /home/runner/work/z3/z3/src/smt/seq/seq_nielsen.cpp
Line: 1444
Failed to verify: ext
```

</details>

<details>
<summary><b>Build Log (last 30 lines)</b></summary>

```
[872/895] Building CXX object src/api/CMakeFiles/api.dir/api_tactic.cpp.o
[873/895] Generating gparams_register_modules.cpp
[874/895] Generating install_tactic.cpp
[875/895] Generating mem_initializer.cpp
[876/895] Generating shell/gparams_register_modules.cpp
[877/895] Building CXX object src/api/dll/CMakeFiles/api_dll.dir/dll.cpp.o
[878/895] Generating shell/install_tactic.cpp
[879/895] Generating shell/mem_initializer.cpp
[880/895] Building CXX object src/api/dll/CMakeFiles/api_dll.dir/mem_initializer.cpp.o
[881/895] Building CXX object src/api/dll/CMakeFiles/api_dll.dir/gparams_register_modules.cpp.o
[882/895] Building CXX object src/shell/CMakeFiles/shell.dir/drat_frontend.cpp.o
[883/895] Building CXX object src/shell/CMakeFiles/shell.dir/dimacs_frontend.cpp.o
[884/895] Building CXX object src/shell/CMakeFiles/shell.dir/datalog_frontend.cpp.o
[885/895] Building CXX object src/shell/CMakeFiles/shell.dir/gparams_register_modules.cpp.o
[886/895] Building CXX object src/shell/CMakeFiles/shell.dir/main.cpp.o
[887/895] Building CXX object src/shell/CMakeFiles/shell.dir/mem_initializer.cpp.o
[888/895] Building CXX object src/shell/CMakeFiles/shell.dir/z3_log_frontend.cpp.o
[889/895] Building CXX object src/shell/CMakeFiles/shell.dir/opt_frontend.cpp.o
[890/895] Building CXX object src/shell/CMakeFiles/shell.dir/smtlib_frontend.cpp.o
[891/895] Building CXX object src/api/dll/CMakeFiles/api_dll.dir/install_tactic.cpp.o
[892/895] Building CXX object src/shell/CMakeFiles/shell.dir/install_tactic.cpp.o
[893/895] Linking CXX shared library libz3.so.4.17.0.0
[894/895] Creating library symlink libz3.so.4.17 libz3.so
[895/895] Linking CXX executable z3

AI generated by Specbot Crash Analyzer · history

• expires on Apr 9, 2026, 9:42 PM UTC

[github-actions[bot]]

This discussion was automatically closed because it expired on 2026-04-09T21:42:10.861Z.

Closed by Workflow