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