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