Home | History | Annotate | Download | only in kati 
      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 
     28 Evaluable::Evaluable() {}
     29 
     30 Evaluable::~Evaluable() {}
     31 
     32 string Evaluable::Eval(Evaluator* ev) const {
     33   string s;
     34   Eval(ev, &s);
     35   return s;
     36 }
     37 
     38 Value::Value() {}
     39 
     40 Value::~Value() {}
     41 
     42 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:
     51   explicit Literal(StringPiece s) : s_(s) {}
     52 
     53   StringPiece val() const { return s_; }
     54 
     55   virtual void Eval(Evaluator* ev, string* s) const override {
     56     ev->CheckStack();
     57     s->append(s_.begin(), s_.end());
     58   }
     59 
     60   virtual bool IsLiteral() const override { return true; }
     61   virtual StringPiece GetLiteralValueUnsafe() const override { return s_; }
     62 
     63   virtual string DebugString_() const override { return s_.as_string(); }
     64 
     65  private:
     66   StringPiece s_;
     67 };
     68 
     69 class Expr : public Value {
     70  public:
     71   Expr() {}
     72 
     73   virtual ~Expr() {
     74     for (Value* v : vals_) {
     75       delete v;
     76     }
     77   }
     78 
     79   // Takes the ownership of |v|.
     80   void AddValue(Value* v) { vals_.push_back(v); }
     81 
     82   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 
     89   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 
    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:
    120   explicit SymRef(Symbol n) : name_(n) {}
    121   virtual ~SymRef() {}
    122 
    123   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 
    130   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:
    140   explicit VarRef(Value* n) : name_(n) {}
    141   virtual ~VarRef() { delete name_; }
    142 
    143   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 
    154   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:
    164   explicit VarSubst(Value* n, Value* p, Value* s)
    165       : name_(n), pat_(p), subst_(s) {}
    166   virtual ~VarSubst() {
    167     delete name_;
    168     delete pat_;
    169     delete subst_;
    170   }
    171 
    172   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 
    191   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:
    205   explicit Func(FuncInfo* fi) : fi_(fi) {}
    206 
    207   ~Func() {
    208     for (Value* a : args_)
    209       delete a;
    210   }
    211 
    212   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 
    220   virtual string DebugString_() const override {
    221     return StringPrintf("Func(%s %s)", fi_->name,
    222                         JoinValues(args_, ",").c_str());
    223   }
    224 
    225   void AddArg(Value* v) { args_.push_back(v); }
    226 
    227   const char* name() const { return fi_->name; }
    228   int arity() const { return fi_->arity; }
    229   int min_arity() const { return fi_->min_arity; }
    230   bool trim_space() const { return fi_->trim_space; }
    231   bool trim_right_space_1st() const { return fi_->trim_right_space_1st; }
    232 
    233  private:
    234   FuncInfo* fi_;
    235   vector<Value*> args_;
    236 };
    237 
    238 static char CloseParen(char c) {
    239   switch (c) {
    240     case '(':
    241       return ')';
    242     case '{':
    243       return '}';
    244   }
    245   return 0;
    246 }
    247 
    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 
    264 bool ShouldHandleComments(ParseExprOpt opt) {
    265   return opt != ParseExprOpt::DEFINE && opt != ParseExprOpt::COMMAND;
    266 }
    267 
    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 
    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 
    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 
    562 Value* ParseExpr(const Loc& loc, StringPiece s, ParseExprOpt opt) {
    563   size_t n;
    564   return ParseExprImpl(loc, s, NULL, opt, &n);
    565 }
    566 
    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 
    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 
    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 
    590 Value* NewLiteral(StringPiece s) {
    591   return new Literal(s);
    592 }
    593