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