sparse.swift

enum Expr {
  case Lit(Int)
  indirect case Neg(Expr)
  indirect case Add(Expr,Expr)
  indirect case Mul(Expr,Expr)
  indirect case Sub(Expr,Expr)
}

let spaces = many(oneof(" \n\r"))
func token<P: ParserType>(p: P) -> Parser<P.A> {
  return p <* spaces
}
func reserved(word: String) -> Parser<String> {
  return token(match(word))
}
let digit = oneof("0123456789").map { c in Int(String(c))! }
let digits = some(digit)
let integer = digits.map { d in d.reduce(0) { (a,e) in e + 10 * a } }
func between<
  P: ParserType,
  Q: ParserType,
  R: ParserType
  >(o: P, c: Q, p: R) -> Parser<R.A> {
    return o *> (p <* c).commit()
}
func parens<P: ParserType>(p: P) -> Parser<P.A> {
  return between(reserved("("), c: reserved(")"), p: p)
}
func infixop<A>(opName: String, opFunc: (A,A) -> A) -> Parser<(A,A) -> A> {
  return reserved(opName) *> pure(opFunc)
}
func id<A>(x: A) -> A { return x }
func prefixop<A>(opName: String, opFunc: A -> A) -> ChoiceParser<A -> A> {
  return (reserved(opName) *> pure(opFunc)).or(pure(id))
}
let negate: ChoiceParser<Expr -> Expr> = prefixop("-", opFunc: Expr.Neg)
let mulop: Parser<(Expr,Expr) -> Expr> = infixop("*", opFunc: Expr.Mul)
let addop: ChoiceParser<(Expr,Expr) -> Expr> = infixop("+", opFunc: Expr.Add).or(infixop("-", opFunc: Expr.Sub))
func factor() -> Parser<Expr> {
  return negate <*> (token(integer).map(Expr.Lit).or(parens(expr())))
}
func term() -> ChainL1Parser<Parser<Expr>, Parser<(Expr,Expr) -> Expr>> {
  return  chainl1(factor, op: mulop)
}
func expr() -> ChainL1Parser<ChainL1Parser<Parser<Expr>, Parser<(Expr,Expr) -> Expr>>, ChoiceParser<(Expr,Expr) -> Expr>> {
  return chainl1(term, op: addop)
}

extension Expr {
  func eval() -> Int {
    switch self {
    case let .Lit(x): return x
    case let .Neg(e): return -e.eval()
    case let .Add(a,b): return a.eval() + b.eval()
    case let .Mul(a,b): return a.eval() * b.eval()
    case let .Sub(a,b): return a.eval() - b.eval()
    }
  }
}

switch expr().parse("(2 + 2) - a * 4") {
case let .Left(e):
  print(e)
  print(e.eval())
case let .Right(e): print(e)
}
  


public typealias ParseIndex = (line: Int, ind: String.Index)

public protocol ParserType {
  associatedtype A
  func run(_: String, _: ParseIndex) -> ParseResult<A>
}

public struct Parser<A>: ParserType {
  private let _run: (String,ParseIndex) -> ParseResult<A>
  public func run(s: String, _ i: ParseIndex) -> ParseResult<A> {
    return self._run(s,i)
  }
  public init(_ f: (String,ParseIndex) -> ParseResult<A>) {
    self._run = f
  }
}

public enum ParseResult<A> {
  case Some(A, ParseIndex)
  case Failure(Int, Set<String>, Bool, ParseIndex) // Expected length, expected values, committed, location
}

public extension ParseResult {
  func map<B>(f: A -> B) -> ParseResult<B> {
    switch  self {
    case let .Some(x,i): return .Some(f(x),i)
    case let .Failure(l,e,c,i):
      return .Failure(l,e,c,i)
    }
  }
}

public struct MappedParser<P: ParserType, A>: ParserType {
  private let p: P
  private let f: P.A -> A
  public func run(s: String, _ i: ParseIndex) -> ParseResult<A> {
    switch  p.run(s,i) {
    case let .Some(x,l): return .Some(f(x),l)
    case let .Failure(l,e,c,i):
      return .Failure(l, e, c, i)
    }
  }
  public func map<B>(t: A -> B) -> MappedParser<P,B> {
    let o = self.f
    return MappedParser<P,B>(p: p) { x in t(o(x)) }
  }
}

infix operator <*> { precedence 120 associativity left }

public func <*><A,B>(lhs: ParseResult<A->B>, rhs: ParseResult<A>) -> ParseResult<B> {
  switch  lhs {
  case let .Some(f,_): return rhs.map(f)
  case let .Failure(l,e,c,i):
    return .Failure(l, e, c, i)
  }
}

public extension ParseResult {
  func flatMap<B>(f: A -> ParseResult<B>) -> ParseResult<B> {
    switch self {
    case let .Some(x,_): return f(x)
    case let .Failure(l,e,c,i): return .Failure(l, e, c, i)
    }
  }
}

public extension ParserType {
  func map<B>(f: A -> B) -> MappedParser<Self,B> {
    return MappedParser(p: self, f: f)
  }
}


public extension ParserType {
  func flatMap<P: ParserType>(f: A -> P) -> Parser<P.A> {
    return Parser<P.A> { (on,loc) in
      switch self.run(on,loc) {
      case let .Some(x,i): return f(x).run(on,i)
      case let .Failure(l,e,c,i): return .Failure(l, e, c, i)
      }
    }
  }
}

public func pure<A>(x: A) -> Parser<A> {
  return Parser { (on,loc) in .Some(x, loc) }
}

extension SequenceType {
  func count(@noescape pred: Generator.Element throws -> Bool) rethrows -> Int {
    var c = 0
    for el in self where try pred(el) { c += 1 }
    return c
  }
}

extension SequenceType where Generator.Element: Equatable {
  func count(x: Generator.Element) -> Int {
    return self.count { el in x == el }
  }
}

private func quote(s: String) -> String {
  return "\"" + s + "\""
}

public struct MatchParser: ParserType, StringLiteralConvertible, CustomStringConvertible {
  public typealias A = String
  private let s: String
  public var description: String { return "Matches \"\(s)\"" }
  public func run(on: String, _ loc: ParseIndex) -> ParseResult<String> {
    var (lin,cur) = loc
    for c in s.characters {
      if cur == on.endIndex || c != on[cur] {
        return .Failure(s.characters.count, [quote(s)], false, loc)
      } else {
        if c == "\n" { lin += 1 }
        cur = cur.successor()
      }
    }
    return .Some(s, (lin,cur))
  }
  public init(stringLiteral s: String)                  { self.s = s }
  public init(extendedGraphemeClusterLiteral s: String) { self.s = s }
  public init(unicodeScalarLiteral s: String)           { self.s = s }
}

public func match(s: String) -> MatchParser { return MatchParser(stringLiteral: s) }

public func many<P: ParserType>(p: P) -> Parser<[P.A]> {
  return Parser<[P.A]> { (on,loc) in
    var loc = loc
    var res: [P.A] = []
    while true {
      switch p.run(on,loc) {
      case let .Some(x,l):
        res.append(x)
        loc = l
      case .Failure(_,_,false,_): return .Some(res,loc)
      case let .Failure(l,e,c,i): return .Failure(l, e, c, i)
      }
    }
  }
}

public func toDesc(s: Set<String>) -> String {
  switch  s.count {
  case 1: return s.first!
  case 2: return s.joinWithSeparator(" or ")
  case let n:
    return s
      .lazy
      .enumerate()
      .map { (i,s) in i+1 == n ? "or " + s : s }
      .joinWithSeparator(", ")
  }
  
}

public func some<P: ParserType>(p: P) -> Parser<[P.A]> {
  return Parser<[P.A]> { (on,loc) in
    switch  p.run(on,loc) {
    case let .Some(x,l): return many(p).run(on,l).map { r in [x] + r }
    case let .Failure(l,e,false,i):
      return .Failure(l, ["at least one " + toDesc(e)], false, i)
    case let .Failure(l,e,true,i):
      return .Failure(l,e,true,i)
    }
  }
}

public func satisfies(pred: Character -> Bool, dsc: Set<String>) -> Parser<Character> {
  return Parser<Character> { (on,loc) in
    if loc.ind == on.endIndex { return .Failure(1,dsc,false,loc) }
    let c = on[loc.ind]
    if pred(c) {
      return .Some(c, (line: c == "\n" ? loc.line.successor() : loc.line, loc.ind.successor()))
    }
    return .Failure(1,dsc,false,loc)
  }
}


public func oneof(s: String) -> Parser<Character> {
  return satisfies(Set(s.characters).contains, dsc: Set(s.characters.lazy.map { c in String(c) }.map(quote)))
}

public func noneof(s: String) -> Parser<Character> {
  let cs = Set(s.characters)
  return satisfies({c in !cs.contains(c)}, dsc: Set(s.characters.lazy.map { c in String(c) }))
}

extension ParserType {
  public func called(dsc: String) -> Parser<A> {
    return Parser { (on,loc) in
      switch self.run(on,loc) {
      case let .Failure(l,_,c,i):
        return .Failure(l,[dsc],c,i)
      case let s: return s
      }
    }
  }
  public func commit() -> Parser<A> {
    return Parser { (on,loc) in
      switch self.run(on,loc) {
      case let .Failure(l,e,_,i):
        return .Failure(l,e,true,i)
      case let s: return s
      }
    }
  }
}

public enum Either<A,B> {
  case Left(A), Right(B)
}

extension ParserType {
  public func parse(s: String) -> Either<A,String> {
    switch self.run(s, (0,s.startIndex)) {
    case let .Some(x,_): return .Left(x)
    case let .Failure(l,e,_,(n,i)):
      var (c,i) = (0,i)
      while s[i] != "\n" && i != s.startIndex {
        i = i.predecessor()
        c += 1
      }
      return .Right("line \(n+1), column \(c+1)\nUnexpected \(quote(s[i..<i.advancedBy(l, limit: s.endIndex)]))\nExpected \(toDesc(e))")
    }
  }
}

public struct ChainL1Parser<P: ParserType, OP: ParserType where OP.A == (P.A,P.A) -> P.A>: ParserType {
  private let p: () -> P
  private let op: OP
  public func run(on: String, _ loc: ParseIndex) -> ParseResult<P.A> {
    var (x,i): (P.A, ParseIndex)
    switch  p().run(on,loc) {
    case let .Failure(l,e,c,i):
      return .Failure(l,e,c,i)
    case let .Some(v,l): (x,i) = (v,l)
    }
    while true {
      switch op.run(on,i) {
      case let .Failure(l,e,true,n):
        return .Failure(l,e,true,n)
      case .Failure: return .Some(x,i)
      case let .Some(f,n):
        switch p().run(on,n) {
        case let .Some(y,l): (x,i) = (f(x,y),l)
        case let .Failure(l,e,c,i):
          return .Failure(l,e,c,i)
        }
      }
    }
  }
}

public func chainl1<P: ParserType, OP: ParserType where OP.A == (P.A,P.A) -> P.A>(p: () -> P, op: OP) -> ChainL1Parser<P,OP> {
  return ChainL1Parser(p: p, op: op)
}

public struct ChoiceParser<A>: ParserType {
  private let ps: [Parser<A>]
  public func run(on: String, _ loc: ParseIndex) -> ParseResult<A> {
    var (m,d): (Int,Set<String>) = (0,[])
    for p in ps {
      switch p.run(on,loc) {
      case let .Some(x,l): return .Some(x,l)
      case let .Failure(l,e,false,_):
        m = max(l,m)
        d.unionInPlace(e)
      case let f: return f
      }
    }
    return .Failure(m, d, false, loc)
  }
  public func or(p: ChoiceParser<A>) -> ChoiceParser<A> {
    return ChoiceParser(ps: self.ps + p.ps)
  }
  public func or(p: Parser<A>) -> ChoiceParser<A> {
    return ChoiceParser(ps: self.ps + [p])
  }
  public func or<P: ParserType where P.A == A>(p: P) -> ChoiceParser<A> {
    return ChoiceParser(ps: self.ps + [Parser(p.run)])
  }
}

extension Parser {
  public func or(p: Parser<A>) -> ChoiceParser<A> {
    return ChoiceParser(ps: [self, p])
  }
}

extension ParserType {
  public func or<P: ParserType where P.A == A>(p: P) -> ChoiceParser<A> {
    return ChoiceParser(ps: [Parser(self.run), Parser(p.run)])
  }
}

public func <*><P: ParserType, Q: ParserType, B where P.A == Q.A -> B>(lhs: P, rhs: Q) -> Parser<B> {
  return Parser { (on,loc) in
    switch lhs.run(on, loc) {
    case let .Some(f,i): return rhs.run(on,i).map(f)
    case let .Failure(l,e,c,i):
      return .Failure(l,e,c,i)
    }
  }
}

infix operator *> { precedence 120 associativity left }
infix operator <* { precedence 120 associativity left }

public func *><P: ParserType, Q: ParserType>(lhs: P, rhs: Q) -> Parser<Q.A> {
  return lhs.map { _ in { x in x } } <*> rhs
}

public func <*<P: ParserType, Q: ParserType>(lhs: P, rhs: Q) -> Parser<P.A> {
  return lhs.map { x in { _ in x } } <*> rhs
}