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 "find.h"
     18 
     19 #include <dirent.h>
     20 #include <fnmatch.h>
     21 #include <limits.h>
     22 #include <sys/stat.h>
     23 #include <sys/types.h>
     24 #include <unistd.h>
     25 
     26 #include <algorithm>
     27 #include <memory>
     28 #include <vector>
     29 
     30 //#undef NOLOG
     31 
     32 #include "fileutil.h"
     33 #include "log.h"
     34 #include "string_piece.h"
     35 #include "strutil.h"
     36 #include "timeutil.h"
     37 
     38 class FindCond {
     39  public:
     40   virtual ~FindCond() = default;
     41   virtual bool IsTrue(const string& path, unsigned char type) const = 0;
     42   virtual bool Countable() const = 0;
     43   virtual unsigned Count() const = 0;
     44  protected:
     45   FindCond() = default;
     46 };
     47 
     48 namespace {
     49 
     50 class NameCond : public FindCond {
     51  public:
     52   explicit NameCond(const string& n)
     53       : name_(n) {
     54     has_wildcard_ = (n.find_first_of("?*[") != string::npos);
     55   }
     56   virtual bool IsTrue(const string& path, unsigned char) const override {
     57     return fnmatch(name_.c_str(), Basename(path).data(), 0) == 0;
     58   }
     59   virtual bool Countable() const override {
     60     return !has_wildcard_;
     61   }
     62   virtual unsigned Count() const override {
     63     return 1;
     64   }
     65  private:
     66   string name_;
     67   bool has_wildcard_;
     68 };
     69 
     70 class TypeCond : public FindCond {
     71  public:
     72   explicit TypeCond(unsigned char t)
     73       : type_(t) {
     74   }
     75   virtual bool IsTrue(const string&, unsigned char type) const override {
     76     return type == type_;
     77   }
     78   virtual bool Countable() const override {
     79     return false;
     80   }
     81   virtual unsigned Count() const override {
     82     return 0;
     83   }
     84  private:
     85   unsigned char type_;
     86 };
     87 
     88 class NotCond : public FindCond {
     89  public:
     90   NotCond(FindCond* c)
     91       : c_(c) {
     92   }
     93   virtual bool IsTrue(const string& path, unsigned char type) const override {
     94     return !c_->IsTrue(path, type);
     95   }
     96   virtual bool Countable() const override {
     97     return false;
     98   }
     99   virtual unsigned Count() const override {
    100     return 0;
    101   }
    102  private:
    103   unique_ptr<FindCond> c_;
    104 };
    105 
    106 class AndCond : public FindCond {
    107  public:
    108   AndCond(FindCond* c1, FindCond* c2)
    109       : c1_(c1), c2_(c2) {
    110   }
    111   virtual bool IsTrue(const string& path, unsigned char type) const override {
    112     if (c1_->IsTrue(path, type))
    113       return c2_->IsTrue(path, type);
    114     return false;
    115   }
    116   virtual bool Countable() const override {
    117     return false;
    118   }
    119   virtual unsigned Count() const override {
    120     return 0;
    121   }
    122  private:
    123   unique_ptr<FindCond> c1_, c2_;
    124 };
    125 
    126 class OrCond : public FindCond {
    127  public:
    128   OrCond(FindCond* c1, FindCond* c2)
    129       : c1_(c1), c2_(c2) {
    130   }
    131   virtual bool IsTrue(const string& path, unsigned char type) const override {
    132     if (!c1_->IsTrue(path, type))
    133       return c2_->IsTrue(path, type);
    134     return true;
    135   }
    136   virtual bool Countable() const override {
    137     return c1_->Countable() && c2_->Countable();;
    138   }
    139   virtual unsigned Count() const override {
    140     return c1_->Count() + c2_->Count();
    141   }
    142  private:
    143   unique_ptr<FindCond> c1_, c2_;
    144 };
    145 
    146 class DirentNode {
    147  public:
    148   virtual ~DirentNode() = default;
    149 
    150   virtual const DirentNode* FindDir(StringPiece) const {
    151     return NULL;
    152   }
    153   virtual bool RunFind(const FindCommand& fc, const Loc& loc, int d,
    154                        string* path,
    155                        unordered_map<const DirentNode*, string>* cur_read_dirs,
    156                        vector<string>& out) const = 0;
    157 
    158   virtual bool IsDirectory() const = 0;
    159 
    160   const string& base() const { return base_; }
    161 
    162  protected:
    163   explicit DirentNode(const string& name) {
    164     base_ = Basename(name).as_string();
    165   }
    166 
    167   void PrintIfNecessary(const FindCommand& fc,
    168                         const string& path,
    169                         unsigned char type,
    170                         int d,
    171                         vector<string>& out) const {
    172     if (fc.print_cond && !fc.print_cond->IsTrue(path, type))
    173       return;
    174     if (d < fc.mindepth)
    175       return;
    176     out.push_back(path);
    177   }
    178 
    179   string base_;
    180 };
    181 
    182 class DirentFileNode : public DirentNode {
    183  public:
    184   DirentFileNode(const string& name, unsigned char type)
    185       : DirentNode(name), type_(type) {
    186   }
    187 
    188   virtual bool RunFind(const FindCommand& fc, const Loc&, int d,
    189                        string* path,
    190                        unordered_map<const DirentNode*, string>*,
    191                        vector<string>& out) const override {
    192     PrintIfNecessary(fc, *path, type_, d, out);
    193     return true;
    194   }
    195 
    196   virtual bool IsDirectory() const override { return false; }
    197 
    198  private:
    199   unsigned char type_;
    200 };
    201 
    202 struct ScopedReadDirTracker {
    203  public:
    204   ScopedReadDirTracker(const DirentNode* n,
    205                        const string& path,
    206                        unordered_map<const DirentNode*, string>* cur_read_dirs)
    207       : n_(NULL), cur_read_dirs_(cur_read_dirs) {
    208     const auto& p = cur_read_dirs->emplace(n, path);
    209     if (p.second) {
    210       n_ = n;
    211     } else {
    212       conflicted_ = p.first->second;
    213     }
    214   }
    215 
    216   ~ScopedReadDirTracker() {
    217     if (n_)
    218       cur_read_dirs_->erase(n_);
    219   }
    220 
    221   bool ok() const { return conflicted_.empty(); }
    222   const string& conflicted() const { return conflicted_; }
    223 
    224  private:
    225   string conflicted_;
    226   const DirentNode* n_;
    227   unordered_map<const DirentNode*, string>* cur_read_dirs_;
    228 };
    229 
    230 class DirentDirNode : public DirentNode {
    231  public:
    232   explicit DirentDirNode(const string& name)
    233       : DirentNode(name) {
    234   }
    235 
    236   ~DirentDirNode() {
    237     for (auto& p : children_) {
    238       delete p.second;
    239     }
    240   }
    241 
    242   virtual const DirentNode* FindDir(StringPiece d) const override {
    243     if (d.empty() || d == ".")
    244       return this;
    245     size_t index = d.find('/');
    246     const string& p = d.substr(0, index).as_string();
    247     for (auto& child : children_) {
    248       if (p == child.first) {
    249         if (index == string::npos)
    250           return child.second;
    251         StringPiece nd = d.substr(index + 1);
    252         return child.second->FindDir(nd);
    253       }
    254     }
    255     return NULL;
    256   }
    257 
    258   virtual bool RunFind(const FindCommand& fc, const Loc& loc, int d,
    259                        string* path,
    260                        unordered_map<const DirentNode*, string>* cur_read_dirs,
    261                        vector<string>& out) const override {
    262     ScopedReadDirTracker srdt(this, *path, cur_read_dirs);
    263     if (!srdt.ok()) {
    264       WARN_LOC(loc, "FindEmulator: find: File system loop detected; `%s' "
    265                "is part of the same file system loop as `%s'.",
    266                path->c_str(), srdt.conflicted().c_str());
    267       return true;
    268     }
    269 
    270     fc.read_dirs->insert(*path);
    271 
    272     if (fc.prune_cond && fc.prune_cond->IsTrue(*path, DT_DIR)) {
    273       if (fc.type != FindCommandType::FINDLEAVES) {
    274         out.push_back(*path);
    275       }
    276       return true;
    277     }
    278 
    279     PrintIfNecessary(fc, *path, DT_DIR, d, out);
    280 
    281     if (d >= fc.depth)
    282       return true;
    283 
    284     size_t orig_path_size = path->size();
    285     if (fc.type == FindCommandType::FINDLEAVES) {
    286       size_t orig_out_size = out.size();
    287       for (const auto& p : children_) {
    288         DirentNode* c = p.second;
    289         // We will handle directories later.
    290         if (c->IsDirectory())
    291           continue;
    292         if ((*path)[path->size()-1] != '/')
    293           *path += '/';
    294         *path += c->base();
    295         if (!c->RunFind(fc, loc, d + 1, path, cur_read_dirs, out))
    296           return false;
    297         path->resize(orig_path_size);
    298       }
    299 
    300       // Found a leaf, stop the search.
    301       if (orig_out_size != out.size()) {
    302         // If we've found all possible files in this directory, we don't need
    303         // to add a regen dependency on the directory, we just need to ensure
    304         // that the files are not removed.
    305         if (fc.print_cond->Countable() &&
    306             fc.print_cond->Count() == out.size() - orig_out_size) {
    307           fc.read_dirs->erase(*path);
    308           for (unsigned i = orig_out_size; i < out.size(); i++) {
    309             fc.found_files->push_back(out[i]);
    310           }
    311         }
    312 
    313         return true;
    314       }
    315 
    316       for (const auto& p : children_) {
    317         DirentNode* c = p.second;
    318         if (!c->IsDirectory())
    319           continue;
    320         if ((*path)[path->size()-1] != '/')
    321           *path += '/';
    322         *path += c->base();
    323         if (!c->RunFind(fc, loc, d + 1, path, cur_read_dirs, out))
    324           return false;
    325         path->resize(orig_path_size);
    326       }
    327     } else {
    328       for (const auto& p : children_) {
    329         DirentNode* c = p.second;
    330         if ((*path)[path->size()-1] != '/')
    331           *path += '/';
    332         *path += c->base();
    333         if (!c->RunFind(fc, loc, d + 1, path, cur_read_dirs, out))
    334           return false;
    335         path->resize(orig_path_size);
    336       }
    337     }
    338     return true;
    339   }
    340 
    341   virtual bool IsDirectory() const override { return true; }
    342 
    343   void Add(const string& name, DirentNode* c) {
    344     children_.emplace(children_.end(), name, c);
    345   }
    346 
    347  private:
    348   vector<pair<string, DirentNode*>> children_;
    349 };
    350 
    351 class DirentSymlinkNode : public DirentNode {
    352  public:
    353   explicit DirentSymlinkNode(const string& name)
    354       : DirentNode(name), to_(NULL), errno_(0) {
    355   }
    356 
    357   virtual const DirentNode* FindDir(StringPiece d) const override {
    358     if (errno_ == 0 && to_)
    359       return to_->FindDir(d);
    360     return NULL;
    361   }
    362 
    363   virtual bool RunFind(const FindCommand& fc, const Loc& loc, int d,
    364                        string* path,
    365                        unordered_map<const DirentNode*, string>* cur_read_dirs,
    366                        vector<string>& out) const override {
    367     unsigned char type = DT_LNK;
    368     if (fc.follows_symlinks && errno_ != ENOENT) {
    369       if (errno_) {
    370         if (fc.type != FindCommandType::FINDLEAVES) {
    371           WARN_LOC(loc, "FindEmulator: find: `%s': %s",
    372                    path->c_str(), strerror(errno_));
    373         }
    374         return true;
    375       }
    376 
    377       if (!to_) {
    378         LOG("FindEmulator does not support %s", path->c_str());
    379         return false;
    380       }
    381 
    382       return to_->RunFind(fc, loc, d, path, cur_read_dirs, out);
    383     }
    384     PrintIfNecessary(fc, *path, type, d, out);
    385     return true;
    386   }
    387 
    388   virtual bool IsDirectory() const override {
    389     return errno_ == 0 && to_ && to_->IsDirectory();
    390   }
    391 
    392   void set_to(const DirentNode* to) {
    393     to_ = to;
    394   }
    395 
    396   void set_errno(int e) {
    397     errno_ = e;
    398   }
    399 
    400  private:
    401   const DirentNode* to_;
    402   int errno_;
    403 };
    404 
    405 class FindCommandParser {
    406  public:
    407   FindCommandParser(StringPiece cmd, FindCommand* fc)
    408       : cmd_(cmd), fc_(fc), has_if_(false) {
    409   }
    410 
    411   bool Parse() {
    412     cur_ = cmd_;
    413     if (!ParseImpl()) {
    414       LOG("FindEmulator: Unsupported find command: %.*s", SPF(cmd_));
    415       return false;
    416     }
    417     CHECK(TrimLeftSpace(cur_).empty());
    418     return true;
    419   }
    420 
    421  private:
    422   bool GetNextToken(StringPiece* tok) {
    423     if (!unget_tok_.empty()) {
    424       *tok = unget_tok_;
    425       unget_tok_.clear();
    426       return true;
    427     }
    428 
    429     cur_ = TrimLeftSpace(cur_);
    430 
    431     if (cur_[0] == ';') {
    432       *tok = cur_.substr(0, 1);
    433       cur_ = cur_.substr(1);
    434       return true;
    435     }
    436     if (cur_[0] == '&') {
    437       if (cur_.get(1) != '&') {
    438         return false;
    439       }
    440       *tok = cur_.substr(0, 2);
    441       cur_ = cur_.substr(2);
    442       return true;
    443     }
    444 
    445     size_t i = 0;
    446     while (i < cur_.size() && !isspace(cur_[i]) &&
    447            cur_[i] != ';' && cur_[i] != '&') {
    448       i++;
    449     }
    450 
    451     *tok = cur_.substr(0, i);
    452     cur_ = cur_.substr(i);
    453 
    454     const char c = tok->get(0);
    455     if (c == '\'' || c == '"') {
    456       if (tok->size() < 2 || (*tok)[tok->size()-1] != c)
    457         return false;
    458       *tok = tok->substr(1, tok->size() - 2);
    459       return true;
    460     }
    461 
    462     return true;
    463   }
    464 
    465   void UngetToken(StringPiece tok) {
    466     CHECK(unget_tok_.empty());
    467     if (!tok.empty())
    468       unget_tok_ = tok;
    469   }
    470 
    471   bool ParseTest() {
    472     if (has_if_ || !fc_->testdir.empty())
    473       return false;
    474     StringPiece tok;
    475     if (!GetNextToken(&tok) || tok != "-d")
    476       return false;
    477     if (!GetNextToken(&tok) || tok.empty())
    478       return false;
    479     fc_->testdir = tok.as_string();
    480     return true;
    481   }
    482 
    483   FindCond* ParseFact(StringPiece tok) {
    484     if (tok == "-not" || tok == "\\!") {
    485       if (!GetNextToken(&tok) || tok.empty())
    486         return NULL;
    487       unique_ptr<FindCond> c(ParseFact(tok));
    488       if (!c.get())
    489         return NULL;
    490       return new NotCond(c.release());
    491     } else if (tok == "\\(") {
    492       if (!GetNextToken(&tok) || tok.empty())
    493         return NULL;
    494       unique_ptr<FindCond> c(ParseExpr(tok));
    495       if (!GetNextToken(&tok) || tok != "\\)") {
    496         return NULL;
    497       }
    498       return c.release();
    499     } else if (tok == "-name") {
    500       if (!GetNextToken(&tok) || tok.empty())
    501         return NULL;
    502       return new NameCond(tok.as_string());
    503     } else if (tok == "-type") {
    504       if (!GetNextToken(&tok) || tok.empty())
    505         return NULL;
    506       char type;
    507       if (tok == "b")
    508         type = DT_BLK;
    509       else if (tok == "c")
    510         type = DT_CHR;
    511       else if (tok == "d")
    512         type = DT_DIR;
    513       else if (tok == "p")
    514         type = DT_FIFO;
    515       else if (tok == "l")
    516         type = DT_LNK;
    517       else if (tok == "f")
    518         type = DT_REG;
    519       else if (tok == "s")
    520         type = DT_SOCK;
    521       else
    522         return NULL;
    523       return new TypeCond(type);
    524     } else {
    525       UngetToken(tok);
    526       return NULL;
    527     }
    528   }
    529 
    530   FindCond* ParseTerm(StringPiece tok) {
    531     unique_ptr<FindCond> c(ParseFact(tok));
    532     if (!c.get())
    533       return NULL;
    534     while (true) {
    535       if (!GetNextToken(&tok))
    536         return NULL;
    537       if (tok != "-and" && tok != "-a") {
    538         UngetToken(tok);
    539         return c.release();
    540       }
    541       if (!GetNextToken(&tok) || tok.empty())
    542         return NULL;
    543       unique_ptr<FindCond> r(ParseFact(tok));
    544       if (!r.get()) {
    545         return NULL;
    546       }
    547       c.reset(new AndCond(c.release(), r.release()));
    548     }
    549   }
    550 
    551   FindCond* ParseExpr(StringPiece tok) {
    552     unique_ptr<FindCond> c(ParseTerm(tok));
    553     if (!c.get())
    554       return NULL;
    555     while (true) {
    556       if (!GetNextToken(&tok))
    557         return NULL;
    558       if (tok != "-or" && tok != "-o") {
    559         UngetToken(tok);
    560         return c.release();
    561       }
    562       if (!GetNextToken(&tok) || tok.empty())
    563         return NULL;
    564       unique_ptr<FindCond> r(ParseTerm(tok));
    565       if (!r.get()) {
    566         return NULL;
    567       }
    568       c.reset(new OrCond(c.release(), r.release()));
    569     }
    570   }
    571 
    572   // <expr> ::= <term> {<or> <term>}
    573   // <term> ::= <fact> {<and> <fact>}
    574   // <fact> ::= <not> <fact> | '\(' <expr> '\)' | <pred>
    575   // <not> ::= '-not' | '\!'
    576   // <and> ::= '-and' | '-a'
    577   // <or> ::= '-or' | '-o'
    578   // <pred> ::= <name> | <type> | <maxdepth>
    579   // <name> ::= '-name' NAME
    580   // <type> ::= '-type' TYPE
    581   // <maxdepth> ::= '-maxdepth' MAXDEPTH
    582   FindCond* ParseFindCond(StringPiece tok) {
    583     return ParseExpr(tok);
    584   }
    585 
    586   bool ParseFind() {
    587     fc_->type = FindCommandType::FIND;
    588     StringPiece tok;
    589     while (true) {
    590       if (!GetNextToken(&tok))
    591         return false;
    592       if (tok.empty() || tok == ";")
    593         return true;
    594 
    595       if (tok == "-L") {
    596         fc_->follows_symlinks = true;
    597       } else if (tok == "-prune") {
    598         if (!fc_->print_cond || fc_->prune_cond)
    599           return false;
    600         if (!GetNextToken(&tok) || tok != "-o")
    601           return false;
    602         fc_->prune_cond.reset(fc_->print_cond.release());
    603       } else if (tok == "-print") {
    604         if (!GetNextToken(&tok) || !tok.empty())
    605           return false;
    606         return true;
    607       } else if (tok == "-maxdepth") {
    608         if (!GetNextToken(&tok) || tok.empty())
    609           return false;
    610         const string& depth_str = tok.as_string();
    611         char* endptr;
    612         long d = strtol(depth_str.c_str(), &endptr, 10);
    613         if (endptr != depth_str.data() + depth_str.size() ||
    614             d < 0 || d > INT_MAX) {
    615           return false;
    616         }
    617         fc_->depth = d;
    618       } else if (tok[0] == '-' || tok == "\\(") {
    619         if (fc_->print_cond.get())
    620           return false;
    621         FindCond* c = ParseFindCond(tok);
    622         if (!c)
    623           return false;
    624         fc_->print_cond.reset(c);
    625       } else if (tok == "2>") {
    626         if (!GetNextToken(&tok) || tok != "/dev/null") {
    627           return false;
    628         }
    629         fc_->redirect_to_devnull = true;
    630       } else if (tok.find_first_of("|;&><*'\"") != string::npos) {
    631         return false;
    632       } else {
    633         fc_->finddirs.push_back(tok.as_string());
    634       }
    635     }
    636   }
    637 
    638   bool ParseFindLeaves() {
    639     fc_->type = FindCommandType::FINDLEAVES;
    640     fc_->follows_symlinks = true;
    641     StringPiece tok;
    642     vector<string> findfiles;
    643     while (true) {
    644       if (!GetNextToken(&tok))
    645         return false;
    646       if (tok.empty()) {
    647         if (fc_->finddirs.size() == 0) {
    648           // backwards compatibility
    649           if (findfiles.size() < 2)
    650             return false;
    651           fc_->finddirs.swap(findfiles);
    652           fc_->print_cond.reset(new NameCond(fc_->finddirs.back()));
    653           fc_->finddirs.pop_back();
    654         } else {
    655           if (findfiles.size() < 1)
    656             return false;
    657           for (auto& file : findfiles) {
    658             FindCond* cond = new NameCond(file);
    659             if (fc_->print_cond.get()) {
    660               cond = new OrCond(fc_->print_cond.release(), cond);
    661             }
    662             CHECK(!fc_->print_cond.get());
    663             fc_->print_cond.reset(cond);
    664           }
    665         }
    666         return true;
    667       }
    668 
    669       if (HasPrefix(tok, "--prune=")) {
    670         FindCond* cond = new NameCond(
    671             tok.substr(strlen("--prune=")).as_string());
    672         if (fc_->prune_cond.get()) {
    673           cond = new OrCond(fc_->prune_cond.release(), cond);
    674         }
    675         CHECK(!fc_->prune_cond.get());
    676         fc_->prune_cond.reset(cond);
    677       } else if (HasPrefix(tok, "--mindepth=")) {
    678         string mindepth_str = tok.substr(strlen("--mindepth=")).as_string();
    679         char* endptr;
    680         long d = strtol(mindepth_str.c_str(), &endptr, 10);
    681         if (endptr != mindepth_str.data() + mindepth_str.size() ||
    682             d < INT_MIN || d > INT_MAX) {
    683           return false;
    684         }
    685         fc_->mindepth = d;
    686       } else if (HasPrefix(tok, "--dir=")) {
    687         StringPiece dir= tok.substr(strlen("--dir="));
    688         fc_->finddirs.push_back(dir.as_string());
    689       } else if (HasPrefix(tok, "--")) {
    690         WARN("Unknown flag in findleaves.py: %.*s", SPF(tok));
    691         return false;
    692       } else {
    693         findfiles.push_back(tok.as_string());
    694       }
    695     }
    696   }
    697 
    698   bool ParseImpl() {
    699     while (true) {
    700       StringPiece tok;
    701       if (!GetNextToken(&tok))
    702         return false;
    703 
    704       if (tok.empty())
    705         return true;
    706 
    707       if (tok == "cd") {
    708         if (!GetNextToken(&tok) || tok.empty() || !fc_->chdir.empty())
    709           return false;
    710         fc_->chdir = tok.as_string();
    711         if (!GetNextToken(&tok) || (tok != ";" && tok != "&&"))
    712           return false;
    713       } else if (tok == "if") {
    714         if (!GetNextToken(&tok) || tok != "[")
    715           return false;
    716         if (!ParseTest())
    717           return false;
    718         if (!GetNextToken(&tok) || tok != "]")
    719           return false;
    720         if (!GetNextToken(&tok) || tok != ";")
    721           return false;
    722         if (!GetNextToken(&tok) || tok != "then")
    723           return false;
    724         has_if_ = true;
    725       } else if (tok == "test") {
    726         if (!fc_->chdir.empty())
    727           return false;
    728         if (!ParseTest())
    729           return false;
    730         if (!GetNextToken(&tok) || tok != "&&")
    731           return false;
    732       } else if (tok == "find") {
    733         if (!ParseFind())
    734           return false;
    735         if (has_if_) {
    736           if (!GetNextToken(&tok) || tok != "fi")
    737             return false;
    738         }
    739         if (!GetNextToken(&tok) || !tok.empty())
    740           return false;
    741         return true;
    742       } else if (tok == "build/tools/findleaves.py") {
    743         if (!ParseFindLeaves())
    744           return false;
    745         return true;
    746       } else {
    747         return false;
    748       }
    749     }
    750   }
    751 
    752   StringPiece cmd_;
    753   StringPiece cur_;
    754   FindCommand* fc_;
    755   bool has_if_;
    756   StringPiece unget_tok_;
    757 };
    758 
    759 static FindEmulator* g_instance;
    760 
    761 class FindEmulatorImpl : public FindEmulator {
    762  public:
    763   FindEmulatorImpl()
    764       : node_cnt_(0), is_initialized_(false) {
    765     g_instance = this;
    766   }
    767 
    768   virtual ~FindEmulatorImpl() = default;
    769 
    770   bool CanHandle(StringPiece s) const {
    771     return (!HasPrefix(s, "../") &&
    772             !HasPrefix(s, "/") &&
    773             !HasPrefix(s, ".repo") &&
    774             !HasPrefix(s, ".git"));
    775   }
    776 
    777   const DirentNode* FindDir(StringPiece d, bool* should_fallback) {
    778     const DirentNode* r = root_->FindDir(d);
    779     if (!r) {
    780       *should_fallback = Exists(d);
    781     }
    782     return r;
    783   }
    784 
    785   virtual bool HandleFind(const string& cmd UNUSED, const FindCommand& fc,
    786                           const Loc& loc, string* out) override {
    787     if (!CanHandle(fc.chdir)) {
    788       LOG("FindEmulator: Cannot handle chdir (%.*s): %s",
    789           SPF(fc.chdir), cmd.c_str());
    790       return false;
    791     }
    792 
    793     if (!is_initialized_) {
    794       ScopedTimeReporter tr("init find emulator time");
    795       root_.reset(ConstructDirectoryTree(""));
    796       if (!root_) {
    797         ERROR("FindEmulator: Cannot open root directory");
    798       }
    799       ResolveSymlinks();
    800       LOG_STAT("%d find nodes", node_cnt_);
    801       is_initialized_ = true;
    802     }
    803 
    804     if (!fc.testdir.empty()) {
    805       if (!CanHandle(fc.testdir)) {
    806         LOG("FindEmulator: Cannot handle test dir (%.*s): %s",
    807             SPF(fc.testdir), cmd.c_str());
    808         return false;
    809       }
    810       bool should_fallback = false;
    811       if (!FindDir(fc.testdir, &should_fallback)) {
    812         LOG("FindEmulator: Test dir (%.*s) not found: %s",
    813             SPF(fc.testdir), cmd.c_str());
    814         return !should_fallback;
    815       }
    816     }
    817 
    818     if (!fc.chdir.empty()) {
    819       if (!CanHandle(fc.chdir)) {
    820         LOG("FindEmulator: Cannot handle chdir (%.*s): %s",
    821             SPF(fc.chdir), cmd.c_str());
    822         return false;
    823       }
    824       bool should_fallback = false;
    825       if (!FindDir(fc.chdir, &should_fallback)) {
    826         if (should_fallback)
    827           return false;
    828         if (!fc.redirect_to_devnull) {
    829           WARN_LOC(loc, "FindEmulator: cd: %.*s: No such file or directory",
    830                    SPF(fc.chdir));
    831         }
    832         return true;
    833       }
    834     }
    835 
    836     vector<string> results;
    837     for (const string& finddir : fc.finddirs) {
    838       const string dir = ConcatDir(fc.chdir, finddir);
    839 
    840       if (!CanHandle(dir)) {
    841         LOG("FindEmulator: Cannot handle find dir (%s): %s",
    842             dir.c_str(), cmd.c_str());
    843         return false;
    844       }
    845 
    846       bool should_fallback = false;
    847       const DirentNode* base = FindDir(dir, &should_fallback);
    848       if (!base) {
    849         if (should_fallback) {
    850           return false;
    851         }
    852         if (!fc.redirect_to_devnull) {
    853           WARN_LOC(loc, "FindEmulator: find: `%s': No such file or directory",
    854                    ConcatDir(fc.chdir, finddir).c_str());
    855         }
    856         continue;
    857       }
    858 
    859       string path = finddir;
    860       unordered_map<const DirentNode*, string> cur_read_dirs;
    861       if (!base->RunFind(fc, loc, 0, &path, &cur_read_dirs, results)) {
    862         LOG("FindEmulator: RunFind failed: %s", cmd.c_str());
    863         return false;
    864       }
    865     }
    866 
    867     if (results.size() > 0) {
    868       // Calculate and reserve necessary space in out
    869       size_t new_length = 0;
    870       for (const string& result : results) {
    871         new_length += result.size() + 1;
    872       }
    873       out->reserve(out->size() + new_length - 1);
    874 
    875       if (fc.type == FindCommandType::FINDLEAVES) {
    876         sort(results.begin(), results.end());
    877       }
    878 
    879       WordWriter writer(out);
    880       for (const string& result : results) {
    881         writer.Write(result);
    882       }
    883     }
    884 
    885     LOG("FindEmulator: OK");
    886     return true;
    887   }
    888 
    889  private:
    890   static unsigned char GetDtTypeFromStat(const struct stat& st) {
    891     if (S_ISREG(st.st_mode)) {
    892       return DT_REG;
    893     } else if (S_ISDIR(st.st_mode)) {
    894       return DT_DIR;
    895     } else if (S_ISCHR(st.st_mode)) {
    896       return DT_CHR;
    897     } else if (S_ISBLK(st.st_mode)) {
    898       return DT_BLK;
    899     } else if (S_ISFIFO(st.st_mode)) {
    900       return DT_FIFO;
    901     } else if (S_ISLNK(st.st_mode)) {
    902       return DT_LNK;
    903     } else if (S_ISSOCK(st.st_mode)) {
    904       return DT_SOCK;
    905     } else {
    906       return DT_UNKNOWN;
    907     }
    908   }
    909 
    910   static unsigned char GetDtType(const string& path) {
    911     struct stat st;
    912     if (lstat(path.c_str(), &st)) {
    913       PERROR("stat for %s", path.c_str());
    914     }
    915     return GetDtTypeFromStat(st);
    916   }
    917 
    918   DirentNode* ConstructDirectoryTree(const string& path) {
    919     DIR* dir = opendir(path.empty() ? "." : path.c_str());
    920     if (!dir) {
    921       if (errno == ENOENT) {
    922         LOG("opendir failed: %s", path.c_str());
    923         return NULL;
    924       } else {
    925         PERROR("opendir failed: %s", path.c_str());
    926       }
    927     }
    928 
    929     DirentDirNode* n = new DirentDirNode(path);
    930 
    931     struct dirent* ent;
    932     while ((ent = readdir(dir)) != NULL) {
    933       if (!strcmp(ent->d_name, ".") ||
    934           !strcmp(ent->d_name, "..") ||
    935           !strcmp(ent->d_name, ".repo") ||
    936           !strcmp(ent->d_name, ".git"))
    937         continue;
    938 
    939       string npath = path;
    940       if (!path.empty())
    941         npath += '/';
    942       npath += ent->d_name;
    943 
    944       DirentNode* c = NULL;
    945       auto d_type = ent->d_type;
    946       if (d_type == DT_UNKNOWN) {
    947         d_type = GetDtType(npath);
    948         CHECK(d_type != DT_UNKNOWN);
    949       }
    950       if (d_type == DT_DIR) {
    951         c = ConstructDirectoryTree(npath);
    952         if (c == NULL) {
    953           continue;
    954         }
    955       } else if (d_type == DT_LNK) {
    956         auto s = new DirentSymlinkNode(npath);
    957         symlinks_.push_back(make_pair(npath, s));
    958         c = s;
    959       } else {
    960         c = new DirentFileNode(npath, d_type);
    961       }
    962       node_cnt_++;
    963       n->Add(ent->d_name, c);
    964     }
    965     closedir(dir);
    966 
    967     return n;
    968   }
    969 
    970   void ResolveSymlinks() {
    971     vector<pair<string, DirentSymlinkNode*>> symlinks;
    972     symlinks.swap(symlinks_);
    973     for (const auto& p : symlinks) {
    974       const string& path = p.first;
    975       DirentSymlinkNode* s = p.second;
    976 
    977       char buf[PATH_MAX+1];
    978       buf[PATH_MAX] = 0;
    979       ssize_t len = readlink(path.c_str(), buf, PATH_MAX);
    980       if (len < 0) {
    981         WARN("readlink failed: %s", path.c_str());
    982         continue;
    983       }
    984       buf[len] = 0;
    985 
    986       struct stat st;
    987       unsigned char type = DT_UNKNOWN;
    988       if (stat(path.c_str(), &st) == 0) {
    989         type = GetDtTypeFromStat(st);
    990       } else {
    991         s->set_errno(errno);
    992         LOG("stat failed: %s: %s", path.c_str(), strerror(errno));
    993       }
    994 
    995       if (*buf != '/') {
    996         const string npath = ConcatDir(Dirname(path), buf);
    997         bool should_fallback = false;
    998         const DirentNode* to = FindDir(npath, &should_fallback);
    999         if (to) {
   1000           s->set_to(to);
   1001           continue;
   1002         }
   1003       }
   1004 
   1005       if (type == DT_DIR) {
   1006         if (path.find('/') == string::npos) {
   1007           DirentNode* dir = ConstructDirectoryTree(path);
   1008           if (dir != NULL) {
   1009             s->set_to(dir);
   1010           } else {
   1011             s->set_errno(errno);
   1012           }
   1013         }
   1014       } else if (type != DT_LNK && type != DT_UNKNOWN) {
   1015           s->set_to(new DirentFileNode(path, type));
   1016       }
   1017     }
   1018 
   1019     if (!symlinks_.empty())
   1020       ResolveSymlinks();
   1021   }
   1022 
   1023   unique_ptr<DirentNode> root_;
   1024   vector<pair<string, DirentSymlinkNode*>> symlinks_;
   1025   int node_cnt_;
   1026   bool is_initialized_;
   1027 };
   1028 
   1029 }  // namespace
   1030 
   1031 FindCommand::FindCommand()
   1032     : follows_symlinks(false), depth(INT_MAX), mindepth(INT_MIN),
   1033       redirect_to_devnull(false),
   1034       found_files(new vector<string>()),
   1035       read_dirs(new unordered_set<string>()) {
   1036 }
   1037 
   1038 FindCommand::~FindCommand() {
   1039 }
   1040 
   1041 bool FindCommand::Parse(const string& cmd) {
   1042   FindCommandParser fcp(cmd, this);
   1043   if (!HasWord(cmd, "find") && !HasWord(cmd, "build/tools/findleaves.py"))
   1044     return false;
   1045 
   1046   if (!fcp.Parse())
   1047     return false;
   1048 
   1049   NormalizePath(&chdir);
   1050   NormalizePath(&testdir);
   1051   if (finddirs.empty())
   1052     finddirs.push_back(".");
   1053   return true;
   1054 }
   1055 
   1056 FindEmulator* FindEmulator::Get() {
   1057   return g_instance;
   1058 }
   1059 
   1060 void InitFindEmulator() {
   1061   new FindEmulatorImpl();
   1062 }
   1063