pcomb 0.3.0

//! Generic static-dispatch-based parser combinators over slice types.
//!
//! For now, see the documentation for the [Parse] trait, which is the main trait of this module.
// todo: add descriptive module documentation: introduce the idea of the remainder and output

#[cfg(feature = "std")]
use std::error::Error;

use core::convert::Infallible;
use core::fmt::{self, Display, Formatter};
use core::iter::{self, Extend};
use core::marker::PhantomData;
use core::mem::{self, MaybeUninit};
use core::ptr;

use crate::slice::Slice;


/// A non-descriptive failure to parse a given input
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
pub enum ParseError {
  /// General rejection: an invalid input has been rejected for an unspecified reason
  Reject,
  /// The input is insufficiently short to conclusively determine if it matches
  Indeterminate,  // todo: this is not respected in certain cases
}

impl Display for ParseError {
  fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    match self {
      ParseError::Reject => write!(f, "Input rejected"),
      ParseError::Indeterminate => {
        write!(f, "Insufficent input to conclusively determine validity")
      },
    }
  }
}

#[cfg(feature = "std")]
impl Error for ParseError {}


/// Tries to parse part of a slice into another form, returning the unparsed
/// __remainder__ of the slice and the __output__ value, or an error.
///
/// This trait is also implemented for all `Fn(T) -> Result<(T, Output), Err>`,
/// so it's possible to use a function to implement a parser.
///
/// # Examples
/// ```
/// use pcomb::parse::{Parse, ParseError};
/// use pcomb::slice::Slice;
///
/// fn alpha(input: &str) -> Result<(&str, &str), ParseError> {
///   let (char, rest) = Slice::split_at(&input, 1).ok_or(ParseError::Reject)?;
///
///   if "a" <= char && char <= "z" || "A" <= char && char <= "Z" {
///     Ok((rest, char))
///   } else {
///     Err(ParseError::Reject)
///   }
/// }
///
/// assert_eq!(alpha.parse("asdf"), Ok(("sdf", "a")));
/// assert_eq!(alpha.parse("1234"), Err(ParseError::Reject));
/// ```
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub trait Parse<T> {
  type Output;
  type Err;

  /// Try to parse part of a slice, returning a tuple of the remainder (the
  /// unparsed slice) and the output value.
  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err>;


  /// Maps the output of a parser with a function to produce a new output.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  /// use pcomb::parsers::str::{alpha, integer};
  ///
  /// #[derive(Debug, Clone, PartialEq, Eq)]
  /// enum Op { Add, Sub, Mul, Div, Int(u32) }
  /// use Op::*;
  ///
  /// let parser = Match("+").map(|_| Add)
  ///   .or(Match("-").map(|_| Sub))
  ///   .or(Match("*").map(|_| Mul))
  ///   .or(Match("/").map(|_| Div))
  ///   .or(integer.map(|num| Int(num)));
  ///
  /// assert_eq!(parser.clone().parse("-"), Ok(("", Sub)));
  /// assert_eq!(parser.clone().parse("24"), Ok(("", Int(24u32))));
  /// assert_eq!(parser.clone().parse("/"), Ok(("", Div)));
  /// assert_eq!(parser.clone().parse("*"), Ok(("", Mul)));
  /// assert_eq!(parser.parse("^"), Err(ParseError::Reject));
  /// ```
  fn map<F, O>(self, func: F) -> Map<T, Self, F, O>
  where F: Fn(Self::Output) -> O, Self: Sized {
    Map { parser: self, func, _t: PhantomData }
  }

  // todo: doctest
  /// Maps the error of a parser with a function to produce a new error.
  fn map_err<F, E>(self, func: F) -> MapErr<T, Self, F, E>
  where F: Fn(Self::Err) -> E, Self: Sized {
    MapErr { parser: self, func, _t: PhantomData }
  }

  /// Executes the parser if possible, wrapping up the output in an Option.
  ///
  /// If you want to provide a default value for None results, see
  /// [Maybe::unwrap_or].
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  ///
  /// let parser = Match("http://example.com/index")
  ///   .fuse(Match(".html").maybe());
  ///
  /// assert_eq!(
  ///   parser.clone().parse("http://example.com/index"),
  ///   Ok(("", ("http://example.com/index", None)))
  /// );
  /// assert_eq!(
  ///   parser.clone().parse("http://example.com/index.html"),
  ///   Ok(("", ("http://example.com/index", Some(".html"))))
  /// );
  /// ```
  fn maybe(self) -> Maybe<T, Self>
  where T: Clone, Self: Sized {
    Maybe { parser: self, _t: PhantomData }
  }

  // todo: doctest
  /// Parses the output of this parser with an inner parser, and passes the
  /// output through.
  fn chain<I>(self, inner: I) -> Chain<T, Self, I>
  where I: Parse<Self::Output, Err = Self::Err>, Self: Sized {
    Chain { parser: self, inner_parser: inner, _t: PhantomData }
  }

  /// Takes the union of both combinators, accepting input which passes either
  /// parser. Both parsers must output the same type.
  ///
  /// This is evaluated lazily: if the input would pass both combinators, the
  /// first from `self` is used.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  /// use pcomb::parsers::str::{alpha, integer};
  ///
  /// let parser = integer
  ///   .fuse(
  ///     Match("+")
  ///       .or(Match("-"))
  ///       .or(Match("*"))
  ///       .or(Match("/"))
  ///   )  // Output = (u32, &str)
  ///   .fuse(integer);  // Output = ((u32, &str), u32)
  ///
  /// assert_eq!(parser.clone().parse("54+3"), Ok(("", ((54, "+"), 3))));
  /// assert_eq!(parser.clone().parse("19/0"), Ok(("", ((19, "/"), 0))));
  /// assert_eq!(parser.parse("-2"), Err(ParseError::Reject));
  /// ```
  fn or<O>(self, other: O) -> Or<T, Self, O>
  where T: Clone, O: Parse<T, Output = Self::Output, Err = Self::Err>, Self: Sized {
    Or { left: self, right: other, _t: PhantomData }
  }

  // todo: doctest
  /// Takes the conjunction of both combinators, accepting input which passes
  /// both parsers. The remainders of both combinators must be equal, otherwise
  /// the specified length error is yielded.
  ///
  /// This is evaluated lazily: if the first input does not pass, the other is
  /// not ran. If you want to ignore the output of one of the parsers, see
  /// [And::first] or [And::second].
  fn and<O>(self, length_err: Self::Err, other: O) -> And<T, Self, O>
  where T: Clone + Eq, O: Parse<T, Err = Self::Err>, Self: Sized {
    And { left: self, right: other, length_err: length_err, _t: PhantomData }
  }

  /// Accepts input which passes this parser first and then `other`, packing the
  /// output as a tuple. The remainder of the input is passed to `other`.
  ///
  /// If you want to concatenate the output of both parsers, see
  /// [Parse::fuse_extend]. If you want to ignore the output of one of the
  /// parsers, see [Fuse::first] or [Fuse::second].
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  /// use pcomb::parsers::str::{alpha, integer};
  ///
  /// let parser = alpha
  ///   .fuse(Match(" = ")) // Fuse's Output = ("x", " = ")
  ///   .first()  // now the Output = "x"
  ///   .fuse(integer);  // Output = ("x", 2u32)
  ///
  /// assert_eq!(parser.parse("x = 2;"), Ok((";", ("x", 2u32))));
  /// ```
  fn fuse<O>(self, other: O) -> Fuse<T, Self, O>
  where O: Parse<T, Err = Self::Err>, Self: Sized, {
    Fuse { left: self, right: other, _t: PhantomData }
  }

  /// Accepts input which passes this parser first and then `other`, extending
  /// this output with `other`'s output. The remainder of the input is passed
  /// to `other`.
  ///
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match};
  ///
  /// // we want to verify it is an integer but ignore the output
  /// let parser = Match("hello")
  ///   .map(|out| out.to_owned())  // map to a type that supports Extend
  ///   .fuse_extend(Match(" "))
  ///   .fuse_extend(Match("world"));
  ///
  /// assert_eq!(parser.parse("hello world!"), Ok(("!", "hello world".to_owned())));
  /// ```
  fn fuse_extend<O>(self, other: O) -> FuseExtend<T, Self, Self::Output, O>
  where O: Parse<T, Err = Self::Err>, Self::Output: Extend<O::Output>, Self: Sized {
    FuseExtend { left: self, right: other, _t: PhantomData }
  }

  /// Accepts exactly a constant amount of repetitions of this parser, packing
  /// the output as a constant array.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  /// use pcomb::parsers::str::alpha;
  ///
  /// let parser = alpha.repeat_const::<5>();
  ///
  /// assert_eq!(
  ///   parser.clone().parse("hello world!"),
  ///   Ok((" world!", ["h", "e", "l", "l", "o"]))
  /// );
  /// assert_eq!(parser.clone().parse("hi world"), Err(ParseError::Reject));
  /// ```
  fn repeat_const<const N: usize>(self) -> RepeatConst<T, Self, N>
  where Self: Clone + Sized {
    RepeatConst { parser: self, _t: PhantomData }
  }

  /// Accepts any amount of repetitions of this parser, extending the output
  /// into the given collection.
  ///
  /// Default is the default value of the collection, and is what is yielded
  /// when no repetitions occur.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match};
  /// use pcomb::parsers::str::alpha;
  ///
  /// let word = alpha.repeat_greedy(String::new());  // a String of consecutive letters
  /// let words_by_spaces = word.clone()  // a Vec of words separated by spaces
  ///   .fuse(Match(" "))
  ///   .first()
  ///   .repeat_greedy(Vec::new());
  ///
  /// assert_eq!(
  ///   word.clone().parse("hello world"),
  ///   Ok((" world", "hello".to_owned()))
  /// );
  /// assert_eq!(
  ///   words_by_spaces.clone().parse("hello world "),
  ///   Ok(("", vec!["hello".to_owned(), "world".to_owned()]))
  /// );
  /// ```
  fn repeat_greedy<O>(self, default: O) -> RepeatGreedy<T, Self, O>
  where T: Clone, O: Extend<Self::Output>, Self: Clone + Sized {
    RepeatGreedy { parser: self, output: default, _t: PhantomData }
  }
}

impl<T, F, R, E> Parse<T> for F
where F: Fn(T) -> Result<(T, R), E> {
  type Err = E;
  type Output = R;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> { self(input) }
}


// todo: doctest
/// Accepts no input, and produce an empty output.
///
/// Empty is infallible: use [Parse::map_err] to specify an error type.
#[derive(Debug, PartialEq, Eq, Clone, Hash, Default)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Empty;

impl<T: Slice<Output = T>> Parse<T> for Empty {
  type Err = Infallible;  // convert to never type (!) when stable
  type Output = T;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    Ok(input.split_at(input.len()).expect("slicing from [i..i] from to [..] must never fail"))
  }
}


// todo: doctest
/// Accept the entire remainder for any input.
///
/// Identity is infallible: use [Parse::map_err] to specify an error type.
#[derive(Debug, PartialEq, Eq, Clone, Hash, Default)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Identity;

impl<T: Slice<Output = T>> Parse<T> for Identity {
  type Err = Infallible;  // convert to never type (!) when stable
  type Output = T;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    Ok(input.split_at(0).expect("slicing from [i..i] or from [..] must never fail"))
  }
}


// todo: doctest
/// Accepts the slice if the input matches the specified sliced.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Match<T: Slice + Eq>(pub T);

impl<T: Slice<Output = T> + Eq> Parse<T> for Match<T> {
  type Err = ParseError;
  type Output = T::Output;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    if self.0.len() > input.len() {
      Err(ParseError::Indeterminate)
    } else {
      input
        .split_at(self.0.len())
        .filter(|(matched, _)| *matched == self.0)
        .map(|(matched, rest)| (rest, matched))
        .ok_or(ParseError::Reject)
    }
  }
}


/// The parser for [Parse::map], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Map<T, P, F, O>
where P: Parse<T>, F: Fn(P::Output) -> O {
  parser: P,
  func: F,
  _t: PhantomData<T>,
}

impl<T, P, F, O> Parse<T> for Map<T, P, F, O>
where P: Parse<T>, F: Fn(P::Output) -> O {
  type Err = P::Err;
  type Output = O;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    self.parser.parse(input).map(|(rest, output)| {
      (rest, (self.func)(output))
    })
  }
}


/// The parser for [Parse::map_err], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct MapErr<T, P, F, E>
where P: Parse<T>, F: Fn(P::Err) -> E {
  parser: P,
  func: F,
  _t: PhantomData<T>,
}

impl<T, P, F, E> Parse<T> for MapErr<T, P, F, E>
where P: Parse<T>, F: Fn(P::Err) -> E {
  type Err = E;
  type Output = P::Output;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    self.parser.parse(input).map_err(|err| { (self.func)(err) })
  }
}


/// The parser for [Parse::maybe], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Maybe<T, P>
where T: Clone, P: Parse<T> {
  parser: P,
  _t: PhantomData<T>,
}

impl<T, P> Maybe<T, P>
where T: Clone, P: Parse<T> {
  /// Unwraps the inner option if possible, or otherwise the provided default
  /// value is used.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  ///
  /// let parser = Match("http://example.com/index").map(|str| str.to_owned())
  ///   .fuse_extend(Match(".html").maybe().unwrap_or(""));
  ///
  /// assert_eq!(
  ///   parser.clone().parse("http://example.com/index"),
  ///   Ok(("", "http://example.com/index".to_owned()))
  /// );
  /// assert_eq!(
  ///   parser.parse("http://example.com/index.html"),
  ///   Ok(("", "http://example.com/index.html".to_owned()))
  /// );
  /// ```
  // note: the generic bounds on the impl Fn cannot include Copy + Send + Sync with specialization
  pub fn unwrap_or(self, default: P::Output) ->
  Map<T, Self, impl Clone + Fn(Option<P::Output>) -> P::Output, P::Output>
  where P::Output: Clone {
    self.map(move |option| option.unwrap_or(default.clone()))
  }
}

impl<T, P> Parse<T> for Maybe<T, P>
where T: Clone, P: Parse<T> {
  type Err = P::Err;
  type Output = Option<P::Output>;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    match self.parser.parse(input.clone()) {
      Ok((rest, output)) => Ok((rest, Some(output))),
      Err(_) => Ok((input, None)),
    }
  }
}


/// The parser for [Parse::chain], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Chain<T, P, I>
where P: Parse<T>, I: Parse<P::Output, Err = P::Err> {
  parser: P,
  inner_parser: I,
  _t: PhantomData<T>,
}

impl<T, P, I> Parse<T> for Chain<T, P, I>
where P: Parse<T>, I: Parse<P::Output, Err = P::Err> + Clone {
  type Err = P::Err;
  type Output = I::Output;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    let (rest, res) = self.parser
      .map(|output| self.inner_parser.clone().parse(output))
      .parse(input)?;

    let (_, output) = res?;
    Ok((rest, output))
  }
}


/// The parser for [Parse::or], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Or<T, L, R>
where T: Clone, L: Parse<T>, R: Parse<T, Output = L::Output, Err = L::Err> {
  left: L,
  right: R,
  _t: PhantomData<T>,
}

impl<T, L, R> Parse<T> for Or<T, L, R>
where T: Clone, L: Parse<T>, R: Parse<T, Output = L::Output, Err = L::Err> {
  type Err = L::Err;
  type Output = L::Output;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    match self.left.parse(input.clone()) {
      Ok(res) => Ok(res),
      Err(_) => self.right.parse(input), // todo: consider handling Indeterminate differently
    }
  }
}


/// The parser for [Parse::or], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct And<T, L, R>
where T: Clone + Eq, L: Parse<T>, R: Parse<T, Err = L::Err> {
  left: L,
  right: R,
  length_err: L::Err,
  _t: PhantomData<T>,
}

impl<T, L, R> And<T, L, R>
where T: Clone + Eq, L: Parse<T>, R: Parse<T, Err = L::Err> {
  /// Pass through the first parser's output, dropping the output of the second.
  ///
  /// Due to the architecture of Parse, it is important to note that both
  /// parsers are still ran. This is commonly used when the second output of a
  /// conjunction parser is not desired, such as when checking a precondition.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  /// use pcomb::parsers::str::integer;
  ///
  /// // we want to verify it is an integer but ignore the output
  /// let parser = Match("420")
  ///   .and(ParseError::Reject, integer::<u32>)  // this fuse has Output = ("420", 420)
  ///   .first();  // now Output = "420"
  ///
  /// assert_eq!(parser.parse("420.1"), Ok((".1", "420")));
  /// ```
  pub fn first(self) -> Map<T, Self, impl Clone + Copy + Send + Sync + Fn((L::Output, R::Output)) -> L::Output, L::Output> {
    self.map(|(out, _)| out)
  }

  /// Pass through the second parser's output, dropping the output of the first.
  ///
  /// Due to the architecture of Parse, it is important to note that both
  /// parsers are still ran. This is commonly used when the second output of a
  /// conjunction parser is not desired, such as when checking a precondition.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match, ParseError};
  /// use pcomb::parsers::str::integer;
  ///
  /// // we want to verify it is exactly 420 but want it as an integer
  /// let parser = Match("420")
  ///   .and(ParseError::Reject, integer::<u32>)  // this fuse has Output = ("420", 420)
  ///   .second();  // now Output = 420
  ///
  /// assert_eq!(parser.parse("420.1"), Ok((".1", 420)));
  /// ```
  pub fn second(self) -> Map<T, Self, impl Clone + Copy + Send + Sync + Fn((L::Output, R::Output)) -> R::Output, R::Output> {
    self.map(|(_, out)| out)
  }
}

impl<T, L, R> Parse<T> for And<T, L, R>
where T: Clone + Eq, L: Parse<T>, R: Parse<T, Err = L::Err> {
  type Err = L::Err;
  type Output = (L::Output, R::Output);

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    let (left_rest, left_output) = self.left.parse(input.clone())?;
    let (right_rest, right_output) = self.right.parse(input)?;

    if left_rest == right_rest {
      Ok((left_rest, (left_output, right_output)))
    } else {
      Err(self.length_err)
    }
  }
}


/// The parser for [Parse::fuse], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct Fuse<T, L, R>
where L: Parse<T>, R: Parse<T, Err = L::Err> {
  left: L,
  right: R,
  _t: PhantomData<T>,
}

impl<T, L, R> Fuse<T, L, R>
where L: Parse<T>, R: Parse<T, Err = L::Err> {
  /// Pass through the first parser's output, dropping the output of the second.
  ///
  /// Due to the architecture of Parse, it is important to note that both
  /// parsers are still ran. This is commonly used when the second output of a
  /// fused parser is not desired, such as when parsing delimiters.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match};
  ///
  /// let parser = Match("hello")
  ///   .fuse(Match(" "))  // this fuse has Output = ("hello", " ")
  ///   .first()  // now Output = "hello"
  ///   .map(|out: &str| Vec::from([out]))  // convert into a Vec and push it
  ///   .fuse_extend(Match("world"));
  ///
  /// // notice how the space get excluded
  /// assert_eq!(parser.parse("hello world!"), Ok(("!", vec!["hello", "world"])));
  /// ```
  pub fn first(self) -> Map<T, Self, impl Clone + Copy + Send + Sync + Fn((L::Output, R::Output)) -> L::Output, L::Output> {
    self.map(|(out, _)| out)
  }

  /// Pass through the second parser's output, dropping the output of the first.
  ///
  /// Due to the architecture of Parse, it is important to note that both
  /// parsers are still ran. This is commonly used when the first output of a
  /// fused parser is not desired, such as when parsing delimiters.
  ///
  /// # Examples
  /// ```
  /// use pcomb::parse::{Parse, Match};
  /// use pcomb::parsers::str::{alpha, integer};
  ///
  /// let parser = Match("let ")
  ///   .fuse(alpha)  // this fuse has Output = ("let ", "x")
  ///   .second()  // now Output = "x"
  ///   .fuse(Match(" = "))  // Output = ("x", " = ")
  ///   .first()  // Output = ("x")
  ///   .fuse(integer::<u32>);  // Output = ("x", 4)
  ///
  /// assert_eq!(parser.parse("let x = 4;"), Ok((";", ("x", 4))));
  /// ```
  pub fn second(self) -> Map<T, Self, impl Clone + Copy + Send + Sync + Fn((L::Output, R::Output)) -> R::Output, R::Output> {
    self.map(|(_, out)| out)
  }
}

impl<T, L, R> Parse<T> for Fuse<T, L, R>
where L: Parse<T>, R: Parse<T, Err = L::Err> {
  type Err = L::Err;
  type Output = (L::Output, R::Output);

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    let (rest, left_output) = self.left.parse(input)?;
    let (rest, right_output) = self.right.parse(rest)?;
    Ok((rest, (left_output, right_output)))
  }
}


/// The parser for [Parse::fuse_extend], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct FuseExtend<T, L, LO, R>
where L: Parse<T, Output = LO>, R: Parse<T, Err = L::Err>, LO: Extend<R::Output> {
  left: L,
  right: R,
  _t: PhantomData<T>,
}

impl<T, L, LO, R> Parse<T> for FuseExtend<T, L, LO, R>
where L: Parse<T, Output = LO>, R: Parse<T, Err = L::Err>, LO: Extend<R::Output> {
  type Err = L::Err;
  type Output = L::Output;

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    let (rest, (mut left, right)) = self.left.fuse(self.right).parse(input)?;
    left.extend(iter::once(right));
    Ok((rest, left))
  }
}


/// The parser for [Parse::repeat_const], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct RepeatConst<T, P, const N: usize>
where P: Parse<T> + Clone {
  parser: P,
  _t: PhantomData<T>,
}

impl<T, P, const N: usize> Parse<T> for RepeatConst<T, P, N>
where P: Parse<T> + Clone {
  type Err = P::Err;
  type Output = [P::Output; N];

  fn parse(self, input: T) -> Result<(T, Self::Output), Self::Err> {
    let mut output: [MaybeUninit<P::Output>; N] = unsafe {
      MaybeUninit::uninit().assume_init()
    };

    let mut rest = input;

    for i in 0..N {
      match self.parser.clone().parse(rest) {
        Ok((new_rest, new_output)) => {
          rest = new_rest;
          output[i].write(new_output);
        },
        Err(error) => {
          // since MaybeUninit doesn't implement Drop, we should drop individual
          // elements if we are going to return early to avoid not running Drop
          for item in &mut output[0..i] {  // i is exclusive
            // safety: we have written an element to every index before index i.
            // since item can only be from before index i, we must of written to
            // it before.
            unsafe { ptr::drop_in_place(item.as_mut_ptr()); }
          }

          return Err(error);
        }
      }
    }

    // safety: at this point the entire array can only be full. We have written
    // an element to every index. Therefore each element is initialized. Also
    // MaybeUninit<T> is guaranteed to have the same binary representation as T,
    // so transmuting from MaybeUninit<T> to T is always sound so long as T is
    // initialized and valid.
    // note: this requires transmute_copy because https://github.com/rust-lang/rust/issues/61956
    let output: [P::Output; N] = unsafe { mem::transmute_copy(&output) };
    Ok((rest, output))
  }
}


/// The parser for [Parse::repeat_greedy], see method for documentation.
#[derive(Debug, PartialEq, Eq, Clone, Hash)]
#[must_use = "parsers are lazy and do not do anything until consumed"]
pub struct RepeatGreedy<T, P, O>
where T: Clone, P: Parse<T> + Clone, O: Extend<P::Output> {
  parser: P,
  output: O,
  _t: PhantomData<T>,
}

impl<T, P, O> Parse<T> for RepeatGreedy<T, P, O>
where T: Clone, P: Parse<T> + Clone, O: Extend<P::Output> {
  type Err = P::Err;  // todo: infallible
  type Output = O;

  fn parse(mut self, input: T) -> Result<(T, Self::Output), Self::Err> {
    let mut rest = input;

    loop {
      match self.parser.clone().parse(rest.clone()) {
        Ok((new_rest, output)) => {
          rest = new_rest;
          self.output.extend(iter::once(output));
        },
        // todo: consider an adapter which does not drop the error
        Err(_) => return Ok((rest, self.output)),
      }
    }
  }
}


// todo: RepeatLazy, a repeat with Err?, repeat_at_least, repeat not const


// todo: macro docs
#[macro_export]
macro_rules! any_of {
  ($parser1:expr $(, $parser:expr )* $(,)? ) => {
    {
      use $crate::parse::Parse;

      $parser1
        $(
          .or($parser)
        )*
    }
  };
}

#[macro_export]
macro_rules! any_of_match {
  ( $($parser:expr),* $(,)? ) => {
    any_of!(
      $(
        Match($parser),
      )*
    )
  };
}

#[macro_export]
macro_rules! any_of_match_arr {
  ( $($parser:expr),* $(,)? ) => {
    any_of!(
      $(
        // todo: this is stupid, &[T; N] does not work in certain cases
        Match(&[$parser][..]),
      )*
    )
  };
}


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

  #[test]
  fn slice() {
    let slice = "asdfghjk";
    for i in 0..slice.len() + 1 {
      for j in 0..slice.len() + 1 {
        assert_eq!(slice.slice(i..j), slice.get(i..j));
      }
    }
  }

  #[test]
  fn split_at() {
    let slice = "asdfghjk";
    assert_eq!(Slice::split_at(&slice, 3), Some(("asd", "fghjk")));
  }

  #[test]
  fn match_test() {
    let val = "asdfg";
    assert_eq!(val.parse_with(Match("asd")), Ok(("fg", "asd")));
  }

  #[test]
  fn any_of() {
    let parser = any_of!(Match("a"), Match("b"), Match("c").map(|_| "C"));
    assert_eq!(parser.clone().parse(&"abcde"), Ok(("bcde", "a")));
    assert_eq!(parser.clone().parse(&"cde"), Ok(("de", "C")));
    assert_eq!(parser.parse(&"def"), Err(ParseError::Reject));
  }

  #[test]
  fn any_of_match() {
    let parser = any_of_match!("a", "b", "c", "d", "e", "f");
    assert_eq!(parser.clone().parse("fedcba"), Ok(("edcba", "f")));

    let parser = any_of_match_arr![2i32, 4i32, 6i32, 8i32, 0i32];
    assert_eq!(parser.parse(&[2i32, 3, 4][..]), Ok((&[3, 4][..], &[2][..])));
  }
}