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 + c.Pos().Line - e.pos.Line
231				curPos.Line += c.Pos().Line - e.pos.Line
232				file.Comments[j].Comments[0].Slash.Offset += values[i].Pos().Offset - e.pos.Offset
233			}
234		}
235
236		curPos.Offset += e.nextPos.Offset - e.pos.Offset
237		curPos.Line++
238	}
239}
240
241func subListIsSorted(values []Expression) bool {
242	if !isListOfPrimitives(values) {
243		return true
244	}
245	prev := ""
246	for _, v := range values {
247		s, ok := v.(*String)
248		if !ok {
249			panic("list contains non-string element")
250		}
251		if prev != "" && numericStringLess(s.Value, prev) {
252			return false
253		}
254		prev = s.Value
255	}
256
257	return true
258}
259
260type elem struct {
261	s       string
262	i       int
263	pos     scanner.Position
264	nextPos scanner.Position
265}
266
267type commentsByOffset []*CommentGroup
268
269func (l commentsByOffset) Len() int {
270	return len(l)
271}
272
273func (l commentsByOffset) Less(i, j int) bool {
274	return l[i].Pos().Offset < l[j].Pos().Offset
275}
276
277func (l commentsByOffset) Swap(i, j int) {
278	l[i], l[j] = l[j], l[i]
279}
280
281func isListOfPrimitives(values []Expression) bool {
282	if len(values) == 0 {
283		return true
284	}
285	switch values[0].Type() {
286	case BoolType, StringType, Int64Type:
287		return true
288	default:
289		return false
290	}
291}
292