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