1package yaml
2
3import (
4	"reflect"
5	"unicode"
6)
7
8type keyList []reflect.Value
9
10func (l keyList) Len() int      { return len(l) }
11func (l keyList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
12func (l keyList) Less(i, j int) bool {
13	a := l[i]
14	b := l[j]
15	ak := a.Kind()
16	bk := b.Kind()
17	for (ak == reflect.Interface || ak == reflect.Ptr) && !a.IsNil() {
18		a = a.Elem()
19		ak = a.Kind()
20	}
21	for (bk == reflect.Interface || bk == reflect.Ptr) && !b.IsNil() {
22		b = b.Elem()
23		bk = b.Kind()
24	}
25	af, aok := keyFloat(a)
26	bf, bok := keyFloat(b)
27	if aok && bok {
28		if af != bf {
29			return af < bf
30		}
31		if ak != bk {
32			return ak < bk
33		}
34		return numLess(a, b)
35	}
36	if ak != reflect.String || bk != reflect.String {
37		return ak < bk
38	}
39	ar, br := []rune(a.String()), []rune(b.String())
40	for i := 0; i < len(ar) && i < len(br); i++ {
41		if ar[i] == br[i] {
42			continue
43		}
44		al := unicode.IsLetter(ar[i])
45		bl := unicode.IsLetter(br[i])
46		if al && bl {
47			return ar[i] < br[i]
48		}
49		if al || bl {
50			return bl
51		}
52		var ai, bi int
53		var an, bn int64
54		if ar[i] == '0' || br[i] == '0' {
55			for j := i-1; j >= 0 && unicode.IsDigit(ar[j]); j-- {
56				if ar[j] != '0' {
57					an = 1
58					bn = 1
59					break
60				}
61			}
62		}
63		for ai = i; ai < len(ar) && unicode.IsDigit(ar[ai]); ai++ {
64			an = an*10 + int64(ar[ai]-'0')
65		}
66		for bi = i; bi < len(br) && unicode.IsDigit(br[bi]); bi++ {
67			bn = bn*10 + int64(br[bi]-'0')
68		}
69		if an != bn {
70			return an < bn
71		}
72		if ai != bi {
73			return ai < bi
74		}
75		return ar[i] < br[i]
76	}
77	return len(ar) < len(br)
78}
79
80// keyFloat returns a float value for v if it is a number/bool
81// and whether it is a number/bool or not.
82func keyFloat(v reflect.Value) (f float64, ok bool) {
83	switch v.Kind() {
84	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
85		return float64(v.Int()), true
86	case reflect.Float32, reflect.Float64:
87		return v.Float(), true
88	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
89		return float64(v.Uint()), true
90	case reflect.Bool:
91		if v.Bool() {
92			return 1, true
93		}
94		return 0, true
95	}
96	return 0, false
97}
98
99// numLess returns whether a < b.
100// a and b must necessarily have the same kind.
101func numLess(a, b reflect.Value) bool {
102	switch a.Kind() {
103	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
104		return a.Int() < b.Int()
105	case reflect.Float32, reflect.Float64:
106		return a.Float() < b.Float()
107	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
108		return a.Uint() < b.Uint()
109	case reflect.Bool:
110		return !a.Bool() && b.Bool()
111	}
112	panic("not a number")
113}
114