These knobs govern the integer cut/cube heuristics (the "hammers":
find_cube, lcube, hnf, gomory, dio), not just cuts, so the names now
reflect that. lp.int_hammer_period sets the shared firing period and
lp.random_hammers toggles random vs deterministic gating.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
The toggle also gates the cube heuristics (find_cube, lcube), not just
cuts, so 'cut' in the name was misleading. random_period covers all the
periodic integer heuristic gates (find_cube, lcube, hnf, gomory, dio).
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Rename the toggle so it sits beside lp.cut_period and reads as a
modifier on it (cut_period + random) rather than burying "cut" in the
middle of the name.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Introduce the boolean lp.random_cut_period parameter (default true).
When enabled, the periodic integer heuristic gates (find_cube, lcube,
hnf, gomory, dio) fire at random with the same 1/period expected rate;
when disabled they fall back to the deterministic every-k-th-call
modulus on m_number_of_calls. The shared hit_period() helper centralizes
this decision, and m_number_of_calls is restored for the deterministic
path.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Replace deterministic m_number_of_calls % period gates with
settings().random_next(period) == 0 for should_find_cube,
should_find_lcube, should_solve_dioph_eq and should_hnf_cut,
matching the existing should_gomory_cut approach. This keeps the
same expected 1/period firing rate while avoiding phase-locking
with the search. Removes the now-unused m_number_of_calls member.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
should_gomory_cut used a deterministic schedule (m_number_of_calls %
m_int_gomory_cut_period == 0). On some UNSAT QF_LIA families (e.g.
rings_preprocessed, cut_lemmas) this fixed period phase-locks with the
search: the solver drowns in theory conflicts (~32k vs ~2k) while the
Diophantine tightening that would close the proof is starved, causing
timeouts that vanish when the period is changed (4 vs 5).
Replace the modulus with a random draw of the same expected rate
(random_next(period) == 0). This breaks the deterministic resonance while
preserving the average cut frequency. Locally this turns the whole
regressing band from timeouts / ~23s into sub-second-to-seconds solves,
with no slowdown observed on a regression sample and lp unit tests passing.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
The find_cube, hnf and gomory integer heuristics were all throttled by a
hardcoded period of 4 (m_int_find_cube_period, m_hnf_cut_period,
m_int_gomory_cut_period). Make this value tunable through the new
lp.cut_period parameter (default 4, preserving current behavior) so the
period can be swept (e.g. 3/4/5) for benchmarking. A value of 0 is clamped
to 1.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
## Summary
z3 already builds under Pyodide (there is a `pyodide.yml` workflow and
an
`IS_PYODIDE` path in `setup.py`), but that path uses `pyodide build` and
produces
a wheel tagged `emscripten_<pyodide-version>_wasm32`, which is pinned to
a single
Pyodide release and rejected by PyPI — so today it's only usable as a CI
artifact.
[PEP 783](https://peps.python.org/pep-0783/) introduced the portable
`pyemscripten_<date>_wasm32` platform tag that **PyPI accepts** and
`micropip` can
install at runtime. This makes `z3-solver` build that wheel via
`cibuildwheel --platform pyodide`.
## Changes
- **`setup.py`** — for the emscripten target, use the wheel platform tag
that
pyodide-build provides verbatim via `_PYTHON_HOST_PLATFORM` (e.g.
`pyemscripten_2026_0_wasm32`) instead of reconstructing an
`emscripten_*` tag.
Falls back to the previous behaviour when that env var is absent.
- **`setup.py` / `CMakeLists.txt` / `pyproject.toml`** — switch the
Pyodide build
from JS-based exceptions (`-fexceptions`,
`-sDISABLE_EXCEPTION_CATCHING=0`) to
**native wasm exception handling** (`-fwasm-exceptions
-sSUPPORT_LONGJMP=wasm`),
matching the ABI of the Pyodide 314 / emscripten 5 main module. With the
old
flags `libz3.so` imports `invoke_*` trampolines the runtime no longer
provides,
so the wheel builds but the first `Z3_mk_config` call fails at runtime
with
`Dynamic linking error: cannot resolve symbol invoke_vi`.
- **`pyproject.toml`** — add `[tool.cibuildwheel]` /
`[tool.pyodide.build]` so
`cibuildwheel --platform pyodide` builds and tests the wheel (`cp314`).
- **`.github/workflows/pyodide-pypi.yml`** (new) — build with
cibuildwheel and
publish to PyPI (trusted publishing) on tags. Existing `pyodide.yml`
unchanged.
## Verification
Built with `cibuildwheel 4.1.0` / `pyodide-build 0.35.0` / `emscripten
5.0.3`,
CPython 3.14 / Pyodide 314:
- Produces `z3_solver-4.17.0.0-py3-none-pyemscripten_2026_0_wasm32.whl`.
- `z3test.py` passes in the Pyodide runtime (node + wasm32).
- Installed via `micropip` and solves SMT problems both under node and
in a
browser (`sat` with a model, `unsat` for a contradiction).
🤖 Generated with [Claude Code](https://claude.com/claude-code)
🕵️♂️ Reviewed by [Alcides Fonseca](https://wiki.alcidesfonseca.com)
Co-authored-by: Claude Opus 4.8 <noreply@anthropic.com>
This is another PR towards the goal of getting a clean build with clang,
using the compiler options used in building clang-tidy.
In https://github.com/Z3Prover/z3/pull/9800, we changed the build flags
to eliminate a warning for zero-length arrays. In that PR, I missed this
one: there was one instance of m_arr[] instead of m_arr[0]. In the
clang-tidy build, that gives warnings like:
```
/Users/daviddetlefs/llvm-project/build_dbg/_deps/z3-src/src/model/func_interp.h:43:12: warning: flexible array members are a C99 feature [-Wc99-extensions]
```
The PR fixes this, making it a zero-length array, the idiom used in all
the other similar cases. I also added the compiler flag that produced
this warning, so we can notice such changes in the future.
PR #9872 caused timeouts in QF_UFBV, QF_BV, and QF_FP regressions
(`t135`, `t136`, `nl53`, `3397`, `4841-1`, `fp-lt-gt`, `fp-rem-11`).
## Root cause
The `goal2sat` change skipped caching AST nodes with `ref_count ≤ 1`
under the assumption they're visited only once. This assumption is
wrong: EUF, BV, and FP theory extensions all call `internalize()` from
the theory solver side, outside the main DFS traversal. On the second
`internalize(n)` call, the missing cache entry causes the entire subtree
to be re-encoded with a fresh literal — inconsistent encoding and
exponential blowup.
## Changes
- **`goal2sat.cpp`**: revert the `ref_count ≤ 1` skip-caching
optimization entirely; it is unsafe whenever any theory extension is
active.
- **`bit_blaster_tpl_def.h`**: retain the `mk_eq` micro-optimization
from #9872 — pre-size with `resize(sz)` and use index assignment instead
of `push_back`. This is correct: `resize` null-initializes slots and
`element_ref::operator=` handles ref-counting via `inc_ref`/`dec_ref`.
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
This tightens two historical `nlsat` regressions that were still
print-only.
Closes#9859.
In `tst_16`, the test already exercises the old `lws2380` shape, but it
only dumped the projected clause. On current `master`, both projection
paths still keep the `x7`-linked root constraints, so this change turns
that observation into an assertion and updates the stale comment to
describe the current invariant.
In `tst_22`, the test already computes whether the projected lemma is
falsified at the stored counterexample. It previously printed the result
and kept going. This change adds `ENSURE(!all_false)` so the test fails
if that historical unsoundness shape comes back.
Testing:
`cmake --build . --target test-z3 -j1`
`./test-z3 /seq nlsat`
`Microsoft.Z3.dll` was being emitted with PE `Machine=0x8664` (AMD64)
despite being pure IL, because the Windows x64 CI environment
(`vcvarsall.bat x64`) injects `Platform=x64` into MSBuild, which sets
the COFF machine type when `PlatformTarget` is not explicitly specified.
This causes `FS0193` / architecture mismatch errors on any arm64 .NET
host (macOS Apple Silicon, Linux aarch64, Windows on ARM).
## Changes
- **`scripts/mk_util.py`** — Add
`<PlatformTarget>AnyCPU</PlatformTarget>` to the in-memory `.csproj`
template generated by the Python build system (`mk_win_dist.py`,
`mk_unix_dist.py`)
- **`src/api/dotnet/Microsoft.Z3.csproj.in`** — Add
`<PlatformTarget>AnyCPU</PlatformTarget>` to the CMake build system
template
Both paths now produce `Machine=0x014C` (i386/AnyCPU) regardless of host
or CI environment, matching the assembly's actual nature (`ILONLY=True`,
`32BIT_REQUIRED=False`). The native side already ships six RIDs; no
changes needed there.
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
This is another PR towards the goal of getting a clean build with clang,
using the compiler options used in building clang-tidy.
By default, without any new -W flags, clang warns about unused local
variables and private class fields. This PR deletes the handful of these
that clang found.
I'm assuming that the class "enode" in smt_context.cpp is the one in
smt_enode.h, so that
```
parent->get_expr()
```
calls a const method with no side effects.
## Summary
egex_bisim::collect_leaves used to descend through `re.union` and
`re.antimirov_union` at the top of each leaf of the transition regex,
splitting a single bisimulation state into multiple states before they
were merged into the union-find. This contradicts the bisimulation
invariant: **each leaf of a t-regex represents one state, regardless of
its top-level shape**. The fix descends into `ite` only (which is the
actual structural splitter of guarded transitions).
## Why it matters
The split happens to be *sound* for the current algorithm when the goal
is asserting `L(union(A, B)) = empty` (since `L(A) = empty AND L(B) =
empty` is equivalent), but it:
1. Adds spurious merges to the union-find that distort state-class
identities.
2. Slows convergence on hard equivalence queries (and causes early
timeouts in practice).
3. Creates latent unsoundness risk for any extension that interprets
leaves more semantically (XOR pair handling, classical-flag propagation,
future antimirov re-enable, etc.).
## Empirical validation
Run on the 1523-file regex-equivalence corpus, 5s/file timeout, 8
workers:
| metric | pre-fix master | post-fix |
|---|---|---|
| sat | 1008 | 1014 |
| unsat | 368 | 368 |
| timeout | 145 | 139 |
| unknown | 2 | 2 |
| SAT↔UNSAT verdict flips | — | **0** |
| timeout→sat flips | — | 6 |
| commonly-solved wall ratio | 1.000x | **0.902x** |
The 6 `timeout` → `sat` cases all return the *same* `sat` under
pre-fix master if given 60s; they are previously-slow cases not
previously-wrong ones.
Z3 unit tests: 89/89 pass (`test-z3 /a`).
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Implemented the largest cube heuristic from Bromberger and Weidenbach's
paper on cubes. Also fixes an overflow bug in mzp.
Use vswhere to find the visual studio version on windows in the build's ymls.
---------
Signed-off-by: Lev Nachmanson <levnach@hotmail.com>
Co-authored-by: Claude Fable 5 <noreply@anthropic.com>
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Homebrew upgrade from Z3 4.15.4 to 4.16.0 failed on macOS 12 during
`src/ast/ast.cpp` compilation because `obj_map::key_data` was used with
`(key, value)` construction but only implicit constructors existed. This
surfaced at `m_poly_roots.insert(new_node, new_node)` and similar map
operations.
- **Root cause addressed**
- `obj_map<Key, Value>::key_data` relied on implicit constructors, which
are insufficient under stricter toolchains when `key_data(k, v)` /
`key_data(k)` are instantiated via `obj_map` helpers.
- **Code change (minimal, targeted)**
- Added explicit struct constructors in `src/util/obj_hashtable.h` for:
- default initialization
- key-only construction (`key_data(Key* k)`)
- key + lvalue value (`key_data(Key* k, Value const& v)`)
- key + rvalue value (`key_data(Key* k, Value&& v)`)
- No behavioral changes to map semantics; this only makes existing call
sites well-formed across compilers.
- **Example of the change**
```c++
struct key_data {
Key * m_key = nullptr;
Value m_value;
key_data() = default;
key_data(Key* k): m_key(k) {}
key_data(Key* k, Value const& v): m_key(k), m_value(v) {}
key_data(Key* k, Value&& v): m_key(k), m_value(std::move(v)) {}
// ...
};
```
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
The C++ implementation of the fixedpoint engine (in
z3/src/api/api_datalog.cpp) already attempts to read `rlimit` from its
local parameters:
```c++
unsigned rlimit = to_fixedpoint(d)->m_params.get_uint("rlimit", mk_c(c)->get_rlimit());
```
However, because `rlimit` was not registered in the public fp parameter
schema (`fp_params.pyg`), any attempt by clients to set it locally via
`Z3_fixedpoint_set_params` was rejected by the Z3 parameter validator
with an "unknown parameter" error.
Implements the algorithm of Eq(p,q) = Empty(p XOR q)' using a union-find
driven bisimulation closure (per the CAV'26 ERE paper).
### What's added
* **New primitive OP_RE_XOR (re.xor)** wired through seq_decl_plugin:
parser signature, info propagation (nullable, min_length), and
pretty-printer.
* **seq_rewriter**: structural XOR rewrites ( XOR r = empty, XOR empty =
r, ull XOR r = comp(r), comp/comp absorption, complement push, AC
normalisation), nullability (Null(p XOR q) = Null(p) != Null(q)),
derivative (D_a(p XOR q) = D_a(p) XOR D_a(q)), reverse, antimirov
derivative, and `check_deriv_normal_form` coverage.
* **New class seq::regex_bisim** in
`src/ast/rewriter/seq_regex_bisim.{h,cpp}` to keep the bisim logic out
of the already-large `seq_rewriter.cpp`. Uses `basic_union_find` from
`util/union_find.h`, an `obj_map` for the node assignment, and a
50000-step bound (returns `l_undef` on overrun).
* **Integration** in `seq_rewriter::reduce_re_eq` (with a re-entry
guard) and in `seq_regex::propagate_eq` / `propagate_ne` for ground
regexes; on `l_undef` we fall back to the existing axiomatisation.
* **`sls_seq_plugin`**: extend `OP_RE_DIFF` switch arms to also cover
`OP_RE_XOR`.
### Validation
* Full release build with MSVC + Ninja.
* `./test-z3 /a` -- 89/89 tests passing.
* `./test-z3 /seq smt2print_parse` -- PASS.
* Smoke tests with `(a|b)*` vs `(a*b*)*` (equal) and `a*` vs `(a|b)*`
(not equal) return the expected `sat`/`unsat` quickly.
---------
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Bumps [shell-quote](https://github.com/ljharb/shell-quote) from 1.7.3 to
1.8.4.
<details>
<summary>Changelog</summary>
<p><em>Sourced from <a
href="https://github.com/ljharb/shell-quote/blob/main/CHANGELOG.md">shell-quote's
changelog</a>.</em></p>
<blockquote>
<h2><a
href="https://github.com/ljharb/shell-quote/compare/v1.8.3...v1.8.4">v1.8.4</a>
- 2026-05-22</h2>
<h3>Commits</h3>
<ul>
<li>[Fix] <code>quote</code>: validate object-token shapes <a
href="4378a6e613"><code>4378a6e</code></a></li>
<li>[Dev Deps] update <code>@ljharb/eslint-config</code>,
<code>auto-changelog</code>, <code>eslint</code>, <code>npmignore</code>
<a
href="22ebec0434"><code>22ebec0</code></a></li>
<li>[Tests] increase coverage <a
href="9f3caa3190"><code>9f3caa3</code></a></li>
<li>[readme] replace runkit CI badge with shields.io check-runs badge <a
href="3344a047dd"><code>3344a04</code></a></li>
<li>[Dev Deps] update <code>@ljharb/eslint-config</code> <a
href="699c5113d1"><code>699c511</code></a></li>
</ul>
<h2><a
href="https://github.com/ljharb/shell-quote/compare/v1.8.2...v1.8.3">v1.8.3</a>
- 2025-06-01</h2>
<h3>Fixed</h3>
<ul>
<li>[Fix] remove unnecessary backslash escaping in single quotes <a
href="https://redirect.github.com/ljharb/shell-quote/issues/15"><code>[#15](https://github.com/ljharb/shell-quote/issues/15)</code></a></li>
</ul>
<h2><a
href="https://github.com/ljharb/shell-quote/compare/v1.8.1...v1.8.2">v1.8.2</a>
- 2024-11-27</h2>
<h3>Fixed</h3>
<ul>
<li>[Fix] <code>quote</code>: preserve empty strings <a
href="https://redirect.github.com/ljharb/shell-quote/issues/18"><code>[#18](https://github.com/ljharb/shell-quote/issues/18)</code></a></li>
</ul>
<h3>Commits</h3>
<ul>
<li>[meta] fix changelog tags <a
href="0fb9fd8441"><code>0fb9fd8</code></a></li>
<li>[actions] split out node 10-20, and 20+ <a
href="819bd842e0"><code>819bd84</code></a></li>
<li>[Dev Deps] update <code>@ljharb/eslint-config</code>,
<code>auto-changelog</code>, <code>npmignore</code>, <code>tape</code>
<a
href="fc564086c8"><code>fc56408</code></a></li>
<li>[actions] update npm for windows tests <a
href="fdeb0fd102"><code>fdeb0fd</code></a></li>
<li>[Dev Deps] update <code>@ljharb/eslint-config</code>,
<code>aud</code>, <code>tape</code> <a
href="b8a4a3b3f5"><code>b8a4a3b</code></a></li>
<li>[actions] prevent node 14 on ARM mac from failing <a
href="9eecafc048"><code>9eecafc</code></a></li>
<li>[meta] exclude more files from the package <a
href="4044e7fad4"><code>4044e7f</code></a></li>
<li>[Tests] replace <code>aud</code> with <code>npm audit</code> <a
href="8cfdbd8ec3"><code>8cfdbd8</code></a></li>
<li>[meta] add missing <code>engines.node</code> <a
href="843820e1a4"><code>843820e</code></a></li>
<li>[Dev Deps] add missing peer dep <a
href="4c3b88d792"><code>4c3b88d</code></a></li>
<li>[Dev Deps] pin <code>jackspeak</code> since 2.1.2+ depends on npm
aliases, which kill the install process in npm < 6 <a
href="80322ed591"><code>80322ed</code></a></li>
</ul>
<h2><a
href="https://github.com/ljharb/shell-quote/compare/v1.8.0...v1.8.1">v1.8.1</a>
- 2023-04-07</h2>
<h3>Fixed</h3>
<ul>
<li>[Fix] <code>parse</code>: preserve whitespace in comments <a
href="https://redirect.github.com/ljharb/shell-quote/issues/6"><code>[#6](https://github.com/ljharb/shell-quote/issues/6)</code></a></li>
<li>[Fix] properly support the <code>escape</code> option <a
href="https://redirect.github.com/ljharb/shell-quote/issues/5"><code>[#5](https://github.com/ljharb/shell-quote/issues/5)</code></a></li>
</ul>
<h3>Commits</h3>
<ul>
<li>[Refactor] <code>parse</code>: hoist <code>getVar</code> to module
level <a
href="b42ac73e39"><code>b42ac73</code></a></li>
<li>[Refactor] hoist some vars to module level <a
href="8f0c5c3c9d"><code>8f0c5c3</code></a></li>
<li>[Refactor] <code>parse</code>: use <code>slice</code> over
<code>substr</code>, cache some values <a
href="fcb2e1acd5"><code>fcb2e1a</code></a></li>
<li>[Refactor] <code>parse</code>: a bit of cleanup <a
href="6780ec5194"><code>6780ec5</code></a></li>
<li>[Refactor] <code>parse</code>: tweak the regex to not match nothing
<a
href="227d4742a0"><code>227d474</code></a></li>
</ul>
<!-- raw HTML omitted -->
</blockquote>
<p>... (truncated)</p>
</details>
<details>
<summary>Commits</summary>
<ul>
<li><a
href="ff166e2b63"><code>ff166e2</code></a>
v1.8.4</li>
<li><a
href="4378a6e613"><code>4378a6e</code></a>
[Fix] <code>quote</code>: validate object-token shapes</li>
<li><a
href="22ebec0434"><code>22ebec0</code></a>
[Dev Deps] update <code>@ljharb/eslint-config</code>,
<code>auto-changelog</code>, <code>eslint</code>, `npmig...</li>
<li><a
href="9f3caa3190"><code>9f3caa3</code></a>
[Tests] increase coverage</li>
<li><a
href="3344a047dd"><code>3344a04</code></a>
[readme] replace runkit CI badge with shields.io check-runs badge</li>
<li><a
href="699c5113d1"><code>699c511</code></a>
[Dev Deps] update <code>@ljharb/eslint-config</code></li>
<li><a
href="487a9b41a7"><code>487a9b4</code></a>
v1.8.3</li>
<li><a
href="01faafff97"><code>01faaff</code></a>
[Fix] remove unnecessary backslash escaping in single quotes</li>
<li><a
href="b19fc77e66"><code>b19fc77</code></a>
v1.8.2</li>
<li><a
href="59d29ea694"><code>59d29ea</code></a>
[Fix] <code>quote</code>: preserve empty strings</li>
<li>Additional commits viewable in <a
href="https://github.com/ljharb/shell-quote/compare/v1.7.3...v1.8.4">compare
view</a></li>
</ul>
</details>
<details>
<summary>Maintainer changes</summary>
<p>This version was pushed to npm by <a
href="https://www.npmjs.com/~ljharb">ljharb</a>, a new releaser for
shell-quote since your current version.</p>
</details>
<details>
<summary>Install script changes</summary>
<p>This version adds <code>prepublish</code> script that runs during
installation. Review the package contents before updating.</p>
</details>
<br />
[](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores)
Dependabot will resolve any conflicts with this PR as long as you don't
alter it yourself. You can also trigger a rebase manually by commenting
`@dependabot rebase`.
[//]: # (dependabot-automerge-start)
[//]: # (dependabot-automerge-end)
---
<details>
<summary>Dependabot commands and options</summary>
<br />
You can trigger Dependabot actions by commenting on this PR:
- `@dependabot rebase` will rebase this PR
- `@dependabot recreate` will recreate this PR, overwriting any edits
that have been made to it
- `@dependabot show <dependency name> ignore conditions` will show all
of the ignore conditions of the specified dependency
- `@dependabot ignore this major version` will close this PR and stop
Dependabot creating any more for this major version (unless you reopen
the PR or upgrade to it yourself)
- `@dependabot ignore this minor version` will close this PR and stop
Dependabot creating any more for this minor version (unless you reopen
the PR or upgrade to it yourself)
- `@dependabot ignore this dependency` will close this PR and stop
Dependabot creating any more for this dependency (unless you reopen the
PR or upgrade to it yourself)
You can disable automated security fix PRs for this repo from the
[Security Alerts page](https://github.com/Z3Prover/z3/network/alerts).
</details>
Signed-off-by: dependabot[bot] <support@github.com>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
This bug was discovered by claude analyzing the descrepency of outputs
in https://github.com/Z3Prover/bench/discussions/2516. The benchmark was
edited - a line required stats was commented out - and this exposed the
scanner inconsistent behavior.
read_comment and read_multiline_comment handled end-of-line newlines as
new_line(); next();, the reverse of the main scan() loop's next();
new_line();. This left m_spos one higher on the line following a
comment, shifting every reported column on that line by +1 (e.g. a (pop)
error reported column 5 instead of 4 when the previous line was a
comment). Reorder both comment readers to match scan() so column numbers
are consistent regardless of whether the preceding line is a comment.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
`seq_rewriter.cpp` was missing several regex-concat normalizations
around `re.all` (`Σ*`), causing avoidable growth and missed
simplifications. This update fills the four gaps: nullable absorption,
guarded union distribution, intersection suffix elimination, and
nested-star collapse.
- **Nullable/full-seq absorption (A1)**
- Generalizes `Σ*·R → Σ*` and `R·Σ* → Σ*` beyond `Σ*·Σ*`.
- Applies when `R` is interpreted, nullable, and has `min_length = 0`.
- **Guarded distribution over union (A2)**
- Adds `Σ*·(R1 ∪ R2)` distribution when at least one arm is already
`Σ*`-headed.
- Rebuilds via normalized union so the redundant arm collapses to `Σ*`.
- **Intersection + full-seq tail elimination (A3)**
- Adds `(R1 ∩ … ∩ Rn)·Σ* → (R1 ∩ … ∩ Rn)` when every intersection leaf
already ends in `Σ*`.
- **Nested star concat collapse (A4)**
- Adds `R*·(R*·X) → R*·X`, covering non-adjacent star patterns not
handled by the prior adjacent-only rewrite.
```cpp
if (re().is_full_seq(a) && accepts_empty_word(b)) result = a; // A1
if (re().is_full_seq(a) && re().is_union(b, u1, u2) && ...) ... // A2
if (re().is_intersection(a, u1, u2) && re().is_full_seq(b) && ...) result=a; // A3
if (re().is_star(a, a1) && re().is_concat(b, b1, b2) && re().is_star(b1,b3) && a1==b3) result=b; // A4
```
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
Fixes#9022.
## Problem
After a `(push)`, Z3 could incorrectly report `unsat` for satisfiable
FPA formulas in which an uninterpreted function returns a floating-point
value (e.g. `int_to_fp`). The example in #9022 has a single `push` and a
single `check-sat` (no `pop`), so the `m_rw.reset()` added in
`pop_scope_eh` by #8712 does not apply.
## Root cause
`theory_fpa` lazily converts FP constraints to bit-vectors and asserts
the equivalences/side conditions as **unit theory axioms**
(`assert_cnstr` → `mk_th_axiom`, which `assign`s the literal at the
current decision level).
For `fp.to_*` terms (`fp.to_real`, `fp.to_ubv`, …) the conversion
equality and side conditions are emitted **only** in
`internalize_term()`, which runs exactly once. The `else if` branch for
fpa-family conversion terms in `relevant_eh` previously did nothing.
These unit axioms are level-local: on DPLL backtracking the assignment
is undone, but `internalize_term()` is not re-run for the
already-internalized term (in particular when the term lives at the
user-`push` base level, where its clause is not a reinit clause). The
side conditions include the axioms linking FP uninterpreted functions to
their bit-vector counterparts (`int_to_fp(i) =
fp(extract(int_to_fp_bv(i)))`). Once lost, `int_to_fp_bv` becomes
unconstrained, enabling an unsound `unsat`. This is exactly the behavior
described in #8345/#9022 (and why the result flips with vs. without
`push`).
## Fix
`relevant_eh` re-fires on relevancy re-propagation after a backtrack.
Re-emit the conversion equality and side conditions for `fp.to_*` terms
there, mirroring `internalize_term`, so the FP↔BV linking axioms stay in
force across backtracking. On an `m_conversions` cache hit this just
re-asserts the (hash-consed) conversion equality and a `true` side
condition, so it adds no new terms and no clause bloat. The change only
adds sound constraints, so it can never turn a satisfiable formula
`unsat`.
## Validation
- #9022 reproducer: no longer reports `unsat` across many random seeds
and longer timeouts; a model (`sat`) is still found (the problem is
inherently hard quantified FP + nonlinear arithmetic, so timeouts are
expected).
- #8345 reproducer: first `check-sat` still `unsat` (the negated
quantifier axiom is valid).
- Additional incremental push/pop FP cases with
`fp.to_real`/`fp.add`/`fp.sub` and FP-returning UFs: correct, consistent
results.
- `test-z3 /a`: all 89 unit tests pass.
- Debug build (soundness assertions enabled): no assertion failures on
the above cases.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
MSVC ASan reports showed a container-overflow in LP tableau pivoting,
reproducible from both examples and solver tests (issue #9781). The
failure came from reading a `column_cell` through a reference after
pivoting removed that entry from the backing column.
- **Root cause**
- `pivot_column_tableau` and the analogous Diophantine elimination loop
both held `auto& c = column.back()` across a call
(`pivot_row_to_row_given_cell`) that immediately removes that very cell
from the column via `remove_element`.
- After the mutation, the subsequent read `c.var()` used for bookkeeping
observed invalid memory.
- **Change**
- Record the affected row in the bookkeeping set (`m_touched_rows` /
`m_changed_rows`) by reading `c.var()` **before** the pivot call, while
the back cell is still valid.
- Make `static_matrix::pivot_row_to_row_given_cell` return `void`
instead of `bool`. Its result (`!rowii.empty()`) was always `true`: both
callers keep the matrix at full row rank (the tableau basis columns form
an identity submatrix; the Diophantine `m_l_matrix` stays invertible),
so an elementary row operation can never empty a row. The dead `if
(!...) return false;` early-exit in `pivot_column_tableau` is removed
and replaced with a `SASSERT(!rowii.empty())` documenting the invariant.
- **Affected code paths**
- `src/math/lp/static_matrix.h`, `src/math/lp/static_matrix.cpp`,
`src/math/lp/static_matrix_def.h`
- `src/math/lp/lp_core_solver_base_def.h`
- `src/math/lp/dioph_eq.cpp`
- **Behavioral impact**
- No algorithmic change to pivoting.
- Removes the stale-reference hazard in the loops that repeatedly
eliminate entries from a column.
```c++
while (column.size() > 1) {
auto& c = column.back();
SASSERT(c.var() != piv_row_index);
if (m_touched_rows != nullptr)
m_touched_rows->insert(c.var());
m_A.pivot_row_to_row_given_cell(piv_row_index, c, j);
}
```
- **Verification**
- Reproduced the exact issue #9781 failure on a local ASan build
(`container-overflow` in `pivot_column_tableau`) using the pre-fix code,
and confirmed it is gone with this change.
- The 4 reported tests pass clean under ASan: `c_example`,
`cpp_example`, `test-z3 get_implied_equalities`, `test-z3 quant_solve`.
- Full `test-z3 /a` suite: 89 passed, 0 failed, 0 ASan errors.
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
Co-authored-by: Nikolaj Bjorner <nbjorner@microsoft.com>
Co-authored-by: Lev Nachmanson <levnach@hotmail.com>
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
The page
https://github.com/Z3Prover/z3/blob/master/README-CMake.md#adding-z3-as-a-dependency-to-a-cmake-project
advises using the CMake FetchContent feature to include z3 as source
into other CMake project. I'm trying to do this to use Z3 within a
ClangTidy checker. This is one of a series of PR's aimed at getting Z3
to compile cleanly when included this way.
This initial PR fixes all the errors, allowing the compilation to
succeed. Subsequent diffs will address warnings.
I tested only the CMake compilation, on a Mac.
*Missing Z3_THROWs*
Update z3++.h to use Z3_THROW in a couple of places. Clang compiles with
exceptions disabled so we get messages like:
```
/Users/daviddetlefs/llvm-project/build_dbg/_deps/z3-src/src/api/c++/z3++.h:4928:17: error: cannot use 'throw' with exceptions disabled4928 | throw exception("rcf_num objects from different contexts");
```
NOTE TO REVIEWERS: I'm not complete clear on the usage conventions for
Z3_THROW. With exception disabled, it seems like the throwing function
will just continue. If there's somethign else that should be done, like
setting some error state, please let me know.
*CMake component name collision*
There was an error at the CMake level, a name collision (on "opt").
Apparently CMake components are named using a flat namespace, so it's
easy to see how this could occur. It seems to me that the right global
way to fix this would be to encourage people to use some form of
"qualified name" convention in naming their component. The fix I chose
was a local version of this, changing the Z3 component name to z3_opt.
(It didn't seem feasible to make the change in clang.)
NOTE TO REVIEWERS: If you think this is OK, please let me know if
a) You'd like me to also change the name of the opt directory, to keep
thecomponent-name == directory-name invariant, and
b) You'd like me to make this z3_ change more globally, to future-proof
(somewhat) against similar component name collisions.
`seq_plugin::edit_distance_with_updates` used the left-string DP index
when checking whether the right string could accept an insertion from
the `d[i][j - 1]` transition. This miscomputed updateable edit distance
and could suppress valid repair proposals when `i != j`.
- **Bug fix**
- Change the right-side insertion guard in
`src/ast/sls/sls_seq_plugin.cpp` from `b.can_add(i - 1)` to `b.can_add(j
- 1)`.
- This aligns the mutability check with the DP transition being
evaluated and with the existing update-generation logic below it.
- **Regression coverage**
- Add a focused test in `src/test/sls_seq_plugin.cpp` for an asymmetric
variable/value layout on the right-hand side.
- The test asserts that the repair logic admits the right-side add at `j
- 1`, which is the case that the previous index mixup could reject.
- **Reference**
- The updated condition now matches the intended transition semantics:
```cpp
if (d[i][j - 1] < u[i][j] && b.can_add(j - 1)) {
m_string_updates.reset();
u[i][j] = d[i][j - 1];
}
```
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
Variables to be projected may not be assigned in the model (e.g.
grounded auxiliary variables that are don't-cares). Enable model
completion in the arith `qe_project` so their evaluation yields concrete
numerals, matching the behavior of the native MBP arith projector.
Two call sites in `arith_project_util`
(`src/muz/spacer/spacer_qe_project.cpp`) now install a
`model::scoped_model_completion` before evaluating projected variables
against the model.
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
On macOS, libz3java.dylib was built without an rpath to find libz3.dylib
in the same directory. When Java loaded the JNI library, the dynamic
linker could not resolve the libz3 dependency, causing
UnsatisfiedLinkError.
Three fixes:
- mk_util.py: add -Wl,-rpath,@loader_path to the macOS JNI link command
- CMakeLists.txt: set MACOSX_RPATH, BUILD_RPATH, INSTALL_RPATH for
z3java target; remove duplicate headerpad block
- update_api.py: improve Native.java error message to show the root
cause from both load attempts instead of only the fallback error
Co-authored-by: Copilot <223556219+Copilot@users.noreply.github.com>
`src/ast/sls/sls_seq_plugin.cpp::is_sat()` had two unconditional abort
paths (`VERIFY(false)` and `NOT_IMPLEMENTED_YET()`) reachable from valid
string formulas under SLS. This changes those paths to graceful
repair/fail behavior so SLS can continue search instead of terminating
the process.
- **Length coherence fallback no longer aborts**
- Replaced the terminal `VERIFY(false)` in the `str.len` coherence block
with a normal `return false` repair failure path.
- Effect: failed local repair is propagated to the outer SLS loop
instead of crashing.
- **Implemented `seq.last_indexof` coherence handling**
- Replaced `NOT_IMPLEMENTED_YET()` with concrete coherence logic:
- read current `x`, `y`, and `e`,
- compute `actual = sx.last_indexof(sy)`,
- update `e` when `e != actual`,
- otherwise continue.
- Effect: formulas containing `seq.last_indexof` are handled in SLS
coherence checks instead of aborting.
- **No new hard-abort behavior introduced**
- In the new `last_index` block, non-numeral `e` is handled by graceful
`return false` (repair failure), not assertion abort.
```cpp
if (seq.str.is_last_index(e, x, y) && seq.is_string(x->get_sort())) {
auto sx = strval0(x), sy = strval0(y);
rational val_e;
if (!a.is_numeral(ctx.get_value(e), val_e))
return false;
rational actual(sx.last_indexof(sy));
if (val_e == actual) continue;
update(e, actual);
return false;
}
```
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
The doctests for Statistics.__len__ and Statistics.__getitem__ in
src/api/python/z3/z3.py asserted a fixed counter count (len(st) == 7).
This is fragile because the ":time" entry is only added to statistics
when the elapsed wall-clock time of check() is non-zero (see
collect_timer_stats in src/solver/check_sat_result.h). On fast native
builds, ":time" rounds to 0 and is omitted; under slow environments
(e.g. riscv64 under qemu emulation), it becomes non-zero and is
included, changing len(st).
Fix this by checking the presence of statistics rather than an exact
count.
Signed-off-by: Julien Stephan <jstephan@baylibre.com>
`add_substr_edit_updates` uses a `HashSet` to deduplicate substrings of
`val_other`, but on a duplicate hit it `break`s the inner loop instead
of skipping just that entry. This causes all longer substrings from the
same starting position to be silently dropped as repair candidates.
## Change
- **`src/ast/sls/sls_seq_plugin.cpp`** — replace `break` with `continue`
in the inner substring-enumeration loop.
```cpp
// Before — exits the inner loop on first duplicate, missing e.g. "ab" in "aab"
if (set.contains(sub))
break;
// After — skips only the duplicate, continues with longer substrings at same offset
if (set.contains(sub))
continue;
```
For `val_other = "aab"`, the old code never proposed `"ab"` (i=1, j=2)
as a repair candidate because the duplicate `"a"` (i=1, j=1) terminated
the inner loop prematurely.
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
`src/ast/ast_smt_pp.cpp` emitted a compiler warning on macOS because
`quantifier_kind::choice_k` was not handled in
`smt_printer::visit_quantifier`. This change makes the switch exhaustive
and preserves printer behavior for existing quantifier kinds.
- **Problem**
- `visit_quantifier` handled `forall_k`, `exists_k`, and `lambda_k`, but
omitted `choice_k`, triggering `-Wswitch`.
- **Change**
- Added an explicit `choice_k` branch in the quantifier-kind switch in
`/tmp/workspace/Z3Prover/z3/src/ast/ast_smt_pp.cpp`.
- The branch prints `choice` in SMT output, consistent with how other
quantifier headers are emitted.
- **Code snippet**
```cpp
switch (q->get_kind()) {
case forall_k: m_out << "forall "; break;
case exists_k: m_out << "exists "; break;
case lambda_k: m_out << "lambda "; break;
case choice_k: m_out << "choice "; break;
}
```
---------
Co-authored-by: copilot-swe-agent[bot] <198982749+Copilot@users.noreply.github.com>
While working on https://github.com/Z3Prover/z3/pull/9405, I noticed
that euf_mam.cpp code was slightly out of sync with mam.cpp and did some
redundant work.
Co-authored-by: Can Cebeci <t-cancebeci@microsoft.com>
