Erroneous equality test in tracing mode

[eric-j-ason]

0000000a  EQ
  [-29] [ "a", "b" ]
  [-28] [ "a" ]
  [+28] true

Running the code below yields an exit status of zero when running with tracing, but non-zero when running without tracing. In the trace, one can find the equality operation quoted above. Exciting!

Funnily, the smallest example code I can produce is over 100 lines long. It's ability to reproduce the bug depends on such things as what happens in functions that are never called, how many lines of whitespace there are, how long variable names are, and sometimes what characters they contain. Try removing or changing something seemingly irrelevant, and you'll see (probably)!

function p(v) {
    print(v);
    print("");
}

let f = () => null;

function uuuuuu(a) {
    for (let e in a) {

        if (a[0] == a[0]) {
            return false;
        }
    }
    return true;
}

function fold(bbbb, aaaa, c) {
    let a = aaaa;
    for (let e in c) {
        a = bbbb(a, e);
    }
    return a;
}

let ss = (f, i, a) => fold((a, b) => f(b, a), i, reverse(a));

function bool(x) {
    return x ? true : false;
}

function b(x) {
    assert(type(x) == "array");
    return bool(fold((a, b) => a && b, true, x));
}

function a() {
    return bool();
}

function tttttttt(arrs) {
    assert(type([]) == "array");
    assert(b(map(arrs, x => type(x) == "array")));
    assert(uuuuuu([]));

    let n = length(arrs);
    let m = length(arrs[0]);

    let z = [];
    for (let j = 0; j < m; j++) {
        z[j] = [];
        for (let i = 0; i < n; i++) {
            z[j][i] = arrs[i][j];
        }
    }

    return z;
}

let g = () => null;

function mmmmm(func, aaaa) {
    return map(tttttttt(aaaa), x => func(...x));
}

let nnnnn = (func, ...aaaa) => mmmmm(func, aaaa);

function equal(x, y) {
    if (x == y) {
        return true;
    }

    let tx = type(x);
    let ty = type(y);

    if (tx == "array" && ty == "array") {
        return length(x) == length(y) && b(nnnnn(equal, x, y));
    }

    if (tx == "object" && ty == "object") {
        let kx = sort(keys(x));
        let ky = sort(keys(y));
        return equal(kx, ky) && b(nnnnn(k => equal(x[k], y[k]), kx));
    }

    return;
}

let s = () => fol((a, b) => null, null, null);

function rrrrr(a, b) {
    assert(type(x) == null);
    assert(type(x) == null);
    for (let i = 0; i < st - st; i++) {}
    return q;
}

function x() {
    return x();
}
assert(ss((a) => a*0, 0, [0]) == 0);
assert(ss((a) => a*0, 0, []) == 0);
assert(ss(() => a*0, 0, []) == 0);
assert((a) => null);
assert(equal([], []));
assert(equal({a: 0, b: "aaaa"}, {a: 0, b: "aaaa"}));
assert(equal({a: 0}, {a: 0, b: "aaaa"}));

# ucode -S example.uc 2>/dev/null
# echo $?
254
# ucode -t -S example.uc 2>/dev/null
# echo $?
0

[eric-j-ason]

It was just pointed out to me that OpenWrt, where I am running this, doesn't use the latest version.

[jow-]

What architecture does this happen on? I cannot reproduce it on x86/64

Edit: can reproduce on MIPS, will investigate.

[eric-j-ason]

I see you could reproduce it on MIPS. I'm relieved to hear that.

My architecture is armv7l, according to uname -m.

I'm running the version that comes with OpenWrt, which would be c7d84aae09691a99ae3db427c0b2463732ef84f4.

[jow-]

Turns out this is the same issue as #165 which has already been addressed in https://github.com/jow-/ucode/commit/08c2ae23b5dd2deb92f5270ae4fb2094ebfc8a9e

I'll take care of pushing a package update to OpenWrt asap.

Problem is/was that the long difference of two pointer addresses was stored into an int8_t variable which could truncate the result in such a way that the actual memory address difference was turned into 0, leading to false equality result.

Since the actual memory addresses depend on the surrounding activity (how much heap memory was allocated and freed etc.) you get the seemingly unpredictable behavior.

[eric-j-ason]

Great! I look forward to pulling in the new version through OpenWrt.

[eric-j-ason]

Looking at the fix, I have a question.

Is delta, an int, guaranteed to be large enough to hold the difference between two values of type intptr_t?

In any case, I think lines 2041-2046 can be replaced by a a simple expression.

https://github.com/jow-/ucode/blob/07c03173d4e6a30953f92fa88ed29b0b956c9106/types.c#L2041-L2046

Like so:

delta = ((uintptr_t)v2 > (uintptr_t)v1) - ((uintptr_t)v2 < (uintptr_t)v1)

That way, delta also needs not be larger than an int8_t.

[jow-]

delta is also used to store the int return value of strcmp() in the string compare case, so it is better to keep it int wide.

[eric-j-ason]

Never mind! I conflated things. There is no pointer difference being stored in delta since the fix.

(Well, I do think that it would be nice to calculate the value as just one expression, as opposed to doing explicit if statements, but it's not necessary for correct behaviour.)

[eric-j-ason]

I'll take care of pushing a package update to OpenWrt asap.

I see you have done it. Thanks!

Will this be taken up by the openwrt-23.05 branch and perhaps included in a 23.05.1 release? I don't know what the development strategy for OpenWrt is like, but I would say that this fix is essential to include wherever ucode is used.

[jow-]

Yes it will be picked into the 23.05 branch soon and be part of the 23.05.1 service release.