1package main
2
3/*
4Large uncovered parts are:
5- methods
6- type assignability and identity
7- consts
8- interfaces, types implementing interfaces, type assertions
9- ... parameters
10*/
11
12import (
13	"bufio"
14	"fmt"
15	"math/rand"
16	"os"
17	"path/filepath"
18	"strings"
19)
20
21type Smith struct {
22	curPackage  int
23	curBlock    *Block
24	curBlockPos int
25	curFunc     *Func
26
27	packages [NPackages]*Package
28
29	idSeq          int
30	typeDepth      int
31	stmtCount      int
32	exprDepth      int
33	exprCount      int
34	totalExprCount int
35
36	predefinedTypes []*Type
37	stringType      *Type
38	boolType        *Type
39	intType         *Type
40	byteType        *Type
41	efaceType       *Type
42	runeType        *Type
43	float32Type     *Type
44	float64Type     *Type
45	complex64Type   *Type
46	complex128Type  *Type
47
48	statements  []func()
49	expressions []func(res *Type) string
50
51	rng *rand.Rand
52}
53
54const (
55	NPackages = 3
56	NFiles    = 3
57
58	NStatements     = 10
59	NExprDepth      = 4
60	NExprCount      = 10
61	NTotalExprCount = 50
62
63/*
64	NStatements     = 30
65	NExprDepth      = 6
66	NExprCount      = 20
67	NTotalExprCount = 1000
68*/
69)
70
71type Package struct {
72	name    string
73	imports map[string]bool
74	top     *Block
75
76	undefFuncs []*Func
77	undefVars  []*Var
78
79	toplevVars  []*Var
80	toplevFuncs []*Func
81}
82
83type Block struct {
84	str           string
85	parent        *Block
86	subBlock      *Block
87	extendable    bool
88	isBreakable   bool
89	isContinuable bool
90	funcBoundary  bool
91	sub           []*Block
92	consts        []*Const
93	types         []*Type
94	funcs         []*Func
95	vars          []*Var
96}
97
98type Func struct {
99	name string
100	args []*Type
101	rets []*Type
102}
103
104type Var struct {
105	id    string
106	typ   *Type
107	block *Block
108	used  bool
109}
110
111type Const struct {
112}
113
114func (smith *Smith) writeProgram(dir string) {
115	smith.initTypes()
116	smith.initExpressions()
117	smith.initStatements()
118	smith.initProgram()
119	for pi := range smith.packages {
120		smith.genPackage(pi)
121	}
122	smith.serializeProgram(dir)
123}
124
125func (smith *Smith) initProgram() {
126	smith.packages[0] = smith.newPackage("main")
127	smith.packages[0].undefFuncs = []*Func{
128		{name: "init", args: []*Type{}, rets: []*Type{}},
129		{name: "init", args: []*Type{}, rets: []*Type{}},
130		{name: "main", args: []*Type{}, rets: []*Type{}},
131	}
132	if !*singlepkg {
133		smith.packages[1] = smith.newPackage("a")
134		smith.packages[2] = smith.newPackage("b")
135	}
136}
137
138func (smith *Smith) newPackage(name string) *Package {
139	return &Package{name: name, imports: make(map[string]bool), top: &Block{extendable: true}}
140}
141
142func (smith *Smith) genPackage(pi int) {
143	smith.typeDepth = 0
144	smith.stmtCount = 0
145	smith.exprDepth = 0
146	smith.exprCount = 0
147	smith.totalExprCount = 0
148
149	p := smith.packages[pi]
150	if p == nil {
151		return
152	}
153	for len(p.undefFuncs) != 0 || len(p.undefVars) != 0 {
154		if len(p.undefFuncs) != 0 {
155			f := p.undefFuncs[len(p.undefFuncs)-1]
156			p.undefFuncs = p.undefFuncs[:len(p.undefFuncs)-1]
157			smith.genToplevFunction(pi, f)
158		}
159		if len(p.undefVars) != 0 {
160			v := p.undefVars[len(p.undefVars)-1]
161			p.undefVars = p.undefVars[:len(p.undefVars)-1]
162			smith.genToplevVar(pi, v)
163		}
164	}
165}
166
167func F(f string, args ...interface{}) string {
168	return fmt.Sprintf(f, args...)
169}
170
171func (smith *Smith) line(f string, args ...interface{}) {
172	s := F(f, args...)
173	b := &Block{parent: smith.curBlock, str: s}
174	if smith.curBlockPos+1 == len(smith.curBlock.sub) {
175		smith.curBlock.sub = append(smith.curBlock.sub, b)
176	} else {
177		smith.curBlock.sub = append(smith.curBlock.sub, nil)
178		copy(smith.curBlock.sub[smith.curBlockPos+2:], smith.curBlock.sub[smith.curBlockPos+1:])
179		smith.curBlock.sub[smith.curBlockPos+1] = b
180	}
181	smith.curBlockPos++
182}
183
184func (smith *Smith) resetContext(pi int) {
185	smith.curPackage = pi
186	p := smith.packages[pi]
187	smith.curBlock = p.top
188	smith.curBlockPos = len(smith.curBlock.sub) - 1
189	smith.curFunc = nil
190}
191
192func (smith *Smith) genToplevFunction(pi int, f *Func) {
193	smith.resetContext(pi)
194	smith.curFunc = f
195	smith.enterBlock(true)
196	smith.enterBlock(true)
197	argIds := make([]string, len(f.args))
198	argStr := ""
199	for i, a := range f.args {
200		argIds[i] = smith.newId("Param")
201		if i != 0 {
202			argStr += ", "
203		}
204		argStr += argIds[i] + " " + a.id
205	}
206	smith.line("func %v(%v)%v {", f.name, argStr, fmtTypeList(f.rets, false))
207	for i, a := range f.args {
208		smith.defineVar(argIds[i], a)
209	}
210	smith.curBlock.funcBoundary = true
211	smith.genBlock()
212	smith.leaveBlock()
213	smith.stmtReturn()
214	smith.line("}")
215	smith.leaveBlock()
216	if f.name != "init" {
217		smith.packages[smith.curPackage].toplevFuncs = append(smith.packages[smith.curPackage].toplevFuncs, f)
218	}
219}
220
221func (smith *Smith) genToplevVar(pi int, v *Var) {
222	smith.resetContext(pi)
223	smith.enterBlock(true)
224	smith.line("var %v = %v", v.id, smith.rvalue(v.typ))
225	smith.leaveBlock()
226	smith.packages[smith.curPackage].toplevVars = append(smith.packages[smith.curPackage].toplevVars, v)
227}
228
229func (smith *Smith) genBlock() {
230	smith.enterBlock(false)
231	for smith.rnd(10) != 0 {
232		smith.genStatement()
233	}
234	smith.leaveBlock()
235}
236
237func (smith *Smith) serializeProgram(dir string) {
238	for _, p := range smith.packages {
239		if p == nil {
240			continue
241		}
242		path := filepath.Join(dir, "src", p.name)
243		os.MkdirAll(path, os.ModePerm)
244		nf := NFiles
245		if *singlefile {
246			nf = 1
247		}
248		files := make([]*bufio.Writer, nf)
249		for i := range files {
250			fname := filepath.Join(path, fmt.Sprintf("%v.go", i))
251			f, err := os.Create(fname)
252			if err != nil {
253				fmt.Fprintf(os.Stdout, "failed to create a file: %v\n", err)
254				os.Exit(1)
255			}
256			w := bufio.NewWriter(bufio.NewWriter(f))
257			files[i] = w
258			defer func() {
259				w.Flush()
260				f.Close()
261			}()
262			fmt.Fprintf(w, "package %s\n", p.name)
263			for imp := range p.imports {
264				fmt.Fprintf(w, "import \"%s\"\n", imp)
265			}
266			if i == 0 && p.name == "main" {
267				fmt.Fprintf(w, "import \"runtime\"\n")
268				fmt.Fprintf(w, "func init() {\n")
269				fmt.Fprintf(w, "	go func() {\n")
270				fmt.Fprintf(w, "		for {\n")
271				fmt.Fprintf(w, "			runtime.GC()\n")
272				fmt.Fprintf(w, "			runtime.Gosched()\n")
273				fmt.Fprintf(w, "		}\n")
274				fmt.Fprintf(w, "	}()\n")
275				fmt.Fprintf(w, "}\n")
276			}
277			for imp := range p.imports {
278				fmt.Fprintf(w, "var _ = %s.UsePackage\n", imp)
279			}
280			if i == 0 {
281				fmt.Fprintf(w, "var UsePackage = 0\n")
282				fmt.Fprintf(w, "var SINK interface{}\n")
283			}
284		}
285		for _, decl := range p.top.sub {
286			serializeBlock(files[smith.rnd(len(files))], decl, 0)
287		}
288	}
289
290	path := filepath.Join(dir, "src", "a")
291	os.MkdirAll(path, os.ModePerm)
292	fname := filepath.Join(path, "0_test.go")
293	f, err := os.Create(fname)
294	if err != nil {
295		fmt.Fprintf(os.Stdout, "failed to create a file: %v\n", err)
296		os.Exit(1)
297	}
298	f.Write([]byte("package a\n"))
299	f.Close()
300}
301
302func serializeBlock(w *bufio.Writer, b *Block, d int) {
303	if true {
304		if b.str != "" {
305			w.WriteString(b.str)
306			w.WriteString("\n")
307		}
308	} else {
309		w.WriteString("/*" + strings.Repeat("*", d) + "*/ ")
310		w.WriteString(b.str)
311		w.WriteString(F(" // ext=%v vars=%v types=%v", b.extendable, len(b.vars), len(b.types)))
312		w.WriteString("\n")
313	}
314	for _, b1 := range b.sub {
315		serializeBlock(w, b1, d+1)
316	}
317}
318
319func (smith *Smith) vars() []*Var {
320	var vars []*Var
321	vars = append(vars, smith.packages[smith.curPackage].toplevVars...)
322	var f func(b *Block, pos int)
323	f = func(b *Block, pos int) {
324		for _, b1 := range b.sub[:pos+1] {
325			vars = append(vars, b1.vars...)
326		}
327		if b.parent != nil {
328			pos := len(b.parent.sub) - 1
329			if b.subBlock != nil {
330				pos = -2
331				for i, b1 := range b.parent.sub {
332					if b1 == b.subBlock {
333						pos = i
334						break
335					}
336				}
337				if pos == -2 {
338					panic("bad")
339				}
340			}
341			f(b.parent, pos)
342		}
343	}
344	f(smith.curBlock, smith.curBlockPos)
345	return vars
346}
347
348func (smith *Smith) types() []*Type {
349	var types []*Type
350	types = append(types, smith.predefinedTypes...)
351	var f func(b *Block, pos int)
352	f = func(b *Block, pos int) {
353		for _, b1 := range b.sub[:pos+1] {
354			types = append(types, b1.types...)
355		}
356		if b.parent != nil {
357			pos := len(b.parent.sub) - 1
358			if b.subBlock != nil {
359				pos = -2
360				for i, b1 := range b.parent.sub {
361					if b1 == b.subBlock {
362						pos = i
363						break
364					}
365				}
366				if pos == -2 {
367					panic("bad")
368				}
369			}
370			f(b.parent, pos)
371		}
372	}
373	f(smith.curBlock, smith.curBlockPos)
374	return types
375}
376
377func (smith *Smith) defineVar(id string, t *Type) {
378	v := &Var{id: id, typ: t, block: smith.curBlock}
379	b := smith.curBlock.sub[smith.curBlockPos]
380	b.vars = append(b.vars, v)
381}
382
383func (smith *Smith) defineType(t *Type) {
384	b := smith.curBlock.sub[smith.curBlockPos]
385	b.types = append(b.types, t)
386}
387
388func (smith *Smith) materializeVar(t *Type) string {
389	// TODO: generate var in another package
390	id := smith.newId("Var")
391	curBlock0 := smith.curBlock
392	curBlockPos0 := smith.curBlockPos
393	curBlockLen0 := len(smith.curBlock.sub)
394	exprDepth0 := smith.exprDepth
395	exprCount0 := smith.exprCount
396	smith.exprDepth = 0
397	smith.exprCount = 0
398	defer func() {
399		if smith.curBlock == curBlock0 {
400			curBlockPos0 += len(smith.curBlock.sub) - curBlockLen0
401		}
402		smith.curBlock = curBlock0
403		smith.curBlockPos = curBlockPos0
404		smith.exprDepth = exprDepth0
405		smith.exprCount = exprCount0
406	}()
407loop:
408	for {
409		if smith.curBlock.parent == nil {
410			break
411		}
412		if !smith.curBlock.extendable || smith.curBlockPos < 0 {
413			if smith.curBlock.subBlock == nil {
414				smith.curBlockPos = len(smith.curBlock.parent.sub) - 2
415			} else {
416				smith.curBlockPos = -2
417				for i, b1 := range smith.curBlock.parent.sub {
418					if b1 == smith.curBlock.subBlock {
419						smith.curBlockPos = i
420						break
421					}
422				}
423				if smith.curBlockPos == -2 {
424					panic("bad")
425				}
426			}
427			smith.curBlock = smith.curBlock.parent
428			continue
429		}
430		if smith.rnd(3) == 0 {
431			break
432		}
433		if smith.curBlockPos >= 0 {
434			b := smith.curBlock.sub[smith.curBlockPos]
435			for _, t1 := range b.types {
436				if dependsOn(t, t1) {
437					break loop
438				}
439			}
440		}
441		smith.curBlockPos--
442	}
443	if smith.curBlock.parent == nil {
444		for i := smith.curPackage; i < NPackages; i++ {
445			if smith.rndBool() || i == NPackages-1 || *singlepkg {
446				if i == smith.curPackage {
447					// emit global var into the current package
448					smith.enterBlock(true)
449					smith.line("var %v = %v", id, smith.rvalue(t))
450					smith.packages[smith.curPackage].toplevVars = append(smith.packages[smith.curPackage].toplevVars, &Var{id: id, typ: t})
451					smith.leaveBlock()
452				} else {
453					// emit global var into another package
454					smith.packages[i].undefVars = append(smith.packages[i].undefVars, &Var{id: id, typ: t})
455					smith.packages[smith.curPackage].imports[smith.packages[i].name] = true
456					id = smith.packages[i].name + "." + id
457				}
458				break
459			}
460		}
461	} else {
462		// emit local var
463		smith.line("%v := %v", id, smith.rvalue(t))
464		smith.defineVar(id, t)
465	}
466	return id
467}
468
469func (smith *Smith) materializeFunc(rets []*Type) *Func {
470	f := &Func{name: smith.newId("Func"), args: smith.atypeList(TraitGlobal), rets: rets}
471
472	curBlock0 := smith.curBlock
473	curBlockPos0 := smith.curBlockPos
474	curFunc0 := smith.curFunc
475	exprDepth0 := smith.exprDepth
476	exprCount0 := smith.exprCount
477	smith.exprDepth = 0
478	smith.exprCount = 0
479	defer func() {
480		smith.curBlock = curBlock0
481		smith.curBlockPos = curBlockPos0
482		smith.curFunc = curFunc0
483		smith.exprDepth = exprDepth0
484		smith.exprCount = exprCount0
485	}()
486
487	if smith.rndBool() && !*singlepkg && smith.curPackage != NPackages-1 {
488		for _, r1 := range rets {
489			if dependsOn(r1, nil) {
490				goto thisPackage
491			}
492		}
493		for _, t := range f.args {
494			if dependsOn(t, nil) {
495				goto thisPackage
496			}
497		}
498		// emit global var into another package
499		newF := new(Func)
500		*newF = *f
501		smith.packages[smith.curPackage+1].undefFuncs = append(smith.packages[smith.curPackage+1].undefFuncs, newF)
502		smith.packages[smith.curPackage].imports[smith.packages[smith.curPackage+1].name] = true
503		f.name = smith.packages[smith.curPackage+1].name + "." + f.name
504		return f
505	}
506thisPackage:
507	smith.genToplevFunction(smith.curPackage, f)
508	return f
509}
510
511func (smith *Smith) materializeGotoLabel() string {
512	// TODO: move lavel up
513	id := smith.newId("Label")
514
515	curBlock0 := smith.curBlock
516	curBlockPos0 := smith.curBlockPos
517	curBlockLen0 := len(smith.curBlock.sub)
518	defer func() {
519		if smith.curBlock == curBlock0 {
520			curBlockPos0 += len(smith.curBlock.sub) - curBlockLen0
521		}
522		smith.curBlock = curBlock0
523		smith.curBlockPos = curBlockPos0
524	}()
525
526	for {
527		if smith.curBlock.parent.funcBoundary && smith.curBlockPos <= 0 {
528			break
529		}
530		if !smith.curBlock.extendable || smith.curBlockPos < 0 {
531			if smith.curBlock.subBlock != nil {
532				// we should have been stopped at func boundary
533				panic("bad")
534			}
535			smith.curBlock = smith.curBlock.parent
536			smith.curBlockPos = len(smith.curBlock.sub) - 2
537			continue
538		}
539		if smith.rnd(3) == 0 {
540			break
541		}
542		smith.curBlockPos--
543	}
544
545	smith.line("%v:", id)
546	return id
547}
548
549func (smith *Smith) rnd(n int) int {
550	return smith.rng.Intn(n)
551}
552
553func (smith *Smith) rndBool() bool {
554	return smith.rnd(2) == 0
555}
556
557func (smith *Smith) choice(ch ...string) string {
558	return ch[smith.rnd(len(ch))]
559}
560
561func (smith *Smith) newId(prefix string) string {
562	if prefix[0] < 'A' || prefix[0] > 'Z' {
563		panic("unexported id")
564	}
565	smith.idSeq++
566	return fmt.Sprintf("%v%v", prefix, smith.idSeq)
567}
568
569func (smith *Smith) enterBlock(nonextendable bool) {
570	b := &Block{parent: smith.curBlock, extendable: !nonextendable}
571	b.isBreakable = smith.curBlock.isBreakable
572	b.isContinuable = smith.curBlock.isContinuable
573	smith.curBlock.sub = append(smith.curBlock.sub, b)
574	smith.curBlock = b
575	smith.curBlockPos = -1
576}
577
578func (smith *Smith) leaveBlock() {
579	for _, b := range smith.curBlock.sub {
580		for _, v := range b.vars {
581			if !v.used {
582				smith.line("_ = %v", v.id)
583			}
584		}
585	}
586
587	smith.curBlock = smith.curBlock.parent
588	smith.curBlockPos = len(smith.curBlock.sub) - 1
589}
590