[C++] Make FindEmulator's symlink support better

Now FindEmulator supports symlinks which refer

- a file in FindEmulator or
- a file which isn't a directory nor a symlink

Also findleaves.py follows symbolic links.

1 files changed, 145 insertions, 60 deletions

diff --git a/find.cc b/find.cc
index f50a5ec..e8aa92a 100644
--- a/find.cc
+++ b/find.cc
@@ -116,7 +116,11 @@ class DirentNode {
     return NULL;
   }
   virtual bool RunFind(const FindCommand& fc, int d,
-                       string* path, string* out) const = 0;
+                       string* path,
+                       unordered_map<const DirentNode*, string>* cur_read_dirs,
+                       string* out) const = 0;
+
+  virtual bool IsDirectory() const = 0;
 
   const string& base() const { return base_; }
 
@@ -148,15 +152,47 @@ class DirentFileNode : public DirentNode {
   }
 
   virtual bool RunFind(const FindCommand& fc, int d,
-                       string* path, string* out) const {
+                       string* path,
+                       unordered_map<const DirentNode*, string>*,
+                       string* out) const {
     PrintIfNecessary(fc, *path, type_, d, out);
     return true;
   }
 
+  virtual bool IsDirectory() const override { return false; }
+
  private:
   unsigned char type_;
 };
 
+struct ScopedReadDirTracker {
+ public:
+  ScopedReadDirTracker(const DirentNode* n,
+                       const string& path,
+                       unordered_map<const DirentNode*, string>* cur_read_dirs)
+      : n_(NULL), cur_read_dirs_(cur_read_dirs) {
+    const auto& p = cur_read_dirs->emplace(n, path);
+    if (p.second) {
+      n_ = n;
+    } else {
+      conflicted_ = p.first->second;
+    }
+  }
+
+  ~ScopedReadDirTracker() {
+    if (n_)
+      cur_read_dirs_->erase(n_);
+  }
+
+  bool ok() const { return conflicted_.empty(); }
+  const string& conflicted() const { return conflicted_; }
+
+ private:
+  string conflicted_;
+  const DirentNode* n_;
+  unordered_map<const DirentNode*, string>* cur_read_dirs_;
+};
+
 class DirentDirNode : public DirentNode {
  public:
   explicit DirentDirNode(const string& name)
@@ -186,8 +222,18 @@ class DirentDirNode : public DirentNode {
   }
 
   virtual bool RunFind(const FindCommand& fc, int d,
-                       string* path, string* out) const {
-    fc.read_dirs->push_back(*path);
+                       string* path,
+                       unordered_map<const DirentNode*, string>* cur_read_dirs,
+                       string* out) const {
+    ScopedReadDirTracker srdt(this, *path, cur_read_dirs);
+    if (!srdt.ok()) {
+      fprintf(stderr, "FindEmulator: find: File system loop detected; `%s' is "
+              "part of the same file system loop as `%s'.\n",
+              path->c_str(), srdt.conflicted().c_str());
+      return true;
+    }
+
+    fc.read_dirs->insert(*path);
 
     if (fc.prune_cond && fc.prune_cond->IsTrue(base_, DT_DIR)) {
       if (fc.type != FindCommandType::FINDLEAVES) {
@@ -208,12 +254,12 @@ class DirentDirNode : public DirentNode {
       for (const auto& p : children_) {
         DirentNode* c = p.second;
         // We will handle directories later.
-        if (dynamic_cast<DirentDirNode*>(c))
+        if (c->IsDirectory())
           continue;
         if ((*path)[path->size()-1] != '/')
           *path += '/';
         *path += c->base();
-        if (!c->RunFind(fc, d + 1, path, out))
+        if (!c->RunFind(fc, d + 1, path, cur_read_dirs, out))
           return false;
         path->resize(orig_path_size);
         // Found a leaf, stop the search.
@@ -223,12 +269,12 @@ class DirentDirNode : public DirentNode {
 
       for (const auto& p : children_) {
         DirentNode* c = p.second;
-        if (!dynamic_cast<DirentDirNode*>(c))
+        if (!c->IsDirectory())
           continue;
         if ((*path)[path->size()-1] != '/')
           *path += '/';
         *path += c->base();
-        if (!c->RunFind(fc, d + 1, path, out))
+        if (!c->RunFind(fc, d + 1, path, cur_read_dirs, out))
           return false;
         path->resize(orig_path_size);
       }
@@ -238,7 +284,7 @@ class DirentDirNode : public DirentNode {
         if ((*path)[path->size()-1] != '/')
           *path += '/';
         *path += c->base();
-        if (!c->RunFind(fc, d + 1, path, out))
+        if (!c->RunFind(fc, d + 1, path, cur_read_dirs, out))
           return false;
         path->resize(orig_path_size);
       }
@@ -246,6 +292,8 @@ class DirentDirNode : public DirentNode {
     return true;
   }
 
+  virtual bool IsDirectory() const override { return true; }
+
   void Add(const string& name, DirentNode* c) {
     children_.emplace(children_.end(), name, c);
   }
@@ -257,58 +305,49 @@ class DirentDirNode : public DirentNode {
 class DirentSymlinkNode : public DirentNode {
  public:
   explicit DirentSymlinkNode(const string& name)
-      : DirentNode(name) {
+      : DirentNode(name), to_(NULL), errno_(0) {
   }
 
   virtual bool RunFind(const FindCommand& fc, int d,
-                       string* path, string* out) const {
+                       string* path,
+                       unordered_map<const DirentNode*, string>* cur_read_dirs,
+                       string* out) const {
     unsigned char type = DT_LNK;
-    if (fc.follows_symlinks) {
-      // TODO
-      LOG("FindEmulator: symlink is hard");
-      return false;
-
-      char buf[PATH_MAX+1];
-      buf[PATH_MAX] = 0;
-      LOG("path=%s", path->c_str());
-      ssize_t len = readlink(path->c_str(), buf, PATH_MAX);
-      if (len > 0) {
-        buf[len] = 0;
-        string oldpath;
-        if (buf[0] != '/') {
-          Dirname(*path).AppendToString(&oldpath);
-          oldpath += '/';
-        }
-        oldpath += buf;
-
-        LOG("buf=%s old=%s", buf, oldpath.c_str());
-
-        struct stat st;
-        if (stat(oldpath.c_str(), &st) == 0) {
-          LOG("st OK");
-          if (S_ISREG(st.st_mode)) {
-            type = DT_REG;
-          } else if (S_ISDIR(st.st_mode)) {
-            type = DT_DIR;
-          } else if (S_ISCHR(st.st_mode)) {
-            type = DT_CHR;
-          } else if (S_ISBLK(st.st_mode)) {
-            type = DT_BLK;
-          } else if (S_ISFIFO(st.st_mode)) {
-            type = DT_FIFO;
-          } else if (S_ISLNK(st.st_mode)) {
-            type = DT_LNK;
-          } else if (S_ISSOCK(st.st_mode)) {
-            type = DT_SOCK;
-          } else {
-            return false;
-          }
+    if (fc.follows_symlinks && errno_ != ENOENT) {
+      if (errno_) {
+        if (fc.type != FindCommandType::FINDLEAVES) {
+          fprintf(stderr, "FindEmulator: find: `%s': %s\n",
+                  path->c_str(), strerror(errno_));
         }
+        return true;
       }
+
+      if (!to_) {
+        LOG("FindEmulator does not support %s", path->c_str());
+        return false;
+      }
+
+      return to_->RunFind(fc, d, path, cur_read_dirs, out);
     }
     PrintIfNecessary(fc, *path, type, d, out);
     return true;
   }
+
+  virtual bool IsDirectory() const override {
+    return errno_ == 0 && to_ && to_->IsDirectory();
+  }
+
+  void set_to(const DirentNode* to) {
+    to_ = to;
+  }
+
+  void set_errno(int e) {
+    errno_ = e;
+  }
+
+ private:
+  const DirentNode* to_;
+  int errno_;
 };
 
 class FindCommandParser {
@@ -546,6 +585,7 @@ class FindCommandParser {
 
   bool ParseFindLeaves() {
     fc_->type = FindCommandType::FINDLEAVES;
+    fc_->follows_symlinks = true;
     StringPiece tok;
     while (true) {
       if (!GetNextToken(&tok))
@@ -683,6 +723,7 @@ class FindEmulatorImpl : public FindEmulator {
     if (!is_initialized_) {
       ScopedTimeReporter tr("init find emulator time");
       root_.reset(ConstructDirectoryTree(""));
+      ResolveSymlinks();
       LOG_STAT("%d find nodes", node_cnt_);
       is_initialized_ = true;
     }
@@ -747,7 +788,8 @@ class FindEmulatorImpl : public FindEmulator {
       }
 
       string path = finddir.as_string();
-      if (!base->RunFind(fc, 0, &path, out)) {
+      unordered_map<const DirentNode*, string> cur_read_dirs;
+      if (!base->RunFind(fc, 0, &path, &cur_read_dirs, out)) {
         LOG("FindEmulator: RunFind failed: %s", cmd.c_str());
         out->resize(orig_out_size);
         return false;
@@ -766,12 +808,7 @@ class FindEmulatorImpl : public FindEmulator {
   }
 
  private:
-  static unsigned char GetDtType(const string& path) {
-    struct stat st;
-    if (lstat(path.c_str(), &st)) {
-      PERROR("stat for %s", path.c_str());
-    }
-
+  static unsigned char GetDtTypeFromStat(const struct stat& st) {
     if (S_ISREG(st.st_mode)) {
       return DT_REG;
     } else if (S_ISDIR(st.st_mode)) {
@@ -791,6 +828,14 @@ class FindEmulatorImpl : public FindEmulator {
     }
   }
 
+  static unsigned char GetDtType(const string& path) {
+    struct stat st;
+    if (lstat(path.c_str(), &st)) {
+      PERROR("stat for %s", path.c_str());
+    }
+    return GetDtTypeFromStat(st);
+  }
+
   DirentNode* ConstructDirectoryTree(const string& path) {
     DIR* dir = opendir(path.empty() ? "." : path.c_str());
     if (!dir)
@@ -821,7 +866,9 @@ class FindEmulatorImpl : public FindEmulator {
       if (d_type == DT_DIR) {
         c = ConstructDirectoryTree(npath);
       } else if (d_type == DT_LNK) {
-        c = new DirentSymlinkNode(npath);
+        auto s = new DirentSymlinkNode(npath);
+        symlinks_.push_back(make_pair(npath, s));
+        c = s;
       } else {
         c = new DirentFileNode(npath, d_type);
       }
@@ -833,7 +880,45 @@ class FindEmulatorImpl : public FindEmulator {
     return n;
   }
 
+  void ResolveSymlinks() {
+    for (const auto& p : symlinks_) {
+      const string& path = p.first;
+      DirentSymlinkNode* s = p.second;
+
+      char buf[PATH_MAX+1];
+      buf[PATH_MAX] = 0;
+      ssize_t len = readlink(path.c_str(), buf, PATH_MAX);
+      if (len < 0) {
+        WARN("readlink failed: %s", path.c_str());
+        continue;
+      }
+      buf[len] = 0;
+
+      struct stat st;
+      if (stat(path.c_str(), &st) < 0) {
+        s->set_errno(errno);
+        LOG("stat failed: %s: %s", path.c_str(), strerror(errno));
+      }
+
+      if (*buf != '/') {
+        const string npath = ConcatDir(Dirname(path), buf);
+        bool should_fallback = false;
+        const DirentNode* to = FindDir(npath, &should_fallback);
+        if (to) {
+          s->set_to(to);
+          continue;
+        }
+      }
+
+      unsigned char type = GetDtTypeFromStat(st);
+      if (type != DT_DIR && type != DT_LNK) {
+        s->set_to(new DirentFileNode(path, type));
+      }
+    }
+  }
+
   unique_ptr<DirentNode> root_;
+  vector<pair<string, DirentSymlinkNode*>> symlinks_;
   int node_cnt_;
   bool is_initialized_;
 };
@@ -843,7 +928,7 @@ class FindEmulatorImpl : public FindEmulator {
 FindCommand::FindCommand()
     : follows_symlinks(false), depth(INT_MAX), mindepth(INT_MIN),
       redirect_to_devnull(false),
-      read_dirs(new vector<string>()) {
+      read_dirs(new unordered_set<string>()) {
 }
 
 FindCommand::~FindCommand() {