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