ASR: add UnsignedInteger

[certik]

The UnsignedInteger, just like the default (signed) Integer should be checked in Debug and ReleaseSafe mode for overflow (from both sides). In Release mode they are not checked for performance.

We have to carefully check that this design fixes all the pitfalls at https://github.com/lcompilers/lpython/wiki/ASR-Design#unsigned-integers, but it looks like it might.

If wraparound is required, then the design at #1578 should be used.

Implementation:

• Initial implementation: Add unsigned int types #1764
• Add tests for all corner cases, harden the implementation
  • Add unsigned integer support to C backend #1769
  • Add a test for all unsigned types #1770
  • Implement unsigned arrays support #1775
• Debug time wraparound check -> implement later: Implement Debug time wraparound check for signed and unsigned integers #1776

[certik]

For example, for unsigned int a = 1000; signed int b = -1; (a > b), in LPython it would look like:

a: u16 = 1000
b: i16 = -1
a > u16(b)

We must decide how u16(b) where b is signed should be handled. It can either cast negative integers to positive (no bit changes), or it can give an error message.

[rebcabin]

I believe C just re-uses the bit pattern: https://replit.com/join/jlxoloezhd-brianbeckman

[certik]

Yes, C does. Rust, on the other hand, does not allow you to do this:

    let a: u8 = 100;
    let b: i8 = -1;
    let val: bool = a > b;                    

which gives:

$ cargo run     
   Compiling xx v0.1.0 (/private/tmp/xx)
error[E0308]: mismatched types
 --> src/main.rs:5:25
  |
5 |     let val: bool = a > b;
  |                         ^ expected `u8`, found `i8`
  |
help: you can convert an `i8` to a `u8` and panic if the converted value doesn't fit
  |
5 |     let val: bool = a > b.try_into().unwrap();
  |                          ++++++++++++++++++++

For more information about this error, try `rustc --explain E0308`.
error: could not compile `xx` due to previous error

and this:

    let a: u8 = 100;
    let b: i8 = -1;
    let val: bool = a > b.try_into().unwrap();

gives:

$ cargo run     
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/xx`
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: TryFromIntError(())', src/main.rs:5:38
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

So the default way that the rust compiler recommended to convert i8 to u8 is the "safe" method, which gives a runtime error if it does not fit exactly.

The casting in Rust is done by as, and then indeed it just casts the bits:

    let a: u8 = 100;
    let b: i8 = -1;
    let val: bool = a > b as u8;
    println!("{}", val);

This prints "false". The b as u8 is equal to 255.

So Rust allows both methods to convert i8 to u8. Here are more details: https://doc.rust-lang.org/rust-by-example/types/cast.html

Conclusion: I think we should cast signed to unsigned like Rust's "as", that is, no change in bits, so u8(-1) becomes 255. The same with u8(300), the value becomes 300 mod 256.

[Smit-create]

So, do we want to introduce a new type in ASR like UnsignedInteger?

[czgdp1807]

If we are going to support unsigned integers, one clean way to do it is to introduce an opaque type, such a OpaqueType(identifier name, int size_in_bytes), where the frontend can set u8, u16, etc. for name, and the number of bytes it occupies in memory.

Suggested in https://github.com/lcompilers/lpython/wiki/ASR-Design#unsigned-integers

#1578 is also one way.

However I think UnsignedInteger is the cleanest for now. You can go ahead with it. If @certik says to use one of the other two designs then we can always update.

[certik]

The best way forward right now seems to be:

• Add UnsignedInteger ttype, just like Integer. It will have the same kinds=1, 2, 4, 8. The LPython types will be u8, u16, u32 and u64.
• The integer does not wrap around and in Debug mode it will be checked

First we should implement it, then we should add the Debug time checks for it, to ensure people do not use wrap around. The behavior should be similar to Rust's.

[certik]

This is now implemented, see the issue description for the 4 PRs that implemented it. There might still be bugs, but if there are, we'll fix it as they are reported.