Coverage Report

Created: 2019-07-24 05:18

/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
132
StringRef ScriptLexer::getLine() {
44
132
  StringRef s = getCurrentMB().getBuffer();
45
132
  StringRef tok = tokens[pos - 1];
46
132
47
132
  size_t pos = s.rfind('\n', tok.data() - s.data());
48
132
  if (pos != StringRef::npos)
49
24
    s = s.substr(pos + 1);
50
132
  return s.substr(0, s.find_first_of("\r\n"));
51
132
}
52
53
// Returns 1-based line number of the current token.
54
3.70k
size_t ScriptLexer::getLineNumber() {
55
3.70k
  StringRef s = getCurrentMB().getBuffer();
56
3.70k
  StringRef tok = tokens[pos - 1];
57
3.70k
  return s.substr(0, tok.data() - s.data()).count('\n') + 1;
58
3.70k
}
59
60
// Returns 0-based column number of the current token.
61
66
size_t ScriptLexer::getColumnNumber() {
62
66
  StringRef tok = tokens[pos - 1];
63
66
  return tok.data() - getLine().data();
64
66
}
65
66
3.70k
std::string ScriptLexer::getCurrentLocation() {
67
3.70k
  std::string filename = getCurrentMB().getBufferIdentifier();
68
3.70k
  return (filename + ":" + Twine(getLineNumber())).str();
69
3.70k
}
70
71
908
ScriptLexer::ScriptLexer(MemoryBufferRef mb) { tokenize(mb); }
72
73
// We don't want to record cascading errors. Keep only the first one.
74
88
void ScriptLexer::setError(const Twine &msg) {
75
88
  if (errorCount())
76
22
    return;
77
66
78
66
  std::string s = (getCurrentLocation() + ": " + msg).str();
79
66
  if (pos)
80
66
    s += "\n>>> " + getLine().str() + "\n>>> " +
81
66
         std::string(getColumnNumber(), ' ') + "^";
82
66
  error(s);
83
66
}
84
85
// Split S into linker script tokens.
86
926
void ScriptLexer::tokenize(MemoryBufferRef mb) {
87
926
  std::vector<StringRef> vec;
88
926
  mbs.push_back(mb);
89
926
  StringRef s = mb.getBuffer();
90
926
  StringRef begin = s;
91
926
92
16.4k
  for (;;) {
93
16.4k
    s = skipSpace(s);
94
16.4k
    if (s.empty())
95
923
      break;
96
15.5k
97
15.5k
    // Quoted token. Note that double-quote characters are parts of a token
98
15.5k
    // because, in a glob match context, only unquoted tokens are interpreted
99
15.5k
    // as glob patterns. Double-quoted tokens are literal patterns in that
100
15.5k
    // context.
101
15.5k
    if (s.startswith("\"")) {
102
124
      size_t e = s.find("\"", 1);
103
124
      if (e == StringRef::npos) {
104
3
        StringRef filename = mb.getBufferIdentifier();
105
3
        size_t lineno = begin.substr(0, s.data() - begin.data()).count('\n');
106
3
        error(filename + ":" + Twine(lineno + 1) + ": unclosed quote");
107
3
        return;
108
3
      }
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.4k
115
15.4k
    // ">foo" is parsed to ">" and "foo", but ">>" is parsed to ">>".
116
15.4k
    // "|", "||", "&" and "&&" are different operators.
117
15.4k
    if (s.startswith("<<") || 
s.startswith("<=")15.4k
||
s.startswith(">>")15.4k
||
118
15.4k
        
s.startswith(">=")15.4k
||
s.startswith("||")15.4k
||
s.startswith("&&")15.4k
) {
119
21
      vec.push_back(s.substr(0, 2));
120
21
      s = s.substr(2);
121
21
      continue;
122
21
    }
123
15.4k
124
15.4k
    // Unquoted token. This is more relaxed than tokens in C-like language,
125
15.4k
    // so that you can write "file-name.cpp" as one bare token, for example.
126
15.4k
    size_t pos = s.find_first_not_of(
127
15.4k
        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
128
15.4k
        "0123456789_.$/\\~=+[]*?-!^:");
129
15.4k
130
15.4k
    // A character that cannot start a word (which is usually a
131
15.4k
    // punctuation) forms a single character token.
132
15.4k
    if (pos == 0)
133
7.19k
      pos = 1;
134
15.4k
    vec.push_back(s.substr(0, pos));
135
15.4k
    s = s.substr(pos);
136
15.4k
  }
137
926
138
926
  tokens.insert(tokens.begin() + pos, vec.begin(), vec.end());
139
923
}
140
141
// Skip leading whitespace characters or comments.
142
16.4k
StringRef ScriptLexer::skipSpace(StringRef s) {
143
28.3k
  for (;;) {
144
28.3k
    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
28.3k
    if (s.startswith("#")) {
154
1.69k
      size_t e = s.find('\n', 1);
155
1.69k
      if (e == StringRef::npos)
156
3
        e = s.size() - 1;
157
1.69k
      s = s.substr(e + 1);
158
1.69k
      continue;
159
1.69k
    }
160
26.6k
    size_t size = s.size();
161
26.6k
    s = s.ltrim();
162
26.6k
    if (s.size() == size)
163
16.4k
      return s;
164
26.6k
  }
165
16.4k
}
166
167
// An erroneous token is handled as if it were the last token before EOF.
168
69.2k
bool ScriptLexer::atEOF() { return errorCount() || 
tokens.size() == pos69.0k
; }
169
170
// Split a given string as an expression.
171
// This function returns "3", "*" and "5" for "3*5" for example.
172
10.3k
static std::vector<StringRef> tokenizeExpr(StringRef s) {
173
10.3k
  StringRef ops = "+-*/:!~=<>"; // List of operators
174
10.3k
175
10.3k
  // Quoted strings are literal strings, so we don't want to split it.
176
10.3k
  if (s.startswith("\""))
177
5
    return {s};
178
10.3k
179
10.3k
  // Split S with operators as separators.
180
10.3k
  std::vector<StringRef> ret;
181
11.3k
  while (!s.empty()) {
182
10.4k
    size_t e = s.find_first_of(ops);
183
10.4k
184
10.4k
    // No need to split if there is no operator.
185
10.4k
    if (e == StringRef::npos) {
186
9.44k
      ret.push_back(s);
187
9.44k
      break;
188
9.44k
    }
189
1.02k
190
1.02k
    // Get a token before the opreator.
191
1.02k
    if (e != 0)
192
77
      ret.push_back(s.substr(0, e));
193
1.02k
194
1.02k
    // Get the operator as a token.
195
1.02k
    // Keep !=, ==, >=, <=, << and >> operators as a single tokens.
196
1.02k
    if (s.substr(e).startswith("!=") || 
s.substr(e).startswith("==")1.01k
||
197
1.02k
        
s.substr(e).startswith(">=")1.00k
||
s.substr(e).startswith("<=")999
||
198
1.02k
        
s.substr(e).startswith("<<")996
||
s.substr(e).startswith(">>")977
) {
199
47
      ret.push_back(s.substr(e, 2));
200
47
      s = s.substr(e + 2);
201
974
    } else {
202
974
      ret.push_back(s.substr(e, 1));
203
974
      s = s.substr(e + 1);
204
974
    }
205
1.02k
  }
206
10.3k
  return ret;
207
10.3k
}
208
209
// In contexts where expressions are expected, the lexer should apply
210
// different tokenization rules than the default one. By default,
211
// arithmetic operator characters are regular characters, but in the
212
// expression context, they should be independent tokens.
213
//
214
// For example, "foo*3" should be tokenized to "foo", "*" and "3" only
215
// in the expression context.
216
//
217
// This function may split the current token into multiple tokens.
218
54.9k
void ScriptLexer::maybeSplitExpr() {
219
54.9k
  if (!inExpr || 
errorCount()10.3k
||
atEOF()10.3k
)
220
44.5k
    return;
221
10.3k
222
10.3k
  std::vector<StringRef> v = tokenizeExpr(tokens[pos]);
223
10.3k
  if (v.size() == 1)
224
10.3k
    return;
225
73
  tokens.erase(tokens.begin() + pos);
226
73
  tokens.insert(tokens.begin() + pos, v.begin(), v.end());
227
73
}
228
229
54.9k
StringRef ScriptLexer::next() {
230
54.9k
  maybeSplitExpr();
231
54.9k
232
54.9k
  if (errorCount())
233
139
    return "";
234
54.8k
  if (atEOF()) {
235
9
    setError("unexpected EOF");
236
9
    return "";
237
9
  }
238
54.8k
  return tokens[pos++];
239
54.8k
}
240
241
39.3k
StringRef ScriptLexer::peek() {
242
39.3k
  StringRef tok = next();
243
39.3k
  if (errorCount())
244
127
    return "";
245
39.2k
  pos = pos - 1;
246
39.2k
  return tok;
247
39.2k
}
248
249
106
StringRef ScriptLexer::peek2() {
250
106
  skip();
251
106
  StringRef tok = next();
252
106
  if (errorCount())
253
0
    return "";
254
106
  pos = pos - 2;
255
106
  return tok;
256
106
}
257
258
24.0k
bool ScriptLexer::consume(StringRef tok) {
259
24.0k
  if (peek() == tok) {
260
3.10k
    skip();
261
3.10k
    return true;
262
3.10k
  }
263
20.9k
  return false;
264
20.9k
}
265
266
// Consumes Tok followed by ":". Space is allowed between Tok and ":".
267
606
bool ScriptLexer::consumeLabel(StringRef tok) {
268
606
  if (consume((tok + ":").str()))
269
140
    return true;
270
466
  if (tokens.size() >= pos + 2 && 
tokens[pos] == tok464
&&
271
466
      
tokens[pos + 1] == ":"6
) {
272
5
    pos += 2;
273
5
    return true;
274
5
  }
275
461
  return false;
276
461
}
277
278
3.46k
void ScriptLexer::skip() { (void)next(); }
279
280
5.40k
void ScriptLexer::expect(StringRef expect) {
281
5.40k
  if (errorCount())
282
53
    return;
283
5.34k
  StringRef tok = next();
284
5.34k
  if (tok != expect)
285
17
    setError(expect + " expected, but got " + tok);
286
5.34k
}
287
288
// Returns true if S encloses T.
289
7.61k
static bool encloses(StringRef s, StringRef t) {
290
7.61k
  return s.bytes_begin() <= t.bytes_begin() && 
t.bytes_end() <= s.bytes_end()7.60k
;
291
7.61k
}
292
293
7.54k
MemoryBufferRef ScriptLexer::getCurrentMB() {
294
7.54k
  // Find input buffer containing the current token.
295
7.54k
  assert(!mbs.empty() && pos > 0);
296
7.54k
  for (MemoryBufferRef mb : mbs)
297
7.61k
    if (encloses(mb.getBuffer(), tokens[pos - 1]))
298
7.54k
      return mb;
299
7.54k
  
llvm_unreachable0
("getCurrentMB: failed to find a token");
300
}