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