Complete month of August 2022¶
Handling instructions¶
We took care of all the dirty work inside the assembler during the previous posts. We now have a cleanly parsed instruction with an optional argument that we can evaluate. Let us dive into parse_instruction():
/// Handles a single instruction of opcode an optional oparg parsed from Assembly file.
fn parse_instruction(&mut self, opname: &str, oparg: Option<&str>) -> Result<(), AsmError> {
match opname {
"nop" => self.parse_a0_instruction(op::NOP, oparg),
"fin" => self.parse_a0_instruction(op::FIN, oparg),
"pop" => self.parse_a0_instruction(op::POP, oparg),
"add" => self.parse_a0_instruction(op::ADD, oparg),
"sub" => self.parse_a0_instruction(op::SUB, oparg),
"mul" => self.parse_a0_instruction(op::MUL, oparg),
"div" => self.parse_a0_instruction(op::DIV, oparg),
"mod" => self.parse_a0_instruction(op::MOD, oparg),
"push_u8" => {
let oparg = oparg.ok_or(AsmError::MissingArgument)?;
let v = parse_int::parse::<u8>(oparg).or(Err(AsmError::InvalidArgument))?;
self.push_a1_instruction(op::PUSH_U8, v)
},
"goto" => {
let oparg = oparg.ok_or(AsmError::MissingArgument)?;
let v = parse_int::parse::<i16>(oparg).or(Err(AsmError::InvalidArgument))?;
let a = v.to_be_bytes();
self.push_a2_instruction(op::GOTO, a[0], a[1])
},
_ => Err(AsmError::UnknownInstruction(String::from(opname)))
}
}
That is a surprisingly simple function. It receives two parameters. opname is a &str that holds the opname of the instruction. oparg is either None, if there was no argument in the instruction, or it holds a none-empty string that holds whatever argument was present in the instruction.
The function only consists of a long match, that directly matches the opname against our known opnames. If there is no match, it returns a helpful error that even contains the unknown opname that was found.
The explicit branches look a bit weirder. That is because I do not like to repeat myself when writing code. And Rust tends to allow some very dense source code.
Different kind of instructions¶
I decided to group by instructions into three categories. They are grouped by the number of bytes an instruction uses as argument. An a0 instruction has zero bytes of oparg, a1 has one byte, and a2 has two bytes.
a0¶
Most of our operations do not allow any argument at all. We want to make sure that there is none given in the instruction. And the only difference in handling those instructions inside the assembler is the byte that will be written to the bytecode. We can handle all of those with the same function: parse_a0_instruction():
/// Helper that parses an instruction with no oparg and pushes it.
fn parse_a0_instruction(&mut self, opcode: u8, oparg: Option<&str>) -> Result<(), AsmError> {
if oparg.is_some() {
Err(AsmError::UnexpectedArgument)
} else {
self.push_a0_instruction(opcode)
}
}
If we did get an argument, we fail, since that is not allowed. And then we push a very basic instruction to the back of our program. We have helper functions to do that:
/// Adds a single instruction to the end of the AsmProgram.
fn push_instruction(&mut self, i: AsmInstruction) -> Result<(), AsmError> {
self.text_pos += i.size();
self.instructions.push(i);
Ok(())
}
/// Helper that creates an instruction with 0 bytes of oparg and pushes it.
fn push_a0_instruction(&mut self, opcode: u8) -> Result<(), AsmError> {
let i = AsmInstruction{
line_number: self.line_number,
opcode,
oparg: vec![],
pos: self.text_pos,
};
self.push_instruction(i)
}
We create a new instruction instance and add it. We also track the position of every instruction in the bytecode, that is why we update the programs current position in the bytecode for every instruction we add (stored in text_pos).
There is nothing we do with that information, yet. But we will need that information later.
a1: push_u8¶
We only have one operation that needs a single byte of oparg, and that is push_u8. We use that operation to push values on the stack, taken directly from the bytecode. u8 is the only type supported at the moment. That is not even a hard restriction; you can easily get any i64 value to the stack by using basic arithmetics, and we have those.
Parsing numbers is no fun. It is hard. So we let someone else do it for us. The crate we are using is called parse_int. Go take a look at what it can do. It allows us to enter numbers easily in hexadecimal, octal, or binary notation. That is a really handy feature in source code! Thanks, Rust community! So how are we parsing push_u8?
"push_u8" => {
let oparg = oparg.ok_or(AsmError::MissingArgument)?;
let v = parse_int::parse::<u8>(oparg).or(Err(AsmError::InvalidArgument))?;
self.push_a1_instruction(op::PUSH_U8, v)
},
First we make sure that we have an argument. If not, we fail. We can again use our handy ? syntax. Then we try to parse it into a u8, using parse_int. The syntax for that call takes some getting used to - I'm still waiting for me to getting used to it. But if it works, we now have a valid u8. If it fails to parse, we quickly return with that failure information. If all goes well we will reach the third line, that calls our helper for adding a1 instructions. There is no big surprise in what that function does:
/// Helper that creates an instruction with 1 byte of oparg and pushes it.
fn push_a1_instruction(&mut self, opcode: u8, a0: u8) -> Result<(), AsmError> {
let i = AsmInstruction{
line_number: self.line_number,
opcode,
oparg: vec![a0],
pos: self.text_pos,
};
self.push_instruction(i)
}
An interesting detail is, that push_instruction() returns a Result, even though it can never fail! It always returns Ok(()). And if you look at push_a2_instruction(), you will now see that it also will always return Ok(()). We do be bother? Take a look at the handler for push_u8 again, in context of the complete function parse_instruction(). That function returns a Result, and it can return Err(...). Because push_a1_instruction() has the same return value of Result, the calls integrate nicely with the layout of the complete function inside the match. For me, it gives the code a clean compactness.
a2: goto¶
There is one more branch to look at:
"goto" => {
let oparg = oparg.ok_or(AsmError::MissingArgument)?;
let v = parse_int::parse::<i16>(oparg).or(Err(AsmError::InvalidArgument))?;
let a = v.to_be_bytes();
self.push_a2_instruction(op::GOTO, a[0], a[1])
},
This time we use parse_int to read a i16. Whether you like the ::<i16> syntax or not, at least you can see what it is for. We need to unpack the two bytes of the i16 after parsing, so that we can store the bytes correctly in the bytecode. to_be_bytes() gives us an array (of size 2) that holds the bytes in big endian byte order. to_le_bytes() is the little endian counterpart. I generally prefer big endian, when I can. And if you remember how we read the bytes in the VM, you can see that we are already using big endian there.
There is nothing new in the push_a2_instruction() function, only one additional byte.
/// Helper that creates an instruction with 1 byte of oparg and pushes it.
fn push_a2_instruction(&mut self, opcode: u8, a0: u8, a1: u8) -> Result<(), AsmError> {
let i = AsmInstruction{
line_number: self.line_number,
opcode,
oparg: vec![a0, a1],
pos: self.text_pos,
};
self.push_instruction(i)
}
Parsing completed¶
We have now parsed the complete program source into the AsmPgm structure. Or we have failed to do so, in which case there is an Error stored in AsmPgm. Either way, you have now seen all the code that does the parsing. Next journal entry will finally produce the bytecode we are longing for.
Assembling bytes¶
Our new assembler is almost done assembling. Over the last entries we learned how the program parses the assembly sourcecode and produces a list of parsed instructions. What we now need to do, is turn that into bytes.
Parsed¶
Let us take a look at where we are. We have our sample program hallo-stack.lass:
If we debug-print the AsmPgm after the parsing, it looks like this:
AsmPgm {
name: "pgm/hallo-stack.lass",
instructions: [
AsmInstruction { line_number: 1, opcode: 2, oparg: [123], pos: 0 },
AsmInstruction { line_number: 2, opcode: 2, oparg: [200], pos: 2 },
AsmInstruction { line_number: 3, opcode: 16, oparg: [], pos: 4 },
AsmInstruction { line_number: 4, opcode: 1, oparg: [], pos: 5 },
AsmInstruction { line_number: 5, opcode: 255, oparg: [], pos: 6 }
],
line_number: 5,
text_pos: 7,
error: None
}
No error, that is nice. And we can see all five instructions parsed. We have a function that connects those bytes.
Connect the bytes¶
/// Convert parsed assembly source to runnable program (or error report).
fn to_program(&self) -> Result<Pgm, AsmErrorReport> {
if let Some(e) = &self.error {
// Assembling failed:
Err(AsmErrorReport{
name: self.name.clone(),
line: self.line_number,
error: e.clone(),
})
} else {
// Assembling succeeded, return a Pgm instance:
let mut text: Vec<u8> = vec![];
for i in &self.instructions {
text.push(i.opcode);
text.extend(&i.oparg);
}
Ok(Pgm{
name: self.name.clone(),
text,
})
}
}
The error part is straightforward. A small detail is the clone() call for name and error. We need to do that, because we cannot move ownership of those values (they must still exist in the AsmPgm instance). And we cannot use references. There is no need to clone the line number; as an integer type it can simply be copied.
The success part isn't complex either. We create a Vector of bytes and push all bytes into it: for each instruction the opcode and the opargs (which there can be zero). We have our bytecode now! Wrap it inside our new Pgm type, and we are done.
Run the assembler¶
Let us see what our program looks like, assembled:
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- pgm/hallo-stack.lass
Finished dev [unoptimized + debuginfo] target(s) in 0.02s
Running `target/debug/lovas pgm/hallo-stack.lass`
Pgm { name: "pgm/hallo-stack.lass", text: [2, 123, 2, 200, 16, 1, 255] }
And how about our noisy program, noice.lass?
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- pgm/noise.lass
Finished dev [unoptimized + debuginfo] target(s) in 0.03s
Running `target/debug/lovas pgm/noise.lass`
Pgm { name: "pgm/noise.lass", text: [2, 123, 2, 200, 16, 1, 255] }
So it does produce the same bytecode for both. As we demanded.
Running into errors¶
What happens, if our program has errors? Easy to find out, I included a broken program: syntax-error.lass
Have you found the problem? Will the assembler?
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- pgm/syntax-error.lass
Finished dev [unoptimized + debuginfo] target(s) in 0.04s
Running `target/debug/lovas pgm/syntax-error.lass`
Error: assembly failed in line 2 of program 'pgm/syntax-error.lass'
Caused by:
InvalidArgument
It does find the error. Using the parse_int create already pays. And the error message really tells us, what is wrong and where. We get a lot of value for very few code we have written.
Why AsmPgm?¶
There does not really seem to be a point of storing all that information inside AsmPgm. We could easily have created the bytecode directly. That would have been a lot easier. And if you have run the code yourself, you will have been bombarded with compiler warnings about unread fields.
We will be needing that information soon, and it was easiest to build it like this right away. But let us just enjoy our new assembler for now.
impl error::Error¶
Okay, before we leave for today, one more thing that you might have spotted. What's with that impl blocks?
impl Display for AsmError {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
write!(f, "{:?}", self)
}
}
impl error::Error for AsmError {
}
impl Display for AsmErrorReport {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
write!(f, "assembly failed in line {} of program '{}'", self.line, self.name)
}
}
impl error::Error for AsmErrorReport {
fn source(&self) -> Option<&(dyn error::Error + 'static)> {
Some(&self.error)
}
}
That is the price we have to pay when we want to use Rust magic. Rust's answer to writing generic code that can be applied to different types (that might not exist at the time of writing) are traits. A function can accept a trait as a type. If you implement that trait for your type, you can use that function. That is a very simplified introduction.
A trait defines specific functions you have to write for a type. That is what we do here. We implement the trait std::error::Error for our AsmError and AsmErrorReport. To do so, we must also implement the trait std::fmt::Display (because the Error trait says so).
There is not much we do there. Types implementing the Display trait can be printed using println!("{}", value). What the println! macro does is just calling that fmt method we define. The trait Debug does a similar thing, but for use with println!("{:?}", value). We can use any value with those constructs that implements the Display trait (for "{}") or the Debug trait (for "{:?}").
The Debug trait we let the compiler implement (derive) for us. That is what the line #[derive(Debug)] does. And for our Display trait we are lazy and just use the function that was created by #[derive(Debug)].
The Error trait lets you implement a source() method, that is used to get a nested Error inside your Error, that was its cause. Think of exception stacks, only that we do not have exceptions, of course. That is exactly what we want for AsmErrorReport; it is, after all, a wrapper for AsmError. AsmError on the other hand does not have a nested error, so we do not implement the source() method. The empty impl error::Error for AsmError block is still needed. If you remove it, the Error trait will not be implemented for AsmError.
Cool story, but why do we do all this? This is what enables us to use the magic of anyhow in our lovas.rs. We can use AsmError and AsmErrorReport (wrapped in an Err()) as return for our main function. It returns anyhow::Result<()>. And when there is an error returned by it, an error message is created and printed for us. With this we can easily create useful error messages in the error type itself, at the place where we understand, what errors exist and what they mean. And we need do it in that one place only. Every program that uses our library (as lovas.rs does) benefits from that without any extra work or even without knowing, error types can be returned by the library.
Running assembler programs¶
We will extend our assembler to do something useful, finally: execute our programs on lovem.
We have created ourselves an assembler in ~300 lines of code. And it has a command line interface, an API to be used in a program, and even useful error reporting. That is cool! But what do we do with the bytecode? It just dumps them to the console. That is not very useful. We could copy/paste that into one of our example binaries... This is not what we wanted. So let us enhance our assembler.
Execution¶
We add some features to lovas.rs. A new command line parameter --run, that takes no arguments. If you add that flag to the call, lovas will take the assembled program (if there are no errors), create an instance of the VM and run the program on it. Thanks to clap, that is really easy to do. We add another field to our Cli struct. Actually, while we are at it, we add four new parameters:
##[clap(short, long, help = "Run the assembled program in lovem.")]
run: bool,
##[clap(long, help = "Enable tracing log when running lovem.")]
trace: bool,
##[clap(long, help = "Output the program to stdout.")]
print: bool,
##[clap(long, default_value_t = 100, help = "Setting the stack size for lovem when running the program.")]
stack_size: usize,
And we change what we do with a successfully created program, depending on our new flag:
// run the assembler:
match asm::assemble(&name, &content) {
Ok(pgm) => {
if args.print {
println!("{:?}", pgm);
}
// we succeeded and now have a program with bytecode:
if args.run {
// lovas was called with `--run`, so create a VM and execute program:
run(&pgm, &args)?
}
Ok(())
},
Err(e) => {
// Something went wrong during assembly.
// Convert the error report, so that `anyhow` can do its magic
// and display some helpful error message:
Err(Error::from(e))
},
}
Just printing the program to stdout is no very useful default behaviour for an assembler. It might still come in handy, if you want to see what you are executing, so we make it optional and for the caller to decide with the --print flag. If the --run flag is set, we call run(). So what does run() do?
/// Executes a program in a freshly created lovem VM.
fn run(pgm: &Pgm, args: &Cli) -> Result<()> {
// Create our VM instance.
let mut vm = VM::new(args.stack_size);
vm.trace = args.trace;
let start = Instant::now();
let outcome = vm.run(&pgm.text);
let duration = start.elapsed();
match outcome {
Ok(_) => {
// Execution successful, program terminated:
eprintln!("Terminated.\nRuntime={:?}\nop_cnt={}, pc={}, stack-depth={}, watermark={}",
duration,
vm.op_cnt, vm.pc, vm.stack.len(), vm.watermark
);
Ok(())
},
Err(e) => {
// Runtime error. Error will be printed on return of main.
eprintln!("Runtime error!\nRuntime={:?}\nop_cnt={}, pc={}, stack-depth={}, watermark={}",
duration, vm.op_cnt, vm.pc, vm.stack.len(), vm.watermark);
Err(Error::from(e))
}
}
}
We create a VM instance, and we run the program on it. If there is a RuntimeError, we return it, just as we did with the AsmErrorReport. Back in our examples, we created a VM with a stack size of 100 - simply because we needed a number there. 100 is still the default, but now you can choose the stack size, when calling lovas. If you do
lovas --run pgm/some-program.lva --stack-size 512
lovas will execute the program in a VM with a stack that can hold 512 values.
Trace Log¶
When we were running a program in our VM, we did always get a lot of output during execution. That is nice for understanding, what a stack machine does, but in general it is not a got idea for a VM to do that. It can be very beneficial, if you run into a problem with your program, so it is an easily available tool for debugging. That is why I removed all those log messages from lovem, but I let some in that can be activated, if you set vm.trace = true. That is what we added the new command line parameter --trace for. You can now control, if you want to see it.
Diagnostics¶
There is some output by lovas, after the execution. It reports if the run was successfully terminated (by executing a fin instruction), or if there was a RuntimeError. In both cases it will show you the time the execution took (wallclock time), as well as the number of instructions executed by the VM, the final position of the programm counter, the number of values on the stack at termination, and the highest number of values on the stack at any time during execution (the watermark). This can give you some quick insight on what your program did and maybe where it ran into trouble.
All this lead to some changes to vm.rs, but nothing that should give you any problems to understand. Remember that we have the power of git at our disposal, so you can easily find out what changed in a file between two releases. You could do that for vm.rs with this handy link:
Our programs¶
We have written a few example programs so far. Each is its own binary in src/bin/, and all of them consist of the same Rust code of creating a VM and running a program. Only the bytecode changed between them.
I got rid of all of those (except for the most basic one) and translated the programs into assembly programs that live in pgm/. You can now execute those using lovas, like this:
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- -r pgm/reverse-polish.lva --trace
Compiling lovem v0.0.9 (/home/kratenko/git/lovem)
Finished dev [unoptimized + debuginfo] target(s) in 2.02s
Running `target/debug/lovas -r pgm/reverse-polish.lva --trace`
VM { stack: [], pc: 0, op_cnt: 0, trace: true, watermark: 0 }
Executing op 0x02
VM { stack: [5], pc: 2, op_cnt: 1, trace: true, watermark: 1 }
Executing op 0x02
VM { stack: [5, 7], pc: 4, op_cnt: 2, trace: true, watermark: 2 }
Executing op 0x02
VM { stack: [5, 7, 11], pc: 6, op_cnt: 3, trace: true, watermark: 3 }
Executing op 0x11
VM { stack: [5, -4], pc: 7, op_cnt: 4, trace: true, watermark: 3 }
Executing op 0x12
VM { stack: [-20], pc: 8, op_cnt: 5, trace: true, watermark: 3 }
Executing op 0x02
VM { stack: [-20, 13], pc: 10, op_cnt: 6, trace: true, watermark: 3 }
Executing op 0x02
VM { stack: [-20, 13, 17], pc: 12, op_cnt: 7, trace: true, watermark: 3 }
Executing op 0x10
VM { stack: [-20, 30], pc: 13, op_cnt: 8, trace: true, watermark: 3 }
Executing op 0x10
VM { stack: [10], pc: 14, op_cnt: 9, trace: true, watermark: 3 }
Executing op 0x01
VM { stack: [], pc: 15, op_cnt: 10, trace: true, watermark: 3 }
Terminated!
VM { stack: [], pc: 16, op_cnt: 11, trace: true, watermark: 3 }
Terminated.
Runtime=49.33µs
op_cnt=11, pc=16, stack size=0, watermark=3
Remember to add --trace to the call, or you won't see very much. It has become a lot easier, to play around with the VM. No more writing bytecode by hand!
File extension¶
You might have noticed that I changed the filename extension that I use for the assembly programs from .lass to .lva. There are multiple reasons, but the main one is, that I thought Lass could be a nice name for a programming language, when I will finally come to writing one for lovem. So I want to reserve the extension for that possible future.
Playing around¶
The diagnostic information given after the execution can be interesting, when you mess around. Let us play a bit with the program endless-stack.lva.
## This program runs in an endless loop, but it will push a new value to the stack on every iteration.
## It will inevitably lead to a stack overrun at some point and crash the program.
push_u8 123
goto -5
fin
The program will fill the stack until it is full, and then it will crash:
Running `target/debug/lovas -r pgm/endless-stack.lva --print`
Pgm { name: "pgm/endless-stack.lva", text: [2, 123, 32, 255, 251, 255] }
Runtime error!
Runtime=41.589µs
op_cnt=201, pc=2, stack-depth=100, watermark=100
Error: StackOverflow
After 201 executed instructions it crashes. The stack depth at the time of the crash is 100. That is the complete stack, the next instruction tried to push value 101, which must fail. Instruction number 201 did cause the crash. That makes sense, if you follow the execution in your head. And the program counter is on 2. The last instruction executed will be the one before that, which would be at 0. That is the push_u8 instruction. There is no surprise that the watermark is at 100. That is the highest possible value for it and also the current value of out stack depth.
As we can now easily change the stack size, let us try what happens with a bigger stack:
Running `target/debug/lovas -r pgm/endless-stack.lva --print --stack-size 150`
Pgm { name: "pgm/endless-stack.lva", text: [2, 123, 32, 255, 251, 255] }
Runtime error!
Runtime=47.648µs
op_cnt=301, pc=2, stack-depth=150, watermark=150
Error: StackOverflow
So now the stack overflows at over 150 values, of course. And it takes 301 instructions to fill it. Runtime has been longer, but only about 15%. I would not have expected a rise of 50%, as there is overhead for starting the program.
What happens, if we activate --trace?
Running `target/debug/lovas -r pgm/endless-stack.lva --print --stack-size 150 --trace`
Pgm { name: "pgm/endless-stack.lva", text: [2, 123, 32, 255, 251, 255] }
VM { stack: [], pc: 0, op_cnt: 0, trace: true, watermark: 0 }
Executing op 0x02
VM { stack: [123], pc: 2, op_cnt: 1, trace: true, watermark: 1 }
Executing op 0x20
[...]
Executing op 0x02
Runtime error!
Runtime=67.312973ms
op_cnt=301, pc=2, stack-depth=150, watermark=150
Error: StackOverflow
There is, of course, a lot of output, that I cut out. What is interesting is the change in execution time. I ran this inside the CLion IDE by JetBrains. The console there will not be a very fast console, as it does a lot with that output coming through. But the impact of the logging is enormous! The runtime until we hit our stack overflow is more than 1000 times longer! The exact numbers don't mean anything; we are running unoptimised Rust code with debuginfo, and the bottleneck is the console. But it is still fascinating to see.
You labeled me, I'll label you¶
We add a feature to our assembler that we overlooked before.
Over the last few entries we created ourselves a really useful little assembler program. I hope you played around with it and enjoyed not having to write bytecode directly. If you did, you should have noticed that I left out a really important detail. Remember when I was complaining about how bad writing bytecode is? And that it got even worth, when we introduced jumps? Yeah, I did not solve that problem at all. If anything, I made it worse, because you still have to count the relative bytes to your destination, but you do not see those bytes any longer. You just have to know, how many bytes each instruction will produce.
Labels¶
There was so much already going on in that assembler program, that I did not want to introduce more complexity up front. Let's fix that now: we will introduce a way to give a position inside your program a name, so that you can goto that name later. And in good tradition, we will call this names labels.
The traditional way of defining labels in assembly is by writing them first thing on a line, followed by a colon :. Take a look at this little program, label.lva. It is neither good style, nor does it do anything useful, but it shows us labels:
| pgm/label.lva | |
|---|---|
There are two labels defined here: back in line 5, and coda in line 9. A label definition is a short string that is directly followed by a colon :. We restrict it to letters, numbers, and underscore, with a letter at the front. For the curious, the regex is: ^[A-Za-z][0-9A-Za-z_]{0,31}$. As you can see in the example, there can be an optional instruction in the same line as the label definition. Now, how will our assembler parse those?
Reconstruction¶
First of all, I did a little reconstruction inside asm.rs, because I did not like how the parsing was done inside an associated function, that also created the AsmPgm instance. That seems messed up. After the change, the fn assemble() creates the instance itself and then calls a method on it, to parse the source code. Here is the new version:
And there is no problem with us changing the code like this. The only public function inside asm.rs is that pub fn assemble(). All methods of AsmPgm are private and therefore internal detail. Not that it would matter at this state of development, but it demonstrates how separation of public API and internal implementation work.
What is also new in that function is a new field inside AsmPgm: labels.
/// A assembler program during parsing/assembling.
##[derive(Debug)]
struct AsmPgm {
...
/// A map storing label definitions by name with there position in bytecode.
labels: HashMap<String, usize>,
}
It is a HashMap (aka. associative array in other languages). This is where we put all label definitions we find, while parsing the source file. It maps the label's name to its position inside the bytecode. Here we can look up where to jump, for a goto that wants to jump to a label.
This is what our parsing methods now look like:
The important part is, that we have to steps now. We parse the complete source, as before. The second run is needed to write the actual relative jump address to the instructions. We do not know them during parsing, at least not for jumps forward.
Parsing label definitions¶
I got a little fancy again, while writing the function for parsing label definitions:
The method is trying to find a label definition in the line, and if so, handles it. We use our trusted Result<> returning, to communicate potential errors. But instead of Ok(()), which is the empty okay value, we return a &str on success. This is because there might also be an instruction in the line. If we find a label definition, it returns the line after the colon. If there is none, it returns the complete line it got. This gives us the lines as we used to get before we introduced labels. Great. But what is that weird 'a that shows up in that highlighted line everywhere?
Lifetime¶
Yeah, this is where it becomes rusty, again. I said, in an early post, that you would hate the Rust compiler and its pedantic error messages. The thing Rust is most pedantic about, is ownership and access to values you do not own. We are working with references to Strings here. A &str references the bytes inside that String directly (a &str need not reference a String, but it does here). We did that before, where is the problem now? This is the first time we are returning a &str.
When you are using references, Rust makes sure that the value you are referencing exists at least as long as the reference exists. That is easy for functions, as long as you drop every reference you have when you are done. But in this function, we return a reference to the parameter we got. Rust cannot allow that without some special care. When I remove the 'a parts of the method, I get a compilation error:
error[E0623]: lifetime mismatch
--> src/asm.rs:277:21
|
269 | fn parse_label_definition(&mut self, line: &str) -> Result<&str, AsmError> {
| ---- ----------------------
| |
| this parameter and the return type are declared with different lifetimes...
...
277 | Ok(rest)
| ^^^^^^^^ ...but data from `line` is returned here
|
= note: each elided lifetime in input position becomes a distinct lifetime
help: consider introducing a named lifetime parameter and update trait if needed
|
269 | fn parse_label_definition<'a>(&'a mut self, line: &'a str) -> Result<&str, AsmError> {
| ++++ ++ ++
The compiler tells me, that I messed up the lifetimes. It even proposes a change that introduces lifetime parameters (but gets it slightly wrong). What do we do with the 'a?
Well we introduce a lifetime parameter called a. The syntax for that is the apostrophe, which looked weird to me at start, but it is so lightweight, that I came to like it. It is custom, to just call your lifetimes 'a, 'b, ... – they normally don't have a long scope anyway. The thing we are telling the compiler with this parameter is this: the lifetime of the returned &str is dependent on the lifetime of the parameter line: &str. So whenever the reference the function is called with runs out of scope, the reference that was returned must be out of scope as well.
An example¶
This is a concept that is new to many programmers when they learn Rust. I think, what we do here demonstrates it quiet well. Let us look at what happens for line 9 of our assembly program:
| pgm/label.lva | |
|---|---|
Our function receives a reference to a String holding that line: " coda: push_u8 2". It finds the label coda and stores it inside self.labels. Its work is done, but there might be more to this line. It returns a reference to a substring of it (&str are actually slices; they can reference only a part of a String's data). That is what we return, a reference to the part data inside the String, starting at the first char after the colon, so it looks like this " push_u8 2". It is not a copy, it is the same area inside the computer's memory! So if you want to make certain, that there are no accesses to memory after its content has run out of scope (use after free, or use of local variable after it runs our of scope), you must not allow access to it, unless you are sure the value still exists. And this is what Rust does. This is what makes Rust a secure language. Many bugs and exploits in the world exist, because most languages do not check this, but leave the responsibility to the programmer. And the really cool thing about Rust is, it does this completely at compile time, as you can see by the fact that we got a compiler error.
The way we call our function is not a problem at all:
| src/asm.rs | |
|---|---|
Our initial line comes from line 228. It is already a reference, because content.lines() is also giving us a reference to the memory inside of content. That is a reference already, the String variable that holds (and owns) the data lives inside lovas.rs:
| src/bin/lovas.rs | |
|---|---|
We do not copy any of that bytes along the way. The first time we do that is in clean_line(). Returning a &str will not work there, because we actually modify the contents of the string, by replacing characters inside it. Have you ever tried to work with inplace "substrings" (I mean char arrays, like this char *str), without modifying the contents (placing \0 bytes). It is not fun. In Rust, it can be, if you understand lifetime restrictions.
Easy way out¶
If you run into problems with your &str inside a Rust program, there is often an easy way to get around that. You can simply create a new String from your &str, as we do in clean_line(). That will copy the bytes. For our program, that would have been no problem at all. Cloning a few bytes of source code for every line during assembly would cost us next to nothing. You would not notice in execution time. But things are different when you need to quickly handle long substrings in a program. Think of a diagnostic job on a busy server. And remember that Strings will be created on the heap. That is a complexity that you sometimes want to avoid. When programming microcontrollers, there is a chance that you do not even have a memory allocator at your disposal. And microcontrollers is, what we are aiming for in our project. There are already some parts of lovem, that we will need to change, because of that. But that is a story for another time. I just thought that this was a nice little example to introduce you to lifetime parameters. We will need them at some point...
Run it already!¶
This is a long entry already. You can look at the complete state of the assembler directly in the sourcecode. You should know how to find the tags inside the repo by now. But I want to execute our new program, using the labels, before I end this. Here it is again:
| pgm/label.lva | |
|---|---|
We need to execute it with the --trace flag, or we will not see anything:
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- -r pgm/label.lva --print --trace
Compiling lovem v0.0.10 (/home/kratenko/git/lovem)
Finished dev [unoptimized + debuginfo] target(s) in 1.33s
Running `target/debug/lovas -r pgm/label.lva --print --trace`
Pgm { name: "pgm/label.lva", text: [2, 1, 32, 0, 3, 2, 3, 255, 2, 2, 32, 255, 248] }
VM { stack: [], pc: 0, op_cnt: 0, trace: true, watermark: 0 }
Executing op 0x02
VM { stack: [1], pc: 2, op_cnt: 1, trace: true, watermark: 1 }
Executing op 0x20
Jump from 5 by 3
VM { stack: [1], pc: 8, op_cnt: 2, trace: true, watermark: 1 }
Executing op 0x02
VM { stack: [1, 2], pc: 10, op_cnt: 3, trace: true, watermark: 2 }
Executing op 0x20
Jump from 13 by -8
VM { stack: [1, 2], pc: 5, op_cnt: 4, trace: true, watermark: 2 }
Executing op 0x02
VM { stack: [1, 2, 3], pc: 7, op_cnt: 5, trace: true, watermark: 3 }
Terminated!
VM { stack: [1, 2, 3], pc: 8, op_cnt: 6, trace: true, watermark: 3 }
Terminated.
Runtime=65.598µs
op_cnt=6, pc=8, stack-depth=3, watermark=3
The program has three push_u8 operations. If you executed them in the order of the source code, they would push [1, 3, 2] to the stack. But because of the goto instructions, they are not executed in that order. You can see the jumps in the trace, and you can see that the stack at termination holds the values in this order: [1, 2, 3].
Not much of a program, but it shows you, how our new labels work. And finally: no more counting bytes!
Homework¶
Our programs endless.lva and endless-stack.lva no longer work, because we changed how the goto instruction must be written. Can you fix them?
What if?¶
Choose your path.
Our assembler gives us a lot of convenience for testing features of our VM. So let us start doing interesting stuff with it. We do have support for jumps already, but as it is now, save of an endless loop, there is absolutely no reason to do it, yet. All our programs run their predetermined way. If you look again at label.lva, you can see that none of those gotos introduce any dynamic. We could just ditch them and reorder the rest. It would do the same, only more efficient. They simple tangle up our linear code, without removing its linearity.
Today we will introduce branches to our VM. A branch is a point in a program from which there are multiple possible paths to take. Two paths, normally. Which of those paths is takes is decided at runtime by looking at the state of the program. For us that means that we look at the value on top of the stack. How does it work?
Conditional jump¶
We already introduced the goto operation. What we will add now, works exactly the same way, but only if a certain condition is met. And, yes, we will call that operation if. But if what? How about if equal?
So we get the new opname ifeq, that pops a value from the stack and only executes its jump when that value is equal. Equal to what, you want to know? How about if it is equal to zero. If you want to compare it to a different number, it is easy to subtract that number from your value before you compare it to zero, and you achieve what you need.
New operations¶
We will introduce multiple if-operations. Six, to be precise.
And we add another operation, while we add it: dup
| src/op.rs | |
|---|---|
This one simply duplicates the value on top of the stack, so that there will be another copy of it on top of it. We will use that often when testing values with an if, if we still need the value after testing it. The if will consume the top most value.
Extending the assembler¶
We add the parsing handlers for our new instructions:
And that is all we need to change on our assembler. The way we have written it, it is easy to introduce new operations, when they share the same syntax in assembly and in bytecode as existing ones.
Adjust the VM¶
First, we add the handler for the dup. Just pop a value and push it back, twice. Easy.
| src/vm.rs | |
|---|---|
And now, the if*-handlers. They are similar to the goto-handler, just with an if added.
And that is all the code we have to change. Our VM can now execute conditional jumps. Now we can do some serious programming!
A for-loop¶
Can't wait to use an if in program:
| pgm/loop.lva | |
|---|---|
And execute it:
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- -r pgm/loop.lva --print --trace
Finished dev [unoptimized + debuginfo] target(s) in 0.02s
Running `target/debug/lovas -r pgm/loop.lva --print --trace`
Pgm { name: "pgm/loop.lva", text: [2, 3, 2, 1, 17, 3, 37, 255, 249, 1, 255] }
VM { stack: [], pc: 0, op_cnt: 0, trace: true, watermark: 0 }
Executing op 0x02
VM { stack: [3], pc: 2, op_cnt: 1, trace: true, watermark: 1 }
Executing op 0x02
VM { stack: [3, 1], pc: 4, op_cnt: 2, trace: true, watermark: 2 }
Executing op 0x11
VM { stack: [2], pc: 5, op_cnt: 3, trace: true, watermark: 2 }
Executing op 0x03
VM { stack: [2, 2], pc: 6, op_cnt: 4, trace: true, watermark: 2 }
Executing op 0x25
Jump from 9 by -7
VM { stack: [2], pc: 2, op_cnt: 5, trace: true, watermark: 2 }
Executing op 0x02
VM { stack: [2, 1], pc: 4, op_cnt: 6, trace: true, watermark: 2 }
Executing op 0x11
VM { stack: [1], pc: 5, op_cnt: 7, trace: true, watermark: 2 }
Executing op 0x03
VM { stack: [1, 1], pc: 6, op_cnt: 8, trace: true, watermark: 2 }
Executing op 0x25
Jump from 9 by -7
VM { stack: [1], pc: 2, op_cnt: 9, trace: true, watermark: 2 }
Executing op 0x02
VM { stack: [1, 1], pc: 4, op_cnt: 10, trace: true, watermark: 2 }
Executing op 0x11
VM { stack: [0], pc: 5, op_cnt: 11, trace: true, watermark: 2 }
Executing op 0x03
VM { stack: [0, 0], pc: 6, op_cnt: 12, trace: true, watermark: 2 }
Executing op 0x25
VM { stack: [0], pc: 9, op_cnt: 13, trace: true, watermark: 2 }
Executing op 0x01
VM { stack: [], pc: 10, op_cnt: 14, trace: true, watermark: 2 }
Terminated!
VM { stack: [], pc: 11, op_cnt: 15, trace: true, watermark: 2 }
Terminated.
Runtime=100.972µs
op_cnt=15, pc=11, stack-depth=0, watermark=2
Nice! This is basically a for-loop. Granted, it does not do anything but loop, but you can see how the program counts down from 3 to 0 and after the third time it reaches line 8, it stops jumping back to loop: and advances to the end.
We can increase the number in line 3, and the number of runs increase with it. If we change it to 200, we get this (I ditched the --trace for this).
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- -r pgm/loop.lva --print
Finished dev [unoptimized + debuginfo] target(s) in 0.02s
Running `target/debug/lovas -r pgm/loop.lva --print`
Pgm { name: "pgm/loop.lva", text: [2, 200, 2, 1, 17, 3, 37, 255, 249, 1, 255] }
Terminated.
Runtime=128.709µs
op_cnt=803, pc=11, stack-depth=0, watermark=2
More than 800 operations with only 10 lines of code. Shall we cranc it up to a million?
kratenko@jotun:~/git/lovem$ cargo run --bin lovas -- -r pgm/loop.lva --print
Finished dev [unoptimized + debuginfo] target(s) in 0.02s
Running `target/debug/lovas -r pgm/loop.lva --print`
Pgm { name: "pgm/loop.lva", text: [2, 100, 2, 100, 18, 2, 100, 18, 2, 1, 17, 3, 37, 255, 249, 1, 255] }
Terminated.
Runtime=564.184652ms
op_cnt=4000007, pc=17, stack-depth=0, watermark=2
Takes about have a second to execute, over 4000000 operations where executed. And the stack never held more than 2 values, as you can see by the watermark. We are programming!
Homework¶
Wait a second! Our only way of getting values on the stack is push_u8. That can only push a u8, so only values 0 - 255. How did I push that 1000000 there?