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, list *List) {
36	if !isListOfPrimitives(list.Values) {
37		return
38	}
39	for i := 0; i < len(list.Values); i++ {
40		// Find a set of values on contiguous lines
41		line := list.Values[i].Pos().Line
42		var j int
43		for j = i + 1; j < len(list.Values); j++ {
44			if list.Values[j].Pos().Line > line+1 {
45				break
46			}
47			line = list.Values[j].Pos().Line
48		}
49
50		nextPos := list.End()
51		if j < len(list.Values) {
52			nextPos = list.Values[j].Pos()
53		}
54		sortSubList(list.Values[i:j], nextPos, file)
55		i = j - 1
56	}
57}
58
59func ListIsSorted(list *List) bool {
60	for i := 0; i < len(list.Values); i++ {
61		// Find a set of values on contiguous lines
62		line := list.Values[i].Pos().Line
63		var j int
64		for j = i + 1; j < len(list.Values); j++ {
65			if list.Values[j].Pos().Line > line+1 {
66				break
67			}
68			line = list.Values[j].Pos().Line
69		}
70
71		if !subListIsSorted(list.Values[i:j]) {
72			return false
73		}
74		i = j - 1
75	}
76
77	return true
78}
79
80func sortListsInValue(value Expression, file *File) {
81	switch v := value.(type) {
82	case *Variable:
83		// Nothing
84	case *Operator:
85		sortListsInValue(v.Args[0], file)
86		sortListsInValue(v.Args[1], file)
87	case *Map:
88		for _, p := range v.Properties {
89			sortListsInValue(p.Value, file)
90		}
91	case *List:
92		SortList(file, v)
93	}
94}
95
96func sortSubList(values []Expression, nextPos scanner.Position, file *File) {
97	if !isListOfPrimitives(values) {
98		return
99	}
100	l := make(elemList, len(values))
101	for i, v := range values {
102		s, ok := v.(*String)
103		if !ok {
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{s.Value, i, v.Pos(), n}
111	}
112
113	sort.Sort(l)
114
115	copyValues := append([]Expression{}, values...)
116	copyComments := make([]*CommentGroup, len(file.Comments))
117	for i := range file.Comments {
118		cg := *file.Comments[i]
119		cg.Comments = make([]*Comment, len(cg.Comments))
120		for j := range file.Comments[i].Comments {
121			c := *file.Comments[i].Comments[j]
122			cg.Comments[j] = &c
123		}
124		copyComments[i] = &cg
125	}
126
127	curPos := values[0].Pos()
128	for i, e := range l {
129		values[i] = copyValues[e.i]
130		values[i].(*String).LiteralPos = curPos
131		for j, c := range copyComments {
132			if c.Pos().Offset > e.pos.Offset && c.Pos().Offset < e.nextPos.Offset {
133				file.Comments[j].Comments[0].Slash.Line = curPos.Line
134				file.Comments[j].Comments[0].Slash.Offset += values[i].Pos().Offset - e.pos.Offset
135			}
136		}
137
138		curPos.Offset += e.nextPos.Offset - e.pos.Offset
139		curPos.Line++
140	}
141}
142
143func subListIsSorted(values []Expression) bool {
144	if !isListOfPrimitives(values) {
145		return true
146	}
147	prev := ""
148	for _, v := range values {
149		s, ok := v.(*String)
150		if !ok {
151			panic("list contains non-string element")
152		}
153		if prev > s.Value {
154			return false
155		}
156		prev = s.Value
157	}
158
159	return true
160}
161
162type elem struct {
163	s       string
164	i       int
165	pos     scanner.Position
166	nextPos scanner.Position
167}
168
169type elemList []elem
170
171func (l elemList) Len() int {
172	return len(l)
173}
174
175func (l elemList) Swap(i, j int) {
176	l[i], l[j] = l[j], l[i]
177}
178
179func (l elemList) Less(i, j int) bool {
180	return l[i].s < l[j].s
181}
182
183type commentsByOffset []*CommentGroup
184
185func (l commentsByOffset) Len() int {
186	return len(l)
187}
188
189func (l commentsByOffset) Less(i, j int) bool {
190	return l[i].Pos().Offset < l[j].Pos().Offset
191}
192
193func (l commentsByOffset) Swap(i, j int) {
194	l[i], l[j] = l[j], l[i]
195}
196
197func isListOfPrimitives(values []Expression) bool {
198	if len(values) == 0 {
199		return true
200	}
201	switch values[0].Type() {
202	case BoolType, StringType, Int64Type:
203		return true
204	default:
205		return false
206	}
207}
208