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