/
Parser.swift
224 lines (183 loc) · 7.32 KB
/
Parser.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
public func until(_ tags: [String]) -> ((TokenParser, Token) -> Bool) {
return { parser, token in
if let name = token.components.first {
for tag in tags {
if name == tag {
return true
}
}
}
return false
}
}
/// A class for parsing an array of tokens and converts them into a collection of Node's
public class TokenParser {
public typealias TagParser = (TokenParser, Token) throws -> NodeType
fileprivate var tokens: [Token]
fileprivate let environment: Environment
public init(tokens: [Token], environment: Environment) {
self.tokens = tokens
self.environment = environment
}
/// Parse the given tokens into nodes
public func parse() throws -> [NodeType] {
return try parse(nil)
}
public func parse(_ parse_until:((_ parser:TokenParser, _ token:Token) -> (Bool))?) throws -> [NodeType] {
var nodes = [NodeType]()
while tokens.count > 0 {
let token = nextToken()!
switch token.kind {
case .text:
nodes.append(TextNode(text: token.contents))
case .variable:
try nodes.append(VariableNode.parse(self, token: token))
case .block:
if let parse_until = parse_until , parse_until(self, token) {
prependToken(token)
return nodes
}
if let tag = token.components.first {
do {
let parser = try environment.findTag(name: tag)
let node = try parser(self, token)
nodes.append(node)
} catch {
throw error.withToken(token)
}
}
case .comment:
continue
}
}
return nodes
}
public func nextToken() -> Token? {
if tokens.count > 0 {
return tokens.remove(at: 0)
}
return nil
}
public func prependToken(_ token:Token) {
tokens.insert(token, at: 0)
}
/// Create filter expression from a string contained in provided token
public func compileFilter(_ filterToken: String, containedIn token: Token) throws -> Resolvable {
return try environment.compileFilter(filterToken, containedIn: token)
}
/// Create boolean expression from components contained in provided token
public func compileExpression(components: [String], token: Token) throws -> Expression {
return try environment.compileExpression(components: components, containedIn: token)
}
/// Create resolvable (i.e. range variable or filter expression) from a string contained in provided token
public func compileResolvable(_ token: String, containedIn containingToken: Token) throws -> Resolvable {
return try environment.compileResolvable(token, containedIn: containingToken)
}
}
extension Environment {
func findTag(name: String) throws -> Extension.TagParser {
for ext in extensions {
if let filter = ext.tags[name] {
return filter
}
}
throw TemplateSyntaxError("Unknown template tag '\(name)'")
}
func findFilter(_ name: String) throws -> FilterType {
for ext in extensions {
if let filter = ext.filters[name] {
return filter
}
}
let suggestedFilters = self.suggestedFilters(for: name)
if suggestedFilters.isEmpty {
throw TemplateSyntaxError("Unknown filter '\(name)'.")
} else {
throw TemplateSyntaxError("""
Unknown filter '\(name)'. \
Found similar filters: \(suggestedFilters.map({ "'\($0)'" }).joined(separator: ", ")).
""")
}
}
private func suggestedFilters(for name: String) -> [String] {
let allFilters = extensions.flatMap({ $0.filters.keys })
let filtersWithDistance = allFilters
.map({ (filterName: $0, distance: $0.levenshteinDistance(name)) })
// do not suggest filters which names are shorter than the distance
.filter({ $0.filterName.count > $0.distance })
guard let minDistance = filtersWithDistance.min(by: { $0.distance < $1.distance })?.distance else {
return []
}
// suggest all filters with the same distance
return filtersWithDistance.filter({ $0.distance == minDistance }).map({ $0.filterName })
}
/// Create filter expression from a string
public func compileFilter(_ token: String) throws -> Resolvable {
return try FilterExpression(token: token, environment: self)
}
/// Create filter expression from a string contained in provided token
public func compileFilter(_ filterToken: String, containedIn containingToken: Token) throws -> Resolvable {
do {
return try FilterExpression(token: filterToken, environment: self)
} catch {
guard var syntaxError = error as? TemplateSyntaxError, syntaxError.token == nil else {
throw error
}
// find offset of filter in the containing token so that only filter is highligted, not the whole token
if let filterTokenRange = containingToken.contents.range(of: filterToken) {
var location = containingToken.sourceMap.location
location.lineOffset += containingToken.contents.distance(from: containingToken.contents.startIndex, to: filterTokenRange.lowerBound)
syntaxError.token = .variable(value: filterToken, at: SourceMap(filename: containingToken.sourceMap.filename, location: location))
} else {
syntaxError.token = containingToken
}
throw syntaxError
}
}
/// Create resolvable (i.e. range variable or filter expression) from a string
public func compileResolvable(_ token: String) throws -> Resolvable {
return try RangeVariable(token, environment: self)
?? compileFilter(token)
}
/// Create resolvable (i.e. range variable or filter expression) from a string contained in provided token
public func compileResolvable(_ token: String, containedIn containingToken: Token) throws -> Resolvable {
return try RangeVariable(token, environment: self, containedIn: containingToken)
?? compileFilter(token, containedIn: containingToken)
}
/// Create boolean expression from components contained in provided token
public func compileExpression(components: [String], containedIn token: Token) throws -> Expression {
return try IfExpressionParser.parser(components: components, environment: self, token: token).parse()
}
}
// https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows
extension String {
subscript(_ i: Int) -> Character {
return self[self.index(self.startIndex, offsetBy: i)]
}
func levenshteinDistance(_ target: String) -> Int {
// create two work vectors of integer distances
var last, current: [Int]
// initialize v0 (the previous row of distances)
// this row is A[0][i]: edit distance for an empty s
// the distance is just the number of characters to delete from t
last = [Int](0...target.count)
current = [Int](repeating: 0, count: target.count + 1)
for i in 0..<self.count {
// calculate v1 (current row distances) from the previous row v0
// first element of v1 is A[i+1][0]
// edit distance is delete (i+1) chars from s to match empty t
current[0] = i + 1
// use formula to fill in the rest of the row
for j in 0..<target.count {
current[j+1] = Swift.min(
last[j+1] + 1,
current[j] + 1,
last[j] + (self[i] == target[j] ? 0 : 1)
)
}
// copy v1 (current row) to v0 (previous row) for next iteration
last = current
}
return current[target.count]
}
}