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 
     31 Evaluable::~Evaluable() {
     32 }
     33 
     34 string Evaluable::Eval(Evaluator* ev) const {
     35   string s;
     36   Eval(ev, &s);
     37   return s;
     38 }
     39 
     40 Value::Value() {
     41 }
     42 
     43 Value::~Value() {
     44 }
     45 
     46 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:
     55   explicit Literal(StringPiece s)
     56       : s_(s) {
     57   }
     58 
     59   StringPiece val() const { return s_; }
     60 
     61   virtual void Eval(Evaluator*, string* s) const override {
     62     s->append(s_.begin(), s_.end());
     63   }
     64 
     65   virtual bool IsLiteral() const override { return true; }
     66   virtual StringPiece GetLiteralValueUnsafe() const override { return s_; }
     67 
     68   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:
     78   Expr() {
     79   }
     80 
     81   virtual ~Expr() {
     82     for (Value* v : vals_) {
     83       delete v;
     84     }
     85   }
     86 
     87   // Takes the ownership of |v|.
     88   void AddValue(Value* v) {
     89     vals_.push_back(v);
     90   }
     91 
     92   virtual void Eval(Evaluator* ev, string* s) const override {
     93     for (Value* v : vals_) {
     94       v->Eval(ev, s);
     95     }
     96   }
     97 
     98   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 
    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:
    129   explicit SymRef(Symbol n)
    130       : name_(n) {
    131   }
    132   virtual ~SymRef() {
    133   }
    134 
    135   virtual void Eval(Evaluator* ev, string* s) const override {
    136     Var* v = ev->LookupVar(name_);
    137     v->Eval(ev, s);
    138   }
    139 
    140   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:
    150   explicit VarRef(Value* n)
    151       : name_(n) {
    152   }
    153   virtual ~VarRef() {
    154     delete name_;
    155   }
    156 
    157   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 
    165   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:
    175   explicit VarSubst(Value* n, Value* p, Value* s)
    176       : name_(n), pat_(p), subst_(s) {
    177   }
    178   virtual ~VarSubst() {
    179     delete name_;
    180     delete pat_;
    181     delete subst_;
    182   }
    183 
    184   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 
    200   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:
    215   explicit Func(FuncInfo* fi)
    216       : fi_(fi) {
    217   }
    218 
    219   ~Func() {
    220     for (Value* a : args_)
    221       delete a;
    222   }
    223 
    224   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 
    231   virtual string DebugString_() const override {
    232     return StringPrintf("Func(%s %s)",
    233                         fi_->name,
    234                         JoinValues(args_, ",").c_str());
    235   }
    236 
    237   void AddArg(Value* v) {
    238     args_.push_back(v);
    239   }
    240 
    241   const char* name() const { return fi_->name; }
    242   int arity() const { return fi_->arity; }
    243   int min_arity() const { return fi_->min_arity; }
    244   bool trim_space() const { return fi_->trim_space; }
    245   bool trim_right_space_1st() const { return fi_->trim_right_space_1st; }
    246 
    247  private:
    248   FuncInfo* fi_;
    249   vector<Value*> args_;
    250 };
    251 
    252 static char CloseParen(char c) {
    253   switch (c) {
    254     case '(':
    255       return ')';
    256     case '{':
    257       return '}';
    258   }
    259   return 0;
    260 }
    261 
    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 
    278 bool ShouldHandleComments(ParseExprOpt opt) {
    279   return opt != ParseExprOpt::DEFINE && opt != ParseExprOpt::COMMAND;
    280 }
    281 
    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 
    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 
    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 
    567 Value* ParseExpr(const Loc& loc, StringPiece s, ParseExprOpt opt) {
    568   size_t n;
    569   return ParseExprImpl(loc, s, NULL, opt, &n);
    570 }
    571 
    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 
    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 
    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 
    595 Value* NewLiteral(StringPiece s) {
    596   return new Literal(s);
    597 }
    598