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