1// Copyright 2017 The go-ethereum Authors 2// This file is part of the go-ethereum library. 3// 4// The go-ethereum library is free software: you can redistribute it and/or modify 5// it under the terms of the GNU Lesser General Public License as published by 6// the Free Software Foundation, either version 3 of the License, or 7// (at your option) any later version. 8// 9// The go-ethereum library is distributed in the hope that it will be useful, 10// but WITHOUT ANY WARRANTY; without even the implied warranty of 11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12// GNU Lesser General Public License for more details. 13// 14// You should have received a copy of the GNU Lesser General Public License 15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. 16 17package asm 18 19import ( 20 "fmt" 21 "math/big" 22 "os" 23 "strings" 24 25 "github.com/ethereum/go-ethereum/common/math" 26 "github.com/ethereum/go-ethereum/core/vm" 27) 28 29// Compiler contains information about the parsed source 30// and holds the tokens for the program. 31type Compiler struct { 32 tokens []token 33 binary []interface{} 34 35 labels map[string]int 36 37 pc, pos int 38 39 debug bool 40} 41 42// newCompiler returns a new allocated compiler. 43func NewCompiler(debug bool) *Compiler { 44 return &Compiler{ 45 labels: make(map[string]int), 46 debug: debug, 47 } 48} 49 50// Feed feeds tokens in to ch and are interpreted by 51// the compiler. 52// 53// feed is the first pass in the compile stage as it 54// collects the used labels in the program and keeps a 55// program counter which is used to determine the locations 56// of the jump dests. The labels can than be used in the 57// second stage to push labels and determine the right 58// position. 59func (c *Compiler) Feed(ch <-chan token) { 60 var prev token 61 for i := range ch { 62 switch i.typ { 63 case number: 64 num := math.MustParseBig256(i.text).Bytes() 65 if len(num) == 0 { 66 num = []byte{0} 67 } 68 c.pc += len(num) 69 case stringValue: 70 c.pc += len(i.text) - 2 71 case element: 72 c.pc++ 73 case labelDef: 74 c.labels[i.text] = c.pc 75 c.pc++ 76 case label: 77 c.pc += 4 78 if prev.typ == element && isJump(prev.text) { 79 c.pc++ 80 } 81 } 82 83 c.tokens = append(c.tokens, i) 84 prev = i 85 } 86 if c.debug { 87 fmt.Fprintln(os.Stderr, "found", len(c.labels), "labels") 88 } 89} 90 91// Compile compiles the current tokens and returns a 92// binary string that can be interpreted by the EVM 93// and an error if it failed. 94// 95// compile is the second stage in the compile phase 96// which compiles the tokens to EVM instructions. 97func (c *Compiler) Compile() (string, []error) { 98 var errors []error 99 // continue looping over the tokens until 100 // the stack has been exhausted. 101 for c.pos < len(c.tokens) { 102 if err := c.compileLine(); err != nil { 103 errors = append(errors, err) 104 } 105 } 106 107 // turn the binary to hex 108 var bin string 109 for _, v := range c.binary { 110 switch v := v.(type) { 111 case vm.OpCode: 112 bin += fmt.Sprintf("%x", []byte{byte(v)}) 113 case []byte: 114 bin += fmt.Sprintf("%x", v) 115 } 116 } 117 return bin, errors 118} 119 120// next returns the next token and increments the 121// position. 122func (c *Compiler) next() token { 123 token := c.tokens[c.pos] 124 c.pos++ 125 return token 126} 127 128// compileLine compiles a single line instruction e.g. 129// "push 1", "jump @label". 130func (c *Compiler) compileLine() error { 131 n := c.next() 132 if n.typ != lineStart { 133 return compileErr(n, n.typ.String(), lineStart.String()) 134 } 135 136 lvalue := c.next() 137 switch lvalue.typ { 138 case eof: 139 return nil 140 case element: 141 if err := c.compileElement(lvalue); err != nil { 142 return err 143 } 144 case labelDef: 145 c.compileLabel() 146 case lineEnd: 147 return nil 148 default: 149 return compileErr(lvalue, lvalue.text, fmt.Sprintf("%v or %v", labelDef, element)) 150 } 151 152 if n := c.next(); n.typ != lineEnd { 153 return compileErr(n, n.text, lineEnd.String()) 154 } 155 156 return nil 157} 158 159// compileNumber compiles the number to bytes 160func (c *Compiler) compileNumber(element token) (int, error) { 161 num := math.MustParseBig256(element.text).Bytes() 162 if len(num) == 0 { 163 num = []byte{0} 164 } 165 c.pushBin(num) 166 return len(num), nil 167} 168 169// compileElement compiles the element (push & label or both) 170// to a binary representation and may error if incorrect statements 171// where fed. 172func (c *Compiler) compileElement(element token) error { 173 // check for a jump. jumps must be read and compiled 174 // from right to left. 175 if isJump(element.text) { 176 rvalue := c.next() 177 switch rvalue.typ { 178 case number: 179 // TODO figure out how to return the error properly 180 c.compileNumber(rvalue) 181 case stringValue: 182 // strings are quoted, remove them. 183 c.pushBin(rvalue.text[1 : len(rvalue.text)-2]) 184 case label: 185 c.pushBin(vm.PUSH4) 186 pos := big.NewInt(int64(c.labels[rvalue.text])).Bytes() 187 pos = append(make([]byte, 4-len(pos)), pos...) 188 c.pushBin(pos) 189 case lineEnd: 190 c.pos-- 191 default: 192 return compileErr(rvalue, rvalue.text, "number, string or label") 193 } 194 // push the operation 195 c.pushBin(toBinary(element.text)) 196 return nil 197 } else if isPush(element.text) { 198 // handle pushes. pushes are read from left to right. 199 var value []byte 200 201 rvalue := c.next() 202 switch rvalue.typ { 203 case number: 204 value = math.MustParseBig256(rvalue.text).Bytes() 205 if len(value) == 0 { 206 value = []byte{0} 207 } 208 case stringValue: 209 value = []byte(rvalue.text[1 : len(rvalue.text)-1]) 210 case label: 211 value = big.NewInt(int64(c.labels[rvalue.text])).Bytes() 212 value = append(make([]byte, 4-len(value)), value...) 213 default: 214 return compileErr(rvalue, rvalue.text, "number, string or label") 215 } 216 217 if len(value) > 32 { 218 return fmt.Errorf("%d type error: unsupported string or number with size > 32", rvalue.lineno) 219 } 220 221 c.pushBin(vm.OpCode(int(vm.PUSH1) - 1 + len(value))) 222 c.pushBin(value) 223 } else { 224 c.pushBin(toBinary(element.text)) 225 } 226 227 return nil 228} 229 230// compileLabel pushes a jumpdest to the binary slice. 231func (c *Compiler) compileLabel() { 232 c.pushBin(vm.JUMPDEST) 233} 234 235// pushBin pushes the value v to the binary stack. 236func (c *Compiler) pushBin(v interface{}) { 237 if c.debug { 238 fmt.Printf("%d: %v\n", len(c.binary), v) 239 } 240 c.binary = append(c.binary, v) 241} 242 243// isPush returns whether the string op is either any of 244// push(N). 245func isPush(op string) bool { 246 return strings.ToUpper(op) == "PUSH" 247} 248 249// isJump returns whether the string op is jump(i) 250func isJump(op string) bool { 251 return strings.ToUpper(op) == "JUMPI" || strings.ToUpper(op) == "JUMP" 252} 253 254// toBinary converts text to a vm.OpCode 255func toBinary(text string) vm.OpCode { 256 return vm.StringToOp(strings.ToUpper(text)) 257} 258 259type compileError struct { 260 got string 261 want string 262 263 lineno int 264} 265 266func (err compileError) Error() string { 267 return fmt.Sprintf("%d syntax error: unexpected %v, expected %v", err.lineno, err.got, err.want) 268} 269 270func compileErr(c token, got, want string) error { 271 return compileError{ 272 got: got, 273 want: want, 274 lineno: c.lineno, 275 } 276} 277