2026年2月3日火曜日

Cadical バグを修正

 多分バグだと思いますが、GCCでは警告がないのかもしれません。

radix sort部分でクラッシュしました。コパイにお願いすると、VisualStudioのエラーと一致する指摘となりました。完全に書き換えるコードの提案をされて、安直に置き換えてみるとエラーは消失しました。凄い。C++ソースも完全に理解しているのですね。



c == b の比較で vector がエラーになる理由は、このコードが イテレータ同士の比較をしているように見えて、実際には “別コンテナのイテレータを比較している” 可能性が非常に高いからです。

🔍 問題の本質：c と b は「同じコンテナのイテレータ」ではない

コードの該当部分を抜き出すと：

I a = first, b = last, c = a;
...
std::vector<T> v;
...
if (!initialized) {
    v.resize(n);
    b = v.begin();
    initialized = true;
}
...
I d = (&*c == &*a) ? b : a;
...
c = d;
...
if (c == b) {
    for (size_t i = 0; i < n; i++)
        a[i] = b[i];
}

ここでのポイントは：

✔ a と c は 元の配列（FIRST〜LAST） のイテレータ

✔ b は vector v の begin()

❌ つまり c == b は 異なるコンテナのイテレータ比較

C++ の規格では：

異なるコンテナのイテレータを比較することは未定義動作（UB）

未定義動作なので、クラッシュしたり、比較が常に false になったり、ランダムな挙動をします。

🧨 なぜこのコードは UB を踏んでしまうのか？

c は毎ループで a または b に切り替わる。

  • c = a のとき → 元の配列のイテレータ
  • c = b のとき → vector のイテレータ

最後に

if (c == b)

を行うが、c が元配列のイテレータのままなら 異なるコンテナのイテレータ比較 になる。

🛠 解決策：イテレータ比較ではなく「どちら側か」を示すフラグを使う

最も安全で一般的な修正は：

✔ c が vector 側を指しているかどうかを bool で管理する

例：

bool using_vector = false;
...
if (!initialized) {
    v.resize(n);
    b = v.begin();
    initialized = true;
}
...
I d;
if (&*c == &*a) {
    d = b;
    using_vector = true;
} else {
    d = a;
    using_vector = false;
}
c = d;
...
if (using_vector) {
    for (size_t i = 0; i < n; i++)
        a[i] = b[i];
}

これなら 異なるコンテナのイテレータ比較を避けられる。

🎯 まとめ

問題点 理由
c == b がクラッシュ 異なるコンテナのイテレータ比較は未定義動作
なぜ起きる？ c は元配列 or vector のどちらかを指す可能性がある
解決策 イテレータ比較ではなく、どちら側を使っているかを bool で管理

必要なら、この radix sort 全体を 安全に書き直したバージョン も作れます。
あるいは、あなたのプロジェクトに合わせて 最適化版 を作ることもできますよ。


了解、孝幸さん。
あなたのコードは CaDiCaL の radix sort 実装をベースにしていますが、イテレータが別コンテナを指す可能性があるのに比較してしまうという UB（未定義動作）が潜んでいました。

そこで、イテレータ比較を完全に排除し、状態フラグで安全に制御するバージョンを用意しました。
元のアルゴリズム構造は維持しつつ、C++ として安全に動くように書き直しています。

✅ 安全に書き直した rsort（イテレータ比較なし・UBなし）

template <class I, class Rank>
void rsort(I first, I last, Rank rank) {
    using T = typename std::iterator_traits<I>::value_type;
    using R = typename Rank::Type;

    assert(first <= last);
    const size_t n = last - first;
    if (n <= 1) return;

    const size_t l = 8;
    const size_t w = (1 << l);
    const unsigned mask = w - 1;

    size_t count[w];

    I a = first;
    I c = a;

    std::vector<T> v;
    I b;                 // vector 側の begin()
    bool using_vector = false;  // ★ どちら側を使っているかを管理

    R upper = 0, lower = ~upper;
    R shifted = mask;
    bool bounded = false;

    R masked_lower = 0, masked_upper = mask;

    for (size_t i = 0; i < 8 * sizeof(rank(*first)); i += l, shifted <<= l) {

        if (bounded && (lower & shifted) == (upper & shifted))
            continue;

        memset(count + masked_lower, 0,
               (masked_upper - masked_lower + 1) * sizeof *count);

        const I end = c + n;
        bool sorted = true;
        R last_bucket = 0;

        for (I p = c; p != end; p++) {
            const auto r = rank(*p);
            if (!bounded) {
                lower &= r;
                upper |= r;
            }
            const auto m = (r >> i) & mask;
            if (sorted && last_bucket > m)
                sorted = false;
            last_bucket = m;
            count[m]++;
        }

        masked_lower = (lower >> i) & mask;
        masked_upper = (upper >> i) & mask;

        if (!bounded) {
            bounded = true;
            if ((lower & shifted) == (upper & shifted))
                continue;
        }

        if (sorted)
            continue;

        size_t pos = 0;
        for (R j = masked_lower; j <= masked_upper; j++) {
            const size_t delta = count[j];
            count[j] = pos;
            pos += delta;
        }

        if (!using_vector) {
            v.resize(n);
            b = v.begin();
        }

        I d = using_vector ? a : b;  // ★ ここで切り替え
        bool next_using_vector = !using_vector;

        for (I p = c; p != end; p++) {
            const auto m = (rank(*p) >> i) & mask;
            d[count[m]++] = *p;
        }

        c = d;
        using_vector = next_using_vector;
    }

    if (using_vector) {
        for (size_t i = 0; i < n; i++)
            a[i] = b[i];
    }

#ifndef NDEBUG
    for (I p = first; p + 1 != last; p++)
        assert(rank(p[0]) <= rank(p[1]));
#endif
}

🔒 このバージョンが安全な理由

問題点 修正内容
異なるコンテナのイテレータ比較 (c == b) bool using_vector で状態管理
&*c == &*a のような危険なアドレス比較 完全に排除
イテレータがどちらの配列を指すか不明瞭 using_vector と next_using_vector で明確化
UB（未定義動作） ゼロ

🎁 さらに改善したい場合

  • std::array<size_t, w> を使って stack allocation を明示化
  • std::span を使って safer pointer arithmetic
  • std::bit_width を使って動的にパス数を決定
  • std::pmr::vector でアロケーション最適化

必要なら、これらも組み込んだ モダン C++20/23 版の高速 radix sort も作れます。

もっと最適化したい、あるいは CaDiCaL の他の部分も安全化したい場合は続けてどうぞ。



投稿者 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)