Coverage Report

Created: 2019-05-19 14:56

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/lld/ELF/ScriptLexer.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ScriptLexer.cpp ----------------------------------------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file defines a lexer for the linker script.
10
//
11
// The linker script's grammar is not complex but ambiguous due to the
12
// lack of the formal specification of the language. What we are trying to
13
// do in this and other files in LLD is to make a "reasonable" linker
14
// script processor.
15
//
16
// Among simplicity, compatibility and efficiency, we put the most
17
// emphasis on simplicity when we wrote this lexer. Compatibility with the
18
// GNU linkers is important, but we did not try to clone every tiny corner
19
// case of their lexers, as even ld.bfd and ld.gold are subtly different
20
// in various corner cases. We do not care much about efficiency because
21
// the time spent in parsing linker scripts is usually negligible.
22
//
23
// Our grammar of the linker script is LL(2), meaning that it needs at
24
// most two-token lookahead to parse. The only place we need two-token
25
// lookahead is labels in version scripts, where we need to parse "local :"
26
// as if "local:".
27
//
28
// Overall, this lexer works fine for most linker scripts. There might
29
// be room for improving compatibility, but that's probably not at the
30
// top of our todo list.
31
//
32
//===----------------------------------------------------------------------===//
33
34
#include "ScriptLexer.h"
35
#include "lld/Common/ErrorHandler.h"
36
#include "llvm/ADT/Twine.h"
37
38
using namespace llvm;
39
using namespace lld;
40
using namespace lld::elf;
41
42
// Returns a whole line containing the current token.
43
128
StringRef ScriptLexer::getLine() {
44
128
  StringRef S = getCurrentMB().getBuffer();
45
128
  StringRef Tok = Tokens[Pos - 1];
46
128
47
128
  size_t Pos = S.rfind('\n', Tok.data() - S.data());
48
128
  if (Pos != StringRef::npos)
49
24
    S = S.substr(Pos + 1);
50
128
  return S.substr(0, S.find_first_of("\r\n"));
51
128
}
52
53
// Returns 1-based line number of the current token.
54
3.41k
size_t ScriptLexer::getLineNumber() {
55
3.41k
  StringRef S = getCurrentMB().getBuffer();
56
3.41k
  StringRef Tok = Tokens[Pos - 1];
57
3.41k
  return S.substr(0, Tok.data() - S.data()).count('\n') + 1;
58
3.41k
}
59
60
// Returns 0-based column number of the current token.
61
64
size_t ScriptLexer::getColumnNumber() {
62
64
  StringRef Tok = Tokens[Pos - 1];
63
64
  return Tok.data() - getLine().data();
64
64
}
65
66
3.41k
std::string ScriptLexer::getCurrentLocation() {
67
3.41k
  std::string Filename = getCurrentMB().getBufferIdentifier();
68
3.41k
  return (Filename + ":" + Twine(getLineNumber())).str();
69
3.41k
}
70
71
800
ScriptLexer::ScriptLexer(MemoryBufferRef MB) { tokenize(MB); }
72
73
// We don't want to record cascading errors. Keep only the first one.
74
85
void ScriptLexer::setError(const Twine &Msg) {
75
85
  if (errorCount())
76
21
    return;
77
64
78
64
  std::string S = (getCurrentLocation() + ": " + Msg).str();
79
64
  if (Pos)
80
64
    S += "\n>>> " + getLine().str() + "\n>>> " +
81
64
         std::string(getColumnNumber(), ' ') + "^";
82
64
  error(S);
83
64
}
84
85
// Split S into linker script tokens.
86
818
void ScriptLexer::tokenize(MemoryBufferRef MB) {
87
818
  std::vector<StringRef> Vec;
88
818
  MBs.push_back(MB);
89
818
  StringRef S = MB.getBuffer();
90
818
  StringRef Begin = S;
91
818
92
16.0k
  for (;;) {
93
16.0k
    S = skipSpace(S);
94
16.0k
    if (S.empty())
95
816
      break;
96
15.1k
97
15.1k
    // Quoted token. Note that double-quote characters are parts of a token
98
15.1k
    // because, in a glob match context, only unquoted tokens are interpreted
99
15.1k
    // as glob patterns. Double-quoted tokens are literal patterns in that
100
15.1k
    // context.
101
15.1k
    if (S.startswith("\"")) {
102
123
      size_t E = S.find("\"", 1);
103
123
      if (E == StringRef::npos) {
104
2
        StringRef Filename = MB.getBufferIdentifier();
105
2
        size_t Lineno = Begin.substr(0, S.data() - Begin.data()).count('\n');
106
2
        error(Filename + ":" + Twine(Lineno + 1) + ": unclosed quote");
107
2
        return;
108
2
      }
109
121
110
121
      Vec.push_back(S.take_front(E + 1));
111
121
      S = S.substr(E + 1);
112
121
      continue;
113
121
    }
114
15.0k
115
15.0k
    // ">foo" is parsed to ">" and "foo", but ">>" is parsed to ">>".
116
15.0k
    // "|", "||", "&" and "&&" are different operators.
117
15.0k
    if (S.startswith("<<") || 
S.startswith("<=")15.0k
||
S.startswith(">>")15.0k
||
118
15.0k
        
S.startswith(">=")15.0k
||
S.startswith("||")15.0k
||
S.startswith("&&")15.0k
) {
119
18
      Vec.push_back(S.substr(0, 2));
120
18
      S = S.substr(2);
121
18
      continue;
122
18
    }
123
15.0k
124
15.0k
    // Unquoted token. This is more relaxed than tokens in C-like language,
125
15.0k
    // so that you can write "file-name.cpp" as one bare token, for example.
126
15.0k
    size_t Pos = S.find_first_not_of(
127
15.0k
        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
128
15.0k
        "0123456789_.$/\\~=+[]*?-!^:");
129
15.0k
130
15.0k
    // A character that cannot start a word (which is usually a
131
15.0k
    // punctuation) forms a single character token.
132
15.0k
    if (Pos == 0)
133
7.05k
      Pos = 1;
134
15.0k
    Vec.push_back(S.substr(0, Pos));
135
15.0k
    S = S.substr(Pos);
136
15.0k
  }
137
818
138
818
  Tokens.insert(Tokens.begin() + Pos, Vec.begin(), Vec.end());
139
816
}
140
141
// Skip leading whitespace characters or comments.
142
16.0k
StringRef ScriptLexer::skipSpace(StringRef S) {
143
27.6k
  for (;;) {
144
27.6k
    if (S.startswith("/*")) {
145
5
      size_t E = S.find("*/", 2);
146
5
      if (E == StringRef::npos) {
147
2
        error("unclosed comment in a linker script");
148
2
        return "";
149
2
      }
150
3
      S = S.substr(E + 2);
151
3
      continue;
152
3
    }
153
27.6k
    if (S.startswith("#")) {
154
1.66k
      size_t E = S.find('\n', 1);
155
1.66k
      if (E == StringRef::npos)
156
3
        E = S.size() - 1;
157
1.66k
      S = S.substr(E + 1);
158
1.66k
      continue;
159
1.66k
    }
160
26.0k
    size_t Size = S.size();
161
26.0k
    S = S.ltrim();
162
26.0k
    if (S.size() == Size)
163
16.0k
      return S;
164
26.0k
  }
165
16.0k
}
166
167
// An erroneous token is handled as if it were the last token before EOF.
168
65.6k
bool ScriptLexer::atEOF() { return errorCount() || 
Tokens.size() == Pos65.5k
; }
169
170
// Split a given string as an expression.
171
// This function returns "3", "*" and "5" for "3*5" for example.
172
9.12k
static std::vector<StringRef> tokenizeExpr(StringRef S) {
173
9.12k
  StringRef Ops = "+-*/:!~"; // List of operators
174
9.12k
175
9.12k
  // Quoted strings are literal strings, so we don't want to split it.
176
9.12k
  if (S.startswith("\""))
177
5
    return {S};
178
9.11k
179
9.11k
  // Split S with operators as separators.
180
9.11k
  std::vector<StringRef> Ret;
181
9.74k
  while (!S.empty()) {
182
9.12k
    size_t E = S.find_first_of(Ops);
183
9.12k
184
9.12k
    // No need to split if there is no operator.
185
9.12k
    if (E == StringRef::npos) {
186
8.49k
      Ret.push_back(S);
187
8.49k
      break;
188
8.49k
    }
189
634
190
634
    // Get a token before the opreator.
191
634
    if (E != 0)
192
8
      Ret.push_back(S.substr(0, E));
193
634
194
634
    // Get the operator as a token. Keep != as one token.
195
634
    if (S.substr(E).startswith("!=")) {
196
7
      Ret.push_back(S.substr(E, 2));
197
7
      S = S.substr(E + 2);
198
627
    } else {
199
627
      Ret.push_back(S.substr(E, 1));
200
627
      S = S.substr(E + 1);
201
627
    }
202
634
  }
203
9.11k
  return Ret;
204
9.11k
}
205
206
// In contexts where expressions are expected, the lexer should apply
207
// different tokenization rules than the default one. By default,
208
// arithmetic operator characters are regular characters, but in the
209
// expression context, they should be independent tokens.
210
//
211
// For example, "foo*3" should be tokenized to "foo", "*" and "3" only
212
// in the expression context.
213
//
214
// This function may split the current token into multiple tokens.
215
53.0k
void ScriptLexer::maybeSplitExpr() {
216
53.0k
  if (!InExpr || 
errorCount()9.13k
||
atEOF()9.12k
)
217
43.9k
    return;
218
9.12k
219
9.12k
  std::vector<StringRef> V = tokenizeExpr(Tokens[Pos]);
220
9.12k
  if (V.size() == 1)
221
9.10k
    return;
222
12
  Tokens.erase(Tokens.begin() + Pos);
223
12
  Tokens.insert(Tokens.begin() + Pos, V.begin(), V.end());
224
12
}
225
226
53.0k
StringRef ScriptLexer::next() {
227
53.0k
  maybeSplitExpr();
228
53.0k
229
53.0k
  if (errorCount())
230
126
    return "";
231
52.9k
  if (atEOF()) {
232
9
    setError("unexpected EOF");
233
9
    return "";
234
9
  }
235
52.9k
  return Tokens[Pos++];
236
52.9k
}
237
238
37.9k
StringRef ScriptLexer::peek() {
239
37.9k
  StringRef Tok = next();
240
37.9k
  if (errorCount())
241
115
    return "";
242
37.8k
  Pos = Pos - 1;
243
37.8k
  return Tok;
244
37.8k
}
245
246
106
StringRef ScriptLexer::peek2() {
247
106
  skip();
248
106
  StringRef Tok = next();
249
106
  if (errorCount())
250
0
    return "";
251
106
  Pos = Pos - 2;
252
106
  return Tok;
253
106
}
254
255
23.8k
bool ScriptLexer::consume(StringRef Tok) {
256
23.8k
  if (peek() == Tok) {
257
3.03k
    skip();
258
3.03k
    return true;
259
3.03k
  }
260
20.8k
  return false;
261
20.8k
}
262
263
// Consumes Tok followed by ":". Space is allowed between Tok and ":".
264
555
bool ScriptLexer::consumeLabel(StringRef Tok) {
265
555
  if (consume((Tok + ":").str()))
266
129
    return true;
267
426
  if (Tokens.size() >= Pos + 2 && 
Tokens[Pos] == Tok424
&&
268
426
      
Tokens[Pos + 1] == ":"6
) {
269
5
    Pos += 2;
270
5
    return true;
271
5
  }
272
421
  return false;
273
421
}
274
275
3.32k
void ScriptLexer::skip() { (void)next(); }
276
277
5.30k
void ScriptLexer::expect(StringRef Expect) {
278
5.30k
  if (errorCount())
279
52
    return;
280
5.25k
  StringRef Tok = next();
281
5.25k
  if (Tok != Expect)
282
16
    setError(Expect + " expected, but got " + Tok);
283
5.25k
}
284
285
// Returns true if S encloses T.
286
7.03k
static bool encloses(StringRef S, StringRef T) {
287
7.03k
  return S.bytes_begin() <= T.bytes_begin() && 
T.bytes_end() <= S.bytes_end()7.02k
;
288
7.03k
}
289
290
6.96k
MemoryBufferRef ScriptLexer::getCurrentMB() {
291
6.96k
  // Find input buffer containing the current token.
292
6.96k
  assert(!MBs.empty() && Pos > 0);
293
6.96k
  for (MemoryBufferRef MB : MBs)
294
7.03k
    if (encloses(MB.getBuffer(), Tokens[Pos - 1]))
295
6.96k
      return MB;
296
6.96k
  
llvm_unreachable0
("getCurrentMB: failed to find a token");
297
}