### Scanner Struct and New Method

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Defines the `Scanner` struct responsible for the tree scanning logic. The `new` method initializes the scanner with a mutable reference to the `Pager` and the starting page index.

```rust
// src/pager.rs

#[derive(Debug)]
pub struct Scanner<'p> {
    pager: &'p mut Pager,
    initial_page: usize,
    page_stack: Vec<PositionedPage>,
}

impl<'p> Scanner<'p> {
    pub fn new(pager: &'p mut Pager, page: usize) -> Scanner<'p> {
        Scanner {
            pager,
            initial_page: page,
            page_stack: Vec::new(),
        }
    }
// ... other methods
```

--------------------------------

### PositionedPage Struct and Methods

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Defines the `PositionedPage` struct to hold a page and the current cell index. Includes methods `next_cell` to iterate through cells and `next_page` to get the rightmost pointer for interior pages.

```rust
#[derive(Debug)]
pub struct PositionedPage {
    pub page: Page,
    pub cell: usize,
}

impl PositionedPage {
    pub fn next_cell(&mut self) -> Option<&Cell> {
        let cell = self.page.get(self.cell);
        self.cell += 1;
        cell
    }

    pub fn next_page(&mut self) -> Option<u32> {
        if self.page.header.page_type == PageType::TableInterior
            && self.cell == self.page.cells.len()
        {
            self.cell += 1;
            self.page.header.rightmost_pointer
        } else {
            None
        }
    }
}
```

--------------------------------

### Scanner next_elem Method

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Determines the next element to process during scanning. It checks for the current page, then tries to get the next page pointer or the next cell. It returns `ScannerElem::Page` for interior nodes or `ScannerElem::Cursor` for leaf nodes.

```rust
fn next_elem(&mut self) -> anyhow::Result<Option<ScannerElem>> {
    let Some(page) = self.current_page()? else {
        return Ok(None);
    };

    if let Some(page) = page.next_page() {
        return Ok(Some(ScannerElem::Page(page)));
    }

    let Some(cell) = page.next_cell() else {
        return Ok(None);
    };

    match cell {
        Cell::TableLeaf(cell) => {
            let header = parse_record_header(&cell.payload)?;
            Ok(Some(ScannerElem::Cursor(Cursor {
                header,
                payload: cell.payload.clone(),
            })))
        }
        Cell::TableInterior(cell) => Ok(Some(ScannerElem::Page(cell.left_child_page))),
    }
}
```

--------------------------------

### Parse Table Interior Cell

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Parses a table interior cell from a buffer. It reads a big-endian double for the left child page pointer and a variable-length integer for the key. Assumes the buffer starts at the cell's data.

```rust
fn parse_table_interior_cell(mut buffer: &[u8]) -> anyhow::Result<page::Cell> {
    let left_child_page = read_be_double_at(buffer, 0);
    buffer = &buffer[4..];

    let (_, key) = read_varint_at(buffer, 0);

    Ok(page::TableInteriorCell {
        left_child_page,
        key,
    }
        .into())
}
```

--------------------------------

### Create and populate a test SQLite database

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part5.md

Use the sqlite3 CLI to create a database file, define a table, and insert sample data for testing query evaluation.

```bash
sqlite3 queries_test.db
sqlite> create table table1(id integer, value text);
sqlite> insert into table1(id, value) values
    ...> (1, '11'),
    ...> (2, '12'),
    ...> (3, '13');
sqlite> .exit
```

--------------------------------

### Running the Rqlite Application

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Execute the rqlite application with release build and specify the test database file. This command is used to demonstrate the functionality after the code changes.

```bash
cargo run --release -- res/test.db
rqlite> .tables
```

--------------------------------

### Bootstrap Rust Project and Add Dependency

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Creates a new Rust project named 'rsqlite' and adds the 'anyhow' crate as a dependency. This sets up the basic project structure for development.

```bash
cargo new rsqlite
cd rsqlite
cargo add anyhow

```

--------------------------------

### Parse Table Leaf Cell

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Parses a table leaf cell from a buffer. It reads a variable-length integer for size and row ID, followed by the payload. Assumes the buffer starts at the cell's data.

```rust
fn parse_table_leaf_cell(mut buffer: &[u8]) -> anyhow::Result<page::Cell> {
    let (n, size) = read_varint_at(buffer, 0);
    buffer = &buffer[n as usize..];

    let (n, row_id) = read_varint_at(buffer, 0);
    buffer = &buffer[n as usize..];

    let payload = buffer[..size as usize].to_vec();

    Ok(page::TableLeafCell {
        size,
        row_id,
        payload,
    }
        .into())
}
```

--------------------------------

### REPL Implementation for rqlite

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Provides the main function and CLI logic for a basic REPL, supporting `.exit` and `.tables` commands. Requires modules for cursor, db, page, pager, and value.

```rust
use std::io::{stdin, BufRead, Write};

use anyhow::Context;

mod cursor;
mod db;
mod page;
mod pager;
mod value;

fn main() -> anyhow::Result<()> {
    let database = db::Db::from_file(std::env::args().nth(1).context("missing db file")?)?;
    cli(database)
}

fn cli(mut db: db::Db) -> anyhow::Result<()> {
    print_flushed("rqlite> ")?;

    let mut line_buffer = String::new();

    while stdin().lock().read_line(&mut line_buffer).is_ok() {
        match line_buffer.trim() {
            ".exit" => break,
            ".tables" => display_tables(&mut db)?,
            _ => {
                println!("Unrecognized command '{}'", line_buffer.trim());
            }
        }

        print_flushed("\nrqlite> ")?;

        line_buffer.clear();
    }

    Ok(())
}

fn display_tables(db: &mut db::Db) -> anyhow::Result<()> {
    let mut scanner = db.scanner(1);

    while let Some(Ok(mut record)) = scanner.next_record() {
        let type_value = record
            .field(0)
            .context("missing type field")
            .context("invalid type field")?;

        if type_value.as_str() == Some("table") {
            let name_value = record
                .field(1)
                .context("missing name field")
                .context("invalid name field")?;

            print!("{} ", name_value.as_str().unwrap());
        }
    }

    Ok(())
}

fn print_flushed(s: &str) -> anyhow::Result<()> {
    print!("{}", s);
    std::io::stdout().flush().context("flush stdout")
}
```

--------------------------------

### Create Minimal Test Database

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Creates a simple SQLite database file named 'minimal_test.db' with two tables, 'table1' and 'table2'. This is used for testing database operations.

```bash
sqlite3 minimal_test.db
sqlite> create table table1(id integer);
sqlite> create table table2(id integer);
sqlite> .exit

```

--------------------------------

### Parsing CREATE TABLE Statements

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

This snippet shows the logic for parsing different statement types, specifically highlighting the handling of `Token::Create` to parse `CREATE TABLE` statements.

```rust
+           Token::Select => self.parse_select().map(Statement::Select),
+           Token::Create => self.parse_create_table().map(Statement::CreateTable),
+           token => bail!("unexpected token: {token:?}"),
+       }
    }
        
    // [...]
```

--------------------------------

### Verify Tables in Test Database

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Verifies the creation of tables in 'minimal_test.db' using the '.tables' command in the SQLite shell. Confirms that 'table1' and 'table2' are present.

```bash
sqlite3 minimal_test.db
sqlite> .tables
table1  table2
sqlite> .exit

```

--------------------------------

### Create 1000 tables in SQLite database

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

This bash script creates a test SQLite database with 1000 tables, each containing a single integer column. This is used to demonstrate the limitations of handling large databases with the previous implementation.

```bash
for i in {1..1000}; do            
    sqlite3 res/test.db "create table table$i(id integer)"
done

cargo run --release -- res/test.db
rqlite> .tables
```

--------------------------------

### Collect Table Metadata in Db::from_file

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

Initializes and collects table metadata when a `Db` instance is created from a file. It uses a `Pager` and `Scanner` to iterate through the schema.

```rust
pub fn from_file(filename: impl AsRef<Path>) -> anyhow::Result<Db> {
    let mut file = std::fs::File::open(filename.as_ref()).context("open db file")?;

    let mut header_buffer = [0; pager::HEADER_SIZE];
    file.read_exact(&mut header_buffer)
        .context("read db header")?;

    let header = pager::parse_header(&header_buffer).context("parse db header")?;

    let tables_metadata = Self::collect_tables_metadata(&mut Pager::new(
        file.try_clone()?,
        header.page_size as usize,
    ))?;

    let pager = Pager::new(file, header.page_size as usize);

    Ok(Db {
        header,
        pager,
        tables_metadata,
    })
}
```

--------------------------------

### Implement Parsing for CREATE TABLE Statement

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

This Rust code implements the `parse_create_table` method within `ParserState`. It handles parsing the table name and its column definitions, expecting specific tokens like CREATE, TABLE, and parentheses.

```rust
// sql/parser.rs

//[...]
impl ParserState {
    // [...]
    fn parse_create_table(&mut self) -> anyhow::Result<CreateTableStatement> {
        self.expect_eq(Token::Create)?;
        self.expect_eq(Token::Table)?;
        let name = self.expect_identifier()?.to_string();
        self.expect_eq(Token::LPar)?;
        let mut columns = vec![self.parse_column_def()?];
        while self.next_token_is(Token::Comma) {
            self.advance();
            columns.push(self.parse_column_def()?);
        }
        self.expect_eq(Token::RPar)?;
        Ok(CreateTableStatement { name, columns })
    }
    // [...]
}
//[...]

```

--------------------------------

### Parse SQL Input to AST

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Takes an input SQL string, tokenizes it, and parses it into an Abstract Syntax Tree (AST). It expects a semicolon at the end of the statement.

```rust
// sql/parser.rs

//...

pub fn parse_statement(input: &str) -> anyhow::Result<Statement> {
    let tokens = tokenizer::tokenize(input)?;
    let mut state = ParserState::new(tokens);
    let statement = state.parse_statement()?;
    state.expect_eq(Token::SemiColon)?;
    Ok(statement)
}
```

--------------------------------

### Implement Pager Read and Load Methods

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part5.md

Updates the `read_page` and `load_page` methods in the Pager struct to handle the new `Arc<Mutex<_>>` and `Arc<RwLock<_>>` fields. The `read_page` method includes logic to acquire read and write locks and re-check the cache after acquiring the write lock.

```rust
impl<I: Read + Seek> Pager<I> {
    // [...] 
    pub fn read_page(&self, n: usize) -> anyhow::Result<Arc<page::Page>> {
        {
            let read_pages = self
                .pages
                .read()
                .map_err(|_| anyhow!("failed to acquire pager read lock"))?;

            if let Some(page) = read_pages.get(&n) {
                return Ok(page.clone());
            }
        }

        let mut write_pages = self
            .pages
            .write()
            .map_err(|_| anyhow!("failed to acquire pager write lock"))?;

        if let Some(page) = write_pages.get(&n) {
            return Ok(page.clone());
        }

        let page = self.load_page(n)?;
        write_pages.insert(n, page.clone());
        Ok(page)
    }

    fn load_page(&self, n: usize) -> anyhow::Result<Arc<page::Page>> {
        let offset = n.saturating_sub(1) * self.page_size;

        let mut input_guard = self
            .input
            .lock()
            .map_err(|_| anyhow!("failed to lock pager mutex"))?;

        input_guard
            .seek(SeekFrom::Start(offset as u64))
            .context("seek to page start")?;

        let mut buffer = vec![0; self.page_size];
        input_guard.read_exact(&mut buffer).context("read page")?;

        Ok(Arc::new(parse_page(&buffer, n)?))
    }
}
```

--------------------------------

### Parsed SQL Query Structure

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Illustrates the Rust structure generated from parsing a simple SQL SELECT query. This shows how the defined AST types represent the query's columns, aliases, and table source.

```rust
Statement::Select(SelectStatement {
core: SelectCore {
result_columns: vec![
    ResultColumn::Expr(ExprResultColumn {
        expr: Expr::Column(Column {
            name: "col1".to_string()
        }),
        alias: Some("first".to_string())
    }),
    ResultColumn::Expr(ExprResultColumn {
        expr: Expr::Column(Column {
            name: "col2".to_string()
        }),
        alias: None
    }),
],
from: SelectFrom::Table("table".to_string()),
},
})
```

--------------------------------

### Update .table Command to Use New Metadata

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

Modifies the `display_tables` function to iterate over the `db.tables_metadata` field instead of scanning the schema table directly. This simplifies table listing.

```rust
fn display_tables(db: &mut db::Db) -> anyhow::Result<()> {
    for table in &db.tables_metadata {
        print!("{} ", &table.name)
    }
    
    Ok(())
}
```

--------------------------------

### Implement SQL Tokenizer

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Implements a function to tokenize an input SQL string into a vector of Token enums. Handles keywords, symbols, whitespace, and identifiers, normalizing identifiers to lowercase.

```rust
use anyhow::bail;

pub fn tokenize(input: &str) -> anyhow::Result<Vec<Token>> {
    let mut tokens = Vec::new();
    let mut chars = input.chars().peekable();

    while let Some(c) = chars.next() {
        match c {
            '*' => tokens.push(Token::Star),
            ',' => tokens.push(Token::Comma),
            ';' => tokens.push(Token::SemiColon),
            c if c.is_whitespace() => continue,
            c if c.is_alphabetic() => {
                let mut ident = c.to_string().to_lowercase();
                while let Some(cc) = chars.next_if(|&cc| cc.is_alphanumeric() || cc == '_') {
                    ident.extend(cc.to_lowercase());
                }

                match ident.as_str() {
                    "select" => tokens.push(Token::Select),
                    "as" => tokens.push(Token::As),
                    "from" => tokens.push(Token::From),
                    _ => tokens.push(Token::Identifier(ident)),
                }
            }
            _ => return Err(anyhow::anyhow!("unexpected character: {}", c)),
        }
    }

    Ok(tokens)
}
```

--------------------------------

### Scanner next_record Method

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Implements the core logic for iterating through records. It uses a loop that calls `next_elem` and handles different `ScannerElem` variants (Cursor, Page, None) to traverse the page tree.

```rust
pub fn next_record(&mut self) -> anyhow::Result<Option<Cursor>> {
    loop {
        match self.next_elem() {
            Ok(Some(ScannerElem::Cursor(cursor))) => return Ok(Some(cursor)),
            Ok(Some(ScannerElem::Page(page_num))) => {
                let new_page = self.pager.read_page(page_num as usize)?.clone();
                self.page_stack.push(PositionedPage {
                    page: new_page,
                    cell: 0,
                });
            }
            Ok(None) if self.page_stack.len() > 1 => {
                self.page_stack.pop();
            }
            Ok(None) => return Ok(None),
            Err(e) => return Err(e),
        }
    }
}
```

--------------------------------

### Define SQL Token Types

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Defines the enumeration for various SQL tokens, including keywords, symbols, and identifiers. Includes a helper method to extract identifier strings.

```rust
#[derive(Debug, Eq, PartialEq)]
pub enum Token {
    Select,
    As,
    From,
    Star,
    Comma,
    SemiColon,
    Identifier(String),
}

impl Token {
    pub fn as_identifier(&self) -> Option<&str> {
        match self {
            Token::Identifier(ident) => Some(ident),
            _ => None,
        }
    }
}
```

--------------------------------

### Pager Implementation in Rust

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

A simple pager implementation that loads and caches pages from an input source. It uses a HashMap to store cached pages and provides a method to read a specific page, loading it if it's not already in the cache.

```rust
// pager.rs
#[derive(Debug, Clone)]
pub struct Pager<I: Read + Seek = std::fs::File> {
    input: I,
    page_size: usize,
    pages: HashMap<usize, page::Page>,
}

impl<I: Read + Seek> Pager<I> {
    pub fn new(input: I, page_size: usize) -> Self {
        Self {
            input,
            page_size,
            pages: HashMap::new(),
        }
    }

    pub fn read_page(&mut self, n: usize) -> anyhow::Result<&page::Page> {
        if self.pages.contains_key(&n) {
            return Ok(self.pages.get(&n).unwrap());
        }

        let page = self.load_page(n)?;
        self.pages.insert(n, page);
        Ok(self.pages.get(&n).unwrap())
    }

    fn load_page(&mut self, n: usize) -> anyhow::Result<page::Page> {
        let offset = n.saturating_sub(1) * self.page_size;

        self.input
            .seek(SeekFrom::Start(offset as u64))
            .context("seek to page start")?;

        let mut buffer = vec![0; self.page_size];
        self.input.read_exact(&mut buffer).context("read page")?;

        parse_page(&buffer, n)
    }
}
```

--------------------------------

### Planner Struct and Compile Method

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part5.md

Defines the Planner struct, responsible for taking a parsed SQL query and producing an executable Operator. The compile method dispatches to specific handlers for different statement types.

```rust
use anyhow::{bail, Context, Ok};

use crate::{
    db::Db,
    sql::ast::{self, SelectFrom},
};

use super::operator::{Operator, SeqScan};

pub struct Planner<'d> {
    db: &'d Db,
}

impl<'d> Planner<'d> {
    pub fn new(db: &'d Db) -> Self {
        Self { db }
    }

    pub fn compile(self, statement: &ast::Statement) -> anyhow::Result<Operator> {
        match statement {
            ast::Statement::Select(s) => self.compile_select(s),
            stmt => bail!("unsupported statement: {:?}", stmt),
        }
    }
}
```

--------------------------------

### Db Struct for Database State

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Defines the `Db` struct to hold the database header and pager, and implements a method to initialize it from a file.

```rust
use std::{io::Read, path::Path};

use anyhow::Context;

use crate::{cursor::Scanner, page::DbHeader, pager, pager::Pager};

pub struct Db {
    pub header: DbHeader,
    pager: Pager,
}

impl Db {
    pub fn from_file(filename: impl AsRef<Path>) -> anyhow::Result<Db> {
        let mut file = std::fs::File::open(filename.as_ref()).context("open db file")?;

        let mut header_buffer = [0; pager::HEADER_SIZE];
        file.read_exact(&mut header_buffer).context("read db header")?;

        let header = pager::parse_header(&header_buffer).context("parse db header")?;

        let pager = Pager::new(file, header.page_size as usize);

        Ok(Db { header, pager })
    }

    pub fn scanner(&mut self, page: usize) -> Scanner {
        Scanner::new(&mut self.pager, page)
    }
}
```

--------------------------------

### Create TableMetadata from Cursor

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

Implements a method to construct `TableMetadata` from a `Cursor` pointing to a schema record. It filters for 'table' types and extracts necessary information.

```rust
impl TableMetadata {
   fn from_cursor(cursor: Cursor) -> anyhow::Result<Option<Self>> {
       let type_value = cursor
           .field(0)
           .context("missing type field")
           .context("invalid type field")?;

       if type_value.as_str() != Some("table") {
           return Ok(None);
       }

       let create_stmt = cursor
           .field(4)
           .context("missing create statement")
           .context("invalid create statement")?
           .as_str()
           .context("table create statement should be a string")?
           .to_owned();

       let create = sql::parse_create_statement(&create_stmt)?;

       let first_page = cursor
           .field(3)
           .context("missing table first page")?
           .as_int()
           .context("table first page should be an integer")? as usize;

       Ok(Some(TableMetadata {
           name: create.name,
           columns: create.columns,
           first_page,
       }))
    }
}
```

--------------------------------

### Update parse_statement to Handle CREATE TABLE

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

This diff shows the modification to the `parse_statement` method in `sql/parser.rs` to incorporate handling for the new `CREATE TABLE` statement type. It also makes the semicolon terminator optional for such statements.

```diff
// sql/parser.rs

//[...]

impl ParserState {
    // [...]
        
    fn parse_statement(&mut self) -> anyhow::Result<Statement> {
-       Ok(ast::Statement::Select(self.parse_select()?))
+       match self.peak_next_token().context("unexpected end of input")? {

```

--------------------------------

### ParserState Struct and Methods

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Defines the ParserState struct to manage the list of tokens and the current position. Includes methods for token inspection, consumption, and error handling.

```rust
// sql/parser.rs

use anyhow::{bail, Context};

use crate::sql::{
    ast::{
        Column,
        Expr,
        ExprResultColumn,
        ResultColumn,
        SelectCore,
        SelectFrom,
        SelectStatement,
        Statement,
    },
    tokenizer::{self, Token},
};

#[derive(Debug)]
struct ParserState {
    tokens: Vec<Token>,
    pos: usize,
}

impl ParserState {
    fn new(tokens: Vec<Token>) -> Self {
        Self { tokens, pos: 0 }
    }

    fn next_token_is(&self, expected: Token) -> bool {
        self.tokens.get(self.pos) == Some(&expected)
    }

    fn expect_identifier(&mut self) -> anyhow::Result<&str> {
        self.expect_matching(|t| matches!(t, Token::Identifier(_)))
            .map(|t| t.as_identifier().unwrap())
    }

    fn expect_eq(&mut self, expected: Token) -> anyhow::Result<&Token> {
        self.expect_matching(|t| *t == expected)
    }

    fn expect_matching(&mut self, f: impl Fn(&Token) -> bool) -> anyhow::Result<&Token> {
        match self.next_token() {
            Some(token) if f(token) => Ok(token),
            Some(token) => bail!("unexpected token: {:?}", token),
            None => bail!("unexpected end of input"),
        }
    }

    fn peak_next_token(&self) -> anyhow::Result<&Token> {
        self.tokens.get(self.pos).context("unexpected end of input")
    }

    fn next_token(&mut self) -> Option<&Token> {
        let token = self.tokens.get(self.pos);
        if token.is_some() {
            self.advance();
        }
        token
    }

    fn advance(&mut self) {
        self.pos += 1;
    }
}
```

--------------------------------

### Integrate SQL Parsing into REPL Loop

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Modify the REPL loop to parse unrecognized commands as SQL statements. This snippet shows the addition of the `sql` module and the new match arm for handling potential SQL statements.

```diff
// src/main.rs

+ mod sql;

//...

fn cli(mut db: db::Db) -> anyhow::Result<()> {
    print_flushed("rqlite> ")?;

    let mut line_buffer = String::new();

    while stdin().lock().read_line(&mut line_buffer).is_ok() {
        match line_buffer.trim() {
            ".exit" => break,
            ".tables" => display_tables(&mut db)?,
+            stmt => match sql::parse_statement(stmt) {
+                Ok(stmt) => {
+                    println!("{:?}", stmt);
+                }
+                Err(e) => {
+                    println!("Error: {}", e);
+                }
+            },
-            _ => {
-               println!("Unrecognized command '{}'", line_buffer.trim());
-           }
        }

        print_flushed("\nrqlite> ")?;

        line_buffer.clear();
    }

    Ok(())
}

//...

```

--------------------------------

### Add New Tokens for CREATE TABLE

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

New tokens CREATE, TABLE, LPar, and RPar are added to the Token enum to support CREATE TABLE statements. This snippet shows the diff for sql/tokenizer.rs.

```diff
// sql/tokenizer.rs

#[derive(Debug, Eq, PartialEq)]
pub enum Token {
+   Create,
+   Table,
    Select,
    As,
    From,
+   LPar,
+   RPar,
    Star,
    Comma,
    SemiColon,
    Identifier(String),
}

//[...]

pub fn tokenize(input: &str) -> anyhow::Result<Vec<Token>> {
    let mut tokens = Vec::new();
    let mut chars = input.chars().peekable();

    while let Some(c) = chars.next() {
        match c {
+           '(' => tokens.push(Token::LPar),
+           ')' => tokens.push(Token::RPar),
            '*' => tokens.push(Token::Star),
            ',' => tokens.push(Token::Comma),
            ';' => tokens.push(Token::SemiColon),
            c if c.is_whitespace() => continue,
            c if c.is_alphabetic() => {
                let mut ident = c.to_string().to_lowercase();
                while let Some(cc) = chars.next_if(|&cc| cc.is_alphanumeric() || cc == '_') {
                    ident.extend(cc.to_lowercase());
                }

                match ident.as_str() {
+                   "create" => tokens.push(Token::Create),
+                   "table" => tokens.push(Token::Table),
                    "select" => tokens.push(Token::Select),
                    "as" => tokens.push(Token::As),
                    "from" => tokens.push(Token::From),
                    _ => tokens.push(Token::Identifier(ident)),
                }
            }
            _ => bail!("unexpected character: {}", c),
        }
    }

    Ok(tokens)
}

```

--------------------------------

### Rust Function to Evaluate SQL Query

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part5.md

This Rust function parses a SQL query, plans its execution using a Planner, and iterates through the resulting rows, printing each one. It's used within the REPL to execute user-provided SQL statements.

```rust
// src/main.rs

// [...]

fn eval_query(db: &db::Db, query: &str) -> anyhow::Result<()> {
    let parsed_query = sql::parse_statement(query, false)?;
    let mut op = engine::plan::Planner::new(db).compile(&parsed_query)?;

    while let Some(values) = op.next_row()? {
        let formated = values
            .iter()
            .map(ToString::to_string)
            .collect::<Vec<_>>()
            .join("|");

        println!("{formated}");
    }

    Ok(())
}
```

--------------------------------

### Update AST for CreateTableStatement

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

The Abstract Syntax Tree (AST) is extended to represent the new CreateTableStatement. This snippet shows the diff for sql/ast.rs.

```diff
// sql/ast.rs

//[...]

#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Statement {
    Select(SelectStatement),
+   CreateTable(CreateTableStatement),
}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
pub struct CreateTableStatement {
+   pub name: String,
+   pub columns: Vec<ColumnDef>,
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
pub struct ColumnDef {
+   pub name: String,
+   pub col_type: Type,
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Type {
+   Integer,
+   Real,
+   Text,
+   Blob,
+}

//[...]

```

--------------------------------

### Scanner for RQLite Pages

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Implements a Scanner struct to iterate over records within a specific page of a RQLite database. Requires a mutable Pager reference and the page number.

```rust
// src/cursor.rs
#[derive(Debug)]
pub struct Scanner<'p> {
    pager: &'p mut Pager,
    page: usize,
    cell: usize,
}

impl<'p> Scanner<'p> {
    pub fn new(pager: &'p mut Pager, page: usize) -> Scanner<'p> {
        Scanner {
            pager,
            page,
            cell: 0,
        }
    }
    pub fn next_record(&mut self) -> Option<anyhow::Result<Cursor>> {
        let page = match self.pager.read_page(self.page) {
            Ok(page) => page,
            Err(e) => return Some(Err(e)),
        };

        match page {
            Page::TableLeaf(leaf) => {
                let cell = leaf.cells.get(self.cell)?;

                let header = match parse_record_header(&cell.payload) {
                    Ok(header) => header,
                    Err(e) => return Some(Err(e)),
                };

                let record = Cursor {
                    header,
                    pager: self.pager,
                    page_index: self.page,
                    page_cell: self.cell,
                };

                self.cell += 1;

                Some(Ok(record))
            }
        }
    }
}
```

--------------------------------

### Scanner current_page Method

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Manages the current page being processed. If the `page_stack` is empty, it reads the initial page from the pager and pushes it onto the stack. Returns a mutable reference to the current `PositionedPage`.

```rust
fn current_page(&mut self) -> anyhow::Result<Option<&mut PositionedPage>> {
    if self.page_stack.is_empty() {
        let page = match self.pager.read_page(self.initial_page) {
            Ok(page) => page.clone(),
            Err(e) => return Err(e),
        };

        self.page_stack.push(PositionedPage { page, cell: 0 });
    }

    Ok(self.page_stack.last_mut())
}
```

--------------------------------

### Rust Cursor for Accessing Record Fields

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Implements a Cursor struct to navigate RQLite database records and provides a `field` method to retrieve the decoded value of a specific record field.

```rust
// src/cursor.rs
#[derive(Debug)]
pub struct Cursor<'p> {
    header: RecordHeader,
    pager: &'p mut Pager,
    page_index: usize,
    page_cell: usize,
}

impl<'p> Cursor<'p> {
    pub fn field(&mut self, n: usize) -> Option<Value> {
        let record_field = self.header.fields.get(n)?;

        let payload = match self.pager.read_page(self.page_index) {
            Ok(Page::TableLeaf(leaf)) => &leaf.cells[self.page_cell].payload,
            _ => return None,
        };

        match record_field.field_type {
            RecordFieldType::Null => Some(Value::Null),
            RecordFieldType::I8 => Some(Value::Int(read_i8_at(payload, record_field.offset))),
            RecordFieldType::I16 => Some(Value::Int(read_i16_at(payload, record_field.offset))),
            RecordFieldType::I24 => Some(Value::Int(read_i24_at(payload, record_field.offset))),
            RecordFieldType::I32 => Some(Value::Int(read_i32_at(payload, record_field.offset))),
            RecordFieldType::I48 => Some(Value::Int(read_i48_at(payload, record_field.offset))),
            RecordFieldType::I64 => Some(Value::Int(read_i64_at(payload, record_field.offset))),
            RecordFieldType::Float => Some(Value::Float(read_f64_at(payload, record_field.offset))),

```

--------------------------------

### Define TableMetadata Struct

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

Defines the structure to hold table name, column definitions, and the first page number. Used to represent metadata for each table.

```rust
#[derive(Debug, Clone)]
pub struct TableMetadata {
    pub name: String,
    pub columns: Vec<ast::ColumnDef>,
    pub first_page: usize,
}
```

--------------------------------

### Implement Parsing for Column Definitions and Types

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

This Rust code implements methods to parse column definitions and SQL types within the ParserState. It handles mapping type names to the AST's Type enum.

```rust
// sql/parser.rs

//[...]
impl ParserState {
    // [...]
    fn parse_column_def(&mut self) -> anyhow::Result<ColumnDef> {
        Ok(ColumnDef {
            name: self.expect_identifier()?.to_string(),
            col_type: self.parse_type()?,
        })
    }

    fn parse_type(&mut self) -> anyhow::Result<Type> {
        let type_name = self.expect_identifier()?;
        let t = match type_name.to_lowercase().as_str() {
            "integer" => Type::Integer,
            "real" => Type::Real,
            "blob" => Type::Blob,
            "text" | "string" => Type::Text,
            _ => bail!("unsupported type: {type_name}"),
        };
        Ok(t)
    }
    // [...]
}

//[...]

```

--------------------------------

### Parse SQLite Database Header

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Implements a function to parse the SQLite database header from a byte buffer. It validates the header prefix and extracts the page size, ensuring it's a power of 2.

```rust
// src/pager.rs
pub const HEADER_SIZE: usize = 100;
const HEADER_PREFIX: &[u8] = b"SQLite format 3\0";
const HEADER_PAGE_SIZE_OFFSET: usize = 16;

const PAGE_MAX_SIZE: u32 = 65536;

pub fn parse_header(buffer: &[u8]) -> anyhow::Result<page::DbHeader> {
    if !buffer.starts_with(HEADER_PREFIX) {
        let prefix = String::from_utf8_lossy(&buffer[..HEADER_PREFIX.len()]);
        anyhow::bail!("invalid header prefix: {prefix}");
    }

    let page_size_raw = read_be_word_at(buffer, HEADER_PAGE_SIZE_OFFSET);
    let page_size = match page_size_raw {
        1 => PAGE_MAX_SIZE,
        n if ((n & (n - 1)) == 0) && n != 0 => n as u32,
        _ => anyhow::bail!("page size is not a power of 2: {}", page_size_raw),
    };

    Ok(page::Header { page_size })
}

fn read_be_word_at(input: &[u8], offset: usize) -> u16 {
    u16::from_be_bytes(input[offset..offset + 2].try_into().unwrap())
}

```

--------------------------------

### Implement Db::collect_tables_metadata

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

Iterates through the schema table using a `Scanner` and collects `TableMetadata` for each table record found. Returns a `Vec<TableMetadata>`.

```rust
fn collect_tables_metadata(pager: &mut Pager) -> anyhow::Result<Vec<TableMetadata>> {
    let mut metadata = Vec::new();
    let mut scanner = Scanner::new(pager, 1);

    while let Some(record) = scanner.next_record()? {
        if let Some(m) = TableMetadata::from_cursor(record)? {
            metadata.push(m);
        }
    }

    Ok(metadata)
}
```

--------------------------------

### New parse_create_statement Function

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

Introduces the `parse_create_statement` function, which utilizes `parse_statement` to specifically extract and return `CreateTableStatement` objects, returning an error if a different statement type is encountered.

```rust
+pub fn parse_create_statement(
+    input: &str,
+) -> anyhow::Result<CreateTableStatement> {
+    match parse_statement(input, false)? {
+        Statement::CreateTable(c) => Ok(c),
+        Statement::Select(_) => bail!("expected a create statement"),
+    }
+}
```

--------------------------------

### Compile SELECT Statement Implementation

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part5.md

Implements the logic to compile a SELECT statement into a SeqScan Operator. It finds the table metadata, determines the required columns, and creates the SeqScan.

```rust
use anyhow::{bail, Context, Ok};

use crate::{
    db::Db,
    sql::ast::{self, SelectFrom},
};

use super::operator::{Operator, SeqScan};

impl<'d> Planner<'d> {
    // [...] 

    fn compile_select(self, select: &ast::SelectStatement) -> anyhow::Result<Operator> {
        let SelectFrom::Table(table_name) = &select.core.from;

        let table = self
            .db
            .tables_metadata
            .iter()
            .find(|m| &m.name == table_name)
            .with_context(|| format!("invalid table name: {table_name}"))?;

        let mut columns = Vec::new();

        for res_col in &select.core.result_columns {
            match res_col {
                ast::ResultColumn::Star => {
                    for i in 0..table.columns.len() {
                        columns.push(i);
                    }
                }
                ast::ResultColumn::Expr(e) => {
                    let ast::Expr::Column(col) = &e.expr;
                    let (index, _) = table
                        .columns
                        .iter()
                        .enumerate()
                        .find(|(_, c)| c.name == col.name)
                        .with_context(|| format!("invalid column name: {}", col.name))?;
                    columns.push(index);
                }
            }
        }

        Ok(Operator::SeqScan(SeqScan::new(
            columns,
            self.db.scanner(table.first_page),
        )))
    }
}
```

--------------------------------

### Rust Function to Parse a Generic Page

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Parses a generic page from a buffer, determining the page type and delegating to specific parsing functions. It handles the offset for the first page which contains the database header.

```rust
fn parse_page(buffer: &[u8], page_num: usize) -> anyhow::Result<page::Page> {
    let ptr_offset = if page_num == 1 { HEADER_SIZE as u16 } else { 0 };

    match buffer[0] {
        PAGE_LEAF_TABLE_ID => parse_table_leaf_page(buffer, ptr_offset),
        _ => Err(anyhow::anyhow!("unknown page type: {}", buffer[0])),
    }
}
```

--------------------------------

### Parse SELECT Statement

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Parses a complete SELECT statement, including result columns and the FROM clause. It expects specific tokens like 'SELECT' and 'FROM'.

```rust
// sql/parser.rs

impl ParserState {
    //...
    fn parse_statement(&mut self) -> anyhow::Result<Statement> {
        Ok(Statement::Select(self.parse_select()?))
    }

    fn parse_select(&mut self) -> anyhow::Result<SelectStatement> {
        self.expect_eq(Token::Select)?;
        let result_columns = self.parse_result_columns()?;
        self.expect_eq(Token::From)?;
        let from = self.parse_select_from()?;
        Ok(SelectStatement {
            core: SelectCore {
                result_columns,
                from,
            },
        })
    }

    fn parse_select_from(&mut self) -> anyhow::Result<SelectFrom> {
        let table = self.expect_identifier()?;
        Ok(SelectFrom::Table(table.to_string()))
    }
    //...
}
```

--------------------------------

### Rust AST for SQL Statements

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part3.md

Defines the Rust data structures for representing SQL statements, including SELECT statements, result columns, expressions, and table references. These structures form the basis for parsing and manipulating SQL queries within the application.

```rust
#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Statement {
    Select(SelectStatement),
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct SelectStatement {
    pub core: SelectCore,
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct SelectCore {
    pub result_columns: Vec<ResultColumn>,
    pub from: SelectFrom,
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub enum ResultColumn {
    Star,
    Expr(ExprResultColumn),
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct ExprResultColumn {
    pub expr: Expr,
    pub alias: Option<String>,
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Expr {
    Column(Column),
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Column {
    pub name: String,
}

#[derive(Debug, Clone, Eq, PartialEq)]
pub enum SelectFrom {
    Table(String),
}
```

--------------------------------

### SeqScan Struct and Implementation

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part5.md

Implements the SeqScan struct for scanning a table and yielding its rows. It's initialized with field indices and a Scanner, and provides a next_row method to retrieve data.

```rust
use anyhow::Context;

use crate::{cursor::Scanner, value::OwnedValue};

#[derive(Debug)]
pub struct SeqScan {
    fields: Vec<usize>,
    scanner: Scanner,
    row_buffer: Vec<OwnedValue>,
}

impl SeqScan {
    pub fn new(fields: Vec<usize>, scanner: Scanner) -> Self {
        let row_buffer = vec![OwnedValue::Null; fields.len()];

        Self {
            fields,
            scanner,
            row_buffer,
        }
    }

    fn next_row(&mut self) -> anyhow::Result<Option<&[OwnedValue]>> {
        let Some(record) = self.scanner.next_record()? else {
            return Ok(None);
        };

        for (i, &n) in self.fields.iter().enumerate() {
            self.row_buffer[i] = record.owned_field(n).context("missing record field")?;
        }

        Ok(Some(&self.row_buffer))
    }
}
```

--------------------------------

### Update display_tables Function Signature

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Modify the `display_tables` function to correctly handle the updated `next_record` signature, ensuring tables spanning multiple pages are processed. This change is necessary for the scanning logic to function with interior pages.

```diff
fn display_tables(db: &mut db::Db) -> anyhow::Result<()> {
    let mut scanner = db.scanner(1);

-   while let Some(Ok(mut record)) = scanner.next_record() {
+   while let Some(mut record) = scanner.next_record()? {
        let type_value = record
            .field(0)
            .context("missing type field")
            .context("invalid type field")?;

        if type_value.as_str() == Some("table") {
            let name_value = record
                .field(1)
                .context("missing name field")
                .context("invalid name field")?;

            print!("{} ", name_value.as_str().unwrap());
        }
    }

    Ok(())
}
```

--------------------------------

### Add Table Metadata Field to Db Struct

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part4.md

Adds a `tables_metadata` field to the `Db` struct to store the collected metadata for all tables.

```rust
pub struct Db {
    pub header: DbHeader,
    pub tables_metadata: Vec<TableMetadata>,
    pager: Pager,
}
```

--------------------------------

### Define SQLite Database Header Structure

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Defines the `DbHeader` struct in Rust to hold the page size of an SQLite database. This struct is part of the page parsing logic.

```rust
// src/page.rs
#[derive(Debug, Copy, Clone)]
pub struct DbHeader {
    pub page_size: u32,
}

```

--------------------------------

### Consolidate Page and Cell Structures

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Refactors the Page struct to be generic and introduces a Cell enum to handle both leaf and interior cell types.

```diff
// src/page.rs

#[derive(Debug, Clone)]
- pub struct TableLeafPage {
+ pub struct Page {
    pub header: PageHeader,
    pub cell_pointers: Vec<u16>,
-   pub cells: Vec<TableLeafCell>,
+   pub cells: Vec<Cell>,
}

- #[derive(Debug, Clone)]
- pub enum Page {
-   TableLeaf(TableLeafPage),
- }

+ #[derive(Debug, Clone)]
+ pub enum Cell {
+    TableLeaf(TableLeafCell),
+    TableInterior(TableInteriorCell),
+ }

+ impl From<TableLeafCell> for Cell {
+    fn from(cell: TableLeafCell) -> Self {
+        Cell::TableLeaf(cell)
+    }
+ }

+ impl From<TableInteriorCell> for Cell {
+    fn from(cell: TableInteriorCell) -> Self {
+        Cell::TableInterior(cell)
+    }
+ }

+ pub struct TableInteriorCell {
+    pub left_child_page: u32,
+    pub key: i64,
+ }

```

--------------------------------

### ScannerElem Enum

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part2.md

Defines the `ScannerElem` enum used by `next_elem` to represent either a page number to visit or a cursor for a record.

```rust
@derive(Debug)
enum ScannerElem {
    Page(u32),
    Cursor(Cursor),
}
```

--------------------------------

### Rust Enum for Record Field Types

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part1.md

Defines the possible data types for fields within an RQLite record, based on the SQLite record format.

```rust
// src/cursor.rs
#[derive(Debug, Copy, Clone)]
pub enum RecordFieldType {
    Null,
    I8,
    I16,
    I24,
    I32,
    I48,
    I64,
    Float,
    Zero,
    One,
    String,
    Blob,
}

#[derive(Debug, Clone)]
pub struct RecordField {
    pub offset: usize,
    pub field_type: RecordFieldType,
}

#[derive(Debug, Clone)]
pub struct RecordHeader {
    pub fields: Vec<RecordField>,
}

```

--------------------------------

### Modify Pager Struct for Shareability

Source: https://github.com/geoffreycopin/rqlite/blob/master/blog/part5.md

Updates the Pager struct to use Arc<Mutex<_>> for input and Arc<RwLock<_>> for pages, enabling shareable access. This change is necessary for supporting concurrent access and cloning the pager.

```diff
// src/pager.rs

- #[derive(Debug, Clone)]
+ #[derive(Debug)]
pub struct Pager<I: Read + Seek = std::fs::File> {
-   input: I,
+   input: Arc<Mutex<I>>
    page_size: usize,
-   pages: HashMap<usize, page::Page>,
+   pages: Arc<RwLock<HashMap<usize, Arc<page::Page>>>>,
}
```