-
Notifications
You must be signed in to change notification settings - Fork 32
Expand file tree
/
Copy pathvalidator.lua
More file actions
394 lines (357 loc) · 11.3 KB
/
validator.lua
File metadata and controls
394 lines (357 loc) · 11.3 KB
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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
--[[
This module impements a validator for the AST
]]
local scope = require "lua-parser.scope"
local lineno = scope.lineno
local new_scope, end_scope = scope.new_scope, scope.end_scope
local new_function, end_function = scope.new_function, scope.end_function
local begin_loop, end_loop = scope.begin_loop, scope.end_loop
local insideloop = scope.insideloop
-- creates an error message for the input string
local function syntaxerror (errorinfo, pos, msg)
local l, c = lineno(errorinfo.subject, pos)
local error_msg = "%s:%d:%d: syntax error, %s"
return string.format(error_msg, errorinfo.filename, l, c, msg)
end
local function exist_label (env, scope, stm)
local l = stm[1]
for s=scope, 0, -1 do
if env[s]["label"][l] then return true end
end
return false
end
local function set_label (env, label, pos)
local scope = env.scope
local l = env[scope]["label"][label]
if not l then
env[scope]["label"][label] = { name = label, pos = pos }
return true
else
local msg = "label '%s' already defined at line %d"
local line = lineno(env.errorinfo.subject, l.pos)
msg = string.format(msg, label, line)
return nil, syntaxerror(env.errorinfo, pos, msg)
end
end
local function set_pending_goto (env, stm)
local scope = env.scope
table.insert(env[scope]["goto"], stm)
return true
end
local function verify_pending_gotos (env)
for s=env.maxscope, 0, -1 do
for k, v in ipairs(env[s]["goto"]) do
if not exist_label(env, s, v) then
local msg = "no visible label '%s' for <goto>"
msg = string.format(msg, v[1])
return nil, syntaxerror(env.errorinfo, v.pos, msg)
end
end
end
return true
end
local function set_vararg (env, is_vararg)
env["function"][env.fscope].is_vararg = is_vararg
end
local traverse_stm, traverse_exp, traverse_var
local traverse_block, traverse_explist, traverse_varlist, traverse_parlist
function traverse_parlist (env, parlist)
local len = #parlist
local is_vararg = false
if len > 0 and parlist[len].tag == "Dots" then
is_vararg = true
end
set_vararg(env, is_vararg)
return true
end
local function traverse_function (env, exp)
new_function(env)
new_scope(env)
local status, msg = traverse_parlist(env, exp[1])
if not status then return status, msg end
status, msg = traverse_block(env, exp[2])
if not status then return status, msg end
end_scope(env)
end_function(env)
return true
end
local function traverse_op (env, exp)
local status, msg = traverse_exp(env, exp[2])
if not status then return status, msg end
if exp[3] then
status, msg = traverse_exp(env, exp[3])
if not status then return status, msg end
end
return true
end
local function traverse_paren (env, exp)
local status, msg = traverse_exp(env, exp[1])
if not status then return status, msg end
return true
end
local function traverse_table (env, fieldlist)
for k, v in ipairs(fieldlist) do
local tag = v.tag
if tag == "Pair" then
local status, msg = traverse_exp(env, v[1])
if not status then return status, msg end
status, msg = traverse_exp(env, v[2])
if not status then return status, msg end
else
local status, msg = traverse_exp(env, v)
if not status then return status, msg end
end
end
return true
end
local function traverse_vararg (env, exp)
if not env["function"][env.fscope].is_vararg then
local msg = "cannot use '...' outside a vararg function"
return nil, syntaxerror(env.errorinfo, exp.pos, msg)
end
return true
end
local function traverse_call (env, call)
local status, msg = traverse_exp(env, call[1])
if not status then return status, msg end
for i=2, #call do
status, msg = traverse_exp(env, call[i])
if not status then return status, msg end
end
return true
end
local function traverse_invoke (env, invoke)
local status, msg = traverse_exp(env, invoke[1])
if not status then return status, msg end
for i=3, #invoke do
status, msg = traverse_exp(env, invoke[i])
if not status then return status, msg end
end
return true
end
local function traverse_assignment (env, stm)
local status, msg = traverse_varlist(env, stm[1])
if not status then return status, msg end
status, msg = traverse_explist(env, stm[2])
if not status then return status, msg end
return true
end
local function traverse_break (env, stm)
if not insideloop(env) then
local msg = "<break> not inside a loop"
return nil, syntaxerror(env.errorinfo, stm.pos, msg)
end
return true
end
local function traverse_forin (env, stm)
begin_loop(env)
new_scope(env)
local status, msg = traverse_explist(env, stm[2])
if not status then return status, msg end
status, msg = traverse_block(env, stm[3])
if not status then return status, msg end
end_scope(env)
end_loop(env)
return true
end
local function traverse_fornum (env, stm)
local status, msg
begin_loop(env)
new_scope(env)
status, msg = traverse_exp(env, stm[2])
if not status then return status, msg end
status, msg = traverse_exp(env, stm[3])
if not status then return status, msg end
if stm[5] then
status, msg = traverse_exp(env, stm[4])
if not status then return status, msg end
status, msg = traverse_block(env, stm[5])
if not status then return status, msg end
else
status, msg = traverse_block(env, stm[4])
if not status then return status, msg end
end
end_scope(env)
end_loop(env)
return true
end
local function traverse_goto (env, stm)
local status, msg = set_pending_goto(env, stm)
if not status then return status, msg end
return true
end
local function traverse_if (env, stm)
local len = #stm
if len % 2 == 0 then
for i=1, len, 2 do
local status, msg = traverse_exp(env, stm[i])
if not status then return status, msg end
status, msg = traverse_block(env, stm[i+1])
if not status then return status, msg end
end
else
for i=1, len-1, 2 do
local status, msg = traverse_exp(env, stm[i])
if not status then return status, msg end
status, msg = traverse_block(env, stm[i+1])
if not status then return status, msg end
end
local status, msg = traverse_block(env, stm[len])
if not status then return status, msg end
end
return true
end
local function traverse_label (env, stm)
local status, msg = set_label(env, stm[1], stm.pos)
if not status then return status, msg end
return true
end
local function traverse_let (env, stm)
local status, msg = traverse_explist(env, stm[2])
if not status then return status, msg end
return true
end
local function traverse_letrec (env, stm)
local status, msg = traverse_exp(env, stm[2][1])
if not status then return status, msg end
return true
end
local function traverse_repeat (env, stm)
begin_loop(env)
local status, msg = traverse_block(env, stm[1])
if not status then return status, msg end
status, msg = traverse_exp(env, stm[2])
if not status then return status, msg end
end_loop(env)
return true
end
local function traverse_return (env, stm)
local status, msg = traverse_explist(env, stm)
if not status then return status, msg end
return true
end
local function traverse_while (env, stm)
begin_loop(env)
local status, msg = traverse_exp(env, stm[1])
if not status then return status, msg end
status, msg = traverse_block(env, stm[2])
if not status then return status, msg end
end_loop(env)
return true
end
function traverse_var (env, var)
local tag = var.tag
if tag == "Id" then -- `Id{ <string> }
return true
elseif tag == "Index" then -- `Index{ expr expr }
local status, msg = traverse_exp(env, var[1])
if not status then return status, msg end
status, msg = traverse_exp(env, var[2])
if not status then return status, msg end
return true
else
error("expecting a variable, but got a " .. tag)
end
end
function traverse_varlist (env, varlist)
for k, v in ipairs(varlist) do
local status, msg = traverse_var(env, v)
if not status then return status, msg end
end
return true
end
function traverse_exp (env, exp)
local tag = exp.tag
if tag == "Nil" or
tag == "Boolean" or -- `Boolean{ <boolean> }
tag == "Number" or -- `Number{ <number> }
tag == "String" then -- `String{ <string> }
return true
elseif tag == "Dots" then
return traverse_vararg(env, exp)
elseif tag == "Function" then -- `Function{ { `Id{ <string> }* `Dots? } block }
return traverse_function(env, exp)
elseif tag == "Table" then -- `Table{ ( `Pair{ expr expr } | expr )* }
return traverse_table(env, exp)
elseif tag == "Op" then -- `Op{ opid expr expr? }
return traverse_op(env, exp)
elseif tag == "Paren" then -- `Paren{ expr }
return traverse_paren(env, exp)
elseif tag == "Call" then -- `Call{ expr expr* }
return traverse_call(env, exp)
elseif tag == "Invoke" then -- `Invoke{ expr `String{ <string> } expr* }
return traverse_invoke(env, exp)
elseif tag == "Id" or -- `Id{ <string> }
tag == "Index" then -- `Index{ expr expr }
return traverse_var(env, exp)
else
error("expecting an expression, but got a " .. tag)
end
end
function traverse_explist (env, explist)
for k, v in ipairs(explist) do
local status, msg = traverse_exp(env, v)
if not status then return status, msg end
end
return true
end
function traverse_stm (env, stm)
local tag = stm.tag
if tag == "Do" then -- `Do{ stat* }
return traverse_block(env, stm)
elseif tag == "Set" then -- `Set{ {lhs+} {expr+} }
return traverse_assignment(env, stm)
elseif tag == "While" then -- `While{ expr block }
return traverse_while(env, stm)
elseif tag == "Repeat" then -- `Repeat{ block expr }
return traverse_repeat(env, stm)
elseif tag == "If" then -- `If{ (expr block)+ block? }
return traverse_if(env, stm)
elseif tag == "Fornum" then -- `Fornum{ ident expr expr expr? block }
return traverse_fornum(env, stm)
elseif tag == "Forin" then -- `Forin{ {ident+} {expr+} block }
return traverse_forin(env, stm)
elseif tag == "Local" then -- `Local{ {ident+} {expr+}? }
return traverse_let(env, stm)
elseif tag == "Localrec" then -- `Localrec{ ident expr }
return traverse_letrec(env, stm)
elseif tag == "Goto" then -- `Goto{ <string> }
return traverse_goto(env, stm)
elseif tag == "Label" then -- `Label{ <string> }
return traverse_label(env, stm)
elseif tag == "Return" then -- `Return{ <expr>* }
return traverse_return(env, stm)
elseif tag == "Break" then
return traverse_break(env, stm)
elseif tag == "Call" then -- `Call{ expr expr* }
return traverse_call(env, stm)
elseif tag == "Invoke" then -- `Invoke{ expr `String{ <string> } expr* }
return traverse_invoke(env, stm)
else
error("expecting a statement, but got a " .. tag)
end
end
function traverse_block (env, block)
local l = {}
new_scope(env)
for k, v in ipairs(block) do
local status, msg = traverse_stm(env, v)
if not status then return status, msg end
end
end_scope(env)
return true
end
local function traverse (ast, errorinfo)
assert(type(ast) == "table")
assert(type(errorinfo) == "table")
local env = { errorinfo = errorinfo, ["function"] = {} }
new_function(env)
set_vararg(env, true)
local status, msg = traverse_block(env, ast)
if not status then return status, msg end
end_function(env)
status, msg = verify_pending_gotos(env)
if not status then return status, msg end
return ast
end
return { validate = traverse, syntaxerror = syntaxerror }