circom/src/gencode.js
src/gencode.jsRaw
1/*
2 Copyright 2018 0KIMS association.
3
4 This file is part of jaz (Zero Knowledge Circuit Compiler).
5
6 jaz is a free software: you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 jaz is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with jaz. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const bigInt = require("big-integer");
21
22module.exports = gen;
23
24function ident(text) {
25 let lines = text.split("\n");
26 for (let i=0; i<lines.length; i++) {
27 if (lines[i]) lines[i] = " "+lines[i];
28 }
29 return lines.join("\n");
30}
31
32function gen(ctx, ast) {
33 if ((ast.type == "NUMBER") ) {
34 return genNumber(ctx, ast);
35 } else if (ast.type == "VARIABLE") {
36 return genVariable(ctx, ast);
37 } else if (ast.type == "PIN") {
38 return genPin(ctx, ast);
39 } else if (ast.type == "OP") {
40 if (ast.op == "=") {
41 return genVarAssignement(ctx, ast);
42 } else if (ast.op == "<--") {
43 return genVarAssignement(ctx, ast);
44 } else if (ast.op == "<==") {
45 return genSignalAssignConstrain(ctx, ast);
46 } else if (ast.op == "===") {
47 return genConstrain(ctx, ast);
48 } else if (ast.op == "+=") {
49 return genVarAddAssignement(ctx, ast);
50 } else if (ast.op == "*=") {
51 return genVarMulAssignement(ctx, ast);
52 } else if (ast.op == "+") {
53 return genAdd(ctx, ast);
54 } else if (ast.op == "-") {
55 return genSub(ctx, ast);
56 } else if (ast.op == "UMINUS") {
57 return genUMinus(ctx, ast);
58 } else if (ast.op == "*") {
59 return genMul(ctx, ast);
60 } else if (ast.op == "%") {
61 return genMod(ctx, ast);
62 } else if (ast.op == "PLUSPLUSRIGHT") {
63 return genPlusPlusRight(ctx, ast);
64 } else if (ast.op == "PLUSPLUSLEFT") {
65 return genPlusPlusLeft(ctx, ast);
66 } else if (ast.op == "**") {
67 return genExp(ctx, ast);
68 } else if (ast.op == "&") {
69 return genBAnd(ctx, ast);
70 } else if (ast.op == "<<") {
71 return genShl(ctx, ast);
72 } else if (ast.op == ">>") {
73 return genShr(ctx, ast);
74 } else if (ast.op == "<") {
75 return genLt(ctx, ast);
76 } else if (ast.op == ">") {
77 return genGt(ctx, ast);
78 } else if (ast.op == "<=") {
79 return genLte(ctx, ast);
80 } else if (ast.op == ">=") {
81 return genGte(ctx, ast);
82 } else if (ast.op == "==") {
83 return genEq(ctx, ast);
84 } else if (ast.op == "?") {
85 return genTerCon(ctx, ast);
86 } else {
87 error(ctx, ast, "Invalid operation: " + ast.op);
88 }
89 } else if (ast.type == "DECLARE") {
90 if (ast.declareType == "COMPONENT") {
91 return genDeclareComponent(ctx, ast);
92 } else if ((ast.declareType == "SIGNALIN")||
93 (ast.declareType == "SIGNALOUT")||
94 (ast.declareType == "SIGNAL")) {
95 return genDeclareSignal(ctx, ast);
96 } else if (ast.declareType == "VARIABLE") {
97 return genDeclareVariable(ctx, ast);
98 } else {
99 error(ctx, ast, "Invalid declaration: " + ast.declareType);
100 }
101 } else if (ast.type == "FUNCTIONCALL") {
102 return genFunctionCall(ctx, ast);
103 } else if (ast.type == "BLOCK") {
104 return genBlock(ctx, ast);
105 } else if (ast.type == "FOR") {
106 return genFor(ctx, ast);
107 } else if (ast.type == "WHILE") {
108 return genWhile(ctx, ast);
109 } else if (ast.type == "IF") {
110 return genIf(ctx, ast);
111 } else if (ast.type == "RETURN") {
112 return genReturn(ctx, ast);
113 } else if (ast.type == "TEMPLATEDEF") {
114 return genTemplateDef(ctx, ast);
115 } else if (ast.type == "FUNCTIONDEF") {
116 return genFunctionDef(ctx, ast);
117 } else if (ast.type == "INCLUDE") {
118 return genInclude(ctx, ast);
119 } else if (ast.type == "ARRAY") {
120 return genArray(ctx, ast);
121 } else {
122 error(ctx, ast, "GEN -> Invalid AST node type: " + ast.type);
123 }
124}
125
126
127function error(ctx, ast, errStr) {
128 ctx.error = {
129 pos: {
130 first_line: ast.first_line,
131 first_column: ast.first_column,
132 last_line: ast.last_line,
133 last_column: ast.last_column
134 },
135 errStr: errStr,
136 ast: ast
137 };
138}
139
140
141function getScope(ctx, name) {
142 for (let i=ctx.scopes.length-1; i>=0; i--) {
143 if (ctx.scopes[i][name]) return ctx.scopes[i][name];
144 }
145 return null;
146}
147
148
149function genFunctionCall(ctx, ast) {
150 let S = "[";
151 for (let i=0; i<ast.params.length; i++) {
152 if (i>0) S += ",";
153 S += gen(ctx, ast.params[i]);
154 }
155 S+="]";
156
157 return `ctx.callFunction("${ast.name}", ${S})`;
158}
159
160function genBlock(ctx, ast) {
161 let body = "";
162 for (let i=0; i<ast.statements.length; i++) {
163 const l = gen(ctx, ast.statements[i]);
164 if (ctx.error) return;
165 if (l) {
166 body += l;
167 if (body[body.length-1] != "\n") body += ";\n";
168 }
169 }
170 return "{\n"+ident(body)+"}\n";
171}
172
173function genTemplateDef(ctx, ast) {
174 let S = "function(ctx) ";
175
176 const newScope = {};
177 for (let i=0; i< ast.params.length; i++) {
178 newScope[ast.params[i]] = { type: "VARIABLE" };
179 }
180
181 ctx.scopes.push(newScope);
182 S += genBlock(ctx, ast.block);
183 ctx.scopes.pop();
184
185// const scope = ctx.scopes[ctx.scopes.length-1];
186 const scope = ctx.scopes[0]; // Scope for templates is top
187
188 scope[ast.name] = {
189 type: "TEMPLATE"
190 };
191
192 ctx.templates[ast.name] = S;
193 return "";
194}
195
196function genFunctionDef(ctx, ast) {
197 let S = "function(ctx) ";
198
199 const newScope = {};
200 const params = [];
201 for (let i=0; i< ast.params.length; i++) {
202 newScope[ast.params[i]] = { type: "VARIABLE" };
203 params.push(ast.params[i]);
204 }
205
206 ctx.scopes.push(newScope);
207 S += genBlock(ctx, ast.block);
208 ctx.scopes.pop();
209
210// const scope = ctx.scopes[0]; // Scope for templates is top
211 const scope = ctx.scopes[ctx.scopes.length-1];
212
213 scope[ast.name] = {
214 type: "FUNCTION"
215 };
216
217 ctx.functions[ast.name] = S;
218 ctx.functionParams[ast.name] = params;
219 return "";
220}
221
222function genFor(ctx, ast) {
223 const init = gen(ctx, ast.init);
224 if (ctx.error) return;
225 const condition = gen(ctx, ast.condition);
226 if (ctx.error) return;
227 const step = gen(ctx, ast.step);
228 if (ctx.error) return;
229 const body = gen(ctx, ast.body);
230 if (ctx.error) return;
231 return `for (${init};${condition};${step}) { \n${body}\n }\n`;
232}
233
234function genWhile(ctx, ast) {
235 const condition = gen(ctx, ast.condition);
236 if (ctx.error) return;
237 const body = gen(ctx, ast.body);
238 if (ctx.error) return;
239 return `while (${condition}) {\n${body}\n}\n`;
240}
241
242function genIf(ctx, ast) {
243 const condition = gen(ctx, ast.condition);
244 if (ctx.error) return;
245 const thenBody = gen(ctx, ast.then);
246 if (ctx.error) return;
247 const elseBody = gen(ctx, ast.else);
248 if (ctx.error) return;
249 return `if (${condition}) {\n${thenBody}\n} else {\n${elseBody}\n}\n`;
250}
251
252
253function genReturn(ctx, ast) {
254 const value = gen(ctx, ast.value);
255 if (ctx.error) return;
256 return `return ${value};`;
257}
258
259function genDeclareComponent(ctx, ast) {
260 const scope = ctx.scopes[ctx.scopes.length - 1];
261
262 if (ast.name.type != "VARIABLE") return error(ctx, ast, "Invalid component name");
263 if (getScope(ctx, ast.name.name)) return error(ctx, ast, "Name already exists: "+ast.name.name);
264
265 scope[ast.name.name] = {
266 type: "COMPONENT"
267 };
268
269 return "";
270}
271
272function genDeclareSignal(ctx, ast) {
273 const scope = ctx.scopes[ctx.scopes.length-1];
274
275 if (ast.name.type != "VARIABLE") return error(ctx, ast, "Invalid component name");
276 if (getScope(ctx, ast.name.name)) return error(ctx, ast, "Name already exists: "+ast.name.name);
277
278 scope[ast.name.name] = {
279 type: "SIGNAL"
280 };
281
282 return "";
283}
284
285function genDeclareVariable(ctx, ast) {
286 const scope = ctx.scopes[ctx.scopes.length-1];
287
288 if (ast.name.type != "VARIABLE") return error(ctx, ast, "Invalid component name");
289 if (getScope(ctx, ast.name.name)) return error(ctx, ast, "Name already exists: "+ast.name.name);
290
291 scope[ast.name.name] = {
292 type: "VARIABLE"
293 };
294
295 return "";
296}
297
298function genNumber(ctx, ast) {
299 return `"${ast.value.toString()}"`;
300}
301
302function genVariable(ctx, ast) {
303 const v = getScope(ctx, ast.name);
304
305 const sels = [];
306 for (let i=0; i<ast.selectors.length; i++) {
307 sels.push(gen(ctx, ast.selectors[i]));
308 if (ctx.error) return;
309 }
310
311
312 if (v.type == "VARIABLE") {
313 return `ctx.getVar("${ast.name}",[${sels.join(",")}])`;
314 } else if (v.type == "SIGNAL") {
315 return `ctx.getSignal("${ast.name}", [${sels.join(",")}])`;
316 } else {
317 error(ctx, ast, "Invalid Variable type");
318 }
319}
320
321function genPin(ctx, ast) {
322 let componentName = ast.component.name;
323 let componentSelectors = [];
324 for (let i=0; i<ast.component.selectors.length; i++) {
325 componentSelectors.push(gen(ctx, ast.component.selectors[i]));
326 }
327 componentSelectors = "["+ componentSelectors.join(",") + "]";
328 let pinName = ast.pin.name;
329 let pinSelectors = [];
330 for (let i=0; i<ast.pin.selectors.length; i++) {
331 pinSelectors.push(gen(ctx, ast.pin.selectors[i]));
332 }
333 pinSelectors = "["+ pinSelectors.join(",") + "]";
334 return `ctx.getPin("${componentName}", ${componentSelectors}, "${pinName}", ${pinSelectors})`;
335}
336
337function genVarAssignement(ctx, ast) {
338
339 const sels = [];
340 let vName;
341
342 if (ctx.error) return;
343
344 if (ast.values[0].type == "PIN") {
345 let componentName = ast.values[0].component.name;
346 let componentSelectors = [];
347 for (let i=0; i<ast.values[0].component.selectors.length; i++) {
348 componentSelectors.push(gen(ctx, ast.values[0].component.selectors[i]));
349 }
350 componentSelectors = "["+ componentSelectors.join(",") + "]";
351 let pinName = ast.values[0].pin.name;
352 let pinSelectors = [];
353 for (let i=0; i<ast.values[0].pin.selectors.length; i++) {
354 pinSelectors.push(gen(ctx, ast.values[0].pin.selectors[i]));
355 }
356 pinSelectors = "["+ pinSelectors.join(",") + "]";
357 const res = gen(ctx, ast.values[1]);
358 return `ctx.setPin("${componentName}", ${componentSelectors}, "${pinName}", ${pinSelectors}, ${res})`;
359 }
360
361 if (ast.values[0].type == "DECLARE") {
362 gen(ctx, ast.values[0]);
363 if (ctx.error) return;
364 vName = ast.values[0].name.name;
365 } else {
366 vName = ast.values[0].name;
367 for (let i=0; i<ast.values[0].selectors.length; i++) {
368 sels.push(gen(ctx, ast.values[0].selectors[i]));
369 if (ctx.error) return;
370 }
371 }
372
373
374 const v = getScope(ctx, vName);
375
376 // Component instantiation is already done.
377 if (v.type == "COMPONENT") return "";
378
379 const res = gen(ctx, ast.values[1]);
380 if (v.type == "VARIABLE") {
381 return `ctx.setVar("${vName}", [${sels.join(",")}], ${res})`;
382 } else if (v.type == "SIGNAL") {
383 return `ctx.setSignal("${vName}", [${sels.join(",")}], ${res})`;
384 } else {
385 return error(ctx, ast, "Assigning to invalid");
386 }
387}
388
389function genConstrain(ctx, ast) {
390 const a = gen(ctx, ast.values[0]);
391 if (ctx.error) return;
392 const b = gen(ctx, ast.values[1]);
393 if (ctx.error) return;
394 return `ctx.assert(${a}, ${b})`;
395}
396
397function genSignalAssignConstrain(ctx, ast) {
398 return genVarAssignement(ctx, ast) + ";\n" + genConstrain(ctx, ast);
399}
400
401function genVarAddAssignement(ctx, ast) {
402 return genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "+", values: ast.values}]});
403}
404
405function genVarMulAssignement(ctx, ast) {
406 return genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "*", values: ast.values}]});
407}
408
409function genPlusPlusRight(ctx, ast) {
410 return `(${genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "+", values: [ast.values[0], {type: "NUMBER", value: bigInt(1)}]}]})}).add(__P__).sub(bigInt(1)).mod(__P__)`;
411}
412
413function genPlusPlusLeft(ctx, ast) {
414 return genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "+", values: [ast.values[0], {type: "NUMBER", value: bigInt(1)}]}]});
415}
416
417function genAdd(ctx, ast) {
418 const a = gen(ctx, ast.values[0]);
419 if (ctx.error) return;
420 const b = gen(ctx, ast.values[1]);
421 if (ctx.error) return;
422 return `bigInt(${a}).add(bigInt(${b})).mod(__P__)`;
423}
424
425function genMul(ctx, ast) {
426 const a = gen(ctx, ast.values[0]);
427 if (ctx.error) return;
428 const b = gen(ctx, ast.values[1]);
429 if (ctx.error) return;
430 return `bigInt(${a}).mul(bigInt(${b})).mod(__P__)`;
431}
432
433function genSub(ctx, ast) {
434 const a = gen(ctx, ast.values[0]);
435 if (ctx.error) return;
436 const b = gen(ctx, ast.values[1]);
437 if (ctx.error) return;
438 return `bigInt(${a}).add(__P__).sub(bigInt(${b})).mod(__P__)`;
439}
440
441function genExp(ctx, ast) {
442 const a = gen(ctx, ast.values[0]);
443 if (ctx.error) return;
444 const b = gen(ctx, ast.values[1]);
445 if (ctx.error) return;
446 return `bigInt(${a}).modPow(bigInt(${b}), __P__)`;
447}
448
449function genBAnd(ctx, ast) {
450 const a = gen(ctx, ast.values[0]);
451 if (ctx.error) return;
452 const b = gen(ctx, ast.values[1]);
453 if (ctx.error) return;
454 return `bigInt(${a}).and(bigInt(${b})).and(__MASK__)`;
455}
456
457function genShl(ctx, ast) {
458 const a = gen(ctx, ast.values[0]);
459 if (ctx.error) return;
460 const b = gen(ctx, ast.values[1]);
461 if (ctx.error) return;
462 return `bigInt(${b}).greater(bigInt(256)) ? 0 : bigInt(${a}).shl(bigInt(${b})).and(__MASK__)`;
463}
464
465function genShr(ctx, ast) {
466 const a = gen(ctx, ast.values[0]);
467 if (ctx.error) return;
468 const b = gen(ctx, ast.values[1]);
469 if (ctx.error) return;
470 return `bigInt(${b}).greater(bigInt(256)) ? 0 : bigInt(${a}).shr(bigInt(${b})).and(__MASK__)`;
471}
472
473function genMod(ctx, ast) {
474 const a = gen(ctx, ast.values[0]);
475 if (ctx.error) return;
476 const b = gen(ctx, ast.values[1]);
477 if (ctx.error) return;
478 return `bigInt(${a}).mod(bigInt(${b}))`;
479}
480
481function genLt(ctx, ast) {
482 const a = gen(ctx, ast.values[0]);
483 if (ctx.error) return;
484 const b = gen(ctx, ast.values[1]);
485 if (ctx.error) return;
486 return `bigInt(${a}).lt(bigInt(${b})) ? 1 : 0`;
487}
488
489function genGt(ctx, ast) {
490 const a = gen(ctx, ast.values[0]);
491 if (ctx.error) return;
492 const b = gen(ctx, ast.values[1]);
493 if (ctx.error) return;
494 return `bigInt(${a}).gt(bigInt(${b})) ? 1 : 0`;
495}
496
497function genLte(ctx, ast) {
498 const a = gen(ctx, ast.values[0]);
499 if (ctx.error) return;
500 const b = gen(ctx, ast.values[1]);
501 if (ctx.error) return;
502 return `bigInt(${a}).lesserOrEquals(bigInt(${b})) ? 1 : 0`;
503}
504
505function genGte(ctx, ast) {
506 const a = gen(ctx, ast.values[0]);
507 if (ctx.error) return;
508 const b = gen(ctx, ast.values[1]);
509 if (ctx.error) return;
510 return `bigInt(${a}).greaterOrEquals(bigInt(${b})) ? 1 : 0`;
511}
512
513function genEq(ctx, ast) {
514 const a = gen(ctx, ast.values[0]);
515 if (ctx.error) return;
516 const b = gen(ctx, ast.values[1]);
517 if (ctx.error) return;
518 return `bigInt(${a}).eq(bigInt(${b})) ? 1 : 0`;
519}
520
521function genUMinus(ctx, ast) {
522 const a = gen(ctx, ast.values[0]);
523 if (ctx.error) return;
524 return `__P__.sub(bigInt(${a})).mod(__P__)`;
525}
526
527function genTerCon(ctx, ast) {
528 const a = gen(ctx, ast.values[0]);
529 if (ctx.error) return;
530 const b = gen(ctx, ast.values[1]);
531 if (ctx.error) return;
532 const c = gen(ctx, ast.values[2]);
533 if (ctx.error) return;
534 return `bigInt(${a}).neq(bigInt(0)) ? (${b}) : (${c})`;
535}
536
537function genInclude(ctx, ast) {
538 return ast.block ? gen(ctx, ast.block) : "";
539}
540
541function genArray(ctx, ast) {
542 let S = "[";
543 for (let i=0; i<ast.values.length; i++) {
544 if (i>0) S += ",";
545 S += gen(ctx, ast.values[i]);
546 }
547 S+="]";
548 return S;
549}
550