blob: ab8a1859bc5101f7e3fcb3c3c0bde6c4b15e17b6 [file] [log] [blame]
Shinichiro Hamaji776ca302015-06-06 03:52:48 +09001#include "parser.h"
2
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +09003#include <stack>
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +09004#include <unordered_map>
5
Shinichiro Hamaji776ca302015-06-06 03:52:48 +09006#include "ast.h"
7#include "file.h"
8#include "loc.h"
9#include "log.h"
10#include "string_piece.h"
Shinichiro Hamaji810fd032015-06-17 04:38:03 +090011#include "strutil.h"
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090012#include "value.h"
13
14enum struct ParserState {
15 NOT_AFTER_RULE = 0,
16 AFTER_RULE,
17 MAYBE_AFTER_RULE,
18};
19
20class Parser {
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +090021 struct IfState {
22 IfAST* ast;
23 bool is_in_else;
24 int num_nest;
25 };
26
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +090027 typedef void (Parser::*DirectiveHandler)(
28 StringPiece line, StringPiece directive);
29 typedef unordered_map<StringPiece, DirectiveHandler> DirectiveMap;
30
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090031 public:
32 Parser(StringPiece buf, const char* filename, vector<AST*>* asts)
33 : buf_(buf),
34 state_(ParserState::NOT_AFTER_RULE),
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +090035 asts_(asts),
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090036 out_asts_(asts),
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +090037 num_if_nest_(0),
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090038 loc_(filename, 0),
39 fixed_lineno_(false) {
40 }
41
Shinichiro Hamaji80456fb2015-06-18 14:56:10 +090042 Parser(StringPiece buf, const Loc& loc, vector<AST*>* asts)
43 : buf_(buf),
44 state_(ParserState::NOT_AFTER_RULE),
45 asts_(asts),
46 out_asts_(asts),
47 num_if_nest_(0),
48 loc_(loc),
49 fixed_lineno_(true) {
50 }
51
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090052 ~Parser() {
53 }
54
55 void Parse() {
56 l_ = 0;
57
58 for (l_ = 0; l_ < buf_.size();) {
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090059 size_t lf_cnt = 0;
60 size_t e = FindEndOfLine(&lf_cnt);
Shinichiro Hamaji8ee8c372015-06-16 16:19:40 +090061 if (!fixed_lineno_)
62 loc_.lineno += lf_cnt;
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090063 StringPiece line(buf_.data() + l_, e - l_);
64 ParseLine(line);
65 if (e == buf_.size())
66 break;
67
68 l_ = e + 1;
Shinichiro Hamaji776ca302015-06-06 03:52:48 +090069 }
70 }
71
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +090072 static void Init() {
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +090073 make_directives_ = new DirectiveMap;
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +090074 (*make_directives_)["include"] = &Parser::ParseInclude;
75 (*make_directives_)["-include"] = &Parser::ParseInclude;
76 (*make_directives_)["sinclude"] = &Parser::ParseInclude;
Shinichiro Hamaji810fd032015-06-17 04:38:03 +090077 (*make_directives_)["define"] = &Parser::ParseDefine;
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +090078 (*make_directives_)["ifdef"] = &Parser::ParseIfdef;
79 (*make_directives_)["ifndef"] = &Parser::ParseIfdef;
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +090080 (*make_directives_)["ifeq"] = &Parser::ParseIfeq;
81 (*make_directives_)["ifneq"] = &Parser::ParseIfeq;
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +090082 (*make_directives_)["else"] = &Parser::ParseElse;
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +090083 (*make_directives_)["endif"] = &Parser::ParseEndif;
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +090084
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +090085 else_if_directives_ = new DirectiveMap;
86 (*else_if_directives_)["ifdef"] = &Parser::ParseIfdef;
87 (*else_if_directives_)["ifndef"] = &Parser::ParseIfdef;
88
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +090089 shortest_directive_len_ = 9999;
90 longest_directive_len_ = 0;
91 for (auto p : *make_directives_) {
92 size_t len = p.first.size();
93 shortest_directive_len_ = min(len, shortest_directive_len_);
94 longest_directive_len_ = max(len, longest_directive_len_);
95 }
96 }
97
98 static void Quit() {
99 delete make_directives_;
100 }
101
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900102 private:
103 void Error(const string& msg) {
Shinichiro Hamaji8ee8c372015-06-16 16:19:40 +0900104 ERROR("%s:%d: %s", LOCF(loc_), msg.c_str());
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900105 }
106
107 size_t FindEndOfLine(size_t* lf_cnt) {
108 size_t e = l_;
109 bool prev_backslash = false;
110 for (; e < buf_.size(); e++) {
111 char c = buf_[e];
112 if (c == '\\') {
113 prev_backslash = !prev_backslash;
114 } else if (c == '\n') {
115 ++*lf_cnt;
116 if (!prev_backslash) {
117 return e;
118 }
119 } else if (c != '\r') {
120 prev_backslash = false;
121 }
122 }
123 return e;
124 }
125
126 void ParseLine(StringPiece line) {
127 if (line.empty() || (line.size() == 1 && line[0] == '\r'))
128 return;
129
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900130 if (!define_name_.empty()) {
131 ParseInsideDefine(line);
132 return;
133 }
134
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900135 if (line[0] == '\t' && state_ != ParserState::NOT_AFTER_RULE) {
136 CommandAST* ast = new CommandAST();
137 ast->expr = ParseExpr(line.substr(1), true);
138 out_asts_->push_back(ast);
139 return;
140 }
141
Shinichiro Hamaji32750622015-06-17 14:57:33 +0900142 line = TrimLeftSpace(line);
Shinichiro Hamajid4e81932015-06-17 04:40:45 +0900143
144 if (line[0] == '#')
145 return;
146
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +0900147 if (HandleDirective(line, make_directives_)) {
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900148 return;
149 }
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900150
151 size_t sep = line.find_first_of(STRING_PIECE("=:"));
152 if (sep == string::npos) {
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +0900153 ParseRule(line, sep);
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900154 } else if (line[sep] == '=') {
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +0900155 ParseAssign(line, sep);
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900156 } else if (line.get(sep+1) == '=') {
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +0900157 ParseAssign(line, sep+1);
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900158 } else if (line[sep] == ':') {
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +0900159 ParseRule(line, sep);
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900160 } else {
161 CHECK(false);
162 }
163 }
164
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +0900165 void ParseRule(StringPiece line, size_t sep) {
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900166 const bool is_rule = line.find(':') != string::npos;
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900167 RuleAST* ast = new RuleAST();
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900168 ast->set_loc(loc_);
169
170 size_t found = line.substr(sep + 1).find_first_of("=;");
171 if (found != string::npos) {
172 found += sep + 1;
173 ast->term = line[found];
Shinichiro Hamaji32750622015-06-17 14:57:33 +0900174 ast->after_term = ParseExpr(TrimLeftSpace(line.substr(found + 1)),
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900175 ast->term == ';');
Shinichiro Hamaji32750622015-06-17 14:57:33 +0900176 ast->expr = ParseExpr(TrimSpace(line.substr(0, found)), false);
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900177 } else {
178 ast->term = 0;
179 ast->after_term = NULL;
Shinichiro Hamaji32750622015-06-17 14:57:33 +0900180 ast->expr = ParseExpr(TrimSpace(line), false);
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900181 }
182 out_asts_->push_back(ast);
183 state_ = is_rule ? ParserState::AFTER_RULE : ParserState::MAYBE_AFTER_RULE;
184 }
185
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +0900186 void ParseAssign(StringPiece line, size_t sep) {
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900187 if (sep == 0)
188 Error("*** empty variable name ***");
189 AssignOp op = AssignOp::EQ;
190 size_t lhs_end = sep;
191 switch (line[sep-1]) {
192 case ':':
193 lhs_end--;
194 op = AssignOp::COLON_EQ;
195 break;
196 case '+':
197 lhs_end--;
198 op = AssignOp::PLUS_EQ;
199 break;
200 case '?':
201 lhs_end--;
202 op = AssignOp::QUESTION_EQ;
203 break;
204 }
205
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900206 AssignAST* ast = new AssignAST();
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900207 ast->set_loc(loc_);
Shinichiro Hamaji32750622015-06-17 14:57:33 +0900208 ast->lhs = ParseExpr(TrimSpace(line.substr(0, lhs_end)), false);
209 ast->rhs = ParseExpr(TrimSpace(line.substr(sep + 1)), false);
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900210 ast->op = op;
211 ast->directive = AssignDirective::NONE;
212 out_asts_->push_back(ast);
213 state_ = ParserState::NOT_AFTER_RULE;
214 }
215
Shinichiro Hamaji14b8bea2015-06-17 03:14:28 +0900216 void ParseInclude(StringPiece line, StringPiece directive) {
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900217 IncludeAST* ast = new IncludeAST();
218 ast->expr = ParseExpr(line, false);
Shinichiro Hamajiefad2dd2015-06-17 03:08:02 +0900219 ast->should_exist = directive[0] == 'i';
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900220 out_asts_->push_back(ast);
221 }
222
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900223 void ParseDefine(StringPiece line, StringPiece) {
224 if (line.empty()) {
225 Error("*** empty variable name.");
226 }
227 define_name_ = line;
228 define_start_ = 0;
229 define_start_line_ = loc_.lineno;
230 }
231
232 void ParseInsideDefine(StringPiece line) {
Shinichiro Hamaji5562caf2015-06-17 17:08:40 +0900233 line = TrimLeftSpace(line);
234 if (GetDirective(line) != "endef") {
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900235 if (define_start_ == 0)
236 define_start_ = l_;
237 return;
238 }
239
Shinichiro Hamaji5562caf2015-06-17 17:08:40 +0900240 StringPiece rest = TrimRightSpace(RemoveComment(TrimLeftSpace(
241 line.substr(sizeof("endef")))));
242 if (!rest.empty()) {
243 WARN("%s:%d: extraneous text after `endef' directive", LOCF(loc_));
244 }
245
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900246 AssignAST* ast = new AssignAST();
247 ast->set_loc(Loc(loc_.filename, define_start_line_));
248 ast->lhs = ParseExpr(define_name_, false);
249 StringPiece rhs;
250 if (define_start_)
Shinichiro Hamaji32750622015-06-17 14:57:33 +0900251 rhs = TrimRightSpace(buf_.substr(define_start_, l_ - define_start_));
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900252 ast->rhs = ParseExpr(rhs, false);
253 ast->op = AssignOp::EQ;
254 ast->directive = AssignDirective::NONE;
255 out_asts_->push_back(ast);
256 define_name_.clear();
257 }
258
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +0900259 void EnterIf(IfAST* ast) {
260 IfState* st = new IfState();
261 st->ast = ast;
262 st->is_in_else = false;
263 st->num_nest = num_if_nest_;
264 if_stack_.push(st);
265 out_asts_ = &ast->true_asts;
266 }
267
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900268 void ParseIfdef(StringPiece line, StringPiece directive) {
269 IfAST* ast = new IfAST();
270 ast->set_loc(loc_);
271 ast->op = directive[2] == 'n' ? CondOp::IFNDEF : CondOp::IFDEF;
272 ast->lhs = ParseExpr(line, false);
273 ast->rhs = NULL;
274 out_asts_->push_back(ast);
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +0900275 EnterIf(ast);
276 }
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900277
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +0900278 bool ParseIfEqCond(StringPiece s, IfAST* ast) {
279 if (s.empty()) {
280 return false;
281 }
282
283 if (s[0] == '(' && s[s.size() - 1] == ')') {
284 s = s.substr(1, s.size() - 2);
285 char terms[] = {',', '\0'};
286 size_t n;
287 ast->lhs = ParseExprImpl(s, terms, false, &n, true);
288 if (s[n] != ',')
289 return false;
290 s = TrimLeftSpace(s.substr(n+1));
291 ast->rhs = ParseExprImpl(s, NULL, false, &n);
Shinichiro Hamajiadeea692015-06-17 17:57:31 +0900292 s = TrimLeftSpace(s.substr(n));
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +0900293 } else {
294 for (int i = 0; i < 2; i++) {
295 if (s.empty())
296 return false;
297 char quote = s[0];
298 if (quote != '\'' && quote != '"')
299 return false;
300 size_t end = s.find(quote, 1);
301 if (end == string::npos)
302 return false;
303 Value* v = ParseExpr(s.substr(1, end - 1), false);
304 if (i == 0)
305 ast->lhs = v;
306 else
307 ast->rhs = v;
308 s = TrimLeftSpace(s.substr(end+1));
309 }
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +0900310 }
Shinichiro Hamajiadeea692015-06-17 17:57:31 +0900311 if (!s.empty()) {
312 Error("extraneous text after `ifeq' directive");
313 }
314 return true;
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +0900315 }
316
317 void ParseIfeq(StringPiece line, StringPiece directive) {
318 IfAST* ast = new IfAST();
319 ast->set_loc(loc_);
320 ast->op = directive[2] == 'n' ? CondOp::IFNEQ : CondOp::IFEQ;
321
322 if (!ParseIfEqCond(line, ast)) {
323 Error("*** invalid syntax in conditional.");
324 }
325
326 out_asts_->push_back(ast);
327 EnterIf(ast);
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900328 }
329
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +0900330 void ParseElse(StringPiece line, StringPiece) {
331 CheckIfStack("else");
332 IfState* st = if_stack_.top();
333 if (st->is_in_else)
334 Error("*** only one `else' per conditional.");
335 st->is_in_else = true;
336 out_asts_ = &st->ast->false_asts;
337
338 StringPiece next_if = TrimLeftSpace(line);
339 if (next_if.empty())
340 return;
341
342 num_if_nest_ = st->num_nest + 1;
343 if (!HandleDirective(next_if, else_if_directives_)) {
344 WARN("%s:%d: extraneous text after `else' directive", LOCF(loc_));
345 }
346 num_if_nest_ = 0;
347 }
348
349 void ParseEndif(StringPiece line, StringPiece) {
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900350 CheckIfStack("endif");
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +0900351 if (!line.empty())
352 Error("extraneous text after `endif` directive");
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900353 IfState st = *if_stack_.top();
354 for (int t = 0; t <= st.num_nest; t++) {
355 delete if_stack_.top();
356 if_stack_.pop();
357 if (if_stack_.empty()) {
358 out_asts_ = asts_;
359 } else {
360 IfState* st = if_stack_.top();
361 if (st->is_in_else)
Shinichiro Hamaji2847f092015-06-17 15:48:37 +0900362 out_asts_ = &st->ast->false_asts;
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900363 else
Shinichiro Hamaji2847f092015-06-17 15:48:37 +0900364 out_asts_ = &st->ast->true_asts;
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900365 }
366 }
367 }
368
369 void CheckIfStack(const char* keyword) {
370 if (if_stack_.empty()) {
371 Error(StringPrintf("*** extraneous `%s'.", keyword));
372 }
373 }
374
Shinichiro Hamaji5562caf2015-06-17 17:08:40 +0900375 StringPiece RemoveComment(StringPiece line) {
Shinichiro Hamajieafd0522015-06-18 16:46:02 +0900376 size_t i = FindOutsideParen(line, '#');
377 if (i == string::npos)
378 return line;
379 return line.substr(0, i);
Shinichiro Hamaji5562caf2015-06-17 17:08:40 +0900380 }
381
382 StringPiece GetDirective(StringPiece line) {
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900383 if (line.size() < shortest_directive_len_)
Shinichiro Hamaji5562caf2015-06-17 17:08:40 +0900384 return StringPiece();
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900385 StringPiece prefix = line.substr(0, longest_directive_len_ + 1);
Shinichiro Hamaji5562caf2015-06-17 17:08:40 +0900386 size_t space_index = prefix.find_first_of(" \t#");
387 return prefix.substr(0, space_index);
388 }
389
390 bool HandleDirective(StringPiece line, const DirectiveMap* directive_map) {
391 StringPiece directive = GetDirective(line);
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +0900392 auto found = directive_map->find(directive);
393 if (found == directive_map->end())
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900394 return false;
395
Shinichiro Hamaji5562caf2015-06-17 17:08:40 +0900396 StringPiece rest = TrimRightSpace(RemoveComment(TrimLeftSpace(
Shinichiro Hamajid146f4c2015-06-17 17:51:24 +0900397 line.substr(directive.size()))));
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900398 (this->*found->second)(rest, directive);
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900399 return true;
400 }
401
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900402 StringPiece buf_;
403 size_t l_;
404 ParserState state_;
405
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900406 vector<AST*>* asts_;
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900407 vector<AST*>* out_asts_;
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900408
Shinichiro Hamaji810fd032015-06-17 04:38:03 +0900409 StringPiece define_name_;
410 size_t define_start_;
411 int define_start_line_;
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900412
Shinichiro Hamaji7e256df2015-06-17 15:33:11 +0900413 int num_if_nest_;
414 stack<IfState*> if_stack_;
415
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900416 Loc loc_;
417 bool fixed_lineno_;
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900418
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +0900419 static DirectiveMap* make_directives_;
420 static DirectiveMap* else_if_directives_;
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900421 static size_t shortest_directive_len_;
422 static size_t longest_directive_len_;
Shinichiro Hamaji776ca302015-06-06 03:52:48 +0900423};
424
425void Parse(Makefile* mk) {
426 Parser parser(StringPiece(mk->buf(), mk->len()),
427 mk->filename().c_str(),
428 mk->mutable_asts());
429 parser.Parse();
430}
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900431
Shinichiro Hamaji80456fb2015-06-18 14:56:10 +0900432void Parse(StringPiece buf, const Loc& loc, vector<AST*>* out_asts) {
433 Parser parser(buf, loc, out_asts);
434 parser.Parse();
435}
436
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900437void InitParser() {
438 Parser::Init();
439}
440
441void QuitParser() {
442 Parser::Quit();
443}
444
Shinichiro Hamaji6cb1c252015-06-17 16:22:51 +0900445Parser::DirectiveMap* Parser::make_directives_;
446Parser::DirectiveMap* Parser::else_if_directives_;
Shinichiro Hamaji42b625f2015-06-16 23:07:21 +0900447size_t Parser::shortest_directive_len_;
448size_t Parser::longest_directive_len_;