1// Copyright 2013 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package types_test
6
7import (
8	"bytes"
9	"flag"
10	"fmt"
11	"go/ast"
12	"go/importer"
13	"go/parser"
14	"go/token"
15	"io/ioutil"
16	"testing"
17
18	. "go/types"
19)
20
21var (
22	H   = flag.Int("H", 5, "Hilbert matrix size")
23	out = flag.String("out", "", "write generated program to out")
24)
25
26func TestHilbert(t *testing.T) {
27	t.Skip("skipping for gccgo--no importer")
28
29	// generate source
30	src := program(*H, *out)
31	if *out != "" {
32		ioutil.WriteFile(*out, src, 0666)
33		return
34	}
35
36	// parse source
37	fset := token.NewFileSet()
38	f, err := parser.ParseFile(fset, "hilbert.go", src, 0)
39	if err != nil {
40		t.Fatal(err)
41	}
42
43	// type-check file
44	DefPredeclaredTestFuncs() // define assert built-in
45	conf := Config{Importer: importer.Default()}
46	_, err = conf.Check(f.Name.Name, fset, []*ast.File{f}, nil)
47	if err != nil {
48		t.Fatal(err)
49	}
50}
51
52func program(n int, out string) []byte {
53	var g gen
54
55	g.p(`// Code generated by: go test -run=Hilbert -H=%d -out=%q. DO NOT EDIT.
56
57// +`+`build ignore
58
59// This program tests arbitrary precision constant arithmetic
60// by generating the constant elements of a Hilbert matrix H,
61// its inverse I, and the product P = H*I. The product should
62// be the identity matrix.
63package main
64
65func main() {
66	if !ok {
67		printProduct()
68		return
69	}
70	println("PASS")
71}
72
73`, n, out)
74	g.hilbert(n)
75	g.inverse(n)
76	g.product(n)
77	g.verify(n)
78	g.printProduct(n)
79	g.binomials(2*n - 1)
80	g.factorials(2*n - 1)
81
82	return g.Bytes()
83}
84
85type gen struct {
86	bytes.Buffer
87}
88
89func (g *gen) p(format string, args ...interface{}) {
90	fmt.Fprintf(&g.Buffer, format, args...)
91}
92
93func (g *gen) hilbert(n int) {
94	g.p(`// Hilbert matrix, n = %d
95const (
96`, n)
97	for i := 0; i < n; i++ {
98		g.p("\t")
99		for j := 0; j < n; j++ {
100			if j > 0 {
101				g.p(", ")
102			}
103			g.p("h%d_%d", i, j)
104		}
105		if i == 0 {
106			g.p(" = ")
107			for j := 0; j < n; j++ {
108				if j > 0 {
109					g.p(", ")
110				}
111				g.p("1.0/(iota + %d)", j+1)
112			}
113		}
114		g.p("\n")
115	}
116	g.p(")\n\n")
117}
118
119func (g *gen) inverse(n int) {
120	g.p(`// Inverse Hilbert matrix
121const (
122`)
123	for i := 0; i < n; i++ {
124		for j := 0; j < n; j++ {
125			s := "+"
126			if (i+j)&1 != 0 {
127				s = "-"
128			}
129			g.p("\ti%d_%d = %s%d * b%d_%d * b%d_%d * b%d_%d * b%d_%d\n",
130				i, j, s, i+j+1, n+i, n-j-1, n+j, n-i-1, i+j, i, i+j, i)
131		}
132		g.p("\n")
133	}
134	g.p(")\n\n")
135}
136
137func (g *gen) product(n int) {
138	g.p(`// Product matrix
139const (
140`)
141	for i := 0; i < n; i++ {
142		for j := 0; j < n; j++ {
143			g.p("\tp%d_%d = ", i, j)
144			for k := 0; k < n; k++ {
145				if k > 0 {
146					g.p(" + ")
147				}
148				g.p("h%d_%d*i%d_%d", i, k, k, j)
149			}
150			g.p("\n")
151		}
152		g.p("\n")
153	}
154	g.p(")\n\n")
155}
156
157func (g *gen) verify(n int) {
158	g.p(`// Verify that product is the identity matrix
159const ok =
160`)
161	for i := 0; i < n; i++ {
162		for j := 0; j < n; j++ {
163			if j == 0 {
164				g.p("\t")
165			} else {
166				g.p(" && ")
167			}
168			v := 0
169			if i == j {
170				v = 1
171			}
172			g.p("p%d_%d == %d", i, j, v)
173		}
174		g.p(" &&\n")
175	}
176	g.p("\ttrue\n\n")
177
178	// verify ok at type-check time
179	if *out == "" {
180		g.p("const _ = assert(ok)\n\n")
181	}
182}
183
184func (g *gen) printProduct(n int) {
185	g.p("func printProduct() {\n")
186	for i := 0; i < n; i++ {
187		g.p("\tprintln(")
188		for j := 0; j < n; j++ {
189			if j > 0 {
190				g.p(", ")
191			}
192			g.p("p%d_%d", i, j)
193		}
194		g.p(")\n")
195	}
196	g.p("}\n\n")
197}
198
199func (g *gen) binomials(n int) {
200	g.p(`// Binomials
201const (
202`)
203	for j := 0; j <= n; j++ {
204		if j > 0 {
205			g.p("\n")
206		}
207		for k := 0; k <= j; k++ {
208			g.p("\tb%d_%d = f%d / (f%d*f%d)\n", j, k, j, k, j-k)
209		}
210	}
211	g.p(")\n\n")
212}
213
214func (g *gen) factorials(n int) {
215	g.p(`// Factorials
216const (
217	f0 = 1
218	f1 = 1
219`)
220	for i := 2; i <= n; i++ {
221		g.p("\tf%d = f%d * %d\n", i, i-1, i)
222	}
223	g.p(")\n\n")
224}
225