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
37class 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
45namespace {
46
47class 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
59class 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
71class 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
83class 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
97class 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
111class 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
148class 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
168struct 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
196class 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
305class 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
359class 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
694static FindEmulator* g_instance;
695
696class 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
945FindCommand::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
951FindCommand::~FindCommand() {
952}
953
954bool 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
969FindEmulator* FindEmulator::Get() {
970  return g_instance;
971}
972
973void InitFindEmulator() {
974  new FindEmulatorImpl();
975}
976