clojure_reader/

parse.rs

//! An EDN syntax parser in Rust.
#![expect(clippy::inline_always)]

use alloc::boxed::Box;
use alloc::collections::{BTreeMap, BTreeSet};
use alloc::vec::Vec;
use core::mem::replace;
use core::primitive::str;

use crate::edn::Edn;
use crate::error::{Code, Error};

#[cfg(feature = "arbitrary-nums")]
use bigdecimal::BigDecimal;
#[cfg(feature = "arbitrary-nums")]
use num_bigint::BigInt;
#[cfg(feature = "floats")]
use ordered_float::OrderedFloat;

/// Possible kinds of an EDN node
///
/// **NOTE:** The vector of items in [`NodeKind::Set`] may contain duplicate items.
/// **NOTE:** The vector of entries in [`NodeKind::Map`] may contain duplicate keys.
#[derive(Debug, Clone, Default, PartialEq, Eq, PartialOrd, Ord)]
#[non_exhaustive]
pub enum NodeKind<'e> {
  Vector(
    Vec<Node<'e>>,
    /* Any trailing discards inside vector, e.g. `[foo bar #_baz #_qux]` */ Vec<Discard<'e>>,
  ),
  Set(
    Vec<Node<'e>>,
    /* Any trailing discards inside set, e.g. `#{foo bar #_baz #_qux}` */ Vec<Discard<'e>>,
  ),
  Map(
    Vec<(Node<'e>, Node<'e>)>,
    /* Any trailing discards inside map, e.g. `{:foo bar #_baz #_qux}` */ Vec<Discard<'e>>,
  ),
  List(
    Vec<Node<'e>>,
    /* Any trailing discards inside list, e.g. `(foo bar #_baz #_qux)` */ Vec<Discard<'e>>,
  ),
  Key(&'e str),
  Symbol(&'e str),
  Str(&'e str),
  Int(i64),
  Tagged(&'e str, /* Span of the tag string */ Span, Box<Node<'e>>),
  #[cfg(feature = "floats")]
  Double(OrderedFloat<f64>),
  Rational((i64, i64)),
  #[cfg(feature = "arbitrary-nums")]
  BigInt(BigInt),
  #[cfg(feature = "arbitrary-nums")]
  BigDec(BigDecimal),
  Char(char),
  Bool(bool),
  #[default]
  Nil,
}

/// A **discarded** form containing the node that was discarded
#[derive(Debug, Clone, Default, PartialEq, Eq, PartialOrd, Ord)]
pub struct Discard<'e>(pub Node<'e>, pub Span);

/// Concrete EDN syntax tree.
///
/// Parse one with [`parse`], then convert it to an [`Edn`] with [`Edn::try_from`].
#[derive(Debug, Clone, Default, PartialEq, Eq, PartialOrd, Ord)]
pub struct Node<'e> {
  pub kind: NodeKind<'e>,
  pub span: Span,
  pub leading_discards: Vec<Discard<'e>>,
}

impl<'e> Node<'e> {
  /// Construct a `Node` with the given kind and span and no leading discards.
  pub const fn no_discards(kind: NodeKind<'e>, span: Span) -> Self {
    Self { kind, span, leading_discards: Vec::new() }
  }

  #[inline]
  pub const fn span(&self) -> Span {
    self.span
  }
}

/// Parse a single `Node` from a [`SourceReader`], consuming that form.
///
/// # Examples
///
/// ```
/// #[cfg(feature = "unstable")]
/// {
///   use clojure_reader::parse::{Node, NodeKind::*, SourceReader, parse};
///
///   let source = r#"
/// (->> txs
///   (keep :refund-amt)
///   (reduce +))
///   ; total refund amount
/// "#;
///   let mut reader = SourceReader::new(source);
///   let Node { kind: node, .. } = parse(&mut reader).expect("failed to parse");
///
///   let List(nodes, _) = node else { panic!("unexpected") };
///
///   // Destruct main list
///   let nodes: Vec<_> = nodes.into_iter().map(|n| n.kind).collect();
///   let [Symbol("->>"), Symbol("txs"), List(keep, _), List(reduce, _)] = nodes.as_slice() else {
///     panic!("unexpected");
///   };
///
///   // Destruct the list calling `keep`
///   let keep: Vec<_> = keep.into_iter().map(|n| &n.kind).collect();
///   let [Symbol("keep"), Key("refund-amt")] = keep.as_slice() else {
///     panic!("unexpected");
///   };
///
///   // Destruct the list calling `reduce`
///   let reduce: Vec<_> = reduce.into_iter().map(|n| &n.kind).collect();
///   let [Symbol("reduce"), Symbol("+")] = reduce.as_slice() else {
///     panic!("unexpected");
///   };
///
///   assert_eq!(reader.remaining(), "\n  ; total refund amount\n");
/// }
/// ```
///
/// # Errors
///
/// See [`crate::error::Error`].
#[cfg_attr(not(feature = "unstable"), expect(dead_code))]
pub fn parse<'r, 'e: 'r>(reader: &'r mut SourceReader<'e>) -> Result<Node<'e>, Error> {
  let start_pos = reader.read_pos;
  let builder = NodeBuilder;
  let parsed = {
    let mut walker = Walker::new(reader);
    parse_internal(&mut walker, &builder)?
  };
  Ok(parsed.unwrap_or_else(|| builder.nil(reader.span_from(start_pos))))
}

/// Parse the first EDN form from a string and return it with the unread remainder.
///
/// # Errors
///
/// See [`crate::error::Error`].
pub fn parse_as_edn(edn: &str) -> Result<(Edn<'_>, &str), Error> {
  let mut source_reader = SourceReader::new(edn);
  let start_pos = source_reader.read_pos;
  let builder = EdnBuilder;
  let parsed = {
    let mut walker = Walker::new(&mut source_reader);
    parse_internal(&mut walker, &builder)?
  };
  let parsed = parsed.unwrap_or_else(|| builder.nil(source_reader.span_from(start_pos)));
  Ok((parsed, source_reader.remaining()))
}

#[cfg_attr(not(feature = "unstable"), expect(clippy::redundant_pub_crate))]
pub(crate) fn parse_optional_edn(edn: &str) -> Result<(Option<Edn<'_>>, &str), Error> {
  let mut source_reader = SourceReader::new(edn);
  let parsed = {
    let mut walker = Walker::new(&mut source_reader);
    parse_internal(&mut walker, &EdnBuilder)?
  };
  Ok((parsed, source_reader.remaining()))
}

const DELIMITERS: [char; 8] = [',', ']', '}', ')', ';', '(', '[', '{'];

fn is_token_boundary(c: char) -> bool {
  c.is_whitespace() || DELIMITERS.contains(&c) || c == '"'
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Position {
  pub line: usize,
  pub column: usize,
  pub ptr: usize,
}

impl Default for Position {
  fn default() -> Self {
    Self { line: 1, column: 1, ptr: 0 }
  }
}

#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Span(pub Position, pub Position);

impl Span {
  /// Whether the span is empty
  pub const fn is_empty(&self) -> bool {
    self.0.ptr == self.1.ptr
  }
}

/// A string-slice reader that records how much of the slice has been read
#[derive(Debug)]
pub struct SourceReader<'s> {
  slice: &'s str,
  // Position till where this string has been read
  read_pos: Position,
}

impl<'e> SourceReader<'e> {
  pub fn new(source: &'e str) -> Self {
    Self { slice: source, read_pos: Position::default() }
  }

  /// Span from some previously marked position to the current position of the reader
  #[inline(always)]
  pub const fn span_from(&self, marker: Position) -> Span {
    Span(marker, self.read_pos)
  }

  /// The portion of the source-string remaining to be read
  ///
  /// ```
  /// #[cfg(feature = "unstable")]
  /// {
  ///   use clojure_reader::parse::{SourceReader, parse};
  ///
  ///   let mut s = SourceReader::new("() []");
  ///   let _ = parse(&mut s).expect("failed to parse");
  ///   assert_eq!(s.remaining(), " []");
  /// }
  /// ```
  pub fn remaining(&self) -> &'e str {
    &self.slice[self.read_pos.ptr..]
  }

  /// Finishes the source-reader, returning:
  /// 1. the current reader position, and
  /// 2. the original source-string.
  ///
  /// ```
  /// #[cfg(feature = "unstable")]
  /// {
  ///   use clojure_reader::parse::{Position, SourceReader, parse};
  ///
  ///   let mut s = SourceReader::new("() []");
  ///   let _ = parse(&mut s).expect("failed to parse");
  ///
  ///   let (pos, slice) = s.finish();
  ///   assert_eq!(
  ///       pos,
  ///       Position {
  ///           line: 1,
  ///           column: 3,
  ///           ptr: 2
  ///       }
  ///   );
  ///   assert_eq!(slice, "() []");
  ///   assert_eq!(&slice[pos.ptr..], " []");
  /// }
  /// ```
  #[cfg_attr(not(feature = "unstable"), expect(dead_code))]
  pub const fn finish(self) -> (Position, &'e str) {
    (self.read_pos, self.slice)
  }

  // Slurps until whitespace or delimiter, returning the slice.
  #[inline(always)]
  fn slurp_literal(&mut self) -> &'e str {
    let token = self.slice[self.read_pos.ptr..]
      .split(is_token_boundary)
      .next()
      .expect("Expected at least an empty slice");

    self.read_pos.ptr += token.len();
    self.read_pos.column += token.chars().count();
    token
  }

  // Slurps a char. Special handling for chars that happen to be delimiters
  #[inline(always)]
  fn slurp_char(&mut self) -> &'e str {
    let starting_ptr = self.read_pos.ptr;

    let mut ptr = 0;
    while let Some(c) = self.peek_next() {
      // first is always \\, second is always a char we want.
      // Handles edge cases of having a valid "\\[" but also "\\c[lolthisisvalidedn"
      if ptr > 1 && (c.is_whitespace() || DELIMITERS.contains(&c)) {
        break;
      }

      let _ = self.nibble_next();
      ptr += c.len_utf8();
    }
    &self.slice[starting_ptr..starting_ptr + ptr]
  }

  #[inline(always)]
  fn slurp_str(&mut self) -> Result<&'e str, Error> {
    let _ = self.nibble_next(); // Consume the leading '"' char
    let starting_ptr = self.read_pos.ptr;
    let mut escape = false;
    loop {
      if let Some(c) = self.nibble_next() {
        if escape {
          match c {
            't' | 'r' | 'n' | '\\' | '"' => (),
            _ => {
              return Err(Error::from_position(Code::InvalidEscape, self.read_pos));
            }
          }
          escape = false;
        } else if c == '"' {
          return Ok(&self.slice[starting_ptr..self.read_pos.ptr - 1]);
        } else {
          escape = c == '\\';
        }
      } else {
        return Err(Error::from_position(Code::UnexpectedEOF, self.read_pos));
      }
    }
  }

  #[inline(always)]
  fn slurp_tag(&mut self) -> Result<&'e str, Error> {
    let starting_ptr = self.read_pos.ptr;

    loop {
      if let Some(c) = self.peek_next() {
        if is_token_boundary(c) {
          return Ok(&self.slice[starting_ptr..self.read_pos.ptr]);
        }
        let _ = self.nibble_next();
      } else {
        return Err(Error::from_position(Code::UnexpectedEOF, self.read_pos));
      }
    }
  }

  // Nibbles away until the next new line
  #[inline(always)]
  fn nibble_newline(&mut self) {
    while let Some(c) = self.peek_next() {
      if matches!(c, '\n' | '\r') {
        break;
      }
      let _ = self.nibble_next();
    }
    self.nibble_whitespace();
  }

  // Nibbles away until the start of the next form
  #[inline(always)]
  fn nibble_whitespace(&mut self) {
    while let Some(n) = self.peek_next() {
      if n == ',' || n.is_whitespace() {
        let _ = self.nibble_next();
        continue;
      }
      break;
    }
  }

  // Consumes next
  #[inline(always)]
  fn nibble_next(&mut self) -> Option<char> {
    let char = self.slice[self.read_pos.ptr..].chars().next();
    if let Some(c) = char {
      self.read_pos.ptr += c.len_utf8();
      if c == '\n' {
        self.read_pos.line += 1;
        self.read_pos.column = 1;
      } else {
        self.read_pos.column += 1;
      }
    }
    char
  }

  // Peek into the next char
  #[inline(always)]
  fn peek_next(&self) -> Option<char> {
    self.slice[self.read_pos.ptr..].chars().next()
  }
}

struct Parsed<I> {
  item: I,
  span: Span,
}

impl<I> Parsed<I> {
  const fn new(item: I, span: Span) -> Self {
    Self { item, span }
  }
}

struct Walker<'e, 'r, B: InternalParser<'e>> {
  reader: &'r mut SourceReader<'e>,
  stack: Vec<ParseContext<'e, B>>,
}

impl<'e, 'r, B: InternalParser<'e>> Walker<'e, 'r, B> {
  fn new(reader: &'r mut SourceReader<'e>) -> Self {
    Self {
      reader,
      stack: alloc::vec![ParseContext { kind: ContextKind::Top, discards: Vec::new() }],
    }
  }

  #[inline(always)]
  const fn pos(&self) -> Position {
    self.reader.read_pos
  }

  /// Span from some previously marked position to the current position of the walker's reader
  #[inline(always)]
  const fn span_from(&self, marker: Position) -> Span {
    Span(marker, self.reader.read_pos)
  }

  #[inline(always)]
  fn push_context(&mut self, ctx: ParseContext<'e, B>) {
    self.stack.push(ctx);
  }

  #[inline(always)]
  fn pop_context(&mut self) -> Option<ParseContext<'e, B>> {
    self.stack.pop()
  }

  #[inline(always)]
  const fn stack_len(&self) -> usize {
    self.stack.len()
  }

  const fn make_error(&self, code: Code) -> Error {
    Error::from_position(code, self.pos())
  }

  fn last_context_discards(&mut self) -> Option<&mut Vec<B::Discard>> {
    match self.stack.last_mut() {
      Some(ParseContext { discards, .. }) => Some(discards),
      None => None,
    }
  }
}

#[derive(Debug, Clone, Copy)]
enum OpenDelimiter {
  Vector,
  List,
  Map,
  Hash,
}

// `Position`, wherever present, contains the start position of that context
enum ContextKind<'e, B: InternalParser<'e>> {
  Top,
  Vector(B::VectorContext, Position),
  List(B::ListContext, Position),
  Map(B::MapContext, Position),
  Set(B::SetContext, Position),
  Tag(&'e str, /* Span of the tag string */ Span, Position),
  Discard(Position),
}

struct ParseContext<'e, B: InternalParser<'e>> {
  kind: ContextKind<'e, B>,
  discards: Vec<B::Discard>,
}

impl<'e, B: InternalParser<'e>> ParseContext<'e, B> {
  const fn no_discards(kind: ContextKind<'e, B>) -> Self {
    Self { kind, discards: Vec::new() }
  }
}

#[derive(Debug, Clone)]
#[cfg_attr(not(feature = "arbitrary-nums"), derive(Copy))]
enum Atom<'e> {
  Key(&'e str),
  Symbol(&'e str),
  Str(&'e str),
  Int(i64),
  #[cfg(feature = "floats")]
  Double(OrderedFloat<f64>),
  Rational((i64, i64)),
  #[cfg(feature = "arbitrary-nums")]
  BigInt(BigInt),
  #[cfg(feature = "arbitrary-nums")]
  BigDec(BigDecimal),
  Char(char),
  Bool(bool),
  Nil,
}

trait InternalParser<'e> {
  type Item;
  type Discard;
  type VectorContext;
  type ListContext;
  type MapContext;
  type SetContext;

  fn atom(&self, atom: Atom<'e>, span: Span) -> Self::Item;

  fn with_leading_discards(
    &self,
    item: Self::Item,
    leading_discards: Vec<Self::Discard>,
  ) -> Self::Item;

  fn new_vector_context(&self) -> Self::VectorContext;

  fn new_list_context(&self) -> Self::ListContext;

  fn new_map_context(&self) -> Self::MapContext;

  fn new_set_context(&self) -> Self::SetContext;

  fn add_to_vector(
    &self,
    ctx: &mut Self::VectorContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error>;

  fn add_to_list(
    &self,
    ctx: &mut Self::ListContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error>;

  fn add_to_map(
    &self,
    ctx: &mut Self::MapContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error>;

  fn add_to_set(
    &self,
    ctx: &mut Self::SetContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error>;

  fn finish_vector(
    &self,
    ctx: Self::VectorContext,
    trailing_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error>;

  fn finish_set(
    &self,
    ctx: Self::SetContext,
    trailing_discards: Vec<Self::Discard>,
    validate: bool,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error>;

  fn finish_map(
    &self,
    ctx: Self::MapContext,
    trailing_discards: Vec<Self::Discard>,
    validate: bool,
    close_pos: Position,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error>;

  fn finish_list(
    &self,
    ctx: Self::ListContext,
    trailing_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error>;

  fn tag(
    &self,
    tag: &'e str,
    tag_span: Span,
    value: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error>;

  fn discard(
    &self,
    value: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
    discard_span: Span,
  ) -> Self::Discard;

  fn nil(&self, span: Span) -> Self::Item {
    self.atom(Atom::Nil, span)
  }
}

struct EdnBuilder;

impl<'e> InternalParser<'e> for EdnBuilder {
  type Item = Edn<'e>;
  type Discard = ();
  type VectorContext = Vec<Edn<'e>>;
  type ListContext = Vec<Edn<'e>>;
  type MapContext = (Vec<(Parsed<Edn<'e>>, Parsed<Edn<'e>>)>, Option<Parsed<Edn<'e>>>);
  type SetContext = Vec<Parsed<Edn<'e>>>;

  fn atom(&self, atom: Atom<'e>, span: Span) -> Self::Item {
    let _ = span;
    match atom {
      Atom::Key(key) => Edn::Key(key),
      Atom::Symbol(symbol) => Edn::Symbol(symbol),
      Atom::Str(str) => Edn::Str(str),
      Atom::Int(int) => Edn::Int(int),
      #[cfg(feature = "floats")]
      Atom::Double(double) => Edn::Double(double),
      Atom::Rational(rational) => Edn::Rational(rational),
      #[cfg(feature = "arbitrary-nums")]
      Atom::BigInt(big_int) => Edn::BigInt(big_int),
      #[cfg(feature = "arbitrary-nums")]
      Atom::BigDec(big_dec) => Edn::BigDec(big_dec),
      Atom::Char(ch) => Edn::Char(ch),
      Atom::Bool(bool) => Edn::Bool(bool),
      Atom::Nil => Edn::Nil,
    }
  }

  fn with_leading_discards(
    &self,
    item: Self::Item,
    _leading_discards: Vec<Self::Discard>,
  ) -> Self::Item {
    item
  }

  fn new_vector_context(&self) -> Self::VectorContext {
    Vec::new()
  }

  fn new_list_context(&self) -> Self::ListContext {
    Vec::new()
  }

  fn new_map_context(&self) -> Self::MapContext {
    (Vec::new(), None)
  }

  fn new_set_context(&self) -> Self::SetContext {
    Vec::new()
  }

  fn add_to_vector(
    &self,
    ctx: &mut Self::VectorContext,
    parsed: Parsed<Self::Item>,
    _leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    ctx.push(parsed.item);
    Ok(())
  }

  fn add_to_list(
    &self,
    ctx: &mut Self::ListContext,
    parsed: Parsed<Self::Item>,
    _leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    ctx.push(parsed.item);
    Ok(())
  }

  fn add_to_map(
    &self,
    ctx: &mut Self::MapContext,
    parsed: Parsed<Self::Item>,
    _leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    let (entries, pending) = ctx;
    if let Some(key) = pending.take() {
      entries.push((key, parsed));
    } else {
      *pending = Some(parsed);
    }
    Ok(())
  }

  fn add_to_set(
    &self,
    ctx: &mut Self::SetContext,
    parsed: Parsed<Self::Item>,
    _leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    ctx.push(parsed);
    Ok(())
  }

  fn finish_vector(
    &self,
    ctx: Self::VectorContext,
    _trailing_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    Ok(Parsed::new(Edn::Vector(ctx), span))
  }

  fn finish_set(
    &self,
    ctx: Self::SetContext,
    _trailing_discards: Vec<Self::Discard>,
    validate: bool,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    let mut set = BTreeSet::new();
    for item in ctx {
      if !set.insert(item.item) && validate {
        return Err(Error::from_position(Code::SetDuplicateKey, item.span.1));
      }
    }
    Ok(Parsed::new(Edn::Set(set), span))
  }

  fn finish_map(
    &self,
    ctx: Self::MapContext,
    _trailing_discards: Vec<Self::Discard>,
    validate: bool,
    close_pos: Position,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    if ctx.1.is_some() {
      return Err(Error::from_position(Code::UnexpectedEOF, close_pos));
    }
    let mut map = BTreeMap::new();
    for (key, value) in ctx.0 {
      if map.insert(key.item, value.item).is_some() && validate {
        return Err(Error::from_position(Code::HashMapDuplicateKey, value.span.1));
      }
    }
    Ok(Parsed::new(Edn::Map(map), span))
  }

  fn finish_list(
    &self,
    ctx: Self::ListContext,
    _trailing_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    Ok(Parsed::new(Edn::List(ctx), span))
  }

  fn tag(
    &self,
    tag: &'e str,
    tag_span: Span,
    value: Parsed<Self::Item>,
    _leading_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    crate::edn::validate_tag(tag, tag_span)?;
    if tag.starts_with(':') && !matches!(&value.item, Edn::Map(_)) {
      return Err(Error::from_position(Code::InvalidTag, tag_span.0));
    }
    Ok(Parsed::new(Edn::Tagged(tag, Box::new(value.item)), span))
  }

  fn discard(
    &self,
    _value: Parsed<Self::Item>,
    _leading_discards: Vec<Self::Discard>,
    _discard_span: Span,
  ) -> Self::Discard {
  }
}

struct NodeBuilder;

impl<'e> InternalParser<'e> for NodeBuilder {
  type Item = Node<'e>;
  type Discard = Discard<'e>;
  type VectorContext = Vec<Node<'e>>;
  type ListContext = Vec<Node<'e>>;
  type MapContext = (Vec<(Node<'e>, Node<'e>)>, Option<Node<'e>>);
  type SetContext = Vec<Node<'e>>;

  fn atom(&self, atom: Atom<'e>, span: Span) -> Self::Item {
    let kind = match atom {
      Atom::Key(key) => NodeKind::Key(key),
      Atom::Symbol(symbol) => NodeKind::Symbol(symbol),
      Atom::Str(str) => NodeKind::Str(str),
      Atom::Int(int) => NodeKind::Int(int),
      #[cfg(feature = "floats")]
      Atom::Double(double) => NodeKind::Double(double),
      Atom::Rational(rational) => NodeKind::Rational(rational),
      #[cfg(feature = "arbitrary-nums")]
      Atom::BigInt(big_int) => NodeKind::BigInt(big_int),
      #[cfg(feature = "arbitrary-nums")]
      Atom::BigDec(big_dec) => NodeKind::BigDec(big_dec),
      Atom::Char(ch) => NodeKind::Char(ch),
      Atom::Bool(bool) => NodeKind::Bool(bool),
      Atom::Nil => NodeKind::Nil,
    };

    Node::no_discards(kind, span)
  }

  fn with_leading_discards(
    &self,
    mut item: Self::Item,
    leading_discards: Vec<Self::Discard>,
  ) -> Self::Item {
    item.leading_discards = leading_discards;
    item
  }

  fn new_vector_context(&self) -> Self::VectorContext {
    Vec::new()
  }

  fn new_list_context(&self) -> Self::ListContext {
    Vec::new()
  }

  fn new_map_context(&self) -> Self::MapContext {
    (Vec::new(), None)
  }

  fn new_set_context(&self) -> Self::SetContext {
    Vec::new()
  }

  fn add_to_vector(
    &self,
    ctx: &mut Self::VectorContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    ctx.push(self.with_leading_discards(parsed.item, leading_discards));
    Ok(())
  }

  fn add_to_list(
    &self,
    ctx: &mut Self::ListContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    ctx.push(self.with_leading_discards(parsed.item, leading_discards));
    Ok(())
  }

  fn add_to_map(
    &self,
    ctx: &mut Self::MapContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    let parsed = self.with_leading_discards(parsed.item, leading_discards);
    if let Some(key) = ctx.1.take() {
      ctx.0.push((key, parsed));
    } else {
      ctx.1 = Some(parsed);
    }
    Ok(())
  }

  fn add_to_set(
    &self,
    ctx: &mut Self::SetContext,
    parsed: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
  ) -> Result<(), Error> {
    ctx.push(self.with_leading_discards(parsed.item, leading_discards));
    Ok(())
  }

  fn finish_vector(
    &self,
    ctx: Self::VectorContext,
    trailing_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    Ok(Parsed::new(Node::no_discards(NodeKind::Vector(ctx, trailing_discards), span), span))
  }

  fn finish_set(
    &self,
    ctx: Self::SetContext,
    trailing_discards: Vec<Self::Discard>,
    _validate: bool,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    Ok(Parsed::new(Node::no_discards(NodeKind::Set(ctx, trailing_discards), span), span))
  }

  fn finish_map(
    &self,
    ctx: Self::MapContext,
    trailing_discards: Vec<Self::Discard>,
    _validate: bool,
    close_pos: Position,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    if ctx.1.is_some() {
      return Err(Error::from_position(Code::UnexpectedEOF, close_pos));
    }
    Ok(Parsed::new(Node::no_discards(NodeKind::Map(ctx.0, trailing_discards), span), span))
  }

  fn finish_list(
    &self,
    ctx: Self::ListContext,
    trailing_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    Ok(Parsed::new(Node::no_discards(NodeKind::List(ctx, trailing_discards), span), span))
  }

  fn tag(
    &self,
    tag: &'e str,
    tag_span: Span,
    value: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
    span: Span,
  ) -> Result<Parsed<Self::Item>, Error> {
    let value = self.with_leading_discards(value.item, leading_discards);
    Ok(Parsed::new(Node::no_discards(NodeKind::Tagged(tag, tag_span, Box::new(value)), span), span))
  }

  fn discard(
    &self,
    value: Parsed<Self::Item>,
    leading_discards: Vec<Self::Discard>,
    discard_span: Span,
  ) -> Self::Discard {
    Discard(self.with_leading_discards(value.item, leading_discards), discard_span)
  }
}

#[expect(clippy::mem_replace_with_default)]
const fn take_discards<D>(discards: &mut Vec<D>) -> Vec<D> {
  replace(discards, Vec::new())
}

#[inline]
fn add_to_context<'e, B: InternalParser<'e>>(
  context: &mut Option<&mut ParseContext<'e, B>>,
  builder: &B,
  parsed: Parsed<B::Item>,
) -> Result<(), Error> {
  match context.as_mut() {
    Some(ParseContext { kind: ContextKind::Vector(ctx, _), discards }) => {
      builder.add_to_vector(ctx, parsed, take_discards(discards))?;
    }
    Some(ParseContext { kind: ContextKind::List(ctx, _), discards }) => {
      builder.add_to_list(ctx, parsed, take_discards(discards))?;
    }
    Some(ParseContext { kind: ContextKind::Map(ctx, _), discards }) => {
      builder.add_to_map(ctx, parsed, take_discards(discards))?;
    }
    Some(ParseContext { kind: ContextKind::Set(ctx, _), discards }) => {
      builder.add_to_set(ctx, parsed, take_discards(discards))?;
    }
    _ => {}
  }
  Ok(())
}

#[inline]
fn handle_open_delimiter<'e, B: InternalParser<'e>>(
  walker: &mut Walker<'e, '_, B>,
  builder: &B,
  delim: OpenDelimiter,
) -> Result<(), Error> {
  let pos_start = walker.pos();
  match delim {
    OpenDelimiter::Vector => {
      let _ = walker.reader.nibble_next();
      walker.push_context(ParseContext::no_discards(ContextKind::Vector(
        builder.new_vector_context(),
        pos_start,
      )));
    }
    OpenDelimiter::List => {
      let _ = walker.reader.nibble_next();
      walker.push_context(ParseContext::no_discards(ContextKind::List(
        builder.new_list_context(),
        pos_start,
      )));
    }
    OpenDelimiter::Map => {
      let _ = walker.reader.nibble_next();
      walker.push_context(ParseContext::no_discards(ContextKind::Map(
        builder.new_map_context(),
        pos_start,
      )));
    }
    OpenDelimiter::Hash => {
      let _ = walker.reader.nibble_next();
      match walker.reader.peek_next() {
        Some('{') => {
          let _ = walker.reader.nibble_next();
          walker.push_context(ParseContext::no_discards(ContextKind::Set(
            builder.new_set_context(),
            pos_start,
          )));
        }
        Some('_') => {
          let _ = walker.reader.nibble_next();
          walker.push_context(ParseContext::no_discards(ContextKind::Discard(pos_start)));
        }
        Some(c) if !c.is_whitespace() && !DELIMITERS.contains(&c) => {
          let tag_pos_start = walker.pos();
          let tag = walker.reader.slurp_tag()?;
          let tag_span = walker.span_from(tag_pos_start);
          if tag.is_empty() {
            return Err(walker.make_error(Code::InvalidTag));
          }

          walker.reader.nibble_whitespace();
          walker
            .push_context(ParseContext::no_discards(ContextKind::Tag(tag, tag_span, pos_start)));
        }
        Some(_) => return Err(walker.make_error(Code::InvalidTag)),
        None => return Err(walker.make_error(Code::UnexpectedEOF)),
      }
    }
  }
  Ok(())
}

fn wrap_pending_tags<'e, 'r, B: InternalParser<'e>>(
  walker: &mut Walker<'e, 'r, B>,
  builder: &B,
  mut parsed: Parsed<B::Item>,
) -> Result<Parsed<B::Item>, Error> {
  while matches!(walker.stack.last(), Some(ParseContext { kind: ContextKind::Tag(..), .. })) {
    let ParseContext { kind: ContextKind::Tag(tag, tag_span, pos_start), discards } =
      walker.pop_context().expect("tag context should exist")
    else {
      unreachable!("tag context should be on top of the stack");
    };

    parsed = builder.tag(tag, tag_span, parsed, discards, walker.span_from(pos_start))?;
  }

  Ok(parsed)
}

fn under_discard<'e, B: InternalParser<'e>>(walker: &Walker<'e, '_, B>) -> bool {
  walker.stack.iter().any(|ctx| matches!(ctx.kind, ContextKind::Discard(..)))
}

fn complete_value<'e, 'r, B: InternalParser<'e>>(
  walker: &mut Walker<'e, 'r, B>,
  builder: &B,
  parsed: Parsed<B::Item>,
) -> Result<Option<B::Item>, Error> {
  let parsed = wrap_pending_tags(walker, builder, parsed)?;

  if walker.stack_len() == 1 {
    let leading_discards =
      take_discards(walker.last_context_discards().expect("Top should be there"));
    return Ok(Some(builder.with_leading_discards(parsed.item, leading_discards)));
  }

  if let Some(ParseContext { kind: ContextKind::Discard(pos_start), discards }) =
    walker.stack.last_mut()
  {
    let pos_start = *pos_start;
    let end_pos = parsed.span.1;
    let discarded = builder.discard(parsed, take_discards(discards), Span(pos_start, end_pos));
    walker.pop_context();
    walker.stack.last_mut().expect("Top should be there").discards.push(discarded);
    return Ok(None);
  }

  add_to_context(&mut walker.stack.last_mut(), builder, parsed)?;
  Ok(None)
}

#[inline]
fn handle_close_delimiter<'e, B: InternalParser<'e>>(
  walker: &mut Walker<'e, '_, B>,
  builder: &B,
  delimiter: char,
) -> Result<Option<B::Item>, Error> {
  if walker.stack_len() <= 1 {
    return Err(walker.make_error(Code::UnmatchedDelimiter(delimiter)));
  }

  let expected = match walker.stack.last().expect("Len > 1 is never empty") {
    ParseContext { kind: ContextKind::Vector(..), .. } => ']',
    ParseContext { kind: ContextKind::List(..), .. } => ')',
    ParseContext { kind: ContextKind::Map(..) | ContextKind::Set(..), .. } => '}',
    _ => {
      return Err(walker.make_error(Code::UnmatchedDelimiter(delimiter)));
    }
  };

  if delimiter != expected {
    return Err(walker.make_error(Code::UnmatchedDelimiter(delimiter)));
  }

  let parsed = match walker.pop_context() {
    Some(ParseContext { kind: ContextKind::Vector(ctx, pos_start), discards }) => {
      let _ = walker.reader.nibble_next();
      builder.finish_vector(ctx, discards, walker.span_from(pos_start))?
    }
    Some(ParseContext { kind: ContextKind::List(ctx, pos_start), discards }) => {
      let _ = walker.reader.nibble_next();
      builder.finish_list(ctx, discards, walker.span_from(pos_start))?
    }
    Some(ParseContext { kind: ContextKind::Map(ctx, pos_start), discards }) => {
      let validate = !under_discard(walker);
      let close_pos = walker.pos();
      let _ = walker.reader.nibble_next();
      builder.finish_map(ctx, discards, validate, close_pos, walker.span_from(pos_start))?
    }
    Some(ParseContext { kind: ContextKind::Set(ctx, pos_start), discards }) => {
      let validate = !under_discard(walker);
      let _ = walker.reader.nibble_next();
      builder.finish_set(ctx, discards, validate, walker.span_from(pos_start))?
    }
    _ => {
      return Err(walker.make_error(Code::UnmatchedDelimiter(delimiter)));
    }
  };

  complete_value(walker, builder, parsed)
}

fn parse_internal<'e, B: InternalParser<'e>>(
  walker: &mut Walker<'e, '_, B>,
  builder: &B,
) -> Result<Option<B::Item>, Error> {
  let mut result = None;
  loop {
    walker.reader.nibble_whitespace();
    match walker.reader.peek_next() {
      Some(';') => walker.reader.nibble_newline(),
      Some('[') => handle_open_delimiter(walker, builder, OpenDelimiter::Vector)?,
      Some('(') => handle_open_delimiter(walker, builder, OpenDelimiter::List)?,
      Some('{') => handle_open_delimiter(walker, builder, OpenDelimiter::Map)?,
      Some('#') => handle_open_delimiter(walker, builder, OpenDelimiter::Hash)?,
      Some(d) if matches!(d, ']' | ')' | '}') => {
        if let Some(parsed) = handle_close_delimiter(walker, builder, d)? {
          result = Some(parsed);
          break;
        }
      }
      Some(c) => {
        let pos_start = walker.reader.read_pos;
        let atom = match c {
          '\\' => parse_char(walker.reader.slurp_char()).map(Atom::Char),
          '"' => Ok(Atom::Str(walker.reader.slurp_str()?)),
          _ => edn_literal(walker.reader.slurp_literal()),
        }
        .map_err(|code| Error::from_position(code, pos_start))?;
        let span = walker.reader.span_from(pos_start);
        let parsed = Parsed::new(builder.atom(atom, span), span);

        if let Some(parsed) = complete_value(walker, builder, parsed)? {
          result = Some(parsed);
          break;
        }
      }
      None => {
        if walker.stack_len() > 1 {
          return Err(walker.make_error(Code::UnexpectedEOF));
        }
        break;
      }
    }
  }
  Ok(result)
}

#[inline]
fn edn_literal(literal: &str) -> Result<Atom<'_>, Code> {
  fn numeric(s: &str) -> bool {
    let (first, second) = {
      let mut s = s.chars();
      (s.next(), s.next())
    };

    let first = first.expect("Empty str is previously caught as nil");
    if first.is_numeric() {
      return true;
    }

    if (first == '-' || first == '+')
      && let Some(s) = second
      && s.is_numeric()
    {
      return true;
    }

    false
  }

  Ok(match literal {
    "nil" => Atom::Nil,
    "true" => Atom::Bool(true),
    "false" => Atom::Bool(false),
    k if k.starts_with(':') => {
      if k.len() <= 1 {
        return Err(Code::InvalidKeyword);
      }
      Atom::Key(&k[1..])
    }
    n if numeric(n) => parse_number(n)?,
    _ => Atom::Symbol(literal),
  })
}

#[inline]
fn parse_char(lit: &str) -> Result<char, Code> {
  let lit = &lit[1..]; // ignore the leading '\\'
  match lit {
    "newline" => Ok('\n'),
    "return" => Ok('\r'),
    "tab" => Ok('\t'),
    "space" => Ok(' '),
    c if c.chars().count() == 1 => Ok(c.chars().next().expect("c must be one character")),
    _ => Err(Code::InvalidChar),
  }
}

#[inline]
fn signed_int_from_slice(slice: &str, radix: u8, polarity: i8) -> Option<i64> {
  let magnitude = u64::from_str_radix(slice, radix.into()).ok()?;
  if polarity < 0 {
    if magnitude == (i64::MAX as u64) + 1 {
      return Some(i64::MIN);
    }
    i64::try_from(magnitude).ok().map(|n| -n)
  } else {
    i64::try_from(magnitude).ok()
  }
}

#[inline]
fn parse_number(lit: &str) -> Result<Atom<'_>, Code> {
  let mut chars = lit.chars().peekable();
  let (number, radix, polarity) = {
    let mut num_ptr_start = 0;
    let polarity = chars.peek().map_or(1i8, |c| {
      if *c == '-' {
        num_ptr_start += 1;
        -1i8
      } else if *c == '+' {
        // The EDN spec allows for a redundant '+' symbol, we just ignore it.
        num_ptr_start += 1;
        1i8
      } else {
        1i8
      }
    });

    let mut number = &lit[num_ptr_start..];

    if number.get(..2).is_some_and(|prefix| prefix.eq_ignore_ascii_case("0x")) {
      number = &number[2..];
      (number, 16, polarity)
    } else if let Some(index) = number.find(['r', 'R']) {
      let radix = (number[0..index]).parse::<u8>();

      match radix {
        Ok(r) => {
          // from_str_radix panics if radix is not in the range from 2 to 36
          if !(2..=36).contains(&r) {
            return Err(Code::InvalidRadix(Some(r)));
          }

          number = &number[(index + 1)..];
          (number, r, polarity)
        }
        Err(_) => {
          return Err(Code::InvalidRadix(None));
        }
      }
    } else {
      (number, 10, polarity)
    }
  };

  if let Some(n) = signed_int_from_slice(number, radix, polarity) {
    return Ok(Atom::Int(n));
  }
  if radix == 10
    && let Some(index) = number.find('/')
  {
    let (num, den) = number.split_at(index);
    let num = num.parse::<i64>();
    let den = &den[1..];
    let den_value = den.parse::<i64>();

    if let (Ok(n), Ok(d)) = (num, den_value)
      && d > 0
      && !den.starts_with(['+', '-'])
    {
      return Ok(Atom::Rational((n * i64::from(polarity), d)));
    }
  }

  #[cfg(feature = "arbitrary-nums")]
  if let Some(n) = big_int_from_slice(number, radix, polarity) {
    return Ok(Atom::BigInt(n));
  }
  #[cfg(feature = "floats")]
  if radix == 10
    && number.contains(['.', 'e', 'E'])
    && let Ok(n) = number.parse::<f64>()
  {
    return Ok(Atom::Double((n * f64::from(polarity)).into()));
  }
  #[cfg(feature = "arbitrary-nums")]
  if let Some(n) = big_dec_from_slice(number, radix, polarity) {
    return Ok(Atom::BigDec(n));
  }

  Err(Code::InvalidNumber)
}

#[inline]
#[cfg(feature = "arbitrary-nums")]
fn big_int_from_slice(slice: &str, radix: u8, polarity: i8) -> Option<num_bigint::BigInt> {
  // strip ending N, if it exists
  let slice = slice.strip_suffix('N').map_or(slice, |slice| slice);
  let num = num_bigint::BigInt::parse_bytes(slice.as_bytes(), radix.into())?;
  Some(num * polarity)
}

#[inline]
#[cfg(feature = "arbitrary-nums")]
fn big_dec_from_slice(slice: &str, radix: u8, polarity: i8) -> Option<bigdecimal::BigDecimal> {
  // strip ending M, if it exists
  let slice = slice.strip_suffix('M').map_or(slice, |slice| slice);
  let num = bigdecimal::BigDecimal::parse_bytes(slice.as_bytes(), radix.into())?;
  Some(num * polarity)
}