circom/src/gencode.js
src/gencode.jsRaw
1/*
2 Copyright 2018 0KIMS association.
3
4 This file is part of circom (Zero Knowledge Circuit Compiler).
5
6 circom 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 circom 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 circom. 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 == "MINUSMINUSRIGHT") {
67 return genMinusMinusRight(ctx, ast);
68 } else if (ast.op == "MINUSMINUSLEFT") {
69 return genMinusMinusLeft(ctx, ast);
70 } else if (ast.op == "**") {
71 return genExp(ctx, ast);
72 } else if (ast.op == "/") {
73 return genDiv(ctx, ast);
74 } else if (ast.op == "\\") {
75 return genIDiv(ctx, ast);
76 } else if (ast.op == "&") {
77 return genBAnd(ctx, ast);
78 } else if (ast.op == "&&") {
79 return genAnd(ctx, ast);
80 } else if (ast.op == "||") {
81 return genOr(ctx, ast);
82 } else if (ast.op == "<<") {
83 return genShl(ctx, ast);
84 } else if (ast.op == ">>") {
85 return genShr(ctx, ast);
86 } else if (ast.op == "<") {
87 return genLt(ctx, ast);
88 } else if (ast.op == ">") {
89 return genGt(ctx, ast);
90 } else if (ast.op == "<=") {
91 return genLte(ctx, ast);
92 } else if (ast.op == ">=") {
93 return genGte(ctx, ast);
94 } else if (ast.op == "==") {
95 return genEq(ctx, ast);
96 } else if (ast.op == "!=") {
97 return genNeq(ctx, ast);
98 } else if (ast.op == "?") {
99 return genTerCon(ctx, ast);
100 } else {
101 error(ctx, ast, "Invalid operation: " + ast.op);
102 }
103 } else if (ast.type == "DECLARE") {
104 if (ast.declareType == "COMPONENT") {
105 return genDeclareComponent(ctx, ast);
106 } else if ((ast.declareType == "SIGNALIN")||
107 (ast.declareType == "SIGNALOUT")||
108 (ast.declareType == "SIGNAL")) {
109 return genDeclareSignal(ctx, ast);
110 } else if (ast.declareType == "VARIABLE") {
111 return genDeclareVariable(ctx, ast);
112 } else {
113 error(ctx, ast, "Invalid declaration: " + ast.declareType);
114 }
115 } else if (ast.type == "FUNCTIONCALL") {
116 return genFunctionCall(ctx, ast);
117 } else if (ast.type == "BLOCK") {
118 return genBlock(ctx, ast);
119 } else if (ast.type == "COMPUTE") {
120 return genCompute(ctx, ast);
121 } else if (ast.type == "FOR") {
122 return genFor(ctx, ast);
123 } else if (ast.type == "WHILE") {
124 return genWhile(ctx, ast);
125 } else if (ast.type == "IF") {
126 return genIf(ctx, ast);
127 } else if (ast.type == "RETURN") {
128 return genReturn(ctx, ast);
129 } else if (ast.type == "TEMPLATEDEF") {
130 return genTemplateDef(ctx, ast);
131 } else if (ast.type == "FUNCTIONDEF") {
132 return genFunctionDef(ctx, ast);
133 } else if (ast.type == "INCLUDE") {
134 return genInclude(ctx, ast);
135 } else if (ast.type == "ARRAY") {
136 return genArray(ctx, ast);
137 } else {
138 error(ctx, ast, "GEN -> Invalid AST node type: " + ast.type);
139 }
140}
141
142
143function error(ctx, ast, errStr) {
144 ctx.error = {
145 pos: {
146 first_line: ast.first_line,
147 first_column: ast.first_column,
148 last_line: ast.last_line,
149 last_column: ast.last_column
150 },
151 errStr: errStr,
152 ast: ast,
153 message: errStr
154 };
155}
156
157
158function getScope(ctx, name) {
159 for (let i=ctx.scopes.length-1; i>=0; i--) {
160 if (ctx.scopes[i][name]) return ctx.scopes[i][name];
161 }
162 return null;
163}
164
165
166function genFunctionCall(ctx, ast) {
167 let S = "[";
168 for (let i=0; i<ast.params.length; i++) {
169 if (i>0) S += ",";
170 S += gen(ctx, ast.params[i]);
171 }
172 S+="]";
173
174 return `ctx.callFunction("${ast.name}", ${S})`;
175}
176
177function genBlock(ctx, ast) {
178 let body = "";
179 for (let i=0; i<ast.statements.length; i++) {
180 const l = gen(ctx, ast.statements[i]);
181 if (ctx.error) return;
182 if (l) {
183 body += l;
184 if (body[body.length-1] != "\n") body += ";\n";
185 }
186 }
187 return "{\n"+ident(body)+"}\n";
188}
189
190function genTemplateDef(ctx, ast) {
191
192 if (ctx.f) return error(ctx, ast, "Already in function");
193
194 ctx.f = ctx.module.addFunction(ast.name);
195 ctx.c = ctx.f.getCodeBuilder();
196
197 ctx.scope = {};
198 for (let i=0; i< ast.params.length; i++) {
199 ctx.f.addParam(ast.params[i].name, "i32");
200 ctx.scope[ast.params[i].name] = {
201 type: "PARAM",
202 sels: ast.params[i].sels,
203 getter: () => { return ctx.c.getLocal(ast.params[i].name); },
204 setter: (v) => { return ctx.c.setLocal(ast.params[i].name, v); }
205 };
206 }
207
208 genBlock(ctx, ast.block);
209
210 ctx.scope = null;
211 ctx.c = null;
212 ctx.f = null;
213}
214
215function genFunctionDef(ctx, ast) {
216 let S = "function(ctx) ";
217
218 const newScope = {};
219 const params = [];
220 for (let i=0; i< ast.params.length; i++) {
221 newScope[ast.params[i]] = { type: "VARIABLE" };
222 params.push(ast.params[i]);
223 }
224
225 ctx.scopes.push(newScope);
226 S += genBlock(ctx, ast.block);
227 ctx.scopes.pop();
228
229// const scope = ctx.scopes[0]; // Scope for templates is top
230 const scope = ctx.scopes[ctx.scopes.length-1];
231
232 scope[ast.name] = {
233 type: "FUNCTION"
234 };
235
236 ctx.functions[ast.name] = S;
237 ctx.functionParams[ast.name] = params;
238 return "";
239}
240
241function genFor(ctx, ast) {
242 ctx.scopes.push({});
243 const init = gen(ctx, ast.init);
244 if (ctx.error) return;
245 const condition = gen(ctx, ast.condition);
246 if (ctx.error) return;
247 const step = gen(ctx, ast.step);
248 if (ctx.error) return;
249 const body = gen(ctx, ast.body);
250 if (ctx.error) return;
251 ctx.scopes.pop();
252 return `for (${init};bigInt(${condition}).neq(bigInt(0));${step}) { \n${body}\n }\n`;
253}
254
255function genWhile(ctx, ast) {
256 const condition = gen(ctx, ast.condition);
257 if (ctx.error) return;
258 const body = gen(ctx, ast.body);
259 if (ctx.error) return;
260 return `while (bigInt(${condition}).neq(bigInt(0))) {\n${body}\n}\n`;
261}
262
263function genCompute(ctx, ast) {
264 const body = gen(ctx, ast.body);
265 if (ctx.error) return;
266 return `{\n${body}\n}\n`;
267}
268
269function genIf(ctx, ast) {
270 const condition = gen(ctx, ast.condition);
271 if (ctx.error) return;
272 const thenBody = gen(ctx, ast.then);
273 if (ctx.error) return;
274 if (ast.else) {
275 const elseBody = gen(ctx, ast.else);
276 if (ctx.error) return;
277 return `if (bigInt(${condition}).neq(bigInt(0))) {\n${thenBody}\n} else {\n${elseBody}\n}\n`;
278 } else {
279 return `if (bigInt(${condition}).neq(bigInt(0))) {\n${thenBody}\n}\n`;
280 }
281}
282
283
284function genReturn(ctx, ast) {
285 const value = gen(ctx, ast.value);
286 if (ctx.error) return;
287 return `return ${value};`;
288}
289
290function genDeclareComponent(ctx, ast) {
291 const scope = ctx.scopes[ctx.scopes.length - 1];
292
293 if (ast.name.type != "VARIABLE") return error(ctx, ast, "Invalid component name");
294 if (getScope(ctx, ast.name.name)) return error(ctx, ast, "Name already exists: "+ast.name.name);
295
296 scope[ast.name.name] = {
297 type: "COMPONENT"
298 };
299
300 return "";
301}
302
303function genDeclareSignal(ctx, ast) {
304 const scope = ctx.scopes[ctx.scopes.length-1];
305
306 if (ast.name.type != "VARIABLE") return error(ctx, ast, "Invalid component name");
307 if (getScope(ctx, ast.name.name)) return error(ctx, ast, "Name already exists: "+ast.name.name);
308
309 scope[ast.name.name] = {
310 type: "SIGNAL"
311 };
312
313 return "";
314}
315
316function genDeclareVariable(ctx, ast) {
317 const scope = ctx.scopes[ctx.scopes.length-1];
318
319 if (ast.name.type != "VARIABLE") return error(ctx, ast, "Invalid component name");
320 if (getScope(ctx, ast.name.name)) return error(ctx, ast, "Name already exists: "+ast.name.name);
321
322 scope[ast.name.name] = {
323 type: "VARIABLE"
324 };
325
326 return "";
327}
328
329function genNumber(ctx, ast) {
330 return `"${ast.value.toString()}"`;
331}
332
333function genVariable(ctx, ast) {
334 const v = getScope(ctx, ast.name);
335
336 const sels = [];
337 for (let i=0; i<ast.selectors.length; i++) {
338 sels.push(gen(ctx, ast.selectors[i]));
339 if (ctx.error) return;
340 }
341
342 if (!v) {
343 return error(ctx, ast, "Invalid left operand");
344 }
345 if (v.type == "VARIABLE") {
346 return `ctx.getVar("${ast.name}",[${sels.join(",")}])`;
347 } else if (v.type == "SIGNAL") {
348 return `ctx.getSignal("${ast.name}", [${sels.join(",")}])`;
349 } else {
350 error(ctx, ast, "Invalid Variable type");
351 }
352}
353
354function genPin(ctx, ast) {
355 let componentName = ast.component.name;
356 let componentSelectors = [];
357 for (let i=0; i<ast.component.selectors.length; i++) {
358 componentSelectors.push(gen(ctx, ast.component.selectors[i]));
359 }
360 componentSelectors = "["+ componentSelectors.join(",") + "]";
361 let pinName = ast.pin.name;
362 let pinSelectors = [];
363 for (let i=0; i<ast.pin.selectors.length; i++) {
364 pinSelectors.push(gen(ctx, ast.pin.selectors[i]));
365 }
366 pinSelectors = "["+ pinSelectors.join(",") + "]";
367 return `ctx.getPin("${componentName}", ${componentSelectors}, "${pinName}", ${pinSelectors})`;
368}
369
370function genVarAssignement(ctx, ast) {
371
372 const sels = [];
373 let vName;
374
375 if (ctx.error) return;
376
377 if (ast.values[0].type == "PIN") {
378 let componentName = ast.values[0].component.name;
379 let componentSelectors = [];
380 for (let i=0; i<ast.values[0].component.selectors.length; i++) {
381 componentSelectors.push(gen(ctx, ast.values[0].component.selectors[i]));
382 }
383 componentSelectors = "["+ componentSelectors.join(",") + "]";
384 let pinName = ast.values[0].pin.name;
385 let pinSelectors = [];
386 for (let i=0; i<ast.values[0].pin.selectors.length; i++) {
387 pinSelectors.push(gen(ctx, ast.values[0].pin.selectors[i]));
388 }
389 pinSelectors = "["+ pinSelectors.join(",") + "]";
390 const res = gen(ctx, ast.values[1]);
391 return `ctx.setPin("${componentName}", ${componentSelectors}, "${pinName}", ${pinSelectors}, ${res})`;
392 }
393
394 if (ast.values[0].type == "DECLARE") {
395 gen(ctx, ast.values[0]);
396 if (ctx.error) return;
397 vName = ast.values[0].name.name;
398 } else {
399 vName = ast.values[0].name;
400 for (let i=0; i<ast.values[0].selectors.length; i++) {
401 sels.push(gen(ctx, ast.values[0].selectors[i]));
402 if (ctx.error) return;
403 }
404 }
405
406
407 const v = getScope(ctx, vName);
408
409 // Component instantiation is already done.
410 if (v.type == "COMPONENT") return "";
411
412 const res = gen(ctx, ast.values[1]);
413 if (v.type == "VARIABLE") {
414 return `ctx.setVar("${vName}", [${sels.join(",")}], ${res})`;
415 } else if (v.type == "SIGNAL") {
416 return `ctx.setSignal("${vName}", [${sels.join(",")}], ${res})`;
417 } else {
418 return error(ctx, ast, "Assigning to invalid");
419 }
420}
421
422function genConstrain(ctx, ast) {
423 const a = gen(ctx, ast.values[0]);
424 if (ctx.error) return;
425 const b = gen(ctx, ast.values[1]);
426 if (ctx.error) return;
427 const strErr = ast.fileName + ":" + ast.first_line + ":" + ast.first_column;
428 return `ctx.assert(${a}, ${b}, \"${strErr}\")`;
429}
430
431function genSignalAssignConstrain(ctx, ast) {
432// return genVarAssignement(ctx, ast) + ";\n" + genConstrain(ctx, ast);
433 return genVarAssignement(ctx, ast);
434}
435
436function genVarAddAssignement(ctx, ast) {
437 return genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "+", values: ast.values}]});
438}
439
440function genVarMulAssignement(ctx, ast) {
441 return genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "*", values: ast.values}]});
442}
443
444function genPlusPlusRight(ctx, ast) {
445 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__)`;
446}
447
448function genPlusPlusLeft(ctx, ast) {
449 return genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "+", values: [ast.values[0], {type: "NUMBER", value: bigInt(1)}]}]});
450}
451
452function genMinusMinusRight(ctx, ast) {
453 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__)`;
454}
455
456function genMinusMinusLeft(ctx, ast) {
457 return genVarAssignement(ctx, {values: [ast.values[0], {type: "OP", op: "-", values: [ast.values[0], {type: "NUMBER", value: bigInt(1)}]}]});
458}
459
460function genAdd(ctx, ast) {
461 const a = gen(ctx, ast.values[0]);
462 if (ctx.error) return;
463 const b = gen(ctx, ast.values[1]);
464 if (ctx.error) return;
465 return `bigInt(${a}).add(bigInt(${b})).mod(__P__)`;
466}
467
468function genMul(ctx, ast) {
469 const a = gen(ctx, ast.values[0]);
470 if (ctx.error) return;
471 const b = gen(ctx, ast.values[1]);
472 if (ctx.error) return;
473 return `bigInt(${a}).mul(bigInt(${b})).mod(__P__)`;
474}
475
476function genSub(ctx, ast) {
477 const a = gen(ctx, ast.values[0]);
478 if (ctx.error) return;
479 const b = gen(ctx, ast.values[1]);
480 if (ctx.error) return;
481 return `bigInt(${a}).add(__P__).sub(bigInt(${b})).mod(__P__)`;
482}
483
484function genDiv(ctx, ast) {
485 const a = gen(ctx, ast.values[0]);
486 if (ctx.error) return;
487 const b = gen(ctx, ast.values[1]);
488 if (ctx.error) return;
489
490 return `bigInt(${a}).mul( bigInt(${b}).inverse(__P__) ).mod(__P__)`;
491}
492
493function genIDiv(ctx, ast) {
494 const a = gen(ctx, ast.values[0]);
495 if (ctx.error) return;
496 const b = gen(ctx, ast.values[1]);
497 if (ctx.error) return;
498
499 return `bigInt(${a}).div( bigInt(${b}))`;
500}
501
502function genExp(ctx, ast) {
503 const a = gen(ctx, ast.values[0]);
504 if (ctx.error) return;
505 const b = gen(ctx, ast.values[1]);
506 if (ctx.error) return;
507 return `bigInt(${a}).modPow(bigInt(${b}), __P__)`;
508}
509
510function genBAnd(ctx, ast) {
511 const a = gen(ctx, ast.values[0]);
512 if (ctx.error) return;
513 const b = gen(ctx, ast.values[1]);
514 if (ctx.error) return;
515 return `bigInt(${a}).and(bigInt(${b})).and(__MASK__)`;
516}
517
518function genAnd(ctx, ast) {
519 const a = gen(ctx, ast.values[0]);
520 if (ctx.error) return;
521 const b = gen(ctx, ast.values[1]);
522 if (ctx.error) return;
523 return `((bigInt(${a}).neq(bigInt(0)) && bigInt(${b}).neq(bigInt(0))) ? bigInt(1) : bigInt(0))`;
524}
525
526function genOr(ctx, ast) {
527 const a = gen(ctx, ast.values[0]);
528 if (ctx.error) return;
529 const b = gen(ctx, ast.values[1]);
530 if (ctx.error) return;
531 return `((bigInt(${a}).neq(bigInt(0)) || bigInt(${b}).neq(bigInt(0))) ? bigInt(1) : bigInt(0))`;
532}
533
534function genShl(ctx, ast) {
535 const a = gen(ctx, ast.values[0]);
536 if (ctx.error) return;
537 const b = gen(ctx, ast.values[1]);
538 if (ctx.error) return;
539 return `bigInt(${b}).greater(bigInt(256)) ? 0 : bigInt(${a}).shl(bigInt(${b})).and(__MASK__)`;
540}
541
542function genShr(ctx, ast) {
543 const a = gen(ctx, ast.values[0]);
544 if (ctx.error) return;
545 const b = gen(ctx, ast.values[1]);
546 if (ctx.error) return;
547 return `bigInt(${b}).greater(bigInt(256)) ? 0 : bigInt(${a}).shr(bigInt(${b})).and(__MASK__)`;
548}
549
550function genMod(ctx, ast) {
551 const a = gen(ctx, ast.values[0]);
552 if (ctx.error) return;
553 const b = gen(ctx, ast.values[1]);
554 if (ctx.error) return;
555 return `bigInt(${a}).mod(bigInt(${b}))`;
556}
557
558function genLt(ctx, ast) {
559 const a = gen(ctx, ast.values[0]);
560 if (ctx.error) return;
561 const b = gen(ctx, ast.values[1]);
562 if (ctx.error) return;
563 return `bigInt(${a}).lt(bigInt(${b})) ? 1 : 0`;
564}
565
566function genGt(ctx, ast) {
567 const a = gen(ctx, ast.values[0]);
568 if (ctx.error) return;
569 const b = gen(ctx, ast.values[1]);
570 if (ctx.error) return;
571 return `bigInt(${a}).gt(bigInt(${b})) ? 1 : 0`;
572}
573
574function genLte(ctx, ast) {
575 const a = gen(ctx, ast.values[0]);
576 if (ctx.error) return;
577 const b = gen(ctx, ast.values[1]);
578 if (ctx.error) return;
579 return `bigInt(${a}).lesserOrEquals(bigInt(${b})) ? 1 : 0`;
580}
581
582function genGte(ctx, ast) {
583 const a = gen(ctx, ast.values[0]);
584 if (ctx.error) return;
585 const b = gen(ctx, ast.values[1]);
586 if (ctx.error) return;
587 return `bigInt(${a}).greaterOrEquals(bigInt(${b})) ? 1 : 0`;
588}
589
590function genEq(ctx, ast) {
591 const a = gen(ctx, ast.values[0]);
592 if (ctx.error) return;
593 const b = gen(ctx, ast.values[1]);
594 if (ctx.error) return;
595 return `(bigInt(${a}).eq(bigInt(${b})) ? 1 : 0)`;
596}
597
598function genNeq(ctx, ast) {
599 const a = gen(ctx, ast.values[0]);
600 if (ctx.error) return;
601 const b = gen(ctx, ast.values[1]);
602 if (ctx.error) return;
603 return `(bigInt(${a}).eq(bigInt(${b})) ? 0 : 1)`;
604}
605
606function genUMinus(ctx, ast) {
607 const a = gen(ctx, ast.values[0]);
608 if (ctx.error) return;
609 return `__P__.sub(bigInt(${a})).mod(__P__)`;
610}
611
612function genTerCon(ctx, ast) {
613 const a = gen(ctx, ast.values[0]);
614 if (ctx.error) return;
615 const b = gen(ctx, ast.values[1]);
616 if (ctx.error) return;
617 const c = gen(ctx, ast.values[2]);
618 if (ctx.error) return;
619 return `bigInt(${a}).neq(bigInt(0)) ? (${b}) : (${c})`;
620}
621
622function genInclude(ctx, ast) {
623 return ast.block ? gen(ctx, ast.block) : "";
624}
625
626function genArray(ctx, ast) {
627 let S = "[";
628 for (let i=0; i<ast.values.length; i++) {
629 if (i>0) S += ",";
630 S += gen(ctx, ast.values[i]);
631 }
632 S+="]";
633 return S;
634}
635