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