DEV Community: geoffreycopin

Build your own SQLite, Part 2: Scanning large tables

geoffreycopin — Sat, 24 Aug 2024 15:06:33 +0000

In the previous post, we discovered the SQLite file format and implemented a toy version
of the .tables command, allowing us to display the list of tables in a database.
But our implementation has a jarring limitation: it assumes that all the data fits into the first
page of the file. In this post, we'll discover how SQLite represents tables that are too large to fit
into a single page, this will make our .tables command more useful, but also lay the groundwork for
our query engine.

Erratum

If you're one of the early readers of the first post, and you coded along, a small mistake might
have slipped into your code: in the load_page method of the Pager struct, there is
no need to add HEADER_SIZE to the offset parameter. Here is the beginning of the corrected version:

// src/pager.rs

fn load_page(&mut self, n: usize) -> anyhow::Result<page::Page> {
-   let offset = HEADER_SIZE + n.saturating_sub(1) * self.page_size;
+   let offset = n.saturating_sub(1) * self.page_size;
    // the rest of the method stays the same
    // [...] 
}

A motivating example

Let's begin our journey with a much larger test database:

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

Without much surprise, our small program isn't able to display the list of tables.
The reason for that is quite simple: database pages are typically 4096 bytes long, which
is far from enough to store 1000 tables.
But why did our code fail, instead of displaying the first records that fit into the first page?

B-tree interior pages

When a table is too large to fit into a single page, SQLite splits it into multiple pages, of
different types:

leaf pages, that contains the actual records
interior pages, that store information about which page contains the records for which table.

Interior tables have the same high-level structure as leaf pages, with two key differences:

instead of storing record, they store a tuple (child_page_number, key) where child_page_number is a 32 bits unsigned integer representing the page number of the "root" page of a subtree that contains records with keys lower or equal to key. Cells in interior pages are logically ordered by key in ascending order.
the header contains an extra field, the "rightmost pointer", which is the page number of the "root" of the subtree that contains records with keys greater than the largest key in the page.

With this new knowledge, we can update our page data structure. We'll start by adding
the new optional rightmost_pointer field to the page header. We'll also add a byte_size
method that returns the size of the header, depending on wheter the rightmost_pointer field is set or not,
and add a new variant to our PageType enum to represent interior pages.

// src/page.rs

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub enum PageType {
    TableLeaf,
+   TableInterior,
}

#[derive(Debug, Copy, Clone)]
pub struct PageHeader {
    pub page_type: PageType,
    pub first_freeblock: u16,
    pub cell_count: u16,
    pub cell_content_offset: u32,
    pub fragmented_bytes_count: u8,
+   pub rightmost_pointer: Option<u32>,
}

+impl PageHeader {
+    pub fn byte_size(&self) -> usize {
+        if self.rightmost_pointer.is_some() {
+            12
+        } else {
+            8
+        }
+    }
+}

Let's modify the parsing function to take the new field into account:

// src/pager.rs

+ const PAGE_LEAF_TABLE_ID: u8 = 0x0d;
+ const PAGE_INTERIOR_TABLE_ID: u8 = 0x05;

fn parse_page_header(buffer: &[u8]) -> anyhow::Result<page::PageHeader> {
-   let page_type = match buffer[0] {
-      0x0d => page::PageType::TableLeaf,
+   let (page_type, has_rightmost_ptr) = match buffer[0] {
+       PAGE_LEAF_TABLE_ID => (page::PageType::TableLeaf, false),
+       PAGE_INTERIOR_TABLE_ID => (page::PageType::TableInterior, true),
        _ => anyhow::bail!("unknown page type: {}", buffer[0]),
    };

    let first_freeblock = read_be_word_at(buffer, PAGE_FIRST_FREEBLOCK_OFFSET);
    let cell_count = read_be_word_at(buffer, PAGE_CELL_COUNT_OFFSET);
    let cell_content_offset = match read_be_word_at(buffer, PAGE_CELL_CONTENT_OFFSET) {
        0 => 65536,
        n => n as u32,
    };
    let fragmented_bytes_count = buffer[PAGE_FRAGMENTED_BYTES_COUNT_OFFSET];

+   let rightmost_pointer = if has_rightmost_ptr {
+       Some(read_be_double_at(buffer, PAGE_RIGHTMOST_POINTER_OFFSET))
+   } else {
+       None
+   };

    Ok(page::PageHeader {
        page_type,
        first_freeblock,
        cell_count,
        cell_content_offset,
        fragmented_bytes_count,
+       rightmost_pointer,
    })
}

We decide whether to parse the rightmost_pointer field depending on the value of the page_type
byte (0x0d for leaf pages, 0x05 for interior pages).

Next, we'll update the Page struct to reflect the fact that both leaf and interior pages
share the same structure, with the only difference being the content of the cells:

// 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,
+ }

This change calls for a major update of our parsing functions, reproduced below:

// src/pager.rs

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 };
    let content_buffer = &buffer[ptr_offset as usize..];
    let header = parse_page_header(content_buffer)?;
    let cell_pointers = parse_cell_pointers(
        &content_buffer[header.byte_size()..],
        header.cell_count as usize,
        ptr_offset,
    );

    let cells_parsing_fn = match header.page_type {
        page::PageType::TableLeaf => parse_table_leaf_cell,
        page::PageType::TableInterior => parse_table_interior_cell,
    };

    let cells = parse_cells(content_buffer, &cell_pointers, cells_parsing_fn)?;

    Ok(page::Page {
        header,
        cell_pointers,
        cells,
    })
}

fn parse_cells(
    buffer: &[u8],
    cell_pointers: &[u16],
    parse_fn: impl Fn(&[u8]) -> anyhow::Result<page::Cell>,
) -> anyhow::Result<Vec<page::Cell>> {
    cell_pointers
        .iter()
        .map(|&ptr| parse_fn(&buffer[ptr as usize..]))
        .collect()
}

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())
}

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())
}

Scanning logic

Our scanning logic will need to be updated to handle interior pages. We can no longer
simply iterate over the cells of a page and call it a day. Instead, we'll need to
implement a depth-first algorithm that recursively explores the tree, starting from
the root page.

To make our task easier, let's introduce a new PositionedPage struct that
stores a page, along with the index of the current cell we're looking at:

// src/pager.rs

#[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
        }
    }
}

The next_cell method returns the content of the current cell and increments the cell index,
so calling it repeatedly will yiels the content of all the cells in the page.

The next_page method is a bit more complex: it returns the rightmost_pointer of the current
page if it's an interior page and we just visited the last cell, otherwise it
it returns None.

We'll also update our Cursor so that it owns it's payload instead of borrowing it through a Pager:

// src/pager.rs

#[derive(Debug)]
- pub struct Cursor<'p> { 
+ pub struct Cursor {
    header: RecordHeader,
-   pager: &'p mut Pager,
-   page_index: usize,
-   page_cell: usize,
+    payload: Vec<u8>,
}

This change will allow us to avoid borrowing the Pager mutably from the
Cursor and the Scanner at the same time, which would lead to a
difficult-to-solve lifetime issue.

With that out of the way, we can focus on the tree scanning logic.
We'll maintain a stack of PositionedPage to keep track of the parent
pages we've visited.
At every step of the walk, there are a few cases to consider:

if the current page is a leaf page and we haven't visited all the cells yet, we'll just have to build a Cursor with the current cell's payload and return it.
if the current page is an interior page, we'll push the next page (either from the current cell or the rightmost pointer) to the stack and continue the walk.
if we've visited all the cells of the current page, we'll pop the stack and continue the walk from the parent page.

This logic is implemented in the new Scanner struct:

// 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(),
        }
    }

    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),
            }
        }
    }

    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))),
        }
    }

    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())
    }
}

#[derive(Debug)]
enum ScannerElem {
    Page(u32),
    Cursor(Cursor),
}

Putting it all together

The only change that remains to be made is to update the display_tables function
to account for the change in next_record signature:

// src/main.rs

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(())
}

We can now display our (long!) list of tables:

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

Conclusion

Our scanning logic is now able to handle tables that span multiple pages, thanks to the introduction
of interior pages. This is a major milestone in our journey to build a fully functional
database! In the next post, we'll learn how to parse simple SQL queries and will lay
the groundwork for our query engine.

Build your own SQLite, Part 1: Listing tables

geoffreycopin — Tue, 23 Jul 2024 22:01:35 +0000

As developers, we use databases all the time. But how do they work? In this series, we'll try to answer that question by building our own SQLite-compatible database from scratch.

Source code examples will be provided in Rust, but you are encouraged to follow along using your language of choice, as we won't be relying on many language-specific features or libraries.

As an introduction, we'll implement the simplest version of the tables command, which lists the names of all the tables in a database. While this looks simple, we'll see that it requires us to make our first deep dive into the SQLite file format.

The complete source code is available on Github.

Building the test database

To keep things as simple as possible, let's build a minimalistic test database:

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

This creates a database with two tables, table1 and table2, each with a single column, id. We can verify this by running the tables command in the SQLite shell:

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

Bootstrapping the project

Let's start by creating a new Rust project. We'll use the cargo add to add our only dependency for now, anyhow:

cargo new rsqlite
cd rsqlite
cargo add anyhow

The SQLite file format

SQLite databases are stored in a single file, the format of which is documented in the SQLite File Format Specification. The file is divided into pages, with each page having the same size: a power of 2, between 512 and 65536 bytes. The first 100 bytes of the first page contain the database header, which includes information such as the page size and the file format version. In this first part, we'll only be interested in the page size. Pages can be of different types, but for this first article, we'll only be interested in table btree leaf pages, which store the actual table data.

Our first task will be to implement a Pager struct that reads and caches pages from the database file. But before we do, we'll have to read the page size from the database header. Let's start by defining our Header struct:

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

The header starts with the magic string SQLite format 3\0, followed by the page size encoded as a big-endian 2-byte integer at offset 16. With this information, we can implement a function that reads the header from a buffer:

// 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())
}

Two things to note here:

As the maximum page size cannot be represented as a 2-byte integer, a page size of 1 is use to represent the maximum page size.
We use a somewhat convoluted expression to check if the page size is a power of 2. The expression n & (n - 1) == 0 is true if and only if n is a power of 2, except for n = 0.

Want to support me?

Checkout my latest project: zenyth.dev

Decoding Table B-tree leaf pages

Now that we have the minimum information we need to read pages from the disk, let's explore the content of a table btree-leaf page. table btree-leaf pages start with an 8-byte header, followed by an sequence of "cell pointers" containing the offset of every cell in the page. The cells contain the table data, and we can think of them as key-value pairs, where the key is a 64-bits integer encoded as a varint (the rowid) and the value is an arbitrary sequence of bytes representing the row data. The header contains the following fields:

page_type: byte representing the page type. For table btree-leaf pages, this is 0x0D.
first_freeblock: 2-byte integer representing the offset of the first free block in the page, or zero if there is no freeblock.
cell_count: 2-byte integer representing the number of cells in the page.
cell_content_offset: 2-byte integer representing the offset of the first cell.
fragmented_bytes_count: 1-byte integer representing the number of fragmented free bytes in the page (we won't make use of it for now).

We'll start by defining a Page enum representing a parsed page, along with the necessary structs to represent the page header and the cell pointers:

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

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

#[derive(Debug, Copy, Clone)]
pub struct PageHeader {
    pub page_type: PageType,
    pub first_freeblock: u16,
    pub cell_count: u16,
    pub cell_content_offset: u32,
    pub fragmented_bytes_count: u8,
}

#[derive(Debug, Copy, Clone)]
pub enum PageType {
    TableLeaf,
}

#[derive(Debug, Clone)]
pub struct TableLeafCell {
    pub size: i64,
    pub row_id: i64,
    pub payload: Vec<u8>,
}

The corresponding parsing functions are quite straightforward. Note the offset handling in parse_page: since the first page contains the database header, we start parsing the page at offset 100.

/// pager.rs
const PAGE_LEAF_HEADER_SIZE: usize = 8;
const PAGE_FIRST_FREEBLOCK_OFFSET: usize = 1;
const PAGE_CELL_COUNT_OFFSET: usize = 3;
const PAGE_CELL_CONTENT_OFFSET: usize = 5;
const PAGE_FRAGMENTED_BYTES_COUNT_OFFSET: usize = 7;

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])),
    }
}

fn parse_table_leaf_page(buffer: &[u8], ptr_offset: u16) -> anyhow::Result<page::Page> {
    let header = parse_page_header(buffer)?;

    let content_buffer = &buffer[PAGE_LEAF_HEADER_SIZE..];
    let cell_pointers = parse_cell_pointers(content_buffer, header.cell_count as usize, ptr_offset);

    let cells = cell_pointers
        .iter()
        .map(|&ptr| parse_table_leaf_cell(&buffer[ptr as usize..]))
        .collect::<anyhow::Result<Vec<page::TableLeafCell>>>()?;

    Ok(page::Page::TableLeaf(page::TableLeafPage {
        header,
        cell_pointers,
        cells,
    }))
}


fn parse_page_header(buffer: &[u8]) -> anyhow::Result<page::PageHeader> {
    let page_type = match buffer[0] {
        0x0d => page::PageType::TableLeaf,
        _ => anyhow::bail!("unknown page type: {}", buffer[0]),
    };

    let first_freeblock = read_be_word_at(buffer, PAGE_FIRST_FREEBLOCK_OFFSET);
    let cell_count = read_be_word_at(buffer, PAGE_CELL_COUNT_OFFSET);
    let cell_content_offset = match read_be_word_at(buffer, PAGE_CELL_CONTENT_OFFSET) {
        0 => 65536,
        n => n as u32,
    };
    let fragmented_bytes_count = buffer[PAGE_FRAGMENTED_BYTES_COUNT_OFFSET];

    Ok(page::PageHeader {
        page_type,
        first_freeblock,
        cell_count,
        cell_content_offset,
        fragmented_bytes_count,
    })
}


fn parse_cell_pointers(buffer: &[u8], n: usize, ptr_offset: u16) -> Vec<u16> {
    let mut pointers = Vec::with_capacity(n);
    for i in 0..n {
        pointers.push(read_be_word_at(buffer, 2 * i) - ptr_offset);
    }
    pointers
}

fn parse_table_leaf_cell(mut buffer: &[u8]) -> anyhow::Result<page::TableLeafCell> {
    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,
    })
}

fn read_varint_at(buffer: &[u8], mut offset: usize) -> (u8, i64) {
    let mut size = 0;
    let mut result = 0;

    while size < 8 && buffer[offset] >= 0b1000_0000 {
        result |= ((buffer[offset] as i64) & 0b0111_1111) << (7 * size);
        offset += 1;
        size += 1;
    }

    result |= (buffer[offset] as i64) << (7 * size);

    (size + 1, result)
}

To read a varint, we copy the 7 least significant bits of each byte to the result, as long as the most significant bit is set. As the maximum length of a varint is 9 bytes, we stop after reading 8 bytes to avoid potential overflows.

We can finally implement the pager itself. For now, it only loads and caches pages without any eviction policy:

// 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 = HEADER_SIZE + 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)
    }
}

Records

We now have a way to read pages, and to access the pages cells. But how to decode the values of the cells? Each cell contains the value of a row in the table, encoded using the SQLite record format. The record format is quite simple: a record consists of a header, followed by a sequence of field values. The header starts with a varint representing the byte size of the headerm followed by a sequence of varints -one per column- determining the type of each column according to the following table:

0: NULL
1: 8-bits signed integer
2: 16-bits signed integer
3: 24-bits signed integer
4: 32-bits signed integer
5: 48-bits signed integer
6: 64-bits signed integer
7: 64-bits IEEE floating point number
8: value is the integer 0
9: value is the integer 1
10 & 11: reserved for internal use
n with n even and n > 12: BLOB of size (n - 12) / 2
n with n odd and n > 13: text of size (n - 13) / 2

We now have all the informations we need to parse and represent record's headers:

// 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>,
}

fn parse_record_header(mut buffer: &[u8]) -> anyhow::Result<RecordHeader> {
    let (varint_size, header_length) = crate::pager::read_varint_at(buffer, 0);
    buffer = &buffer[varint_size as usize..header_length as usize];

    let mut fields = Vec::new();
    let mut current_offset = header_length as usize;

    while !buffer.is_empty() {
        let (discriminant_size, discriminant) = crate::pager::read_varint_at(buffer, 0);
        buffer = &buffer[discriminant_size as usize..];

        let (field_type, field_size) = match discriminant {
            0 => (RecordFieldType::Null, 0),
            1 => (RecordFieldType::I8, 1),
            2 => (RecordFieldType::I16, 2),
            3 => (RecordFieldType::I24, 3),
            4 => (RecordFieldType::I32, 4),
            5 => (RecordFieldType::I48, 6),
            6 => (RecordFieldType::I64, 8),
            7 => (RecordFieldType::Float, 8),
            8 => (RecordFieldType::Zero, 0),
            9 => (RecordFieldType::One, 0),
            n if n >= 12 && n % 2 == 0 => {
                let size = ((n - 12) / 2) as usize;
                (RecordFieldType::Blob(size), size)
            }
            n if n >= 13 && n % 2 == 1 => {
                let size = ((n - 13) / 2) as usize;
                (RecordFieldType::String(size), size)
            }
            n => anyhow::bail!("unsupported field type: {}", n),
        };

        fields.push(RecordField {
            offset: current_offset,
            field_type,
        });

        current_offset += field_size;
    }

    Ok(RecordHeader { fields })
}

To make it easier to work with records, we'll define a Value type, representing field values and a Cursor struct that uniquely identifies a record within a database file. The Cursor will expose a field method, returning the value of the record's n-th field:

// src/value.rs
use std::borrow::Cow;

#[derive(Debug, Clone)]
pub enum Value<'p> {
    Null,
    String(Cow<'p, str>),
    Blob(Cow<'p, [u8]>),
    Int(i64),
    Float(f64),
}

impl<'p> Value<'p> {
    pub fn as_str(&self) -> Option<&str> {
        if let Value::String(s) = self {
            Some(s.as_ref())
        } else {
            None
        }
    }
}

// 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))),
            RecordFieldType::String(length) => {
                let value = std::str::from_utf8(
                    &payload[record_field.offset..record_field.offset + length],
                ).expect("invalid utf8");
                Some(Value::String(Cow::Borrowed(value)))
            }
            RecordFieldType::Blob(length) => {
                let value = &payload[record_field.offset..record_field.offset + length];
                Some(Value::Blob(Cow::Borrowed(value)))
            }
            _ => panic!("unimplemented"),
        }
    }
}

fn read_i8_at(input: &[u8], offset: usize) -> i64 {
    input[offset] as i64
}

fn read_i16_at(input: &[u8], offset: usize) -> i64 {
    i16::from_be_bytes(input[offset..offset + 2].try_into().unwrap()) as i64
}

fn read_i24_at(input: &[u8], offset: usize) -> i64 {
    (i32::from_be_bytes(input[offset..offset + 3].try_into().unwrap()) & 0x00FFFFFF) as i64
}

fn read_i32_at(input: &[u8], offset: usize) -> i64 {
    i32::from_be_bytes(input[offset..offset + 4].try_into().unwrap()) as i64
}

fn read_i48_at(input: &[u8], offset: usize) -> i64 {
    i64::from_be_bytes(input[offset..offset + 6].try_into().unwrap()) & 0x0000FFFFFFFFFFFF
}

fn read_i64_at(input: &[u8], offset: usize) -> i64 {
    i64::from_be_bytes(input[offset..offset + 8].try_into().unwrap())
}

fn read_f64_at(input: &[u8], offset: usize) -> f64 {
    f64::from_be_bytes(input[offset..offset + 8].try_into().unwrap())
}

To simplify iteration over a page's records, we'll also implement a Scanner struct that wraps a page and allows us to get a Cursor for each record:

// 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))
            }
        }
    }
}

Table descriptions

With most of the leg work out of the way, we can get back to our original goal: listing tables. SQLite stores the schema of a database in a special table called sqlite_master. The schema for the sqlite_master table is as follows:

CREATE TABLE sqlite_schema(
  type text,
  name text,
  tbl_name text,
  rootpage integer,
  sql text
);

Theses columns are used as follows:

type: the type of the schema object. For tables, this will always be table.
name: the name of the schema object.
tbl_name: the name of the table the schema object is associated with. In the case of tables, this will be the same as name.
rootpage: root page of the table, we'll use it later to read the table's content.
sql: the SQL statement used to create the table.

Since our simple database only handles basic schemas for now, we can assume that the entire schema fits in the first page of our database file. In order to list the tables in the database, we'll need to:

initialize the pager with the database file
create a Scanner for the first page
iterate over the records, and print the value of the name field (at index 1) for each record.

First, we'll define a Db struct to hold our global state:

// src/db.rs
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)
    }
}

The implementation of a basic REPL supporting the tables and tables commands is straightforward:

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")
}

Conclusion

The first part of our SQLite-compatible database is now complete. We can read the database header, parse table btree-leaf pages and decode records, but we still have a long way to go before we can support rich queries. In the next part, we'll learn how to parse the SQL language and make our first strides towards implementing the SELECT statement!

Build a HTTP server with Rust and tokio - Part 1: serving static files

geoffreycopin — Sat, 20 May 2023 22:24:12 +0000

In this episode, we'll extend our server to serve static files.
We'll also refactor our code to support connection reuse, and we'll implement a graceful shutdown mechanism.

If your didn't follow the previous episode, you can find the code on GitHub.

As we will use new dependencies, we'll need to update our Cargo.toml file:

cargo add clap tokio-util futures

Connection reuse

Under HTTP/1.0, a separate TCP connection is established for each request/response pair.
This is inefficient, as it requires a new TCP handshake for each request. HTTP/1.1 introduced connection reuse,
which allows multiple requests to be sent over the same TCP connection. This mechanism is also necessary
to support request pipelining, which we'll see in a future episode.

We'll keep waiting for new requests on the same connection until the client closes it, unless the client sets
the Connection: close header. In that case, we'll close the connection after sending the response.
All we have to do to implement this change is to wrap our client handling code in a loop:

// main.rs

// [...]
info!(?addr, "new connection");

loop {
    let req = match req::parse_request(&mut stream).await {
        Ok(req) => {
            info!(?req, "incoming request");
            req
        }
        Err(e) => {
            error!(?e, "failed to parse request");
            break;
        }
    };

    let close_connection =
        req.headers.get("Connection") == Some(&"close".to_string());

    let resp = resp::Response::from_html(
        resp::Status::NotFound,
        include_str!("../static/404.html"),
    );

    resp.write(&mut stream).await.unwrap();

    if close_connection {
        break;
    }
}
// [...]

Serving static files

Answering every request with the same 'Not found' page was ok for a start, but the time has come to serve
some real content. In this section, we'll implement a handler that serves static files from a directory.
This directory will be either the current working directory, or a directory specified by the user.

As our CLI is getting more complex, we'll use the clap crate to parse the
command line arguments.

// args.rs
use std::path::PathBuf;

use clap::Parser;

#[derive(Parser, Debug)]
pub struct Args {
    #[arg(short, long, default_value_t = 8080)]
    pub port: u16,
    #[arg(short, long)]
    pub root: Option<PathBuf>,
}

// main.rs
use clap::Parser;

// [...]

#[tokio::main]
async fn main() -> anyhow::Result<()> {
    // [...]
    let args = args::Args::parse();
    let port = args.port;
    let listener = TcpListener::bind(format!("0.0.0.0:{port}")).await.unwrap();
    // [...]
}

In order to simplify our handling code, we'll also refactor our Response struct by
using a trait object instead of a generic type parameter. This will allow use to use the same
Response type for all our handlers, even if they don't return the same type of response.

We'll also add a new from_file constructor to our Response type, which will allow us to
create a response struct from a file on disk. At this stage, we will not implement any
kind of sophisticated content negotiation, so we'll just set the Content-Type header to
a mime type based on the file extension.

// resp.rs
pub struct Response {
    pub status: Status,
    pub headers: HashMap<String, String>,
    pub data: Box<dyn AsyncRead + Unpin + Send>,
}

impl Response {
    // [...]
    pub async fn from_file(path: &Path, file: File) -> anyhow::Result<Response> {
        let headers = hashmap! {
            "Content-Length".to_string() => file.metadata().await?.len().to_string(),
            "Content-Type".to_string() => mime_type(path).to_string(),
        };

        Ok(Response {
            headers,
            status: Status::Ok,
            data: Box::new(file),
        })
    } 
    // [...]
}

fn mime_type(path: &Path) -> &str {
    match path.extension().and_then(|ext| ext.to_str()) {
        Some("html") => "text/html",
        Some("css") => "text/css",
        Some("js") => "text/javascript",
        Some("png") => "image/png",
        Some("jpg") => "image/jpeg",
        Some("gif") => "image/gif",
        _ => "application/octet-stream",
    }
}

These preparatory steps allow us to implement our static file handler in a few lines of code:

// handler.rs
use std::{env::current_dir, io, path::PathBuf};

use crate::{
    req::Request,
    resp::{Response, Status},
};

#[derive(Debug, Clone)]
pub struct StaticFileHandler {
    root: PathBuf,
}

impl StaticFileHandler {
    pub fn in_current_dir() -> io::Result<StaticFileHandler> {
        current_dir().map(StaticFileHandler::with_root)
    }

    pub fn with_root(root: PathBuf) -> StaticFileHandler {
        StaticFileHandler { root }
    }

    pub async fn handle(&self, request: Request) -> anyhow::Result<Response> {
        let path = self.root.join(request.path.strip_prefix('/').unwrap());

        if !path.is_file() {
            return Ok(Response::from_html(
                Status::NotFound,
                include_str!("../static/404.html"),
            ));
        }

        let file = tokio::fs::File::open(&path).await?;
        Response::from_file(&path, file).await
    }
}


// main.rs

#[tokio::main]
async fn main() -> anyhow::Result<()> {
    // [...]
    let handler = args
        .root
        .map(handler::StaticFileHandler::with_root)
        .unwrap_or_else(|| {
            handler::StaticFileHandler::in_current_dir().expect("failed to get current dir")
        });
    // [...]
    match handler.handle(req).await {
        Ok(resp) => {
            resp.write(stream).await.unwrap();
        }
        Err(e) => {
            error!(?e, "failed to handle request");
            return Ok(false);
        }
    };
    // [...]
}

After copying these files to the static directory, we can now serve them with our server:

cargo run -- --root static

Pressing Ctrl+C will stop the server, but in a rather abrupt way: the server will not log any
message regarding the shutdown, and will not wait for the pending requests to be processed before
closing the connection. This is not a big deal for a toy server, but in a real world application,
we would want to handle this more gracefully.

Graceful shutdown

The most straightforward way to stop our server would be to collect the client handling tasks
into a JoinSet and abort them when we receive a SIGINT signal. However, by doing so, we would
have no way to wait for the pending requests to be processed before exiting the program.

Instead, we'll use a CancellationToken to signal that the server should:

stop accepting new connection,
stop processing requests from the current connections

We'll use the two methods provided by the CancellationToken:

cancel: request cancellation from the main thread when the user presses Ctrl+C
cancelled: return a future that resolves when the cancellation is requested. Used in conjunction with select!, this will allow us to stop the client handling tasks when the cancellation is requested.

Our main function now looks like this:

// [...]
async fn main() -> anyhow::Result<()> {
    // [...]
    let cancel_token = CancellationToken::new();

    tokio::spawn({
        let cancel_token = cancel_token.clone();
        async move {
            if let Ok(()) = signal::ctrl_c().await {
                info!("received Ctrl-C, shutting down");
                cancel_token.cancel();
            }
        }
    });
    // [...]

    let mut tasks = Vec::new();

    loop {
        let cancel_token = cancel_token.clone();

        tokio::select! {
            Ok((stream, addr)) = listener.accept() => {
                let handler = handler.clone();
                let client_task = tokio::spawn(async move {
                    if let Err(e) = handle_client(cancel_token, stream, addr, &handler).await {
                        error!(?e, "failed to handle client");
                    }
                });
                tasks.push(client_task);
            },
            _ = cancel_token.cancelled() => {
                info!("stop listening");
                break;
            }
        }
    }

    futures::future::join_all(tasks).await;

    Ok(())
}

async fn handle_client(
    cancel_token: CancellationToken,
    stream: TcpStream,
    addr: SocketAddr,
    handler: &handler::StaticFileHandler,
) -> anyhow::Result<()> {
    let mut stream = BufStream::new(stream);

    info!(?addr, "new connection");

    loop {
        tokio::select! {
            req = req::parse_request(&mut stream) => {
                match req {
                    Ok(req) => {
                        info!(?req, "incoming request");
                        let close_conn = handle_req(req, &handler, &mut stream).await?;
                        if close_conn {
                            break;
                        }
                    }
                    Err(e) => {
                        error!(?e, "failed to parse request");
                        break;
                    }
                }
            }
            _ = cancel_token.cancelled() => {
                info!(?addr, "closing connection");
                break;
            }
        }
    }

    Ok(())
}

async fn handle_req<S: AsyncWrite + Unpin>(
    req: req::Request,
    handler: &handler::StaticFileHandler,
    stream: &mut S,
) -> anyhow::Result<bool> {
    let close_connection = req.headers.get("Connection") == Some(&"close".to_string());

    match handler.handle(req).await {
        Ok(resp) => {
            resp.write(stream).await.unwrap();
        }
        Err(e) => {
            error!(?e, "failed to handle request");
            return Ok(false);
        }
    };

    Ok(close_connection)
}

We can now stop the server by pressing Ctrl+C, and the server will wait for the pending requests
to be processed before exiting.

The full source code for this part is available here.

Looking for a Rust dev? Let’s get in touch!

# Build a web server with Rust and tokio - Part 0: the simplest possible GET handler

geoffreycopin — Thu, 11 May 2023 19:06:08 +0000

Welcome to this series of blog posts where we will be exploring how to
build a web server from scratch using the Rust programming language.
We will be taking a hands-on approach, maximizing our learning experience
by using as few dependencies as possible and implementing as much logic as we can.
This will enable us to understand the inner workings of a web server and the underlying
protocols that it uses.

By the end of this tutorial, you will have a solid understanding of how to build a
web server from scratch using Rust and the tokio library. So, let's dive in and
get started on our journey!

In this first part, we'll be building a barebones web server that can only
anwser GET requests with a static Not Found response. This will give us a
good starting point to build upon in the following tutorial.

Setting up our project

First, we need to create a new Rust project. We'll use the following crates:

tokio: async runtime
anyhow: easy error handling
maplit: macro for creating HashMaps
tracing: structured logging
tracing-subscriber: instrumentation ```bash

cargo new webserver
cargo add tokio --features full
cargo add anyhow maplit tracing tracing-subscriber


## Anatomy of a simple GET request
In order to actually see what a GET request looks like, we'll set up a simple server 
listening on port 8080 that will print the incoming requests to the console.
This can be done with `netcat`:
```bash


nc -l 8080

Now, if we open a new terminal and use curl send a simple GET request to
our server, we should see the following output:

Let's break down the request parts:

the method: indicates the action to be performed on the resource. In this case, we are performing a GET request, which means we want to retrieve the resource
the path: uniquely identifies the resource. In this case, we are requesting the root path /
the protocol: the protocol version. At this stage, we will always asume HTTP/1.1
the headers: a set of key-value pairs that provide additional information about the request. Our request contains the Host header, which indicates the host name of the server, the User-Agent header, which describes the client software that is making the request and the Accept header, which indicates the media types that are acceptable for the response. We'll go into more details about headers in a later tutorial

We'll use the following struct to represent requests in our code:



// req.rs

#[derive(Debug, Clone, Eq, PartialEq)]
pub struct Request {
    pub method: Method,
    pub path: String,
    pub headers: HashMap<String, String>,
}

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub enum Method {
    Get,
}

Parsing the request is just a matter of splitting the request string into
lines. The first line contains the method, path and protocol separated by spaces.
The following lines contain the headers, followed by an empty line.



// req.rs
use std::{collections::HashMap, hash::Hash};

use tokio::io::{AsyncBufRead, AsyncBufReadExt};

// [...]

impl TryFrom<&str> for Method {
    type Error = anyhow::Error;

    fn try_from(value: &str) -> Result<Self, Self::Error> {
        match value {
            "GET" => Ok(Method::Get),
            m => Err(anyhow::anyhow!("unsupported method: {m}")),
        }
    }
}

pub async fn parse_request(mut stream: impl AsyncBufRead + Unpin) -> anyhow::Result<Request> {
    let mut line_buffer = String::new();
    stream.read_line(&mut line_buffer).await?;

    let mut parts = line_buffer.split_whitespace();

    let method: Method = parts
        .next()
        .ok_or(anyhow::anyhow!("missing method"))
        .and_then(TryInto::try_into)?;

    let path: String = parts
        .next()
        .ok_or(anyhow::anyhow!("missing path"))
        .map(Into::into)?;

    let mut headers = HashMap::new();

    loop {
        line_buffer.clear();
        stream.read_line(&mut line_buffer).await?;

        if line_buffer.is_empty() || line_buffer == "\n" || line_buffer == "\r\n" {
            break;
        }

        let mut comps = line_buffer.split(":");
        let key = comps.next().ok_or(anyhow::anyhow!("missing header name"))?;
        let value = comps
            .next()
            .ok_or(anyhow::anyhow!("missing header value"))?
            .trim();

        headers.insert(key.to_string(), value.to_string());
    }

    Ok(Request {
        method,
        path,
        headers,
    })
}

Accepting connections

Now that we know how to parse a request, we can start accepting connections.
Each time a new connection is established, we'll spawn a new task to handle it
in order to keep the main thread free to accept new connections.



// main.rs
use tokio::{io::BufStream, net::TcpListener};
use tracing::info;

mod req;

static DEFAULT_PORT: &str = "8080";

#[tokio::main]
async fn main() -> anyhow::Result<()> {
    // Initialize the default tracing subscriber.
    tracing_subscriber::fmt::init();

    let port: u16 = std::env::args()
        .nth(1)
        .unwrap_or_else(|| DEFAULT_PORT.to_string())
        .parse()?;

    let listener = TcpListener::bind(format!("0.0.0.0:{port}")).await.unwrap();

    info!("listening on: {}", listener.local_addr()?);

    loop {
        let (stream, addr) = listener.accept().await?;
        let mut stream = BufStream::new(stream);

        // do not block the main thread, spawn a new task
        tokio::spawn(async move {
            info!(?addr, "new connection");

            match req::parse_request(&mut stream).await {
                Ok(req) => info!(?req, "incoming request"),
                Err(e) => {
                    info!(?e, "failed to parse request");
                }
            }
        });
    }
}

We can now run our server on port 8081with the following command:
cargo run -- 8081.
Sending a GET request to localhost:8081 should print the following output:



INFO http_server: listening on: 0.0.0.0:8081
INFO http_server: new connection addr=127.0.0.1:49351
INFO http_server: incoming request req=Request { method: Get, path: "/", headers: {"Host": "localhost", "User-Agent": "curl/7.87.0", "Accept": "*/*"} }

Sending a response

At this stage, we'll answer every request with a static Not found page.
Our response will have the following format:

Let's explore the different parts of the response:

the status line: contains the protocol version, the status code and a human-readable status message
the response headers: encoded in the same way as for the request. Our response contains the Content-Length header, which specified the length of the response body, and the Content-Type header, which indicates that the response body is encoded in HTML. The headers are followed by an empty line.
the response body: contains the actual data that will be displayed in the browser. We used an empty HTML document for brevity

We'll use the following struct to represent responses in our code:



// resp.rs
use tokio::io::{AsyncRead, AsyncWrite, AsyncWriteExt};

#[derive(Debug, Clone)]
pub struct Response<S: AsyncRead + Unpin> {
    pub status: Status,
    pub headers: HashMap<String, String>,
    pub data: S,
}

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
pub enum Status {
    NotFound,
}

impl Display for Status {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Status::NotFound => write!(f, "404 Not Found"),
        }
    }
}

The data field is generic over the type of the response body to account for
future use cases where we might want to send a stream of data.

Creating a response from an HTML string is straight forward:



// resp.rs
use std::io::Cursor;
use maplit::hashmap;

// [..]

impl Response<Cursor<Vec<u8>>> {
    pub fn from_html(status: Status, data: impl ToString) -> Self {
        let bytes = data.to_string().into_bytes();

        let headers = hashmap! {
            "Content-Type".to_string() => "text/html".to_string(),
            "Content-Length".to_string() => bytes.len().to_string(),
        };

        Self {
            status,
            headers,
            data: Cursor::new(bytes),
        }
    }
}

Sending a response is a bit more involved. We'll use the AsyncWrite trait
to write the response to a generic output stream.



// resp.rs
use std::{
    collections::HashMap,
    fmt::{Display, Formatter},
    io::Cursor,
};

use maplit::hashmap;
use tokio::io::{AsyncRead, AsyncWrite, AsyncWriteExt};

// [...]

impl<S: AsyncRead + Unpin> Response<S> {
    pub fn status_and_headers(&self) -> String {
        let headers = self
            .headers
            .iter()
            .map(|(k, v)| format!("{}: {}", k, v))
            .collect::<Vec<_>>()
            .join("\r\n");

        format!("HTTP/1.1 {}\r\n{headers}\r\n\r\n", self.status)
    }

    pub async fn write<O: AsyncWrite + Unpin>(mut self, stream: &mut O) -> anyhow::Result<()> {
        stream
            .write_all(self.status_and_headers().as_bytes())
            .await?;

        tokio::io::copy(&mut self.data, stream).await?;

        Ok(())
    }
}

impl Display for Status {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Status::NotFound => write!(f, "404 Not Found"),
        }
    }
}

Puting it all together

We'll use the following document as our 404 page:



<!-- static/404.html -->
<!DOCTYPE html>
<html lang="en">
<head>
    <title>Page Not Found</title>
    <style>
        body {
            background-color: #f8f8f8;
            font-family: Arial, sans-serif;
            font-size: 16px;
            color: #333;
        }
        .container {
            max-width: 600px;
            margin: 0 auto;
            padding: 40px 20px;
            text-align: center;
            border: 1px solid #ddd;
            border-radius: 5px;
            background-color: #fff;
            box-shadow: 0 2px 4px rgba(0,0,0,0.1);
        }
        h1 {
            font-size: 48px;
            margin-bottom: 20px;
            color: #333;
        }
        p {
            font-size: 24px;
            margin-bottom: 40px;
        }
    </style>
</head>
<body>
<div class="container">
    <h1>404</h1>
    <p>The page you are looking for could not be found.</p>
</div>
</body>
</html>

We can now use our Response struct to send a Not found page to the client
when we receive a request:



// main.rs
// [...]
let resp = resp::Response::from_html(
    resp::Status::NotFound,
    include_str!("../static/404.html"),
);

resp.write(&mut stream).await.unwrap();
// [...]

Navigating to localhost:8081 should now display our Not found page.

That's a good start, but we're still far from a fully functional web server.
In the next part, we'll add support for serving static files.
You can find the code for this part here.

Looking for a Rust dev? Let’s get in touch!

Build a custom Python linter in 5 minutes

geoffreycopin — Fri, 20 Jan 2023 15:55:39 +0000

Creating a custom linter can be a great way to enforce coding standards and detect code smells. In this tutorial, we'll use Sylver, a source code query engine to build a custom Python linter in just a few lines of code.

Sylver's main interface is a REPL console, in which we can load the source code of our project to query it using a SQL-like query language called SYLQ. Once we'll have authored SYLQ queries expressing our linting rules, we'll be able to save them into a ruleset that can be run like a traditional linter.

Installation

If sylver --version doesn't output a version number >= 0.2.2, go to https://sylver.dev to download a fresh copy of the software.

Project setup

We'll use the following Python file to test our linting rules:

#main.py
from users.models import *
from auth.models import check_password

foo = 100
O = 100.0

my_dict = {'hello': 'world'}

if my_dict.has_key('hello'):
    print('It works!')

if 'hello' in my_dict:
    print('It works!')

Starting the REPL

Starting the REPL is as simple as invoking the following command at the root of your project:

sylver query --files="src/**/*.py" --language=python

The REPL can be exited by pressing Ctrl+C or typing :quit at the prompt.

We can now execute SYLQ queries by typing the code of the query, followed by a ;.
For instance: to retrieve all the if statements (denoted by the node type IfStatement):

match IfStatement;

The results of the query will be formatted as follow:

$0 [IfStatement main.py:1:9-23:10]
$1 [IfStatement main.py:1:12-23:13]

The code of a given if statement can be displayed by typing :print followed by the node alias (for instance: :print $1). The parse tree can be displayed using the :print_ast command (for instance: :print_ast $1).

Rule1: wildcard imports (inspired by F403)

This rule will flag all the imports of the form from x import *.

The first step is to get familiar with the tree structure of Python's import statements, so let's print a ImportFromStatement node along with its AST:

λ> match ImportFromStatement;

$2 [ImportFromStatement main.py:1:1-27:1]
$3 [ImportFromStatement main.py:1:2-39:2]

λ> :print $2

from users.models import *

λ> :print_ast $2

ImportFromStatement {
. ● module_name: DottedName {
. . Identifier { users }
. . Identifier { models }
. }
. WildcardImport { * }
}

It appears that the faulty part of the import statement (the wildcard: *) is represented by a WildcardImport node.
So this first rule can easily be expressed in SYLQ:

match WildcardImport;

Rule2: Ambiguous variable name (inspired by E741)

This style-oriented rule will detect variables named 'l', 'I' or 'O', as these names can be confusing.

Same as before, let's analyze the tree structure of an assignment:

λ> match Assignment;

$4 [Assignment main.py:1:4-10:4]
$5 [Assignment main.py:1:5-10:5]
$6 [Assignment main.py:1:7-29:7]

λ> :print_ast $5

Assignment {
. ● left: Identifier { O }
. ● right: Float { 100.0 }
}

The variable's Identifier can be accessed through the left field of the Assignment node. We can match the Identifier's text against a regex
by using the builtin matches method:

match a@Assignment when a.left.text.matches(`^(I|O|l)$`);

Here the Assignment node is bound to a using the binding operator: @.

Rule3: `has_key()` is deprecated (inspired by W601)

This rule signals uses of the deprecated dictionnary has_key method.

Here is the tree representation of a call to has_key:

Call {
. ● function: Attribute {
. . ● object: Identifier { my_dict }
. . ● attribute: Identifier { has_key }
. }
. ● arguments: ArgumentList {
. . String { 'hello' }
. }
}

This query can be expressed using nested patterns, as follow:

match Call(function: Attribute(attribute: 'has_key'));

Creating the ruleset

The following ruleset uses our linting rules:

id: customRules

language: python

rules:
    - id: F403
      severity: warning
      message: "wildcard import"
      note: "wildcard imports are discouraged because the programmer often won’t know where an imported object is defined"

      query: >
        match WildcardImport



    - id: E741
      severity: info
      message: "ambiguous variable name"
      note: "variables named I, O and l can be very hard to read"

      query: >
        match a@Assignment when a.left.text.matches(`^(I|O|l)$`)


    - id: W601
      severity: error
      message: ".has_key() is deprecated"
      note: "'.has_key()' was deprecated in Python 2. It is recommended to use the 'in' operator instead"

      query: >
        match Call(function: Attribute(attribute: 'has_key'))

Assuming that it is stored in a file called ruleset.yaml at the root of our project, we can run it with the following command:

sylver ruleset run --files "**/*.py" --rulesets ruletset.yaml

Getting updates

For more informations about new features and/or cool SYLQ one-liners, connect with Sylver on Twitter or Discord!

Build a custom Javascript linter in 5 minutes

geoffreycopin — Fri, 09 Dec 2022 08:29:22 +0000

Creating a custom linter can be a great way to enforce coding standards and detect code smells. In this tutorial, we'll use Sylver, a source code query engine to build a custom Javascript linter in just a few lines of code.

Sylver's main interface is a REPL console, in which we can load the source code of our project to query it using a SQL-like query language called SYLQ. Once we'll have authored SYLQ queries expressing our linting rules, we'll be able to save them into a ruleset that can be run like a traditional linter.

Installation

If sylver --version doesn't output a version number >= 0.1.9, go to https://sylver.dev to download a fresh copy of the software.

Starting the REPL

Starting the REPL is as simple as invoking the following command at the root of your project:

sylver query --files="src/**/*.js" --spec=https://github.com/sylver-dev/javascript.git#javascript.yaml

The REPL can be exited by pressing Ctrl+C or typing :quit at the prompt.

We can now execute SYLQ queries by typing the code of the query, followed by a ;. For instance: to retrieve all the method definitions (denoted by the node type MethodDefinition):

match MethodDefinition;

The results of the query will be formatted as follow:

[...]
$0 [MethodDefinition src/store/createArticles.js:36:5-38:5]
$1 [MethodDefinition src/store/createArticles.js:39:5-41:5]
$2 [MethodDefinition src/store/createArticles.js:42:5-59:5]
$3 [MethodDefinition src/store/createArticles.js:60:5-77:5]
$4 [MethodDefinition src/store/createArticles.js:78:5-83:5]
$5 [MethodDefinition src/store/createArticles.js:84:5-89:5]
[...]

The code of a given method definition can be displayed by typing :print followed by the node alias (for instance: :print $3). The parse tree can be displayed using the :print_ast command (for instance: :print_ast $3).

Rule1: use of the `==` operator

For our first rule, we'd like to detect uses of the unsafe == operator for checking equality. The first step is to get familiar with the tree structure of Javascript's binary expressions, so let's print a BinaryExpression node along with its AST:

λ> match BinaryExpression;

[...]
$43 [BinaryExpression src/pages/Article/Comments.js:7:31-7:77]
[...]

λ> :print $43

currentUser.username == comment.author.username

λ> :print_ast $43

BinaryExpression {
. ● left: MemberExpression {
. . ● object: Identifier { currentUser }
. . ● property: Identifier { username }
. }
. ● operator: EqEq { == }
. ● right: MemberExpression {
. . ● object: MemberExpression {
. . . ● object: Identifier { comment }
. . . ● property: Identifier { author }
. . }
. . ● property: Identifier { username }
. }
}

It appears that the nodes violating our rule are the BinaryExpression nodes for which the operator field contains an EqEq node. This can be easily expressed in SYLQ:

match BinaryExpression(operator: EqEq);

Rule2: functions with too many parameters

For our second linting rule, we'd like to identify functions that have more than 6 parameters.

Here is the relevant part of the parse tree of a Function node:

Function {
. ● async: AsyncModifier { async }
. ● name: Identifier { send }
. ● parameters: FormalParameters {
. . ● params: List {
. . . FormalParameter {
. . . . ● value: Identifier { method }
. . . }
. . . FormalParameter {
. . . . ● value: Identifier { url }
. . . }
. . . FormalParameter {
. . . . ● value: Identifier { data }
. . . }
. . . FormalParameter {
. . . . ● value: Identifier { resKey }
. . . }
. . }
. }
. ● body: StatementBlock {
[...]

Function parameters are represented by FormalParameters nodes with a params field containing the actual function parameters. In our query, the condition regarding the length of the params list can be specified in a when clause, as follows:

match f@FormalParameters when f.params.length > 6;

Rule3: JSX 'img' elements without an 'alt' attribute

For our last rule, we'd like to identify <img> elements that miss the alt attribute. img elements are self-closing, so we'll start by looking at the parse tree of a JsxSelfClosingElement node:

λ> match JsxSelfClosingElement;
[...]
$73 [JsxSelfClosingElement src/pages/Article/Comments.js:21:11-21:55]
[...]

λ> :print $73

<img src={image} class="comment-author-img"/>

λ> :print_ast $73

JsxSelfClosingElement {
. ● name: Identifier { img }
. ● attribute: List {
. . JsxAttribute {
. . . ● name: Identifier { src }
. . . ● value: JsxExpression {
. . . . Identifier { image }
. . . }
. . }
. . JsxAttribute {
. . . ● name: Identifier { class }
. . . ● value: String { "comment-author-img" }
. . }
. }
}

In order to find the img elements that have no JsxAttribute with named alt in their attribute list, we can use a list quantifying expression, as illustrated in the following query:

match j@JsxSelfClosingElement(name: "img") 
      when no j.attribute match JsxAttribute(name: "alt");

Creating the ruleset

The following ruleset uses our linting rules:

id: customLinter

language: "https://github.com/sylver-dev/javascript.git#javascript.yaml"

rules:
    - id: unsafeEq
      message: equality comparison with `==` operator
      severity: warning

      query: "match BinaryExpression(operator: EqEq)"


    - id: tooManyParams
      message: function has too many parameters
      severity: info
      note: According to our style guide, functions should have less than 6 parameters.

      query: match f@FormalParameters when f.params.length > 6


    - id: missingAlt
      message: <img> tags should have an "alt" attribute
      severity: error

      query:
        "match j@JsxSelfClosingElement(name: 'img')
              when no j.attribute match JsxAttribute(name: 'alt')"

Assuming that it is stored in a file called custom_linter.yaml at the root of our project, we can run it with the following command:

sylver ruleset run --files="src/**/*.js" --rulesets=custom_linter.yaml

Getting updates

For more informations about new features and/or cool SYLQ one-liners, connect with Sylver on Twitter or Discord!

Build a custom Go linter in 5 minutes

geoffreycopin — Fri, 23 Sep 2022 14:37:29 +0000

Creating a custom linter can be a great way to enforce coding standards and detect code smells. In this tutorial, we'll use Sylver's, a source code query engine to build a custom Golang linter in just a few lines of code.

Installation

If sylver --version doesn't output a version number >= 0.1.8, go to https://sylver.dev to download a fresh copy of the software.

Starting the REPL

Starting the REPL is as simple as invoking the following command at the root of your project:

sylver query --files="**/*.go" --spec=https://github.com/sylver-dev/golang.git#golang.yaml

The REPL can be exited by pressing Ctrl+C or typing :quit at the prompt.

We can now execute SYLQ queries by typing the code of the query, followed by a ;.
For instance: to retrieve all the struct declarations:

match StructType;

The results of the query will be formatted as follow:

[...]
$359 [StructType association.go:323:17-327:1]
$360 [StructType schema/index.go:10:12-18:1]
$361 [StructType schema/index.go:20:18-27:1]
$362 [StructType tests/group_by_test.go:70:12-73:2]
$363 [StructType schema/check.go:11:12-15:1]

The code of a given struct declaration can be displayed by typing :print followed by the node alias (for instance: :print $362). The parse tree can be displayed using the :print_ast command (for instance: :print_ast $362).

Rule1: detect struct declarations with too many fields

For our first rule, we'd like to flag struct declarations that have more than 10 fields.
The first step is to get familiar with the tree structure of struct declarations, so let's print a StructType along with its ast:

λ> :print $362

struct {
        Name  string
        Total int64
    }

λ> :print_ast $362

StructType {
. ● fields: List<FieldSpec> {
. . FieldSpec {
. . . ● names: List<Identifier> {
. . . . Identifier { Name }
. . . }
. . . ● type: TypeIdent {
. . . . ● name: Identifier { string }
. . . }
. . }
. . FieldSpec {
. . . ● names: List<Identifier> {
. . . . Identifier { Total }
. . . }
. . . ● type: TypeIdent {
. . . . ● name: Identifier { int64 }
. . . }
. . }
. }
}

The fields of the struct are stored in a field aptly named fields that holds a list of FieldSpec nodes. This means that the nodes violating our rule are all the StructType nodes for which the fields list has a length higher than 10.
This can be easily expressed in SYLQ:

 match StructType s when s.fields.length > 10;

Rule2: suggest the usage of assignment operators

For our second linting rule, we'd like to identify assignments that could be simplified by using an assignment operator (like +=) such as:

x = x + 1

Let's explore the parse tree of a simple assignment:

λ> :print $5750

err = nil

λ> :print_ast $5750

AssignStmt {
. ● lhs: List<Expr> {
. . Identifier { err }
. }
. ● rhs: List<Expr> {
. . NilLit { nil }
. }
}

So we want to retrieve the AssignStmt nodes for which the rhs field contains a Binop that has lhs as its left operand. Also, the left-hand side of the assignment must contain a single expression. This can be written as:

match AssignStmt a when
      a.lhs.length == 1
   && a.rhs[0] is { BinOp b when b.left.text == a.lhs[0].text };

Rule3: incorrect usage of the `make` builtin function

For our last linting rule, we want to identify incorrect usage of the make function, where the length is higher than the capacity, as this probably indicates a programming error.

Here is the parse tree of a call to make:

λ> :print $16991

make([]string, 0, len(value))

λ> :print_ast $16991

CallExpr {
. ● fun: Identifier { make }
. ● args: List<GoNode> {
. . SliceType {
. . . ● elemsType: TypeIdent {
. . . . ● name: Identifier { string }
. . . }
. . }
. . IntLit { 0 }
. . CallExpr {
. . . ● fun: Identifier { len }
. . . ● args: List<GoNode> {
. . . . Identifier { value }
. . . }
. . }
. }
}

Here are the conditions that violating nodes will meet:

The test of fun is make
The args list contains 3 elements
The last two arguments are int literals
The third argument (capacity) is smaller than the second (length)

Let's encode this in SYLQ:

match CallExpr c when
      c.fun.text == 'make'
   && c.args.length == 3
   && c.args[1] is IntLit
   && c.args[2] is IntLit
   && c.args[2].text.to_int() < c.args[1].text.to_int();

Creating the ruleset

The following ruleset uses our linting rules:

id: customLinter

language: "https://github.com/sylver-dev/golang.git#golang.yaml"

rules:
    - id: largeStruct
      message: struct has many fields
      severity: info

      query:  match StructType s when s.fields.length > 10


    - id: assignOp
      message: assignment should use an assignment operator
      severity: warning
      note: According to our style guide, assignment operators should be preferred.

      query: >
        match AssignStmt a when
             a.lhs.length == 1
          && a.rhs[0] is { BinOp b when b.left.text == a.lhs[0].text }

    - id: makeCapacityErr 
      message: capacity should be higher than length     
      severity: error

      query: >
        match CallExpr c when
              c.fun.text == 'make'
          && c.args.length == 3
          && c.args[1] is IntLit
          && c.args[2] is IntLit
          && c.args[2].text.to_int() < c.args[1].text.to_int()

Assuming that it is stored in a file called custom_linter.yaml at the root of our project, we can run it with the following command:

sylver ruleset run --files="**/*.go" --rulesets=custom_linter.yaml

Getting started with Sylver - Part3/3 : From queries to analyzer

geoffreycopin — Tue, 30 Aug 2022 15:01:42 +0000

In Part1 and
Part2 of the
series, we learned how to build a language spec and how to use Sylver's query language to explore the parse tree of our JSON documents.

While it can be insightful to explore a codebase interactively through source-code queries, it's not the most practical way to perform source code verification. In this tutorial, we'll learn how to package the queries we built in the last part into a ruleset to use them in a linter-like fashion.

If you have already installed sylver and sylver --version doesn't output
a version number >= 0.1.4, please go to https://sylver.dev to download a fresh copy of the software.

Prelude

We'll reuse two files from the last tutorial:

json.syl

node JsonNode { }

node Null: JsonNode { }

node Bool: JsonNode { }

node Number: JsonNode { }

node String: JsonNode { }

node Array: JsonNode { 
    elems: List<JsonNode> 
}

node Object: JsonNode {
    members: List<Member>
}

node Member: JsonNode {
    key: String,
    value: JsonNode
}

term COMMA = ','
term COLON = ':'
term L_BRACE = '{'
term R_BRACE = '}'
term L_BRACKET = '['
term R_BRACKET = ']'
term NULL = 'null'

term BOOL_LIT = `true|false`
term NUMBER_LIT = `\-?(0|([1-9][0-9]*))(.[0-9]+)?((e|E)(\+|-)?[0-9]+)?`
term STRING_LIT = `"([^"\\]|(\\[\\/bnfrt"])|(\\u[a-fA-F0-9]{4}))*"`


ignore term WHITESPACE = `\s`

rule string = String { STRING_LIT }

rule member = Member { key@string COLON value@main }

rule main =
    Null { NULL }
  | Number { NUMBER_LIT }
  | Bool { BOOL_LIT }
  | string
  | Array { L_BRACKET elems@sepBy(COMMA, main) R_BRACKET }
  | Object { L_BRACE members@sepBy(COMMA, member) R_BRACE }@

invalid_config.json

{
    "variables": [
        {
            "name": "date of birt`",
            "description": "Customer's date of birth",
            "type": "datetime"
        },
        {
            "name": "activity",
            "description": "A short text describing the customer's profession",
            "type": "string"
        },
        {
            "name": "country",
            "description": "Customer's country of residence",
            "type": "string",
            "values": ["us", "fr", "it" ]
        }
    ]
}

Stepping out of the REPL

Creating a ruleset

Packaging the rules from the previous tutorial into a reusable ruleset is as simple as
creating the following YAML file:

id: 'JSON ruleset'
language: json.syl

rules: 
  - id: variable_length
    message: Variable name is too long
    severity: warning
    query: >
      match String desc when desc.text.length > 37 && desc.parent is {
        Member m when m.key.text == '"description"'
      }  

  - id: variable_format 
    message: Variable name isn't a lowercase word
    severity: info
    query: >
      match String s when !s.text.matches(`"[a-z]+"`) && s.parent is {
        Member m when m.key.text == '"name"'
      }    

  - id: types_or_values
    message: Fields 'type' and 'values' are mutually exclusive    
    severity: error
    note: The type can be deduced from the values list.
    query: >
      match Object n when
        any n.members.children match {  
            Member m when m.key.text == '"type"' 
        }
        && any n.members.children match { 
            Member m when m.key.text == '"values"' 
        }

Where id is a human-readable description of the ruleset, and language refers to
a language spec file.

The following properties describe the individual rules composing the ruleset:

id: unique and short name of the rule
message: a concise description of the issue
severity: error, info, or warning
query: inline query
note: optional additional informations

Assuming that our ruleset file is called ruleset.yaml, we can run this ruleset on every .json file in the current directory by invoking the following command:

sylver ruleset run --files "*.json" --rulesets ruleset.yaml

Storing our project configuration

If we wish to validate our codebase against multiple rulesets, repeating the above
command for every ruleset can be tedious. Instead, we can write a project configuration
in a sylver.yaml file at the root of our project:

subprojects:
  - language: json.syl
    rulesets: ['ruleset.yaml']
    include:
      - './**/*.json'

The configuration contains a list of subprojects, each having a language, an optional list of rulesets, and a list of files to include.

Invoking sylver check will read the config from sylver.yaml and run the
specified rulesets.

Git integration

Should you want to reuse your language specs or rulesets in several projects, copying your .syl and .yaml files in every project would be inconvenient. Luckily
rulesets and project configurations can refer to artifacts stored in a git repository.

The language spec and ruleset for this tutorial have been uploaded to this repo, so if we rewrite our sylver.yaml config file as:

subprojects:
  - language: 
      repo: https://github.com/geoffreycopin/getting_started_json_tutorial
      file: json.syl
    rulesets: 
      - repo: https://github.com/geoffreycopin/getting_started_json_tutorial
        file: 'ruleset.yaml'
    include:
      - './**/*.json'

the language spec and ruleset will be cloned automatically in the .sylver directory
when running sylver check.

Conclusion

We now have a reusable linter for our JSON configuration files built from
scratch using Sylver's DSL.

The following tutorial will use a pre-built Golang to write a general-purpose Go linter.

Getting started with Sylver - Part2/3 : Intuitive JSON AST queries

geoffreycopin — Sat, 20 Aug 2022 11:20:00 +0000

In Part 1,
we used Sylver's meta language to build a specification for the
JSON format. But an AST, by itself, is not of much use.
In this next tutorial, we'll continue building our JSON configuration validator.
To this end, we'll learn how to use Sylver's query REPL (Read Eval Print Loop) to
identify the parts of our JSON code that do not comply with a set of increasingly complex
rules. In the next and last part, we'll learn how to package queries into a rule set
to share and reuse them easily.

If you have already installed sylver and sylver --version doesn't output
a version number >= 0.1.3, please go to https://sylver.dev to download a fresh copy of the software.

Prelude

We will reuse the json.syl spec file built in the previous tutorial.
Since the config.json file that we used to test our parser contains a valid
configuration, we'll need to create a new JSON document (invalid_config.json) containing
an incorrect configuration:

{
    "variables": [
        {
            "name": "date of birt`",
            "description": "Customer's date of birth",
            "type": "datetime"
        },
        {
            "name": "activity",
            "description": "A short text describing the customer's profession",
            "type": "string"
        },
        {
            "name": "country",
            "description": "Customer's country of residence",
            "type": "string",
            "values": ["us", "fr", "it" ]
        }
    ]
}

This file represents the configuration of an imaginary software handling a database of
customers. Each customer profile is described using a configurable set of variables.

We want to validate these variable declarations using the following rules:

Variable descriptions must contain at most 35 characters
The name of a variable must be a single lowercase word
If the values field is set, the type field should be absent (as it matches the type of the values)

Let's parse this file and start a REPL to query our AST!

Basic REPL usage

Loading the AST of invalid_config.json is as simple as invoking:

sylver query --spec=json.syl --files=invalid_config.json

The files argument accepts one or several file names or quoted glob patterns.

You can exit the REPL by typing :quit at the prompt.

:print invalid_config.json and :print_ast invalid_config.json can be used to visualize
one of the loaded files, or the corresponding AST.

Query language basics

Syntax queries are of the form match <NodeType> <binding>? (when <boolean expression>)?.
The node binding and the when [...] clause are optional.
NodeType represents either a node type as it appears when printing the AST or a
placeholder (_) that matches every node. The whole part following the match keyword
is called a query pattern.

In the REPL, queries must be followed by a ;

The most straightforward query, returning every node in the AST, is written as follows:

match _;

A slightly more advanced query to return every String node in our document:

match String;

If we only wish to retrieve the string literals above a certain length, we can
add a when clause:

match String str when str.text.length > 35;

This query matches only the string literals whose text representation (quotes included)
contains more than 35 characters. In our document, there is only one match on line 10.

The node type can be tested using the is keyword. For instance,
to retrieve any node whose direct parent is an Object:

match _ node when node.parent is Object;

Returns the members list of all the objects in our document.

The is keyword can also test a node against a full query pattern surrounded by curly braces. So, for example, we can retrieve every node whose parent
is a member with key name.

match _ node when node.parent is {
    Member m when m.key.text == '"name"'
};

String literals can be single or double quoted.

Now that we know how to write basic queries, let's try to find the nodes that violate our rules.

Rule 1: variable descriptions should be shorter than 35 characters

Except for the && operator in boolean expressions, this rule only
uses features that appeared in the previous section so you can test
yourself by trying to write it without looking at the following block of code!

match String desc when desc.text.length > 37 && desc.parent is {
   Member m when m.key.text == '"description"'
};

This query should return a single node on line 10 that is indeed longer than the
specified length.
Note that we check that the text length is above 37 instead of 35 because of the surrounding quotes.

Rule 2: variable names should be a single lowercase word

match String s when !s.text.matches(`"[a-z]+"`) && s.parent is {
   Member m when m.key.text == '"name"'
};

Returns a single node corresponding to the invalid date of birth name.

Apart from the boolean ! operator, this rule demonstrates the use of the matches
method on text values. Unsurprisingly, it returns true when the text matches the
regex literal given as an argument. As in spec files, regex literals are delimited by
backticks.

Rule 3: fields `type` and `values` should be mutually exclusive

For this rule, we'll use array quantifying expressions of the form:

<quantifier> <array value> match <query pattern>

Where the quantifier is any of the following keywords: no, any, all.
Array quantifying expressions return true when any, all, or none of the values
in the given array match the query pattern.
Using this new tool, we can find the Object nodes for witch
there is at least one child member with key type and one child member with key values:

match Object n when
    any n.members.children match {  
        Member m when m.key.text == '"type"' 
    }
    && any n.members.children match { 
        Member m when m.key.text == '"values"' 
    };

Conclusion

We now have queries to identify violations of our business rules, but opening the REPL
and pasting the queries whenever we want to validate a document isn't very practical.
So, in the final part of this series, we'll learn how to package queries into a Sylver rule
set to consume, distribute and share them more conveniently!

Getting started with Sylver - Part1 : Building a JSON parser in 49 lines of code

geoffreycopin — Wed, 10 Aug 2022 16:55:00 +0000

Sylver is a language agnostic platform for building custom source code
analyzers (think eslint for every language).
This might be a lot to unpack, so let us explore this tool
by solving a real-world problem: our application's configuration is stored in
complex JSON documents, and we'd like to build a tool to automatically validate
these documents against our business rules.

In this series of tutorials, we'll go from having zero knowledge of Sylver or
static analysis to building a fully-fledged linter for our configuration files.
We will use JSON as an example, but the tools and techniques presented
apply to many data formats and even complete programming languages!
Also, note that while we will be building everything from scratch using
Sylver's domain-specific languages (DSL), a catalog of built-in specifications for the most common languages will be included in future releases of the tool.

In part 1, we will discover Sylver's meta language, a DSL used to describe the shape
of programming languages and data formats. After completing this tutorial, we'll have
a complete spec for the JSON language, allowing us to turn JSON documents into
Sylver parse trees.
In part 2, we will load the parse trees into Sylver's query engine,
and we will find nodes that violate our business rules using an SQL-like query
language.
In part 3, we will learn how to turn our language spec and queries into a set of
linting rules so that we can run them conveniently and share them.

Installation

Sylver is distributed as a single static binary. Installing it is as simple as:

Go to https://sylver.dev to download the binary for your platform
Unpack the downloaded archive
Move the sylver binary to a location in your $PATH

Prelude

Let us create a blank workspace for this tutorial!

We'll start by creating a new folder and a json.syl file to write
the Sylver specification for the JSON language.

mkdir sylver_getting_started
cd sylver_getting_started
touch json.syl

We will also store our test JSON file in config.json.

{
    "variables": [
        {
            "name": "country",
            "description": "Customer's country of residence",
            "values": ["us", "fr", "it"]
        },
        {
            "name": "age",
            "description": "Cusomer's age",
            "type": "number"
        }
    ]
}

This file specifies the variables used to describe customer profiles in a fictional
customer database.
Variables are assigned a type or a list of potential values.

Types definition

Sylver parses raw text into typed structures called parse trees. The first step in defining a language spec is to define a set of types for our tree nodes.
We'll add the following node types declarations to our json.syl spec:

node JsonNode { }

node Null: JsonNode { }

node Bool: JsonNode { }

node Number: JsonNode { }

node String: JsonNode { }

node Array: JsonNode { 
    elems: List<JsonNode> 
}

node Object: JsonNode {
    members: List<Member>
}

node Member: JsonNode {
    key: String,
    value: JsonNode
}

These declarations resemble object type declarations in many mainstream languages.
The : syntax denotes inheritance.

Now that we have a set of types to describe JSON documents, we need to specify how to build a
parse tree from a sequence of characters. This process is done in two steps:

Lexical analysis: in this step, individual characters that form an indivisible entity (such as the digits of a number or the characters of a string) are grouped together into tokens. Some tokens are only one character-wide (for example, the brackets and semicolons in JSON).
Syntactic analysis, in which tree nodes are built for the stream of tokens.

Lexical analysis

Tokens are described using declarations of the form term NAME = <term_content> where
<term_content> is either a literal surrounded by single-quotes (') or a regex
between backticks (`). The regexes use a syntax similar to Perl-style regular expressions.

Characters in the input string that match one of the terminal literals
or regexes will be grouped into a token of the given name.

term COMMA = ','
term COLON = ':'
term L_BRACE = '{'
term R_BRACE = '}'
term L_BRACKET = '['
term R_BRACKET = ']'
term NULL = 'null'

term BOOL_LIT = `true|false`
term NUMBER_LIT = `\-?(0|([1-9][0-9]*))(.[0-9]+)?((e|E)(\+|-)?[0-9]+)?`
term STRING_LIT = `"([^"\\]|(\\[\\/bnfrt"])|(\\u[a-fA-F0-9]{4}))*"`


ignore term WHITESPACE = `\s`

Term rules for numbers and strings are slightly involved in accounting for some
of JSON's peculiarities.

Note that the WHITESPACE term declaration (matching a single whitespace character) is prefixed with the ignore keyword. This means that WHITESPACE tokens do not affect
the structure of the document and can be ignored during syntactic analysis.

Syntactic analysis

In this last part of the language spec, we write rules describing how tree nodes are built by matching tokens from the input stream.

For example, a rule specifying: "if the current token is a STRING_LIT, build a
String node" can be written as follows:

rule string = String { STRING_LIT }

Rules can refer to other rules to construct nested nodes.
For example, here is a rule specifying that a Member node (corresponding to an object member
in JSON) can be built by building a node using the string rule and then matching a COLON token followed by any valid JSON value:

rule member = Member { key@string COLON value@main }

Nested nodes are associated with a field using the @ syntax.
The main rule is the entry point for the parser, so in our case, it designates any valid JSON value.

A valid JSON document can be made of a 'null' literal, a number, a boolean value,
a string, an array of JSON values, or a JSON object, which is reflected in the main rule:

rule main =
    Null { NULL }
  | Number { NUMBER_LIT }
  | Bool { BOOL_LIT }
  | string
  | Array { L_BRACKET elems@sepBy(COMMA, main) R_BRACKET }
  | Object { L_BRACE members@sepBy(COMMA, member) R_BRACE }

The sepBy(TOKEN, rule_name) syntax is used to parse nodes using the main rule,
while matching a TOKEN token between every parsed node.

Conclusion

We now have a complete language spec for the JSON language:

node JsonNode { }

node Null: JsonNode { }

node Bool: JsonNode { }

node Number: JsonNode { }

node String: JsonNode { }

node Array: JsonNode { 
    elems: List<JsonNode> 
}

node Object: JsonNode {
    members: List<Member>
}

node Member: JsonNode {
    key: String,
    value: JsonNode
}

term COMMA = ','
term COLON = ':'
term L_BRACE = '{'
term R_BRACE = '}'
term L_BRACKET = '['
term R_BRACKET = ']'
term NULL = 'null'

term BOOL_LIT = `true|false`
term NUMBER_LIT = `\-?(0|([1-9][0-9]*))(.[0-9]+)?((e|E)(\+|-)?[0-9]+)?`
term STRING_LIT = `"([^"\\]|(\\[\\/bnfrt"])|(\\u[a-fA-F0-9]{4}))*"`


ignore term WHITESPACE = `\s`

rule string = String { STRING_LIT }

rule member = Member { key@string COLON value@main }

rule main =
    Null { NULL }
  | Number { NUMBER_LIT }
  | Bool { BOOL_LIT }
  | string
  | Array { L_BRACKET elems@sepBy(COMMA, main) R_BRACKET }
  | Object { L_BRACE members@sepBy(COMMA, member) R_BRACE }

The last step is to test it on our test file!
This is done by invoking the following command:
sylver parse --spec=json.syl --file=config.json

Which yields the following parse tree:

Object {
. ● members: List<Member> {
. . Member {
. . . ● key: String { "variables" }
. . . ● value: Array {
. . . . ● elems: List<JsonNode> {
. . . . . Object {
. . . . . . ● members: List<Member> {
. . . . . . . Member {
. . . . . . . . ● key: String { "name" }
. . . . . . . . ● value: String { "country" }
. . . . . . . }
. . . . . . . Member {
. . . . . . . . ● key: String { "description" }
. . . . . . . . ● value: String { "Customer's country of residence" }
. . . . . . . }
. . . . . . . Member {
. . . . . . . . ● key: String { "values" }
. . . . . . . . ● value: Array {
. . . . . . . . . ● elems: List<JsonNode> {
. . . . . . . . . . String { "us" }
. . . . . . . . . . String { "fr" }
. . . . . . . . . . String { "it" }
. . . . . . . . . }
. . . . . . . . }
. . . . . . . }
. . . . . . }
. . . . . }
. . . . . Object {
. . . . . . ● members: List<Member> {
. . . . . . . Member {
. . . . . . . . ● key: String { "name" }
. . . . . . . . ● value: String { "age" }
. . . . . . . }
. . . . . . . Member {
. . . . . . . . ● key: String { "description" }
. . . . . . . . ● value: String { "Customer's age" }
. . . . . . . }
. . . . . . . Member {
. . . . . . . . ● key: String { "type" }
. . . . . . . . ● value: String { "number" }
. . . . . . . }
. . . . . . }
. . . . . }
. . . . }
. . . }
. . }
. }
}

In the next part, we'll define business rules to validate our JSON
configuration (for example, the possible values for each variable must be
of the same type), and we will use a query DSL to identify the tree nodes that violate these rules.

DEV Community: geoffreycopin

Build your own SQLite, Part 2: Scanning large tables

Erratum

A motivating example

B-tree interior pages

Scanning logic

Putting it all together

Conclusion

Build your own SQLite, Part 1: Listing tables

Building the test database

Bootstrapping the project

The SQLite file format

Want to support me?

Decoding Table B-tree leaf pages

Records

Table descriptions

Conclusion

Build a HTTP server with Rust and tokio - Part 1: serving static files

Connection reuse

Serving static files

Graceful shutdown

# Build a web server with Rust and tokio - Part 0: the simplest possible GET handler

Setting up our project

Accepting connections

Sending a response

Puting it all together

Build a custom Python linter in 5 minutes

Installation

Project setup

Starting the REPL

Rule1: wildcard imports (inspired by F403)

Rule2: Ambiguous variable name (inspired by E741)

Rule3: has_key() is deprecated (inspired by W601)

Creating the ruleset

Getting updates

Build a custom Javascript linter in 5 minutes

Installation

Starting the REPL

Rule1: use of the == operator

Rule2: functions with too many parameters

Rule3: JSX 'img' elements without an 'alt' attribute

Creating the ruleset

Getting updates

Build a custom Go linter in 5 minutes

Installation

Starting the REPL

Rule1: detect struct declarations with too many fields

Rule2: suggest the usage of assignment operators

Rule3: incorrect usage of the make builtin function

Creating the ruleset

Getting started with Sylver - Part3/3 : From queries to analyzer

Prelude

Stepping out of the REPL

Creating a ruleset

Storing our project configuration

Git integration

Conclusion

Getting started with Sylver - Part2/3 : Intuitive JSON AST queries

Prelude

Basic REPL usage

Query language basics

Rule 1: variable descriptions should be shorter than 35 characters

Rule 2: variable names should be a single lowercase word

Rule 3: fields type and values should be mutually exclusive

Conclusion

Getting started with Sylver - Part1 : Building a JSON parser in 49 lines of code

Installation

Prelude

Types definition

Lexical analysis

Syntactic analysis

Conclusion

Rule3: `has_key()` is deprecated (inspired by W601)

Rule1: use of the `==` operator

Rule3: incorrect usage of the `make` builtin function

Rule 3: fields `type` and `values` should be mutually exclusive