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