1
//
2
// Copyright (c) 2011-2019 Canonical Ltd
3
//
4
// Licensed under the Apache License, Version 2.0 (the "License");
5
// you may not use this file except in compliance with the License.
6
// You may obtain a copy of the License at
7
//
8
//     http://www.apache.org/licenses/LICENSE-2.0
9
//
10
// Unless required by applicable law or agreed to in writing, software
11
// distributed under the License is distributed on an "AS IS" BASIS,
12
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
// See the License for the specific language governing permissions and
14
// limitations under the License.
15

16
package yaml
17

18
import (
19
	"reflect"
20
	"unicode"
21
)
22

23
type keyList []reflect.Value
24

25
func (l keyList) Len() int      { return len(l) }
26
func (l keyList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
27
func (l keyList) Less(i, j int) bool {
28
	a := l[i]
29
	b := l[j]
30
	ak := a.Kind()
31
	bk := b.Kind()
32
	for (ak == reflect.Interface || ak == reflect.Ptr) && !a.IsNil() {
33
		a = a.Elem()
34
		ak = a.Kind()
35
	}
36
	for (bk == reflect.Interface || bk == reflect.Ptr) && !b.IsNil() {
37
		b = b.Elem()
38
		bk = b.Kind()
39
	}
40
	af, aok := keyFloat(a)
41
	bf, bok := keyFloat(b)
42
	if aok && bok {
43
		if af != bf {
44
			return af < bf
45
		}
46
		if ak != bk {
47
			return ak < bk
48
		}
49
		return numLess(a, b)
50
	}
51
	if ak != reflect.String || bk != reflect.String {
52
		return ak < bk
53
	}
54
	ar, br := []rune(a.String()), []rune(b.String())
55
	digits := false
56
	for i := 0; i < len(ar) && i < len(br); i++ {
57
		if ar[i] == br[i] {
58
			digits = unicode.IsDigit(ar[i])
59
			continue
60
		}
61
		al := unicode.IsLetter(ar[i])
62
		bl := unicode.IsLetter(br[i])
63
		if al && bl {
64
			return ar[i] < br[i]
65
		}
66
		if al || bl {
67
			if digits {
68
				return al
69
			} else {
70
				return bl
71
			}
72
		}
73
		var ai, bi int
74
		var an, bn int64
75
		if ar[i] == '0' || br[i] == '0' {
76
			for j := i - 1; j >= 0 && unicode.IsDigit(ar[j]); j-- {
77
				if ar[j] != '0' {
78
					an = 1
79
					bn = 1
80
					break
81
				}
82
			}
83
		}
84
		for ai = i; ai < len(ar) && unicode.IsDigit(ar[ai]); ai++ {
85
			an = an*10 + int64(ar[ai]-'0')
86
		}
87
		for bi = i; bi < len(br) && unicode.IsDigit(br[bi]); bi++ {
88
			bn = bn*10 + int64(br[bi]-'0')
89
		}
90
		if an != bn {
91
			return an < bn
92
		}
93
		if ai != bi {
94
			return ai < bi
95
		}
96
		return ar[i] < br[i]
97
	}
98
	return len(ar) < len(br)
99
}
100

101
// keyFloat returns a float value for v if it is a number/bool
102
// and whether it is a number/bool or not.
103
func keyFloat(v reflect.Value) (f float64, ok bool) {
104
	switch v.Kind() {
105
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
106
		return float64(v.Int()), true
107
	case reflect.Float32, reflect.Float64:
108
		return v.Float(), true
109
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
110
		return float64(v.Uint()), true
111
	case reflect.Bool:
112
		if v.Bool() {
113
			return 1, true
114
		}
115
		return 0, true
116
	}
117
	return 0, false
118
}
119

120
// numLess returns whether a < b.
121
// a and b must necessarily have the same kind.
122
func numLess(a, b reflect.Value) bool {
123
	switch a.Kind() {
124
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
125
		return a.Int() < b.Int()
126
	case reflect.Float32, reflect.Float64:
127
		return a.Float() < b.Float()
128
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
129
		return a.Uint() < b.Uint()
130
	case reflect.Bool:
131
		return !a.Bool() && b.Bool()
132
	}
133
	panic("not a number")
134
}
135

136