记一个难以发现的 UB

观察以下代码:

vector X, Y, A, val;
inline int ls(int p) { return p > 1, p = X.size();
    X.push_back(0), Y.push_back(0);
    X[p] = solve(ls(i), l, mid);
    Y[p] = solve(rs(i), mid + 1, r);
    // do something
    return val[i];
}

这是一份标准的线段树分治代码,其中数组 (A) 是给定的,(val)(solve) 函数调用之前已经分配好了内存,而 (X)(Y) 的内存空间则是动态分配的。

当我在本地测试完整的代码时,不会出现任何的异常。当我将代码提交到学校的 OJ 上时,却发现输出的结果不符合预期,而且对于同样的输入,输出却和本地有所出入。

经过艰难的排查,我最终发现问题出现在了 (solve) 函数中,即上述代码的第 (8)(9) 行。我尝试将这两行替换为下面的代码:

int lp = solve(ls(i), l, mid);
X[p] = lp;
int rp = solve(rs(i), mid + 1, r);
Y[p] = rp;

这时 (X[p])(Y[p]) 的值就从错误的 (0) 变成了正确的答案。

我不禁陷入沉思,为何看似逻辑完全相同的代码,产生的效果却大相径庭?直到我发现第 (7) 行代码中的操作:

X.push_back(0), Y.push_back(0);

有没有可能,在第 (8) 行和第 (9) 行的赋值过程中,编译器先对等号左边的表达式进行计算,得到 (X[p])(Y[p]) 的左值引用,然后再计算了等号右边的表达式,调用了 (solve) 函数呢?

这样一切就解释得通了,(X[p])(Y[p]) 的引用先被取出,然后在递归调用 (solve) 函数的过程中,执行到了第 (7) 行的 (push_back) 函数,使得 (vector) 重新分配了堆空间,导致 (X[p])(Y[p]) 的引用失效。于是,在赋值的过程中,我们对一个已经被释放掉的空间进行了修改,且不说有没有访问到不该访问的位置,当前 (vector) 中真实的 (X[p])(Y[p]) 也没能被赋为正确的值。

现在我们弄清楚发生 UB 的过程了。在这之后,我又进行了一些测试,目的在于弄清楚产生两种不同情况的本质原因。继续观察以下代码:

#include 
using namespace std;
int func1() {
    cout 

当我使用 g++ 作为编译器,输出结果如下:

func1
func2
func3

当我使用 clang 作为编译器,输出结果如下:

func3
func2
func1

归根结底,产生这两种区别的原因还是在于编译器的实现。从上面的例子可以看出,g++ 在执行赋值语句的过程中,会从左往右进行运算,而 clang 则是从右往左。

在我的本机上,常用的编译器是 apple-clang,因此上文中线段树分治的代码从右往左执行赋值操作,不会产生引用失效的问题。而学校 OJ 的默认编译器为 g++,自然就出现与预期相违的情况了。

个人认为,对于这两种执行顺序,应当是从右往左更加符合正常人的逻辑,毕竟如 A = B = C 这样的连续赋值语句也是从右往左执行的。

总而言之,为了不触发此类未定义行为,在写代码时还需要多注意一下。对于本文开头的例子,最好还是在调用 (solve) 函数之前先对 (X)(Y) 的内存空间进行 (reserve),这样就不会在 (push_back) 时出现引用失效的问题了。

文章来源于互联网:记一个难以发现的 UB

THE END
分享
二维码