3 ms·

I'm not sure I agree with #1. While it's true that using signed integers for lengths would have solved this problem, a negative length doesn't generally make se

I'm not sure I agree with #1. While it's true that using signed integers for lengths would have solved this problem, a negative length doesn't generally make sense or have any defined meaning. So if you have any logic that is doing case analysis on lengths, you basically have no reasonable action in the case of a negative length: all you can do is complain that the length got corrupted at some point. For example, imagine that instead of testing whether the strings differed by more than 20, you were just testing whether the needle was >= 20 in length: impl Searcher { fn new(haystack: &[u8], needle: &[u8]) -> Searcher { match needle.len() { 0..20 => Naive(NaiveSearcher::New) 20..uint::MAX => TwoWay(TwoWaySearcher::New(needle)) _ => fail!("Negative length, shouldn't happen!") } } } Part of the feature of an unsigned type IMO is that it cannot have an out-of-domain value by definition.

CJefferson 12y ago
The problem is that while unsigned types cannot have an out-of-domain value, they wrap. Also, often negative lengths make sense as meaning "backwards". In C++ I often hit in algorithms code that looks like some variant of: a.size()-1 >= capacity But when a.size() == 0, a.size() - 1 is MAXINT. Of course I could re-write this as a.size() >= capacity + 1, but that requires remembering / noticing. Personally I find this so annoying that when I recently had to write a set of my own C++ containers (as I needed 1-indexed rather than 0-indexed containers), I decided to make the return value of size() signed.
- haberman 12y ago
  > But when a.size() == 0, a.size() - 1 is MAXINT. This is exactly the same problem class of bug as mentioned in the original article. But my argument is that while signed lengths fix some problems, they cause others. Maybe I'd put it this way: I dislike using signed integers for lengths, because it creates an entirely new class of undefined (or arbitrarily-defined) behavior. Imagine that memcpy() took a signed length instead of unsigned. What should it do if it receives a negative length? There is no great answer to that question. It's true that if you have a bug, you might accidentally pass a very large unsigned integer to memcpy(). But at least you can predict what memcpy() will do now: it will attempt to copy a very large number of bytes and probably crash. Whereas if you pass a negative integer, it might reasonably do any of these things: - nothing - crash - attempt to copy bytes *before* the supplied ptr - assert()-fail and/or call abort() What's worse, it creates a sense of anxiety for anyone implementing a function like memcpy(), because there is no right answer for what they should do with a negative length. Callers of memcpy() might reasonably want any of the above. But then you get your callers angry with you because "obviously" a negative length means you should do nothing, or "obviously" a negative length means you should assert()-fail (a programmer's opinion about what is the "obvious" right behavior is often unduly influenced by their specific circumstances).
  - __david__ 12y ago
    It would be nice to have C/C++ operators/types that failed on overflow/underflow. The sad part is it's available on all processors in the status register. Just no one has brought it up to the higher level language level. If you could declare hard unsigned int x=0; then things like a.size() - 1 could abort() loudly instead of silently doing something that's probably wrong and masking errors later on.
    - pcwalton 12y ago
      Rust does have those types, but they aren't free: overflow checking has a significant performance cost even when fully optimized. Because of the performance cost, a lot of code doesn't use the overflow-checking types. I think what we really need is for the hardware manufacturers to help us out here.
      - StefanKarpinski 12y ago
        Agreed – hardware assistance would be a huge boon.
        mkup 12y ago
        BOUND instruction on x86 architecture exists for time immemorial, but not widely used and may be slow in modern microcode (like AAM/AAD and other stuff of handwritten assembly era, never emitted by compilers).
      - __david__ 12y ago
        > …overflow checking has a significant performance cost even when fully optimized. That surprises me—I would have thought a quick bit-test on the status register and conditional jump wouldn't be all that bad. > I think what we really need is for the hardware manufacturers to help us out here. Are you thinking something like a software interrupt on integer overflow?
        dbaupp 12y ago

CJefferson 12y ago

The problem is that while unsigned types cannot have an out-of-domain value, they wrap. Also, often negative lengths make sense as meaning "backwards". In C++ I often hit in algorithms code that looks like some variant of: a.size()-1 >= capacity But when a.size() == 0, a.size() - 1 is MAXINT. Of course I could re-write this as a.size() >= capacity + 1, but that requires remembering / noticing. Personally I find this so annoying that when I recently had to write a set of my own C++ containers (as I needed 1-indexed rather than 0-indexed containers), I decided to make the return value of size() signed.

haberman 12y ago
> But when a.size() == 0, a.size() - 1 is MAXINT. This is exactly the same problem class of bug as mentioned in the original article. But my argument is that while signed lengths fix some problems, they cause others. Maybe I'd put it this way: I dislike using signed integers for lengths, because it creates an entirely new class of undefined (or arbitrarily-defined) behavior. Imagine that memcpy() took a signed length instead of unsigned. What should it do if it receives a negative length? There is no great answer to that question. It's true that if you have a bug, you might accidentally pass a very large unsigned integer to memcpy(). But at least you can predict what memcpy() will do now: it will attempt to copy a very large number of bytes and probably crash. Whereas if you pass a negative integer, it might reasonably do any of these things: - nothing - crash - attempt to copy bytes *before* the supplied ptr - assert()-fail and/or call abort() What's worse, it creates a sense of anxiety for anyone implementing a function like memcpy(), because there is no right answer for what they should do with a negative length. Callers of memcpy() might reasonably want any of the above. But then you get your callers angry with you because "obviously" a negative length means you should do nothing, or "obviously" a negative length means you should assert()-fail (a programmer's opinion about what is the "obvious" right behavior is often unduly influenced by their specific circumstances).
- __david__ 12y ago
  It would be nice to have C/C++ operators/types that failed on overflow/underflow. The sad part is it's available on all processors in the status register. Just no one has brought it up to the higher level language level. If you could declare hard unsigned int x=0; then things like a.size() - 1 could abort() loudly instead of silently doing something that's probably wrong and masking errors later on.
  - pcwalton 12y ago
    Rust does have those types, but they aren't free: overflow checking has a significant performance cost even when fully optimized. Because of the performance cost, a lot of code doesn't use the overflow-checking types. I think what we really need is for the hardware manufacturers to help us out here.
    - StefanKarpinski 12y ago
      Agreed – hardware assistance would be a huge boon.
      - mkup 12y ago
        BOUND instruction on x86 architecture exists for time immemorial, but not widely used and may be slow in modern microcode (like AAM/AAD and other stuff of handwritten assembly era, never emitted by compilers).
    - __david__ 12y ago
      > …overflow checking has a significant performance cost even when fully optimized. That surprises me—I would have thought a quick bit-test on the status register and conditional jump wouldn't be all that bad. > I think what we really need is for the hardware manufacturers to help us out here. Are you thinking something like a software interrupt on integer overflow?
      - dbaupp 12y ago