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