Where are Rust's boolean and other primitive types implemented?

Question

I was going through the code behind some of the basic types in Rust, e.g. the pleasantly simple implementation of Option<T> or the weird macro magic behind tuple and I was able to find all of the types that I wanted in libcore. All except for one - bool. I couldn't find it anywhere else either.

Where is the code behind bool in Rust? I know this is not the most novel type out there, but I was surprised I could not find it.

Thanks to the answers by Francis and rodrigo, I noticed that the code I found for other primitives was just their traits and related macros, but not actual implementations.

The Rust book states that the primitives are built-in to the language, but I'm not satisfied with this explanation. When were they built in? Can it be traced to the time when the Rust compiler was first built with Rust or did it happen when it was still built in OCaml? Does any relevant code exist?

Evenfall

What exactly are you looking for? At some point, a "boolean" is just a single bit on the processor (or a full byte for performance reasons). Before that, it's an i1 (i8) in LLVM bitcode, and before that it's probably an enum in some Rust IR. Going lower down, you get to logic gates and transistors and electrons. Which of those is an "actual implementation"? – Goalie

I'm looking for the place where the Rust language (not LLVM bitcode or the CPU) started recognizing e.g. the == operator (i.e. boolean logic). I'm not too savvy with writing compilers so my wording might not be perfect, but I think there must have been a stage where the primitives were first "embedded" in the rustc compiler so it was able to compile them down to LLVM. – Evenfall

Answer 1

So here's a bit more information about what goes on in the compiler. For starters, as has already been mentioned, the actual operations that occur with booleans are entirely handled by LLVM, and get directly translated to the corresponding CPU instructions. While there are some cases where code just magically appears due to bootstrapping, this is not one of them. The compiler is specifically written to handle these types and emit the correct LLVM instructions.

For the earliest parts of compilation (e.g. during macro expansion) the type bool isn't special. It's just some path with the identifier bool. Eventually around here it will get converted to a primitive type. The actual definition of the type is here.

So now let's look at how the ! operator works. As I mentioned earlier, the code in libcore that does impl Not for bool never gets used. Code in the form !expr gets transformed into <T as Not>::not(expr) here. However, you'll notice that it checks to see if this particular expression is in fact a method call or not, and just leaves it as !expr if it's not meant to be a method call. How does it know? The call in MIR is just a cache lookup. The cache got populated during the type checking pass. Here is where the cache insertion occurs -- basically checking to see if the Not trait is implemented for a given type any time it sees a !. And you'll notice that this line specifically excludes booleans and integral types, which end up compiling down to LLVM instructions directly.

That's the rough picture of how it's defined. You'll find similar code in the same files for other primitives. In theory there could be some line somewhere that was enum bool { true, false } -- but ultimately this same code would still need to override it and emit the appropriate LLVM intrinsics, and integers couldn't be represented this way.

Orangy

Answer 2

bool is a primitive type. Primitive types and operations on them are implemented by the compiler, i.e. the compiler emits specialized code to perform operations on primitive types.

You'll see that bool implements many traits. Those implementations come from libcore, but they are often implemented by using the corresponding operator. For example, Not::not is implemented by returning !self. For any non-primitive type, this would invoke Not::not recursively and cause a stack overflow, but for primitive types, the compiler resolves the operator differently, and those trait implementations are only provided for the benefit of generic code.

Haaf

An array is a primitive too, but its implementation can be found easily. I was initially hoping to find bool by the code for not, but no luck. – Evenfall

To be fair, though, array's code is macro magic, so it may not be an "actual" implementation like you had in mind. – Evenfall

You'll find implementations of traits for the primitive types (in fact, you can define a trait in a crate and implement it for a primitive type yourself), but you'll never find the definition of primitive types in any library. – Cutch

You are right, it looks like those are not there at all. – Evenfall

Answer 3

You can see the definition for core::i32 only because of the constants i32::MIN and i32::MAX. The actual type is just an alias for the built-in type i32.

In the core::f32 case, for example there are a lot of useful constants.

But for bool, there is no useful values, other than true and false that are keywords, so there is no source for bool.

Bartholomeo

That makes sense, but it must have been introduced somehow. – Evenfall

@ljedrz: It just the same as i32. It is not introduced in core, it is an intrinsic type, defined directly by the compiler. The core part are just additional pieces around the type. – Bartholomeo

How does it work, then? I adjusted the question, since the natural follow-up to this answer is "how is this possible?" rustc is built from the code at github, so if it is defined directly by the compiler, how is it not there? – Evenfall

@Ijedrz: But it is there: It's defined as an 8-bit LLVM type github.com/rust-lang/rust/blob/master/src/librustc_trans/… – Rosetta

@ljedrz: I'm far from an expert in the Rust internals, but take a look at enum PrimTy and the PrimitiveTypeTable inside the implementation of rustc, the Rust Compiler. – Bartholomeo

@Kha: I think this code is just for the purposes of translation to LLVM's language, not for rustc use. – Evenfall

@Ijedrz: Ah, if your question is where the bool that rustc itself uses comes from, then the answer is: from the binary of the bootstrapping rustc version reddit.com/r/rust/comments/518gcs/… – Rosetta

@Kha: it looks like this is the explanation I am after; can you post an answer with some additional information about it? – Evenfall