1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "gn/tokenizer.h"
6
7 #include "base/logging.h"
8 #include "base/strings/string_util.h"
9 #include "gn/input_file.h"
10
11 namespace {
12
CouldBeTwoCharOperatorBegin(char c)13 bool CouldBeTwoCharOperatorBegin(char c) {
14 return c == '<' || c == '>' || c == '!' || c == '=' || c == '-' || c == '+' ||
15 c == '|' || c == '&';
16 }
17
CouldBeTwoCharOperatorEnd(char c)18 bool CouldBeTwoCharOperatorEnd(char c) {
19 return c == '=' || c == '|' || c == '&';
20 }
21
CouldBeOneCharOperator(char c)22 bool CouldBeOneCharOperator(char c) {
23 return c == '=' || c == '<' || c == '>' || c == '+' || c == '!' || c == ':' ||
24 c == '|' || c == '&' || c == '-';
25 }
26
CouldBeOperator(char c)27 bool CouldBeOperator(char c) {
28 return CouldBeOneCharOperator(c) || CouldBeTwoCharOperatorBegin(c);
29 }
30
IsScoperChar(char c)31 bool IsScoperChar(char c) {
32 return c == '(' || c == ')' || c == '[' || c == ']' || c == '{' || c == '}';
33 }
34
GetSpecificOperatorType(std::string_view value)35 Token::Type GetSpecificOperatorType(std::string_view value) {
36 if (value == "=")
37 return Token::EQUAL;
38 if (value == "+")
39 return Token::PLUS;
40 if (value == "-")
41 return Token::MINUS;
42 if (value == "+=")
43 return Token::PLUS_EQUALS;
44 if (value == "-=")
45 return Token::MINUS_EQUALS;
46 if (value == "==")
47 return Token::EQUAL_EQUAL;
48 if (value == "!=")
49 return Token::NOT_EQUAL;
50 if (value == "<=")
51 return Token::LESS_EQUAL;
52 if (value == ">=")
53 return Token::GREATER_EQUAL;
54 if (value == "<")
55 return Token::LESS_THAN;
56 if (value == ">")
57 return Token::GREATER_THAN;
58 if (value == "&&")
59 return Token::BOOLEAN_AND;
60 if (value == "||")
61 return Token::BOOLEAN_OR;
62 if (value == "!")
63 return Token::BANG;
64 if (value == ".")
65 return Token::DOT;
66 return Token::INVALID;
67 }
68
69 } // namespace
70
Tokenizer(const InputFile * input_file,Err * err,WhitespaceTransform whitespace_transform)71 Tokenizer::Tokenizer(const InputFile* input_file,
72 Err* err,
73 WhitespaceTransform whitespace_transform)
74 : input_file_(input_file),
75 input_(input_file->contents()),
76 err_(err),
77 whitespace_transform_(whitespace_transform) {}
78
79 Tokenizer::~Tokenizer() = default;
80
81 // static
Tokenize(const InputFile * input_file,Err * err,WhitespaceTransform whitespace_transform)82 std::vector<Token> Tokenizer::Tokenize(
83 const InputFile* input_file,
84 Err* err,
85 WhitespaceTransform whitespace_transform) {
86 Tokenizer t(input_file, err, whitespace_transform);
87 return t.Run();
88 }
89
Run()90 std::vector<Token> Tokenizer::Run() {
91 DCHECK(tokens_.empty());
92 while (!done()) {
93 AdvanceToNextToken();
94 if (done())
95 break;
96 Location location = GetCurrentLocation();
97
98 Token::Type type = ClassifyCurrent();
99 if (type == Token::INVALID) {
100 *err_ = GetErrorForInvalidToken(location);
101 break;
102 }
103 size_t token_begin = cur_;
104 AdvanceToEndOfToken(location, type);
105 if (has_error())
106 break;
107 size_t token_end = cur_;
108
109 std::string_view token_value(&input_.data()[token_begin],
110 token_end - token_begin);
111
112 if (type == Token::UNCLASSIFIED_OPERATOR) {
113 type = GetSpecificOperatorType(token_value);
114 } else if (type == Token::IDENTIFIER) {
115 if (token_value == "if")
116 type = Token::IF;
117 else if (token_value == "else")
118 type = Token::ELSE;
119 else if (token_value == "true")
120 type = Token::TRUE_TOKEN;
121 else if (token_value == "false")
122 type = Token::FALSE_TOKEN;
123 } else if (type == Token::UNCLASSIFIED_COMMENT) {
124 if (AtStartOfLine(token_begin) &&
125 // If it's a standalone comment, but is a continuation of a comment on
126 // a previous line, then instead make it a continued suffix comment.
127 (tokens_.empty() || tokens_.back().type() != Token::SUFFIX_COMMENT ||
128 tokens_.back().location().line_number() + 1 !=
129 location.line_number() ||
130 tokens_.back().location().column_number() !=
131 location.column_number())) {
132 type = Token::LINE_COMMENT;
133 if (!at_end()) // Could be EOF.
134 Advance(); // The current \n.
135 // If this comment is separated from the next syntax element, then we
136 // want to tag it as a block comment. This will become a standalone
137 // statement at the parser level to keep this comment separate, rather
138 // than attached to the subsequent statement.
139 while (!at_end() && IsCurrentWhitespace()) {
140 if (IsCurrentNewline()) {
141 type = Token::BLOCK_COMMENT;
142 break;
143 }
144 Advance();
145 }
146 } else {
147 type = Token::SUFFIX_COMMENT;
148 }
149 }
150
151 tokens_.push_back(Token(location, type, token_value));
152 }
153 if (err_->has_error())
154 tokens_.clear();
155 return tokens_;
156 }
157
158 // static
ByteOffsetOfNthLine(const std::string_view & buf,int n)159 size_t Tokenizer::ByteOffsetOfNthLine(const std::string_view& buf, int n) {
160 DCHECK_GT(n, 0);
161
162 if (n == 1)
163 return 0;
164
165 int cur_line = 1;
166 size_t cur_byte = 0;
167 while (cur_byte < buf.size()) {
168 if (IsNewline(buf, cur_byte)) {
169 cur_line++;
170 if (cur_line == n)
171 return cur_byte + 1;
172 }
173 cur_byte++;
174 }
175 return static_cast<size_t>(-1);
176 }
177
178 // static
IsNewline(const std::string_view & buffer,size_t offset)179 bool Tokenizer::IsNewline(const std::string_view& buffer, size_t offset) {
180 DCHECK(offset < buffer.size());
181 // We may need more logic here to handle different line ending styles.
182 return buffer[offset] == '\n';
183 }
184
185 // static
IsIdentifierFirstChar(char c)186 bool Tokenizer::IsIdentifierFirstChar(char c) {
187 return base::IsAsciiAlpha(c) || c == '_';
188 }
189
190 // static
IsIdentifierContinuingChar(char c)191 bool Tokenizer::IsIdentifierContinuingChar(char c) {
192 // Also allow digits after the first char.
193 return IsIdentifierFirstChar(c) || base::IsAsciiDigit(c);
194 }
195
AdvanceToNextToken()196 void Tokenizer::AdvanceToNextToken() {
197 while (!at_end() && IsCurrentWhitespace())
198 Advance();
199 }
200
ClassifyCurrent() const201 Token::Type Tokenizer::ClassifyCurrent() const {
202 DCHECK(!at_end());
203 char next_char = cur_char();
204 if (base::IsAsciiDigit(next_char))
205 return Token::INTEGER;
206 if (next_char == '"')
207 return Token::STRING;
208
209 // Note: '-' handled specially below.
210 if (next_char != '-' && CouldBeOperator(next_char))
211 return Token::UNCLASSIFIED_OPERATOR;
212
213 if (IsIdentifierFirstChar(next_char))
214 return Token::IDENTIFIER;
215
216 if (next_char == '[')
217 return Token::LEFT_BRACKET;
218 if (next_char == ']')
219 return Token::RIGHT_BRACKET;
220 if (next_char == '(')
221 return Token::LEFT_PAREN;
222 if (next_char == ')')
223 return Token::RIGHT_PAREN;
224 if (next_char == '{')
225 return Token::LEFT_BRACE;
226 if (next_char == '}')
227 return Token::RIGHT_BRACE;
228
229 if (next_char == '.')
230 return Token::DOT;
231 if (next_char == ',')
232 return Token::COMMA;
233
234 if (next_char == '#')
235 return Token::UNCLASSIFIED_COMMENT;
236
237 // For the case of '-' differentiate between a negative number and anything
238 // else.
239 if (next_char == '-') {
240 if (!CanIncrement())
241 return Token::UNCLASSIFIED_OPERATOR; // Just the minus before end of
242 // file.
243 char following_char = input_[cur_ + 1];
244 if (base::IsAsciiDigit(following_char))
245 return Token::INTEGER;
246 return Token::UNCLASSIFIED_OPERATOR;
247 }
248
249 return Token::INVALID;
250 }
251
AdvanceToEndOfToken(const Location & location,Token::Type type)252 void Tokenizer::AdvanceToEndOfToken(const Location& location,
253 Token::Type type) {
254 switch (type) {
255 case Token::INTEGER:
256 do {
257 Advance();
258 } while (!at_end() && base::IsAsciiDigit(cur_char()));
259 if (!at_end()) {
260 // Require the char after a number to be some kind of space, scope,
261 // or operator.
262 char c = cur_char();
263 if (!IsCurrentWhitespace() && !CouldBeOperator(c) && !IsScoperChar(c) &&
264 c != ',') {
265 *err_ = Err(GetCurrentLocation(), "This is not a valid number.");
266 // Highlight the number.
267 err_->AppendRange(LocationRange(location, GetCurrentLocation()));
268 }
269 }
270 break;
271
272 case Token::STRING: {
273 char initial = cur_char();
274 Advance(); // Advance past initial "
275 for (;;) {
276 if (at_end()) {
277 *err_ = Err(LocationRange(location, GetCurrentLocation()),
278 "Unterminated string literal.",
279 "Don't leave me hanging like this!");
280 break;
281 }
282 if (IsCurrentStringTerminator(initial)) {
283 Advance(); // Skip past last "
284 break;
285 } else if (IsCurrentNewline()) {
286 *err_ = Err(LocationRange(location, GetCurrentLocation()),
287 "Newline in string constant.");
288 }
289 Advance();
290 }
291 break;
292 }
293
294 case Token::UNCLASSIFIED_OPERATOR:
295 // Some operators are two characters, some are one.
296 if (CouldBeTwoCharOperatorBegin(cur_char())) {
297 if (CanIncrement() && CouldBeTwoCharOperatorEnd(input_[cur_ + 1]))
298 Advance();
299 }
300 Advance();
301 break;
302
303 case Token::IDENTIFIER:
304 while (!at_end() && IsIdentifierContinuingChar(cur_char()))
305 Advance();
306 break;
307
308 case Token::LEFT_BRACKET:
309 case Token::RIGHT_BRACKET:
310 case Token::LEFT_BRACE:
311 case Token::RIGHT_BRACE:
312 case Token::LEFT_PAREN:
313 case Token::RIGHT_PAREN:
314 case Token::DOT:
315 case Token::COMMA:
316 Advance(); // All are one char.
317 break;
318
319 case Token::UNCLASSIFIED_COMMENT:
320 // Eat to EOL.
321 while (!at_end() && !IsCurrentNewline())
322 Advance();
323 break;
324
325 case Token::INVALID:
326 default:
327 *err_ = Err(location, "Everything is all messed up",
328 "Please insert system disk in drive A: and press any key.");
329 NOTREACHED();
330 return;
331 }
332 }
333
AtStartOfLine(size_t location) const334 bool Tokenizer::AtStartOfLine(size_t location) const {
335 while (location > 0) {
336 --location;
337 char c = input_[location];
338 if (c == '\n')
339 return true;
340 if (c != ' ')
341 return false;
342 }
343 return true;
344 }
345
IsCurrentWhitespace() const346 bool Tokenizer::IsCurrentWhitespace() const {
347 DCHECK(!at_end());
348 char c = input_[cur_];
349 // Note that tab (0x09), vertical tab (0x0B), and formfeed (0x0C) are illegal.
350 return c == 0x0A || c == 0x0D || c == 0x20 ||
351 (whitespace_transform_ == WhitespaceTransform::kInvalidToSpace &&
352 (c == 0x09 || c == 0x0B || c == 0x0C));
353 }
354
IsCurrentStringTerminator(char quote_char) const355 bool Tokenizer::IsCurrentStringTerminator(char quote_char) const {
356 DCHECK(!at_end());
357 if (cur_char() != quote_char)
358 return false;
359
360 // Check for escaping. \" is not a string terminator, but \\" is. Count
361 // the number of preceding backslashes.
362 int num_backslashes = 0;
363 for (int i = static_cast<int>(cur_) - 1; i >= 0 && input_[i] == '\\'; i--)
364 num_backslashes++;
365
366 // Even backslashes mean that they were escaping each other and don't count
367 // as escaping this quote.
368 return (num_backslashes % 2) == 0;
369 }
370
IsCurrentNewline() const371 bool Tokenizer::IsCurrentNewline() const {
372 return IsNewline(input_, cur_);
373 }
374
Advance()375 void Tokenizer::Advance() {
376 DCHECK(cur_ < input_.size());
377 if (IsCurrentNewline()) {
378 line_number_++;
379 column_number_ = 1;
380 } else {
381 column_number_++;
382 }
383 cur_++;
384 }
385
GetCurrentLocation() const386 Location Tokenizer::GetCurrentLocation() const {
387 return Location(input_file_, line_number_, column_number_,
388 static_cast<int>(cur_));
389 }
390
GetErrorForInvalidToken(const Location & location) const391 Err Tokenizer::GetErrorForInvalidToken(const Location& location) const {
392 std::string help;
393 if (cur_char() == ';') {
394 // Semicolon.
395 help = "Semicolons are not needed, delete this one.";
396 } else if (cur_char() == '\t') {
397 // Tab.
398 help =
399 "You got a tab character in here. Tabs are evil. "
400 "Convert to spaces.";
401 } else if (cur_char() == '/' && cur_ + 1 < input_.size() &&
402 (input_[cur_ + 1] == '/' || input_[cur_ + 1] == '*')) {
403 // Different types of comments.
404 help = "Comments should start with # instead";
405 } else if (cur_char() == '\'') {
406 help = "Strings are delimited by \" characters, not apostrophes.";
407 } else {
408 help = "I have no idea what this is.";
409 }
410
411 return Err(location, "Invalid token.", help);
412 }
413