Great!
Great!
Posted May 18, 2015 16:44 UTC (Mon) by tterribe (guest, #66972)In reply to: Great! by ibukanov
Parent article: Rust 1.0 released
Some examples:
https://git.xiph.org/?p=opus.git;a=commitdiff;h=d6b56793d...
https://git.xiph.org/?p=opus.git;a=commitdiff;h=58ecb1ac1...
I agree with ms_43: the only way this works is if you actually test with fault-injection. We had next to no allocations in libopus (just a few mallocs when setting up the encoder and decoder, absolutely nothing when encoding or decoding a frame), and we _still_ had to do this to catch our bugs, and it's not like this is our first project in C.
Posted May 18, 2015 17:22 UTC (Mon)
by ibukanov (subscriber, #3942)
[Link] (7 responses)
These bugs happen when NaN model interacts with the code that does not follow it, which is a nice demonstration of my point of poor language/library support for doing that style in the rest of code.
Now consider what happens if the code with those bugs when the whole code is compiled as asm.js target which defines precisely what should happen when code accesses unallocated memory, a sort of NaN for pointers. The end result would be no crash or possibilities for arbitrary code execution, but rather a corrupted video frame.
Posted May 18, 2015 20:51 UTC (Mon)
by tterribe (guest, #66972)
[Link] (6 responses)
But I don't even buy the argument about interacting with "code that does not follow [the NaN model]". Take the first change for example:
- if (x>=8)
The behavior differs precisely because and only when the comparison follows the NaN model, and while in this case the difference happened to lead to a crash later on because of a float->int conversion, there are plenty of other cases where it would simply produce a wrong result. I do not believe that every time a developer writes a comparison against a float, they are asking themselves, "What happens if one of these values is NaN (or Inf)?" and even when they do ask, that they reason correctly about what *should* happen without testing it. Think about things like convergence tests, etc., that could lead to infinite loops. There's no "NaN for pointers" that is going to fix that.
Posted May 18, 2015 21:16 UTC (Mon)
by ibukanov (subscriber, #3942)
[Link] (5 responses)
This is a tooling issue. Implementation can generate a stacktrace when it generates NaN the first time.
> The behavior differs precisely because and only when the comparison follows the NaN model,
NaN model in this case does not add an extra branch. If one has a test coverage for both branches for normal code, that test coverage covers NaN case as well.
> Think about things like convergence tests, etc., that could lead to infinite loops.
I can trivially kill a media application that stuck in ∞ loop. Compare that with a bug that leads to arbitrary code execution coming from a randomly downloaded media file. These are vastly different outcomes in consequences. Similarly, compare the same buggy C code that corrupts memory compiled as asm.js and run in a browser (effectively forcing something like NaN model for C pointers) and run as a native desktop application. I personally would vastly prefer to experience the bug in its former incarnation rather than latter.
In general I do not claim that NaN model leads to less bugs. Rather the claim is that the total cost of consequences of those bugs is lower.
Posted May 19, 2015 14:38 UTC (Tue)
by nybble41 (subscriber, #55106)
[Link] (4 responses)
I think the real point here is that branch coverage is _insufficient_. The tests should exercise the boundaries of all of the "equivalence classes", groups of inputs which are expected to cause similar behavior in the code. That includes covering all the branches, but in this case a NaN input—or an input which can cause NaN in an intermediate calculation—would also be a separate equivalence class, even if the same branches are used (because the real branches are hidden in the ALU hardware).
NaN inputs, or ranges of inputs which result in NaN, represent discontinuities in the program, and discontinuities need to be tested. Branches are merely a special case of this rule, discontinuities in a piecewise-defined function which determines the control flow.
Posted May 19, 2015 16:40 UTC (Tue)
by ibukanov (subscriber, #3942)
[Link] (3 responses)
Ideally this should be expressed by types. For example, consider the following fragment which should report an error if z becomes NaN, not only when it is negative:
double x, y, z;
With better typesystem the relational operators could only be applied to non-NaN doubles requiring one to write something like:
double x, y, z;
Now, this looks like a contradiction to my assertion that NaN model reduces the number of branches and the number of tests, but consider if NaN would not be supported. Then the code becomes using a common C practice to return a false value to indicate an error:
double x, y, z;
Notice that now there 5 branches rather than 3 with NaN. This reduction comes from the multiplication having well-defined semantic for NaN values. In turn this directly translates into simpler test coverage as to test the code path leading to error with NaN values it is sufficient to arrange for f1 to return NaN, rather than making f1, f2 and mult to return false.
Posted May 19, 2015 19:06 UTC (Tue)
by nybble41 (subscriber, #55106)
[Link]
I don't think anyone has really suggested removing support for NaN—sum types of this kind are indeed very useful for error handling and other tasks—but merely that the NaN cases need to be tested separately from the non-NaN cases.
> ... In turn this directly translates into simpler test coverage as to test the code path leading to error with NaN values it is sufficient to arrange for f1 to return NaN, rather than making f1, f2 and mult to return false.
Treating f1() and f2() as the inputs, I would define six equivalence classes based on the _product_ of the inputs, z, and how z is used in the condition: -Inf, <0, 0, >0, +Inf, NaN. After all, the point of the exercise is not to test the machine's multiplication algorithm, and the behavior of the code depends only on the product and not the individual inputs. Of course, this presumes white-box testing; unless the specifications are unusually detailed, a black-box tester wouldn't be able to assume the use of the multiplication primitive and would therefore need more test cases to cover different combinations of inputs.
Full branch coverage would only require two tests, but that isn't enough to show that the condition is implemented correctly for +/-Inf, NaN, or zero, each of which could easily exhibit incorrect behavior without suggesting deliberate malice on the part of the implementer.
Posted May 20, 2015 11:58 UTC (Wed)
by paulj (subscriber, #341)
[Link] (1 responses)
E.g., Monads? Isn't this what they were invented for?
Posted May 20, 2015 13:06 UTC (Wed)
by ibukanov (subscriber, #3942)
[Link]
Yes, ideally Monads as implemented if not as in Koka [1] but at least as in PureScript [2]. Haskell typesystem is not powerful enough to express many useful idioms that are required by a system language or language where one need to interface a lot with code in other languages. But even just supporting kind-2 types and some syntax sugar should help Rust a lot.
[1] - http://research.microsoft.com/en-us/projects/koka/
Great!
> https://git.xiph.org/?p=opus.git;a=commitdiff;h=d6b56793d...
> https://git.xiph.org/?p=opus.git;a=commitdiff;h=58ecb1ac1...
Great!
+ /* Tests are reversed to catch NaNs */
+ if (!(x<8))
Great!
Great!
Great!
x = f1();
y = f2();
z = x * y;
if (z < 0) return error;
x = f1();
y = f2();
z = x * y;
if (isNaN(t) || t.asDefinedNumber() < 0) return error;
if (!f1(&x)) return error;
if (!f2(&y)) return error;
if (!mult(x, y, &z)) return error;
if (z < 0) return error;
Great!
Great!
Ideally this should be expressed by types.
Great!
[2] - http://www.purescript.org/