1// Copyright 2014 Google Inc. All rights reserved. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package parser 16 17import ( 18 "fmt" 19 "sort" 20 "strconv" 21 "strings" 22 "text/scanner" 23) 24 25// numericStringLess compares two strings, returning a lexicographical comparison unless the first 26// difference occurs in a sequence of 1 or more numeric characters, in which case it returns the 27// numerical comparison of the two numbers. 28func numericStringLess(a, b string) bool { 29 isNumeric := func(r rune) bool { return r >= '0' && r <= '9' } 30 isNotNumeric := func(r rune) bool { return !isNumeric(r) } 31 32 minLength := len(a) 33 if len(b) < minLength { 34 minLength = len(b) 35 } 36 37 byteIndex := 0 38 numberStartIndex := -1 39 40 var aByte, bByte byte 41 42 // Start with a byte comparison to find where the strings differ. 43 for ; byteIndex < minLength; byteIndex++ { 44 aByte, bByte = a[byteIndex], b[byteIndex] 45 if aByte != bByte { 46 break 47 } 48 byteIsNumeric := isNumeric(rune(aByte)) 49 if numberStartIndex != -1 && !byteIsNumeric { 50 numberStartIndex = -1 51 } else if numberStartIndex == -1 && byteIsNumeric { 52 numberStartIndex = byteIndex 53 } 54 } 55 56 // Handle the case where we reached the end of one or both strings without finding a difference. 57 if byteIndex == minLength { 58 if len(a) < len(b) { 59 // Reached the end of a. a is a prefix of b. 60 return true 61 } else { 62 // Reached the end of b. b is a prefix of a or b is equal to a. 63 return false 64 } 65 } 66 67 aByteNumeric := isNumeric(rune(aByte)) 68 bByteNumeric := isNumeric(rune(bByte)) 69 70 if (aByteNumeric || bByteNumeric) && !(aByteNumeric && bByteNumeric) && numberStartIndex != -1 { 71 // Only one of aByte and bByte is a number, but the previous byte was a number. That means 72 // one is a longer number with the same prefix, which must be numerically larger. If bByte 73 // is a number then the number in b is numerically larger than the number in a. 74 return bByteNumeric 75 } 76 77 // If the bytes are both numbers do a numeric comparison. 78 if aByteNumeric && bByteNumeric { 79 // Extract the numbers from each string, starting from the first number after the last 80 // non-number. This won't be invalid utf8 because we are only looking for the bytes 81 //'0'-'9', which can only occur as single-byte runes in utf8. 82 if numberStartIndex == -1 { 83 numberStartIndex = byteIndex 84 } 85 aNumberString := a[numberStartIndex:] 86 bNumberString := b[numberStartIndex:] 87 88 // Find the first non-number in each, using the full length if there isn't one. 89 endANumbers := strings.IndexFunc(aNumberString, isNotNumeric) 90 endBNumbers := strings.IndexFunc(bNumberString, isNotNumeric) 91 if endANumbers == -1 { 92 endANumbers = len(aNumberString) 93 } 94 if endBNumbers == -1 { 95 endBNumbers = len(bNumberString) 96 } 97 98 // Convert each to an int. 99 aNumber, err := strconv.Atoi(aNumberString[:endANumbers]) 100 if err != nil { 101 panic(fmt.Errorf("failed to convert %q from %q to number: %w", 102 aNumberString[:endANumbers], a, err)) 103 } 104 bNumber, err := strconv.Atoi(bNumberString[:endBNumbers]) 105 if err != nil { 106 panic(fmt.Errorf("failed to convert %q from %q to number: %w", 107 bNumberString[:endBNumbers], b, err)) 108 } 109 // Do a numeric comparison. 110 return aNumber < bNumber 111 } 112 113 // At least one is not a number, do a byte comparison. 114 return aByte < bByte 115} 116 117func SortLists(file *File) { 118 for _, def := range file.Defs { 119 if assignment, ok := def.(*Assignment); ok { 120 sortListsInValue(assignment.Value, file) 121 } else if module, ok := def.(*Module); ok { 122 for _, prop := range module.Properties { 123 sortListsInValue(prop.Value, file) 124 } 125 } 126 } 127 sort.Sort(commentsByOffset(file.Comments)) 128} 129 130func SortList(file *File, list *List) { 131 if !isListOfPrimitives(list.Values) { 132 return 133 } 134 for i := 0; i < len(list.Values); i++ { 135 // Find a set of values on contiguous lines 136 line := list.Values[i].Pos().Line 137 var j int 138 for j = i + 1; j < len(list.Values); j++ { 139 if list.Values[j].Pos().Line > line+1 { 140 break 141 } 142 line = list.Values[j].Pos().Line 143 } 144 145 nextPos := list.End() 146 if j < len(list.Values) { 147 nextPos = list.Values[j].Pos() 148 } 149 sortSubList(list.Values[i:j], nextPos, file) 150 i = j - 1 151 } 152} 153 154func ListIsSorted(list *List) bool { 155 for i := 0; i < len(list.Values); i++ { 156 // Find a set of values on contiguous lines 157 line := list.Values[i].Pos().Line 158 var j int 159 for j = i + 1; j < len(list.Values); j++ { 160 if list.Values[j].Pos().Line > line+1 { 161 break 162 } 163 line = list.Values[j].Pos().Line 164 } 165 166 if !subListIsSorted(list.Values[i:j]) { 167 return false 168 } 169 i = j - 1 170 } 171 172 return true 173} 174 175func sortListsInValue(value Expression, file *File) { 176 switch v := value.(type) { 177 case *Variable: 178 // Nothing 179 case *Operator: 180 sortListsInValue(v.Args[0], file) 181 sortListsInValue(v.Args[1], file) 182 case *Map: 183 for _, p := range v.Properties { 184 sortListsInValue(p.Value, file) 185 } 186 case *List: 187 SortList(file, v) 188 } 189} 190 191func sortSubList(values []Expression, nextPos scanner.Position, file *File) { 192 if !isListOfPrimitives(values) { 193 return 194 } 195 l := make([]elem, len(values)) 196 for i, v := range values { 197 s, ok := v.(*String) 198 if !ok { 199 panic("list contains non-string element") 200 } 201 n := nextPos 202 if i < len(values)-1 { 203 n = values[i+1].Pos() 204 } 205 l[i] = elem{s.Value, i, v.Pos(), n} 206 } 207 208 sort.SliceStable(l, func(i, j int) bool { 209 return numericStringLess(l[i].s, l[j].s) 210 }) 211 212 copyValues := append([]Expression{}, values...) 213 copyComments := make([]*CommentGroup, len(file.Comments)) 214 for i := range file.Comments { 215 cg := *file.Comments[i] 216 cg.Comments = make([]*Comment, len(cg.Comments)) 217 for j := range file.Comments[i].Comments { 218 c := *file.Comments[i].Comments[j] 219 cg.Comments[j] = &c 220 } 221 copyComments[i] = &cg 222 } 223 224 curPos := values[0].Pos() 225 for i, e := range l { 226 values[i] = copyValues[e.i] 227 values[i].(*String).LiteralPos = curPos 228 for j, c := range copyComments { 229 if c.Pos().Offset > e.pos.Offset && c.Pos().Offset < e.nextPos.Offset { 230 file.Comments[j].Comments[0].Slash.Line = curPos.Line 231 file.Comments[j].Comments[0].Slash.Offset += values[i].Pos().Offset - e.pos.Offset 232 } 233 } 234 235 curPos.Offset += e.nextPos.Offset - e.pos.Offset 236 curPos.Line++ 237 } 238} 239 240func subListIsSorted(values []Expression) bool { 241 if !isListOfPrimitives(values) { 242 return true 243 } 244 prev := "" 245 for _, v := range values { 246 s, ok := v.(*String) 247 if !ok { 248 panic("list contains non-string element") 249 } 250 if prev != "" && numericStringLess(s.Value, prev) { 251 return false 252 } 253 prev = s.Value 254 } 255 256 return true 257} 258 259type elem struct { 260 s string 261 i int 262 pos scanner.Position 263 nextPos scanner.Position 264} 265 266type commentsByOffset []*CommentGroup 267 268func (l commentsByOffset) Len() int { 269 return len(l) 270} 271 272func (l commentsByOffset) Less(i, j int) bool { 273 return l[i].Pos().Offset < l[j].Pos().Offset 274} 275 276func (l commentsByOffset) Swap(i, j int) { 277 l[i], l[j] = l[j], l[i] 278} 279 280func isListOfPrimitives(values []Expression) bool { 281 if len(values) == 0 { 282 return true 283 } 284 switch values[0].Type() { 285 case BoolType, StringType, Int64Type: 286 return true 287 default: 288 return false 289 } 290} 291