Jak si napsat skriptovací jazyk v Rustu
Cílem tohoto (delšího) cvíčení je naučit se jak fungují skriptovací jazyky, jejich spouštěče a programovací jazyk Rust. Je předpokládána základní až střední znalost programovaní.
Co je to skriptovací jazyk
Na začátek si popišme co vlastně chceme. Náš jazyk bude interpretovaný, což znamená, že se nezkompiluje do jednotlivých instrukcí pro počítač a místo toho dané instrukce bude provádět náš program.
Přirovnal bych to k opisování údajů mezi počítači - máte větší kompatibilitu, nemusíte počítače propojovat, a když klávesnice bude o trochu posunutá, vadit vám to nebude. Ale bude to pomalejší a pro vás víc nepříjemné. Podobně to tak je i tady, počítač nemůže spustit kód přímo a tak musí spustit váš program aby spustil cílový program, ale je jednodušší napsat ten program i interpreter, to co jej spustí.
Náš jazyk
Jako skriptovací jazyk se většině asi vybaví Javascript, a tak si vymodelujeme něco podobného. Pro jednoduchost chceme striktnější variantu a jen pár základních věcí, zahodíme většinu věcí aby se z dálky podobaly jazyky jen syntaxí.
Chceme mít proměnné, do kterých budeme moci uložit čísla a text.
Dále pro to, aby to byl programovací jazyk potřebujeme smyčky a podmínky. Pro naše potřeby to bude while a if.
Více pro základní jazyk již nepotřebujeme, ale stejně si tam přihodíme i funkce, které budeme moci spustit.
Ukázka syntaxe:
let variable = "value";
let second = variable + "2";
let number = 2;
while(number > 0) {
number = number - 1;
}
function myprint(value) {
print(value);
}
if (number == 0) {
myprint(second);
}Můžete si vyzkoušet mezi výstupy i finální výstup programu na playground (též výše).
Teorie
Rozvrhněme si co náš program bude dělat.
Potřebujeme si nejdříve rozdělit text na jednodušší sousta ke zpracování.
Například souvislý text let var = 1; na let, var, =, 1, ;.
Tomuto kroku se říká lexer.
Poté tyto sousta převedeme do formátu se kterým se nám bude dobře pracovat. Na to se používají takzvané stromy. Tady už se nahlíží na proud programu, například
let variable = 1;
if(variable == 0) { print(1); }By se přepsalo na
[
deklaruj proměnnou("variable", 1),
if(
rovná se("variable", 0),
block[
zavolej funkci("print", 1)
]
)
]Tohle se dělá z toho důvodu. že je poté jednoduché to spustit - stačí krok po kroku vykonávat příkazy, a pokud se nalezne změna proudu, jako třeba if, tak se zkontroluje podmínka a pokud platí, spustí se kód uvnitř.
Pro podmínky by mohlo fungovat i to mít lineárně v jednom listu, kdy by se počítalo počet závorek a podobně, jenže to by nefungovalo u smyček kdy je potřeba se vracet. Museli bychom si kvůli tomu ukládat všechny pozice, a ve finále by kód byl složitější než by musel být.
Této části se říká parser a je to ta nejsložitější část u jednodušších interpreterů.
Následně už se akorát kód spustí v executorovi.
Příprava prostředí
Potřebujeme si nainstalovat rust. Pro to doporučuji nástroj rustup - stáhněte si a nainstalujte rustup a následně v terminálu spusťte rustup install stable,
tím si nainstalujete nejnovější stabilní verzi rustu a nástrojů okolo.
Ve složce kde budete chtít mít projekt spusťte cargo init, to vytvoří pár souborů a složek.
Nás zajímají dva soubory - Cargo.toml, kde jsou informace o programu a knihoven co se používají, a src/main.rs kde bude náš program.
Jako editor doporučuji VSCode s Rust rozšířením či RustRover od JetBrains.
Základy jazyka rust
Většinově se budeme učit Rust "za běhu", ukazovat nové vlastnosti jak se objeví. Ale stejně zde představím některé základy:
Rust je kompilovaný jazyk, čehož výhoda je možnost sáhnout si na nízké vrstvy systému - dá se v něm například psát operační systém. Dále je typovaný tak, aby za normálního používaní nenechal možnost uložit nevalidní stav. Pro nás to znamená, že když bude proměnná definována s typem string, tak se do ní nebude moci uložit číslo, nebo aby jsme ji použili a byla prázdná. Ne vždy to ale znamená že musíme psát typy, rust si sám typy vypočítá pokud má možnost.
Typy jsou uvnitř virtuálních složek či kategorií kterým se říká Namespace. Namespace může být soubor, ale taky to může být i část uvnitř souboru - funkce či mod. K mod se dostaneme později.
Referuje se na ně přes ::, například Let uvnitř Token je Token::Let.
Dalším namespace je crate, což je momentální projekt. Jestliže je Token uvnitř mod.rs v src složce, jeho plné jméno bude crate::Token::Let. Není ale potřeba jej používat, stačí Token::Let.
Objeví se později.
Nevadí-li Vám angličtina a chtěli by jste si v rychlosti pročíst o většině hlavních vlastností jazyka Rust, přečtěte si Rust basics, from the perspective of a high level programmer. Dostanete tak náskok, a v některých případech jde lehce více do detailů než tento článek. Navíc obsahuje odkazy na další zdroje.
Takové upozornění, Rust není OOP (objektově orientovaný) jazyk, a proto nemá žádné třídy, interface a podobně. Místo toho má základní objekty (structy) a funkce napřímo, obdobně jako jazyk C, a některé pokročilejší typy jako trait, enum a další, k nimž se dostaneme později.
Lexer
Základní lexer rozdělí text na tokeny. Pojďme si rozdělit tokeny co budeme chtít:
Každé klíčové slovo bude samostatný token - tak máme let, if, while, function.
Pak jen přihodit speciální znaky - hlavně závorky (){}[] a středník ;, a máme téměř hotovo -
na závěr se akorát přihodí jméno (identifier), který bude sloužit pro názvy proměnných a funkcí, text (uzavřen uvovozvkami), který bude obsahovat text uvnitř uvozovek a číslo.
Teď to akorát zapsat.
V Rustu máme k dispozici Enumy, datovou strukturu která ukazuje možné varianty. V jiných jazycích by to bylo jednoduché mapování čitelných slov na čísla,
tady mají trochu možností navíc, ale v jejich základní formě to je totéž.
Tudíž, základní enum nám ukazuje jednu vybrannou možnost ze seznamu. Aneb to co chceme pro token, kde přesně víme možné varianty.
Zapíšeme si tedy základní tokeny:
enum Token {
Let,
If,
While,
Function,
Equal, // =
Comma, // ,
Colon, // :
SemiColon, // ;
ParensOpen, // (
ParensClose, // )
CurlyOpen, // {
CurlyClose, // }
...
}Text a číslo jde též reprezentovat uvnitř enumu - enum možnosti totiž mohou obsahovat i další hodnoty v sobě:
enum Token {
...,
Identifier(String),
String(String),
Number(i64),
...
}Tady může působit matečně String(String), a toť tím že je definovaný String jako možnost uvnitř Tokenu, který má hodnotu String -
ovšem ne jako možnost Tokenu ale jako jiný typ, tentokrát text.
i64 je číselný typ. Jsou referovány typem čísla - integer, unsigned či float, a jeho počtem bitů. Integer znamená celé číslo, včetně záporných. Unsigned integer
je to stejné ale jen pozitivní (a zároveň numericky vyšší maximální hodnota, tím že se reprezentovaná škála "posune" - u 8bit to znamená že místo -128 až +127 to je 0 až 255, rozpětí je stále 256 hodnot).
Floating point čísla jsou čísla s desetinnou čárkou, floating znamená že se desetinná čárka může posouvat. Umí reprezentovat velká i malá čísla s různou přesnosti, a zároveň i
necelá čísla. V javascriptu se pro číslo používá právě f64. My použijeme i64 (celá 64bitová čísla) pro jednoduchost.
Enum nám takto garantuje, že nebude uložený String u věcí kde by neměl být úložený, třeba Let nebo Number.
To může být v kontrastu s jinými jazyky, kde by se použil například objekt s klíčem type a hodnotou, a pak případnými dalšími hodnotami navíc.
Rozdíl mezi Identifier a String je v jeho původním zápisu - identifier se používá pro názvy, zatímco text je vždy ohraničen uvozovkami.
hello by tudíž byl Identifier a "hello world" by byl String.
Matematické a porovnávací operace přidáme jako separátní enum Op, aby jsme je mohli jednoduše referencovat později.
enum Op {
Plus, // +
Minus, // -
Multiply, // *
Division, // /
EqualTo, // ==
NotEqual, // !=
LessThan, // <
GreaterThan, // >
Dot, // .
}Do Token je přidáme obdobně jako Identifier či String - jako Op(Op).
Zde je akorát potřeba nezaměnit Token::Equal a Token::Op(Op::EqualTo) - Equal je = a používá se uvnitř let zatímco EqualTo je ==, operace která porovná dvě hodnoty.
Tečka jako operátor může vypadat zmatečně, nicméně funguje obdobně jako jiné operátory - bere dvě hodnoty, operuje s nimi (v našem případě vezme hodnotu klíče v objektu, např. object.key vrátí hodnotu key uvnitř object{:.meta.property-name}). Čísla v našem jazyce budou pouze celá, tudíž nemusí mít tečku.
Implementace
Otevřeme si projekt v našem vybraném editoru a začneme upravovat src/main.rs.
Na začátek by měl obsahovat základní "Hello, world!" program:
fn main() {
println!("Hello, world!");
}Můžeme ověřit funkčnost přes cargo run.
Program můžeme rovnou rozšířit o možnost čtení souborů.
V složce projektu vytvoříme složku test a v ní soubor hello.js s obsahem print("Hello, world!");.
Následně upravíme src/main.rs na
fn main() {
let file = std::fs::read_to_string("test/hello.js").unwrap();
println!("{}", file);
}Nezapomeňte do src/main.rs přidat enum Token a enum Op z předchozí sekce.
Importy
std::fs:: je označení modulu kde najdeme daný objekt, v našem případě funkci read_to_string. std jako modul je přístupný většině programům (není dostupný jen v ojedinelých případech jako psaní OS či kompilaci do prohlížeče).
Je to obdoba require("node:fs") z Node.js.
Jelikož nechceme psát std::fs:: u všech funkcí, je zde možnost si je přidat pomocí use
use std::fs::read_to_string;
fn main() {
let file = read_to_string("test/hello.js").unwrap();
println!("{}", file);
}Takto si můžeme přidat jakoukoliv úroveň - můžeme si přidat i jen std::fs a pak by se na funkci referovalo přes fs::read_to_string().
Result a chyby
.unwrap() je zde kvůli tomu, že čtení souboru může selhat - soubor nemusí existovat, zařízení nemusí odpovídat, nemusíme mít oprávnění číst soubor a podobně.
Chyby jsou v rustu explicitní - není zde žádný try/catch či throw, místo toho se chybovost značí jako separátní typ, enum Result.
Je ve všech rust programech (i bez std - proto nemusíme psát std::Result), a jeho základní zápis je
enum Result<T, E> {
Ok(T),
Err(E)
}Má tudíž dvě hodnoty - Ok, operace proběhla v pořádku, a Err, operace selhala. Zároveň mohou mít hodnotu, zde T či E. Tyto typy jsou generické - uživatel typu si je může specifikovat, proto jsou psané v <T, E>.
Například read_to_string vrací Result<String, std::io::error::Error>.
unwrap je metoda na Result která buďto vrátí T (String v našem případě) nebo "se nevrátí" a crashne program. Tomuto se říká v rustu panic, a značí to chybu ze které se nedá vrátit do normální funkce programu - chyba se vypíše a program se ukončí.
Je to obdoba použití
let file = match read_to_string("test/hello.js") {
Ok(value) => value,
Err(err) => panic!("{err}")
};Match je takový switch, který vyžaduje vypsat všechny možnosti (rust vám to připomene) a může vracet hodnotu (jako v tomto případě kdy vrací value).
Není zde žádný fall through, nemusí se tudíž psát break. Je taky default možnost, značí se přes _ - v rustu obecně znamená "všechno" nebo "nespecifikováno".
Panic nikdy nevrací (jeho return type je !, obdoba never z typescriptu), a tudíž se nepočítá jako možná hodnota. Match jinak vyžaduje mít všude stejný return type, ale ! lze počítat jako jakoukoliv hodnotu. Nezaměňte s void - to znamená že funkce se normálně vrací, ale nevrací žádnou hodnotu. V rustu se zapisuje jako prázdná tuple (). Ta se nemusí zapisovat, například naše main funkce vrací () když v ní není zapsaný typ hodnoty co se vrací (return type).
Alternativa pro .unwrap() je .expect("something"), který bere &str pro lepší chybovou hlášku - selže-li podmínka, místo základního "panic: unwrapping error" se zobrazí daný text.
let file = read_to_string("test/hello.js").expect("couldn't read script");Cursor
Pro náš lexer chceme mít strukturu která bude ukládat aktuální stav. Pojmenujeme si ji Cursor.
Bude nám stačit ukládat str a Chars:
str samo o sobě je unsized (značeno !Sized, dá se s tím setkat v chybách či v pokročilejších funkcích), nevíme u něj velikost. To je problém, protože struktury musí mít pevnou velikost, aby s nimi compiler uměl pracovat.
Je na to ovšem jednoduché řešení - do struktury se nebude ukládat objekty samotný, ale pouze pointer na něj. Ty se v rustu značí &.
U pointerů ovšem nastává další problém - jak garantujeme že paměť na kterou pointer ukazuje zůstane validní? V jazycích jako C/C++ se to řeší tak že se to negarantuje a je na Vás neudělat chybu. A na autorech všech knihoven co používáte. A na autorech kernelu. Naopak v jazycích jako Java, JS či Python se to neřeší a používá se garbage collector, který pointery hlídá, ale naopak má velký overhead při použití paměti.
Rust proto chce dokázat že paměť bude validní, a to přes jejich životnost (lifetime). Ta se značí pomocí ', například 'static, znamenající "do konce programu".
I tyto lifetime lze používat genericky, obdobně jako typy (například v Result). Právě Chars bere životnost jako argument, aby text, na který Chars ukazuje, zůstal validní.
Pokud by jej nebral, musel by nabrat vlastnictví textu, což by buďto znamenalo že by jste již text nemohli použít jinde (pro normální čtení), nebo jej museli kopírovat, což by zbytečně zbrzdilo program.
Jelikož chceme aby str i Chars ukazovali na stejný text, aniž by se kopíroval, tak celá naše struktura bude brát životnost jako argument a pouze jej předá dál:
struct LexerCursor<'a> {
chars: Chars<'a>,
str: &'a str
}Novou instanci tohoto objektu si vytvoříme jednoduše přes
LexerCursor {
chars: file.chars(),,
str: file
}Nemusíme manuálně vpisovat lifetime - není-li přímo specifikovaný (implicitně je '_), Rust si sám životnost dopočítá a zkontroluje.
Nyní akorát přidáme pár základních funkcí pro ulehčení práce s Cursorem.
impl<'a> LexerCursor<'a> {
fn new(input: &'a str) -> Self {
Self {
chars: input.chars(),
str: input
}
}
/// Advances the cursor
fn bump(&mut self) -> Option<char>{
self.chars.next()
}
/// Looks at the next item without advancing the cursor
fn peek(&self) -> char {
self.chars.clone().next().unwrap_or(' ')
}
/// Returns current position in string
fn pos(&self) -> usize {
self.str.len() - self.chars.as_str().len()
}
/// Returns true if the cursor has reached the end of the string
fn ended(&self) -> bool {
self.peek() == ' '
}
/// Advances the cursor as long as the predicate returns true.
/// Checks the predicate first before advancing.
fn eat_while(&mut self, predicate: impl Fn(char) -> bool) {
while predicate(self.peek()) && !self.ended() {
self.bump();
}
}
}impl značí implementaci metod pro objekt či traitu (o traitách za chvilku). Zároveň i impl může brát generika, je to kvůli tomu aby jednak bylo explicitně daný na co se nastavují generika objektu (v našem případě LexerCursor), a zároveň aby bylo možné dát určité podmínky - některé metody jsou na objektech dostupné pouze pro určité typy, například Arc<T> má k dispozici Debug pouze když T má Debug.
Zároveň však impl může značit "jakýkoliv typ co implementuje trait", což se používá právě v eat_while. Ta bere argument predikátu, což je jakákoliv funkce která bere argument char a vrací bool. Return typ je dán přes ->, stejně jako u normálních funkcí.
V této implementaci se také setkáváme se dvouma typama funkcí uvnitř impl - ty, které neberou self jako argument (new) a ty co jej berou.
Oba typy jsou dostupné přes LexerCursor::, ale ty, co berou self (self, &self, &mut self) jsou zároveň dostupné přímo na objektu (daného typu).
To je taky vidět uvnitř funkcí - eat_while používá bump metodu přes self.bump(). Zároveň ale používá i peek, i když ta je definována na &self - jde-li typ upravit na výsledný typ, rust to udělá, což pro nás znamená že může změnit self -> &mut self -> &self v tomto pořadí (máme-li self, můžeme volat jakoukoliv metodu, s &mut self pouze metody co berou &mut self či &self).
Běžně se funkce bez self používají pouze na vytvoření objektů. Ty funkce se poté většinou jmenují new, nicméně není to žádný speciální název, akorát konvence - u objektů s dalším nastavením zas často bývá build.
&self a obdoba je akorát zkrácená verze nad self: &Self, kde Self zas referuje na aktuální typ - LexerCursor. A rozdíl mezi &self a &mut self je, stejně jako u ostatních pointerů, že & je read-only a může jich být vícero zároveň, zatímco &mut povoluje úpravu ale je exkluzivní - může být pouze jeden mut pointer a během jeho existence nesmí být žádný jiný - ať už read nebo mut. V ruzných místech / času ovšem můžou existovat.
Zároveň je zde ukázka dokumentace - v rustu se používá /// pro dokumentaci u funkcí, structu, enumu, traitu, re-exportovaných objektů etc. Pro dokumentaci celého modulu (souboru) se používá //! na začátku.
Dokumentace se poté v lepších IDE zobrazí po najetí myši, zároveň se dá generovat přes cargo doc lokální HTML soubor s dokumentací (to mimo jiné vygeneruje i dokumentaci použitých knihoven, a lze tak alespoň částečně vyvíjet lokálně bez internetu). Dokumentace umí markdown a odkazy na jiné rust objekty.
Iterator
Teď se konečně dostáváme k trait. Trait je sada definicí metod, která se může implementovat pro objekt (struct, enum, funkci, objekty které implementují jiný trait...). Je to forma sdílení kódu a mechanik jako alternativa pro klasické OOP. Lze tak popisovat které akce lze dělat na kterých objektech, a naopak akceptovat objekty podle toho co umí a ne co jsou.
Díky tomu můžete brát věci podle toho jak se chovají, místo toho co přesně jsou.
Například tak funguje debug výpis - daný objekt musí implementovat trait Debug aby se dal debug printovat, ať už přes dbg!(objekt) či println!("{:?}", objekt). Bohužel to jsou oboje macra, a tak není jednoduše vidět jejich typ, ale Rust vám to připomene, řekne že objekt neimplementuje (neumí) trait Debug a jak ho implementovat.
Traity se implementují pomocí impl Trait for Object. Zde ovšem pro běžné traity lze použít macra (automaticky generovaný kód).
Například, chcete-li (debug) vypsat array tokenu (resp. dynamický array Vec), stačí vám před enum Token přidat #[derive(Debug)]. To taky využívá (tzv. blanket) implementaci Debug pro arraye jejichž itemy umí Debug - impl<T: Debug> Debug for Vec<T> { ... }.
My si zaimplementujeme trait Iterator pro náš LexerCursor, jelikož nám to zjednodušší práci.
Hezky od začátku to je jednoduché:
impl Iterator for LexerCursor<'_> {
type Item = Token;'_ nám značí že na lifetime nezáleží - jelikož nebudeme vracet reference na žádnou LexerCursor paměť, nemusíme reference řešit ani uvnitř implementace. Jakmile bychom potřebovali vracet referenci, už bychom museli lifetime řešit a definovat, avšak pro jednoduchost není třeba.
type Item nám definuje typ uvnitř trait - mohou obsahovat type které specifikuje implementace. Je to z toho důvodu, že například právě Iterator definuje různé metody na použití iterátoru, ale chce mít volnost vracet různé typy. V našem případě chceme vracet Iterator Tokenu.
Definice traitů též může mít default implementace daných metod, a ty poté nejsou povinné implementovat. Například právě Iterator má spoustu metod navíc kterým stačí pouze next. nth vezme n itemu (pomocí next) a vrátí poslední z nich, count spočítá celkový počet itemů díky volání next ve smyčce a podobně.
Nám právě u Iteratoru stačí zaimplementovat next:
fn next(&mut self) -> Option<Self::Item> {
self.eat_while(|c| c.is_ascii_whitespace());
let pos = self.pos();
let c = self.bump()?;První řádek musí přesně odpovídat definici v trait - nelze mít return type jiný než Item (jde ovšem rozepsat na Token, dokud je výsledný typ shodný) nebo brát argumenty navíc.
API pro ostatní musí být vždy shodná - to je právě jedna z garancí celého trait systému.
Dále je řádek na přeskočení netisknutelných znaků. Používá již dříve definovanou metodu eat_while na LexerCursoru. Zde je stále možné použít self, jelikož referuje na LexerCursor, rust najde danou metodu. Jako argument dáváme lambda, obdobu inline funkce (c) => c.is_ascii_whitespace() v js. c je char, jelikož v definici eat_while je funkce která bere char argument a vrací bool. Je to opět kontrolovaný typ - nemůžete vrátit 0, nemůžete pracovat s c jako s struct, nebo nebrát žádný argument - rust tento typ sice inferuje (není explicitně zapsát v kódu), ale stále ho kontroluje že platí.
Následně si uložíme aktuální pozici ve stringu a přečteme další znak, čímž zároveň posuneme cursor dále. Otazník zde změní Option<char> na char pokud je Some(char), jinak funkce vrátí None, vyžaduje proto aby return type funkce byl též Option. Dal by se rozepsat na match self.bump() { Some(char) => char, None => return None }.
Teď se konečně dostáváme k tý lex části lexeru - rozdělení textu na tokeny. Zde nám akorát stačí zapsat logika převodu znaků na tokeny.
Sepišme si nejdříve podmínky:
speciální znaky (různé závorky, čárka, středník, dvojtečka, operace jako porovnání, matematické operace a tečka) se uloží jako jejich relevantní token
začíná-li text číslem (
0-9), jedná se o číslo a dokud se nachází číslo, spojí se token do jednoho (například123je jeden token)začíná-li text uvozovkou, jedná se o string a čte se text dokud se nenajde další uvozovka
začíná-li text
a-zA-Z_(ascii písmena, malá i velká, a podtržítko), čte se text dokud se jedná o alfanumerický znak či podtržítkoje-li text jedním z
let,if,whilečifunction, jedná se o daný keyword (samostatný token)jinak se jedná o identifier
nesplňuje-li text ani jednu z podmínek, nejspíše se jedná o UTF-8 znak či speciální ASCII znak pro které nemáme definované chování - vrátit uživateli chybu a ukončit běh programu
Tyto podmínky můžeme postupně zapsat do match.
Nejdříve sepíšeme ty nejjednodušší možnosti - speciální znaky (po jednom):
match c {
'(' => Some(Token::ParensOpen),
')' => Some(Token::ParensClose),
'{' => Some(Token::CurlyOpen),
'}' => Some(Token::CurlyClose),
',' => Some(Token::Comma),
':' => Some(Token::Colon),
';' => Some(Token::SemiColon),
'+' => Some(Token::Op(Op::Plus)),
'-' => Some(Token::Op(Op::Minus)),
'*' => Some(Token::Op(Op::Multiply)),
'/' => Some(Token::Op(Op::Division)),
'.' => Some(Token::Op(Op::Dot)),
'<' => Some(Token::Op(Op::LessThan)),
'>' => Some(Token::Op(Op::GreaterThan)),Dále potřebujeme zapsat speciální znaky které jsou přes dva znaky. Zde máme dva případy, == a !=.
'=' => {
if self.peek() == '=' {
self.bump();
Some(Token::Op(Op::EqualTo))
} else {
Some(Token::Equal)
}
},
'!' => {
if self.peek() == '=' {
self.bump();
Some(Token::Op(Op::NotEqual))
} else {
panic!("unexpected character: {}", c)
}
},První případ je jednoduchý - najdeme-li =, koukneme se na další, je-li též =, našli jsme ==, Token::Op(Op::EqualTo), a nezapomeneme posunout cursor. Pokud ne, máme jednoduchý = Token::Equal.
U druhého případu probíhá kontrola že po ! se vždy nachází =. Náš jazyk zatím nepodporuje použití ! pro negaci hodnoty, nemá pro to token a tudíž je to nevalidní znak mimo použití uvnitř !=.
Čísla též není těžké přidat:
'0'..='9' => {
self.eat_while(|c| c.is_numeric());
let number = &self.str[pos..self.pos()];
Some(Token::Number(number.parse().unwrap()))
},Zde se používá range pro porovnání znaku. ascii '0' až '9', včetně - range bez = je vpravo exklusivní, neobsahuje poslední hodnotu.
Čteme znaky dokud jsou číselné. Poté ze stringu vezmeme úsek (&array[a..b] vrátí slice, referenci na část arraye či str od a do b) a spustíme na něj parse. To je metoda na &str která zavolá from_str na cílovém typu. V našem případě i64, jelikož Token::Number() bere právě i64 jako hodnotu, a rust si to dopočítá. Parse vrací Result v případě že by text nešlo rozparsovat, například neobsahoval validní číslo. Mylně by jste si mohli myslet že se to zde nemůže stát - přece kontrolujeme všechny znaky že jsou číselné, nicméně se zde nachází dva problémy. Ten první, hlavní, je to že to rustu nemůžeme dokázat. Ovšem ten druhý, problém logiky, je že se text sice může skládat jen z čísel, ale může přesáhnout limity.
Uvozovky fungují obdobně
'"' => {
self.eat_while(|c| c != '"');
self.bump();
let string = &self.str[pos+1..self.pos()-1];
Some(Token::String(string.to_string()))
},Jediný rozdíl je že stejně posuneme kurzor - eat_while čte dokud nenarazí na uvozovku, nicméně náš token "spotřebuje" i tu uvozovku.
Dále slice je posunutý oproti minule - nechceme do textu přidat i uvozovky totiž.
Nakonec závoláme .to_string() - to převede &str na String pomocí trait ToString, což v této implementaci prostě zkopíruje obsah, jelikož se již jedná o string, akorát v lehce jiné formě (pointer který nevlastníme).
Nakonec akorát logiku pro identifier a keywordy:
'a'..='z' | 'A'..='Z' | '_' => {
self.eat_while(|c| c.is_alphanumeric() || c == '_');
let ident = &self.str[pos..self.pos()];
match ident {
"let" => Some(Token::Let),
"if" => Some(Token::If),
"while" => Some(Token::While),
"function" => Some(Token::Function),
_ => Some(Token::Identifier(ident.to_string()))
}
},Zde se jen dávají dohromoady již známé vlastnosti - vícero range oddělených | pro or (tenhle or je pouze v match), filtrace na alfanumerické znaky a podtržítko, získání obsahu, vnořený match pro vyhledání keywordu který vrací hodnotu s default hodnotou Identifier.
A jako úplně poslední se do match přidá
_ => panic!("unexpected character: {}", c)Jako fallback/default použije-li se neznámý znak.
Teď to jen od závorkovat (měli by stačit 3 }), a jsme připraveni iterátor použít.
Použití iterátoru
Do funkce main přidáme
let cursor = LexerCursor::new(&file);
let tokens: Vec<Token> = cursor.collect();
dbg!(tokens);První řádek bychom již měli znát - používá to new z impl<'a> LexerCursor<'a>. Druhý řádek je trochu odlišný - na našem cursoru totiž žádnou collect metodu nemáme, jak jistě vidíte.
Ona totiž tato metoda je na Iterator, a jelikož jej implementujeme (přes impl Iterator for LexerCursor), můžeme tuto funkci použít.
Collect vytvoří kolekci z daného iterátoru. Jelikož je však vícero kolekcí do kterých lze výsledek uložit, rust nemůže sám vyzjistit výsledný typ, a proto mu musíme pomoc.
Jedna z možnosti, zde využita, je otypovat výslednou proměnnou - rust poté ví typ (nebo alespoň jeho část) a může zjistit kterou variantu kolekce použít.
Ta poznatka s částí je k věci - v našem případě stačí i Vec<_> - řekneme rustu že chceme Vec ale ať jeho generikum T (item) dopočítá, a jelikož je pouze jedna varianta co má Vec jako výsledek tak to zvládne správně dopočítat.
Druhá možnost je tzv. turbofish syntax. Ten je též zmíněný v dokumentaci pro collect, najedete-li na něj myší. Zapisuje se ::<>, takže v našem případě .collect::<Vec<_>>(). Toto se používá neukládáme-li do proměnné, nebo taky jednoduše když už jsme napsali část kódu a nechceme se vracet při psaní.
Jako poslední poznatek k této části kódu je že vyžaduje Debug trait impl pro Token. Ten lze automaticky přidat přes #[derive(Debug)], nemáte-li ho již přidané před enum Token. Rust by vám to měl ukázat chybí-li vám. Také by vám měl říct že to vyžaduje Debug i pro Op, jelikož se používá uvnitř Token, takže tam též musíte přidat derive.
Organizace kódu
Jelikož plánujeme přidat další funkce do našeho programu, má smysl se nyní podívat trochu na organizaci kódu. Momentálně totiž máme všechen kód v jednom souboru.
Vytvořme si tedy druhý soubor, lexer.rs. Do něj přesuneme veškerý kód mimo funkci main a use std::fs::read_to_string;.
Pokud však zkusíme zkompilovat, dostaneme chybu že LexerCursor nebyl nalezen. A naše IDE ho nechce najít, i když je hned ve vedlejším souboru.
Je to kvůli viditelnosti modulů. Zde máme několik vlastností rustu, co je třeba vysvětlit:
mod slouží k popisu hierarchie. Do main.rs přidáme mod lexer;, pokud již není přidaný - některé editory, třeba RustRover, již přidávají mod automaticky nebo se zeptají při vytvoření souboru zda-li ho mají přidat.
Ten se nepoužívá ve vícero souborech - již je v hierarchii pod modulem main, naším hlavním modulem, a poté je všichni mají k dispozici též pod hlavním modulem.
Nyní je kanonické jméno modulu lexer crate::lexer - crate totiž referuje na modul main v aktuálním projektu.
Uvnitř main však nepotřebujeme referovat na crate, je totiž dostupný přímo. Můžeme tak referovat na LexerCursor jako lexer::LexerCursor.
Nyní tedy můžeme použít use i na přidání LexerCursor jako "alias" na lexer::LexerCursor.
Teď však narazíme na další problém. Náš editor stále nechce najít LexerCursor, a rust si na to též stále stěžuje! Ale tentokrát s jinou chybou - LexerCursor je private.
V rustu platí, že objekty u kterých se dá měnit visibilita, jsou private dokud se nedají explicitně public pomocí pub. Pokud tedy chceme použít LexerCursor, je třeba mít pub struct LexerCursor.
Dále se viditelnost vztahuje na enum definice, jednotlivé pole structu (chars a str u LexerCursor, nemusí být pub protože se nepoužívá mimo lexer.rs), funkce, metody uvnitř impl Object, trait Trait, ale už ne u impl Trait for Object - jakmile je Trait i Object viditelné (je nutné mít use Trait), bude viditelná i implementace.
Dále se pub dá použít i na mod, čímž se modul publikuje "dále", můžete tak používat modul i když by byl uvnitř složky, dokud je cesta k němu pub.
Pro náš lexer je nutné mít jako pub LexerCursor, new uvnitř impl LexerCursor a oba enumy (Token a Op).
Token stream
Momentálně nám Lexer vrací tento výstup pro if(variable){print("hello world");}:
[
If,
ParensOpen,
Identifier(
"variable",
),
ParensClose,
CurlyOpen,
Identifier(
"print",
),
ParensOpen,
String(
"hello world",
),
ParensClose,
SemiColon,
CurlyClose
]
Naším aktuálním cílem je dostat z toho strom instrukcí, tzv. Abstract Syntax Tree (AST). Mohl by vypadat například takto (tip: předchozí příklad je interaktivní a můžete si zobrazit i finální Parse/AST):
[
If(
IfStatement {
condition: Identifier(
"variable",
),
body: Block(
[
Value(
FunctionCall(
FunctionCall {
func: Identifier(
"print",
),
args: [
String(
"hello world",
),
],
},
),
),
],
),
},
),
]
Poté je jednoduché ho spustit - v If získáme hodnotu condition (což zase získá hodnotu variable) a pokud je pravdivá (v našem případě je-li číslo nenulové), spustí se body.
Body je opět vector (list) instrukcí, postupně spustíme a narazíme na FunctionCall, přes name najdeme funkci (získáme hodnotu proměnné print) a zavoláme ji s danými argumenty (zjistíme hodnotu String hello world, což je zase String).
Převod z rozparsovaných tokenů na AST provádí komponenta parser. U ní máme vícero způsobů jak ale text rozparsovat. Totiž, primárně jak rozparsovat závorky.
Je totiž nutné je správně rozpočítat, může nastat rekurze - uvnitř if() můžeme mít další závorky, například if((1+1) == 2), či uvnitř funkcí můžeme volat další funkce, např. print(format(var)).
Můžeme například jít a počítat kolik závorek jsme již viděli. U jednoho z mých prvních parserů jsem to tak dělal - když jsem našel ParensOpen, dal jsem si proměnnou i = 1 a kdykoliv jsem našel ParensOpen, přičetl jsem jedna a když jsem dostal ParensClose, odečetl jsem jedna. Jakmile jsem se dostal na nulu, došel jsem ke konci závorek, a vnitřek jsem si nechal rozparsovat znova, rekurzivně. V tomto je ovšem jednoduché chybovat či nedetekovat různé chyby správně - co se stane když bude ({)?
Následně jsem studoval zdrojové kódy Rust compileru (rustc), a našel jsem strukturu TokenStream, která s tímto problémem pomáhá. Je to totiž malá komponenta před parserem, která rozparsuje pouze závorky a vše ostatní ponechá tak jak je. Výstup by poté měl vypadat takto:
[
If,
Group {
mode: Parens,
tokens: [
Identifier(
"variable",
),
],
},
Group {
mode: Curly,
tokens: [
Identifier(
"print",
),
Group {
mode: Parens,
tokens: [
String(
"hello world",
),
],
},
SemiColon,
],
},
]
Díky tomuto krátkému předparsování (které je do 90 řádků jednoduchého kódu) můžeme výrazně zjednodušit finální parser - místo počítání a problematického předávání informací můžeme jednoduše vidět If a přečíst/zkontrolovat následující dva tokeny z tokenstreamu, a vytvořit výsledné AST:
[
If(
IfStatement {
condition: Identifier(
"variable",
),
body: Block(
[
Value(
FunctionCall(
FunctionCall {
func: Identifier(
"print",
),
args: [
String(
"hello world",
),
],
},
),
),
],
),
},
),
]
Přesné typy věcí si vysvětlíme až u parseru, ale mělo by zde být vidět že už si jsou podobné vstupy a výstupy.
Implementace
Vytvoříme si nový soubor tokenstream.rs a přidáme si ho do hierarchie modulů přes mod tokenstream; v main.rs.
V tokenstream modulu si vytvoříme nový typ - TokenTree. Jedná se pořád o malou jednotku, tedy token, ale již bude mít stromovou (rekurzivní) strukturu.
Zkopírujeme do něj většinou token z Token struktury, ovšem krom závorek, a ty nahradíme novou variantou Group:
#[derive(Debug)]
pub enum TokenTree {
Let,
If,
While,
Function,
Comma, // ,
Colon, // :
SemiColon, // ;
Group {
mode: GroupMode,
tokens: Vec<TokenTree>
},
Identifier(String),
String(String),
Number(i64),
Op(Op)
}Group je varianta co má v sobě struct s poli mode a tokens - je to podobné vytvoření nového structu Group a varianty Group(Group), interně by se to uložilo shodně.
tokens je array tokenu uvnitř skupiny, tudíž (if) by vrátil [TokenTree::Group { mode = Curly, tokens: [ TokenTree::If ] }]. Je rekurzivní tím, že může obsahovat samo sebe.
Zde je vhodno zmínit že objekty nemohou být přímo rekurzivní, nemohla by se totiž spočítat jejich velikost (resp. by byla nekonečná). Mohou ovšem být nepřímo rekurzivní tím, že budou uloženy přes referenci či na heapu (čímž je též uložen přes referenci). Vec, Box a další ukládají na heap, a proto je TokenTree validní. Více to bude vysvětlené později.
GroupMode je další enum který ukládá variantu závorek:
#[derive(Debug)]
pub enum GroupMode {
Parens, // ()
Curly, // {}
}Teď se dostáváme k samotné implementaci funkcí.
Budeme používat iterátory jako vstup, jednak protože jej vytváří náš Lexer, ale taky protože to je jednodušší pro implementaci. Budou totiž fungovat jako taková fronta, ze které si postupně budeme brát Tokeny a zpracovávat je.
Náš algoritmus token_to_tokentree tedy bude brát Token, není-li to otevírací závorka, rovnou ho převede na TokenTree, jinak převede token závorky na GroupMode a spustí parse_group.
Ten bude číst tokeny, je-li to uzavírací závorka, vratí načtené tokeny jako TokenTree::Group, jinak postupně bude volat token_to_tokentree.
To vše akorát zabalíme do funkce parse_from_tokens, která vezme iterátor a bude ve smyčce volat token_to_tokentree.
Například ( if ( 1 ) ) lexer převede na iterátor (což v tomto případě znamená že nejsou všechny tokeny v paměti, pouze aktuální, čímž šetříme paměť i výpočetní kapacitu) který bude postupně vracet ParensOpen, If, ParensOpen, Number, ParensClose, ParensClose. Náš algoritmus načte ParensOpen, převede na GroupMode::Parens, zavolá parsování skupiny, ta přečte If a převede na ekvivalentní tokentree, a pak opět ParensOpen, převede na GroupMode::Parens a zavolá samo sebe. To najde číslo, dá ekvivalent, a najde ParensClose - u toho zkontroluje že je též Parens a vrátí, předchozí parse_group (rekurzivita) též najde ParensClose, opět ověří a opět vrátí, a pak iterátor již nic nevrátí, došli jsme nakonec a máme vytvořený Vec<TokenTree>.
Začněme tedy token_to_tokentree:
fn token_to_tokentree(token: Token, iter: &mut impl Iterator<Item = Token>) -> TokenTree {Funkce bere dva argumenty, Token, a referenci na Iterator který vrací Token. Reference (&mut) zde sice není nutná, nicméně na volání (když voláme parse_group) bychom museli přidávat referenci (jinak by se iter předával a při další iteraci bychom k němu neměli přístup) a místo toho iter označit jako mut proměnnou - výsledek je stejný, tady toho napíšeme méně a kód je přehlednější.
Obsah funkce bude akorát jeden velký match který bude mapovat jednotlivé tokeny. Začneme těmi jednoduchými které jsou pouze zkopírované:
match token {
Token::Let => TokenTree::Let,
Token::If => TokenTree::If,
Token::While => TokenTree::While,
Token::Function => TokenTree::Function,
Token::Comma => TokenTree::Comma,
Token::Colon => TokenTree::Colon,
Token::SemiColon => TokenTree::SemiColon,
Token::Identifier(ident) => TokenTree::Identifier(ident),
Token::String(string) => TokenTree::String(string),
Token::Number(num) => TokenTree::Number(num),
Token::Op(op) => TokenTree::Op(op),Mohli bychom se sice vyhnout tomuto opakování přes macra, nicméně by výsledný kód nebyl o moc kratší a jen méně přehledný. Rust bohužel neumí mapovat takto typy samo na sebe když si jsou podobné.
Match umí tzv. destructování, kdy rozdělí objekt na jeho části. Zde například rozdělí Identifier(ident) na ident, a vytvoří tak proměnnou v dané části match. Tu poté referencujeme při vytvoření nového TokenTree::Identifier. Jelikož Identifier obsahuje tuple (proměnné v závorce které mohou být různého typu a dle pořadí je typ), můžeme si je přejmenovat jak chceme - místo ident by se dalo použít identifier, string a další. ident je typu String protože Token::Identifier je definován jako Token::Identifier(String).
match se takto používá na získání hodnot uvnitř enum - díky tomu nám garantuje že se nebudeme snažit přečíst číslo uložené uvnitř Identifier či uvnitř Let (který žádnou další hodnotu uloženou nemá). Navíc nemáme jinou možnost, všechny jiné způsoby jak získat hodnotu používají match (někdy však skrytě, jako if let který si ukážeme za chvilku v parse_group).
Jako další přidáme logiku pro otevírací závorky, a zároveň si představíme novou syntaxi uvnitř match:
open @ (Token::ParensOpen | Token::CurlyOpen | Token::BracketOpen) => {
let group = parse_group(token_to_groupmode(&open).unwrap(), iter);
group
},open @ značí že chceme jako open mít dostupný token, odpovídá-li (match) danému vzoru. Již jsme viděli | použité v lexeru pro vícero range, ale můžeme je použít i u kontroly enumu.
open @ (..) by zde nemusel být, mohli bychom ho odebrat a místo toho uvnitř token_to_groupmode referovat na token argument. Takto akorát máme lepší čitelnost (open je definován jako ParensOpen/CurlyOpen/BracketOpen a o řádek výše) a můžeme lépe přemýšlet nad programem později.
Teď ovšem pokud uzavřeme funkci (přidáme }}), dostaneme chybu - match totiž stále nereferencuje close varianty. Dostaneme-li však uvnitř token_to_tokentree uzavírací závorky, jedná se o chybu - správné uzavírací závorky by měl odchytit nadřazený parse_group. Přidáme proto poslední možnost která dá chybu - rust po nás chce explicitně referencovat všechny možnosti (exhaustive match), aby jsme omylem nezapomněli na určité varianty, například kdyby jsme později přidali další tokeny.
Token::ParensClose | Token::CurlyClose | Token::BracketClose => panic!("unexpected token: {:?}", token),Zde opět máme výpis možností - nepřidáváme _ => protože když bychom později přidal nový token, mohlo by se stát že bychom ho zapomněli přidat do této funkce a zbytečně bychom dostali chybu když bychom se ho pokusili použít. Můžeme tak jednoduše myslet na budoucnost, a v případě budoucího přidání nového Token dostaneme od rustu chybu že ve funkci token_to_tokentree nám chybí varianta pro tento nový token.
Posuňme se dále, chybí nám token_to_groupmode. Je to akorát pomocná funkce s dalším match:
fn token_to_groupmode(token: &Token) -> Option<GroupMode> {
match token {
Token::ParensOpen | Token::ParensClose => Some(GroupMode::Parens),
Token::CurlyOpen | Token::CurlyClose => Some(GroupMode::Curly),
_ => None
}
}Zde nám nevadí použít _ => jelikož se týká pouze specifických tokenu. Vracíme však Option a ne přímo GroupMode (s tím že by byl _ => panic!("..") jako jinde) pro lepší práci s chybou. V budoucnu se k tomuto vrátíme i jinde, zde akorát chceme aby uživatelé této funkce explicitně řešili chybu - token_to_tokentree proto volá unwrap.
Pokračujme dále, token_to_tokentree referencuje parse_group. Ta bere GroupMode a iterátor. Jejím úkolem je parsovat postupně tokeny, dokud nenajde uzavírací závorku. Je-li správného typu, vratí Group struct (& enum TokenTree hodnotu), jinak vrátí chybu (resp. momentálně crashne program přes panic!):
fn parse_group(mode: GroupMode, iter: &mut impl Iterator<Item = Token>) -> TokenTree {
let mut tokens = Vec::new();
while let Some(token) = iter.next() {
match token {
close @ (Token::ParensClose | Token::CurlyClose | Token::BracketClose) => {
if mode != token_to_groupmode(&close).unwrap() {
panic!("unexpected token: {:?}", close);
}
return TokenTree::Group {
mode,
tokens
}
},
token => tokens.push(token_to_tokentree(token, iter))
}
}
panic!("unexpected end of input in group {:?}", mode);
}Náš lexer implementuje metodu next, což je právě ta která se zde používá - dokud next vrací Some a ne None, budeme ve smyčce. Zde používáme variantu match, i když ho specificky nezmiňujeme - if a while totiž umí let deklaraci která dělá jednu variantu (můžeme se též setkat s názvem "rameno") z match. Samozřejmě umí i destructování pro získání hodnoty.
Uvnitř smyčky máme další malý match expression, který tentokrát bere uzavírací závorky. Uvnitř této varianty kontroluje zda sedí typ závorky, aby se detekovali chyby jako ( }. Pokud sedí typ, vrátíme nový TokenTree s hodnotou Group { mode, tokens } - mode jsme dostali jako argument, a tak ho i vracíme, a tokens jsme si vybudovali z ostatních tokenů.
Nejedná-li se o uzavírací závorku, voláme token_to_tokentree a ukládáme výsledek do seznamu tokens. Zde je rekurze - token_to_tokentree může dostat otevírací závorku a v tu chvíly opět volá parse_group.
Celé to zakončíme poslední nejkratší funkcí, která bude určená pro použití mimo modul tokenstream:
pub fn parse_from_tokens(mut iter: impl Iterator<Item = Token>) -> Vec<TokenTree> {
let mut tokens = Vec::new();
while let Some(token) = iter.next() {
tokens.push(token_to_tokentree(token, &mut iter))
}
tokens
}Obdobně jako parse_group ve smyčce (dokud iter.next() vrací Some) voláme token_to_tokentree a ukládáme výsledky do seznamu Vec<TokenTree>, který pak vracíme.
Nyní na konec funkce main (v modulu main) můžeme přidat tokenstream:
let tokentree = tokenstream::parse_from_tokens(cursor);
dbg!(&tokentree);Ale nastane chyba při kompilaci - use of moved value: cursor. .collect::<Vec<_>>() si totiž převezme proměnnou, a my ji poté nemůžeme použít. Ono by to totiž nebylo správné chování, collect spotřebuje celý iterátor (frontu), a nenechal by nám nic ke zpracování. Mohli bychom zaimplementovat rozdělení iterátoru do dvou, nicméně je k dispozici mnohem jednodušší řešení - zakomentovat řádek s collect, jelikož ho již nepotřebujeme.
Poté bychom měli být schopni spustit náš program a dostat nový výstup pro script if(variable){print("hello world");}:
[
If,
Group {
mode: Parens,
tokens: [
Identifier(
"variable",
),
],
},
Group {
mode: Curly,
tokens: [
Identifier(
"print",
),
Group {
mode: Parens,
tokens: [
String(
"hello world",
),
],
},
SemiColon,
],
},
]
Parser
Parser je takový final boss našeho jazyka - i když je executor přibližně stejně dlouhý (obojí kolem 300 řádků kódu, když do parseru nepočítám definici objektů která executor používá též), parser má mnohem složitější kód. Většina funkcí executoru jsou akorát definice jak vykonat akce, a na spočítání plus a minus toho opravdu moc nepotřebujete. Mezitím v parseru musíme řešit kontrolu chyb (co když dostaneme let;), přednosti (a to nejen že násobení má mít přednost před sčítání - to ani momentálně nebudeme mít zaimplementované - ale i mezi jinými operacemi jako že matematické operace mají přednost před porovnáváním, aby 1 < 1 + 2 vrátilo 1/true a ne 2) a obecné zpracování složitějších zápisů.
Vytvořme si nový modul parser a zadefinujme v něm datové struktury. Cílem parseru je převést seznam tokenů (v našem případě tokentree) do struktur se kterými se lépe pracuje později. Tedy místo [Let, Identifier("variable"), Op(Equal), String("value")] dostat [Let { ident: "variable", value: String("value") }].
Náš executor poté později nemusí řešit a kontrolovat že po let následuje identifier a po něm =, ale pouze zadefinujeme jak se má spustit Let struktura.
Pro prvotní parser si přidáme pár zjednodušení oproti původnímu plánu - žádné objekty (struktury) nebo seznamy, jen čísla a text.
Nejdříve si rozdělíme zapisovatelné věci do dvou skupin podle toho kde je můžeme použít, statement a expression:
Statement něco jen říká, ale nevrací hodnotu. Pro nás definice proměnné (let), definice funkce, if a while.
Expression se snaží vyjádřit určitou hodnotu. Jedná se o proměnné, jejich přímé zapsání (text a číslo), operace na nich a volání funkcí.
Začneme výrazy které vrací hodnotu, z toho důvodu, že uvnitř statement můžeme používat expression, a tudíž bychom je stejně museli zaimplementovat.
Nejjednodušší výraz je ten co vrací rovnou hodnotu a nic už s ní neprovádí (žádné početní operace a podobně). Typy výrazu jsou následující:
#[derive(Debug)]
pub enum Expression {
Identifier(String),
String(String),
Number(i64)
}Všechny 3 již známe, a jsou mapované přímo na základní tokeny.
Tudíž i naše základní funkce bude jednoduchá:
fn parse_simple_value(mut tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {
if let Some(token) = tt.next() {
match token {
TokenTree::Identifier(ident) => {
Some(Expression::Identifier(ident))
},
TokenTree::String(string) => {
Some(Expression::String(string))
},
TokenTree::Number(num) => {
Some(Expression::Number(num))
},
token => panic!("Unexpected token: {token:?}")
}
} else {
None
}
}Hurá máme parser, a to jsme se báli že bude složitý. Má teda pár podmínek pro funkci, primární problém je že neumí nic než proměnnou, text a číslo, a neumí víc jak právě jeden token, takže ani ta proměnná nam nebude na moc věcí.
Přidáme si pro jednodušší úpravu jednu zabalovací funkci která bude sloužit jako veřejné api tohoto modulu:
pub fn parse_expr(tt: impl IntoIterator<Item = TokenTree>) -> Option<Expression> {
parse_simple_value(tt.into_iter())
}Později přidáme vícero funkcí, tak ať je nemusíme měnit všude kde je používáme.
Další ukázka je impl IntoIterator místo Iterator. Rust má pro jednodušší převádění Into a From traity, a zde používáme obdobu, kde bereme jakýkoliv typ který lze převést na Iterator. Přímo Iterator totiž nemají naimplementované (z různých důvodů) všechny typy, i u těch kde bychom to čekali - Vec, [] atd. Pokud je chceme brát jako argument, musíme si je nejdříve převést na Iterator, pro čež IntoIterator má jednoduchou funkci - into_iter. Díky tomu můžeme brát jak Vec tak i jiné iterátory (protože Iterator má zaimplementovaný IntoIterator - prostě vrátí sám sebe) bez dupliciti kódu, ale zároveň s bezpečnými typy, nenechá nás tam dát číslo (ale například 1..2 implementuje IntoIterator - i když už ne IntoIterator<Item = TokenTree>, protože vrací číslo a tudíž je akorát Item = s číselnými typy).
Pojďme přidat závorky na přednost.
V parseru je nutné pamatovat na přednosti, zde jsou ale lehce převráceně než jak by si někteří mohli myslet - části s největší předností zpracováváme jako poslední. Executor totiž, lehce neintuitivně, spouští nejvíc vnořený kód první, například (1 + (2 + 3)) dá obdobu Op { left: 1, op: +, right: Op { left: 2, op: +, right: 3 } }. Pro vypočítání operace musíme nejdříve zjistit hodnoty, levá je jednoduchá, ale pravá je další Op, kteoru spustíme, tudíž se vnořená operace spustí dříve.
Budeme proto parsovat menší přednosti jako první, čímž dostaneme vyšší přednost hlouběji ve výsledném AST.
Největší přednost mají závorky, a jako poslední se spustí parse_simple_value, proto přidáme jejich parsování právě tam:
fn parse_simple_value(mut tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {
if let Some(token) = tt.next() {
match token {
...,
TokenTree::Group { mode, tokens } => {
match mode {
GroupMode::Parens => {
parse_expr(tokens)
},
_ => panic!("unexpected group mode in value: {:?}", mode)
}
},
token => panic!("Unexpected token: {token:?}")
}
} else { None }
}Postraní poznámka, v tomto bodě již můžete přeskočit a zaimplementovat Executor pro Expression (viz příští velký nadpis) a použít jej. Můžete rozparsovat (přes parse_expr) Vec<TokenTree> z parse_from_tokens, a rozparsovaný Expression spustit. I když vám toho moc nedá zatím, ale můžete jej použít i pro testování mezikroků.
Volání funkcí
Jedna z možností, jak přidat funkce, by byla v parse_simple_value přidat smyčku, ukládat mezihodnotu a nalezneme-li groupu po hodnotě (a ne jako první), bude se jednat o volání funkce. Tím by jsme si pokryli příklady typu print("text"), (print)("text"), function(1)(2) a podobně. Problém by však nastal později, pokud by jsme chtěli přidat operaci s vyšší předností než zavolání funkce - protože by naše parsování funkce mělo největší přednost, například dot operátor pro struktury/objekty či listy (console.log(), array[1].func(), array[1]()).
Náš parser proto bude vrstven - každá vrstva bude brát Iterator a vracet Expression (resp. Option<Expression> pro případ že Iterator by byl prázdný). Interně si vrstva iterátor rozdělí a zpracuje dle potřeb a zavolá ostatní vrstvy. Díky tomu budeme moci (relativně) jednoduše přidat další funkcionalitu do našeho parseru později. To se nám projeví rychle - parsování tzv. binary operací, například sčítání či porovnání, je téměř shodné ale má jinou prioritu a tudíž musí mít vlastní vrstvu.
První a poslední vrstvu již máme - naše poslední vrstva je parse_simple_value, a první je parse_expr který rovnou volá tu poslední.
Zde se hodí myslet nad invariantami, podmínky, pro které naše funkce funguje správně. Postupně je budeme uvolňovat. parse_simple_value má jako podmínku že je pouze jedna hodnota v iterátoru. Naše funkce parse_fn_call již nemá podmínku že má pouze jednu hodnotu, ale má podmínku že se skládá pouze z jednoduchých hodnot a závorek, a že po první hodnotě následují pouze TokenTree závorek.
Budeme tedy moci parsovat kód jako 1, print(1), (print)(1), function(1)(2), (function(1))(2) a podobně. Ostatní operace v rámci expression (porovnávání, matematické operace, nastavení hodnoty etc) odstraní vrstvy nad námi (tedy s nižší prioritou), a jediný validní kód na této vrstvě je tedy akorát jednoduché hodnoty a závorky.
Náš algoritmus tedy bude následující: první hodnota je vždy přímo hodnota (dá se do parse_simple_value), dále mohou následovat pouze závorky které budou dělat z předchozí hodnoty funkci která se bude volat, a ty se mohou opakovat.
Vytvoříme si nejdříve strukturu FunctionCall:
#[derive(Debug)]
pub struct FunctionCall {
pub func: Box<Expression>,
pub args: Vec<Expression>
}Zde je opět použita indirekce, jednou Vec, který již známe, a jednou Box. Box je struktura která svůj obsah dá na heap ("hromadu") a vrací pouze pointer na svůj obsah. Díky této indirekci víme velikost FunctionCall a můžeme mít rekurzivní struktury. Nevýhoda je že vytvoření Box (stejně jako Vec a dalších heap struktur) trvá déle.
FunctionCall přidáme do Expression:
#[derive(Debug)]
pub enum Expression {
Identifier(String),
String(String),
Number(i64),
FunctionCall(FunctionCall)
}Naše funkce pak akorát dá první hodnotu jako vstup do předchozí vrstvy a následně hodnotu vkládá do FunctionCall.
fn parse_fn_call(mut tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {
let first = tt.next().unwrap();
let mut value = parse_simple_value([first].into_iter());
if value.is_some() {
while let Some(token) = tt.next() {
match token {
TokenTree::Group { mode, tokens } if mode == GroupMode::Parens => {
value = Some(Expression::FunctionCall(FunctionCall {
func: Box::new(value.unwrap()),
args: Vec::new()
}))
},
token => panic!("unexpected tokens in value (call): {:?}", token)
}
}
}
value
}Tím by nám mělo fungovat parsování test(), (test)() a podobně. Dokonce i print("Hello world") se rozprazuje - ale jeho argumenty zmizí. Ty totiž zatím ignorujeme (při kompilaci a v editoru byste měli dostat varování že tokens uvnítř Group v naší funkci se nepoužívají).
Zase si sepíšeme náš algoritmus na argumenty: oddělit tokeny čárkou (není to hezké když nemusíme řešit závorky vždy? Závorky jsou jeden token a čárky u nich "neuvidíme") a každý z iterátorů mezi čárkami spracovat pro hodnotu zvlášť. Zde navíc ne simple hodnotu, ale plnohodnotné parse_expr.
Zde ovšem narážíme - standartní knihovna Rustu nemá jak rozdělit iterátor na vícero iterátorů. Mohli by jsme iterátor převést na Vec a ten rozdělit, ale poté by jsme museli mít tokeny vícekrát v paměti a navíc by to bylo pomalejší - například pro print(process(load(1))) by jsme token pro 1 museli mít v paměti 4x! V našem případě by to nejspíše nedělalo problém, ale nabízí se nám mnohem lepší řešení: použít knihovnu která toto umí, navíc je v běžné praxi, a tím se naučit používat knihovny (a za chvilku i jak řešit lifetime kvůli této knihovně).
Knihovna kterou chceme použít se jmenuje itertools. Pro přidání do projektu spustíme v terminálu cargo add itertools. Cargo přidá dependency do Cargo.toml a stáhne to. Druhá možnost je najít si verzi (v docs.rs, viz odkaz, je vlevo pod názvem, v době psaní 0.13.0) a přidat do Cargo.toml manuálně. Jakmile začneme knihovnu používat v kódu, cargo run knihovnu stáhne a zkompiluje dle použitých funkcí.
itertools exportuje trait Itertools, který je implementován pro všechny iterátory. Tudíž funkce které budeme používat by vám váš editor měl již doporučit, a při jejich použití přidat use. My si ho ale můžeme samozřejmě přidat i manuálně: use itertools::Itertools;. To přidá trait mezi viditelné objekty, a následně můžeme používat jeho funkce na objektech pro které je implementován, v našem případě na objektech s traitem Iterator. Rust viditelnost vyžaduje totiž mít trait "viditelně" pro jeho použití - doteď jsme to nemuseli dělat protože spousta trait je viditelných v základu (včetně Debug, Iterator atd).
Budeme si chtít naimplementovat novou funkci, parse_args. Jejím úkolem bude vzít tokens (Vec<TokenTree>) ze závorek (Group), rozdělit ji přes , a rozparsovat. Pro to můžeme použít funkci chunk_by na iteratorech z Itertools, která bere funkci podle které objekt rozdělí (podle toho jak jsou v pořadí, i.e. nemění jejich pořadí a místo toho se klíč může opakovat, takže 1 1 , , 2 by dal tři iterátory (false, [1 1]) ; (true, [, ,]) ; (false, [2])). Funkce může vracit cokoliv, co se dá porovnávat pro rozdělení, v našem případě nám bude stačit jednoduchý boolean true/false, a to jestli se jedná o čárku nebo ne. To nám dá speciální ChunkBy objekt ze kterého můžeme udělat opět iterátor přes into_iter. Ten nám dá Groups, což je iterátor, který vrací jiné iterátory jako jeho objekt (takový impl Iterator<Item = impl Iterator<Item = TokenTree>>), podle jejich rozdělení, a zároveň do kterého rozdělení patří. My si poté vyfiltrujeme iterátory na ty které nemají čárky, a ty jednotlivě převedeme na Expression a uložíme (vrátíme) jako argumenty.
Což je opravdu hodně slov na následující funkci:
fn parse_args(tokens: Vec<TokenTree>) -> Vec<Expression> {
tokens
.into_iter()
.chunk_by(|tt| match tt { TokenTree::Comma => false, _ => true })
.into_iter()
.filter_map(|(matches,value)| if matches { Some(Value) } else { None })
.filter_map(|tokens| parse_expr(tokens))
.collect()
}První funkce vrací false pro comma, jelikož filtrujeme na matchující iterátory (ty, které jsou true), a ty parsujeme, a my chceme rozparsovat všechny krom Comma.
Tento kód můžeme dále zjednodušit a tím (dle mého) i zlepšit čitelnost.
Nejdříve si druhou funkci extrahujeme jako samostatnou funkci filter_for_matches:
fn filter_for_matches<T>((matches, value): (bool, T)) -> Option<T> {
matches.then_some(value)
}I když je tato funkce krátká, budeme ji používat na vícero místech pro stejné či podobné účely, a tak se může hodit se neopakovat. Nemusíme totiž opakovat |(matches, value)| matches.then_some(value) ale vpíšeme pouze filter_for_matches.
Funkce je generalizovaná pro jakékoliv T, jelikož to se nám bude měnit.
Druhá úprava je použití macra místo první closure/funkce. Jelikož je toto (match na boolean) častý vzor, rust má ve své standartní knihovně jednoduché macro matches!, které se rozšíří na to stejné co náš existující kód, jen je opět kratší a čitelnější (vyhneme se změti znaků , _ =>).
Výsledná funkce bude vypadat následovně:
fn parse_args(tokens: Vec<TokenTree>) -> Vec<Expression> {
tokens
.into_iter()
.chunk_by(|tt| matches!(tt, TokenTree::Comma))
.into_iter()
.filter_map(filter_for_matches)
.filter_map(parse_expr)
.collect()
}Změníme-li nyní parse_expr aby volalo parse_fn_call místo parse_simple_value, mělo by nám správně fungovat parsování volání. print("Hello world!") jde rozparsovat.
Operace
Dostáváme se k nejtěžší části parseru, parsování operací. Operací je myšleno práce s dvěmi hodnotami, například sčítání, porovnání či nastavení proměnné. My začneme s nastavením proměnné jelikož je odlišné a jednodušší než ty ostatní.
Nastavení proměnné
Nastavení proměnné přes = je jediná operace která se zpracovává zprava doleva, tzv. right associative.
Je to kvůli tomu, že chceme, aby var1 = var2 = 3 nastavilo var1 i var2 na 3, tudíž správný výsledný tree je var1 = (var2 = 3) a nikoliv (var1 = var2) = 3, to by totiž nefungovalo (nastavit var1 na var2 a výsledek této operace na 3).
Naše funkce tedy rozdělí iterátor přes = a jednotlivé části nechá rozparzovat další vrstvou (parse_fn_call; v příští sekci se však změní).
Dále zjistíme jestli je zde vícero částí - není-li tak, vrátíme první rozparzovanou část rovnou (i.e. neobsahuje-li iterátor =, není co řešit a vrátíme to co rozparzují další vrstvy).
Obsahuje-li však další, načteme všechny části do Vec a budeme v něm iterovat nazpátek - načíst do listu musíme právě kvůli tomu aby jsme mohli jít od posledního k prvnímu.
Ty následně převedeme do Operation přes fold na iterátoru - ten bere prvotní hodnotu a funkci, která vezme předchozí hodnotu a aktuální prvek z iterátoru a vrací novou hodnotu. Toto lze použít například na sčítání ([1,2,3].into_iter().fold(0, |(sum, item)| sum + item)), ale výsledná hodnota může být i jiná než jednotlivé prvky, čehož právě využijeme.
Kontrola zda máme dvě a více části je zde kvůli prvotní hodnotě, ta totiž bude vyžadovat dva prvky:
#[derive(Debug)]
pub struct Operation {
pub left: Box<Expression>,
pub right: Box<Expression>,
pub op: Op
}I když naše funkce vždy kontroluje pouze pro Op::Equal, ukládáme i vybranou operaci aby jsme později (až přidáme parsování ostatních operací) nemuseli duplikovat kód.
Funkce bere opět iterátor a vrací Option<Expression>:
fn parse_op_equal(tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {Následně si iterátor předpřipravíme tím že ho rozdělíme přes = a rozprazujeme další vrstvou:
let mut grouped = tt
.chunk_by(|tt| !matches!(tt, TokenTree::Op(Op::Equal)));
.into_iter()
.filter_map(filter_for_matches)
.map(|tokens| parse_fn_call(tokens));To nám však dá chybu "temporary value dropped while borrowed". into_iter pracuje (v tomto případě) s referencí, a objekt na který se referuje (hodnota která vrací chunk_by) by se zahodil (protože si ho nikam neuložíme) zatímco by byl vypůjčen (referován). Rust nám však rovnou řekne i řešení: uložit si mezi výsledek do proměnné. Ta se může i jmenovat stejně, čímž skryjeme její původní výsledek, jelikož ho nebudeme potřebovat:
let grouped = tt
.chunk_by(|tt| !matches!(tt, TokenTree::Op(Op::Equal)));
let mut grouped = grouped
.into_iter()
.filter_map(filter_for_matches)
.map(|tokens| parse_fn_call(tokens));Následně si získáme první dvě hodnoty. První rovnou převedeme z Option<Expression> na Expression - je-li None, není nutnost pokračovat dále a můžeme rovnou vrátit None. Použijeme na to, obdobně jako u lexeru, ?, který v případě možnosti None rovnou vrátí z funkce None, jinak se do first uloží rozbalený Expression.
let first = grouped.next()?;
let second = grouped.next();U druhé však ? není - pokud by byl a nebyla by druhá hodnota, funkce by vrátila None, my však chceme aby v tomto případě vrátila první hodnotu.
Proto navážeme podmínkou, která vrátí první hodnotu když nebude splněna:
if let Some(second) = second {
...
} else {
first
}Do první části přidáme logiku této vrstvy. Nejdříve si převedeme iterátor na array, ale nezapomeneme na první a druhou hodnotu kterou jsme z iterátoru už "vytáhli".
let mut collected = [first, second]
.into_iter()
.chain(grouped)
.filter_map(|v| v)
.collect::<Vec<_>>();chain je metoda iterátorů která spojí dva iterátory stejného typu (resp. stejného výsledku) do jednoho, v pořadí první iterátor chain druhý iterátor.
Následně z Option<Expression>, který vrací následující vrstva, uděláme Expression tím že odfiltrujeme None výsledy v rámci filter_map. Nakonec pouze vytvoříme kolekci Vec<Expression>.
Než však přidáme fold, potřebujeme si vytvořit první hodnotu pro fold. Ta se bude skládat z poslední a předposlední hodnoty kolekce. Vec na toto má funkci pop, která odebere a vrátí poslední element. Vrací Option pro případ že je kolekce prázdná, my však máme garantované že nebude (bude mít alespoň dva prvky), a tudíž zavoláme unwrap:
let last = collected.pop().unwrap();
let prevlast = collected.pop().unwrap();Následně akorát vrátíme nový Expression vyrobený z foldování iterátoru:
Some(Expression::Operation(collected
.into_iter()
.rev()
.fold(Operation {
left: Box::new(prevlast),
right: Box::new(last),
op: Op::Equal
}, |prev, value| Operation {
left: Box::new(value),
right: Box::new(Expression::Operation(prev)),
op: Op::Equal
})))rev je funkce na speciálních iterátorech (double ended iterator), většinou pouze těch které jsou nad kolekcí (Vec, String, []...), která otočí pořadí itemů (jde pozpátku).
Změňte parse_expr aby volal parse_op_equal.
Můžete otestovat, zda 1 = 2 = 3 vytvoří následující kód:
[
Value(
Operation(
Operation {
left: Number(
1,
),
right: Operation(
Operation {
left: Number(
2,
),
right: Number(
3,
),
op: Equal,
},
),
op: Equal,
},
),
),
]
Ostatní
Pro ostatní operace si vytvoříme jednu utility funkci. Bude brát iterátor, filtr operace a další vrstvu.
Na tomto si zároveň ukážeme generika s trait podmínkami. My totiž voláme funkci která bere iterátor, s referencí na objekt který vlastníme. My proto musíme dát podmínku, že si referenci nemůže uložit, tato reference totiž přestane být validní po ukončení této funkce. Zároveň, chceme-li volat funkci, nemůžeme ji volat s impl Trait, jelikož by nešlo spočítat přesný typ, ale s konkrétním typem. V našem případě to je itertools::Group, jelikož chunk_by vrací ChunkBy, který přes into_iter převedeme na typ Groups, což je iterátor který vrací Group.
Group bere svoje parametry, lifetime pro který je skupina validní (který my musíme nastavit správně), klíč podle kterého se sdružují výsledky, typ iterátoru a typ filtru, který vrací klíč.
My typ klíče známe, bool, ale neznáme přesně ostatní typy (impl Iterator není konkrétní typ; každá funkce je vlastní typ a proto nejde sestavit přesný typ pro filtr a další vrstvu).
Naše funkce tedy začne následujícím způsobem:
fn parse_op<T, F, P>(tt: T, filter: F, parse: P) -> Option<Expression>Kde T, F a P jsou generika, podobně jako u typů (jako třeba Option<T>). My je však musímě upřesnit jelikož nebereme všechny možnosti. Pro to se používá where. Pro upřesnění T a F nám stačí jednoduše přepsat jejich typy:
where
T: Iterator<Item = TokenTree>,
F: Fn(&TokenTree) -> bool,Pro P však musíme přepsat i správně lifetime. Jedno z řešení, které se běžně používají, je dát i lifetime jako generikum funkce, tedy mít parse_op<'a, T, F, P>, u nás by však nefungoval jelikož by si volající mohl vybrat lifetime delší než tato funkce, což by mohlo generovat nevalidní kód, což nás rust nenechá.
Pro zápis "lifetime je validní pouze v rámci funkce" se používá for<'a>, tedy pro každý lifetime 'a musí platit. A jediná možnost jak může platit pro každý lifetime je použít ten nejkratší možný, což je právě ten pro volanou funkci. Lifetime totiž lze zkracovat ale nelze jej prodlužovat.
P: for<'a> Fn(itertools::Group<'a, bool, T, F>) -> Option<Expression> {Náš algoritmus bude následující: rozdělíme si tokeny podle filtru na operátory a ne-operátory.
let grouped = tt.chunk_by(filter);
let grouped = grouped.into_iter();Zde nechceme ani filtrovat ani nijak mapovat funkci zatím, potřebujeme totiž pracovat s operátory ale i s ostatníma tokenama.
Náš algoritmus bude postupně brát tokeny.
Budeme si ukládat poslední expression a operátor.
Najdeme-li expression, necháme rozparzovat. Pokud najdeme první, tak ještě nebudeme znát operátor a uložíme si do příští loopy. Pokud ale již známe operátor, vytvoříme Operation, operátor odebereme (použili jsme ho při vytvoření objektu Operation) a výsledný expression si uložíme.
Najdeme-li operátor, zkontrolujeme že je pouze jeden (jinak chyba) a uložíme.
chunk_by nám garantuje že se nebude opakovat stejný typ (střídá se operátor a ostatní), tudíž v operátoru nemusíme kontrolovat zda-li je operátor přítomen - v předchozí iteraci musela být hodnota, která by operátor použila, nebo nic (a začalo se operátorem; v příští iteraci se zkontroluje a zjistí se že není první hodnota ale je operátor a funkce dá chybu).
Implementace takového algoritmu je
let mut val = None;
let mut op = None;
// A funny loop:
// chunk_by gurantees that is_op oscilates between true and false
// thus if is_op is false, it means that it's either the first time (so val is None by default) or that the previous token was an operator
// if the previous token was an operator, op is Some and hte if statement is true, which consumes op
// that's why if is_op is true op is never Some and if false val is either Some *and* op is Some or val is None.
for (is_op, tt) in grouped {
if is_op {
if op.is_some() { unreachable!() }
let new_op = tt.exactly_one().map_err(|t| t.collect::<Vec<_>>()).expect("expected one operator");
op = match new_op {
TokenTree::Op(op) => Some(op),
_ => unreachable!()
};
} else {
let new_val = parse(tt);
if let Some(op) = op.take() {
val = Some(Expression::Operation(Operation {
left: Box::new(val.expect("expected value before operator")),
right: Box::new(new_val.expect("expected value after operator")),
op
}));
} else {
// chunk_by guarantees this
if val.is_some() { unreachable!() }
// Some should be guaranteed as the tt isn't empty iterator
val = new_val;
}
}
}Po konci smyčky zkontrolujeme že není nastavený operátor (aby 1 + dalo chybu):
if op.is_some() {
panic!("expected value after operator")
}A funkci zakončíme vrácením val:
val
}Nyní můžeme vytvořenou funkci parse_op použít pro rozparzování matematických operací a porovnávání:
pub fn parse_op_math(tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {
parse_op(tt, |tt| matches!(tt, TokenTree::Op(Op::Plus | Op::Minus | Op::Multiply | Op::Division)), |g| parse_fn_call(g))
}
pub fn parse_op_comps(tt: impl Iterator<Item = TokenTree>) -> Option<Expression> {
parse_op(tt, |tt| matches!(tt, TokenTree::Op(Op::EqualTo | Op::NotEqual | Op::LessThan | Op::GreaterThan)), |g| parse_op_math(g))
}Zde si můžete všimnout že |g| parse_fn_call(g) je zbytečné a mohlo by se dát pouze jméno funkce. Bohužel tomu tak není, jelikož podmínky parse_op si musí změnit typ funkce, tedy nechat rust vyzjistit pro které typy funguje. Bez toho by vyžadoval 'static lifetime iterátoru, který nemůžeme poskytnout.
Nakonec akorát změníme vrstvu parse_op_equal aby místo parse_fn_call volala parse_op_comps.
Statement
Pojmem statement je myšleno to, co nemusí vracet hodnotu a nemůže se použít jako hodnota. V našem případě je to let, if, while a function, ale zároveň můžeme použít i expression jako statement - volání funkce, změně proměnné a podobně. Jako poslední možnost, statement může být i seznam jiných statementů, jedná-li se o blok ohraničený { }.
#[derive(Debug)]
pub enum Statement {
Let(LetDefinition),
Function(FunctionDefinition),
If(IfStatement),
While(WhileStatement),
/// { } delimited block of code, used after if/while/function
Block(Vec<Statement>),
Value(Expression)
}Přesné definice hodnot si ukážeme postupně během přidávání logiky do parse_statement.
Naše funkce parse_statement bude vracet rozparzovaný statement, zabalený v option pro případy kdy iterátor je prázdný (v budoucnu by jsme zde mohli raději vracet chybu) nebo začíná středníkem (aby ;; byl validní syntax).
Záček funkce nepřináší žádné novinky:
fn parse_statement(mut tt: impl Iterator<Item = TokenTree>) -> Option<Statement> {Následně vytvoříme velký match který bude vracet hodnotu, a to rozparzovaný statement. Nejdříve podle prvního tokenu poznáme kterým směrem se vydat dále (podle keywordu poznáme jednotlivé statementy, jinak se jedná o Value):
let statement = match tt.next()? {Otazník zde (obdobně jako v lexeru) funguje obdobně jako unwrap, ale místo panic funkce pouze vrátí None. Tedy je to přepis match (match tt.next() { Some(t) => t, None => return None }) {.
Let
Jako první budeme zpracovávat let, jde o definici proměnné ve formát let variable = value;. Naše struktura tudíž musí držet jméno proměnné a její základní hodnotu.
#[derive(Debug)]
pub struct LetDefinition {
pub ident: String,
pub value: Expression
}A první možnost uvnitř match pro Let keyword:
TokenTree::Let => {
let ident = match tt.next() {
Some(TokenTree::Identifier(ident)) => ident,
_ => panic!("expected identifier after let keyword")
};
if tt.next() != Some(TokenTree::Op(Op::Equal)) {
panic!("expected equal sign after identifier")
}
let value = tt.take_while(|tt| !matches!(tt, TokenTree::SemiColon));
let value = parse_expr(value);
let value = value.expect("expected value after Equal (=)");
Statement::Let(LetDefinition {
ident,
value
})
},Zde nejdříve přečteme identifier (nebo vrátíme chybu, není-li Identifier), zkontrolujeme = a následně přečteme vše do první SemiColon z token streamu. take_while je standartní funkce Iterator, která čte z iterátoru dokud sedí určitá podmínka. Naše podmínka je dokud se nematchuje SemiColon. take_while přečte ze streamu i první hodnotu pro kterou podmínka neplatí, tedy středník, jelikož aby zkontrolovala podmínku musí přečíst aktuální hodnotu ze iterátoru, čímž ho posune. Tu však ale nevrací ve výsledném iterátoru.
Následně se rozparzuje hodnota z nového iterátoru (take_while pouze vytvoří nový iterátor který čte z původního, díky tomu to nebere žádnou paměť navíc i minimální výkon navíc). Poté akorát převedeme Option<Expression> na Expression přes klasický expect.
Vracíme náš Statement s LetDefinition.
Následující statementy If a While jsou obdobou Let:
If
If má podmínku a tělo které se má spustit. V našem případě se bude vždy jednat o Block.
#[derive(Debug)]
pub struct IfStatement {
pub condition: Expression,
pub body: Box<Statement>
}body musí být Box pro indirekci kvůli rekurzi typu.
Rozparzování opět neobsahuje nic nového:
TokenTree::If => {
let condition = match tt.next() {
Some(TokenTree::Group { mode, tokens }) if mode == GroupMode::Parens => {
parse_expr(tokens).expect("expected value in parens")
},
_ => panic!("expected parens after if keyword")
};
let stmts = match tt.next() {
Some(TokenTree::Group { mode, tokens }) if mode == GroupMode::Curly => {
parse_statements(tokens)
},
_ => panic!("expected curly braces after if condition")
};
Statement::If(IfStatement {
condition,
body: Box::new(Statement::Block(stmts))
})
},While
A while je z pohledu parseru zcela shodný, jen vrací jiný typ a hledá jiný keyword.
#[derive(Debug)]
pub struct IfStatement {
pub condition: Expression,
pub body: Box<Statement>
}Místo duplikátního kódu tudíž jen upravíme If aby si uložil typ tokenu a aby bral jak If tak While. Poté upravíme poslední výraz který vrací Expression aby použil další, vnořený match:
condtype @ (TokenTree::If | TokenTree::While) => {
let condition = match tt.next() {
Some(TokenTree::Group { mode, tokens }) if mode == GroupMode::Parens => {
parse_expr(tokens).expect("expected value in parens")
},
_ => panic!("expected parens after if keyword")
};
let stmt = match tt.next() {
Some(TokenTree::Group { mode, tokens }) if mode == GroupMode::Curly => {
parse_statements(tokens)
},
_ => panic!("expected curly braces after if condition")
};
match condtype {
TokenTree::If => {
Statement::If(IfStatement {
condition,
body: Box::new(Statement::Block(stmt)),
else_body: None
})
},
TokenTree::While => {
Statement::While(WhileStatement {
condition,
body: Box::new(Statement::Block(stmt))
})
},
_ => unreachable!()
}
},Function
Poslední statement je deklarace funkce. Formát je function name(arg1, arg2) { body }, tzn zase obdoba předchozích, akorát nyní musíme rozparzovat jména argumentů a uložit do objektu.
#[derive(Debug)]
pub struct FunctionDefinition {
pub ident: String,
pub args: Vec<String>,
pub body: Box<Statement>
}Naše parser funkce postupně přečte identifier, group (parens) a druhou group (curly).
TokenTree::Function => {
let ident = match tt.next() {
Some(TokenTree::Identifier(ident)) => ident,
_ => panic!("expected identifier after function keyword")
};
let args = match tt.next() {
Some(TokenTree::Group { mode, tokens }) if mode == GroupMode::Parens => {
tokens
.into_iter()
.chunk_by(|tt| !matches!(tt, TokenTree::Comma))
.into_iter()
.filter_map(filter_for_matches)
.map(|tokens| match tokens.exactly_one().map_err(|_| ()).expect("Expected only name in function args") {
TokenTree::Identifier(ident) => ident.clone(),
tokens => panic!("expected identifier in function args, found {:?}", tokens)
})
.collect()
},
_ => panic!("expected parens after function identifier")
};
let body = match tt.next() {
Some(TokenTree::Group { mode, tokens }) if mode == GroupMode::Curly => {
parse_statements(tokens)
},
_ => panic!("expected curly braces after function args")
};
Statement::Function(FunctionDefinition {
ident,
args,
body: Box::new(Statement::Block(body))
})
},První skupina, args, se rozdělí přes čárku na jednotlivé iterátory.
Poté se každý iterátor zkontroluje, že má právě jeden element (exactly_one z itertools), a unwrapne se - zde nám však Rust řekne, že ExactlyOneError<I> neimplementuje trait Debug (v lehce delší zprávě - Groups neimplementuje Debug protože..., přečtěte si tu zprávu celou a pokuste se ji pochopit).
My použijeme map_err, který mění Error typ v Result. Bere funkci (closure) která bere starý typ a vrací ten nový, my však o přesný typ nestojíme a celý error můžeme zahodit, a proto dáváme funkci která bere jeden argument beze jména _ a vrací prázdný typ ().
Zbytek je shodný s předchozím.
SemiColon
Pro středník vrátíme None, aby ;;; byla validní syntaxe (zignoruje se).
Tomuto vzoru se říká early return, brzké vracení se, kdy se zbytek funkce nespustí (a tudíž ani match nevrací hodnotu do proměnné statement).
TokenTree::SemiColon => { return None },Ostatní
Všechny ostatní tokeny budou buďto chyba, nebo hodnota/výraz (expression). My proto vytvoříme nový iterátor z daného tokenu a všech následujících které nejsou SemiColon, a necháme je rozparzovat přes parse_expr.
token => {
let value = [token].into_iter().chain(
tt.take_while(|tt| !matches!(tt, TokenTree::SemiColon))
);
let value = parse_expr(value);
Statement::Value(value.expect("Expression should be present"))
}Zakončení
Nyní akorát vrátíme Statement a uzavřeme funkci:
};
Some(statement)
}Executor
Exekutor spustí kód. Je to ta "interpreter" část interpretovaných jazyků - u kompilovaného jsou všechny předchozí části, ale místo executoru je generace kódu do souboru.
Začneme, stejně jako předtím, s definicí typů. Zbytek executoru budou akorát implementace trait, výsledkem bude relativně krátký a čitelný kód. Naše proměnné mohou ukládat číslo, text či funkci. Musíme však i přidat prázdný typ pro uložení prázdné hodnoty z funkce, můžeme si ho pojmenovat Void nebo třeba Null.
#[derive(Debug, PartialEq)]
pub enum Type {
Number(i64),
String(String),
Void,
Function(Function)
}PartialEq implementuje ==, aby jsme mohli porovnávat (jednoduše) hodnoty mezi sebou pro shodu.
Function je nový typ, jelikož chceme podporovat jak nativní funkce (z rust kódu, například print), tak funkce definované v jazyce. Použijeme pro to nový enum:
#[derive(Clone, Debug, PartialEq)]
enum Function {
Native(Rc<NativeFunction>),
UserDefined(Rc<FunctionDefinition>)
}Rc zde použijeme aby jsme nemuseli kopírovat paměť při kopírování proměnné, například když dáme test = print. Druhý důvod je pro porovnávání - nemáme jak zjistit že jsou si funkce rovny, Rc nás nechá porovnat pointery a jestliže je pointer shodný, je i funkce shodná (tedy jestliže test = print, tak print == test).
A nakonec pro nativní funkce definujeme struct:
struct NativeFunction {
name: String,
body: Mutex<Box<dyn Fn(Vec<Type>) -> Type>>
}Mutex nám umožní upravitelnost z vícero míst. Normálně z Rc nemůžeme dostat &mut, protože by Rust nemohl doložit že nemáme víc jak jeden &mut, což by mohlo způsobit chyby. My však potřebujeme &mut kvůli tomu, že FnMut pro spuštění vyžaduje &mut. Mutex uzamkne objekt a během jeho úprav jej nemůže nikdo jiný uzamknout, čímž se garantuje pravidlo "pouze jeden &mut". Zde nutno zmínit, že tím že uzamkne objekt může dojít k tzv. deadlocku, tedy stavu, kdy se program zastaví a nic nedělá. Mutex totiž čeká na to než ho předchozí uživatel odemkne. My si nemusíme hlídat že se odemčení stane, to Rust uděla za nás, nicméně si musíme hlídat že se během uzamčení nepokusíme udělat druhé. Například tento kód:
let a = Mutex::new(1);
let lock1 = a.lock();
let lock2 = b.lock();
drop(lock1);
print!("Done");Nikdy nevypíše Done. Přesuneme-li však drop o řádek více, vše bude fungovat správně. Jelikož ale náš program nebude používat Mutex z vícero míst naráz ale pouze v čase (nespustí se jedna nativní funkce více jak jednou naráz - během nativní funkce se nespouští jiný script kód), není problém. V UserDefined funkcích by tento problém mohl nastat, tam však žádný Mutex není.
Box je potřeba protože dyn nemá pevnou velikost, s čímž si Box umí poradit (Box::new zjišťuje velikost objektu a podle toho alokuje paměť) ale normální objekty ne.
dyn je pro dynamické typování objektu, kdy nevíme jeho typ dopředu, ani při kompilaci. U funkcí nelze znát jejich typ, a impl nelze uložit do objektu, je proto hlavní způsob jak uložit funkci do objektu. Po něm nenásleduje typ ale Trait, který musí daný objekt implementovat. V paměti se poté pouze uloží pointer na implementace traitu, které poté lze volat. My poté můžeme pouze používat funkce z dané traity, ale nemáme jak (jednoduše) dostat původní typ či na něm volat jiné funkce. impl se chová jako generikum, tedy fn test(t: impl Debug) a fn test<T: Debug>(t: T) jsou ekvivalentní, zatímco dyn je konkrétní typ, i když na něj compiler převede (semi) automaticky. Můžeme ale volat s dyn funkce které berou impl, například fn test2(t: dyn Debug) { test(t) }.
Dále si nadefinujeme Context, který si bude ukládat proměnné. Proměnné budou v našem jazyce scoped, tedy budou mít svůj začátek a konec. Například v Javascriptu je var scoped na funkci (proměnná definovaná uvnitř funkce není dostupná mimo ni) a let s const scoped na block, tedy {}. V Pythonu jsou proměnné scoped na funkci. U nás budou na block, tedy {}.
Aby jsme věděli které proměnné jsou dostupné v kterém scopu, budeme si ukládat seznam scopů a v každým z nich mapu názvu (String) na hodnotu (Type). V Rustu je vícero druhů mapy/dictionary, nejpoužívanější je HashMap, který funguje obdobně jako objekt v JS nebo jako Dictionary v Pythonu.
#[derive(Default, Debug)]
pub struct Context {
scopes: Vec<HashMap<String, Type>>
}Context též implementuje pro nás nový trait Default. Ten definuje pouze jednu funkci, default, která vytvoří nový objekt bez vložených parametrů. Některé, ne však všechny typy, obdobně jako u Debug, definují vlastní Default, a obdobně jako Debug, i Default vyžaduje aby všechny hodnoty objektu (u nás scopes) měli implementovaný Default. Vec implementuje Default tak že vrací prázdný array, takže default context bude Context { scopes: Vec::new() }.
A poslední definicí bude nový trait Exec. Bude mít jedinou metodu, a to exec, která bude brát sebe a Context a vracet hodnotu (Type):
pub trait Exec {
fn exec(&self, ctx: &mut Context) -> Type;
}Nyní si však Rust bude stěžovat, že NativeFunction neimplementuje Debug. Ale přidat #[derive] nebude fungovat, jelikož dyn Fn neimplementuje Debug (je to nezávislá trait, tedy to že objekt implementuje Fn neznamená že musí implementovat Debug), musíme proto implementovat Debug manuálně.
Debug má jednu povinnou funkci, a to je fmt, která bere formatter a vrací fmt::Result (definovaný jako Result<(), fmt::Error>). Implementace samotná je však jednoduchá:
impl Debug for NativeFunction {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("NativeFunction")
.field("name", &self.name)
.finish()
}
}Formatteru řekneme že chceme debugovat struct se jménem NativeFunction a jedním polem name. Nemusíme zde debugovat všechny, a proto nebudeme vypisovat i funkci - ta totiž Debug neimplementuje (narozdíl od String uvnitř name), a nešla by tak jednoduše použít.
Context
Pro Context budeme chtít metody pro přidání scopu (našli jsme block), odebrání scopu (odešli jsme z něj), definování nové proměnné, nastavení hodnoty proměnné (když už je definovaná), přečtení hodnoty a definování nativní funkce.
Přidání a odebrání scope je jednoduché:
impl Context {
pub fn add_scope(&mut self) {
self.scopes.push(HashMap::new());
}
pub fn pop_scope(&mut self) {
self.scopes.pop();
}
}Pro definici proměnné chceme upravit poslední HashMap. Na to slouží last_mut, který vrací Option<&mut HashMap>. Podmínka funkce je že bude alespoň jeden scope, a proto můžeme použít unwrap.
insert je funkce z HashMap která nastaví hodnotu pod klíčem ident na hodnotu value.
pub fn define(&mut self, ident: String, value: Type) {
self.scopes.last_mut().unwrap().insert(ident, value);
}Následně chceme mít možnost upravit již definovanou proměnnou.
Na to půjdeme od posledního scopu zpátky, a jakmile nám get_mut z HashMap vrátí Some(&mut Type), upravíme jej.
Funkce vrací bool podle toho jestli se našla proměnná nebo ne.get_mut chce &mut na HashMap, proto musíme použít iterátor který vrací &mut HashMap, což je iter_mut. Tato funkce navíc nespotřebuje naši proměnnou (což by jsme ani nemohli, nevlastníme self.scopes ale máme pouze &mut referenci), místo toho jen použije referenci.
pub fn update(&mut self, ident: String, value: Type) -> bool {
for scope in self.scopes.iter_mut().rev() {
if let Some(v) = scope.get_mut(&ident) {
*v = value;
return true;
}
}
false
}Zjištění hodnoty je téměř to stejné, jen použije get místo get_mut a vrátí referenci na proměnnou:
pub fn get(&self, ident: &str) -> Option<&Type> {
self.scopes
.iter()
.rev()
.find_map(|scope| scope.get(ident))
}Nakonec jen nejsložitější kód pro Context, definice nativní funkce. Bere název funkce (String) a implementaci, s tím že implementace musí být 'static, tedy validní do konce běhu programu. Je to dané tím, že chceme uložit funkci do objektu který nemá lifetime podmínku, tedy musí objekt vlastnit. Pro uživatele této funkce to znamená, že nemůžou použít reference ale mohou před vlastnictví, například tím že se funkce definuje přímo při volání nebo se nepoužije &. Tohle však zní složitěji než je.
pub fn define_native_func(
&mut self,
name: String,
body: impl Fn(Vec<Type>) -> Type + 'static) {
self.define(
name.clone(),
Type::Function(Function::Native(Rc::new(NativeFunction {
name,
body: Mutex::new(Box::new(body))
})))
);
}Tím je Context hotový. V main uvnitř main.rs si definujte nový Context, například ctx, a dejte mu hodnotu Context::default().
Vytvořte první scope (říkejme mu global scope), a definujte si funkci print. Výsledný kód by mohl vypadat třeba takto:
let mut ctx = Context::default();
ctx.add_scope();
ctx.define_native_func("print".to_string(), |args| {
println!("{:?}", args);
exec::Type::Void
});Type
Pro hodnoty naimplementujeme ToString, aby jsme mohli jednoduše použít to_string pro převod hodnoty na String. To použijeme pro operaci +, která u textu bude spojovat text a u čísel sčítat. Dále matematické operace pro jednodušší spouštění operací, From<bool>, pro jednoduchý převod true/false na 1/0 a nakonec PartialOrd pro >, < <= a >=.
Začneme ToString. U jednoduchých typů je i jednoduchá implementace:
impl ToString for Type {
fn to_string(&self) -> String {
match self {
Type::Number(num) => num.to_string(),
Type::String(string) => string.clone(),
Type::Void => "void".to_string(),
...
}
}
}Pro funkce musíme rozlišit mezi nativní a user defined, aby jsme mohli získat jejich jméno. Použijeme format macro, které používá stejné formátovací podmínky jako print, ale pro vytvoření stringu.
Type::Function(func) => match func {
Function::Native(native) => format!("<native function {}>", native.name),
Function::UserDefined(defined) => format!("<user defined function {}>", defined.ident)
}Například print("" + print) by vypsal <native function print>. "" definuje string a + spojuje text, což použije právě ToString. Když mluvíme o +, pojďme i jej implementovat:
impl Add for Type {
type Output = Self;
fn add(self, other: Self) -> Self {
match (self, other) {
(Type::Number(a), Type::Number(b)) => Type::Number(a + b),
(Type::String(a), b) => Type::String(a + &b.to_string()),
(a, Type::String(b)) => Type::String(a.to_string() + &b),
_ => unimplemented!()
}
}
}Add je traita která se použije při použití + v rustu. Typy self, other a výstupu nemusí být shodné - můžeme například sečíst datum s časovým intervalem a dostat nové datum.
My zkontrolujeme zda jsou oba argumenty čísla, pokud ano, tak je sečteme. Pokud je jeden z argumentů string, převedeme ten druhý na string přes to_string() a ty spojíme - pro čež se v rustu též použije +!
V případě nesplnění ani jedné podmínky (např. sečtení funkce a funkce) vrátíme chybu.
Ostatní matematické operace, tedy odečítání (-, Sub), násobení (*, Mul) a dělení (/, Div) implementujeme pouze pro číslo.
Zde se budeme opakovat, nicméně jediný způsob jak se vyhnout opakování je napsat si macro, což je momentálně mimo scope tohoto článku.
impl Sub for Type {
type Output = Self;
fn sub(self, other: Self) -> Self {
match (self, other) {
(Type::Number(a), Type::Number(b)) => Type::Number(a - b),
_ => unimplemented!()
}
}
}
impl Mul for Type {
type Output = Self;
fn mul(self, other: Self) -> Self {
match (self, other) {
(Type::Number(a), Type::Number(b)) => Type::Number(a * b),
_ => unimplemented!()
}
}
}
impl Div for Type {
type Output = Self;
fn div(self, other: Self) -> Self {
match (self, other) {
(Type::Number(a), Type::Number(b)) => Type::Number(a / b),
_ => unimplemented!()
}
}
}Implementace From<bool> pro Type pro převedení porovnání hodnot, je též krátká:
impl From<bool> for Type {
fn from(b: bool) -> Self {
Type::Number(b.into())
}
}From<bool> pro Type totiž zaimplementuje Into<Type> pro bool, a my pak můžeme zavolat into na bool a dostat tak Type. Jelikož je implementovaný From<bool> pro i64, můžeme i my zde použít into.
Zaimplementujeme i opak pro jednodušší a konzistentní převod čísla na boolean uvnitř if a while:
impl From<Type> for bool {
fn from(t: Type) -> Self {
match t {
Type::Number(num) => num != 0,
_ => unimplemented!()
}
}
}Nakonec nám zbývá zaimplementovat PartialOrd, pro >, <, <= a >=. Ten zaimplementujeme pro dvojice čísel a dvojice textů, tedy:
impl PartialOrd for Type {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
match (self, other) {
(Type::Number(a), Type::Number(b)) => a.partial_cmp(b),
(Type::String(a), Type::String(b)) => a.partial_cmp(b),
_ => None
}
}
}Exec
Když jsme si tak krásně naimplementovali operace, pojďme je rovnou použít a ukázat si proč jsme je dělali.
Našim cílem je zaimplementovat Exec pro všechny objekty v AST (objekty z parseru), tedy Expression, Statement a objekty v nich.
Operation
Třeba pro Operation je implementace následující:
impl Exec for Operation {
fn exec(&self, ctx: &mut Context) -> Type {
let left = self.left.exec(ctx);
let right = self.right.exec(ctx);
match self.op {
Op::Plus => left + right,
Op::Minus => left - right,
Op::Multiply => left * right,
Op::Division => left / right,
Op::EqualTo => (left == right).into(),
Op::NotEqual => (left != right).into(),
Op::LessThan => (left < right).into(),
Op::GreaterThan => (left > right).into(),
Op::Equal => {
if let Expression::Identifier(ident) = self.left.as_ref() {
if !ctx.update(ident.clone(), right) {
panic!("variable not found: {}", ident);
}
Type::Void
} else {
panic!("expected identifier on left side of equal operator");
}
},
}
}
}Spustíme levou a pravou stranu (na pořadí spuštění zde záleží, programátoři většinou počítají s tím že se kód bude spouštět zleva doprava), a poté s nimi provedeme požadovanou operaci.
as_ref nám vrátí referenci na obsah Boxu (left i right jsou Box<Expresion>).
Musíme klonovat jméno, jelikož se tento kód může spustit vícekrát (uvnitř while či funkce). Kdyby jsme nepoužili clone a as_ref, rust by si stěžoval "cannot move variable".
Zatím ignorujte chybu že exec není implementovaný pro Expression. Hned se k tomu dostaneme a vyřešíme ji.
FunctionCall
Při zavolání funkce si zjistíme nejdřív obsah funkce a obsah argumentů:
impl Exec for FunctionCall {
fn exec(&self, ctx: &mut Context) -> Type {
let func = self.func.exec(ctx);
let args = self.args.iter().map(|arg| arg.exec(ctx)).collect();
...
}
}Následně zkontrolujeme že se jedná o funkci
match func {
Type::Function(func) => ...,
_ => panic!("expected function in function call")
}A druh funkce
match func {
Function::Native(native) => (native.body.lock().unwrap())(args),
Function::UserDefined(defined) => ...
}Nativní se uzamkne (body je v Mutex) a následně zavolá s argumenty (je na funkci si zkontrolovat argumenty).
Pro funkce v našem jazyce si přidáme nový scope, nadefinujeme proměnné podle názvu proměnných, spustíme obsah, a nakonec opustíme scope a vrátíme výsledek.
{
ctx.add_scope();
for ident in defined.args.iter() {
ctx.define(ident.clone(), Type::Void);
}
for (ident, value) in defined.args.iter().zip(args.iter()) {
ctx.define(ident.clone(), value.clone());
}
let result = defined.body.exec(ctx);
ctx.pop_scope();
result
}Nejdříve všechny argumenty nastavíme na Void, aby existovali ale neměli hodnotu, pro případ že volající nedá dostatečný počet agumentů.
Následně použijeme zip u iterátoru. Ten prolne dva iterátory a dokud oba dva vrací hodnotu, výsledný iterátor vrátí obě hodnoty.
Například [1 2 3] [ "a" "b" "c" ] vrátí iterátor [ (1 "a") (2 "b") (3 "c") ]. Což zde krásně využijeme pro definování proměnných pořadím.
Zde opět dostaneme chybu že Statement neimplementuje Exec. Máme zde trochu problém toho že na sobě věci závisí - Expression může volat Statement a ten zas může volat Expression, budeme proto dostávat chybu o chybějící implementaci než dopíšeme kód. Na druhou stranu si můžeme být jistí že jsme zmínili všechny varianty, i když můžou vracet chybu (například u sčítání máme unimplemented, které spustí panic).
FunctionCall je nejdelší implementace Exec :).
Expression
Implementace Exec pro Expression není složitá, pouze vykopíruje hodnoty u hodnot, zjistí hodnotu proměnné, nebo zavolá jednu z předešlých implementací.
impl Exec for Expression {
fn exec(&self, ctx: &mut Context) -> Type {
match self {
Expression::Number(num) => Type::Number(*num),
Expression::String(string) => Type::String(string.clone()),
Expression::Identifier(ident) => ctx.get(ident).expect("variable not found").clone(),
Expression::Operation(op) => op.exec(ctx),
Expression::FunctionCall(call) => call.exec(ctx)
}
}
}Nyní nám zbývá jen Statement a jeho možnosti. Myslím si, že by jste v tomto bodě měli být schopní zaimplementovat zbytek. Stačí jen pamatovat, že uvnitř Statement::Block je potřeba vytvořit scope a zas ho odebrat po skončení, a že podmínky jsou dělané s čísly, tudíž doporučuji porovnávat s nulou (rozbalit číslo a porovnat s nulou).
Možná jen se podívat na řešení FunctionDefinition.
FunctionDefinition
UserDefined přímo obsahuje Rc<FunctionDefinition>, a tak stačí nakopírovat sebe. Zde též upozornění, implementace je pro Rc<FunctionDefinition> a ne přímo FunctionDefinition jako jinde.
impl Exec for Rc<FunctionDefinition> {
fn exec(&self, ctx: &mut Context) -> Type {
ctx.define(self.ident.clone(), Type::Function(Function::UserDefined(self.clone())));
Type::Void
}
}LetDefinition
LetDefinition jen zavolá v contextu define s hodnotou:
impl Exec for LetDefinition {
fn exec(&self, ctx: &mut Context) -> Type {
let value = self.value.exec(ctx);
ctx.define(self.ident.clone(), value);
Type::Void
}
}IfStatement
Zde použijeme impl From<bool> for Type pro jednoduchý převod typu z čísla na boolean.
impl Exec for IfStatement {
fn exec(&self, ctx: &mut Context) -> Type {
if self.condition.exec(ctx).into() {
self.body.exec(ctx)
} else {
Type::Void
}
}
}WhileStatement
impl Exec for WhileStatement {
fn exec(&self, ctx: &mut Context) -> Type {
while self.condition.exec(ctx).into() {
self.body.exec(ctx);
}
Type::Void
}
}Vec<T>
Chceme implementaci i pro seznam spustitelných bloků. Naše použití je momentálně pro Block, který v sobě má array, a pro funkce.
Můžeme ale zaimplementovat Exec pro listy všech spustitelných bloků, tedy Vec<Expression>, Vec<Statement>...
impl<T: Exec> Exec for Vec<T> {
fn exec(&self, ctx: &mut Context) -> Type {
for stmt in self {
stmt.exec(ctx);
}
Type::Void
}
}<T: Exec> říká "jakékoliv T které implementuje Exec".
Statement
A jako poslední, implementace pro Statement který stejně jako u `Exp
impl Exec for Statement {
fn exec(&self, ctx: &mut Context) -> Type {
match self {
Statement::Let(definition) => definition.exec(ctx),
Statement::Value(value) => value.exec(ctx),
Statement::Function(function) => function.exec(ctx),
Statement::If(if_statement) => if_statement.exec(ctx),
Statement::While(while_statement) => while_statement.exec(ctx),
Statement::Block(stmts) => {
ctx.add_scope();
stmts.exec(ctx);
ctx.pop_scope();
Type::Void
}
}
}
}Zakončení
V tomto bodě by jste měli mít vše potřebné k spuštění vašeho kódu.
Finální main.rs by měl vypadat takto:
use std::fs::read_to_string;
mod lexer;
mod tokenstream;
mod parser;
mod exec;
use exec::{self, Context, Exec};
use lexer::LexerCursor;
fn main() {
let file = read_to_string("test/hello.js").expect("couldn't read file");
let cursor = LexerCursor::new(&file);
let tokentree = tokenstream::parse_from_tokens(cursor);
let parsed = parser::parse_statements(tokentree);
let mut ctx = Context::default();
ctx.add_scope();
ctx.define_native_func("print".to_string(), |args| {
println!("{:?}", args);
exec::Type::Void
});
parsed.exec(&mut ctx);
}Chcete-li brát jméno souboru ke spuštění, můžete použít std::env::args(), který vrací iterátor stringu. Jako první element je jméno binárky, pro získání druhého můžete použít metodu nth, například let filename = std::env::args().nth(1).expect("no file provided");.
V příští kapitole se podívame jak si program rozšířit, jak se pracuje s pamětí a další.