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