1 // Copyright 2015 Google Inc. All rights reserved
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 // +build ignore
16
17 #include "expr.h"
18
19 #include <vector>
20
21 #include "eval.h"
22 #include "func.h"
23 #include "log.h"
24 #include "stringprintf.h"
25 #include "strutil.h"
26 #include "var.h"
27
Evaluable()28 Evaluable::Evaluable() {}
29
~Evaluable()30 Evaluable::~Evaluable() {}
31
Eval(Evaluator * ev) const32 string Evaluable::Eval(Evaluator* ev) const {
33 string s;
34 Eval(ev, &s);
35 return s;
36 }
37
Value()38 Value::Value() {}
39
~Value()40 Value::~Value() {}
41
DebugString() const42 string Value::DebugString() const {
43 if (static_cast<const Value*>(this)) {
44 return NoLineBreak(DebugString_());
45 }
46 return "(null)";
47 }
48
49 class Literal : public Value {
50 public:
Literal(StringPiece s)51 explicit Literal(StringPiece s) : s_(s) {}
52
val() const53 StringPiece val() const { return s_; }
54
Eval(Evaluator * ev,string * s) const55 virtual void Eval(Evaluator* ev, string* s) const override {
56 ev->CheckStack();
57 s->append(s_.begin(), s_.end());
58 }
59
IsLiteral() const60 virtual bool IsLiteral() const override { return true; }
GetLiteralValueUnsafe() const61 virtual StringPiece GetLiteralValueUnsafe() const override { return s_; }
62
DebugString_() const63 virtual string DebugString_() const override { return s_.as_string(); }
64
65 private:
66 StringPiece s_;
67 };
68
69 class Expr : public Value {
70 public:
Expr()71 Expr() {}
72
~Expr()73 virtual ~Expr() {
74 for (Value* v : vals_) {
75 delete v;
76 }
77 }
78
79 // Takes the ownership of |v|.
AddValue(Value * v)80 void AddValue(Value* v) { vals_.push_back(v); }
81
Eval(Evaluator * ev,string * s) const82 virtual void Eval(Evaluator* ev, string* s) const override {
83 ev->CheckStack();
84 for (Value* v : vals_) {
85 v->Eval(ev, s);
86 }
87 }
88
DebugString_() const89 virtual string DebugString_() const override {
90 string r;
91 for (Value* v : vals_) {
92 if (r.empty()) {
93 r += "Expr(";
94 } else {
95 r += ", ";
96 }
97 r += v->DebugString();
98 }
99 if (!r.empty())
100 r += ")";
101 return r;
102 }
103
Compact()104 virtual Value* Compact() override {
105 if (vals_.size() != 1) {
106 return this;
107 }
108 Value* r = vals_[0];
109 vals_.clear();
110 delete this;
111 return r;
112 }
113
114 private:
115 vector<Value*> vals_;
116 };
117
118 class SymRef : public Value {
119 public:
SymRef(Symbol n)120 explicit SymRef(Symbol n) : name_(n) {}
~SymRef()121 virtual ~SymRef() {}
122
Eval(Evaluator * ev,string * s) const123 virtual void Eval(Evaluator* ev, string* s) const override {
124 ev->CheckStack();
125 Var* v = ev->LookupVar(name_);
126 v->Used(ev, name_);
127 v->Eval(ev, s);
128 }
129
DebugString_() const130 virtual string DebugString_() const override {
131 return StringPrintf("SymRef(%s)", name_.c_str());
132 }
133
134 private:
135 Symbol name_;
136 };
137
138 class VarRef : public Value {
139 public:
VarRef(Value * n)140 explicit VarRef(Value* n) : name_(n) {}
~VarRef()141 virtual ~VarRef() { delete name_; }
142
Eval(Evaluator * ev,string * s) const143 virtual void Eval(Evaluator* ev, string* s) const override {
144 ev->CheckStack();
145 ev->IncrementEvalDepth();
146 const string&& name = name_->Eval(ev);
147 ev->DecrementEvalDepth();
148 Symbol sym = Intern(name);
149 Var* v = ev->LookupVar(sym);
150 v->Used(ev, sym);
151 v->Eval(ev, s);
152 }
153
DebugString_() const154 virtual string DebugString_() const override {
155 return StringPrintf("VarRef(%s)", name_->DebugString().c_str());
156 }
157
158 private:
159 Value* name_;
160 };
161
162 class VarSubst : public Value {
163 public:
VarSubst(Value * n,Value * p,Value * s)164 explicit VarSubst(Value* n, Value* p, Value* s)
165 : name_(n), pat_(p), subst_(s) {}
~VarSubst()166 virtual ~VarSubst() {
167 delete name_;
168 delete pat_;
169 delete subst_;
170 }
171
Eval(Evaluator * ev,string * s) const172 virtual void Eval(Evaluator* ev, string* s) const override {
173 ev->CheckStack();
174 ev->IncrementEvalDepth();
175 const string&& name = name_->Eval(ev);
176 Symbol sym = Intern(name);
177 Var* v = ev->LookupVar(sym);
178 const string&& pat_str = pat_->Eval(ev);
179 const string&& subst = subst_->Eval(ev);
180 ev->DecrementEvalDepth();
181 v->Used(ev, sym);
182 const string&& value = v->Eval(ev);
183 WordWriter ww(s);
184 Pattern pat(pat_str);
185 for (StringPiece tok : WordScanner(value)) {
186 ww.MaybeAddWhitespace();
187 pat.AppendSubstRef(tok, subst, s);
188 }
189 }
190
DebugString_() const191 virtual string DebugString_() const override {
192 return StringPrintf("VarSubst(%s:%s=%s)", name_->DebugString().c_str(),
193 pat_->DebugString().c_str(),
194 subst_->DebugString().c_str());
195 }
196
197 private:
198 Value* name_;
199 Value* pat_;
200 Value* subst_;
201 };
202
203 class Func : public Value {
204 public:
Func(FuncInfo * fi)205 explicit Func(FuncInfo* fi) : fi_(fi) {}
206
~Func()207 ~Func() {
208 for (Value* a : args_)
209 delete a;
210 }
211
Eval(Evaluator * ev,string * s) const212 virtual void Eval(Evaluator* ev, string* s) const override {
213 ev->CheckStack();
214 LOG("Invoke func %s(%s)", name(), JoinValues(args_, ",").c_str());
215 ev->IncrementEvalDepth();
216 fi_->func(args_, ev, s);
217 ev->DecrementEvalDepth();
218 }
219
DebugString_() const220 virtual string DebugString_() const override {
221 return StringPrintf("Func(%s %s)", fi_->name,
222 JoinValues(args_, ",").c_str());
223 }
224
AddArg(Value * v)225 void AddArg(Value* v) { args_.push_back(v); }
226
name() const227 const char* name() const { return fi_->name; }
arity() const228 int arity() const { return fi_->arity; }
min_arity() const229 int min_arity() const { return fi_->min_arity; }
trim_space() const230 bool trim_space() const { return fi_->trim_space; }
trim_right_space_1st() const231 bool trim_right_space_1st() const { return fi_->trim_right_space_1st; }
232
233 private:
234 FuncInfo* fi_;
235 vector<Value*> args_;
236 };
237
CloseParen(char c)238 static char CloseParen(char c) {
239 switch (c) {
240 case '(':
241 return ')';
242 case '{':
243 return '}';
244 }
245 return 0;
246 }
247
SkipSpaces(StringPiece s,const char * terms)248 static size_t SkipSpaces(StringPiece s, const char* terms) {
249 for (size_t i = 0; i < s.size(); i++) {
250 char c = s[i];
251 if (strchr(terms, c))
252 return i;
253 if (!isspace(c)) {
254 if (c != '\\')
255 return i;
256 char n = s.get(i + 1);
257 if (n != '\r' && n != '\n')
258 return i;
259 }
260 }
261 return s.size();
262 }
263
ShouldHandleComments(ParseExprOpt opt)264 bool ShouldHandleComments(ParseExprOpt opt) {
265 return opt != ParseExprOpt::DEFINE && opt != ParseExprOpt::COMMAND;
266 }
267
ParseFunc(const Loc & loc,Func * f,StringPiece s,size_t i,char * terms,size_t * index_out)268 void ParseFunc(const Loc& loc,
269 Func* f,
270 StringPiece s,
271 size_t i,
272 char* terms,
273 size_t* index_out) {
274 terms[1] = ',';
275 terms[2] = '\0';
276 i += SkipSpaces(s.substr(i), terms);
277 if (i == s.size()) {
278 *index_out = i;
279 return;
280 }
281
282 int nargs = 1;
283 while (true) {
284 if (f->arity() && nargs >= f->arity()) {
285 terms[1] = '\0'; // Drop ','.
286 }
287
288 if (f->trim_space()) {
289 for (; i < s.size(); i++) {
290 if (isspace(s[i]))
291 continue;
292 if (s[i] == '\\') {
293 char c = s.get(i + 1);
294 if (c == '\r' || c == '\n')
295 continue;
296 }
297 break;
298 }
299 }
300 const bool trim_right_space =
301 (f->trim_space() || (nargs == 1 && f->trim_right_space_1st()));
302 size_t n;
303 Value* v = ParseExprImpl(loc, s.substr(i), terms, ParseExprOpt::FUNC, &n,
304 trim_right_space);
305 // TODO: concatLine???
306 f->AddArg(v);
307 i += n;
308 if (i == s.size()) {
309 ERROR_LOC(loc,
310 "*** unterminated call to function '%s': "
311 "missing '%c'.",
312 f->name(), terms[0]);
313 }
314 nargs++;
315 if (s[i] == terms[0]) {
316 i++;
317 break;
318 }
319 i++; // Should be ','.
320 if (i == s.size())
321 break;
322 }
323
324 if (nargs <= f->min_arity()) {
325 ERROR_LOC(loc,
326 "*** insufficient number of arguments (%d) to function `%s'.",
327 nargs - 1, f->name());
328 }
329
330 *index_out = i;
331 return;
332 }
333
ParseDollar(const Loc & loc,StringPiece s,size_t * index_out)334 Value* ParseDollar(const Loc& loc, StringPiece s, size_t* index_out) {
335 CHECK(s.size() >= 2);
336 CHECK(s[0] == '$');
337 CHECK(s[1] != '$');
338
339 char cp = CloseParen(s[1]);
340 if (cp == 0) {
341 *index_out = 2;
342 return new SymRef(Intern(s.substr(1, 1)));
343 }
344
345 char terms[] = {cp, ':', ' ', 0};
346 for (size_t i = 2;;) {
347 size_t n;
348 Value* vname =
349 ParseExprImpl(loc, s.substr(i), terms, ParseExprOpt::NORMAL, &n);
350 i += n;
351 if (s[i] == cp) {
352 *index_out = i + 1;
353 if (vname->IsLiteral()) {
354 Literal* lit = static_cast<Literal*>(vname);
355 Symbol sym = Intern(lit->val());
356 if (g_flags.enable_kati_warnings) {
357 size_t found = sym.str().find_first_of(" ({");
358 if (found != string::npos) {
359 KATI_WARN_LOC(loc, "*warning*: variable lookup with '%c': %.*s",
360 sym.str()[found], SPF(s));
361 }
362 }
363 Value* r = new SymRef(sym);
364 delete lit;
365 return r;
366 }
367 return new VarRef(vname);
368 }
369
370 if (s[i] == ' ' || s[i] == '\\') {
371 // ${func ...}
372 if (vname->IsLiteral()) {
373 Literal* lit = static_cast<Literal*>(vname);
374 if (FuncInfo* fi = GetFuncInfo(lit->val())) {
375 delete lit;
376 Func* func = new Func(fi);
377 ParseFunc(loc, func, s, i + 1, terms, index_out);
378 return func;
379 } else {
380 KATI_WARN_LOC(loc, "*warning*: unknown make function '%.*s': %.*s",
381 SPF(lit->val()), SPF(s));
382 }
383 }
384
385 // Not a function. Drop ' ' from |terms| and parse it
386 // again. This is inefficient, but this code path should be
387 // rarely used.
388 delete vname;
389 terms[2] = 0;
390 i = 2;
391 continue;
392 }
393
394 if (s[i] == ':') {
395 terms[2] = '\0';
396 terms[1] = '=';
397 size_t n;
398 Value* pat =
399 ParseExprImpl(loc, s.substr(i + 1), terms, ParseExprOpt::NORMAL, &n);
400 i += 1 + n;
401 if (s[i] == cp) {
402 Expr* v = new Expr;
403 v->AddValue(vname);
404 v->AddValue(new Literal(":"));
405 v->AddValue(pat);
406 *index_out = i + 1;
407 return new VarRef(v);
408 }
409
410 terms[1] = '\0';
411 Value* subst =
412 ParseExprImpl(loc, s.substr(i + 1), terms, ParseExprOpt::NORMAL, &n);
413 i += 1 + n;
414 *index_out = i + 1;
415 return new VarSubst(vname->Compact(), pat, subst);
416 }
417
418 // GNU make accepts expressions like $((). See unmatched_paren*.mk
419 // for detail.
420 size_t found = s.find(cp);
421 if (found != string::npos) {
422 KATI_WARN_LOC(loc, "*warning*: unmatched parentheses: %.*s", SPF(s));
423 *index_out = s.size();
424 return new SymRef(Intern(s.substr(2, found - 2)));
425 }
426 ERROR_LOC(loc, "*** unterminated variable reference.");
427 }
428 }
429
ParseExprImpl(const Loc & loc,StringPiece s,const char * terms,ParseExprOpt opt,size_t * index_out,bool trim_right_space)430 Value* ParseExprImpl(const Loc& loc,
431 StringPiece s,
432 const char* terms,
433 ParseExprOpt opt,
434 size_t* index_out,
435 bool trim_right_space) {
436 if (s.get(s.size() - 1) == '\r')
437 s.remove_suffix(1);
438
439 Expr* r = new Expr;
440 size_t b = 0;
441 char save_paren = 0;
442 int paren_depth = 0;
443 size_t i;
444 for (i = 0; i < s.size(); i++) {
445 char c = s[i];
446 if (terms && strchr(terms, c) && !save_paren) {
447 break;
448 }
449
450 // Handle a comment.
451 if (!terms && c == '#' && ShouldHandleComments(opt)) {
452 if (i > b)
453 r->AddValue(new Literal(s.substr(b, i - b)));
454 bool was_backslash = false;
455 for (; i < s.size() && !(s[i] == '\n' && !was_backslash); i++) {
456 was_backslash = !was_backslash && s[i] == '\\';
457 }
458 *index_out = i;
459 return r->Compact();
460 }
461
462 if (c == '$') {
463 if (i + 1 >= s.size()) {
464 break;
465 }
466
467 if (i > b)
468 r->AddValue(new Literal(s.substr(b, i - b)));
469
470 if (s[i + 1] == '$') {
471 r->AddValue(new Literal(StringPiece("$")));
472 i += 1;
473 b = i + 1;
474 continue;
475 }
476
477 if (terms && strchr(terms, s[i + 1])) {
478 *index_out = i + 1;
479 return r->Compact();
480 }
481
482 size_t n;
483 Value* v = ParseDollar(loc, s.substr(i), &n);
484 i += n;
485 b = i;
486 i--;
487 r->AddValue(v);
488 continue;
489 }
490
491 if ((c == '(' || c == '{') && opt == ParseExprOpt::FUNC) {
492 char cp = CloseParen(c);
493 if (terms && terms[0] == cp) {
494 paren_depth++;
495 save_paren = cp;
496 terms++;
497 } else if (cp == save_paren) {
498 paren_depth++;
499 }
500 continue;
501 }
502
503 if (c == save_paren) {
504 paren_depth--;
505 if (paren_depth == 0) {
506 terms--;
507 save_paren = 0;
508 }
509 }
510
511 if (c == '\\' && i + 1 < s.size() && opt != ParseExprOpt::COMMAND) {
512 char n = s[i + 1];
513 if (n == '\\') {
514 i++;
515 continue;
516 }
517 if (n == '#' && ShouldHandleComments(opt)) {
518 r->AddValue(new Literal(s.substr(b, i - b)));
519 i++;
520 b = i;
521 continue;
522 }
523 if (n == '\r' || n == '\n') {
524 if (terms && strchr(terms, ' ')) {
525 break;
526 }
527 if (i > b) {
528 r->AddValue(new Literal(TrimRightSpace(s.substr(b, i - b))));
529 }
530 r->AddValue(new Literal(StringPiece(" ")));
531 // Skip the current escaped newline
532 i += 2;
533 if (n == '\r' && s.get(i) == '\n')
534 i++;
535 // Then continue skipping escaped newlines, spaces, and tabs
536 for (; i < s.size(); i++) {
537 if (s[i] == '\\' && (s.get(i + 1) == '\r' || s.get(i + 1) == '\n')) {
538 i++;
539 continue;
540 }
541 if (s[i] != ' ' && s[i] != '\t') {
542 break;
543 }
544 }
545 b = i;
546 i--;
547 }
548 }
549 }
550
551 if (i > b) {
552 StringPiece rest = s.substr(b, i - b);
553 if (trim_right_space)
554 rest = TrimRightSpace(rest);
555 if (!rest.empty())
556 r->AddValue(new Literal(rest));
557 }
558 *index_out = i;
559 return r->Compact();
560 }
561
ParseExpr(const Loc & loc,StringPiece s,ParseExprOpt opt)562 Value* ParseExpr(const Loc& loc, StringPiece s, ParseExprOpt opt) {
563 size_t n;
564 return ParseExprImpl(loc, s, NULL, opt, &n);
565 }
566
JoinValues(const vector<Value * > & vals,const char * sep)567 string JoinValues(const vector<Value*>& vals, const char* sep) {
568 vector<string> val_strs;
569 for (Value* v : vals) {
570 val_strs.push_back(v->DebugString());
571 }
572 return JoinStrings(val_strs, sep);
573 }
574
NewExpr2(Value * v1,Value * v2)575 Value* NewExpr2(Value* v1, Value* v2) {
576 Expr* e = new Expr();
577 e->AddValue(v1);
578 e->AddValue(v2);
579 return e;
580 }
581
NewExpr3(Value * v1,Value * v2,Value * v3)582 Value* NewExpr3(Value* v1, Value* v2, Value* v3) {
583 Expr* e = new Expr();
584 e->AddValue(v1);
585 e->AddValue(v2);
586 e->AddValue(v3);
587 return e;
588 }
589
NewLiteral(StringPiece s)590 Value* NewLiteral(StringPiece s) {
591 return new Literal(s);
592 }
593