Bootstrapping a Fully Automated Homelab Technical Deep Dive: Writing a Proxmox Answer File Scanner
This is the third article in a series describing my current homelab setup including technical deep dives on related concepts. The previous article is here. The next article is here.
Introduction
As part of my quest towards a fully automated homelab setup, I wanted some tool for automatically configuring Proxmox answer files in order to fully automate a Proxmox install. In my mind, it would work in a way similar to ssh-keygen in that the user would be able to generate a new answer file by responding to prompts. However, I wanted it to have some extra features including the ability to edit answer files using terminal prompts, the ability to validate answer files using Proxmox’s default tool proxmox-auto-install-assistant, and the ability to genereate ISO images necessary for the automatic install.
In general, I am not a fan of using dependencies, so I figured I would write as much as I found reasonable from scratch. Well, in order to parse and allow for editing of answer files, some way to scan and parse the answer files must exist. It has been a few years since I wrote scanners and parsers as part of a larger compiler, so I chose to revisit that knowledge by writing a scanner for a subset of TOML that relates to my needs.
This article goes through some high level theory of lexing and then applies that theory to describe the design of an answer file scanner written in Rust. At the end, I provide a link to the scanner I wrote, which I actually used as part of the tool I created for my own cluster. The next couple of articles in the series will go over parsing and the final tool.
Scanning: A High Level Overview
The job of a scanner is to read a stream of characters, aggregate them into words, and decide using a series of rules whether the words are valid in a language. Assuming the word is valid, the scanner assigns a category to that word(from now on referred to as a token). The stream of tokens along with their type is the output. This definition comes from the book Engineering a Compiler, which, along with Crafting Interpreters, serves as an excellent point of reference for lexing theory and application.
Combining this theoretical understanding with some of the practical advice from Crafting Interpreters, I argue that desgining and implementing a scanner generally boils down to the following steps:
- Decide which language to scan.
- Pick a subset of the language and what tokens to consider.
- Create finite automata(introduced later) for each token type.
- Turn the FA’s into code, generally done by looping one character at a time and considering token types using peeks.
- If desired, use regular expressions to express FA’s. Not necessary, but interesting.
For the purposes of my tool, I chose a subset of the Proxmox answer file format, which itself is a subset of TOML. With that in mind, I picked which tokens I found relevant to my task and went on to steps 3-5.
A Primer on Recognizing Tokens
One key question to consider is how to formalize the idea of recognizing tokens. When humans look at a sentence, they intuitively understand what a word is: a series of alphabetic characters surrounded by punctuation or space. In order for computers to also understand that, the notion of “recognizing a word” must be formalized in some way. The way to do this is by using finite state machines, mathematically known as finite automata, and graphically displayed as transition diagrams.
In other words, tokens are recognized by using code which implements an abstraction that starts in one state, considers characters that are encountered as state transitions towards an end state, and terminates when the end state is reached. In diagrams of finite automata, the end state or acceptance state is shown using double circles. Arrows represent state transitions, with relevant characters drawn nearby.
NOTE: “Engineering a Compiler” provides in depth mathematical explanation of finite automata as mathematical objects, namely five-tuples. It is very interesting, it would just make the article too long to get into, but everyone should read it.
Applying Finite Automata Diagrams Proxmox Answer Files
It turns out that for Proxmox answer files, the relevant high level tokens are TOML Keys, Strings, Table Headers, and Arrays of Strings(Note that an array of strings is really the combination of a few automata representing the character [, several strings separated by commas, and the character ].).
Based on the TOML grammar, the finite automata for relevant pieces would look something like:
With these FAs in hand, the next step is to turn them into code. The book “Engineering a Compiler” has a very in depth breakdown of several automated algorithms for how to do this. However, I find it more interesting to do it by hand, so I ended up doing just that in Ruist. The full handwritten code for how to do so can be found at my github. At a high level, the scanner is simply a loop with a few more nested loops inside, one for each FA. Since I used Rust and peeking is required, I ended up using a an object that tracks a file and a peeakble iterator that can be passed around as a parameter, giving something like:
pub fn scan(&mut self) -> io::Result<()> {
// first we read the file and print the lines
let f = File::open(&self.file_path)?;
let reader = io::BufReader::new(f);
let mut iter = reader.bytes().peekable();
let mut new_line = true;
while let Some(current_byte_or_err) = iter.next() {
let current_char = current_byte_or_err? as char;
match current_char {
'#' => {
// skip comment
}
_ if new_line && current_char == '[' => {
// handle table header
}
'"' => {
// handle string
}
_ if new_line && current_char.is_alphabetic() => {
// handle key
}
'\n' => {
// new_line = true
}
'[' => {
// push array start
}
']' => {
// push array end
}
',' => {
// push comma
}
'=' => {
// push equals, as part of key value pair for parsing
}
_ => {}
}
}
Ok(())
}
A Digresion on Regular Expressions and Their Relevance
Regular expressions are found all over programming yet it seems to me like most software engineers do not actually know where they came from or what they represent. I aim to fix that by first outlining what regular expressions actually are, and then pointing to a proof in “Engineering a Compiler” that concludes that regular expressions and FAs are equivalent.
According to “Engineering a Compiler”, an RE describes a set of strings over the characters contained in some alphabet ${latex.inline\Sigma} augmented with a character ${latex.inline\epsilon} that represents the empty string. An RE is built from three basic operations:
-
Alternation(union) of two sets of strings R and S, denoted R | S: ${latex.inline\ x \in R\ or\ x \in S}}.
-
Concatenation of two sets of strings R and S, denoted RS: ${latex.inline\ x \in R\ and\ y \in S}}
-
Closure of a set R is the union of concatenations of R with itself 0 or more times.
With these oprations in mind as well as some examples of the syntactic sugar that languages like Python or Perl may apply, it’s much easier to understand why regex expressions look the way they do. Take the following for example:
- abc matches the string “abc”, which is just a concatenation of “a”, “b”, and “c”
- [abc] matches any character that is a, b, or c. This can be rewritten as (a|b|c), which is just a series of alternations.
- go+gle represents gogle, google, gooogle, etc beause o+ is just a representation of a closure using the letter o.
Conclusion
Hopefully by now the purpose of scanners and the process for building one are a bit more clear. Furthermore, I hope that it’s more obvious that the process is repeatable and that anyone can build their own scanner by following the same series of steps, albeit the specifics of each step change. For the full source code of the scanner I wrote in Rust for the purpose of scanning Proxmox answer files, feel free to check out my github. In that same repo you will find the parser as well, which is the topic of the next article. The parser is part of the same library I called ana.