mdbook_extended_markdown_table/

extended_table.rs

use anyhow::{bail, Result};

struct ExtendedTableCell {
    start_column: usize,
    width: usize,
    start_row: usize,
    height: usize,
    contents: String,
}

impl ExtendedTableCell {
    fn is_header(&self) -> bool {
        self.start_row == 0
    }

    fn is_left_border(&self) -> bool {
        self.start_column == 0
    }

    fn into_html(self) -> String {
        let mut classes = vec![];
        if self.is_header() {
            classes.push("extended-markdown-header");
        }
        if self.is_left_border() {
            classes.push("extended-markdown-left-border");
        }
        let classes = classes.join(" ");

        format!(
            r#"<div class="{}" style="grid-column-start: {}; grid-column-end: {}; grid-row-start: {}; grid-row-end: {}">{}</div>"#,
            classes,
            self.start_column + 1,
            self.start_column + 1 + self.width,
            self.start_row + 1,
            self.start_row + 1 + self.height,
            self.contents
        )
    }
}

pub struct ExtendedTable {
    cells: Vec<ExtendedTableCell>,
}

impl ExtendedTable {
    pub fn parse(contents: &str) -> Result<Self> {
        let lines_count = contents.lines().count();
        if lines_count == 0 {
            bail!("Table cannot be empty");
        } else if lines_count % 2 == 0 {
            bail!("Table must have an odd number of lines: lines must alternate between grid content and horizontal separators, with no separators on the top or bottom");
        }
        let width_chars = contents.lines().next().unwrap().chars().count();

        // Holds all the indices of a '|' character within _any_ of the lines of the table. This is
        // used to determine the ground truth for locations of column separators.
        let mut all_column_separators = std::collections::HashSet::<usize>::new();

        let mut has_zero_column_row = false;

        for line in contents.lines() {
            let line_length = line.chars().count();
            if !line.starts_with('|') || !line.ends_with('|') || line_length != width_chars {
                bail!("All lines of a tables must start and end with a '|' character, and be the same length");
            }

            let mut num_columns = 0;
            for (i, c) in line.chars().enumerate() {
                if c == '|' {
                    all_column_separators.insert(i);
                    if i != 0 {
                        num_columns += 1;
                    }
                }
            }

            // The previous error should have precedence in the case of `|` on the first line, so
            // we defer this until after checking all lines
            if num_columns < 1 {
                has_zero_column_row = true;
            }
        }

        if has_zero_column_row {
            bail!("Tables must have at least one column");
        }

        // Convert the above HashMap into a sorted Vec instead, for easier iteration.
        let mut all_column_separators: Vec<_> = all_column_separators.into_iter().collect();
        all_column_separators.sort();

        // Find all the locations of cell boundaries within a base unit grid template.
        let unit_cell_boundaries = Self::get_cell_boundaries(contents, &all_column_separators);

        // Fun algorithm time!
        // Iterate through the rows to discover the rightmost boundaries of cells in the output.
        // Store the row on which each right boundary starts in `last_vertical_separator_indices`.
        // When a bottom-right corner of a cell is found, record its dimensions and contents, and
        // store it into `cells`.
        let mut cells = vec![];
        let mut last_vertical_separator_indices: Vec<usize> =
            vec![0; unit_cell_boundaries[0].len()];
        for row in 0..unit_cell_boundaries.len() {
            let mut last_horizontal_separator_index = 0;
            for col in 0..unit_cell_boundaries[0].len() {
                // Cell's bottom-right corner
                if unit_cell_boundaries[row][col].right && unit_cell_boundaries[row][col].bottom {
                    let start_column = last_horizontal_separator_index;
                    let width = col + 1 - last_horizontal_separator_index;
                    let start_row = last_vertical_separator_indices[col];
                    let height = row - last_vertical_separator_indices[col] + 1;

                    let mut cell_contents = String::new();
                    let content_start = all_column_separators[start_column] + 1;
                    let content_len = all_column_separators[col + 1] - content_start;
                    let lines = contents.lines().skip(start_row * 2);
                    for line in lines.take(height * 2 - 1) {
                        let additional_text = line
                            .chars()
                            .skip(content_start)
                            .take(content_len)
                            .collect::<String>()
                            .trim()
                            .to_string();
                        let padding = if cell_contents.is_empty() || additional_text.is_empty() {
                            ""
                        } else {
                            " "
                        };
                        cell_contents = format!("{}{}{}", cell_contents, padding, additional_text);
                    }

                    cells.push(ExtendedTableCell {
                        start_column,
                        width,
                        start_row,
                        height,
                        contents: cell_contents,
                    });
                }
                // Cell's right border - cache the start row of the next cell to the right
                if unit_cell_boundaries[row][col].right {
                    last_horizontal_separator_index = col + 1;
                }
                // Cell's bottom border - cache the start column of the next cell below
                if unit_cell_boundaries[row][col].bottom {
                    last_vertical_separator_indices[col] = row + 1;
                }
            }
        }

        Ok(Self { cells })
    }

    /// Constructs a 2D array with the dimensions of the intended table's base geometry (i.e. as if
    /// no cells were merged). Each element describes whether or not the corresponding cell
    /// location in the table has a border separating it from the cell immediately to its right, as
    /// well as from the cell immediately below it. Each cell in the rightmost column always has a
    /// right border, and each cell in the bottom row always has a bottom border.
    fn get_cell_boundaries(
        contents: &str,
        all_column_separator_indices: &[usize],
    ) -> Vec<Vec<CellBoundaries>> {
        // First, just look for each potential cell's boundary separating it from the cell
        // immediately to its right.
        let all_horizontal_separators = contents.lines().step_by(2).map(|line| {
            // offset by 1 because we skip the first column separator
            let mut chars: Box<dyn Iterator<Item = char>> = Box::new(line.chars().skip(1));
            let mut last_index = 0;
            let mut seps = Vec::with_capacity(all_column_separator_indices.len());
            for column_separator_index in all_column_separator_indices.iter().skip(1) {
                chars = Box::new(chars.skip(*column_separator_index - last_index - 1));
                let sep = chars.next().unwrap();
                seps.push(sep == '|');
                last_index = *column_separator_index;
            }
            seps
        });

        // Same as before, but for each potential cell's boundary separating it from the cell
        // immediately below. **All** of the characters within a separator must be a dash in order
        // to count as a boundary.
        let all_vertical_separators = contents
            .lines()
            .skip(1)
            .step_by(2)
            .map(|line| {
                let mut chars = line.chars();
                let mut seps = Vec::with_capacity(all_column_separator_indices.len() - 1);
                for window in
                    all_column_separator_indices[0..all_column_separator_indices.len()].windows(2)
                {
                    let left_column_separator_index = window[0];
                    let right_column_separator_index = window[1];

                    chars.by_ref().take(1).for_each(drop);

                    let mut consumed = 0;
                    let to_consume = right_column_separator_index - left_column_separator_index - 1;
                    if chars.by_ref().take(to_consume).all(|c| {
                        consumed += 1;
                        c == '-'
                    }) {
                        seps.push(true);
                    } else {
                        chars.by_ref().take(to_consume - consumed).for_each(drop);
                        seps.push(false);
                    }
                }
                seps
            })
            // Add the bottom row, which doesn't actually exist in the source string
            .chain(std::iter::once(vec![
                true;
                all_column_separator_indices.len() - 1
            ]));

        // Combine the two together.
        all_horizontal_separators
            .zip(all_vertical_separators)
            .map(|(h_line, v_line)| {
                h_line
                    .into_iter()
                    .zip(v_line.into_iter())
                    .map(|(right, bottom)| CellBoundaries { right, bottom })
                    .collect()
            })
            .collect()
    }

    pub fn into_html(self) -> String {
        let mut contents: String = String::new();
        self.cells
            .into_iter()
            .for_each(|cell| contents += &cell.into_html());
        format!(r#"<div class="extended-markdown-table">{}</div>"#, contents)
    }
}

/// Records whether or not a unit position in a table grid has a boundary to its right and bottom.
/// A position without a boundary will be merged with the neighboring position.
struct CellBoundaries {
    /// Whether or not the position has a boundary between it and the position immediately to the
    /// right.
    right: bool,
    /// Whether or not the position has a boundary between it and the position immediately to the
    /// bottom.
    bottom: bool,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_simple() {
        let table = r###"
| Packet ID |       State        | Bound To | Field Name | Field Type |                    Notes                   |
|-----------|--------------------|----------|------------|------------|--------------------------------------------|
|      0x00 | Decentralized Auth | Client   | Reason     | Chat       | The reason why the player was disconnected |
"###.trim();

        let parsed = ExtendedTable::parse(table).unwrap();

        assert_eq!(parsed.cells.len(), 6 * 2);
    }

    #[test]
    fn test_complex() {
        let table = r###"
| Packet ID |       State        | Bound To |     Field Name       |       Field Type               |                    Notes                        |
|-----------|--------------------|----------|----------------------|--------------------------------|-------------------------------------------------|
|      0x03 | Decentralized Auth | Client   | Has Profile Data     | Boolean                        | Whether or not the remaining fields are present |
|           |                    |          |----------------------|--------------------------------|-------------------------------------------------|
|           |                    |          | UUID                 | UUID                           |                                                 |
|           |                    |          |----------------------|--------------------------------|-------------------------------------------------|
|           |                    |          | Username             | String (16)                    |                                                 |
|           |                    |          |----------------------|--------------------------------|-------------------------------------------------|
|           |                    |          | Number of Properties | VarInt                         | Number of elements in the following array       |
|           |                    |          |----------------------|--------------------------------|-------------------------------------------------|
|           |                    |          | Property | Name      | Array | String(32767)          |                                                 |
|           |                    |          |          |-----------|       |------------------------|-------------------------------------------------|
|           |                    |          |          | Value     |       | String(32767)          |                                                 |
|           |                    |          |          |-----------|       |------------------------|-------------------------------------------------|
|           |                    |          |          | Is Signed |       | Boolean                | Generally false for Decentralized Auth          |
|           |                    |          |          |-----------|       |------------------------|-------------------------------------------------|
|           |                    |          |          | Signature |       | Optional String(32767) | Only if Is Signed is true                       |
"###.trim();

        let parsed = ExtendedTable::parse(table).unwrap();

        assert_eq!(parsed.cells.len(), 6 + 3 + 3 * 4 + 1 + 4 + 1 + 4 * 2);

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents == "Field Name")
                .expect("find cell with `Field Name` as content");
            assert_eq!(cell.start_column, 3);
            assert_eq!(cell.width, 2);
            assert_eq!(cell.start_row, 0);
            assert_eq!(cell.height, 1);
        }

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents == "0x03")
                .expect("find cell with `0x03` as content");
            assert_eq!(cell.start_column, 0);
            assert_eq!(cell.width, 1);
            assert_eq!(cell.start_row, 1);
            assert_eq!(cell.height, 8);
        }

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents == "Array")
                .expect("find cell with `Array` as content");
            assert_eq!(cell.start_column, 5);
            assert_eq!(cell.width, 1);
            assert_eq!(cell.start_row, 5);
            assert_eq!(cell.height, 4);
        }
    }

    #[test]
    fn test_misaligned() {
        let table = r###"
| One col spanning multiple rows | Info | Another | More information |
|-------------------------------------------------|------------------|
|   ?   |  Another col overlapping the other one  |       null       |
"###
        .trim();

        let parsed = ExtendedTable::parse(table).unwrap();

        assert_eq!(parsed.cells.len(), 4 + 3);
    }

    #[test]
    fn test_multiline_wrapping() {
        let table = r###"
| One col spanning multiple rows | Info | Another | More information |
|-------------------------------------------------| could be         |
|   ?   |                                         |      appreciated |
|-------|   Another col overlapping the other one,|------------------|
|   no  |but this time,   it has a lot of text!   |       null       |
"###
        .trim();

        let parsed = ExtendedTable::parse(table).unwrap();

        assert_eq!(parsed.cells.len(), 3 + 2 + 1 + 2);

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents.starts_with("More information"))
                .expect("find cell starting with `More information` as content");
            assert_eq!(cell.start_column, 4);
            assert_eq!(cell.width, 1);
            assert_eq!(cell.start_row, 0);
            assert_eq!(cell.height, 2);
            assert_eq!(cell.contents, "More information could be appreciated");
        }

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents.starts_with("Another col"))
                .expect("find cell starting with `Another col` as content");
            assert_eq!(cell.start_column, 1);
            assert_eq!(cell.width, 3);
            assert_eq!(cell.start_row, 1);
            assert_eq!(cell.height, 2);
            assert_eq!(
                cell.contents,
                "Another col overlapping the other one, but this time,   it has a lot of text!"
            );
        }
    }

    #[test]
    fn test_large() {
        let table = r###"
|a|b|c|d|e|f|g|h|
|-|-|-------|-|-|
|i|j| chonk |k|l|
|-|-|       |-|-|
|m|n|       |o|p|
|-|-|       |-|-|
|q|r|       |s|t|
|-|-----------|-|
|u|  v  |  w  |x|
"###
        .trim();

        let parsed = ExtendedTable::parse(table).unwrap();

        assert_eq!(parsed.cells.len(), 8 + 2 * 3 + 1 + 2 * 3 + 4);

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents == "o")
                .expect("find cell with `o` as content");
            assert_eq!(cell.start_column, 6);
            assert_eq!(cell.width, 1);
            assert_eq!(cell.start_row, 2);
            assert_eq!(cell.height, 1);
        }

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents == "chonk")
                .expect("find cell with `chonk` as content");
            assert_eq!(cell.start_column, 2);
            assert_eq!(cell.width, 4);
            assert_eq!(cell.start_row, 1);
            assert_eq!(cell.height, 3);
        }

        {
            let cell = &parsed
                .cells
                .iter()
                .find(|cell| cell.contents == "v")
                .expect("find cell with `v` as content");
            assert_eq!(cell.start_column, 1);
            assert_eq!(cell.width, 3);
            assert_eq!(cell.start_row, 4);
            assert_eq!(cell.height, 1);
        }
    }

    #[test]
    fn test_separators() {
        let table = r###"
|a|b|c|d|e|f|g|h|
|-|-|-------|-|-|
|i|j| chonk |k|l|
|-|-|       |-|-|
|m|n|       |o|p|
|-|-|       |-|-|
|q|r|       |s|t|
|-|-----------|-|
|u|  v  |  w  |x|
"###
        .trim();

        let separators =
            ExtendedTable::get_cell_boundaries(table, &vec![0, 2, 4, 6, 8, 10, 12, 14, 16]);

        for i in 0..separators[0].len() {
            assert!(separators[0][i].right);
            assert!(separators[0][i].bottom);
        }

        for r in 1..3 {
            for i in [0, 1, 6, 7] {
                assert!(separators[r][i].right);
                assert!(separators[r][i].bottom);
            }
            for i in [2, 3, 4] {
                assert!(!separators[r][i].right);
                assert!(!separators[r][i].bottom);
            }
            assert!(separators[r][5].right);
            assert!(!separators[r][5].bottom);
        }

        for i in 0..separators[0].len() {
            assert!(separators[3][i].bottom);
        }

        for i in 0..separators[0].len() {
            assert!(separators[4][i].bottom);
        }
    }
}