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