# Protocol Description Language

## Introduction

## Grammar

Beginning with the basics from which we'll construct the grammar, various characters and special variations thereof:

```

SP = " " // space 

HTAB = 0x09 // horizontal tab

VCHAR = 0x21-0x7E // visible ASCII character

VCHAR-ESCLESS = 0x20-0x5B | 0x5D-0x7E // visible ASCII character without "\"

WSP = SP | HTAB // whitespace

ALPHA = 0x41-0x5A | 0x61-0x7A // characters (lower and upper case)

DIGIT = 0x30-0x39 // digit

NEWLINE = (0x15 0x0A) | 0x0A // carriage return and line feed, or just line feed

// Classic backslash escaping to produce particular ASCII charcters

ESCAPE_CHAR = "\"

ESCAPED_CHARS = 

    ESCAPE_CHAR ESCAPE_CHAR |

    ESCAPE_CHAR "t" |

    ESCAPE_CHAR "r" |

    ESCAPE_CHAR "n" |

    ESCAPE_CHAR "0" |

    ESCAPE_CHAR "'" |

    ESCAPE_CHAR """

```

Which are composed into the following components of an input file that do not directly contribute towards the AST:

```

// asterisk followed by any ASCII char, excluding "/", or just any ASCII char without "*"

block-comment-contents = "*" (0x00-0x2E | 0x30-0x7E) | (0x20-0x29 | 0x2B-0x7E)

block-comment = "/*" block-comment-contents* "*/"

line-comment = "//" (WSP | VCHAR)* NEWLINE

comment = block-comment | line-comment

cw = (comment | WSP | NEWLINE)*

cwb = (comment | WSP | newline)+

```

Where it should be noted that the `cw` rule allows for not encountering any of the indicated characters, while the `cwb` rule expects at least one instance.

The following operators are defined:

```

binary-operator = "||" | "&&" | 

                  "!=" | "==" | "<=" | ">=" | "<" | ">" |

                  "|" | "&" | "^" | "<<" | ">>" |

                  "+" | "-" | "*" | "/" | "%"

assign-operator = "=" |

                  "|=" | "&=" | "^=" | "<<=" | ">>=" |

                  "+=" | "-=" | "*=" | "/=" | "%="

unary-operator = "++" | "--" | "+" | "-" | "~" | "!"

```

**QUESTION**: Do we include the pre/postfix "++" and "--" operators? They were introduced in C to reduce the amount of required characters. But is still necessary?

And to define various constants in the language, we allow for the following:

```

// Various integer constants, binary, octal, decimal, or hexadecimal, with a 

// utility underscore to enhance humans reading the characters. Allowing use to

// write something like 100_000_256 or 0xDEAD_BEEF

int-bin-char = "0" | "1"

int-bin-constant = "0b" int-bin-char (int-bin-char | "_")* // 0b0100_1110

int-oct-char = "0"-"7"

int-oct-constant = "0o" int-oct-char (int-oct-char | "_")* // 0o777

int-dec-constant = DIGIT (DIGIT | "_")* //

int-hex-char = DIGIT | "a"-"f" | "A"-"F" 

int-hex-constant = "0x" int-hex-char (int-hex-char | "_")* // 0xFEFE_1337

int-constant = int-bin-constant | int-oct-constant | int-dec-constant | int-hex-constant

// Floating point numbers

//  language, but might be useful? 

float-constant = DIGIT* "." DIGIT+

// Character constants: a single character. Its element may be an escaped 

// character or a VCHAR (excluding "'" and "\")

char-element = ESCAPED_CHARS | (0x20-0x26 | 0x28-0x5B | 0x5D-0x7E) 

char-constant = "'" char-element "'"

// Same thing for strings, but these may contain 0 or more characters

str-element = ESCAPED_CHARS | (0x20-0x21 | 0x23-0x5B | 0x5D-0x7E)

str-constant = """ str-element* """

```

Note that the integer characters are forced, somewhat arbitrarily without hampering the programmer's expressiveness, to start with a valid digit. Only then may one introduce the `_` character. And non-rigorously speaking characters may not contain an unescaped `'`-character, and strings may not contain an unescaped `"`-character.

We now introduce the various identifiers that exist within the language, we make a distinction between "any identifier" and "any identifier except for the builtin ones". Because we h

```

identifier-any = ALPHA | (ALPHA | DIGIT | "_")*

keyword = 

    "composite" | "primitive" |

    type-primitive | "true" | "false" | "null" |

    "struct" | "enum" |

    "if" | "else" |

    "while" | "break" | "continue" | "return" |

    "synchronous" | "assert" |

    "goto" | "skip" | "new" | "let"

builtin = "put" | "get" | "fires" | "create" | "assert"

identifier = identifier-any WITHOUT (keyword | builtin)

// Identifier with any number of prefixed namespaces

ns-identifier = (identifier "::")* identifier

```

We then start introducing the type system. Learning from the "mistake" of C/C++ of having types like `byte` and `short` with unspecified and compiler-dependent byte-sizes (followed by everyone using `stdint.h`), we use the Rust/Zig-like `u8`, `i16`, etc. Currently we will limit the programmer to not produce integers which take up more than 64 bits. Furthermore, as one is writing network code, it would be quite neat to be able to put non-byte-aligned integers into a struct in order to directly access meaningful bits. Hence, with restrictions introduced later, we will allow for types like `i4` or `u1`. When actually retrieving them or performing computations with them we will use the next-largest byte-size to operate on them in "registers".

**Question**: Difference between u1 and bool? Do we allow assignments between them? What about i1 and bool?

As the language semantics are value-based, we are prevented from returning information from functions through its arguments. We may only return information through its (single) return value. If we consider the common case of having to parse a series of bytes into a meaningful struct, we cannot return both the struct and a value as a success indicator. For this reason, we introduce algebraic datatypes (or: tagged unions, or: enums) as well.

Lastly, since functions are currently without internal side-effects (since functions cannot perform communication with components, and there is no functionality to interact "with the outside world" from within a function), it does not make sense to introduce the "void" type, as found in C/C++ to indicate that a function doesn't return anything of importance. However, internally we will allow for a "void" type, this will allow treating builtins such as "assert" and "put" like functions while constructing and evaluating the AST.

```

// The digits 1-64, without any leading zeros allowed, to allow specifying the

// signed and unsigned integer types

number-1-64 = NZ-DIGIT | (0x31-0x35 DIGIT) | ("6" 0x30-0x34)

type-signed-int = "i" number-1-64 // i1 through i64

type-unsigned-int = "u" number-1-64 // u1 through u64

// Standard floats and bools

type-float = "f32" | "f64"

type-bool = "bool"

// Messages, may be removed later

type-msg = "msg"

// Indicators of port types

type-port = "in" | "out"

// Unions and tagged unions, so we allow:

// enum SpecialBool { True, False }

// enum SpecialBool{True,False,}

// enum Tagged{Boolean(bool),SignedInt(i64),UnsignedInt(u64),Nothing}

type-union-element = identifier cw (("(" cw type cw ")") | ("=" cw int-constant))? 

type-union-def = "enum" cwb identifier cw "{" cw type-union-element (cw "," cw type-union-element)* (cw ",")? cw "}"

// Structs, so we allow:

// struct { u8 type, u2 flag0, u6 reserved }

type-struct-element = type cwb identifier

type-struct-def = "struct" cwb identifier cw "{" cw type-struct-element (cw "," cw type-struct-element)* (cw ",")? cw "}"

type-primitive = type-signed-int |

    type-unsigned-int |

    type-float |

    type-bool |

    type-msg |

    type-port

// A type may be a user-defined type (e.g. "struct Bla"), a namespaced

// user type (e.g. "Module::Bla"), or a non-namespaced primitive type. We 

// currently have no way (yet) to access nested modules, so we don't need to 

// care about identifier nesting.

type = type-primitive | ns-identifier

```

With these types, we need to introduce some extra constant types. Ones that are used to construct struct instances and ones that are used to construct/assign enums. These are constructed as:

```

// Struct literals

struct-constant-element = identifier cw ":" cw expr

struct-constant = ns-identifier cw "{" cw struct-constant-element (cw "," struct-constant-element)* cw "}"

enum-constant = ns-identifier "::" identifier cw "(" cw expr cw ")" 

```

Finally, we declare methods and field accessors as:

```

method = builtin | ns-identifier

field = "length" | identifier

```

**Question**: This requires some discussion. We allow for a "length" field on messages, and allow the definition of arrays. But if we wish to perform computation in a simple fashion, we need to allow for variable-length arrays of custom types. This requires builtin methods like "push", "pop", etc. But I suppose there is a much nicer way... In any case, this reminds me of programming in Fortran, which I definitely don't want to impose on other people (that, or I will force 72-character line lengths on them as well)

When we parse a particular source file, we may expect the following "pragmas" to be sprinkled at the top of the source

file. They may exist at any position in the global scope of a source file.

```

// A domain identifier is a dot-separated sequence of identifiers. As these are

// only used to identify modules we allow any identifier to be used in them. 

// The exception is the last identifier, which we, due to namespacing rules,

// force to be a non-reserved identifier.

domain-identifier = (identifier-any ".")* identifier

pragma-version = "#version" cwb int-constant cw ";" // e.g. #version 500

pragma-module = "#module" cwb domain-identifier cw ";" // e.g. #module hello.there

// Import, e.g.

// #import module.submodule // access through submodule::function(), or submodule::Type

// #import module.submodule as Sub // access through Sub::function(), or Sub::type

// #import module.submodule::* // access through function(), or Type

// #import module.submodule::{function} // access through function()

// #import module.submodule::{function as func, type} // access through func() or type

pragma-import-alias = cwb "as" cwb identifier

pragma-import-all = "::*"

pragma-import-single-symbol = "::" identifier pragma-import-alias?

pragma-import-multi-symbol = "::{" ...

    cw identifier pragma-import-alias? ...

    (cw "," cw identifier pragma-import-alias?)* ...

    (cw ",")? cw "}"

pragma-import = "#import" cwb domain-identifier ...

    (pragma-import-alias | pragma-import-all | pragma-import-single-symbol | pragma-import-multi-symbol)? 

// Custom pragmas for people which may be using (sometime, somewhere) 

// metaprogramming with pragmas

pragma-custom = "#" identifier-any (cwb VCHAR (VCHAR | WS)*) cw ";"

// Finally, a pragma may be any of the ones above

pragma = pragma-version | pragma-module | pragma-import | pragma-custom

```

Note that, different from C-like languages, we do require semicolons to exist at the end of a pragma statement. The reason is to prevent future hacks using the "\" character to indicate an end-of-line-but-not-really-end-of-line statements.

Apart from these pragmas, we can have component definitions, type definitions and function definitions within the source file. The grammar for these may be formulated as:

```

// Annotated types and function/component arguments

type-annotation = type (cw [])?

var-declaration = type-annotation cwb identifier

params-list = "(" cw (var-declaration (cw "," cw var-declaration)*)? cw ")"

// Functions and components

function-def = type-annotation cwb identifier cw params-list cw block

composite-def = "composite" cwb identifier cw params-list cw block

primitive-def = "primitive" cwb identifier cw params-list cw block

component-def = composite-def | primitive-def

// Symbol definitions now become

symbol-def = type-union-def | type-struct-def | function-def | component-def 

```

Using these rules, we can now describe the grammar of a single file as:

```

file = cw (pragma | symbol-def)* cw

```

Of course, we currently cannot do anything useful with our grammar, hence we have to describe blocks to let the functions and component definitions do something. To do so, we proceed as:

```

// channel a->b;, or channel a -> b;

channel-decl = channel cwb identifier cw "->" cw identifier cw ";"

// int a = 5, b = 2 + 3;

memory-decl = var-declaration cw "=" cw expression (cw "," cw identifier cw "=" cw expression)* cw ";"

stmt = block |

    identifier cw ":" cw stmt | // label

    "if" cw pexpr cw stmt (cw "else" cwb stmt)? |

    "while" cw pexpr cw stmt |

    "break" (cwb identifier)? cw ";" |

    "continue" (cwb identifier)? cw ";" |

    "synchronous" stmt |

    "return" cwb identifier cw ";" |

    "goto" cwb identifier cw ";" |

    "skip" cw ";" |

    "new" cwb method-expr cw ";" |

    expr cw ";"

method-params-list = "(" cw (expr (cw "," cw expr)* )? cw ")"

method-expr = method cw method-params-list

enum-destructure-expr = "let" cw ns-identifier "::" identifier cw "(" cw identifier cw ")" cw "=" expr

enum-test-expr = ns-identifier "::" identifier cw "==" cw expr

block = "{" (cw (channel-decl | memory-decl | stmt))* cw "}"

```

Note that we have a potential collision of various expressions/statements. The following cases are of importance:

1. An empty block is written as `{}`, while an empty array construction is also written as `{}`.

2. Both function calls as enum constants feature the same construction syntax. That is: `foo::bar(expression)` may refer to a function call to `bar` in the namespace `foo`, but may also be the construction of enum `foo`'s `bar` variant (containing a value `expression`). These may be disambiguated using the type system.

3. The enumeration destructuring expression may collide with the constant enumeration literal. These may be disambiguated by looking at the inner value. If the inner value is an identifier and not yet defined as a variable, then it is a destructuring expression. Otherwise it must be interpreted as a constant enumeration. The enumeration destructuring expression must then be completed by it being a child of an binary equality operator. If not, then it is invalid syntax.

Finally, for consistency, there are additional rules to the enumeration destructuring. As a preamble: the language should allow programmers to express any kind of trickery they want, as long as it is correct. But programmers should be prevented from expressing something that is by definition incorrect/illogical. So enumeration destructuring (e.g. `Enum::Variant(bla) == expression`) should return a value with a special type (e.g. `EnumDestructureBool`) that may only reside within the testing expressions of `if` and `while` statements. Furthermore, this special boolean type only supports the logical-and (`&&`) operator. This way we prevent invalid expressions such as `if (Enum::Variant1(foo) == expr || Enum::Variant2(bar) == expr) { ... }`, but we do allow potentially valid expressions like `if (Enum::Variant1(foo) == expr_foo && Enum::Variant2(bar) == expr_bar) { ... }`.

**Question**: In the documentation for V1.0 we find the `synchronous cw (params-list cw stmt | block)` rule. Why the `params-list`?

**TODO**: Release constructions on memory declarations: as long as we have a write to it before a read we should be fine. Can be done once we add semantic analysis in order to optimize putting and getting port values.

**TODO**: Implement type inference, should be simpler once I figure out how to write a typechecker.

**TODO**: Add constants assigned in the global scope.

**TODO**: Add a runtime expression evaluator (probably before constants in global scope) to simplify expressions and/or remove impossible branches.

use std::marker::PhantomData;

use alloc::raw_vec::RawVec;

/// Entry in a freelist. Contains a generation number to ensure silly mistakes

/// using an item's index after freeing it.

struct Entry<T> {

    generation: usize,

    item: T,

}

/// Key of an item in the freelist. Contains a generation number to prevent

/// use-after-free during development.

// TODO: Two usizes are probably overkill

#[derive(Copy, Clone)]

pub struct Key<T> {

    generation: usize,

    index: usize,

    _type: PhantomData<T>,

}

/// Generic freelist structure. Item insertion/retrieval/deletion works like a

/// HashMap through keys.

pub struct FreeList<T> {

    items: *mut Entry<T>,

    capacity: usize,

    length: usize,

    free: Vec<usize>,

}

impl<T> FreeList<T> {

    pub fn new() -> Self<T> {

        std::alloc::Layout::from_size_align()

        Self{

            items: std::ptr::null_mut(),

            capacity: 0,

            length: 0,

            free: Vec::new(),

        }

    }

    pub fn with_capacity(capacity: usize) -> Self {

        alloc::

        Self{

            items: std::,

            free: Vec::with_capacity(capacity),

            length: 0,

        }

    }

    /// Inserts a new item into the freelist. Will return a key that can be used

    /// to retrieve the item and delete it.

    pub fn insert(&mut self, item: T) -> Key<T> {

        let mut generation;

        let mut index;

        if self.free.is_empty() {

            // No free elements, make sure we have enough capacity

            if self.length == self.items.capacity() {

                self.items.reserve(self.length, 1);

            }

            // Now we do

            generation = 0;

            index = self.length;

            unsafe {

                let target = self.items.ptr().add(self.length);

                std::ptr::write(&mut target.item, item);

                self.length += 1;

            }

        } else {

            // We have a free spot. Note that the generation is incremented upon

            // freeing an item. So we can just take the current generation value

            // here.

            index = self.free.pop().unwrap();

            unsafe {

                let target = self.items.ptr().add(self.length);

                generation = target.generation;

                std::ptr::write(&mut target.item, item);

            }

        }

        Key { generation, index, _type: PhantomData::default() }

    }

    /// Removes the entry using the provided key. Will panic if the element was

    /// removed already.

    pub fn erase(&mut self, index: Key<T>) {

        // This should always be the case

        debug_assert!(index.index < self.length);

        // Retrieve element and make sure that the generation matches

        unsafe {

            let entry = self.items.ptr().add(index.index);

            assert_eq!(entry.generation, entry.generation);

            *entry.generation += 1;

            std::ptr::drop_in_place(&mut entry.item);

        }

        // Add the entry to the freelist.

        self.free.push(index.index);

    }

}

impl<T> std::ops::Index<Key<T>> for FreeList<T> {

    type Output = T;

    fn index(&self, index: &Key<T>) -> &Self::Output {

        debug_assert!(index.index < self.length);

        unsafe {

            let entry = self.items.ptr().add(index.index);

            assert_eq!(entry.generation, index.generation);

            return &entry.item;

        }

    }

}

impl<T> std::ops::IndexMut<Key<T>> for FreeList<T> {

    fn index_mut(&self, index: &Key<T>) -> &Self::Output {

        debug_assert!(index.index < self.length);

        unsafe {

            let entry = self.items.ptr().add(index.index);

            assert_eq!(entry.generation, index.generation);

            return &mut entry.item;

        }

    }

}

impl<T> Drop for FreeList<T> {

    fn drop(&mut self) {

        // Sort free indices to use them while traversing the allocated items

        self.free.sort_unstable();

        let free_length = self.free.len();

        let mut next_free_idx = 1;

        let mut next_free_item = usize::MAX;

        if free_length != 0 {

            next_free_item = self.free[0];

        }

        // Go through all items. If we didn't yet drop the item, then we do

        // so here.

        for item_idx in 0..self.length {

            if item_idx == next_free_item {

                if next_free_idx < free_length {

                    next_free_item = self.free[next_free_idx];

                    next_free_idx += 1;

                } else {

                    next_free_item = usize::MAX;

                }

                // Skipped the current item, go to the next one

                continue

            }

            // Need to deallocate the current item

            unsafe {

                let entry = self.items.ptr().add(item_idx);

                std::ptr::drop_in_place(&mut entry.item);

            }

        }

    }

}

#[cfg(test)]

mod tests {

    use super::*;

    use std::sync::Arc;

    use std::sync::atomic::{AtomicU32, Ordering};

    struct Counters {

        constructed: Arc<AtomicU32>,

        destructed: Arc<AtomicU32>,

    }

    impl Counters {

        pub fn new() -> Self {

            Self{

                constructed: Arc::new(AtomicU32::new(0)),

                destructed: Arc::new(AtomicU32::new(0)),

            }

        }

    }

    struct TestEntity {

        counters: Counters,

        pub value: u32,

    }

    impl TestEntity {

        pub fn new(counters: &Counters, value: u32) -> Self {

            counters.constructed.fetch_add(1, Ordering::SeqCst);

            return TestEntity{

                counters: Counters{

                    constructed: counters.constructed.clone(),

                    destructed: counters.destructed.clone(),

                },

                value,

            }

        }

    }

    impl Drop for TestEntity {

        fn drop(&mut self) {

            self.counters.destructed.fetch_add(1, Ordering::SeqCst);

        }

    }

    #[test]

    fn only_constructing() {

        const NUM_CREATED: u32 = 3;

        let counters = Counters::new();

        let mut list = FreeList::new();

mod string_pool;

mod scoped_buffer;

mod sets;

mod raw_vec;

// mod freelist;

pub(crate) use string_pool::{StringPool, StringRef};

pub(crate) use scoped_buffer::{ScopedBuffer, ScopedSection};

pub(crate) use sets::{DequeSet, VecSet};

pub(crate) use raw_vec::RawVec;

use std::ptr::null_mut;

use std::hash::{Hash, Hasher};

use std::marker::PhantomData;

use std::fmt::{Debug, Display, Result as FmtResult};

use crate::common::Formatter;

const SLAB_SIZE: usize = u16::MAX as usize;

#[derive(Clone)]

pub struct StringRef<'a> {

    data: *const u8,

    length: usize,

    _phantom: PhantomData<&'a [u8]>,

}

// As the StringRef is an immutable thing:

unsafe impl Sync for StringRef<'_> {}

unsafe impl Send for StringRef<'_> {}

impl<'a> StringRef<'a> {

    /// `new` constructs a new StringRef whose data is not owned by the

    /// `StringPool`, hence cannot have a `'static` lifetime.

    pub(crate) fn new(data: &'a [u8]) -> StringRef<'a> {

        // This is an internal (compiler) function: so debug_assert that the

        // string is valid ascii. Most commonly the input will come from the

        // code's source file, which is checked for ASCII-ness anyway.

        debug_assert!(data.is_ascii());

        let length = data.len();

        let data = data.as_ptr();

        StringRef{ data, length, _phantom: PhantomData }

    }

    pub fn as_str(&self) -> &'a str {

        unsafe {

            let slice = std::slice::from_raw_parts::<'a, u8>(self.data, self.length);

            std::str::from_utf8_unchecked(slice)

        }

    }

    pub fn as_bytes(&self) -> &'a [u8] {

        unsafe {

            std::slice::from_raw_parts::<'a, u8>(self.data, self.length)

        }

    }

}

impl<'a> Debug for StringRef<'a> {

    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {

        f.write_str("StringRef{ value: ")?;

        f.write_str(self.as_str())?;

        f.write_str(" }")

    }

}

impl<'a> Display for StringRef<'a> {

    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {

        f.write_str(self.as_str())

    }

}

impl PartialEq for StringRef<'_> {

    fn eq(&self, other: &StringRef) -> bool {

        self.as_str() == other.as_str()

    }

}

impl Eq for StringRef<'_> {}

impl Hash for StringRef<'_> {

    fn hash<H: Hasher>(&self, state: &mut H) {

        state.write(self.as_bytes());

    }

}

struct StringPoolSlab {

    prev: *mut StringPoolSlab,

    data: Vec<u8>,

    remaining: usize,

}

impl StringPoolSlab {

    fn new(prev: *mut StringPoolSlab) -> Self {

        Self{ prev, data: Vec::with_capacity(SLAB_SIZE), remaining: SLAB_SIZE }

    }

}

/// StringPool is a ever-growing pool of strings. Strings have a maximum size

/// equal to the slab size. The slabs are essentially a linked list to maintain

/// pointer-stability of the strings themselves.

/// All `StringRef` instances are invalidated when the string pool is dropped

pub(crate) struct StringPool {

    last: *mut StringPoolSlab,

}

impl StringPool {

    pub(crate) fn new() -> Self {

        // To have some stability we just turn a box into a raw ptr.

        let initial_slab = Box::new(StringPoolSlab::new(null_mut()));

        let initial_slab = Box::into_raw(initial_slab);

        StringPool{

            last: initial_slab,

        }

    }

    /// Interns a string to the `StringPool`, returning a reference to it. The

    /// pointer owned by `StringRef` is `'static` as the `StringPool` doesn't

    /// reallocate/deallocate until dropped (which only happens at the end of

    /// the program.)

    pub(crate) fn intern(&mut self, data: &[u8]) -> StringRef<'static> {

        let data_len = data.len();

        debug_assert!(std::str::from_utf8(data).is_ok(), "string to intern is not valid UTF-8 encoded");

        let mut last = unsafe{&mut *self.last};

        if data.len() > last.remaining {

            // Doesn't fit: allocate new slab

            self.alloc_new_slab();

            last = unsafe{&mut *self.last};

        }

        // Must fit now, compute hash and put in buffer

        debug_assert!(data_len <= last.remaining);

        let range_start = last.data.len();

        last.data.extend_from_slice(data);

        last.remaining -= data_len;

        debug_assert_eq!(range_start + data_len, last.data.len());

        unsafe {

            let start = last.data.as_ptr().offset(range_start as isize);

            StringRef{ data: start, length: data_len, _phantom: PhantomData }

        }

    }

    fn alloc_new_slab(&mut self) {

        let new_slab = Box::new(StringPoolSlab::new(self.last));

        let new_slab = Box::into_raw(new_slab);

        self.last = new_slab;

    }

}

impl Drop for StringPool {

    fn drop(&mut self) {

        let mut new_slab = self.last;

        while !new_slab.is_null() {

            let cur_slab = new_slab;

            unsafe {

                new_slab = (*cur_slab).prev;

                Box::from_raw(cur_slab); // consume and deallocate

            }

        }

    }

}

// String pool cannot be cloned, and the created `StringRef` instances remain

// allocated until the end of the program, so it is always safe to send. It is

// also sync in the sense that it becomes an immutable thing after compilation,

// but lets not derive that if we would ever become a multithreaded compiler in

// the future.

unsafe impl Send for StringPool {}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test_string_just_fits() {

        let large = "0".repeat(SLAB_SIZE);

        let mut pool = StringPool::new();

        let interned = pool.intern(large.as_bytes());

        assert_eq!(interned.as_str(), large);

    }

    #[test]

    #[should_panic]

    fn test_string_too_large() {

        let large = "0".repeat(SLAB_SIZE + 1);

        let mut pool = StringPool::new();

        let _interned = pool.intern(large.as_bytes());

    }

    #[test]

    fn test_lots_of_small_allocations() {

        const NUM_PER_SLAB: usize = 32;

        const NUM_SLABS: usize = 4;

        let to_intern = "0".repeat(SLAB_SIZE / NUM_PER_SLAB);

        let mut pool = StringPool::new();

        let mut last_slab = pool.last;

        let mut all_refs = Vec::new();

        // Fill up first slab

        for _alloc_idx in 0..NUM_PER_SLAB {

            let interned = pool.intern(to_intern.as_bytes());

            all_refs.push(interned);

            assert!(std::ptr::eq(last_slab, pool.last));

        }

        for _slab_idx in 0..NUM_SLABS-1 {

            for alloc_idx in 0..NUM_PER_SLAB {

                let interned = pool.intern(to_intern.as_bytes());

                all_refs.push(interned);

                if alloc_idx == 0 {

                    // First allocation produces a new slab

                    assert!(!std::ptr::eq(last_slab, pool.last));

                    last_slab = pool.last;

                } else {

                    assert!(std::ptr::eq(last_slab, pool.last));

                }

            }

        }

        // All strings are still correct

        for string_ref in all_refs {

            assert_eq!(string_ref.as_str(), to_intern);

        }

    }

}

use std::fmt;

use std::fmt::{Debug, Display, Formatter};

use std::ops::{Index, IndexMut};

use super::arena::{Arena, Id};

use crate::collections::StringRef;

use crate::protocol::input_source::InputSpan;

/// Helper macro that defines a type alias for a AST element ID. In this case 

/// only used to alias the `Id<T>` types.

macro_rules! define_aliased_ast_id {

    // Variant where we just defined the alias, without any indexing

    ($name:ident, $parent:ty) => {

        pub type $name = $parent;

    };

    // Variant where we define the type, and the Index and IndexMut traits

    (

        $name:ident, $parent:ty, 

        index($indexed_type:ty, $indexed_arena:ident)

    ) => {

        define_aliased_ast_id!($name, $parent);

        impl Index<$name> for Heap {

            type Output = $indexed_type;

            fn index(&self, index: $name) -> &Self::Output {

                &self.$indexed_arena[index]

            }

        }

        impl IndexMut<$name> for Heap {

            fn index_mut(&mut self, index: $name) -> &mut Self::Output {

                &mut self.$indexed_arena[index]

            }

        }

    };

    // Variant where we define type, Index(Mut) traits and an allocation function

    (

        $name:ident, $parent:ty,

        index($indexed_type:ty, $indexed_arena:ident),

        alloc($fn_name:ident)

    ) => {

        define_aliased_ast_id!($name, $parent, index($indexed_type, $indexed_arena));

        impl Heap {

            pub fn $fn_name(&mut self, f: impl FnOnce($name) -> $indexed_type) -> $name {

                self.$indexed_arena.alloc_with_id(|id| f(id))

            }

        }

    };

}

/// Helper macro that defines a wrapper type for a particular variant of an AST

/// element ID. Only used to define single-wrapping IDs.

macro_rules! define_new_ast_id {

    // Variant where we just defined the new type, without any indexing

    ($name:ident, $parent:ty) => {

        #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]

        pub struct $name (pub(crate) $parent);

        #[allow(dead_code)]

        impl $name {

            pub(crate) fn new_invalid() -> Self     { Self(<$parent>::new_invalid()) }

            pub(crate) fn is_invalid(&self) -> bool { self.0.is_invalid() }

            pub fn upcast(self) -> $parent          { self.0 }

        }

    };

    // Variant where we define the type, and the Index and IndexMut traits

    (

        $name:ident, $parent:ty, 

        index($indexed_type:ty, $wrapper_type:path, $indexed_arena:ident)

    ) => {

        define_new_ast_id!($name, $parent);

        impl Index<$name> for Heap {

            type Output = $indexed_type;

            fn index(&self, index: $name) -> &Self::Output {

                if let $wrapper_type(v) = &self.$indexed_arena[index.0] {

                    v

                } else {

                    unreachable!()

                }

            }

        }

        impl IndexMut<$name> for Heap {

            fn index_mut(&mut self, index: $name) -> &mut Self::Output {

                if let $wrapper_type(v) = &mut self.$indexed_arena[index.0] {

                    v

                } else {

                    unreachable!()

                }

            }

        }

    };

    // Variant where we define the type, the Index and IndexMut traits, and an allocation function

    (

        $name:ident, $parent:ty, 

        index($indexed_type:ty, $wrapper_type:path, $indexed_arena:ident),

        alloc($fn_name:ident)

    ) => {

        define_new_ast_id!($name, $parent, index($indexed_type, $wrapper_type, $indexed_arena));

        impl Heap {

            pub fn $fn_name(&mut self, f: impl FnOnce($name) -> $indexed_type) -> $name {

                $name(

                    self.$indexed_arena.alloc_with_id(|id| {

                        $wrapper_type(f($name(id)))

                    })