ParserConvertible.swift

typealias Parser<T: Collection, U, T2> = (T) -> (U, T2)?
typealias StandardParser<T: Collection, U> = Parser<T, U, T>
typealias HomogeneousParser<T: Collection> = StandardParser<T, T>

protocol ParserConvertible {
  associatedtype InputType : Collection = Self
  associatedtype ParsedValueType = Self
  associatedtype OutputType = Self
  func mkParser() -> Parser<InputType, ParsedValueType, OutputType>
}

/// A parser which matches the prefix `pattern`
func match<InputType: Collection>(_ pattern: InputType) -> Parser<InputType.SubSequence, InputType.SubSequence, InputType.SubSequence> where InputType.Element : Equatable {
  return { source in
    if source.starts(with: pattern, by: { $0 == $1 }) {
      return (source.prefix(pattern.count), source.dropFirst(pattern.count))
    } else {
      return nil
    }
  }
}


func accept<Element, T: Collection>(range: ClosedRange<Element>) -> Parser<T, Element, T.SubSequence>
  where Element == T.Element {
  return { source in
    if let first = source.first, range.contains(first) {
      return (first, source.dropFirst())
    } else {
      return nil
    }
  }
}

extension Array : ParserConvertible where Element : Equatable {
  func mkParser() -> HomogeneousParser<ArraySlice<Element>> {
    return match(self)    
  }
}

extension ArraySlice : ParserConvertible where Element : Equatable {
  func mkParser() -> HomogeneousParser<ArraySlice<Element>> {
    return match(self)
  }
}

extension Substring : ParserConvertible {
  func mkParser() -> HomogeneousParser<Substring> {
    return match(self)
  }
}

extension String : ParserConvertible {
  func mkParser() -> HomogeneousParser<Substring> {
    return match(self)
  }
}

enum LexicalToken {
  case leftParen
  case rightParen
  case name(String)
}

extension LexicalToken : Equatable {}

extension LexicalToken : ParserConvertible {
  func mkParser() -> StandardParser<ArraySlice<LexicalToken>, LexicalToken> {
    return { source in
      if let first = source.first, first == self {
        return (first, source.dropFirst())
      } else {
        return nil
      }
    }
  }
}

/// A parser that succeeds when `parser` succeeds.
func identity<T, U, V, ParserLike: ParserConvertible>(_ parser: ParserLike) -> Parser<T, U, V> where
  T == ParserLike.InputType,
  U == ParserLike.ParsedValueType,
  V == ParserLike.OutputType
{
  return { source in
    parser.mkParser()(source)    
  }
}

/// A parser that succeeds when `left` and `right` both succeed in order.
func seq<T, LeftParserLike: ParserConvertible, RightParserLike: ParserConvertible>(
  _ left: LeftParserLike,
  _ right: RightParserLike
) -> Parser<T, (LeftParserLike.ParsedValueType, RightParserLike.ParsedValueType), RightParserLike.OutputType> where
  T == LeftParserLike.InputType,
  RightParserLike.InputType == LeftParserLike.OutputType
{
  return { source in
    left.mkParser()(source).flatMap { leftResult in
      right.mkParser()(leftResult.1).map { rightResult in
        ((leftResult.0, rightResult.0), rightResult.1)
      }
    }
  }
}

func seq<LeftInputType: Collection, LeftParsedValueType, LeftOutputType, RightParserLike: ParserConvertible>(
  _ left: @autoclosure @escaping () -> Parser<LeftInputType, LeftParsedValueType, LeftOutputType>,
  _ right: RightParserLike
) -> Parser<LeftInputType, (LeftParsedValueType, RightParserLike.ParsedValueType), RightParserLike.OutputType> where
  RightParserLike.InputType == LeftOutputType
{
  return { source in
    left()(source).flatMap { leftResult in
      right.mkParser()(leftResult.1).map { rightResult in
        ((leftResult.0, rightResult.0), rightResult.1)
      }
    }
  }
}

func seq<LeftParserLike: ParserConvertible, RightInputType: Collection, RightParsedValueType, RightOutputType>(
  _ left: LeftParserLike,
  _ right: @autoclosure @escaping () -> Parser<RightInputType, RightParsedValueType, RightOutputType>
) -> Parser<LeftParserLike.InputType, (LeftParserLike.ParsedValueType, RightParsedValueType), RightOutputType> where
  LeftParserLike.OutputType == RightInputType
{
  return { source in
    left.mkParser()(source).flatMap { leftResult in
      right()(leftResult.1).map { rightResult in
        ((leftResult.0, rightResult.0), rightResult.1)
      }
    }
  }
}

infix operator ~: MultiplicationPrecedence
func ~<T, LeftParserLike: ParserConvertible, RightParserLike: ParserConvertible>(
  _ left: LeftParserLike,
  _ right: RightParserLike
) -> Parser<T, (LeftParserLike.ParsedValueType, RightParserLike.ParsedValueType), RightParserLike.OutputType> where
  T == LeftParserLike.InputType,
  RightParserLike.InputType == LeftParserLike.OutputType
{
  return seq(left, right)
}

func ~<LeftInputType: Collection, LeftParsedValueType, LeftOutputType, RightParserLike: ParserConvertible>(
  _ left: @autoclosure @escaping () -> Parser<LeftInputType, LeftParsedValueType, LeftOutputType>,
  _ right: RightParserLike
) -> Parser<LeftInputType, (LeftParsedValueType, RightParserLike.ParsedValueType), RightParserLike.OutputType> where
  RightParserLike.InputType == LeftOutputType
{
  return seq(left(), right)
}

func ~<LeftParserLike: ParserConvertible, RightInputType: Collection, RightParsedValueType, RightOutputType>(
  _ left: LeftParserLike,
  _ right: @autoclosure @escaping () -> Parser<RightInputType, RightParsedValueType, RightOutputType>
) -> Parser<LeftParserLike.InputType, (LeftParserLike.ParsedValueType, RightParsedValueType), RightOutputType> where
  LeftParserLike.OutputType == RightInputType
{
  return seq(left, right())
}


let a = identity("test")
a("test test test")

let parser = "(" ~ "idea!" ~ ")"
if let (((first, second), third), remaining) = parser("(idea!)") {
  print(first, second, third, remaining)
}


let args = LexicalToken.leftParen ~ LexicalToken.name("arg") ~ LexicalToken.rightParen
let result = args([LexicalToken.leftParen, .name("arg"), .rightParen])
print(result)

let parser2 = [1,2,3] ~ [4,5,6]
print(parser2([1,2,3,4,5,6]))


let test = match("test")
print(test("test string"))


let sub: Substring = "123"
let str = sub