Reading Object Files and Relocations
A .o file can contain a function's machine instructions before the addresses of its callees are known. Looking at one helps explain what remains to be done after compilation.
An object file holds machine code and data, along with metadata needed to finish building the program. Relocation records identify places to patch once a symbol's final address is known. They let the assembler encode a call now and leave its destination for the linker to resolve.
Why this phase matters
Object files support separate compilation: one source file can be compiled without the final addresses of its callees. Libraries can be built once and linked later, and projects can rebuild changed units. Code from C, Rust, assembly, and other languages can share a build if their object formats, symbols, and calling conventions agree.
C exposes this model directly: compile add.c to add.o, compile main.c to main.o, then link them. Cargo and rustc handle more of these steps for Rust users, but the native toolchain still uses the same machinery. Java .class files and Python .pyc files are compiled artifacts for virtual machines, with different mechanisms for resolving references. JavaScript usually travels as source, which engines compile internally at runtime.
We'll emit assembly, use the system assembler to produce an object file, and inspect the result. Writing an ELF or Mach-O emitter would mean implementing the format ourselves; using the assembler lets us focus on what the resulting file contains.
What we are building here
We'll extend the driver in main.rs to take the assembly from code generation and pass it to the platform assembler. The resulting object file contains sections, symbols, and relocations.
Our compiler source is still main.rs, and its input is a file such as example.mrs. The main.s and main.o files below are generated output from that input. They are not new compiler components for the reader to implement.
Sections divide the file into kinds of content. Machine instructions usually live in .text. Read-only constants may live in .rodata. Writable globals would live in .data or .bss, though MicroRust does not have globals beyond functions.
Symbols name functions and other entities. The label mr_add becomes a defined symbol, while the runtime helper microrust_print_i32 is referenced but not defined in the generated object.
Relocation entries record which instruction bytes need patching once symbol addresses are known. Together with the section contents and symbol table, they let us encode a call while leaving its final displacement unresolved.
Why this build needs a runtime
Our runtime is the support code called by the generated program. It has two small functions: microrust_print_i32 prints an integer followed by a newline, and microrust_trap reports an arithmetic failure and exits. These are ordinary function calls in a native executable.
MicroRust recognises println!("{}", value) as a special form, but we haven't implemented Rust's macro system or standard library. The compiler turns that form into a call to our printing helper. The helper supplies the code that formats the integer and writes it to the output stream. Similarly, a failed arithmetic check calls the failure helper.
We use C for these helpers so we can reuse the platform's existing printing and error-reporting functions through a small interface. The compiler itself remains written in Rust and never parses C source. A C compiler builds the helpers separately. This is our choice of runtime implementation; the compiler phases don't inherently require C.
This chapter's object file contains references to those helpers, but not their definitions. The native build needs those definitions before it can produce a runnable program. In the linking chapter, the driver will compile the runtime and link it with our object file. Its C source is embedded in the final main.rs listing, so there is no extra source file for readers to collect.
The printing helper gives us a separate-compilation example. This MicroRust program calls it:
fn main() {
println!("{}", 41);
}A shortened Linux assembly example makes that external reference visible. It combines the entry wrapper and body for illustration; the companion emits them separately:
.intel_syntax noprefix
.text
.globl main
main:
push rbp
mov rbp, rsp
mov edi, 41
call microrust_print_i32
xor eax, eax
pop rbp
retAt assembly time, the assembler does not know where microrust_print_i32 will live in the final executable. It can still encode a placeholder and emit relocation records.
Conceptually, the object file says:
symbol table:
main defined in .text
microrust_print_i32 undefined
relocation:
call operand target microrust_print_i32The diagram omits byte offsets; objdump supplies those. Relocation types depend on the platform and instruction encoding. x86-64 calls often use PC-relative offsets, measured from the next instruction to the callee. This helps code work at different load addresses, provided the linker computes the correct displacement.
The assembler can usually resolve a branch to a local label such as .Lreturn in the same section. External references still need definitions and final offsets before the program can run.
The compiler can write its assembly text to a file:
fn write_assembly(path: &std::path::Path, asm: &str) -> std::io::Result<()> {
std::fs::write(path, asm)
}Then a build script or driver invokes the system assembler:
cc -c main.s -o main.oHere cc is acting as a toolchain driver: the .s input goes to the assembler. This command does not compile any C source. Compiling the C runtime is a separate step in the next chapter.
These commands use Linux's spelling and object format. On macOS, generate assembly with --target macos and use cc -arch x86_64 -c main.s -o main.o; merely changing the assembler flag is not enough if the symbols still have Linux spelling. Using cc as the driver gives us the platform's assembler support. Linux commonly uses ELF object files, macOS uses Mach-O, and Windows uses COFF. They share the concepts we've discussed, though implementing each format would require substantial additional work.
On a Unix-like system, we can inspect symbols and relocations with commands such as these, using platform equivalents where necessary:
nm main.o
objdump -r main.onm prints symbols and objdump -r prints relocations; macOS also has otool. The output lets us check that main is defined, that microrust_print_i32 is undefined, and that its call site has a relocation entry. I find this much easier to reason about with the object file open alongside the assembly.
For an undefined symbol, we can ask which object or archive should define it and whether that input was included. Mangling, visibility, and link order may also explain a missing definition.
The assembler handles headers, sections, symbol and string tables, relocations, and machine encoding. We remain responsible for the assembly we give it.
C makes this boundary easy to demonstrate:
// helper.c
int add_one(int x) {
return x + 1;
}The compiled helper.o defines add_one. A C caller can declare it and leave the linker to match the reference to this definition. MicroRust has no external-declaration syntax, so an undeclared add_one fails resolution before assembly. Our runtime print call is a special case. Rust crates add metadata and richer symbol naming to this native linking process.
Linker symbol names need to distinguish functions across compilation units. C names usually appear plainly, apart from platform conventions such as leading underscores. C++ mangles names to encode namespaces, overloads, and types; Rust mangles symbols to distinguish modules, crates, and monomorphized generic instances. MicroRust uses a simple mr_ prefix for source functions. It avoids ordinary C library names without implementing Rust's mangling scheme.
Following one call helps connect the representations. Source contains add(x, y), which becomes call mr_add in our Linux assembly. An unresolved reference records a relocation targeting mr_add at the call site. A same-section call may instead be resolved by the assembler, depending on binding and platform rules. Once the linker knows the destination, it writes the offset used by the instruction.
Position-independent code adds another layer. Shared libraries cannot assume they will be loaded at one fixed address in every process. Modern systems also use address space layout randomization, which intentionally varies load addresses. That means code often uses relative addressing, tables, and dynamic relocations so it can run no matter where the loader places it. MicroRust emits relative calls and stack references, without absolute global-data addresses. That works with the PIE defaults used in our tests. An assembler cannot generally turn arbitrary absolute-address assembly into position-independent code; adding globals would require revisiting the emitter.
An ELF emitter could be a later exercise in section headers and binary encoding. For this build, we'll keep using the platform assembler.
Object files also carry visibility. Some symbols are meant to be used by other objects. Some are local implementation details. In assembly, labels that begin with local-label conventions often stay local, while .globl helper_label exports helper_label for the linker to see outside the file:
.intel_syntax noprefix
.text
.globl helper_label
helper_label:
retThis label demonstrates visibility, not an integer-returning function. Without .globl main, startup code may be unable to find our C entry wrapper; main is not the raw process entry point. Exporting every helper label would risk collisions. Visibility also affects performance, encapsulation, dynamic linking, and debugging in larger builds.
Our one-file build needs only prefixed names such as mr_add. Rust must also distinguish identically named functions in separate crates and concrete instances of generics, which its mangling scheme handles.
Object files can carry debug information mapping instructions to source files, lines, variables, and sometimes types. Debuggers use it to set source breakpoints; profilers and postmortem tools use it too. They no longer have the compiler's AST. MicroRust doesn't emit DWARF or other platform debug data. Stripping symbols also limits what tools can report without changing the executable instructions.
Run this version
Keep the backend in main.rs and add an object command. It writes assembly into a temporary directory, invokes the system toolchain, and leaves the requested object file in our project folder.
This step needs a C toolchain named cc. On macOS, that comes with the command-line developer tools; the driver supplies -arch x86_64. On x86-64 Linux, it uses the host toolchain. Creating an x86-64 object on Apple Silicon does not require running x86-64 code.
These are the source files to keep. Any golden.mrs saved earlier can stay beside them; the commands below use example.mrs:
microrust/
|-- main.rs
`-- example.mrsReplace the contents of main.rs with this complete version, or compare it with the additions you've made while reading. The listing already includes the earlier phases.
main.rs: compiler through object-file generation
// Chapter 09: add object-file generation.
use std::fmt;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Span {
pub start: usize,
pub end: usize,
}
#[derive(Debug, Clone)]
pub struct Error {
pub phase: &'static str,
pub span: Span,
pub message: String,
}
impl Error {
pub fn new(phase: &'static str, span: Span, message: impl Into<String>) -> Self {
Self {
phase,
span,
message: message.into(),
}
}
pub fn render(&self, path: &str, source: &str) -> String {
let start = self.span.start.min(source.len());
let prefix = &source[..start];
let line = prefix.bytes().filter(|b| *b == b'\n').count() + 1;
let column = prefix.rsplit('\n').next().unwrap_or("").chars().count() + 1;
let text = source.lines().nth(line - 1).unwrap_or("");
format!(
"{}\n --> {path}:{line}:{column}\n{line} | {text}\n | {}^",
self,
" ".repeat(column - 1)
)
}
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} error: {}", self.phase, self.message)
}
}
impl std::error::Error for Error {}
// Later phases will use the source spans retained in the AST.
#[allow(dead_code)]
mod syntax {
use crate::{Error, Span};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TokenKind {
Fn,
Let,
Return,
Ident,
Int,
String,
I32,
Plus,
Minus,
Star,
Slash,
Colon,
Semicolon,
Comma,
LParen,
RParen,
LBrace,
RBrace,
Arrow,
Eq,
Bang,
Eof,
}
#[derive(Debug, Clone)]
pub struct Token {
pub kind: TokenKind,
pub lexeme: String,
pub span: Span,
}
pub fn ident_or_keyword(text: &str) -> TokenKind {
match text {
"fn" => TokenKind::Fn,
"let" => TokenKind::Let,
"return" => TokenKind::Return,
"i32" => TokenKind::I32,
_ => TokenKind::Ident,
}
}
pub fn lex(source: &str) -> Result<Vec<Token>, Error> {
let bytes = source.as_bytes();
let mut pos = 0;
let mut tokens = Vec::new();
while pos < bytes.len() {
if bytes[pos].is_ascii_whitespace() {
pos += 1;
continue;
}
if source[pos..].starts_with("//!")
|| (source[pos..].starts_with("///") && !source[pos..].starts_with("////"))
{
return Err(Error::new(
"lex",
Span {
start: pos,
end: pos + 3,
},
"doc comments are outside MicroRust",
));
}
if source[pos..].starts_with("//") {
while pos < bytes.len() && bytes[pos] != b'\n' {
pos += 1;
}
continue;
}
let start = pos;
let c = bytes[pos];
pos += 1;
let kind = if c.is_ascii_alphabetic() || c == b'_' {
while pos < bytes.len()
&& (bytes[pos].is_ascii_alphanumeric() || bytes[pos] == b'_')
{
pos += 1;
}
ident_or_keyword(&source[start..pos])
} else if c.is_ascii_digit() {
while pos < bytes.len() && bytes[pos].is_ascii_digit() {
pos += 1;
}
TokenKind::Int
} else {
match c {
b'+' => TokenKind::Plus,
b'-' if bytes.get(pos) == Some(&b'>') => {
pos += 1;
TokenKind::Arrow
}
b'-' => TokenKind::Minus,
b'*' => TokenKind::Star,
b'/' if bytes.get(pos) == Some(&b'*') => {
return Err(Error::new(
"lex",
Span {
start,
end: pos + 1,
},
"block comments are outside MicroRust; use //",
))
}
b'/' => TokenKind::Slash,
b':' => TokenKind::Colon,
b';' => TokenKind::Semicolon,
b',' => TokenKind::Comma,
b'(' => TokenKind::LParen,
b')' => TokenKind::RParen,
b'{' => TokenKind::LBrace,
b'}' => TokenKind::RBrace,
b'=' => TokenKind::Eq,
b'!' => TokenKind::Bang,
b'"' => {
while pos < bytes.len() && bytes[pos] != b'"' {
if !bytes[pos].is_ascii() || matches!(bytes[pos], b'\\' | b'\n' | b'\r')
{
return Err(Error::new(
"lex",
Span { start, end: pos },
"only the unescaped format string \"{}\" is supported",
));
}
pos += 1;
}
if pos == bytes.len() {
return Err(Error::new(
"lex",
Span { start, end: pos },
"unterminated string",
));
}
pos += 1;
TokenKind::String
}
_ => {
let ch = source[start..].chars().next().unwrap();
return Err(Error::new(
"lex",
Span {
start,
end: start + ch.len_utf8(),
},
format!("unexpected character '{ch}'"),
));
}
}
};
tokens.push(Token {
kind,
lexeme: source[start..pos].into(),
span: Span { start, end: pos },
});
}
tokens.push(Token {
kind: TokenKind::Eof,
lexeme: String::new(),
span: Span {
start: pos,
end: pos,
},
});
Ok(tokens)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Type {
I32,
Unit,
Never,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinOp {
Add,
Sub,
Mul,
Div,
}
#[derive(Debug, Clone)]
pub struct Program {
pub functions: Vec<Function>,
}
#[derive(Debug, Clone)]
pub struct Function {
pub name: String,
pub span: Span,
pub params: Vec<Param>,
pub return_type: Type,
pub body: Block,
}
#[derive(Debug, Clone)]
pub struct Param {
pub name: String,
pub span: Span,
}
#[derive(Debug, Clone)]
pub struct Block {
pub statements: Vec<Stmt>,
pub tail: Option<Box<Expr>>,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum Stmt {
Let {
name: String,
span: Span,
value: Expr,
},
Return {
value: Option<Expr>,
span: Span,
},
Expr(Expr),
}
#[derive(Debug, Clone)]
pub struct Expr {
pub kind: ExprKind,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum ExprKind {
Int(i32),
Name(String),
Binary {
op: BinOp,
left: Box<Expr>,
right: Box<Expr>,
},
Call {
callee: String,
args: Vec<Expr>,
},
Println {
value: Box<Expr>,
},
Block(Block),
}
impl BinOp {
pub fn checked(self, a: i32, b: i32) -> Option<i32> {
match self {
Self::Add => a.checked_add(b),
Self::Sub => a.checked_sub(b),
Self::Mul => a.checked_mul(b),
Self::Div => a.checked_div(b),
}
}
}
pub struct Parser {
tokens: Vec<Token>,
pos: usize,
}
impl Parser {
pub fn new(tokens: Vec<Token>) -> Self {
Self { tokens, pos: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.pos]
}
fn advance(&mut self) -> Token {
let t = self.peek().clone();
if t.kind != TokenKind::Eof {
self.pos += 1;
}
t
}
fn error(&self, message: &str) -> Error {
Error::new("parse", self.peek().span, message)
}
fn eat(&mut self, kind: TokenKind) -> bool {
if self.peek().kind == kind {
self.advance();
true
} else {
false
}
}
fn expect(&mut self, kind: TokenKind) -> Result<Token, Error> {
if self.peek().kind == kind {
Ok(self.advance())
} else {
Err(self.error(&format!("expected {kind:?}, found {:?}", self.peek().kind)))
}
}
fn ident(&mut self) -> Result<Token, Error> {
let token = self.expect(TokenKind::Ident)?;
// A restricted scanner must not turn Rust keywords into valid user names.
const RESERVED: &[&str] = &[
"_", "as", "async", "await", "break", "const", "continue", "crate", "dyn", "else",
"enum", "extern", "false", "for", "if", "impl", "in", "loop", "match", "mod",
"move", "mut", "pub", "ref", "self", "Self", "static", "struct", "super", "trait",
"true", "type", "unsafe", "use", "where", "while", "abstract", "become", "box",
"do", "final", "macro", "override", "priv", "typeof", "unsized", "virtual",
"yield", "try", "gen",
];
if RESERVED.contains(&token.lexeme.as_str()) {
return Err(Error::new(
"parse",
token.span,
"reserved Rust word is not an identifier",
));
}
Ok(token)
}
pub fn parse(mut self) -> Result<Program, Error> {
let mut functions = Vec::new();
while self.peek().kind != TokenKind::Eof {
functions.push(self.parse_function()?);
}
Ok(Program { functions })
}
fn parse_function(&mut self) -> Result<Function, Error> {
self.expect(TokenKind::Fn)?;
let name = self.ident()?;
self.expect(TokenKind::LParen)?;
let mut params = Vec::new();
while self.peek().kind != TokenKind::RParen {
let param = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
params.push(Param {
name: param.lexeme,
span: param.span,
});
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
let return_type = if self.eat(TokenKind::Arrow) {
self.expect(TokenKind::I32)?;
Type::I32
} else {
Type::Unit
};
let body = self.parse_block()?;
Ok(Function {
name: name.lexeme,
span: name.span,
params,
return_type,
body,
})
}
fn parse_block(&mut self) -> Result<Block, Error> {
let start = self.expect(TokenKind::LBrace)?.span.start;
let mut statements = Vec::new();
let mut tail = None;
while self.peek().kind != TokenKind::RBrace {
if self.peek().kind == TokenKind::Eof {
return Err(self.error("unclosed block"));
}
if self.eat(TokenKind::Let) {
let name = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
self.expect(TokenKind::Eq)?;
let value = self.parse_expr(0)?;
self.expect(TokenKind::Semicolon)?;
statements.push(Stmt::Let {
name: name.lexeme,
span: name.span,
value,
});
} else if self.peek().kind == TokenKind::Return {
let span = self.advance().span;
let value = if self.peek().kind == TokenKind::Semicolon {
None
} else {
Some(self.parse_expr(0)?)
};
self.expect(TokenKind::Semicolon)?;
statements.push(Stmt::Return { value, span });
} else {
let value = self.parse_expr(0)?;
if self.eat(TokenKind::Semicolon) {
statements.push(Stmt::Expr(value));
} else {
tail = Some(Box::new(value));
break;
}
}
}
let end = self.expect(TokenKind::RBrace)?.span.end;
Ok(Block {
statements,
tail,
span: Span { start, end },
})
}
fn current_infix(&self) -> Option<(BinOp, u8, u8)> {
match self.peek().kind {
TokenKind::Plus => Some((BinOp::Add, 20, 21)),
TokenKind::Minus => Some((BinOp::Sub, 20, 21)),
TokenKind::Star => Some((BinOp::Mul, 30, 31)),
TokenKind::Slash => Some((BinOp::Div, 30, 31)),
_ => None,
}
}
fn parse_expr(&mut self, min_bp: u8) -> Result<Expr, Error> {
let mut left = self.parse_prefix()?;
while let Some((op, left_bp, right_bp)) = self.current_infix() {
if left_bp < min_bp {
break;
}
self.advance();
let right = self.parse_expr(right_bp)?;
let span = Span {
start: left.span.start,
end: right.span.end,
};
left = Expr {
kind: ExprKind::Binary {
op,
left: Box::new(left),
right: Box::new(right),
},
span,
};
}
Ok(left)
}
fn parse_prefix(&mut self) -> Result<Expr, Error> {
match self.peek().kind {
TokenKind::Int => {
let t = self.advance();
let n = t.lexeme.parse::<i32>().map_err(|_| {
Error::new("parse", t.span, "integer literal is outside 0..=2147483647")
})?;
Ok(Expr {
kind: ExprKind::Int(n),
span: t.span,
})
}
TokenKind::Ident => {
let name = self.ident()?;
let kind = if self.eat(TokenKind::Bang) {
if name.lexeme != "println" {
return Err(Error::new(
"parse",
name.span,
"only println! is supported",
));
}
self.expect(TokenKind::LParen)?;
let format = self.expect(TokenKind::String)?;
if format.lexeme != "\"{}\"" {
return Err(Error::new(
"parse",
format.span,
"expected format string \"{}\"",
));
}
self.expect(TokenKind::Comma)?;
let value = self.parse_expr(0)?;
self.expect(TokenKind::RParen)?;
ExprKind::Println {
value: Box::new(value),
}
} else if self.eat(TokenKind::LParen) {
let mut args = Vec::new();
while self.peek().kind != TokenKind::RParen {
args.push(self.parse_expr(0)?);
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
ExprKind::Call {
callee: name.lexeme,
args,
}
} else {
ExprKind::Name(name.lexeme)
};
let end = self.tokens[self.pos - 1].span.end;
Ok(Expr {
kind,
span: Span {
start: name.span.start,
end,
},
})
}
TokenKind::LParen => {
self.advance();
let expr = self.parse_expr(0)?;
self.expect(TokenKind::RParen)?;
Ok(expr)
}
TokenKind::LBrace => {
let block = self.parse_block()?;
let span = block.span;
Ok(Expr {
kind: ExprKind::Block(block),
span,
})
}
_ => Err(self.error("expected expression")),
}
}
}
}
#[allow(dead_code)]
mod semantics {
use crate::syntax::{Block, Expr, ExprKind, Program, Stmt, Type};
use crate::{Error, Span};
use std::collections::{HashMap, HashSet};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SymbolId(pub usize);
#[derive(Debug, Clone)]
pub struct Symbol {
pub name: String,
pub kind: SymbolKind,
pub span: Span,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SymbolKind {
Function,
Local,
Parameter,
}
pub struct ResolvedProgram {
pub ast: Program,
pub symbols: Vec<Symbol>,
pub names: HashMap<usize, SymbolId>,
pub globals: HashMap<String, SymbolId>,
}
struct Resolver {
symbols: Vec<Symbol>,
names: HashMap<usize, SymbolId>,
globals: HashMap<String, SymbolId>,
scopes: Vec<HashMap<String, SymbolId>>,
}
pub fn resolve(ast: Program) -> Result<ResolvedProgram, Error> {
let mut r = Resolver {
symbols: vec![],
names: HashMap::new(),
globals: HashMap::new(),
scopes: vec![],
};
for f in &ast.functions {
if r.globals.contains_key(&f.name) {
return Err(Error::new(
"resolve",
f.span,
format!("duplicate function `{}`", f.name),
));
}
let id = r.declare(&f.name, SymbolKind::Function, f.span);
r.globals.insert(f.name.clone(), id);
}
for f in &ast.functions {
r.scopes.push(HashMap::new());
for p in &f.params {
if r.scopes.last().unwrap().contains_key(&p.name) {
return Err(Error::new("resolve", p.span, "duplicate parameter"));
}
let id = r.declare(&p.name, SymbolKind::Parameter, p.span);
r.scopes.last_mut().unwrap().insert(p.name.clone(), id);
}
r.block(&f.body)?;
r.scopes.pop();
}
Ok(ResolvedProgram {
ast,
symbols: r.symbols,
names: r.names,
globals: r.globals,
})
}
impl Resolver {
fn declare(&mut self, name: &str, kind: SymbolKind, span: Span) -> SymbolId {
let id = SymbolId(self.symbols.len());
self.symbols.push(Symbol {
name: name.into(),
kind,
span,
});
self.names.insert(span.start, id);
id
}
fn lookup_local(&self, name: &str) -> Option<SymbolId> {
self.scopes
.iter()
.rev()
.find_map(|scope| scope.get(name).copied())
}
fn block(&mut self, block: &Block) -> Result<(), Error> {
self.scopes.push(HashMap::new());
for stmt in &block.statements {
match stmt {
Stmt::Let { name, span, value } => {
self.expr(value)?;
let id = self.declare(name, SymbolKind::Local, *span);
self.scopes.last_mut().unwrap().insert(name.clone(), id);
}
Stmt::Return { value, .. } => {
if let Some(value) = value {
self.expr(value)?;
}
}
Stmt::Expr(value) => self.expr(value)?,
}
}
if let Some(tail) = &block.tail {
self.expr(tail)?;
}
self.scopes.pop();
Ok(())
}
fn expr(&mut self, expr: &Expr) -> Result<(), Error> {
match &expr.kind {
ExprKind::Int(_) => {}
ExprKind::Name(name) => {
let id = self.lookup_local(name).ok_or_else(|| {
Error::new(
"resolve",
expr.span,
format!("cannot find local `{name}` in this scope"),
)
})?;
self.names.insert(expr.span.start, id);
}
ExprKind::Binary { left, right, .. } => {
self.expr(left)?;
self.expr(right)?;
}
ExprKind::Call { callee, args } => {
if self.lookup_local(callee).is_some() {
return Err(Error::new(
"resolve",
expr.span,
format!("`{callee}` is a local, not a callable function"),
));
}
let id = self.globals.get(callee).copied().ok_or_else(|| {
Error::new(
"resolve",
expr.span,
format!("cannot find function `{callee}`"),
)
})?;
self.names.insert(expr.span.start, id);
for arg in args {
self.expr(arg)?;
}
}
ExprKind::Println { value } => self.expr(value)?,
ExprKind::Block(block) => self.block(block)?,
}
Ok(())
}
}
#[derive(Debug, Clone)]
pub struct FnSig {
pub params: Vec<Type>,
pub ret: Type,
}
pub struct TypedProgram {
pub resolved: ResolvedProgram,
pub signatures: HashMap<SymbolId, FnSig>,
pub types: HashMap<(usize, usize), Type>,
}
pub fn type_check(resolved: ResolvedProgram) -> Result<TypedProgram, Error> {
let main = resolved
.ast
.functions
.iter()
.find(|f| f.name == "main")
.ok_or_else(|| Error::new("type", Span { start: 0, end: 0 }, "missing fn main()"))?;
if !main.params.is_empty() || main.return_type != Type::Unit {
return Err(Error::new(
"type",
main.span,
"main must have no parameters and return unit",
));
}
let mut signatures = HashMap::new();
for f in &resolved.ast.functions {
if f.params.len() > 6 {
return Err(Error::new(
"type",
f.span,
"MicroRust supports at most six parameters",
));
}
signatures.insert(
resolved.globals[&f.name],
FnSig {
params: vec![Type::I32; f.params.len()],
ret: f.return_type,
},
);
}
let mut c = Checker {
resolved: &resolved,
signatures: &signatures,
types: HashMap::new(),
exits: HashSet::new(),
ret: Type::Unit,
};
for f in &resolved.ast.functions {
c.ret = f.return_type;
let actual = c.block(&f.body)?;
expect_type(f.return_type, actual, f.body.span)?;
}
let types = c.types;
Ok(TypedProgram {
resolved,
signatures,
types,
})
}
fn expect_type(expected: Type, actual: Type, span: Span) -> Result<(), Error> {
if actual == expected || actual == Type::Never {
Ok(())
} else {
Err(Error::new(
"type",
span,
format!("expected {expected:?}, found {actual:?}"),
))
}
}
struct Checker<'a> {
resolved: &'a ResolvedProgram,
signatures: &'a HashMap<SymbolId, FnSig>,
types: HashMap<(usize, usize), Type>,
exits: HashSet<(usize, usize)>,
ret: Type,
}
impl Checker<'_> {
fn block(&mut self, block: &Block) -> Result<Type, Error> {
let mut diverges = false;
for stmt in &block.statements {
match stmt {
Stmt::Let { value, .. } => {
let ty = self.expr(value)?;
expect_type(Type::I32, ty, value.span)?;
diverges |= self.exits.contains(&(value.span.start, value.span.end));
}
Stmt::Return { value, span } => {
let actual = match value {
Some(value) => self.expr(value)?,
None => Type::Unit,
};
expect_type(self.ret, actual, *span)?;
diverges = true;
}
Stmt::Expr(value) => {
self.expr(value)?;
diverges |= self.exits.contains(&(value.span.start, value.span.end));
}
}
}
let ty = if let Some(expr) = &block.tail {
let ty = self.expr(expr)?;
diverges |= self.exits.contains(&(expr.span.start, expr.span.end));
ty
} else if diverges {
Type::Never
} else {
Type::Unit
};
if diverges {
self.exits.insert((block.span.start, block.span.end));
}
// An explicit tail still has to type-check, even when unreachable.
Ok(ty)
}
fn expr(&mut self, expr: &Expr) -> Result<Type, Error> {
let ty = match &expr.kind {
ExprKind::Int(_) | ExprKind::Name(_) => Type::I32,
ExprKind::Binary { left, right, .. } => {
let a = self.expr(left)?;
let b = self.expr(right)?;
expect_type(Type::I32, a, left.span)?;
expect_type(Type::I32, b, right.span)?;
if a == Type::Never || b == Type::Never {
Type::Never
} else {
Type::I32
}
}
ExprKind::Call { callee, args } => {
let sig = self.signatures[&self.resolved.names[&expr.span.start]].clone();
if args.len() != sig.params.len() {
return Err(Error::new(
"type",
expr.span,
format!(
"function `{callee}` expects {} arguments but got {}",
sig.params.len(),
args.len()
),
));
}
let mut diverges = false;
for (arg, expected) in args.iter().zip(&sig.params) {
let actual = self.expr(arg)?;
expect_type(*expected, actual, arg.span)?;
diverges |= actual == Type::Never;
}
if diverges {
Type::Never
} else {
sig.ret
}
}
ExprKind::Println { value } => {
let ty = self.expr(value)?;
expect_type(Type::I32, ty, value.span)?;
if ty == Type::Never {
Type::Never
} else {
Type::Unit
}
}
ExprKind::Block(block) => self.block(block)?,
};
let exits = match &expr.kind {
ExprKind::Binary { left, right, .. } => {
self.exits.contains(&(left.span.start, left.span.end))
|| self.exits.contains(&(right.span.start, right.span.end))
}
ExprKind::Call { args, .. } => args
.iter()
.any(|arg| self.exits.contains(&(arg.span.start, arg.span.end))),
ExprKind::Println { value } => {
self.exits.contains(&(value.span.start, value.span.end))
}
ExprKind::Block(block) => self.exits.contains(&(block.span.start, block.span.end)),
_ => false,
};
if exits {
self.exits.insert((expr.span.start, expr.span.end));
}
self.types.insert((expr.span.start, expr.span.end), ty);
Ok(ty)
}
}
}
#[allow(dead_code)]
mod ir {
use crate::semantics::{SymbolId, TypedProgram};
use crate::syntax::{BinOp, Block, Expr, ExprKind, Stmt, Type};
use crate::{Error, Span};
use std::collections::{HashMap, HashSet};
pub type ValueId = usize;
pub type LocalId = SymbolId;
#[derive(Debug, Clone)]
pub struct IrProgram {
pub functions: Vec<IrFunction>,
}
#[derive(Debug, Clone)]
pub struct IrFunction {
pub name: String,
pub params: Vec<LocalId>,
pub ret: Type,
pub block: BasicBlock,
pub value_count: usize,
}
#[derive(Debug, Clone)]
pub struct BasicBlock {
pub instrs: Vec<SpannedInstr>,
pub terminator: Terminator,
}
#[derive(Debug, Clone)]
pub struct SpannedInstr {
pub instr: Instr,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum Instr {
Const {
dst: ValueId,
value: i32,
},
LoadLocal {
dst: ValueId,
local: LocalId,
},
StoreLocal {
local: LocalId,
src: ValueId,
},
Binary {
dst: ValueId,
op: BinOp,
left: ValueId,
right: ValueId,
},
Call {
dst: Option<ValueId>,
name: String,
args: Vec<ValueId>,
},
Println {
value: ValueId,
},
}
#[derive(Debug, Clone, Copy)]
pub enum Terminator {
Return(Option<ValueId>),
}
impl Instr {
pub fn destination(&self) -> Option<ValueId> {
match self {
Self::Const { dst, .. }
| Self::LoadLocal { dst, .. }
| Self::Binary { dst, .. } => Some(*dst),
Self::Call { dst, .. } => *dst,
_ => None,
}
}
pub fn inputs(&self) -> Vec<ValueId> {
match self {
Self::Binary { left, right, .. } => vec![*left, *right],
Self::StoreLocal { src, .. } => vec![*src],
Self::Println { value } => vec![*value],
Self::Call { args, .. } => args.clone(),
_ => vec![],
}
}
pub fn has_side_effects(&self) -> bool {
// Checked arithmetic can trap even if its result is never used.
!matches!(self, Self::Const { .. } | Self::LoadLocal { .. })
}
}
pub fn lower(typed: &TypedProgram) -> IrProgram {
let mut functions = Vec::new();
for f in &typed.resolved.ast.functions {
let mut l = Lowerer {
typed,
instrs: vec![],
terminator: None,
next: 0,
};
let tail = l.block(&f.body);
let terminator = l.terminator.unwrap_or(Terminator::Return(tail));
functions.push(IrFunction {
name: f.name.clone(),
params: f
.params
.iter()
.map(|p| typed.resolved.names[&p.span.start])
.collect(),
ret: f.return_type,
block: BasicBlock {
instrs: l.instrs,
terminator,
},
value_count: l.next,
});
}
IrProgram { functions }
}
struct Lowerer<'a> {
typed: &'a TypedProgram,
instrs: Vec<SpannedInstr>,
terminator: Option<Terminator>,
next: usize,
}
impl Lowerer<'_> {
fn new_value(&mut self) -> ValueId {
let id = self.next;
self.next += 1;
id
}
fn emit(&mut self, instr: Instr, span: Span) {
self.instrs.push(SpannedInstr { instr, span });
}
fn block(&mut self, block: &Block) -> Option<ValueId> {
for stmt in &block.statements {
if self.terminator.is_some() {
return None;
}
match stmt {
Stmt::Let { span, value, .. } => {
if let Some(src) = self.expr(value) {
let local = self.typed.resolved.names[&span.start];
self.emit(Instr::StoreLocal { local, src }, *span);
}
}
Stmt::Return { value, .. } => {
let value = value.as_ref().and_then(|v| self.expr(v));
if self.terminator.is_none() {
self.terminator = Some(Terminator::Return(value));
}
}
Stmt::Expr(expr) => {
self.expr(expr);
}
}
}
if self.terminator.is_some() {
None
} else {
block.tail.as_ref().and_then(|e| self.expr(e))
}
}
fn expr(&mut self, expr: &Expr) -> Option<ValueId> {
if self.terminator.is_some() {
return None;
}
let instr = match &expr.kind {
ExprKind::Int(value) => Instr::Const {
dst: self.new_value(),
value: *value,
},
ExprKind::Name(_) => Instr::LoadLocal {
dst: self.new_value(),
local: self.typed.resolved.names[&expr.span.start],
},
ExprKind::Binary { op, left, right } => {
let left = self.expr(left)?;
let right = self.expr(right)?;
Instr::Binary {
dst: self.new_value(),
op: *op,
left,
right,
}
}
ExprKind::Call { callee, args } => {
let mut values = Vec::new();
for arg in args {
values.push(self.expr(arg)?);
}
let sig = &self.typed.signatures[&self.typed.resolved.names[&expr.span.start]];
let dst = if sig.ret == Type::I32 {
Some(self.new_value())
} else {
None
};
Instr::Call {
dst,
name: callee.clone(),
args: values,
}
}
ExprKind::Println { value } => Instr::Println {
value: self.expr(value)?,
},
ExprKind::Block(block) => return self.block(block),
};
let dst = instr.destination();
self.emit(instr, expr.span);
dst
}
}
pub fn fold_constants(block: &mut BasicBlock) {
let mut constants = HashMap::<ValueId, i32>::new();
let mut locals = HashMap::<LocalId, i32>::new();
for item in &mut block.instrs {
let replacement = match &item.instr {
Instr::Const { value, .. } => Some(*value),
Instr::LoadLocal { local, .. } => locals.get(local).copied(),
Instr::Binary {
op, left, right, ..
} => constants
.get(left)
.zip(constants.get(right))
.and_then(|(a, b)| op.checked(*a, *b)),
Instr::StoreLocal { local, src } => {
if let Some(value) = constants.get(src) {
locals.insert(*local, *value);
} else {
locals.remove(local);
}
None
}
_ => None,
};
if let (Some(dst), Some(value)) = (item.instr.destination(), replacement) {
constants.insert(dst, value);
item.instr = Instr::Const { dst, value };
}
}
}
pub fn eliminate_dead_code(block: &mut BasicBlock) {
let mut used = HashSet::new();
let mut needed_locals = HashSet::new();
if let Terminator::Return(Some(value)) = block.terminator {
used.insert(value);
}
let mut kept = Vec::new();
for item in block.instrs.drain(..).rev() {
let live = item
.instr
.destination()
.is_some_and(|dst| used.contains(&dst));
let keep = match &item.instr {
Instr::StoreLocal { local, .. } => needed_locals.remove(local),
_ => live || item.instr.has_side_effects(),
};
if keep {
if let Instr::LoadLocal { local, .. } = &item.instr {
needed_locals.insert(*local);
}
used.extend(item.instr.inputs());
kept.push(item);
}
}
kept.reverse();
block.instrs = kept;
}
pub fn optimize(program: &mut IrProgram) {
for function in &mut program.functions {
fold_constants(&mut function.block);
eliminate_dead_code(&mut function.block);
}
}
pub fn verify(program: &IrProgram) -> Result<(), Error> {
let bad = |message| Error::new("IR", Span { start: 0, end: 0 }, message);
for f in &program.functions {
let mut values = HashSet::new();
let mut locals: HashSet<_> = f.params.iter().copied().collect();
for item in &f.block.instrs {
let instr = &item.instr;
if instr.inputs().iter().any(|v| !values.contains(v)) {
return Err(bad("value used before definition"));
}
if let Some(dst) = instr.destination() {
if dst >= f.value_count || !values.insert(dst) {
return Err(bad("invalid or duplicate destination"));
}
}
match instr {
Instr::LoadLocal { local, .. } if !locals.contains(local) => {
return Err(bad("load from uninitialized local"))
}
Instr::StoreLocal { local, .. } => {
locals.insert(*local);
}
Instr::Call { name, args, dst } => {
let callee = program
.functions
.iter()
.find(|c| c.name == *name)
.ok_or_else(|| bad("missing callee"))?;
if args.len() != callee.params.len()
|| dst.is_some() != (callee.ret == Type::I32)
{
return Err(bad("invalid IR call signature"));
}
}
_ => {}
}
}
let Terminator::Return(value) = f.block.terminator;
if value.is_some_and(|v| !values.contains(&v))
|| value.is_some() != (f.ret == Type::I32)
{
return Err(bad("invalid IR return"));
}
}
Ok(())
}
pub fn execute(program: &IrProgram) -> Result<Vec<i32>, Error> {
verify(program)?;
let mut runner = Runner {
program,
output: vec![],
budget: 1_000_000,
};
runner.call("main", &[], 0)?;
Ok(runner.output)
}
struct Runner<'a> {
program: &'a IrProgram,
output: Vec<i32>,
budget: usize,
}
impl Runner<'_> {
fn call(&mut self, name: &str, args: &[i32], depth: usize) -> Result<Option<i32>, Error> {
let error = |message| Error::new("runtime", Span { start: 0, end: 0 }, message);
if depth >= 256 {
return Err(error("IR runner call-depth limit reached"));
}
let f = self
.program
.functions
.iter()
.find(|f| f.name == name)
.ok_or_else(|| error("unknown function"))?;
let mut locals: HashMap<LocalId, i32> =
f.params.iter().copied().zip(args.iter().copied()).collect();
let mut values = vec![0; f.value_count];
for item in &f.block.instrs {
if self.budget == 0 {
return Err(error("IR runner instruction limit reached"));
}
self.budget -= 1;
match &item.instr {
Instr::Const { dst, value } => values[*dst] = *value,
Instr::LoadLocal { dst, local } => values[*dst] = locals[local],
Instr::StoreLocal { local, src } => {
locals.insert(*local, values[*src]);
}
Instr::Binary {
dst,
op,
left,
right,
} => {
values[*dst] =
op.checked(values[*left], values[*right]).ok_or_else(|| {
Error::new(
"runtime",
item.span,
"integer overflow or division by zero",
)
})?;
}
Instr::Call { dst, name, args } => {
let args: Vec<_> = args.iter().map(|v| values[*v]).collect();
let result = self.call(name, &args, depth + 1)?;
if let Some(dst) = dst {
values[*dst] = result.expect("verified i32 call");
}
}
Instr::Println { value } => self.output.push(values[*value]),
}
}
let Terminator::Return(value) = f.block.terminator;
Ok(value.map(|v| values[v]))
}
}
pub fn display(program: &IrProgram) -> String {
let mut text = String::new();
for f in &program.functions {
text.push_str(&format!("fn {}({:?}):\nbb0:\n", f.name, f.params));
for item in &f.block.instrs {
let line = match &item.instr {
Instr::Const { dst, value } => format!("%{dst} = const {value}"),
Instr::LoadLocal { dst, local } => format!("%{dst} = load #{}", local.0),
Instr::StoreLocal { local, src } => format!("store #{}, %{src}", local.0),
Instr::Binary {
dst,
op,
left,
right,
} => format!(
"%{dst} = {} %{left}, %{right}",
format!("{op:?}").to_lowercase()
),
Instr::Call { dst, name, args } => format!(
"{}call {name}({})",
dst.map_or(String::new(), |d| format!("%{d} = ")),
args.iter()
.map(|a| format!("%{a}"))
.collect::<Vec<_>>()
.join(", ")
),
Instr::Println { value } => format!("println %{value}"),
};
text.push_str(&format!(" {line}\n"));
}
let Terminator::Return(value) = f.block.terminator;
text.push_str(&format!(
" return{}\n",
value.map_or(String::new(), |v| format!(" %{v}"))
));
}
text
}
}
#[allow(dead_code)]
mod backend {
use crate::ir::{Instr, IrFunction, IrProgram, Terminator};
use crate::semantics::SymbolId;
use crate::syntax::BinOp;
use std::collections::HashMap;
use std::fmt::Write as _;
use std::path::{Path, PathBuf};
use std::process::Command;
use std::sync::atomic::{AtomicU64, Ordering};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Target {
Linux,
Macos,
}
impl Target {
pub fn host() -> Result<Self, String> {
if cfg!(target_os = "macos") {
Ok(Self::Macos)
} else if cfg!(all(target_os = "linux", target_arch = "x86_64")) {
Ok(Self::Linux)
} else {
Err("native builds require x86-64 Linux or macOS (Rosetta on Apple Silicon); use run for the portable IR runner".into())
}
}
fn symbol(self, name: &str) -> String {
match self {
Self::Linux => name.to_owned(),
Self::Macos => format!("_{name}"),
}
}
fn cc(self) -> Command {
let mut cc = Command::new("cc");
if matches!(self, Self::Macos) {
cc.args(["-arch", "x86_64"]);
}
cc
}
}
struct Frame {
locals: HashMap<SymbolId, usize>,
value_base: usize,
size: usize,
}
impl Frame {
fn new(f: &IrFunction) -> Self {
let mut locals = HashMap::new();
for local in f
.params
.iter()
.copied()
.chain(f.block.instrs.iter().filter_map(|i| match i.instr {
Instr::StoreLocal { local, .. } => Some(local),
_ => None,
}))
{
let offset = (locals.len() + 1) * 4;
locals.entry(local).or_insert(offset);
}
let value_base = locals.len() * 4;
let size = (value_base + f.value_count * 4).div_ceil(16) * 16;
Self {
locals,
value_base,
size,
}
}
fn value(&self, id: usize) -> usize {
self.value_base + (id + 1) * 4
}
}
pub fn assembly(program: &IrProgram, target: Target) -> String {
let mut out = String::from(".intel_syntax noprefix\n.text\n");
let regs = ["edi", "esi", "edx", "ecx", "r8d", "r9d"];
// Keep the C process entry separate from Rust's unit-valued main.
let main = target.symbol("main");
let entry = target.symbol("mr_main");
writeln!(out, ".globl {main}\n{main}:\n push rbp\n mov rbp, rsp\n call {entry}\n xor eax, eax\n pop rbp\n ret").unwrap();
for (index, f) in program.functions.iter().enumerate() {
let name = target.symbol(&format!("mr_{}", f.name));
let frame = Frame::new(f);
let trap = format!("L_microrust_trap_{index}");
writeln!(
out,
".globl {name}\n{name}:\n push rbp\n mov rbp, rsp\n sub rsp, {}",
frame.size
)
.unwrap();
for (param, reg) in f.params.iter().zip(regs) {
writeln!(
out,
" mov DWORD PTR [rbp - {}], {reg}",
frame.locals[param]
)
.unwrap();
}
for item in &f.block.instrs {
match &item.instr {
Instr::Const { dst, value } => {
writeln!(
out,
" mov DWORD PTR [rbp - {}], {value}",
frame.value(*dst)
)
.unwrap();
}
Instr::LoadLocal { dst, local } => {
writeln!(
out,
" mov eax, DWORD PTR [rbp - {}]\n mov DWORD PTR [rbp - {}], eax",
frame.locals[local],
frame.value(*dst)
)
.unwrap();
}
Instr::StoreLocal { local, src } => {
writeln!(
out,
" mov eax, DWORD PTR [rbp - {}]\n mov DWORD PTR [rbp - {}], eax",
frame.value(*src),
frame.locals[local]
)
.unwrap();
}
Instr::Binary {
dst,
op,
left,
right,
} => {
writeln!(out, " mov eax, DWORD PTR [rbp - {}]", frame.value(*left))
.unwrap();
match op {
BinOp::Div => {
// Guard both idiv traps so failure follows the same runtime path.
writeln!(out, " mov ecx, DWORD PTR [rbp - {}]\n test ecx, ecx\n jz {trap}\n cmp eax, -2147483648\n jne L_div_ok_{index}_{dst}\n cmp ecx, -1\n je {trap}\nL_div_ok_{index}_{dst}:\n cdq\n idiv ecx", frame.value(*right)).unwrap();
}
_ => {
let instruction = match op {
BinOp::Add => "add",
BinOp::Sub => "sub",
BinOp::Mul => "imul",
BinOp::Div => unreachable!(),
};
writeln!(
out,
" {instruction} eax, DWORD PTR [rbp - {}]\n jo {trap}",
frame.value(*right)
)
.unwrap();
}
}
writeln!(out, " mov DWORD PTR [rbp - {}], eax", frame.value(*dst))
.unwrap();
}
Instr::Call { dst, name, args } => {
for (arg, reg) in args.iter().zip(regs) {
writeln!(
out,
" mov {reg}, DWORD PTR [rbp - {}]",
frame.value(*arg)
)
.unwrap();
}
writeln!(out, " call {}", target.symbol(&format!("mr_{name}"))).unwrap();
if let Some(dst) = dst {
writeln!(out, " mov DWORD PTR [rbp - {}], eax", frame.value(*dst))
.unwrap();
}
}
Instr::Println { value } => {
writeln!(
out,
" mov edi, DWORD PTR [rbp - {}]\n call {}",
frame.value(*value),
target.symbol("microrust_print_i32")
)
.unwrap();
}
}
}
let Terminator::Return(value) = f.block.terminator;
if let Some(value) = value {
writeln!(out, " mov eax, DWORD PTR [rbp - {}]", frame.value(value)).unwrap();
}
writeln!(
out,
" mov rsp, rbp\n pop rbp\n ret\n{trap}:\n call {}\n ud2",
target.symbol("microrust_trap")
)
.unwrap();
}
if matches!(target, Target::Linux) {
out.push_str(".section .note.GNU-stack,\"\",@progbits\n");
}
out
}
fn run(command: &mut Command) -> Result<(), String> {
let output = command
.output()
.map_err(|e| format!("cannot run {command:?}: {e}"))?;
if output.status.success() {
Ok(())
} else {
Err(format!(
"{command:?} failed:\n{}",
String::from_utf8_lossy(&output.stderr)
))
}
}
static NEXT_DIR: AtomicU64 = AtomicU64::new(0);
pub struct WorkDir(pub PathBuf);
impl WorkDir {
pub fn new() -> Result<Self, String> {
for _ in 0..100 {
let path = std::env::temp_dir().join(format!(
"microrust-{}-{}",
std::process::id(),
NEXT_DIR.fetch_add(1, Ordering::Relaxed)
));
match std::fs::create_dir(&path) {
Ok(()) => return Ok(Self(path)),
Err(e) if e.kind() == std::io::ErrorKind::AlreadyExists => continue,
Err(e) => return Err(e.to_string()),
}
}
Err("cannot allocate build directory".into())
}
}
impl Drop for WorkDir {
fn drop(&mut self) {
let _ = std::fs::remove_dir_all(&self.0);
}
}
pub fn assemble(asm: &Path, object: &Path, target: Target) -> Result<(), String> {
run(target.cc().arg("-c").arg(asm).arg("-o").arg(object))
}
pub fn build_object(program: &IrProgram, output: &Path, target: Target) -> Result<(), String> {
let work = WorkDir::new()?;
let asm = work.0.join("main.s");
std::fs::write(&asm, assembly(program, target)).map_err(|e| e.to_string())?;
assemble(&asm, output, target)
}
}
fn expression(expr: &syntax::Expr) -> String {
use syntax::ExprKind;
match &expr.kind {
ExprKind::Int(value) => value.to_string(),
ExprKind::Name(name) => name.clone(),
ExprKind::Binary { op, left, right } => {
let symbol = match op {
syntax::BinOp::Add => "+",
syntax::BinOp::Sub => "-",
syntax::BinOp::Mul => "*",
syntax::BinOp::Div => "/",
};
format!("({} {symbol} {})", expression(left), expression(right))
}
ExprKind::Call { callee, args } => {
let args = args.iter().map(expression).collect::<Vec<_>>().join(", ");
format!("{callee}({args})")
}
ExprKind::Println { value } => format!("println({})", expression(value)),
ExprKind::Block(block) => format!("{{ {} }}", statements(block).join(" ")),
}
}
fn statements(block: &syntax::Block) -> Vec<String> {
let mut lines = Vec::new();
for statement in &block.statements {
let line = match statement {
syntax::Stmt::Let { name, value, .. } => {
format!("let {name}: i32 = {};", expression(value))
}
syntax::Stmt::Return { value, .. } => match value {
Some(value) => format!("return {};", expression(value)),
None => "return;".into(),
},
syntax::Stmt::Expr(value) => format!("{};", expression(value)),
};
lines.push(line);
}
if let Some(tail) = &block.tail {
lines.push(format!("tail {}", expression(tail)));
}
lines
}
fn print_tree(program: &syntax::Program) {
for function in &program.functions {
let params = function
.params
.iter()
.map(|param| format!("{}: i32", param.name))
.collect::<Vec<_>>()
.join(", ");
println!(
"fn {}({params}) -> {:?}",
function.name, function.return_type
);
for line in statements(&function.body) {
println!(" {line}");
}
}
}
fn main() {
if let Err(error) = run() {
eprintln!("{error}");
std::process::exit(1);
}
}
fn run() -> Result<(), String> {
const USAGE: &str = "usage: microrustc <tokens|ast|resolve|check|ir|run|asm|object> FILE [--no-opt] [-o OUTPUT] [--target linux|macos]";
let mut args = std::env::args().skip(1);
let mode = args.next().ok_or(USAGE)?;
if ![
"tokens", "ast", "resolve", "check", "ir", "run", "asm", "object",
]
.contains(&mode.as_str())
{
return Err(USAGE.into());
}
let mut path = None;
let mut output = None;
let mut target = None;
let mut optimize = true;
while let Some(arg) = args.next() {
match arg.as_str() {
"--no-opt" if matches!(mode.as_str(), "ir" | "run" | "asm" | "object") => {
optimize = false
}
"-o" if matches!(mode.as_str(), "asm" | "object") => {
output = Some(args.next().ok_or("missing output path")?);
}
"--target" if matches!(mode.as_str(), "asm" | "object") => {
target = Some(match args.next().as_deref() {
Some("linux") => backend::Target::Linux,
Some("macos") => backend::Target::Macos,
_ => return Err("expected linux or macos".into()),
});
}
_ if arg.starts_with('-') => return Err(format!("unknown option {arg}")),
_ if path.is_none() => path = Some(arg),
_ => return Err("more than one source file".into()),
}
}
let path = path.ok_or(USAGE)?;
let source = std::fs::read_to_string(&path).map_err(|error| format!("{path}: {error}"))?;
let render = |error: Error| error.render(&path, &source);
let tokens = syntax::lex(&source).map_err(render)?;
if mode == "tokens" {
print_tokens(&tokens);
return Ok(());
}
let ast = syntax::Parser::new(tokens).parse().map_err(render)?;
if mode == "ast" {
print_tree(&ast);
return Ok(());
}
let resolved = semantics::resolve(ast).map_err(render)?;
if mode == "resolve" {
print_symbols(&resolved);
return Ok(());
}
let typed = semantics::type_check(resolved).map_err(render)?;
if mode == "check" {
println!("checked {path}");
return Ok(());
}
let mut program = ir::lower(&typed);
ir::verify(&program).map_err(render)?;
if optimize {
ir::optimize(&mut program);
ir::verify(&program).map_err(render)?;
}
match mode.as_str() {
"ir" => print!("{}", ir::display(&program)),
"run" => {
for value in ir::execute(&program).map_err(render)? {
println!("{value}");
}
}
"asm" => {
let target = target.map_or_else(backend::Target::host, Ok)?;
let assembly = backend::assembly(&program, target);
if let Some(output) = output {
std::fs::write(&output, assembly).map_err(|e| e.to_string())?;
println!("wrote {output}");
} else {
print!("{assembly}");
}
}
"object" => {
let target = target.map_or_else(backend::Target::host, Ok)?;
if target != backend::Target::host()? {
return Err("object files and executables require the host platform's target; use asm for other targets".into());
}
let output = output.as_deref().unwrap_or("a.o");
backend::build_object(&program, std::path::Path::new(output), target)?;
println!("wrote {output}");
}
_ => unreachable!(),
}
Ok(())
}
fn print_tokens(tokens: &[syntax::Token]) {
for token in tokens {
println!(
"{:?} {:?} {}..{}",
token.kind, token.lexeme, token.span.start, token.span.end
);
}
}
fn print_symbols(program: &semantics::ResolvedProgram) {
for (index, symbol) in program.symbols.iter().enumerate() {
println!("#{index} {:?} {}", symbol.kind, symbol.name);
}
}The additions are the command runner, WorkDir, assemble, and build_object. Arguments are passed directly to cc, without building a shell command string. The temporary directory is removed when the build finishes, including when a tool reports an error.
Keep the same canonical input in example.mrs:
fn add(a: i32, b: i32) -> i32 {
return a + b;
}
fn main() {
let x: i32 = 5 + 3;
let y: i32 = x * 2;
let result: i32 = add(x, y);
println!("{}", result);
}From the parent of your microrust folder, run these commands. If you're already inside microrust, omit the first line:
cd microrust
rustc main.rs -o microrustc
./microrustc object example.mrs -o example.o
./microrustc run example.mrsThe expected output is:
wrote example.o
24We can inspect example.o with nm example.o. It should define main, mr_add, and mr_main, while leaving microrust_print_i32 and microrust_trap undefined. On macOS these names have a leading underscore.
Inspect relocations with otool -rv example.o on macOS or objdump -r example.o on Linux. There should be references to the runtime helpers. Addresses and formatting vary by platform, so the names and relocation targets are more useful than copying a particular offset.
The object command regenerates assembly for the host platform. It doesn't reuse a Linux-formatted example.s left from chapter 08 on a Mac. The driver rejects a different platform target for object creation; emitting text for that target is still possible with asm.
The final 24 in the output comes from the portable runner again. An object file cannot run by itself. The next chapter will supply the missing helper definitions and link it.
The object now contains our machine code, with unresolved references to the runtime helpers. In linking, we'll supply those definitions and combine the objects into an executable.