1// run
2
3// Copyright 2009 The Go Authors. All rights reserved.
4// Use of this source code is governed by a BSD-style
5// license that can be found in the LICENSE file.
6
7// Test maps, almost exhaustively.
8// Complexity (linearity) test is in maplinear.go.
9
10package main
11
12import (
13	"fmt"
14	"math"
15	"strconv"
16)
17
18const count = 100
19
20func P(a []string) string {
21	s := "{"
22	for i := 0; i < len(a); i++ {
23		if i > 0 {
24			s += ","
25		}
26		s += `"` + a[i] + `"`
27	}
28	s += "}"
29	return s
30}
31
32func main() {
33	testbasic()
34	testfloat()
35	testnan()
36}
37
38func testbasic() {
39	// Test a map literal.
40	mlit := map[string]int{"0": 0, "1": 1, "2": 2, "3": 3, "4": 4}
41	for i := 0; i < len(mlit); i++ {
42		s := string([]byte{byte(i) + '0'})
43		if mlit[s] != i {
44			panic(fmt.Sprintf("mlit[%s] = %d\n", s, mlit[s]))
45		}
46	}
47
48	mib := make(map[int]bool)
49	mii := make(map[int]int)
50	mfi := make(map[float32]int)
51	mif := make(map[int]float32)
52	msi := make(map[string]int)
53	mis := make(map[int]string)
54	mss := make(map[string]string)
55	mspa := make(map[string][]string)
56	// BUG need an interface map both ways too
57
58	type T struct {
59		i int64 // can't use string here; struct values are only compared at the top level
60		f float32
61	}
62	mipT := make(map[int]*T)
63	mpTi := make(map[*T]int)
64	mit := make(map[int]T)
65	//	mti := make(map[T] int)
66
67	type M map[int]int
68	mipM := make(map[int]M)
69
70	var apT [2 * count]*T
71
72	for i := 0; i < count; i++ {
73		s := strconv.Itoa(i)
74		s10 := strconv.Itoa(i * 10)
75		f := float32(i)
76		t := T{int64(i), f}
77		apT[i] = new(T)
78		apT[i].i = int64(i)
79		apT[i].f = f
80		apT[2*i] = new(T) // need twice as many entries as we use, for the nonexistence check
81		apT[2*i].i = int64(i)
82		apT[2*i].f = f
83		m := M{i: i + 1}
84		mib[i] = (i != 0)
85		mii[i] = 10 * i
86		mfi[float32(i)] = 10 * i
87		mif[i] = 10.0 * f
88		mis[i] = s
89		msi[s] = i
90		mss[s] = s10
91		mss[s] = s10
92		as := make([]string, 2)
93		as[0] = s10
94		as[1] = s10
95		mspa[s] = as
96		mipT[i] = apT[i]
97		mpTi[apT[i]] = i
98		mipM[i] = m
99		mit[i] = t
100		//	mti[t] = i
101	}
102
103	// test len
104	if len(mib) != count {
105		panic(fmt.Sprintf("len(mib) = %d\n", len(mib)))
106	}
107	if len(mii) != count {
108		panic(fmt.Sprintf("len(mii) = %d\n", len(mii)))
109	}
110	if len(mfi) != count {
111		panic(fmt.Sprintf("len(mfi) = %d\n", len(mfi)))
112	}
113	if len(mif) != count {
114		panic(fmt.Sprintf("len(mif) = %d\n", len(mif)))
115	}
116	if len(msi) != count {
117		panic(fmt.Sprintf("len(msi) = %d\n", len(msi)))
118	}
119	if len(mis) != count {
120		panic(fmt.Sprintf("len(mis) = %d\n", len(mis)))
121	}
122	if len(mss) != count {
123		panic(fmt.Sprintf("len(mss) = %d\n", len(mss)))
124	}
125	if len(mspa) != count {
126		panic(fmt.Sprintf("len(mspa) = %d\n", len(mspa)))
127	}
128	if len(mipT) != count {
129		panic(fmt.Sprintf("len(mipT) = %d\n", len(mipT)))
130	}
131	if len(mpTi) != count {
132		panic(fmt.Sprintf("len(mpTi) = %d\n", len(mpTi)))
133	}
134	//	if len(mti) != count {
135	//              panic(fmt.Sprintf("len(mti) = %d\n", len(mti)))
136	//	}
137	if len(mipM) != count {
138		panic(fmt.Sprintf("len(mipM) = %d\n", len(mipM)))
139	}
140	//	if len(mti) != count {
141	//		panic(fmt.Sprintf("len(mti) = %d\n", len(mti)))
142	//	}
143	if len(mit) != count {
144		panic(fmt.Sprintf("len(mit) = %d\n", len(mit)))
145	}
146
147	// test construction directly
148	for i := 0; i < count; i++ {
149		s := strconv.Itoa(i)
150		s10 := strconv.Itoa(i * 10)
151		f := float32(i)
152		// BUG m := M(i, i+1)
153		if mib[i] != (i != 0) {
154			panic(fmt.Sprintf("mib[%d] = %t\n", i, mib[i]))
155		}
156		if mii[i] != 10*i {
157			panic(fmt.Sprintf("mii[%d] = %d\n", i, mii[i]))
158		}
159		if mfi[f] != 10*i {
160			panic(fmt.Sprintf("mfi[%d] = %d\n", i, mfi[f]))
161		}
162		if mif[i] != 10.0*f {
163			panic(fmt.Sprintf("mif[%d] = %g\n", i, mif[i]))
164		}
165		if mis[i] != s {
166			panic(fmt.Sprintf("mis[%d] = %s\n", i, mis[i]))
167		}
168		if msi[s] != i {
169			panic(fmt.Sprintf("msi[%s] = %d\n", s, msi[s]))
170		}
171		if mss[s] != s10 {
172			panic(fmt.Sprintf("mss[%s] = %g\n", s, mss[s]))
173		}
174		for j := 0; j < len(mspa[s]); j++ {
175			if mspa[s][j] != s10 {
176				panic(fmt.Sprintf("mspa[%s][%d] = %s\n", s, j, mspa[s][j]))
177			}
178		}
179		if mipT[i].i != int64(i) || mipT[i].f != f {
180			panic(fmt.Sprintf("mipT[%d] = %v\n", i, mipT[i]))
181		}
182		if mpTi[apT[i]] != i {
183			panic(fmt.Sprintf("mpTi[apT[%d]] = %d\n", i, mpTi[apT[i]]))
184		}
185		//	if(mti[t] != i) {
186		//		panic(fmt.Sprintf("mti[%s] = %s\n", s, mti[t]))
187		//	}
188		if mipM[i][i] != i+1 {
189			panic(fmt.Sprintf("mipM[%d][%d] = %d\n", i, i, mipM[i][i]))
190		}
191		//	if(mti[t] != i) {
192		//		panic(fmt.Sprintf("mti[%v] = %d\n", t, mti[t]))
193		//	}
194		if mit[i].i != int64(i) || mit[i].f != f {
195			panic(fmt.Sprintf("mit[%d] = {%d %g}\n", i, mit[i].i, mit[i].f))
196		}
197	}
198
199	// test existence with tuple check
200	// failed lookups yield a false value for the boolean.
201	for i := 0; i < count; i++ {
202		s := strconv.Itoa(i)
203		f := float32(i)
204		{
205			_, b := mib[i]
206			if !b {
207				panic(fmt.Sprintf("tuple existence decl: mib[%d]\n", i))
208			}
209			_, b = mib[i]
210			if !b {
211				panic(fmt.Sprintf("tuple existence assign: mib[%d]\n", i))
212			}
213		}
214		{
215			_, b := mii[i]
216			if !b {
217				panic(fmt.Sprintf("tuple existence decl: mii[%d]\n", i))
218			}
219			_, b = mii[i]
220			if !b {
221				panic(fmt.Sprintf("tuple existence assign: mii[%d]\n", i))
222			}
223		}
224		{
225			_, b := mfi[f]
226			if !b {
227				panic(fmt.Sprintf("tuple existence decl: mfi[%d]\n", i))
228			}
229			_, b = mfi[f]
230			if !b {
231				panic(fmt.Sprintf("tuple existence assign: mfi[%d]\n", i))
232			}
233		}
234		{
235			_, b := mif[i]
236			if !b {
237				panic(fmt.Sprintf("tuple existence decl: mif[%d]\n", i))
238			}
239			_, b = mif[i]
240			if !b {
241				panic(fmt.Sprintf("tuple existence assign: mif[%d]\n", i))
242			}
243		}
244		{
245			_, b := mis[i]
246			if !b {
247				panic(fmt.Sprintf("tuple existence decl: mis[%d]\n", i))
248			}
249			_, b = mis[i]
250			if !b {
251				panic(fmt.Sprintf("tuple existence assign: mis[%d]\n", i))
252			}
253		}
254		{
255			_, b := msi[s]
256			if !b {
257				panic(fmt.Sprintf("tuple existence decl: msi[%d]\n", i))
258			}
259			_, b = msi[s]
260			if !b {
261				panic(fmt.Sprintf("tuple existence assign: msi[%d]\n", i))
262			}
263		}
264		{
265			_, b := mss[s]
266			if !b {
267				panic(fmt.Sprintf("tuple existence decl: mss[%d]\n", i))
268			}
269			_, b = mss[s]
270			if !b {
271				panic(fmt.Sprintf("tuple existence assign: mss[%d]\n", i))
272			}
273		}
274		{
275			_, b := mspa[s]
276			if !b {
277				panic(fmt.Sprintf("tuple existence decl: mspa[%d]\n", i))
278			}
279			_, b = mspa[s]
280			if !b {
281				panic(fmt.Sprintf("tuple existence assign: mspa[%d]\n", i))
282			}
283		}
284		{
285			_, b := mipT[i]
286			if !b {
287				panic(fmt.Sprintf("tuple existence decl: mipT[%d]\n", i))
288			}
289			_, b = mipT[i]
290			if !b {
291				panic(fmt.Sprintf("tuple existence assign: mipT[%d]\n", i))
292			}
293		}
294		{
295			_, b := mpTi[apT[i]]
296			if !b {
297				panic(fmt.Sprintf("tuple existence decl: mpTi[apT[%d]]\n", i))
298			}
299			_, b = mpTi[apT[i]]
300			if !b {
301				panic(fmt.Sprintf("tuple existence assign: mpTi[apT[%d]]\n", i))
302			}
303		}
304		{
305			_, b := mipM[i]
306			if !b {
307				panic(fmt.Sprintf("tuple existence decl: mipM[%d]\n", i))
308			}
309			_, b = mipM[i]
310			if !b {
311				panic(fmt.Sprintf("tuple existence assign: mipM[%d]\n", i))
312			}
313		}
314		{
315			_, b := mit[i]
316			if !b {
317				panic(fmt.Sprintf("tuple existence decl: mit[%d]\n", i))
318			}
319			_, b = mit[i]
320			if !b {
321				panic(fmt.Sprintf("tuple existence assign: mit[%d]\n", i))
322			}
323		}
324		//		{
325		//			_, b := mti[t]
326		//			if !b {
327		//				panic(fmt.Sprintf("tuple existence decl: mti[%d]\n", i))
328		//			}
329		//			_, b = mti[t]
330		//			if !b {
331		//				panic(fmt.Sprintf("tuple existence assign: mti[%d]\n", i))
332		//			}
333		//		}
334	}
335
336	// test nonexistence with tuple check
337	// failed lookups yield a false value for the boolean.
338	for i := count; i < 2*count; i++ {
339		s := strconv.Itoa(i)
340		f := float32(i)
341		{
342			_, b := mib[i]
343			if b {
344				panic(fmt.Sprintf("tuple nonexistence decl: mib[%d]", i))
345			}
346			_, b = mib[i]
347			if b {
348				panic(fmt.Sprintf("tuple nonexistence assign: mib[%d]", i))
349			}
350		}
351		{
352			_, b := mii[i]
353			if b {
354				panic(fmt.Sprintf("tuple nonexistence decl: mii[%d]", i))
355			}
356			_, b = mii[i]
357			if b {
358				panic(fmt.Sprintf("tuple nonexistence assign: mii[%d]", i))
359			}
360		}
361		{
362			_, b := mfi[f]
363			if b {
364				panic(fmt.Sprintf("tuple nonexistence decl: mfi[%d]", i))
365			}
366			_, b = mfi[f]
367			if b {
368				panic(fmt.Sprintf("tuple nonexistence assign: mfi[%d]", i))
369			}
370		}
371		{
372			_, b := mif[i]
373			if b {
374				panic(fmt.Sprintf("tuple nonexistence decl: mif[%d]", i))
375			}
376			_, b = mif[i]
377			if b {
378				panic(fmt.Sprintf("tuple nonexistence assign: mif[%d]", i))
379			}
380		}
381		{
382			_, b := mis[i]
383			if b {
384				panic(fmt.Sprintf("tuple nonexistence decl: mis[%d]", i))
385			}
386			_, b = mis[i]
387			if b {
388				panic(fmt.Sprintf("tuple nonexistence assign: mis[%d]", i))
389			}
390		}
391		{
392			_, b := msi[s]
393			if b {
394				panic(fmt.Sprintf("tuple nonexistence decl: msi[%d]", i))
395			}
396			_, b = msi[s]
397			if b {
398				panic(fmt.Sprintf("tuple nonexistence assign: msi[%d]", i))
399			}
400		}
401		{
402			_, b := mss[s]
403			if b {
404				panic(fmt.Sprintf("tuple nonexistence decl: mss[%d]", i))
405			}
406			_, b = mss[s]
407			if b {
408				panic(fmt.Sprintf("tuple nonexistence assign: mss[%d]", i))
409			}
410		}
411		{
412			_, b := mspa[s]
413			if b {
414				panic(fmt.Sprintf("tuple nonexistence decl: mspa[%d]", i))
415			}
416			_, b = mspa[s]
417			if b {
418				panic(fmt.Sprintf("tuple nonexistence assign: mspa[%d]", i))
419			}
420		}
421		{
422			_, b := mipT[i]
423			if b {
424				panic(fmt.Sprintf("tuple nonexistence decl: mipT[%d]", i))
425			}
426			_, b = mipT[i]
427			if b {
428				panic(fmt.Sprintf("tuple nonexistence assign: mipT[%d]", i))
429			}
430		}
431		{
432			_, b := mpTi[apT[i]]
433			if b {
434				panic(fmt.Sprintf("tuple nonexistence decl: mpTi[apt[%d]]", i))
435			}
436			_, b = mpTi[apT[i]]
437			if b {
438				panic(fmt.Sprintf("tuple nonexistence assign: mpTi[apT[%d]]", i))
439			}
440		}
441		{
442			_, b := mipM[i]
443			if b {
444				panic(fmt.Sprintf("tuple nonexistence decl: mipM[%d]", i))
445			}
446			_, b = mipM[i]
447			if b {
448				panic(fmt.Sprintf("tuple nonexistence assign: mipM[%d]", i))
449			}
450		}
451		//		{
452		//			_, b := mti[t]
453		//			if b {
454		//				panic(fmt.Sprintf("tuple nonexistence decl: mti[%d]", i))
455		//			}
456		//			_, b = mti[t]
457		//			if b {
458		//				panic(fmt.Sprintf("tuple nonexistence assign: mti[%d]", i))
459		//			}
460		//		}
461		{
462			_, b := mit[i]
463			if b {
464				panic(fmt.Sprintf("tuple nonexistence decl: mit[%d]", i))
465			}
466			_, b = mit[i]
467			if b {
468				panic(fmt.Sprintf("tuple nonexistence assign: mit[%d]", i))
469			}
470		}
471	}
472
473	// tests for structured map element updates
474	for i := 0; i < count; i++ {
475		s := strconv.Itoa(i)
476		mspa[s][i%2] = "deleted"
477		if mspa[s][i%2] != "deleted" {
478			panic(fmt.Sprintf("update mspa[%s][%d] = %s\n", s, i%2, mspa[s][i%2]))
479
480		}
481
482		mipT[i].i += 1
483		if mipT[i].i != int64(i)+1 {
484			panic(fmt.Sprintf("update mipT[%d].i = %d\n", i, mipT[i].i))
485
486		}
487		mipT[i].f = float32(i + 1)
488		if mipT[i].f != float32(i+1) {
489			panic(fmt.Sprintf("update mipT[%d].f = %g\n", i, mipT[i].f))
490
491		}
492
493		mipM[i][i]++
494		if mipM[i][i] != (i+1)+1 {
495			panic(fmt.Sprintf("update mipM[%d][%d] = %d\n", i, i, mipM[i][i]))
496
497		}
498	}
499
500	// test range on nil map
501	var mnil map[string]int
502	for _, _ = range mnil {
503		panic("range mnil")
504	}
505}
506
507func testfloat() {
508	// Test floating point numbers in maps.
509	// Two map keys refer to the same entry if the keys are ==.
510	// The special cases, then, are that +0 == -0 and that NaN != NaN.
511
512	{
513		var (
514			pz   = float32(0)
515			nz   = math.Float32frombits(1 << 31)
516			nana = float32(math.NaN())
517			nanb = math.Float32frombits(math.Float32bits(nana) ^ 2)
518		)
519
520		m := map[float32]string{
521			pz:   "+0",
522			nana: "NaN",
523			nanb: "NaN",
524		}
525		if m[pz] != "+0" {
526			panic(fmt.Sprintln("float32 map cannot read back m[+0]:", m[pz]))
527		}
528		if m[nz] != "+0" {
529			fmt.Sprintln("float32 map does not treat", pz, "and", nz, "as equal for read")
530			panic(fmt.Sprintln("float32 map does not treat -0 and +0 as equal for read"))
531		}
532		m[nz] = "-0"
533		if m[pz] != "-0" {
534			panic(fmt.Sprintln("float32 map does not treat -0 and +0 as equal for write"))
535		}
536		if _, ok := m[nana]; ok {
537			panic(fmt.Sprintln("float32 map allows NaN lookup (a)"))
538		}
539		if _, ok := m[nanb]; ok {
540			panic(fmt.Sprintln("float32 map allows NaN lookup (b)"))
541		}
542		if len(m) != 3 {
543			panic(fmt.Sprintln("float32 map should have 3 entries:", m))
544		}
545		m[nana] = "NaN"
546		m[nanb] = "NaN"
547		if len(m) != 5 {
548			panic(fmt.Sprintln("float32 map should have 5 entries:", m))
549		}
550	}
551
552	{
553		var (
554			pz   = float64(0)
555			nz   = math.Float64frombits(1 << 63)
556			nana = float64(math.NaN())
557			nanb = math.Float64frombits(math.Float64bits(nana) ^ 2)
558		)
559
560		m := map[float64]string{
561			pz:   "+0",
562			nana: "NaN",
563			nanb: "NaN",
564		}
565		if m[nz] != "+0" {
566			panic(fmt.Sprintln("float64 map does not treat -0 and +0 as equal for read"))
567		}
568		m[nz] = "-0"
569		if m[pz] != "-0" {
570			panic(fmt.Sprintln("float64 map does not treat -0 and +0 as equal for write"))
571		}
572		if _, ok := m[nana]; ok {
573			panic(fmt.Sprintln("float64 map allows NaN lookup (a)"))
574		}
575		if _, ok := m[nanb]; ok {
576			panic(fmt.Sprintln("float64 map allows NaN lookup (b)"))
577		}
578		if len(m) != 3 {
579			panic(fmt.Sprintln("float64 map should have 3 entries:", m))
580		}
581		m[nana] = "NaN"
582		m[nanb] = "NaN"
583		if len(m) != 5 {
584			panic(fmt.Sprintln("float64 map should have 5 entries:", m))
585		}
586	}
587
588	{
589		var (
590			pz   = complex64(0)
591			nz   = complex(0, math.Float32frombits(1<<31))
592			nana = complex(5, float32(math.NaN()))
593			nanb = complex(5, math.Float32frombits(math.Float32bits(float32(math.NaN()))^2))
594		)
595
596		m := map[complex64]string{
597			pz:   "+0",
598			nana: "NaN",
599			nanb: "NaN",
600		}
601		if m[nz] != "+0" {
602			panic(fmt.Sprintln("complex64 map does not treat -0 and +0 as equal for read"))
603		}
604		m[nz] = "-0"
605		if m[pz] != "-0" {
606			panic(fmt.Sprintln("complex64 map does not treat -0 and +0 as equal for write"))
607		}
608		if _, ok := m[nana]; ok {
609			panic(fmt.Sprintln("complex64 map allows NaN lookup (a)"))
610		}
611		if _, ok := m[nanb]; ok {
612			panic(fmt.Sprintln("complex64 map allows NaN lookup (b)"))
613		}
614		if len(m) != 3 {
615			panic(fmt.Sprintln("complex64 map should have 3 entries:", m))
616		}
617		m[nana] = "NaN"
618		m[nanb] = "NaN"
619		if len(m) != 5 {
620			panic(fmt.Sprintln("complex64 map should have 5 entries:", m))
621		}
622	}
623
624	{
625		var (
626			pz   = complex128(0)
627			nz   = complex(0, math.Float64frombits(1<<63))
628			nana = complex(5, float64(math.NaN()))
629			nanb = complex(5, math.Float64frombits(math.Float64bits(float64(math.NaN()))^2))
630		)
631
632		m := map[complex128]string{
633			pz:   "+0",
634			nana: "NaN",
635			nanb: "NaN",
636		}
637		if m[nz] != "+0" {
638			panic(fmt.Sprintln("complex128 map does not treat -0 and +0 as equal for read"))
639		}
640		m[nz] = "-0"
641		if m[pz] != "-0" {
642			panic(fmt.Sprintln("complex128 map does not treat -0 and +0 as equal for write"))
643		}
644		if _, ok := m[nana]; ok {
645			panic(fmt.Sprintln("complex128 map allows NaN lookup (a)"))
646		}
647		if _, ok := m[nanb]; ok {
648			panic(fmt.Sprintln("complex128 map allows NaN lookup (b)"))
649		}
650		if len(m) != 3 {
651			panic(fmt.Sprintln("complex128 map should have 3 entries:", m))
652		}
653		m[nana] = "NaN"
654		m[nanb] = "NaN"
655		if len(m) != 5 {
656			panic(fmt.Sprintln("complex128 map should have 5 entries:", m))
657		}
658	}
659}
660
661func testnan() {
662	n := 500
663	m := map[float64]int{}
664	nan := math.NaN()
665	for i := 0; i < n; i++ {
666		m[nan] = 1
667	}
668	if len(m) != n {
669		panic("wrong size map after nan insertion")
670	}
671	iters := 0
672	for k, v := range m {
673		iters++
674		if !math.IsNaN(k) {
675			panic("not NaN")
676		}
677		if v != 1 {
678			panic("wrong value")
679		}
680	}
681	if iters != n {
682		panic("wrong number of nan range iters")
683	}
684}
685