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