parser_combinator.swift

//: [Previous](@previous)

import Foundation
import UIKit
import XCPlayground

enum ParseError: Swift.Error {
    case notSatisfy
}

struct Source {
    enum Error: Swift.Error {
        case empty
    }
    
    private let input: String
    fileprivate var caret: Int = 0
    
    init(input: String) {
        self.input = input
    }
    
    private func peek() -> Character? {
        guard let i = input.characters.index(
            input.characters.startIndex,
            offsetBy: caret,
            limitedBy: input.characters.endIndex), i != input.characters.endIndex else {
                return nil
        }
        return input.characters[i]
    }
    
    mutating func next() throws ->  Character {
        guard let ch = peek() else { throw Error.empty }
        defer {
            caret += 1
        }
        return ch
    }
    
    mutating func transaction<T>(_ block: (inout Source) throws -> T) rethrows -> T {
        let current = self
        do {
            return try block(&self)
        } catch {
            self = current
            throw error
        }
    }
}

typealias Parser = (inout Source) throws -> String

typealias Checker = (Character) -> Bool

func satisfy(_ f: @escaping Checker) -> Parser {
    return { s in
        try s.transaction { ss in
            let char = try ss.next()
            if f(char) {
                return String(char)
            }
            throw ParseError.notSatisfy
        }
    }
}

func tryp(_ p: @escaping Parser) -> Parser {
    return { s in
        let bak = s
        do {
            return try p(&s)
        } catch {
            s = bak
            throw error
        }
    }
}

let isDigit: Checker = { (Character("0")...Character("9")).contains($0) }
let isUpper: Checker = { (Character("A")...Character("Z")).contains($0) }
let isLower: Checker = { (Character("a")...Character("z")).contains($0) }
let isAlpha: Checker = { isUpper($0) || isLower($0) }
let isAlphaNum: Checker = { isAlpha($0) || isDigit($0) }
let isLetter: Checker = { isAlpha($0) || $0 == "_" }


//
let any = satisfy { _ in true }
let digit = satisfy(isDigit)
let upper = satisfy(isUpper)
let lower = satisfy(isLower)
let alpha = satisfy(isAlpha)
let alphaNum = satisfy(isAlphaNum)
let letter = satisfy(isLetter)
let char = { (ch: Character) in satisfy { $0 == ch } }


func + (lhs: @escaping Parser, rhs: @escaping Parser) -> Parser {
    return { (s: inout Source) throws -> String in
        try s.transaction { ss in
            (try lhs(&ss)) + (try rhs(&ss))
        }
    }
}


func * (lhs: Int, rhs: @escaping Parser) -> Parser {
    return { s in
        try s.transaction { ss in
            let str = try (0..<lhs).map { _ in try rhs(&ss) }.joined()
            return str
        }
    }
}

func || (lhs: @escaping Parser, rhs: @escaping Parser) -> Parser {
    return { s in
        do {
            return try s.transaction { ss in
                try lhs(&ss)
            }
        } catch {
            return try rhs(&s)
        }
    }
}

// combinator
func many(_ parser: @escaping Parser) -> Parser {
    return { s in
        try s.transaction { ss in
            var result: [String] = []
            do {
                while true {
                    result.append(try parser(&s))
                }
            } catch Source.Error.empty {
            } catch ParseError.notSatisfy {
            } catch { throw error }
            return result.joined()
        }
    }
}
let string: (String) throws -> Parser = { str in
    let chars = str.characters
    guard let first = chars.first else { throw Source.Error.empty }
    return chars.dropFirst()
        .map { char($0) }
        .reduce(char(first), +)
}

let test1 = digit + upper + upper
let test2 = any + 2 * char("A") + char("B")

// main

do {
    var source = Source(input: "abc123")
    let s1a = try many(alpha)(&source)
    let s1b = try many(digit)(&source)
} catch {
    print(error)
}

do {
    var source = Source(input: "abcde9")
    let s2a = try many(alpha)(&source)
    let s2b = try many(digit)(&source)
} catch {
    print(error)
}


do {
    let test5 = letter || digit
    var s1 = Source(input: "a")
    var s2 = Source(input: "1")
    var s3 = Source(input: "!")
    let ret1 = try test5(&s1)
    let ret2 = try test5(&s2)
    let ret3 = try test5(&s3)
} catch {
    print(error)
}



do {
    let test6 = many(letter || digit)
    var s1 = Source(input: "abc123")
    var s2 = Source(input: "123abc")
    var s3 = Source(input: "___!_ddd")
    let ret1 = try test6(&s1)
    let ret2 = try test6(&s2)
    let ret3 = try test6(&s3)
} catch {
    print(error)
}

do {
    let (a, b, c) = (char("a"), char("b"), char("c"))
    let test7 = a + b || c + b
    var s1 = Source(input: "ab")
    var s2 = Source(input: "cb")
    var s3 = Source(input: "acb")
    let ret1 = try test7(&s1)
    let ret2 = try test7(&s2)
    let ret3 = try test7(&s3)
} catch {
    print(error)
}


do {
    let (a, b, c) = (char("a"), char("b"), char("c"))
    let test7 = a + b || a + c
    var s1 = Source(input: "ab")
    var s2 = Source(input: "ac")
    let ret1 = try test7(&s1)
    let ret2 = try test7(&s2)
} catch {
    print(error)
}