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