mod string_pool;

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

use std::ptr::null_mut;

const SLAB_SIZE: usize = u16::max_value() as usize;

pub struct StringRef {

    data: *const u8,

    length: usize,

}

impl StringRef {

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

        unsafe {

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

            std::str::from_utf8_unchecked(slice)

        }

    }

}

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

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

        // TODO: Large string allocations, if ever needed.

        let data_len = data.len();

        assert!(data_len <= SLAB_SIZE, "string is too large for slab");

        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

        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 }

        }

    }

    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

            }

        }

    }

}

#[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);

        }

    }

}

mod collections;

use std::fmt;

use std::cell::{Ref, RefCell};

#[derive(Debug, Clone, Copy)]

pub struct InputPosition2 {

    pub line: u32,

    pub offset: u32,

}

pub struct InputSpan {

    pub begin: InputPosition2,

    pub end: InputPosition2,

}

impl InputSpan {

    #[inline]

    fn from_positions(begin: InputPosition2, end: InputPosition2) -> Self {

        Self { begin, end }

    }

}

/// Wrapper around source file with optional filename. Ensures that the file is

/// only scanned once.

pub struct InputSource2 {

    pub(crate) filename: String,

    pub(crate) input: Vec<u8>,

    // Iteration

    line: u32,

    offset: usize,

    // State tracking

    had_error: Option<ParseError>,

    // The offset_lookup is built on-demand upon attempting to report an error.

    // As the compiler is currently not multithreaded, we simply put it in a 

    // RefCell to allow interior mutability.

    offset_lookup: RefCell<Vec<u32>>,

}

impl InputSource2 {

    pub fn new(filename: String, input: Vec<u8>) -> Self {

        Self{

            filename,

            input,

            line: 1,

            offset: 0,

            had_error: None,

            offset_lookup: RefCell::new(Vec::new()),

        }

    }

    #[inline]

    pub fn pos(&self) -> InputPosition2 {

        InputPosition2{ line: self.line, offset: self.offset as u32 }

    }

    pub fn next(&self) -> Option<u8> {

        if self.offset < self.input.len() {

            Some(self.input[self.offset])

        } else {

            None

        }

    }

    pub fn lookahead(&self, offset: usize) -> Option<u8> {

        let offset_pos = self.offset + offset;

        if offset_pos < self.input.len() {

            Some(self.input[offset_pos])

        } else {

            None

        }

    }

    pub fn section(&self, start: u32, end: u32) -> &[u8] {

        &self.input[start as usize..end as usize]

    }

    // Consumes the next character. Will check well-formedness of newlines: \r

    // must be followed by a \n, because this is used for error reporting. Will

    // not check for ascii-ness of the file, better left to a tokenizer.

    pub fn consume(&mut self) {

        match self.next() {

            Some(b'\r') => {

                if Some(b'\n') == self.lookahead(1) {

                    // Well formed file

                    self.offset += 1;

                } else {

                    // Not a well-formed file, pretend like we can continue

                    self.offset += 1;

                    self.set_error("Encountered carriage-feed without a following newline");

                }

            },

            Some(b'\n') => {

                self.line += 1;

                self.offset += 1;

            },

            Some(_) => {

                self.offset += 1;

            }

            None => {}

        }

        // Maybe we actually want to check this in release mode. Then again:

        // a 4 gigabyte source file... Really?

        debug_assert!(self.offset < u32::max_value() as usize);

    }

    fn set_error(&mut self, msg: &str) {

        if self.had_error.is_none() {

            self.had_error = Some(ParseError::new_error(self, self.pos(), msg));

        }

    }

    fn get_lookup(&self) -> Ref<Vec<u32>> {

        // Once constructed the lookup always contains one element. We use this

        // to see if it is constructed already.

        let lookup = self.offset_lookup.borrow();

        if !lookup.is_empty() {

            return lookup;

        }

        // Build the line number (!) to offset lookup, so offset by 1. We 

        // assume the entire source file is scanned (most common case) for

        // preallocation.

        let lookup = self.offset_lookup.borrow_mut();

        lookup.reserve(self.line as usize + 2);

        lookup.push(0); // line 0: never used

        lookup.push(0); // first line: first character

        for char_idx in 0..self.input.len() {

            if self.input[char_idx] == b'\n' {

                lookup.push(char_idx as u32 + 1);

            }

        }

        lookup.push(self.input.len() as u32); // for lookup_line_end

        debug_assert_eq!(self.line as usize + 2, lookup.len(), "remove me: i am a testing assert and sometimes invalid");

        // Return created lookup

        let lookup = self.offset_lookup.borrow();

        return lookup;

    }

    fn lookup_line_start_offset(&self, line_number: u32) -> u32 {

        let lookup = self.get_lookup();

        lookup[line_number as usize]

    }

    fn lookup_line_end_offset(&self, line_number: u32) -> u32 {

        let lookup = self.get_lookup();

        let offset = lookup[(line_number + 1) as usize] - 1;

        let offset_usize = offset as usize;

        // Compensate for newlines and a potential carriage feed

        if self.input[offset_usize] == b'\n' {

            if offset_usize > 0 && self.input[offset_usize] == b'\r' {

                offset - 2

            } else {

                offset - 1

            }

        } else {

            offset

        }

    }

}

#[derive(Debug)]

pub enum ParseErrorType {

    Info,

    Error

}

#[derive(Debug)]

pub struct ParseErrorStatement {

    pub(crate) error_type: ParseErrorType,

    pub(crate) line: u32,

    pub(crate) column: u32,

    pub(crate) offset: u32,

    pub(crate) filename: String,

    pub(crate) context: String,

    pub(crate) message: String,

}

impl ParseErrorStatement {

    fn from_source(error_type: ParseErrorType, source: &InputSource2, position: InputPosition2, msg: &str) -> Self {

        // Seek line start and end

        let line_start = source.lookup_line_start_offset(position.line);

        let line_end = source.lookup_line_end_offset(position.line);

        debug_assert!(position.offset >= line_start);

        let column = position.offset - line_start + 1;

        Self{

            error_type,

            line: position.line,

            column,

            offset: position.offset,

            filename: source.filename.clone(),

            context: String::from_utf8_lossy(&source.input[line_start as usize..line_end as usize]).to_string(),

            message: msg.to_string()

        }

    }

}

impl fmt::Display for ParseErrorStatement {

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

        // Write message

        match self.error_type {

            ParseErrorType::Info => write!(f, " INFO: ")?,

            ParseErrorType::Error => write!(f, "ERROR: ")?,

        }

        writeln!(f, "{}", &self.message)?;

        // Write originating file/line/column

        if self.filename.is_empty() {

            writeln!(f, " +- at {}:{}", self.line, self.column)?;

        } else {

            writeln!(f, " +- at {}:{}:{}", self.filename, self.line, self.column)?;

        }

        // Write source context

        writeln!(f, " | ")?;

        writeln!(f, " | {}", self.context)?;

        // Write underline indicating where the error ocurred

        debug_assert!(self.column as usize <= self.context.chars().count());

        let mut arrow = String::with_capacity(self.context.len() + 3);

        arrow.push_str(" | ");

        let mut char_col = 1;

        for char in self.context.chars() {

            if char_col == self.column { break; }

            if char == '\t' {

                arrow.push('\t');

            } else {

                arrow.push(' ');

            }

            char_col += 1;

        }

        arrow.push('^');

        writeln!(f, "{}", arrow)?;

        Ok(())

    }

}

#[derive(Debug)]

pub struct ParseError {

    pub(crate) statements: Vec<ParseErrorStatement>

}

impl fmt::Display for ParseError {

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

        if self.statements.is_empty() {

            return Ok(())

        }

        self.statements[0].fmt(f)?;

        for statement in self.statements.iter().skip(1) {

            writeln!(f)?;

            statement.fmt(f)?;

        }

        Ok(())

    }

}

impl ParseError {

    pub fn empty() -> Self {

        Self{ statements: Vec::new() }

    }

    pub fn new_error(source: &InputSource2, position: InputPosition2, msg: &str) -> Self {

        Self{ statements: vec!(ParseErrorStatement::from_source(ParseErrorType::Error, source, position, msg))}

    }

    pub fn with_prefixed(mut self, error_type: ParseErrorType, source: &InputSource2, position: InputPosition2, msg: &str) -> Self {

        self.statements.insert(0, ParseErrorStatement::from_source(error_type, source, position, msg));

        self

    }

    pub fn with_postfixed(mut self, error_type: ParseErrorType, source: &InputSource2, position: InputPosition2, msg: &str) -> Self {

        self.statements.push(ParseErrorStatement::from_source(error_type, source, position, msg));

        self

    }

    pub fn with_postfixed_info(self, source: &InputSource2, position: InputPosition2, msg: &str) -> Self {

        self.with_postfixed(ParseErrorType::Info, source, position, msg)

    }

}

pub struct Lexer<'a> {

    source: &'a mut InputSource,

}

pub(crate) mod input_source2;

pub(crate) mod lexer2;

use crate::protocol::input_source2::{InputSource2 as InputSource, ParseError, InputPosition2 as InputPosition, InputSpan};

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

enum TokenKind {

    // Variable-character tokens, followed by a SpanEnd token

    Ident,

    Integer,

    String,

    Character,

    LineComment,

    BlockComment,

    // Punctuation

    Exclamation,    // !

    Question,       // ?

    Pound,          // #

    OpenAngle,      // <

    OpenCurly,      // {

    OpenParen,      // (

    OpenSquare,     // [

    CloseAngle,     // >

    CloseCurly,     // }

    CloseParen,     // )

    CloseSquare,    // ]

    Colon,          // :

    ColonColon,     // ::

    Comma,          // ,

    Dot,            // .

    DotDot,         // ..

    SemiColon,      // ;

    Quote,          // '

    DoubleQuote,    // "

    // Operator-like

    At,             // @

    Plus,           // +

    PlusPlus,       // ++

    PlusEquals,     // +=

    Minus,          // -

    ArrowRight,     // ->

    MinusMinus,     // --

    MinusEquals,    // -=

    Star,           // *

    StarEquals,     // *=

    Slash,          // /

    SlashEquals,    // /=

    Percent,        // %

    PercentEquals,  // %=

    Caret,          // ^

    CaretEquals,    // ^=

    And,            // &

    AndAnd,         // &&

    AndEquals,      // &=

    Or,             // |

    OrOr,           // ||

    OrEquals,       // |=

    Tilde,          // ~

    Equal,          // =

    EqualEqual,     // ==

    NotEqual,       // !=

    ShiftLeft,      // <<

    ShiftLeftEquals,// <<=

    ShiftRight,     // >>

    ShiftRightEquals, // >>=

    // Special marker token to indicate end of variable-character tokens

    SpanEnd,

}

struct Token {

    kind: TokenKind,

    pos: InputPosition, // probably need something different

}

impl Token {

    fn new(kind: TokenKind, pos: InputPosition) -> Self {

        Self{ kind, pos }

    }

#[derive(Debug, PartialEq, Eq)]

enum TokenRangeKind {

    Module,

    Definition,

    Code,

    // Index of parent in `TokenBuffer.ranges`, does not have a parent if the 

    // range kind is Module, in that case the parent index points to itself.

    parent_idx: usize,

    range_kind: TokenRangeKind,

    curly_depth: u8,

    subranges: usize,

struct ParseState {

    kind: TokenRangeKind,

    start: usize,

}

// Tokenizer is a reusable parser to tokenize multiple source files using the

// same allocated buffers. In a well-formed program, we produce a consistent

// tree of token ranges such that we may identify tokens that represent a 

// defintion or an import before producing the entire AST.

//

// If the program is not well-formed then the tree may be inconsistent, but we

// will detect this once we transform the tokens into the AST.

pub(crate) struct Tokenizer {

    curly_depth: u8,

    stack_idx: usize,

}

impl Tokenizer {

    pub(crate) fn tokenize(&mut self, source: &mut InputSource, target: &mut TokenBuffer) -> Result<(), ParseError> {

        // Assert source and buffer are at start

        debug_assert_eq!(source.pos().offset, 0);

        debug_assert!(target.tokens.is_empty());

        debug_assert!(target.ranges.is_empty());

        // Set up for tokenization by pushing the first range onto the stack.

        // This range may get transformed into the appropriate range kind later,

        // see `push_range` and `pop_range`.

        self.curly_depth = 0;

        self.stack_idx = 1;

        target.ranges.push(TokenRange{

            parent_idx: 0,

            range_kind: TokenRangeKind::Module,

            curly_depth: 0,

            start: 0,

            end: 0,

            subranges: 0,

        });

        // Main processing loop

        while let Some(c) = source.next() {

            let token_index = target.tokens.len();

            if is_char_literal_start(c) {

                self.consume_char_literal(source, target)?;

            } else if is_string_literal_start(c) {

                self.consume_string_literal(source, target)?;

            } else if is_identifier_start(c) {

                let ident = self.consume_identifier(source, target)?;

                if demarks_definition(ident) {

                    self.push_range(target, TokenRangeKind::Definition, token_index);

                } else if demarks_import(ident) {

                    self.push_range(target, TokenRangeKind::Import, token_index);

                }

            } else if is_integer_literal_start(c) {

                self.consume_number(source, target)?;

            } else if is_pragma_start(c) {

                self.consume_pragma(c, source, target);

                self.push_range(target, TokenRangeKind::Pragma, token_index);

            } else if self.is_line_comment_start(c, source) {

                self.consume_line_comment(source, target)?;

            } else if self.is_block_comment_start(c, source) {

                self.consume_block_comment(source, target)?;

            } else if is_whitespace(c) {