formula.swift

//
//  main.swift
//  Formula
//
//  Created by 林達也 on 2016/03/20.
//  Copyright © 2016年 jp.sora0077. All rights reserved.
//

//: Playground - noun: a place where people can play

import Cocoa


protocol Acceptable {}
extension String: Acceptable {}
extension Symbol: Acceptable {}
extension Parser: Acceptable {}
extension Array: Acceptable {}

struct Numeric: Acceptable {}

struct Group: Acceptable {
    
    let values: [Acceptable]
    
    init(_ values: Acceptable...) {
        self.values = values
    }
}



enum Either<L: CustomStringConvertible, R: CustomStringConvertible>: CustomStringConvertible {
    case left(L)
    case right(R)
    
    var forceLeft: L {
        switch self {
        case .left(let val):
            return val
        default:
            print(self)
            fatalError()
        }
    }
    
    var forceRight: R {
        switch self {
        case .right(let val):
            return val
        default:
            fatalError()
        }
    }
    
    var description: String {
        switch self {
        case .left(let val):
            return val.description
        case .right(let val):
            return val.description
        }
    }
}


protocol SignOrPattern: CustomStringConvertible {
    
    var rawValue: String { get }
}



final class Tokens {
    
    
    enum Pattern: String, SignOrPattern {
        case Numeric = "^[+-]?([1-9][0-9]*|0)(\\.[0-9]+)?"
        
        static let all: [Pattern] = [
            .Numeric
        ]
        
        var description: String {
            return "Numric"
        }
    }
    
    enum Sign: String, SignOrPattern {
        case LParen = "("
        case RParen = ")"
        case Plus = "+"
        case Minus = "-"
        case Multiply = "*"
        case Divide = "/"
        
        static let all: [Sign] = [
            .LParen,
            .RParen,
            .Plus,
            .Minus,
            .Multiply,
            .Divide
        ]
        
        var description: String {
            return "Symbol"
        }
    }
    
    struct Token: CustomStringConvertible {
        let type: SignOrPattern
        let label: String
        
        var description: String {
            return "(type: \(type), label: \"\(label)\")"
        }
    }
    
    private var pointer: Int = 0
    private var pointerStack: [Int] = []
    private var tokens: [Token] = []
    
    var token: Token? {
        
        if tokens.count <= pointer {
            return nil
        }
        return tokens[pointer]
    }
    
    init(source: String) {
        
        
        var unread = source
        while !unread.isEmpty {
            
            unread = unread.stringByTrimmingCharactersInSet(NSCharacterSet.whitespaceCharacterSet())
            
            var tokenFound = false
            for pattern in Pattern.all {
                let regex = try! NSRegularExpression(pattern: pattern.rawValue, options: [])
                let results = regex.matchesInString(unread, options: [], range: NSMakeRange(0, unread.utf16.count))
                if results.isEmpty { continue }
                
                tokenFound = true
                
                tokens.append(Token(type: pattern, label: {
                    let range = results[0].rangeAtIndex(0)
                    let start = unread.utf16.startIndex.advancedBy(range.location)
                    let end = start.advancedBy(range.length)
                    return String(unread.utf16[start..<end])
                }()))
                
                let range = results[0].rangeAtIndex(0)
                let start = unread.utf16.startIndex.advancedBy(range.length)
                unread = String(unread.utf16[start..<unread.utf16.endIndex])
            }
            
            if !tokenFound {
                for symbol in Sign.all {
                    let endIndex = unread.startIndex.advancedBy(symbol.rawValue.characters.count)
                    if unread[unread.startIndex..<endIndex] == symbol.rawValue {
                        unread = unread.substringFromIndex(endIndex)
                        tokens.append(Token(type: symbol, label: symbol.rawValue))
                        
                        tokenFound = true
                    }
                }
            }
            
            if !tokenFound {
                print("Error")
            }
        }
        
    }
    
    
    var exhausted: Bool {
        return pointer >= tokens.count
    }
    
    
    func check() -> Self {
        pointerStack.append(pointer)
        return self
    }
    
    func uncheck() -> Self {
        pointerStack.removeLast()
        return self
    }
    
    func next() -> Token? {
        
        if pointer < tokens.count {
            pointer += 1
        }
        return token
    }
    
    func rewind() -> Self {
        
        pointer = pointerStack.count > 0 ? pointerStack.removeLast() : 0
        return self
    }
}


final class Parser {
    
    typealias Parsed = Either<Double, Tokens.Token>
    typealias Rule = (patterns: [Acceptable], handler: (inout [Parsed]) -> Double)
    private var rules: [Rule] = []
    
    private let name: String
    
    init(_ name: String) {
        self.name = name
    }
    
    
    func accept(pattern: Acceptable, _ patterns: [Acceptable], _ handler: (inout [Parsed]) -> Double) -> Self {
        
        rules.append((patterns: [pattern, patterns], handler: handler))
        return self
    }
    
    func accept(patterns: Acceptable..., _ handler: (inout [Parsed]) -> Double) -> Self {
        
        rules.append((patterns: patterns, handler: handler))
        return self
    }
    
    func parse(tokens: Tokens) -> Double? {
        
        func patternMatch(patterns: [Acceptable], inout parsed: [Parsed]) -> Bool {
            
            var matched: [Parsed] = []
            func traverse() -> Bool {
                
                for (idx, pattern) in patterns.enumerate() {
                    
                    var pattern = pattern
                    if let str = pattern as? String {
                        pattern = Symbol(str)
                    }
                    
                    print(self, tokens.token, idx, pattern, matched)
                    
                    if let parser = pattern as? Parser {
                        if let node = parser.parse(tokens) {
                            matched.append(.left(node))
                        } else {
                            return false
                        }
                    } else if let symbol = pattern as? Symbol {
                        switch symbol {
                        case .terminator(let val):
                            if let token = tokens.token where token.label == val {
                                matched.append(.right(token))
                                tokens.next()
                                print("matched next: ", tokens.token)
                            } else {
                                return false
                            }
                        case .or(let lhs, let rhs):
                            func subpatternMatch() -> Bool {
                                for subpattern in [lhs, rhs] {
                                    if patternMatch([subpattern], parsed: &matched) {
                                        print("subpattern matched")
                                        return true
                                    }
                                }
                                return false
                            }
                            if !subpatternMatch() {
                                return false
                            }
                        }
                    } else if let patterns = pattern as? [Acceptable] {
                        while patternMatch(patterns, parsed: &matched) {}
                    } else if let group = pattern as? Group {
                        while patternMatch(group.values, parsed: &matched) {}
                    } else if tokens.exhausted {
                        return false
                    } else if let token = tokens.token
                        where pattern is Numeric && token.type.rawValue == Tokens.Pattern.Numeric.rawValue
                    {
                        matched.append(.right(token))
                        tokens.next()
                    } else {
                        return false
                    }
                }
                
                return true
            }
            
            tokens.check()
            
            if !traverse() {
                tokens.rewind()
                return false
            }
            
            parsed.appendContentsOf(matched)
            tokens.uncheck()
            return true
        }
        
        for rule in rules {
            var parsed: [Parsed] = []
            if patternMatch(rule.patterns, parsed: &parsed) {
                let val = rule.handler(&parsed)
                print("result: ", parsed, val)
                return val
            }
        }
        print("return: nil", self, tokens.token)
        return nil
    }
}

extension Parser: CustomStringConvertible {
    
    var description: String {
        return "Parser(\(name))"
    }
    
    func justify() -> Self {
        return self
    }
}

enum Symbol: StringLiteralConvertible {
    case terminator(String)
    case or(Acceptable, Acceptable)
    
    init(_ value: String) {
        self = .terminator(value)
    }
    
    init(stringLiteral value: String) {
        self.init(value)
    }
    
    init(unicodeScalarLiteral value: String) {
        self.init(value)
    }
    
    init(extendedGraphemeClusterLiteral value: String) {
        self.init(value)
    }
}

func ||(lhs: Acceptable, rhs: Acceptable) -> Symbol {
    return .or(lhs, rhs)
}


let E = Parser("E")
let F = Parser("F")
let N = Parser("N")


E   .accept(F, ["+" || "-", F]) { parsed in
        var result = parsed.removeFirst().forceLeft
        while !parsed.isEmpty {
            let label = parsed.removeFirst().forceRight.label
            let val = parsed.removeFirst().forceLeft
            result = label == "+" ? result + val : result - val
        }
        return result
    }

F   .accept(N, ["*" || "/", N]) { parsed in
        var result = parsed.removeFirst().forceLeft
        while !parsed.isEmpty {
            let label = parsed.removeFirst().forceRight.label
            let val = parsed.removeFirst().forceLeft
            result = label == "*" ? result * val : result / val
        }
        return result
    }

N   .accept("(", E, ")") { parsed in
        let val = parsed[1].forceLeft
        return val
    }
    .accept("+" || "-", N) { parsed in
        let num = parsed[1].forceLeft
        return parsed[0].forceRight.label == "+" ? num : -num
    }
    .accept(Numeric()) { parsed in
        let val = Double(parsed[0].forceRight.label)
        return val!
    }

print(E.parse(Tokens(source: "1 + 2 * 3 - (4 + 5) / 3")))