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:
NameCond(const string & n)49 explicit NameCond(const string& n)
50 : name_(n) {
51 }
IsTrue(const string & path,unsigned char) const52 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:
TypeCond(unsigned char t)61 explicit TypeCond(unsigned char t)
62 : type_(t) {
63 }
IsTrue(const string &,unsigned char type) const64 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:
NotCond(FindCond * c)73 NotCond(FindCond* c)
74 : c_(c) {
75 }
IsTrue(const string & path,unsigned char type) const76 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:
AndCond(FindCond * c1,FindCond * c2)85 AndCond(FindCond* c1, FindCond* c2)
86 : c1_(c1), c2_(c2) {
87 }
IsTrue(const string & path,unsigned char type) const88 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:
OrCond(FindCond * c1,FindCond * c2)99 OrCond(FindCond* c1, FindCond* c2)
100 : c1_(c1), c2_(c2) {
101 }
IsTrue(const string & path,unsigned char type) const102 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
FindDir(StringPiece) const115 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
base() const125 const string& base() const { return base_; }
126
127 protected:
DirentNode(const string & name)128 explicit DirentNode(const string& name) {
129 base_ = Basename(name).as_string();
130 }
131
PrintIfNecessary(const FindCommand & fc,const string & path,unsigned char type,int d,string * out) const132 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:
DirentFileNode(const string & name,unsigned char type)150 DirentFileNode(const string& name, unsigned char type)
151 : DirentNode(name), type_(type) {
152 }
153
RunFind(const FindCommand & fc,int d,string * path,unordered_map<const DirentNode *,string> *,string * out) const154 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
IsDirectory() const162 virtual bool IsDirectory() const override { return false; }
163
164 private:
165 unsigned char type_;
166 };
167
168 struct ScopedReadDirTracker {
169 public:
ScopedReadDirTracker__anon2fe5d9d00111::ScopedReadDirTracker170 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
~ScopedReadDirTracker__anon2fe5d9d00111::ScopedReadDirTracker182 ~ScopedReadDirTracker() {
183 if (n_)
184 cur_read_dirs_->erase(n_);
185 }
186
ok__anon2fe5d9d00111::ScopedReadDirTracker187 bool ok() const { return conflicted_.empty(); }
conflicted__anon2fe5d9d00111::ScopedReadDirTracker188 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:
DirentDirNode(const string & name)198 explicit DirentDirNode(const string& name)
199 : DirentNode(name) {
200 }
201
~DirentDirNode()202 ~DirentDirNode() {
203 for (auto& p : children_) {
204 delete p.second;
205 }
206 }
207
FindDir(StringPiece d) const208 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
RunFind(const FindCommand & fc,int d,string * path,unordered_map<const DirentNode *,string> * cur_read_dirs,string * out) const224 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
IsDirectory() const295 virtual bool IsDirectory() const override { return true; }
296
Add(const string & name,DirentNode * c)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:
DirentSymlinkNode(const string & name)307 explicit DirentSymlinkNode(const string& name)
308 : DirentNode(name), to_(NULL), errno_(0) {
309 }
310
FindDir(StringPiece d) const311 virtual const DirentNode* FindDir(StringPiece d) const override {
312 if (errno_ == 0 && to_)
313 return to_->FindDir(d);
314 return NULL;
315 }
316
RunFind(const FindCommand & fc,int d,string * path,unordered_map<const DirentNode *,string> * cur_read_dirs,string * out) const317 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
IsDirectory() const342 virtual bool IsDirectory() const override {
343 return errno_ == 0 && to_ && to_->IsDirectory();
344 }
345
set_to(const DirentNode * to)346 void set_to(const DirentNode* to) {
347 to_ = to;
348 }
349
set_errno(int e)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:
FindCommandParser(StringPiece cmd,FindCommand * fc)361 FindCommandParser(StringPiece cmd, FindCommand* fc)
362 : cmd_(cmd), fc_(fc), has_if_(false) {
363 }
364
Parse()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:
GetNextToken(StringPiece * tok)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
UngetToken(StringPiece tok)419 void UngetToken(StringPiece tok) {
420 CHECK(unget_tok_.empty());
421 if (!tok.empty())
422 unget_tok_ = tok;
423 }
424
ParseTest()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
ParseFact(StringPiece tok)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
ParseTerm(StringPiece tok)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
ParseExpr(StringPiece tok)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
ParseFindCond(StringPiece tok)536 FindCond* ParseFindCond(StringPiece tok) {
537 return ParseExpr(tok);
538 }
539
ParseFind()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
ParseFindLeaves()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
ParseImpl()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:
FindEmulatorImpl()698 FindEmulatorImpl()
699 : node_cnt_(0), is_initialized_(false) {
700 g_instance = this;
701 }
702
703 virtual ~FindEmulatorImpl() = default;
704
CanHandle(StringPiece s) const705 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
FindDir(StringPiece d,bool * should_fallback)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
HandleFind(const string & cmd UNUSED,const FindCommand & fc,string * out)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:
GetDtTypeFromStat(const struct stat & st)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
GetDtType(const string & path)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
ConstructDirectoryTree(const string & path)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
ResolveSymlinks()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
FindCommand()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
~FindCommand()951 FindCommand::~FindCommand() {
952 }
953
Parse(const string & cmd)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
Get()969 FindEmulator* FindEmulator::Get() {
970 return g_instance;
971 }
972
InitFindEmulator()973 void InitFindEmulator() {
974 new FindEmulatorImpl();
975 }
976