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