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
16package yaml
17
18import (
19	"reflect"
20	"unicode"
21)
22
23type keyList []reflect.Value
24
25func (l keyList) Len() int      { return len(l) }
26func (l keyList) Swap(i, j int) { l[i], l[j] = l[j], l[i] }
27func (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.
103func 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.
122func 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