1/* 2 * gomacro - A Go interpreter with Lisp-like macros 3 * 4 * Copyright (C) 2018-2019 Massimiliano Ghilardi 5 * 6 * This Source Code Form is subject to the terms of the Mozilla Public 7 * License, v. 2.0. If a copy of the MPL was not distributed with this 8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 9 * 10 * 11 * template_maker.go 12 * 13 * Created on Jun 16, 2018 14 * Author Massimiliano Ghilardi 15 */ 16 17package fast 18 19import ( 20 "bytes" 21 "fmt" 22 "go/ast" 23 "go/token" 24 r "reflect" 25 "sort" 26 "strings" 27 28 "github.com/cosmos72/gomacro/ast2" 29 "github.com/cosmos72/gomacro/base" 30 31 "github.com/cosmos72/gomacro/parser" 32 xr "github.com/cosmos72/gomacro/xreflect" 33) 34 35// set to false to disable compiling gomacro generics, version 1 36const GENERICS_V1 = parser.GENERICS_V1 37 38type templateMaker struct { 39 comp *Comp 40 sym *Symbol 41 ifun I 42 exprs []ast.Expr 43 vals []I 44 types []xr.Type 45 ikey I 46 name string 47 pos token.Pos 48} 49 50type templateTypeCandidate struct { 51 decl TemplateTypeDecl 52 params []string 53 vals []I 54 types []xr.Type 55} 56 57type templateFuncCandidate struct { 58 decl TemplateFuncDecl 59 vals []I 60 types []xr.Type 61} 62 63func (special *templateFuncCandidate) injectBinds(c *Comp) { 64 for i, name := range special.decl.Params { 65 t := special.types[i] 66 if val := special.vals[i]; val != nil { 67 c.DeclConst0(name, t, val) 68 } else { 69 c.declTypeAlias(name, t) 70 } 71 } 72} 73 74func (special *templateTypeCandidate) injectBinds(c *Comp) { 75 for i, name := range special.decl.Params { 76 t := special.types[i] 77 if val := special.vals[i]; val != nil { 78 c.DeclConst0(name, t, val) 79 } else { 80 c.declTypeAlias(name, t) 81 } 82 } 83} 84 85// return the qualified name of the function or type to instantiate, for example "Pair#[int,string]" 86func (maker *templateMaker) String() string { 87 if len(maker.name) != 0 { 88 return maker.name 89 } 90 var buf bytes.Buffer 91 buf.WriteString(maker.sym.Name) 92 buf.WriteString("#[") 93 94 for i, val := range maker.vals { 95 if i != 0 { 96 buf.WriteByte(',') 97 } 98 if val == nil { 99 val = maker.types[i].ReflectType() 100 } 101 fmt.Fprint(&buf, val) 102 } 103 buf.WriteByte(']') 104 maker.name = buf.String() 105 return maker.name 106} 107 108func (c *Comp) templateMaker(node *ast.IndexExpr, which BindClass) *templateMaker { 109 name, templateArgs, ok := splitTemplateArgs(node) 110 if !ok { 111 return nil 112 } 113 sym, upc := c.tryResolve(name) 114 if sym == nil { 115 c.Errorf("undefined identifier: %v", name) 116 } 117 n := len(templateArgs) 118 var params []string 119 ifun := sym.Value 120 ok = false 121 if ifun != nil && sym.Desc.Class() == which { 122 switch which { 123 case TemplateFuncBind: 124 fun, _ := ifun.(*TemplateFunc) 125 ok = fun != nil 126 if ok { 127 params = fun.Master.Params 128 } 129 case TemplateTypeBind: 130 typ, _ := ifun.(*TemplateType) 131 ok = typ != nil 132 if ok { 133 params = typ.Master.Params 134 } 135 } 136 } 137 if !ok { 138 c.Errorf("symbol is not a %v, cannot use #[...] on it: %s", which, name) 139 } 140 if n != len(params) { 141 c.Errorf("%v expects exactly %d template parameters %v, found %d: %v", which, len(params), params, n, node) 142 } 143 vals := make([]I, n) 144 types := make([]xr.Type, n) 145 146 // make a copy of templateArgs, then replace constant expressions with their values 147 templateArgs = append([]ast.Expr(nil), templateArgs...) 148 149 for i, templateArg := range templateArgs { 150 e, t := c.Expr1OrType(templateArg) 151 if e != nil { 152 if !e.Const() { 153 c.Errorf("argument of template function %q is not a constant: %v", name, templateArg) 154 } 155 // UntypedLit is unsuitable as map key, because its == is not usable 156 vals[i] = e.EvalConst(COptDefaults) 157 types[i] = e.Type // also remember the type 158 templateArgs[i] = c.constToAstExpr(vals[i], templateArg.Pos()) 159 } else { 160 types[i] = t 161 } 162 } 163 return &templateMaker{upc, sym, ifun, templateArgs, vals, types, makeTemplateKey(vals, types), "", node.Pos()} 164} 165 166func makeTemplateKey(vals []I, types []xr.Type) I { 167 // slices cannot be used as map keys. use an array and reflection 168 key := r.New(r.ArrayOf(len(types), rtypeOfInterface)).Elem() 169 170 for i, t := range types { 171 if val := vals[i]; val == nil { 172 key.Index(i).Set(r.ValueOf(xr.MakeKey(t))) 173 } else { 174 key.Index(i).Set(r.ValueOf(val)) 175 } 176 } 177 return key.Interface() 178} 179 180// convert true to &ast.Ident{Name: "true"}, convert false similarly, 181// convert integers to &ast.BasicLit{Kind: token.INT, Value: fmt.Sprint(val)} 182// convert float32, float64 and strings analogously, 183// convert complex64 and complex128 to &ast.BinaryExpr{X: real(...), Op: token.Add, Y: imag(...)} 184func (c *Comp) constToAstExpr(val interface{}, pos token.Pos) ast.Expr { 185 var kind token.Token 186 var str string 187 v := r.ValueOf(val) 188 switch v.Kind() { 189 case r.Bool: 190 return &ast.Ident{NamePos: pos, Name: fmt.Sprint(val)} 191 case r.Int, r.Int8, r.Int16, r.Int32, r.Int64, 192 r.Uint, r.Uint8, r.Uint16, r.Uint32, r.Uint64, r.Uintptr: 193 kind = token.INT 194 str = fmt.Sprint(val) 195 case r.Float32, r.Float64: 196 kind = token.FLOAT 197 str = fmt.Sprintf("%g", val) 198 case r.Complex64, r.Complex128: 199 return &ast.BinaryExpr{ 200 X: &ast.BasicLit{ 201 Kind: token.FLOAT, 202 Value: fmt.Sprintf("%g", real(v.Complex())), 203 ValuePos: pos, 204 }, 205 Op: token.ADD, 206 Y: &ast.BasicLit{ 207 Kind: token.IMAG, 208 Value: fmt.Sprintf("%g", imag(v.Complex())), 209 }, 210 } 211 case r.String: 212 kind = token.STRING 213 str = fmt.Sprintf("%q", val) 214 default: 215 c.Errorf("unexpected const type, cannot convert to ast.Expr: %v // %T", val, val) 216 } 217 return &ast.BasicLit{ 218 Kind: kind, 219 Value: str, 220 ValuePos: pos, 221 } 222} 223 224func splitTemplateArgs(node *ast.IndexExpr) (string, []ast.Expr, bool) { 225 if ident, _ := node.X.(*ast.Ident); ident != nil { 226 cindex, _ := node.Index.(*ast.CompositeLit) 227 if cindex != nil && cindex.Type == nil { 228 return ident.Name, cindex.Elts, true 229 } 230 } 231 return "", nil, false 232} 233 234func (c *Comp) templateParams(params []ast.Expr, errlabel string, node ast.Node) ([]string, []ast.Expr) { 235 names := make([]string, 0, len(params)) 236 var exprs []ast.Expr 237 for i, param := range params { 238 switch param := param.(type) { 239 case *ast.Ident: 240 names = append(names, param.Name) 241 case *ast.BadExpr: 242 case *ast.CompositeLit: 243 exprs = param.Elts 244 default: 245 c.Errorf("invalid template %s declaration: template parameter %d should be *ast.Ident or *ast.CompositeLit, found %T: %v", 246 errlabel, i, param, node) 247 } 248 } 249 return names, exprs 250} 251 252// return the most specialized function declaration applicable to used params. 253// panics if there is no single most specialized declaration. 254func (maker *templateMaker) chooseFunc(fun *TemplateFunc) (string, *templateFuncCandidate) { 255 candidates := map[string]*templateFuncCandidate{ 256 maker.sym.Name + "#[...]": &templateFuncCandidate{ 257 decl: fun.Master, 258 vals: maker.vals, 259 types: maker.types, 260 }, 261 } 262 g := &maker.comp.Globals 263 debug := g.Options&base.OptDebugTemplate != 0 264 var ok1, ok2 bool 265 266 if debug { 267 g.Debugf("choosing template function for %s from %d specializations", maker.String(), 1+len(fun.Special)) 268 } 269 270 for key, special := range fun.Special { 271 vals, types, ok := maker.patternMatches(special.Params, special.For, maker.exprs) 272 if !ok { 273 continue 274 } 275 // check whether special is more specialized than all other candidates 276 for declKey, candidate := range candidates { 277 decl := candidate.decl 278 if len(decl.For) == 0 { 279 ok1, ok2 = false, true 280 } else { 281 _, _, ok1 = maker.patternMatches(special.Params, special.For, decl.For) 282 _, _, ok2 = maker.patternMatches(decl.Params, decl.For, special.For) 283 } 284 if !ok1 && ok2 { 285 // special is more specialized, remove the other 286 if debug { 287 g.Debugf("template function %s is more specialized than %s, removing the latter", key, declKey) 288 } 289 delete(candidates, declKey) 290 } 291 } 292 if debug { 293 g.Debugf("adding template function specialization %s to candidates", key) 294 } 295 candidates[key] = &templateFuncCandidate{ 296 decl: special, 297 vals: vals, 298 types: types, 299 } 300 } 301 switch n := len(candidates); n { 302 case 1: 303 for key, candidate := range candidates { 304 if debug { 305 g.Debugf("chosen template function specialization: %v", key) 306 } 307 return key, candidate 308 } 309 fallthrough 310 case 0: 311 g.Errorf("no template function specialization matches %v", maker.String()) 312 default: 313 names := make([]string, n) 314 var i int 315 for name := range candidates { 316 names[i] = name 317 i++ 318 } 319 sort.Strings(names) 320 g.Errorf("multiple candidates match template function %v:\n\t%s", maker.String(), strings.Join(names, "\n\t")) 321 } 322 return "", nil 323} 324 325// return the most specialized type declaration applicable to used params. 326// panics if there is no single most specialized declaration. 327func (maker *templateMaker) chooseType(typ *TemplateType) (string, *templateTypeCandidate) { 328 candidates := map[string]*templateTypeCandidate{ 329 maker.sym.Name + "#[...]": &templateTypeCandidate{ 330 decl: typ.Master, 331 vals: maker.vals, 332 types: maker.types, 333 }, 334 } 335 g := &maker.comp.Globals 336 debug := g.Options&base.OptDebugTemplate != 0 337 var ok1, ok2 bool 338 339 if debug { 340 g.Debugf("choosing template type for %s from %d specializations", maker.String(), 1+len(typ.Special)) 341 } 342 343 for key, special := range typ.Special { 344 vals, types, ok := maker.patternMatches(special.Params, special.For, maker.exprs) 345 if !ok { 346 continue 347 } 348 // check whether special is more specialized than all other candidates 349 for declKey, candidate := range candidates { 350 decl := candidate.decl 351 if len(decl.For) == 0 { 352 ok1, ok2 = false, true 353 } else { 354 _, _, ok1 = maker.patternMatches(special.Params, special.For, decl.For) 355 _, _, ok2 = maker.patternMatches(decl.Params, decl.For, special.For) 356 } 357 if !ok1 && ok2 { 358 // special is more specialized, remove the other 359 if debug { 360 g.Debugf("template type %s is more specialized than %s, removing the latter", key, declKey) 361 } 362 delete(candidates, declKey) 363 } 364 } 365 if debug { 366 g.Debugf("adding template type specialization %s to candidates", key) 367 } 368 candidates[key] = &templateTypeCandidate{ 369 decl: special, 370 vals: vals, 371 types: types, 372 } 373 } 374 switch n := len(candidates); n { 375 case 1: 376 for key, candidate := range candidates { 377 if debug { 378 g.Debugf("chosen template type specialization: %v", key) 379 } 380 return key, candidate 381 } 382 fallthrough 383 case 0: 384 g.Errorf("no template type specialization matches %v", maker.String()) 385 default: 386 names := make([]string, n) 387 var i int 388 for name := range candidates { 389 names[i] = name 390 i++ 391 } 392 sort.Strings(names) 393 g.Errorf("multiple candidates match template type %v:\n\t%s", maker.String(), strings.Join(names, "\n\t")) 394 } 395 return "", nil 396} 397 398// if template specialization 'patterns' parametrized on 'names' matches 'exprs', 399// return the constants and types required for the match 400func (maker *templateMaker) patternMatches(names []string, patterns []ast.Expr, exprs []ast.Expr) ([]interface{}, []xr.Type, bool) { 401 vals := make([]interface{}, len(names)) 402 types := make([]xr.Type, len(names)) 403 ok := true 404 405 for i, pattern := range patterns { 406 ok = maker.patternMatch(names, vals, types, ast2.ToAst(pattern), ast2.ToAst(exprs[i])) 407 if !ok { 408 break 409 } 410 } 411 return vals, types, ok 412} 413 414// if template specialization 'pattern1' parametrized on 'names' matches 'expr1', 415// fill 'vals' and 'types' with the constants and types required for the match 416func (maker *templateMaker) patternMatch(names []string, 417 vals []interface{}, types []xr.Type, pattern ast2.Ast, expr ast2.Ast) bool { 418 419 switch node := pattern.Interface().(type) { 420 case *ast.Ident: 421 for i, name := range names { 422 if name == node.Name { 423 return maker.patternMatched(i, vals, types, expr) 424 } 425 } 426 e, ok := expr.Interface().(*ast.Ident) 427 return ok && node.Name == e.Name 428 case *ast.BasicLit: 429 e, ok := expr.Interface().(*ast.BasicLit) 430 return ok && node.Kind == e.Kind && node.Value == e.Value 431 default: 432 if pattern.Op() == expr.Op() && pattern.Size() == expr.Size() { 433 for i, n := 0, pattern.Size(); i < n; i++ { 434 if !maker.patternMatch(names, vals, types, pattern.Get(i), expr.Get(i)) { 435 return false 436 } 437 } 438 return true 439 } 440 return false 441 } 442} 443 444// if template specialization 'pattern1' parametrized on 'names' matches 'expr1', 445// fill 'vals' and 'types' with the constants and types required for the match 446func (maker *templateMaker) patternMatched(i int, vals []interface{}, types []xr.Type, expr ast2.Ast) (ok bool) { 447 expr1, eok := expr.Interface().(ast.Expr) 448 if !eok { 449 return false 450 } 451 panicking := true 452 defer func() { 453 if panicking { 454 recover() 455 ok = false 456 } 457 }() 458 e, typ := maker.comp.Expr1OrType(expr1) 459 panicking = false 460 461 if e != nil { 462 if e.Const() { 463 val := e.EvalConst(COptDefaults) 464 if vals[i] == nil { 465 vals[i] = val 466 ok = true 467 } else { 468 ok = vals[i] == val 469 } 470 } 471 } else if typ != nil { 472 if types[i] == nil { 473 types[i] = typ 474 ok = true 475 } else { 476 ok = typ.IdenticalTo(types[i]) 477 } 478 } 479 return ok 480} 481