go-snark/circuitcompiler/parser.go
circuitcompiler/parser.goRaw
1package circuitcompiler
2
3import (
4 "bufio"
5 "errors"
6 "fmt"
7 "io"
8 "os"
9 "regexp"
10 "strconv"
11 "strings"
12)
13
14// Parser data structure holds the Scanner and the Parsing functions
15type Parser struct {
16 s *Scanner
17 buf struct {
18 tok Token // last read token
19 lit string // last read literal
20 n int // buffer size (max=1)
21 }
22}
23
24// NewParser creates a new parser from a io.Reader
25func NewParser(r io.Reader) *Parser {
26 return &Parser{s: NewScanner(r)}
27}
28
29func (p *Parser) scan() (tok Token, lit string) {
30 // if there is a token in the buffer return it
31 if p.buf.n != 0 {
32 p.buf.n = 0
33 return p.buf.tok, p.buf.lit
34 }
35 tok, lit = p.s.scan()
36
37 p.buf.tok, p.buf.lit = tok, lit
38
39 return
40}
41
42func (p *Parser) unscan() {
43 p.buf.n = 1
44}
45
46func (p *Parser) scanIgnoreWhitespace() (tok Token, lit string) {
47 tok, lit = p.scan()
48 if tok == WS {
49 tok, lit = p.scan()
50 }
51 return
52}
53
54// parseLine parses the current line
55func (p *Parser) parseLine() (*Constraint, error) {
56 /*
57 in this version,
58 line will be for example s3 = s1 * s4
59 this is:
60 val eq val op val
61 */
62 c := &Constraint{}
63 tok, lit := p.scanIgnoreWhitespace()
64 c.Out = lit
65 c.Literal += lit
66
67 if c.Literal == "func" {
68 // format: `func name(in):`
69 line, err := p.s.r.ReadString(':')
70 if err != nil {
71 return c, err
72 }
73 // get func name
74 fName := strings.Split(line, "(")[0]
75 fName = strings.Replace(fName, " ", "", -1)
76 fName = strings.Replace(fName, " ", "", -1)
77 c.V1 = fName // so, the name of the func will be in c.V1
78
79 // read string inside ( )
80 rgx := regexp.MustCompile(`\((.*?)\)`)
81 insideParenthesis := rgx.FindStringSubmatch(line)
82 varsString := strings.Replace(insideParenthesis[1], " ", "", -1)
83 allInputs := strings.Split(varsString, ",")
84
85 // from allInputs, get the private and the public separated
86 for _, in := range allInputs {
87 if strings.Contains(in, "private") {
88 input := strings.Replace(in, "private", "", -1)
89 c.PrivateInputs = append(c.PrivateInputs, input)
90 } else if strings.Contains(in, "public") {
91 input := strings.Replace(in, "public", "", -1)
92 c.PublicInputs = append(c.PublicInputs, input)
93 } else {
94 // TODO give more info about the circuit code error
95 fmt.Println("error on declaration of public and private inputs")
96 os.Exit(0)
97 }
98 }
99 return c, nil
100 }
101 if c.Literal == "equals" {
102 // format: `equals(a, b)`
103 line, err := p.s.r.ReadString(')')
104 if err != nil {
105 return c, err
106 }
107 // read string inside ( )
108 rgx := regexp.MustCompile(`\((.*?)\)`)
109 insideParenthesis := rgx.FindStringSubmatch(line)
110 varsString := strings.Replace(insideParenthesis[1], " ", "", -1)
111 params := strings.Split(varsString, ",")
112 c.V1 = params[0]
113 c.V2 = params[1]
114 return c, nil
115 }
116 if c.Literal == "return" {
117 _, varToReturn := p.scanIgnoreWhitespace()
118 c.Out = varToReturn
119 return c, nil
120 }
121 if c.Literal == "import" {
122 line, err := p.s.r.ReadString('\n')
123 if err != nil {
124 return c, err
125 }
126 // read string inside " "
127 path := strings.TrimLeft(strings.TrimRight(line, `"`), `"`)
128 path = strings.Replace(path, `"`, "", -1)
129 path = strings.Replace(path, " ", "", -1)
130 path = strings.Replace(path, "\n", "", -1)
131 c.Out = path
132 return c, nil
133 }
134
135 _, lit = p.scanIgnoreWhitespace() // skip =
136 c.Literal += lit
137
138 // v1
139 _, lit = p.scanIgnoreWhitespace()
140
141 // check if lit is a name of a func that we have declared
142 if _, ok := circuits[lit]; ok {
143 // if inside, is calling a declared function
144 c.Literal = "call"
145 c.Op = lit // c.Op handles the name of the function called
146 // put the inputs of the call into the c.PrivateInputs
147 // format: `funcname(a, b)`
148 line, err := p.s.r.ReadString(')')
149 if err != nil {
150 fmt.Println("ERR", err)
151 return c, err
152 }
153 // read string inside ( )
154 rgx := regexp.MustCompile(`\((.*?)\)`)
155 insideParenthesis := rgx.FindStringSubmatch(line)
156 varsString := strings.Replace(insideParenthesis[1], " ", "", -1)
157 params := strings.Split(varsString, ",")
158 c.PrivateInputs = params
159 return c, nil
160
161 }
162
163 c.V1 = lit
164 c.Literal += lit
165 // operator
166 _, lit = p.scanIgnoreWhitespace()
167 if lit == "(" {
168 panic(errors.New("using not declared function"))
169 }
170 c.Op = lit
171 c.Literal += lit
172 // v2
173 _, lit = p.scanIgnoreWhitespace()
174 c.V2 = lit
175 c.Literal += lit
176 if tok == EOF {
177 return nil, errors.New("eof in parseline")
178 }
179 return c, nil
180}
181
182func existInArray(arr []string, elem string) bool {
183 for _, v := range arr {
184 if v == elem {
185 return true
186 }
187 }
188 return false
189}
190
191func addToArrayIfNotExist(arr []string, elem string) []string {
192 for _, v := range arr {
193 if v == elem {
194 return arr
195 }
196 }
197 arr = append(arr, elem)
198 return arr
199}
200
201func subsIfInMap(original string, m map[string]string) string {
202 if v, ok := m[original]; ok {
203 return v
204 }
205 return original
206}
207
208var circuits map[string]*Circuit
209
210// Parse parses the lines and returns the compiled Circuit
211func (p *Parser) Parse() (*Circuit, error) {
212 // funcsMap is a map holding the functions names and it's content as Circuit
213 circuits = make(map[string]*Circuit)
214 mainExist := false
215 circuits["main"] = &Circuit{}
216 callsCount := 0
217
218 circuits["main"].Signals = append(circuits["main"].Signals, "one")
219 nInputs := 0
220 currCircuit := ""
221 for {
222 constraint, err := p.parseLine()
223 if err != nil {
224 break
225 }
226 if constraint.Literal == "func" {
227 // the name of the func is in constraint.V1
228 // check if the name of func is main
229 if constraint.V1 != "main" {
230 currCircuit = constraint.V1
231 circuits[currCircuit] = &Circuit{}
232 circuits[currCircuit].Constraints = append(circuits[currCircuit].Constraints, *constraint)
233 continue
234 }
235 currCircuit = "main"
236 mainExist = true
237 // l, _ := json.Marshal(constraint)
238 // fmt.Println(string(l))
239
240 // one constraint for each input
241 for _, in := range constraint.PublicInputs {
242 newConstr := &Constraint{
243 Op: "in",
244 Out: in,
245 }
246 circuits[currCircuit].Constraints = append(circuits[currCircuit].Constraints, *newConstr)
247 nInputs++
248 circuits[currCircuit].Signals = addToArrayIfNotExist(circuits[currCircuit].Signals, in)
249 circuits[currCircuit].NPublic++
250 }
251 for _, in := range constraint.PrivateInputs {
252 newConstr := &Constraint{
253 Op: "in",
254 Out: in,
255 }
256 circuits[currCircuit].Constraints = append(circuits[currCircuit].Constraints, *newConstr)
257 nInputs++
258 circuits[currCircuit].Signals = addToArrayIfNotExist(circuits[currCircuit].Signals, in)
259 }
260 circuits[currCircuit].PublicInputs = constraint.PublicInputs
261 circuits[currCircuit].PrivateInputs = constraint.PrivateInputs
262 continue
263 }
264 if constraint.Literal == "equals" {
265 constr1 := &Constraint{
266 Op: "*",
267 V1: constraint.V2,
268 V2: "1",
269 Out: constraint.V1,
270 Literal: "equals(" + constraint.V1 + ", " + constraint.V2 + "): " + constraint.V1 + "==" + constraint.V2 + " * 1",
271 }
272 circuits[currCircuit].Constraints = append(circuits[currCircuit].Constraints, *constr1)
273 constr2 := &Constraint{
274 Op: "*",
275 V1: constraint.V1,
276 V2: "1",
277 Out: constraint.V2,
278 Literal: "equals(" + constraint.V1 + ", " + constraint.V2 + "): " + constraint.V2 + "==" + constraint.V1 + " * 1",
279 }
280 circuits[currCircuit].Constraints = append(circuits[currCircuit].Constraints, *constr2)
281 continue
282 }
283 if constraint.Literal == "return" {
284 currCircuit = ""
285 continue
286 }
287 if constraint.Literal == "call" {
288 callsCountStr := strconv.Itoa(callsCount)
289 // for each of the constraints of the called circuit
290 // add it into the current circuit
291 signalMap := make(map[string]string)
292 for i, s := range constraint.PrivateInputs {
293 // signalMap[s] = circuits[constraint.Op].Constraints[0].PrivateInputs[i]
294 signalMap[circuits[constraint.Op].Constraints[0].PrivateInputs[i]+callsCountStr] = s
295 }
296 // add out to map
297 signalMap[circuits[constraint.Op].Constraints[len(circuits[constraint.Op].Constraints)-1].Out+callsCountStr] = constraint.Out
298
299 for i := 1; i < len(circuits[constraint.Op].Constraints); i++ {
300 c := circuits[constraint.Op].Constraints[i]
301 // add constraint, puting unique names to vars
302 nc := &Constraint{
303 Op: c.Op,
304 V1: subsIfInMap(c.V1+callsCountStr, signalMap),
305 V2: subsIfInMap(c.V2+callsCountStr, signalMap),
306 Out: subsIfInMap(c.Out+callsCountStr, signalMap),
307 Literal: "",
308 }
309 nc.Literal = nc.Out + "=" + nc.V1 + nc.Op + nc.V2
310 circuits[currCircuit].Constraints = append(circuits[currCircuit].Constraints, *nc)
311 }
312 for _, s := range circuits[constraint.Op].Signals {
313 circuits[currCircuit].Signals = addToArrayIfNotExist(circuits[currCircuit].Signals, subsIfInMap(s+callsCountStr, signalMap))
314 }
315 callsCount++
316 continue
317
318 }
319 if constraint.Literal == "import" {
320 circuitFile, err := os.Open(constraint.Out)
321 if err != nil {
322 panic(errors.New("imported path error: " + constraint.Out))
323 }
324 parser := NewParser(bufio.NewReader(circuitFile))
325 _, err = parser.Parse() // this will add the imported file funcs into the `circuits` map
326 continue
327 }
328
329 circuits[currCircuit].Constraints = append(circuits[currCircuit].Constraints, *constraint)
330 isVal, _ := isValue(constraint.V1)
331 if !isVal {
332 circuits[currCircuit].Signals = addToArrayIfNotExist(circuits[currCircuit].Signals, constraint.V1)
333 }
334 isVal, _ = isValue(constraint.V2)
335 if !isVal {
336 circuits[currCircuit].Signals = addToArrayIfNotExist(circuits[currCircuit].Signals, constraint.V2)
337 }
338
339 circuits[currCircuit].Signals = addToArrayIfNotExist(circuits[currCircuit].Signals, constraint.Out)
340 }
341 circuits["main"].NVars = len(circuits["main"].Signals)
342 circuits["main"].NSignals = len(circuits["main"].Signals)
343 if mainExist == false {
344 return circuits["main"], errors.New("No 'main' func declared")
345 }
346 return circuits["main"], nil
347}
348func copyArray(in []string) []string { // tmp
349 var out []string
350 for _, e := range in {
351 out = append(out, e)
352 }
353 return out
354}