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 "sort" 19 "text/scanner" 20) 21 22func SortLists(file *File) { 23 for _, def := range file.Defs { 24 if assignment, ok := def.(*Assignment); ok { 25 sortListsInValue(assignment.Value, file) 26 } else if module, ok := def.(*Module); ok { 27 for _, prop := range module.Properties { 28 sortListsInValue(prop.Value, file) 29 } 30 } 31 } 32 sort.Sort(commentsByOffset(file.Comments)) 33} 34 35func SortList(file *File, value Value) { 36 for i := 0; i < len(value.ListValue); i++ { 37 // Find a set of values on contiguous lines 38 line := value.ListValue[i].Pos.Line 39 var j int 40 for j = i + 1; j < len(value.ListValue); j++ { 41 if value.ListValue[j].Pos.Line > line+1 { 42 break 43 } 44 line = value.ListValue[j].Pos.Line 45 } 46 47 nextPos := value.EndPos 48 if j < len(value.ListValue) { 49 nextPos = value.ListValue[j].Pos 50 } 51 sortSubList(value.ListValue[i:j], nextPos, file) 52 i = j - 1 53 } 54} 55 56func ListIsSorted(value Value) bool { 57 for i := 0; i < len(value.ListValue); i++ { 58 // Find a set of values on contiguous lines 59 line := value.ListValue[i].Pos.Line 60 var j int 61 for j = i + 1; j < len(value.ListValue); j++ { 62 if value.ListValue[j].Pos.Line > line+1 { 63 break 64 } 65 line = value.ListValue[j].Pos.Line 66 } 67 68 if !subListIsSorted(value.ListValue[i:j]) { 69 return false 70 } 71 i = j - 1 72 } 73 74 return true 75} 76 77func sortListsInValue(value Value, file *File) { 78 if value.Variable != "" { 79 return 80 } 81 82 if value.Expression != nil { 83 sortListsInValue(value.Expression.Args[0], file) 84 sortListsInValue(value.Expression.Args[1], file) 85 return 86 } 87 88 if value.Type == Map { 89 for _, p := range value.MapValue { 90 sortListsInValue(p.Value, file) 91 } 92 return 93 } else if value.Type != List { 94 return 95 } 96 97 SortList(file, value) 98} 99 100func sortSubList(values []Value, nextPos scanner.Position, file *File) { 101 l := make(elemList, len(values)) 102 for i, v := range values { 103 if v.Type != String { 104 panic("list contains non-string element") 105 } 106 n := nextPos 107 if i < len(values)-1 { 108 n = values[i+1].Pos 109 } 110 l[i] = elem{v.StringValue, i, v.Pos, n} 111 } 112 113 sort.Sort(l) 114 115 copyValues := append([]Value{}, values...) 116 copyComments := append([]Comment{}, file.Comments...) 117 118 curPos := values[0].Pos 119 for i, e := range l { 120 values[i] = copyValues[e.i] 121 values[i].Pos = curPos 122 for j, c := range copyComments { 123 if c.Pos.Offset > e.pos.Offset && c.Pos.Offset < e.nextPos.Offset { 124 file.Comments[j].Pos.Line = curPos.Line 125 file.Comments[j].Pos.Offset += values[i].Pos.Offset - e.pos.Offset 126 } 127 } 128 129 curPos.Offset += e.nextPos.Offset - e.pos.Offset 130 curPos.Line++ 131 } 132} 133 134func subListIsSorted(values []Value) bool { 135 prev := "" 136 for _, v := range values { 137 if v.Type != String { 138 panic("list contains non-string element") 139 } 140 if prev > v.StringValue { 141 return false 142 } 143 prev = v.StringValue 144 } 145 146 return true 147} 148 149type elem struct { 150 s string 151 i int 152 pos scanner.Position 153 nextPos scanner.Position 154} 155 156type elemList []elem 157 158func (l elemList) Len() int { 159 return len(l) 160} 161 162func (l elemList) Swap(i, j int) { 163 l[i], l[j] = l[j], l[i] 164} 165 166func (l elemList) Less(i, j int) bool { 167 return l[i].s < l[j].s 168} 169 170type commentsByOffset []Comment 171 172func (l commentsByOffset) Len() int { 173 return len(l) 174} 175 176func (l commentsByOffset) Less(i, j int) bool { 177 return l[i].Pos.Offset < l[j].Pos.Offset 178} 179 180func (l commentsByOffset) Swap(i, j int) { 181 l[i], l[j] = l[j], l[i] 182} 183