Coverage Report

Created: 2018-06-25 02:00

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