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