1// Copyright 2012 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 build
6
7import (
8	"strconv"
9	"testing"
10
11	"golang.org/x/text/internal/colltab"
12)
13
14type entryTest struct {
15	f   func(in []int) (uint32, error)
16	arg []int
17	val uint32
18}
19
20// makeList returns a list of entries of length n+2, with n normal
21// entries plus a leading and trailing anchor.
22func makeList(n int) []*entry {
23	es := make([]*entry, n+2)
24	weights := []rawCE{{w: []int{100, 20, 5, 0}}}
25	for i := range es {
26		runes := []rune{rune(i)}
27		es[i] = &entry{
28			runes: runes,
29			elems: weights,
30		}
31		weights = nextWeight(colltab.Primary, weights)
32	}
33	for i := 1; i < len(es); i++ {
34		es[i-1].next = es[i]
35		es[i].prev = es[i-1]
36		_, es[i-1].level = compareWeights(es[i-1].elems, es[i].elems)
37	}
38	es[0].exclude = true
39	es[0].logical = firstAnchor
40	es[len(es)-1].exclude = true
41	es[len(es)-1].logical = lastAnchor
42	return es
43}
44
45func TestNextIndexed(t *testing.T) {
46	const n = 5
47	es := makeList(n)
48	for i := int64(0); i < 1<<n; i++ {
49		mask := strconv.FormatInt(i+(1<<n), 2)
50		for i, c := range mask {
51			es[i].exclude = c == '1'
52		}
53		e := es[0]
54		for i, c := range mask {
55			if c == '0' {
56				e, _ = e.nextIndexed()
57				if e != es[i] {
58					t.Errorf("%d: expected entry %d; found %d", i, es[i].elems, e.elems)
59				}
60			}
61		}
62		if e, _ = e.nextIndexed(); e != nil {
63			t.Errorf("%d: expected nil entry; found %d", i, e.elems)
64		}
65	}
66}
67
68func TestRemove(t *testing.T) {
69	const n = 5
70	for i := int64(0); i < 1<<n; i++ {
71		es := makeList(n)
72		mask := strconv.FormatInt(i+(1<<n), 2)
73		for i, c := range mask {
74			if c == '0' {
75				es[i].remove()
76			}
77		}
78		e := es[0]
79		for i, c := range mask {
80			if c == '1' {
81				if e != es[i] {
82					t.Errorf("%d: expected entry %d; found %d", i, es[i].elems, e.elems)
83				}
84				e, _ = e.nextIndexed()
85			}
86		}
87		if e != nil {
88			t.Errorf("%d: expected nil entry; found %d", i, e.elems)
89		}
90	}
91}
92
93// nextPerm generates the next permutation of the array.  The starting
94// permutation is assumed to be a list of integers sorted in increasing order.
95// It returns false if there are no more permuations left.
96func nextPerm(a []int) bool {
97	i := len(a) - 2
98	for ; i >= 0; i-- {
99		if a[i] < a[i+1] {
100			break
101		}
102	}
103	if i < 0 {
104		return false
105	}
106	for j := len(a) - 1; j >= i; j-- {
107		if a[j] > a[i] {
108			a[i], a[j] = a[j], a[i]
109			break
110		}
111	}
112	for j := i + 1; j < (len(a)+i+1)/2; j++ {
113		a[j], a[len(a)+i-j] = a[len(a)+i-j], a[j]
114	}
115	return true
116}
117
118func TestInsertAfter(t *testing.T) {
119	const n = 5
120	orig := makeList(n)
121	perm := make([]int, n)
122	for i := range perm {
123		perm[i] = i + 1
124	}
125	for ok := true; ok; ok = nextPerm(perm) {
126		es := makeList(n)
127		last := es[0]
128		for _, i := range perm {
129			last.insertAfter(es[i])
130			last = es[i]
131		}
132		for _, e := range es {
133			e.elems = es[0].elems
134		}
135		e := es[0]
136		for _, i := range perm {
137			e, _ = e.nextIndexed()
138			if e.runes[0] != orig[i].runes[0] {
139				t.Errorf("%d:%d: expected entry %X; found %X", perm, i, orig[i].runes, e.runes)
140				break
141			}
142		}
143	}
144}
145
146func TestInsertBefore(t *testing.T) {
147	const n = 5
148	orig := makeList(n)
149	perm := make([]int, n)
150	for i := range perm {
151		perm[i] = i + 1
152	}
153	for ok := true; ok; ok = nextPerm(perm) {
154		es := makeList(n)
155		last := es[len(es)-1]
156		for _, i := range perm {
157			last.insertBefore(es[i])
158			last = es[i]
159		}
160		for _, e := range es {
161			e.elems = es[0].elems
162		}
163		e := es[0]
164		for i := n - 1; i >= 0; i-- {
165			e, _ = e.nextIndexed()
166			if e.runes[0] != rune(perm[i]) {
167				t.Errorf("%d:%d: expected entry %X; found %X", perm, i, orig[i].runes, e.runes)
168				break
169			}
170		}
171	}
172}
173
174type entryLessTest struct {
175	a, b *entry
176	res  bool
177}
178
179var (
180	w1 = []rawCE{{w: []int{100, 20, 5, 5}}}
181	w2 = []rawCE{{w: []int{101, 20, 5, 5}}}
182)
183
184var entryLessTests = []entryLessTest{
185	{&entry{str: "a", elems: w1},
186		&entry{str: "a", elems: w1},
187		false,
188	},
189	{&entry{str: "a", elems: w1},
190		&entry{str: "a", elems: w2},
191		true,
192	},
193	{&entry{str: "a", elems: w1},
194		&entry{str: "b", elems: w1},
195		true,
196	},
197	{&entry{str: "a", elems: w2},
198		&entry{str: "a", elems: w1},
199		false,
200	},
201	{&entry{str: "c", elems: w1},
202		&entry{str: "b", elems: w1},
203		false,
204	},
205	{&entry{str: "a", elems: w1, logical: firstAnchor},
206		&entry{str: "a", elems: w1},
207		true,
208	},
209	{&entry{str: "a", elems: w1},
210		&entry{str: "b", elems: w1, logical: firstAnchor},
211		false,
212	},
213	{&entry{str: "b", elems: w1},
214		&entry{str: "a", elems: w1, logical: lastAnchor},
215		true,
216	},
217	{&entry{str: "a", elems: w1, logical: lastAnchor},
218		&entry{str: "c", elems: w1},
219		false,
220	},
221}
222
223func TestEntryLess(t *testing.T) {
224	for i, tt := range entryLessTests {
225		if res := entryLess(tt.a, tt.b); res != tt.res {
226			t.Errorf("%d: was %v; want %v", i, res, tt.res)
227		}
228	}
229}
230