How can core implement binary ops for builtin types?

[dylngg]

I am implementing core from scratch for fun (I know, I know, you're not supposed to do that). I've gotten to the point where I'm defining the Add trait for builtin types such as i32. To implement such a trait, I think I should use the + operator inside add, like found in the actual core crate. However, this begs the question, how does the compiler know to not use the Add trait implementation in add (to avoid a self-referential issue) and to use the Add implementation outside?

Take the following code, which emulates the behavior inside of core:

#![feature(no_core)]
#![feature(lang_items)]
#![no_core]

#[lang = "receiver"]
pub trait Receiver {}

// Allows for fn(&self)
impl<T: ?Sized> Receiver for &T {}
// Allows for fn(&mut self)
impl<T: ?Sized> Receiver for &mut T {}

#[lang="sized"]
pub trait Sized {}

#[lang="clone"]
pub trait Clone: Sized {
   // Required
    fn clone(&self) -> Self;

    // Provided
    fn clone_from(&mut self, source: &Self) {
        *self = source.clone()
    }
}

#[lang="copy"]
pub trait Copy: Clone {}

#[lang="add"]
pub trait Add<Rhs = Self> {
    type Output;

    fn add(self, rhs: Rhs) -> Self::Output;
}

impl Add for i32 {
    type Output = i32;

    fn add(self, other: Self) -> i32 {
        self + other
    }
}

fn main() {
    let _ = 1 + 2;
}

How does this code work? (I compile with a nightly rustc fully_perform_ice.rs)

It doesn't in fact, for reasons I don't understand. I get an ICE:

warning: the feature `lang_items` is internal to the compiler or standard library
 --> fully_perform_ice.rs:2:12
  |
2 | #![feature(lang_items)]
  |            ^^^^^^^^^^
  |
  = note: using it is strongly discouraged
  = note: `#[warn(internal_features)]` on by default

warning: 1 warning emitted

note: no errors encountered even though delayed bugs were created

note: those delayed bugs will now be shown as internal compiler errors

error: internal compiler error: error performing operation: fully_perform
  --> fully_perform_ice.rs:41:9
   |
41 |         self + other
   |         ^^^^
   |
note: delayed at /Users/dylngg/Source/rust/git/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs:87:25 - disabled backtrace
  --> fully_perform_ice.rs:41:9
   |
41 |         self + other
   |         ^^^^

error: internal compiler error: error performing operation: fully_perform
  --> fully_perform_ice.rs:41:16
   |
41 |         self + other
   |                ^^^^^
   |
note: delayed at /Users/dylngg/Source/rust/git/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs:87:25 - disabled backtrace
  --> fully_perform_ice.rs:41:16
   |
41 |         self + other
   |                ^^^^^

error: internal compiler error: error performing operation: fully_perform
  --> fully_perform_ice.rs:41:9
   |
41 |         self + other
   |         ^^^^^^^^^^^^
   |
note: delayed at /Users/dylngg/Source/rust/git/compiler/rustc_trait_selection/src/traits/query/type_op/custom.rs:87:25 - disabled backtrace
  --> fully_perform_ice.rs:41:9
   |
41 |         self + other
   |         ^^^^^^^^^^^^

note: using internal features is not supported and expected to cause internal compiler errors when used incorrectly

note: please attach the file at `/Users/dylngg/Desktop/rust/rustc-ice-2024-09-01T21_06_27-62553.txt` to your bug report

query stack during panic:
end of query stack

Can any rust compiler experts point out how my Add usage is wrong? It seems to be nearly the same as core.

I do see the issue with the same error for a seemingly unrelated bug. However, this is core behavior, so I think there must be something minor I am overlooking in my implementation.

[tczajka]

There is a special case in the compiler for built-in types: + doesn't call Add::add for them.

[quinedot]

You were missing Clone and Copy for i32. That's enough when using --release (for the OP).^[1]

Without --release, you need panic_const_add_overflow and then you need some more panic-related lang items....

(Eventually you've reimplemented half or more of core.)

---

1. Use Build not Run in the upper left. ↩︎

[scottmcm]

@dylngg

However, this begs the question, how does the compiler know to not use the Add trait implementation in add (to avoid a self-referential issue) and to use the Add implementation outside?

Look at the MIR for stuff: https://rust.godbolt.org/z/WG759T6Pa

The compiler knows about primitives and emits MIR primitives for them directly.

[jjpe]

@tczajka

There is a special case in the compiler for built-in types: + doesn't call Add::add for them.

To be fair, something like this (i.e. effectively an intrinsic) was always going to be unavoidable at some point, for any PL implementation. The only alternative I know of would be circular definitions, which may as well be an antonym to the word "useful".

[tczajka]

@jjpe

To be fair, something like this (i.e. effectively an intrinsic) was always going to be unavoidable at some point, for any PL implementation. The only alternative I know of would be circular definitions, which may as well be an antonym to the word "useful".

The issue here isn't that there is an intrinsic, but that the dependency is inverted for builtin types vs other types.

For other types: + defers to Add::add.
For builtin types: Add::add defers to + which is an intrinsic.

It could have been that for builtin types + also defers to Add::add which is either an intrinsic or implemented in terms of intrinsics::add_i32.

[paramagnetic]

@dylngg

how does the compiler know to not use the Add trait implementation in add (to avoid a self-referential issue) and to use the Add implementation outside?

Because it literally knows and defines the types?

(The whole point of static typing is that you do stuff based on types.)

[dylngg]

For what it's worth, when you compile the following code:

#![feature(no_core)]                                                              
#![feature(lang_items)]                                                           
#![no_core]                                                                       
                                                                                  
#[lang = "receiver"]                                                              
pub trait Receiver {}                                                             
                                                                                  
// Allows for fn(&self)                                                           
impl<T: ?Sized> Receiver for &T {}                                                
// Allows for fn(&mut self)                                                       
impl<T: ?Sized> Receiver for &mut T {}                                            
                                                                                  
#[lang="sized"]                                                                   
pub trait Sized {}                                                                
                                                                                  
#[lang="clone"]                                                                   
pub trait Clone: Sized {                                                          
   // Required                                                                    
    fn clone(&self) -> Self;                                                      
                                                                                  
    // Provided                                                                   
    fn clone_from(&mut self, source: &Self) {                                     
        *self = source.clone()                                                    
    }                                                                             
}                                                                                 
                                                                                  
#[lang="copy"]                                                                    
pub trait Copy: Clone {}                                                          
                                                                                  
impl Clone for i32 {                                                              
    fn clone(&self) -> Self { *self }                                             
}                                                                                 
                                                                                  
impl Copy for i32 {}                                                              
                                                                                  
fn main() {                                                                       
    let _ = 1 + 2;                                                                
} 

you get the following error:

error[E0369]: cannot add `{integer}` to `{integer}`
  --> fully_perform_ice.rs:37:15
   |
37 |     let _ = 1 + 2;
   |             - ^ - {integer}
   |             |
   |             {integer}

So this why I was confused how it avoided a circular dependency if adding in main requires the Add trait.

[scottmcm]

@dylngg

For what it's worth, when you compile the following code:

#![feature(no_core)]                                                              
#![feature(lang_items)]                                                           
#![no_core]    
…

you get the following error:

If you use internal features, you should expect bad errors if you do it wrong. We're not going to add code and maintenance overheads to make things you're not supposed to use smoother: Policy for ICEs on incorrect usage of internal-only features · Issue #620 · rust-lang/compiler-team · GitHub

[CAD97]

@dylngg

For what it's worth

IIRC the reason this occurs is that while the operation is lowered as an intrinsic and not a call to Add::add, the trait obligation that ensures Add is implemented is still validated.

Lang items are for most intents and purposes part of the compiler and doing them wrong is unsupported.

[scottmcm]

Also, the compiler hard-codes knowledge that primitives like i32 are copy -- because going to check traits for that is a waste of CPU -- but that means if you don't have i32: Copy you'll get a MIR typecheck error later.

[SOFe]

it isn't impossible; you can totally avoid it by delegating to an intrinsic function call like extern "rust-operator" fn add_i32(). The compiler just doesn't do so because (afaik) of unnecessary compile speed impact for OCD.

[jjpe]

That would just be punting the existence of that intrinsic down the line though. In particular, it wouldn't get rid of it.
The point I was making was that such an intrinsic will always exist somewhere.