Implicit widening, polymorphic indexing, and similar ideas

[aturon]

Just a heads-up: I’ve posted a comment on the currently open RFC for renaming int types. I think we should move forward with that (modulo picking final names), and then separately address these ergonomic considerations after we’ve had more time to discuss and experiment. (They are backwards compatible, modulo the issue with whether operator traits should use associated types.)

Keep the ideas coming!

[aturon]

Please don’t bake in a >= 32-bit architecture assumption. Rust is so much safer than C/C++ for embedded systems.

Ah, sorry, that was a bit glib. We’ve discussed possibly allowing a u32 -> usize implicit coercion, but with an optional lint that can be used when working in a 16-bit ecosystem. But that’s just a sketch of an idea.

[darinmorrison]

I think straight up widening is too confusing, but I would totally be down for having separate heterogeneous operators. These would be syntactically distinct, e.g. ** ++ --. For arithmetic: Whereas the normal ones might have an associated output type, these will have both args and the return type as input types. Also, they could only be implemented for the combinations where overflow is impossible, giving the programmer some handy guarantees and making them not overlap with the normal ones. For == it would simply be backed by a heterogeneous equality trait.

I really like this approach. I’m also wary of having implicit widening as a default behavior. I also think the likely loss of type inference is not a good trade for the default. If there were separate operators it would provide more flexibility to change things around in the future.

Polymorphic indexing seems pretty reasonable.

[petrochenkov]

Implicit widening feels like a much more significant change to the language, with a lot more considerations to take into account and worry about getting right. I think it should only be considered if things are found to still be too painful after the other ideas have been experimented with.

This is exactly my thought. All these additions are backward compatible. Let’s add polymorphic indexing, then wait a couple of months and look if people are still complaining. If they aren’t, then the problem is solved.

Moreover, I like the current rules and the explicitness they provide, because with them it’s always obvious where are which types used and where do type transitions happen. This explicitness is much more important, than slightly shorter code in some relatively rare scenarios. When I learned Rust, the absence of integer conversions was one of the first pleasant surprises, and I especially appreciated it later when I rewrote to Rust some C code with… quite liberal use of integer types. Every as operator in the intermediate code said “Hey, look at me later and correct the types respectively”. Personally, I’m even against polymorphic indexing for these reasons, but I acknowledge that indexing with smaller types is common in some domains and creates more noise there than people can accept.

– By the way, polymorphic indexing will sometimes change the types obtained by type inference undesirably:

let v = vec![0, 1, 2, 3];

// Now i is inferred as uint, with polymorphic indexing i has the integer fall-back type - i32
// This will be especially funny if vectors are polymorphically-indexable by unsigned types only (and I hope they are)
// Note, that the amount of checks is doubled, when the indexing is performed by (sufficiently small) signed types, like i32 on x64, for example
for i in range(0, 3) {
   println!("{}", v[i]);
} 

[arielb1]

The number of checks isn’t doubled - you just need to do the extra sign-extend.

[petrochenkov]

Indeed. If the checks are performed on the signed indexes after sign-extending and reinterpreting them as unsigned numbers, then the length of indexable containers should be limited by int::MAX. Currently it seems to be true for containers using continuous memory, but not necessarily true for bit containers, containers of zero-sized objects or non-continuous indexable containers (like deque). Although it may be a sane constraint to impose.

[comex]

-1 on implicit widening due to the ‘confusing order of possibly overflowing arithmetic and widening’ issue. +1 on polymorphic indexing, as this makes it easier to do the safe thing.

[Ericson2314]

Sure, two things:

• Whatever C does has always confused me.
• Widening seems mainly useful for arithmetic, rather than e.g. applying arbitrary functions. Likewise I could see some downsides to the feature (with user code). e.g. with an API to marshal data in and out of a packet there is more opportunity to move a value from a smaller field into a bigger field by mistake.

[Ericson2314]

Now that i think about it, my heterogenous operators could be defined with associated types if they only were defined for the minimal amount of widening. Then they would offer the invariant that using them without the normal ops or casts means both overflow is impossible, and the smallest-sized integer values were used.

[CloudiDust]

I agree that we should do polymorphic indexing first, and if the result is still unbearable, then maybe coercions can be a last resort.

[glaebhoerl]

To get forward inference there, you’d have to say something like that when multiple trait impls could match, but there’s a default type parameter, you use that to inform which impl to choose. But that would add more subtlety to an already pretty complex dispatch system.

Ah, so apparently we don’t already do this. That’s one of the things I didn’t know. (I don’t really know how the whole trait matching, inference, defaults, etc. system works today, only that it seems complicated.)

Implicit widening, paired with (possibly multiple) lints, seems like a clear improvement. Targeted linting is IMO likely to be more effective in catching mistakes than requiring coercions everywhere (which will lead to blind coercions).

My suspicion/intuition is that if we can tell the user what the right thing to do is with a lint, then we can also just do that right thing automatically. More in a followup comment.

Promotion and heterogeneous comparisons: if we do implicit widening, I believe that these will both fall out for free.

As @rkjnsn also notes, heterogenous comparisons would work between every pair of integer types, not just the “losslessly widenable” ones.

Multiplication forced-promotion to the next largest type could be more problem than solution, and why for multiplication but not addition and subtraction?

Mainly because (if I’m thinking straight) the result of an addition among two N-bit numbers can always be represented, at most, in N+1 bits. A multiplication, by contrast, needs N*2 bits to be sure to fit: going, for instance, from u32 right to u64. (As @Ericson2314 notes, x86 at least has direct support for this.) But given that we don’t have a u33, and the next largest is u64 anyways, it may not make sense to attach too much significance to this difference in practice.

(Incidentally, this is one reason why it might be useful to have iN and uN types for any N (at least up to 64): currently when we widen the result of an addition between u32s to u64 to make sure it fits, we lose information: that it actually takes up at most u33. Then when we add two such u64s, we have nowhere further to widen. While if we had two u33s, we could safely go to u34. This gives us a lot more space for such incremental steps, raising the hope that such automatic widenings could actually be propagated through real-world arithmetic expressions without hitting the upper bound depressingly quickly. But it would likely still be too complicated and unergonomic to attempt to actually put something like this into practice.)

I also think the likely loss of type inference is not a good trade for the default.

My assumption is that it wouldn’t have any negative impact on inference - that it would allow strictly more programs to typecheck. My understanding of coercions is that they’re like an “after the fact fix-up”: after “normal” type inference, if the compiler determines that an expression has type A in a context where B is expected, if there is a valid coercion from A to B, then instead of throwing a type error, it will insert the coercion. At any rate, that is how I think implicit widening would/should work. (We do already have a bunch of coercions e.g. for trait objects, so it’s not some completely new thing.)

[glaebhoerl]

So I think these are all variations on the basic idea that given an operation involving different integer types, the “right thing” to do is always at least sometimes, but sometimes always, uniquely determined by the types involved in it. We can, as we do, make operations between different types illegal and require the user to figure out and manually do the ‘right thing’ afresh every time using explicit casts, but we could also do her a favor and make it do the right thing right away.

In the case of indexing with types other than uint, the right thing is always to do the bounds check first, and then to index as uint. So we can add impls to do just that.

In the case of comparisons between different types, the right thing is always, if the signedness is different, to first check if the signed operand is negative, and after that to perform the comparison with the narrower type cast as the wider one. As @jerrym notes, when the compiler complains of a comparison between signed and unsigned types, it is always a pain to figure out the right way to make it stop doing so, even though there is a single correct solution in every case. We can instead teach the type system what to do by adding some impls.

If you want to pass a particular integer type to (for instance) a function expecting a different one, the right thing is sometimes obvious: if the expected type is strictly wider than the one you have, then you just need to cast it with as. We could make this happen automatically.

And my feeling is that in the case of arithmetic operations involving different types, it should sometimes be possible to uniquely determine the right thing as a function of three types: the type of the left operand, the type of the right, and the type of the result. Perhaps: if the result type is at least as wide as both of the operands, then cast the operands to that type before performing the operation. Whether that’s actually the right rule and whether there is a clean way to encode it into the current type system are separate questions, but I think they should at least be investigated. (The direction I sketched earlier is not necessarily the only possible one.)

These things would have a threefold benefit:

• For ergonomics: the user has less thinking and typing to do.

• For correctness: by doing the right thing automatically, we eliminate the possibility of accidentally doing a wrong one.

• For clarity: if the “obviously correct” thing is always automatic, then any explicit casts which had to be inserted must have been non-obvious, and so deserve special scrutiny. (I would go so far as to make superfluous casts a warning or error.)

[Uther]

[quote=“glaebhoerl, post:31, topic:1141”] Mainly because (if I’m thinking straight) the result of an addition among two N-bit numbers can always be represented, at most, in N+1 bits. A multiplication, by contrast, needs N*2 bits to be sure to fit: going, for instance, from u32 right to u64. (As @Ericson2314 notes, x86 at least has direct support for this.) But given that we don’t have a u33, and the next largest is u64 anyways, it may not make sense to attach too much significance to this difference in practice.

(Incidentally, this is one reason why it might be useful to have iN and uN types for any N (at least up to 64): currently when we widen the result of an addition between u32s to u64 to make sure it fits, we lose information: that it actually takes up at most u33. Then when we add two such u64s, we have nowhere further to widen. While if we had two u33s, we could safely go to u34. This gives us a lot more space for such incremental steps, raising the hope that such automatic widenings could actually be propagated through real-world arithmetic expressions without hitting the upper bound depressingly quickly. But it would likely still be too complicated and unergonomic to attempt to actually put something like this into practice.) [/quote]If we have to widen type on multiplication, we have to do it for all the operators too or the language would be completely inconsistant and misleading.

The RFC 45 cover how to handle this cleanly, but it’s far too late to go that way : it would make Rust a completely new language.

[jerrym]

@glaebhoerl There are risks of unexpected behavior (esp. serious in real-time code). [Search for “true scala complexity”, “scala puzzlers”, and “scala unpredictable”.]

Integer n < m seems obvious: Just (conceptually) widen the two values to a type with sufficient range.

Indexing an array index with a wide or narrow index seems clear, but people pointed out that a too-narrow-index warning would flag code that didn’t get updated for an array that’s now larger. Probably the cost/benefit for polymorphic indexing is good but experiments can tell.

Pushing auto-widening down through arithmetic operations could be like Scala’s implicit conversions (e.g. String to RichString so it can call a RichString method on the value) which are so unpredictable that people single-step in the debugger to figure out what the code does. Which functions are “arithmetic”? How to explain the precision of integer expressions if some operations auto-widen?

Q. Is there a doc on Rust type inference?

[rkjnsn]

I also think the likely loss of type inference is not a good trade for the default.

My assumption is that it wouldn’t have any negative impact on inference - that it would allow strictly more programs to typecheck. My understanding of coercions is that they’re like an “after the fact fix-up”: after “normal” type inference, if the compiler determines that an expression has type A in a context where B is expected, if there is a valid coercion from A to B, then instead of throwing a type error, it will insert the coercion. At any rate, that is how I think implicit widening would/should work. (We do already have a bunch of coercions e.g. for trait objects, so it’s not some completely new thing.)

While it is certainly possible to implement implicit widening without changing the meaning of existing programs by having widening only kick in in situations that are presently errors, I worry that it may make it easier accidentally affect the correctness of code. Consider the following (admittedly contrived) example:

fn func1(_: i32) {}
fn func2(_: i16) {}

let input  = "4500";
let mut n = input.parse().unwrap();
// A
func1(n);
n *= 16;
println!("{}", n);

In this example, n is inferred to be i32, because that’s what func1 expects, and the program outputs 72000. Now, what happens if one adds func2(n) at point A without remembering that it takes a narrower type? Today, this causes n to be inferred as an i16, and results in the following error:

error: mismatched types: expected `i32`, found `i16` (expected i32, found i16)

However, with implicit widening, this wouldn’t be an compile-time error. Instead, the code would happily build with n as an i16, implicitly widening the value when calling func1. Some formerly-accepted values would then result in a panic, while others would result in overflow. In this case, without overflow checking, the code would happily and erroneously output 6464.

It may very well be possible to come up with good solutions for the various pitfalls by coming up with good rules for when widening can and can’t kick in, how it can affect inference, and whether it should propagate to the arguments of a widened expression, but I wouldn’t want it included without a lot of thought and testing.

Given that things like polymorphic indexing and heterogeneous comparisons don’t carry nearly as much risk, are ergonomic wins, and are useful even in a world with implicit widening, I still feel we should start there. Given that it wouldn’t affect the meaning of existing programs, implicit widening can be added at a later date if it really turns out to be necessary.

[rkjnsn]

What about some kind of mechanism to explicitly mark a value to be widened? Unlike a cast, it would only perform lossless conversions, and it would infer the target type. That way, you know at a glance that it’s a safe conversion, it can be less verbose, but you still get to explicitly determine where the widening happens. Just for fun, I decided to play with a basic [Widen trait](http://play.rust-lang.org/?code=use%20widen%3A%3AWiden%3B use%20widen%3A%3Awiden%20as%20w%3B mod%20widen%20{ %20%20%20%20pub%20trait%20Widen<T>%20{ %20%20%20%20%20%20%20%20fn%20widen(self)%20->%20T%3B %20%20%20%20} %20%20%20%20impl<T%3A%20%3A%3Astd%3A%3Anum%3A%3AInt>%20Widen<T>%20for%20T%20{ %20%20%20%20%20%20%20%20fn%20widen(self)%20->%20T%20{ %20%20%20%20%20%20%20%20%20%20%20%20self %20%20%20%20%20%20%20%20} %20%20%20%20} %20%20%20%20impl%20Widen<i32>%20for%20i16%20{ %20%20%20%20%20%20%20%20fn%20widen(self)%20->%20i32%20{ %20%20%20%20%20%20%20%20%20%20%20%20self%20as%20i32 %20%20%20%20%20%20%20%20} %20%20%20%20} %20%20%20%20impl%20Widen<i64>%20for%20i16%20{ %20%20%20%20%20%20%20%20fn%20widen(self)%20->%20i64%20{ %20%20%20%20%20%20%20%20%20%20%20%20self%20as%20i64 %20%20%20%20%20%20%20%20} %20%20%20%20} %20%20%20%20impl%20Widen<i64>%20for%20i32%20{ %20%20%20%20%20%20%20%20fn%20widen(self)%20->%20i64%20{ %20%20%20%20%20%20%20%20%20%20%20%20self%20as%20i64 %20%20%20%20%20%20%20%20} %20%20%20%20} %20%20%20%20 %20%20%20%20pub%20fn%20widen<F%2C%20T>(val%3A%20F)%20->%20T%20 %20%20%20%20%20%20%20%20where%20F%3AWiden<T> %20%20%20%20{ %20%20%20%20%20%20%20%20val.widen() %20%20%20%20} } fn%20main()%20{ %20%20%20%20fn%20func1(%3A%20i16)%20%7B%7D%0A%20%20%20%20fn%20func2(%3A%20i32)%20%7B%7D%0A%20%20%20%20fn%20func3(_%3A%20i64)%20%7B%7D%0A%0A%20%20%20%20let%20a%20%3D%2057i16%3B%0A%20%20%20%20let%20b%20%3D%2067i32%3B%0A%20%20%20%20let%20c%20%3D%2079i64%3B%0A%20%20%20%20%0A%20%20%20%20func1(a.widen())%3B%0A%20%20%20%20func2(a.widen())%3B%0A%20%20%20%20func3(a.widen())%3B%0A%20%20%20%20%0A%20%20%20%20%2F%2Ffunc1(w(b))%3B%0A%20%20%20%20func2(w(b))%3B%0A%20%20%20%20func3(w(b))%3B%0A%20%20%20%20%0A%20%20%20%20%2F%2Ffunc1(w©)%3B%0A%20%20%20%20%2F%2Ffunc2(w©)%3B%0A%20%20%20%20func3(w©)%3B%0A%7D%0A).

[darinmorrison]

My assumption is that it wouldn’t have any negative impact on inference - that it would allow strictly more programs to typecheck. My understanding of coercions is that they’re like an “after the fact fix-up”: after “normal” type inference, if the compiler determines that an expression has type A in a context where B is expected, if there is a valid coercion from A to B, then instead of throwing a type error, it will insert the coercion. At any rate, that is how I think implicit widening would/should work. (We do already have a bunch of coercions e.g. for trait objects, so it’s not some completely new thing.)

Actually that part makes sense to me. I was referring to the suggestion of making operators polymorphic in their result (where the result type is not a function of the input types). I’d be pretty surprised if this wouldn’t negatively impact type inference, even if the effect could be mitigated most of the time. Generally speaking, type inference is somewhat overrated and the overemphasis on it has led to some pretty unfortunate design choices in some languages. However, in my experience it’s usually a bad idea to opt for API design choices that break type inference for the promise of more flexibility. It rarely works out that the added flexibility is worth the cost. Maybe I’m wrong though, or misunderstanding your suggestion.

Regarding the coercions, I think I get the idea but I’m pretty skeptical as to whether adding a bunch of additional to the default behavior is a good idea unless other possibilities have been exhausted first. These things have a tendency to increase complexity in subtle ways and cause serious headaches down the road. I’m certainly no expert on the numeric or systems stuff and maybe my fears are misplaced but I think I’d try to consider other alternatives first.

Generally speaking, it would be nice if coercion functionality where available as part of a module system. For example, in Coq, coercions act as a sort of dual to the canonicalization machinery for structures (what would be impls for Rust).

[glaebhoerl]

I don’t think we really disagree, except perhaps on emphasis. I agree that polymorphic indexing and heterogenous comparisons are the biggest and easiest wins, and we should start there. I just think that the others also deserve serious thought and investigation - which is not the same as “let’s add them tomorrow”. But no one’s saying otherwise, either.

Generally speaking, it would be nice if coercion functionality where available as part of a module system.

Do you mean that coercions would be given names and imported explicitly where desired? I’ve had that thought as well… probably too late for the existing coercions though.

[darinmorrison]

I don’t think we really disagree, except perhaps on emphasis. I agree that polymorphic indexing and heterogenous comparisons are the biggest and easiest wins, and we should start there. I just think that the others also deserve serious thought and investigation - which is not the same as “let’s add them tomorrow”. But no one’s saying otherwise, either.

Indeed, and it’s definitely good to have a number of options to explore in this space :]

Do you mean that coercions would be given names and imported explicitly where desired? I’ve had that thought as well… probably too late for the existing coercions though.

Basically, yes. Ideally, one would like to be able to have some control over import/export and applicability, as well as the ability to query the the compiler to see which coercions are in scope. For debugging purposes it should be possible to show where coercions are used when pretty-printing. You can see how Coq handles some of these things here. I don’t know how feasible some of that would be with the current implementation of coercions in Rust though.

[simias]

I’m a bit wary of implicit widening as well, mostly because of negative Pavlovian conditioning caused by having way too many bugs caused by it in C. C is particularly bad in the way it handles widening though, so maybe Rust could do it right.

That being said I don’t usually mind having to explicitly cast integers when doing arithmetics, it makes it easier to understand what the code does. Especially with inference, it can be tricky to figure out what types are at a glance when browsing through the code. If you have a long chain of arithmetic operations with many intermediate temporary variables it might become hard to reason about the type of those intermediate variable if there are implicit conversions going on. Here’s some actual code:

/// Helper function to add two `u8`s with carry and update the CPU flags
fn add_with_carry_and_set_flags(cpu: &mut Cpu, x: u8, y: u8) -> u8 {
    // Check for carry using 32bit arithmetics
    let x = x as u32;
    let y = y as u32;
    let carry = cpu.carry() as u32;

    let r = x + y + carry;

    let rb = r as u8;

    cpu.set_zero(rb == 0);
    cpu.set_halfcarry((x ^ y ^ r) & 0x10 != 0);
    cpu.set_carry(r & 0x100 != 0);
    cpu.set_substract(false);

    rb
}

With implicit widening I believe that could be written (assuming the bool returned by cpu.carry() is also candidate to widening):

/// Helper function to add two `u8`s with carry and update the CPU flags
fn add_with_carry_and_set_flags(cpu: &mut Cpu, x: u8, y: u8) -> u8 {
    // Check for carry using 32bit arithmetics
    let r: u32 = (x as u32) + y + cpu.carry();

    let rb = r as u8;

    cpu.set_zero(rb == 0);
    cpu.set_halfcarry((x ^ y ^ r) & 0x10 != 0);
    cpu.set_carry(r & 0x100 != 0);
    cpu.set_substract(false);

    rb
}

That does remove some noise but unless I’m mistaken the code would still build (and be incorrect) if I replaced the (x as u32) with a plain x. I’m not really sure which version I prefer to be honest, I kind of like how explicit the first version is but it is significantly more noisy.

An other simpler real life example could be:

fn pack_u16(lo: u8, hi: u8) -> u16 {
    (lo as u16) | ((hi as u16) << 8)
}
```

The order of the casts is obviously important, if we shift `hi` by 8 places without first upgrading it to an `u16` we'll end up with 0. With implicit widening this example would build without any casts at all and yield incorrect results. Currently it would print an error and force you to add a cast (and therefore you'll have to think about where the cast should take place). It's still possible to get the cast wrong, e.g. `(lo | (hi << 8)) as u16` but at least it's blatantly obvious when reading the code. That being said, writing `hi << 8` also triggers a warning with current rust when `hi` is a `u8` so it could be caught that way (although that only works if you're shifting completely out of range, not partially).

On the other hand having to cast integer types to `usize` when indexing and slicing is really annoying and not really useful in my experience, I'd be very much in favor of adding polymorphic indexing.

I think even bigger types should be allowed to remove the portability concerns, i.e. allowing indexing with `u64` on 32bit machines. Maybe in this case u64 truncation could be considered an overflow when the value is not in the 32bit range and trigger an assertion in debug builds.