this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
3/*
4 * Main authors:
5 * Jip J. Dekker <jip.dekker@monash.edu>
6 */
7
8/* This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
11
12%define api.pure
13%define api.header.include {<minizinc/support/mza_parser.tab.hh>}
14
15%{
16#include <cstdio>
17#include <list>
18
19#include <minizinc/interpreter.hh>
20
21//Anonymous struct for when yyparse is exported
22typedef struct MZAContext MZAContext;
23#include <minizinc/support/mza_parser.tab.hh>
24
25using namespace MiniZinc;
26
27typedef struct yy_buffer_state *YY_BUFFER_STATE;
28YY_BUFFER_STATE mza_yy_scan_string ( const char* yy_str );
29
30extern int yylex(YYSTYPE*, YYLTYPE*);
31extern FILE* yyin;
32
33struct ProcPatch {
34 int code;
35 BytecodeProc::Mode mode;
36 std::vector<std::pair<int, std::pair<std::string, int>>> patch;
37 ProcPatch(int code0, BytecodeProc::Mode mode0, std::vector<std::pair<int, std::pair<std::string, int>>> patch0)
38 : code(code0), mode(mode0), patch(std::move(patch0)) {}
39};
40
41typedef struct MZAContext {
42 std::vector<BytecodeProc>& procs;
43 std::unordered_map<std::string, int>& proc_map;
44 int& max_glob;
45 std::vector<ProcPatch> to_patch;
46 BytecodeStream proc_body;
47 std::unordered_map<std::string, int> labels;
48 std::vector<std::pair<int, std::string>> patch_labels;
49 std::vector<std::pair<int, std::pair<std::string, int>>> patch_procs;
50} MZAContext;
51
52void yyerror(YYLTYPE* location, MZAContext& ctx, const char* s);
53%}
54
55%union {
56 int iValue;
57 char* sValue;
58 MiniZinc::BytecodeStream::Instr bValue;
59 std::list<int>* liValue;
60 std::list<std::string>* sliValue;
61}
62%parse-param {MZAContext& ctx}
63%locations
64%define parse.error verbose
65
66%token<iValue> MZA_INT
67%token<iValue> MZA_REG
68%token<iValue> MZA_MODE
69%token<iValue> MZA_CTX
70%token<sValue> MZA_ID
71
72%token MZA_COLON ":"
73%token MZA_DELAY "D"
74
75%token MZA_GLOBAL "GLOBAL"
76
77%token<bValue> MZA_ADDI
78%token<bValue> MZA_SUBI
79%token<bValue> MZA_MULI
80%token<bValue> MZA_DIVI
81%token<bValue> MZA_MODI
82%token<bValue> MZA_INCI
83%token<bValue> MZA_DECI
84
85%token<bValue> MZA_IMMI
86%token<bValue> MZA_CLEAR
87%token<bValue> MZA_LOAD_GLOBAL
88%token<bValue> MZA_STORE_GLOBAL
89%token<bValue> MZA_MOV
90
91%token<bValue> MZA_JMP
92%token<bValue> MZA_JMPIF
93%token<bValue> MZA_JMPIFNOT
94
95%token<bValue> MZA_EQI
96%token<bValue> MZA_LTI
97%token<bValue> MZA_LEI
98
99%token<bValue> MZA_AND
100%token<bValue> MZA_OR
101%token<bValue> MZA_NOT
102%token<bValue> MZA_XOR
103
104%token<bValue> MZA_ISPAR
105%token<bValue> MZA_ISEMPTY
106%token<bValue> MZA_LENGTH
107%token<bValue> MZA_GET_VEC
108%token<bValue> MZA_GET_ARRAY
109
110%token<bValue> MZA_LB
111%token<bValue> MZA_UB
112%token<bValue> MZA_DOM
113
114%token<bValue> MZA_MAKE_SET
115%token<bValue> MZA_DIFF
116%token<bValue> MZA_INTERSECTION
117%token<bValue> MZA_UNION
118
119%token<bValue> MZA_INTERSECT_DOMAIN
120
121%token<bValue> MZA_OPEN_AGGREGATION
122%token<bValue> MZA_CLOSE_AGGREGATION
123%token<bValue> MZA_SIMPLIFY_LIN
124
125%token<bValue> MZA_PUSH
126%token<bValue> MZA_POP
127%token<bValue> MZA_POST
128
129%token<bValue> MZA_RET
130%token<bValue> MZA_CALL
131%token<bValue> MZA_BUILTIN
132%token<bValue> MZA_TCALL
133
134%token<bValue> MZA_ITER_ARRAY
135%token<bValue> MZA_ITER_VEC
136%token<bValue> MZA_ITER_RANGE
137%token<bValue> MZA_ITER_NEXT
138%token<bValue> MZA_ITER_BREAK
139
140%token<bValue> MZA_TRACE
141%token<bValue> MZA_ABORT
142
143
144%type<iValue> delay instruction mode
145%type<bValue> instr instrI instrIR instrR instrRR instrRS instrRRR instrRRS instrRRIRRR instrS
146%type<sValue> label
147%type<liValue> registers
148%type<sliValue> labels
149
150%start procedures
151
152%%
153
154procedures:
155 /* empty */
156 | procedures procedure
157
158procedure:
159 ":" MZA_ID ":" mode MZA_INT delay instructions
160 {
161 // Patch jumps with recorded labels
162 for (auto& cl : ctx.patch_labels) {
163 if (ctx.labels.find(cl.second) == ctx.labels.end()) {
164 throw Error("Error: label " + cl.second + " not found\n");
165 }
166 ctx.proc_body.patchAddress(cl.first, ctx.labels[cl.second]);
167 }
168 ctx.labels.clear();
169 ctx.patch_labels.clear();
170
171 ctx.proc_body.setNArgs($5);
172
173 // Add ABORT instruction for error management
174 if (ctx.proc_body.size() > 0) {
175 ctx.proc_body.addInstr(BytecodeStream::ABORT);
176 }
177 // Store procedure in the correct place
178 auto mode = static_cast<BytecodeProc::Mode>($4);
179 auto it = ctx.proc_map.find($2);
180 if (it != ctx.proc_map.end()) {
181 BytecodeProc& bcp = ctx.procs[it->second];
182 if (bcp.mode[mode].size() > 0) {
183 throw Error("Error: procedure " + std::string($2) + " already defined before with the same mode\n");
184 }
185 if (bcp.nargs != $5 ) {
186 throw Error("Error: procedure " + std::string($2) + " already defined before with different number of arguments\n");
187 }
188 bcp.mode[$4] = ctx.proc_body;
189 ctx.to_patch.emplace_back(it->second, mode, ctx.patch_procs);
190 } else {
191 BytecodeProc bcp;
192 bcp.name = $2;
193 bcp.mode[mode] = ctx.proc_body;
194 bcp.nargs = $5;
195 bcp.delay = $6;
196 ctx.proc_map.emplace($2, ctx.procs.size());
197 ctx.to_patch.emplace_back(ctx.procs.size(), mode, ctx.patch_procs);
198 ctx.procs.push_back(bcp);
199 }
200 ctx.proc_body = BytecodeStream();
201 ctx.patch_procs.clear();
202 }
203
204mode:
205 /* empty */ { $$ = BytecodeProc::FUN; }
206 | MZA_MODE
207
208delay:
209 /* empty */ { $$ = 0; }
210 | MZA_DELAY { $$ = 1; }
211
212instructions:
213 /* empty */
214 | instructions labeled_instr
215
216labeled_instr:
217 labels instruction
218 {
219 for (auto l : *$1) {
220 ctx.labels.emplace(l, $2);
221 }
222 delete $1;
223 }
224
225labels:
226 /* empty */ { $$ = new std::list<std::string>(); }
227 | labels label { $1->push_back($2); $$ = $1; }
228
229label:
230 MZA_ID ":"
231
232instruction:
233 instr
234 {
235 $$ = ctx.proc_body.size();
236 ctx.proc_body.addInstr($1);
237 }
238 | instrI MZA_INT
239 {
240 $$ = ctx.proc_body.size();
241 ctx.proc_body.addInstr($1);
242 ctx.proc_body.addIntVal($2);
243 }
244 | instrIR MZA_INT MZA_REG
245 {
246 $$ = ctx.proc_body.size();
247 ctx.proc_body.addInstr($1);
248 ctx.proc_body.addIntVal($2);
249 ctx.proc_body.addReg($3);
250 }
251 | instrR MZA_REG
252 {
253 $$ = ctx.proc_body.size();
254 ctx.proc_body.addInstr($1);
255 ctx.proc_body.addReg($2);
256 }
257 | instrRR MZA_REG MZA_REG
258 {
259 $$ = ctx.proc_body.size();
260 ctx.proc_body.addInstr($1);
261 ctx.proc_body.addReg($2);
262 ctx.proc_body.addReg($3);
263 }
264 | instrRS MZA_REG MZA_ID
265 {
266 $$ = ctx.proc_body.size();
267 ctx.proc_body.addInstr($1);
268 ctx.proc_body.addReg($2);
269 ctx.patch_labels.emplace_back(ctx.proc_body.size(), $3);
270 ctx.proc_body.addSmallInt(0);
271 }
272 | instrRRS MZA_REG MZA_REG MZA_ID
273 {
274 $$ = ctx.proc_body.size();
275 ctx.proc_body.addInstr($1);
276 ctx.proc_body.addReg($2);
277 ctx.proc_body.addReg($3);
278 ctx.patch_labels.emplace_back(ctx.proc_body.size(), $4);
279 ctx.proc_body.addSmallInt(0);
280 }
281 | instrRRR MZA_REG MZA_REG MZA_REG
282 {
283 $$ = ctx.proc_body.size();
284 ctx.proc_body.addInstr($1);
285 ctx.proc_body.addReg($2);
286 ctx.proc_body.addReg($3);
287 ctx.proc_body.addReg($4);
288 }
289 | instrRRIRRR MZA_REG MZA_REG MZA_INT MZA_REG MZA_REG MZA_REG
290 {
291 $$ = ctx.proc_body.size();
292 ctx.proc_body.addInstr($1);
293 ctx.proc_body.addReg($2);
294 ctx.proc_body.addReg($3);
295 ctx.proc_body.addIntVal($4);
296 ctx.proc_body.addReg($5);
297 ctx.proc_body.addReg($6);
298 ctx.proc_body.addReg($7);
299 }
300 | instrS MZA_ID
301 {
302 $$ = ctx.proc_body.size();
303 ctx.proc_body.addInstr($1);
304 ctx.patch_labels.emplace_back(ctx.proc_body.size(), $2);
305 ctx.proc_body.addSmallInt(0);
306 }
307 | MZA_CALL MZA_MODE MZA_ID MZA_INT registers
308 {
309 $$ = ctx.proc_body.size();
310 ctx.proc_body.addInstr($1);
311 ctx.proc_body.addCharVal($2);
312 ctx.patch_procs.emplace_back(ctx.proc_body.size(), std::make_pair($3, $5->size()));
313 ctx.proc_body.addSmallInt(0);
314 ctx.proc_body.addCharVal($4);
315 for (auto arg : *$5) {
316 ctx.proc_body.addReg(arg);
317 }
318 delete $5;
319 }
320 | MZA_BUILTIN MZA_ID registers
321 {
322 $$ = ctx.proc_body.size();
323 ctx.proc_body.addInstr($1);
324 ctx.patch_procs.emplace_back(ctx.proc_body.size(), std::make_pair($2, $3->size()));
325 ctx.proc_body.addSmallInt(0);
326 for (auto arg : *$3) {
327 ctx.proc_body.addReg(arg);
328 }
329 delete $3;
330 }
331 | MZA_TCALL MZA_MODE MZA_ID MZA_INT
332 {
333 $$ = ctx.proc_body.size();
334 ctx.proc_body.addInstr($1);
335 ctx.proc_body.addCharVal($2);
336 ctx.patch_procs.emplace_back(ctx.proc_body.size(), std::make_pair($3, -1));
337 ctx.proc_body.addSmallInt(0);
338 ctx.proc_body.addCharVal($4);
339 }
340 | MZA_OPEN_AGGREGATION MZA_CTX
341 {
342 $$ = ctx.proc_body.size();
343 ctx.proc_body.addInstr($1);
344 ctx.proc_body.addCharVal($2);
345 }
346 // Special cases: Using aggregation context with the same name as instructions
347 | MZA_OPEN_AGGREGATION MZA_AND
348 {
349 $$ = ctx.proc_body.size();
350 ctx.proc_body.addInstr($1);
351 ctx.proc_body.addCharVal(AggregationCtx::VCTX_AND);
352 }
353 | MZA_OPEN_AGGREGATION MZA_OR
354 {
355 $$ = ctx.proc_body.size();
356 ctx.proc_body.addInstr($1);
357 ctx.proc_body.addCharVal(AggregationCtx::VCTX_OR);
358 }
359 // Special cases: Read INT, but adds Reg value on the Stream
360 | MZA_LOAD_GLOBAL MZA_INT MZA_REG
361 {
362 $$ = ctx.proc_body.size();
363 ctx.proc_body.addInstr($1);
364 ctx.proc_body.addReg($2, true);
365 ctx.max_glob = std::max(ctx.max_glob, $2);
366 ctx.proc_body.addReg($3);
367 }
368 | MZA_STORE_GLOBAL MZA_REG MZA_INT
369 {
370 $$ = ctx.proc_body.size();
371 ctx.proc_body.addInstr($1);
372 ctx.proc_body.addReg($2);
373 ctx.proc_body.addReg($3, true);
374 ctx.max_glob = std::max(ctx.max_glob, $3);
375 }
376 | MZA_GET_ARRAY MZA_INT registers
377 {
378 $$ = ctx.proc_body.size();
379 ctx.proc_body.addInstr($1);
380 ctx.proc_body.addIntVal($2);
381 for (auto arg : *$3) {
382 ctx.proc_body.addReg(arg);
383 }
384 delete $3;
385 }
386
387instrIR:
388 MZA_IMMI
389
390instrI:
391 MZA_ITER_BREAK
392
393instrR:
394 MZA_INCI
395 | MZA_DECI
396 | MZA_PUSH
397 | MZA_POP
398 | MZA_POST
399 | MZA_ITER_NEXT
400 | MZA_TRACE
401
402instrRR:
403 MZA_MOV
404 | MZA_NOT
405 | MZA_ISPAR
406 | MZA_ISEMPTY
407 | MZA_LENGTH
408 | MZA_MAKE_SET
409 | MZA_UB
410 | MZA_LB
411 | MZA_DOM
412 | MZA_CLEAR
413
414instrRS:
415 MZA_JMPIF
416 | MZA_JMPIFNOT
417 | MZA_ITER_ARRAY
418 | MZA_ITER_VEC
419
420instrRRR:
421 MZA_ADDI
422 | MZA_SUBI
423 | MZA_MULI
424 | MZA_DIVI
425 | MZA_MODI
426 | MZA_EQI
427 | MZA_LTI
428 | MZA_LEI
429 | MZA_AND
430 | MZA_OR
431 | MZA_XOR
432 | MZA_GET_VEC
433 | MZA_DIFF
434 | MZA_INTERSECTION
435 | MZA_UNION
436 | MZA_INTERSECT_DOMAIN
437
438instrRRS:
439 MZA_ITER_RANGE
440
441instrRRIRRR:
442 MZA_SIMPLIFY_LIN
443
444instrS:
445 MZA_JMP
446
447instr:
448 MZA_RET
449 | MZA_CLOSE_AGGREGATION
450 | MZA_ABORT
451
452
453registers:
454 /* empty */ { $$ = new std::list<int>(); }
455 | registers MZA_REG { $1->push_back($2); $$ = $1; }
456
457%%
458
459#include <minizinc/interpreter/primitives.hh>
460#include <minizinc/interpreter.hh>
461
462void yyerror(YYLTYPE* location, MZAContext& ctx, const char* s) {
463 std::ostringstream oss;
464 oss << "Cannot parse MiniZinc assembly in line " << location->first_line << ": " << std::string(s);
465 throw Error(oss.str());
466}
467
468std::pair<int, std::vector<BytecodeProc>> parse_mza(const std::string& assembly_str) {
469 std::vector<BytecodeProc> procs;
470 std::unordered_map<std::string, int> proc_map;
471 int max_glob;
472 // Initialise first slots with
473 for (PrimitiveMap::Primitive* p : primitiveMap()) {
474 BytecodeProc bcp;
475 bcp.name = p->name();
476 bcp.nargs = p->n_args();
477 bcp.delay = false;
478 procs.push_back(bcp);
479 proc_map.emplace(bcp.name, p->ident());
480 }
481 mza_yy_scan_string(assembly_str.c_str());
482 MZAContext ctx = MZAContext{procs, proc_map, max_glob};
483 int err = yyparse(ctx);
484 if (err != 0) {
485 throw std::runtime_error("Cannot parse MiniZinc assembly: " + std::to_string(err));
486 }
487 for (auto& p : ctx.to_patch) {
488 int code = p.code;
489 BytecodeProc::Mode mode = p.mode;
490 for (auto& patch : p.patch) {
491 int& nargs = patch.second.second;
492 std::string& name = patch.second.first;
493
494 if (nargs >= 0 && nargs != procs[proc_map[name]].nargs) {
495 throw Error("Error: number of arguments in call to " + patch.second.first + " at position "
496 + std::to_string(patch.second.second) + " has an invalid number of arguments.\n");
497 }
498 procs[code].mode[mode].patchAddress(patch.first, proc_map[patch.second.first]);
499 }
500 }
501 return {max_glob, procs};
502}