// Copyright 2015 Google Inc. All rights reserved
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// +build ignore

#include "find.h"

#include <dirent.h>
#include <fnmatch.h>
#include <limits.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>

#include <map>
#include <memory>
#include <vector>

//#undef NOLOG

#include "log.h"
#include "string_piece.h"
#include "strutil.h"
#include "time.h"

namespace {

class Cond {
 public:
  virtual ~Cond() = default;
  virtual bool IsTrue(const string& name, unsigned char type) const = 0;
 protected:
  Cond() = default;
};

class NameCond : public Cond {
 public:
  explicit NameCond(const string& n)
      : name_(n) {
  }
  virtual bool IsTrue(const string& name, unsigned char) const {
    return fnmatch(name_.c_str(), name.c_str(), 0) == 0;
  }
 private:
  string name_;
};

class TypeCond : public Cond {
 public:
  explicit TypeCond(unsigned char t)
      : type_(t) {
  }
  virtual bool IsTrue(const string&, unsigned char type) const {
    return type == type_;
  }
 private:
  unsigned char type_;
};

class NotCond : public Cond {
 public:
  NotCond(Cond* c)
      : c_(c) {
  }
  virtual bool IsTrue(const string& name, unsigned char type) const {
    return !c_->IsTrue(name, type);
  }
 private:
  unique_ptr<Cond> c_;
};

class AndCond : public Cond {
 public:
  AndCond(Cond* c1, Cond* c2)
      : c1_(c1), c2_(c2) {
  }
  virtual bool IsTrue(const string& name, unsigned char type) const {
    if (c1_->IsTrue(name, type))
      return c2_->IsTrue(name, type);
    return false;
  }
 private:
  unique_ptr<Cond> c1_, c2_;
};

class OrCond : public Cond {
 public:
  OrCond(Cond* c1, Cond* c2)
      : c1_(c1), c2_(c2) {
  }
  virtual bool IsTrue(const string& name, unsigned char type) const {
    if (!c1_->IsTrue(name, type))
      return c2_->IsTrue(name, type);
    return true;
  }
 private:
  unique_ptr<Cond> c1_, c2_;
};

struct FindCommand {
  FindCommand()
      : follows_symlinks(false), depth(INT_MAX) {
  }
  ~FindCommand() {
  }

  StringPiece chdir;
  StringPiece testdir;
  vector<StringPiece> finddirs;
  bool follows_symlinks;
  unique_ptr<Cond> print_cond;
  unique_ptr<Cond> prune_cond;
  int depth;
};

class DirentNode {
 public:
  virtual ~DirentNode() = default;

  virtual const DirentNode* FindDir(StringPiece) const {
    return NULL;
  }
  virtual bool RunFind(const FindCommand& fc, int d,
                       string* path, string* out) const = 0;

  const string& base() const { return base_; }

 protected:
  explicit DirentNode(const string& name) {
    base_ = Basename(name).as_string();
  }

  void PrintIfNecessary(const FindCommand& fc,
                        const string& path,
                        unsigned char type,
                        string* out) const {
    if (fc.print_cond && !fc.print_cond->IsTrue(base_, type))
      return;
    *out += path;
    *out += ' ';
  }

  string base_;
};

class DirentFileNode : public DirentNode {
 public:
  DirentFileNode(const string& name, unsigned char type)
      : DirentNode(name), type_(type) {
  }

  virtual bool RunFind(const FindCommand& fc, int,
                       string* path, string* out) const {
    PrintIfNecessary(fc, *path, type_, out);
    return true;
  }

 private:
  unsigned char type_;
};

class DirentDirNode : public DirentNode {
 public:
  explicit DirentDirNode(const string& name)
      : DirentNode(name) {
  }
  ~DirentDirNode() {
    for (auto& p : children_) {
      delete p.second;
    }
  }

  virtual const DirentNode* FindDir(StringPiece d) const {
    if (d.empty() || d == ".")
      return this;
    size_t index = d.find('/');
    const string& p = d.substr(0, index).as_string();
    auto found = children_.find(p);
    if (found == children_.end())
      return NULL;
    if (index == string::npos)
      return found->second;
    StringPiece nd = d.substr(index + 1);
    return found->second->FindDir(nd);
  }

  virtual bool RunFind(const FindCommand& fc, int d,
                       string* path, string* out) const {
    if (fc.prune_cond && fc.prune_cond->IsTrue(base_, DT_DIR)) {
      *out += *path;
      *out += ' ';
      return true;
    }
    PrintIfNecessary(fc, *path, DT_DIR, out);

    if (d >= fc.depth)
      return true;

    size_t orig_path_size = path->size();
    for (const auto& p : children_) {
      DirentNode* c = p.second;
      if ((*path)[path->size()-1] != '/')
        *path += '/';
      *path += c->base();
      if (!c->RunFind(fc, d + 1, path, out))
        return false;
      path->resize(orig_path_size);
    }
    return true;
  }

  void Add(const string& name, DirentNode* c) {
    auto p = children_.emplace(name, c);
    CHECK(p.second);
  }

 private:
  map<string, DirentNode*> children_;
};

class DirentSymlinkNode : public DirentNode {
 public:
  explicit DirentSymlinkNode(const string& name)
      : DirentNode(name) {
  }

  virtual bool RunFind(const FindCommand& fc, int,
                       string* path, 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;
          }
        }
      }
    }
    PrintIfNecessary(fc, *path, type, out);
    return true;
  }
};

static FindEmulator* g_instance;

class FindEmulatorImpl : public FindEmulator {
 public:
  FindEmulatorImpl() {
    ScopedTimeReporter tr("init find emulator time");
    root_.reset(ConstructDirectoryTree(""));
    g_instance = this;
  }

  virtual ~FindEmulatorImpl() = default;

  static string ConcatDir(StringPiece b, StringPiece n) {
    string r;
    if (!b.empty()) {
      b.AppendToString(&r);
      r += '/';
    }
    n.AppendToString(&r);
    NormalizePath(&r);
    return r;
  }

  virtual bool HandleFind(const string& cmd, string* out) override {
    FindCommand fc;
    if (!ParseFindCommand(cmd, &fc))
      return false;

    if (HasPrefix(fc.chdir, "/")) {
      LOG("FindEmulator: Cannot handle abspath: %s", cmd.c_str());
      return false;
    }
    for (StringPiece finddir : fc.finddirs) {
      if (HasPrefix(finddir, "/")) {
        LOG("FindEmulator: Cannot handle abspath: %s", cmd.c_str());
        return false;
      }
    }

    if (!fc.testdir.empty() && !root_->FindDir(fc.testdir)) {
      LOG("FindEmulator: Test dir (%.*s) not found: %s",
          SPF(fc.testdir), cmd.c_str());
      return false;
    }

    const size_t orig_out_size = out->size();
    for (StringPiece finddir : fc.finddirs) {
      const DirentNode* base = root_->FindDir(ConcatDir(fc.chdir, finddir));
      if (!base) {
        LOG("FindEmulator: Find dir (%s) not found: %s",
            ConcatDir(fc.chdir, finddir).c_str(), cmd.c_str());
        out->resize(orig_out_size);
        return false;
      }

      string path = finddir.as_string();
      if (!base->RunFind(fc, 0, &path, out)) {
        LOG("FindEmulator: RunFind failed: %s", cmd.c_str());
        out->resize(orig_out_size);
        return false;
      }
    }

    if (!out->empty() && (*out)[out->size()-1] == ' ')
      out->resize(out->size()-1);
    LOG("FindEmulator: OK");
    return true;
  }

 private:
  class FindCommandParser {
   public:
    FindCommandParser(StringPiece cmd, FindCommand* fc)
        : cmd_(cmd), fc_(fc), has_if_(false) {
    }

    bool Parse() {
      cur_ = cmd_;
      if (!ParseImpl()) {
        LOG("FindEmulator: Unsupported find command: %.*s", SPF(cmd_));
        return false;
      }
      CHECK(TrimLeftSpace(cur_).empty());
      return true;
    }

   private:
    bool GetNextToken(StringPiece* tok) {
      if (!unget_tok_.empty()) {
        *tok = unget_tok_;
        unget_tok_.clear();
        return true;
      }

      cur_ = TrimLeftSpace(cur_);

      if (cur_[0] == ';') {
        *tok = cur_.substr(0, 1);
        cur_ = cur_.substr(1);
        return true;
      }
      if (cur_[0] == '&') {
        if (cur_.get(1) != '&') {
          return false;
        }
        *tok = cur_.substr(0, 2);
        cur_ = cur_.substr(2);
        return true;
      }

      size_t i = 0;
      while (i < cur_.size() && !isspace(cur_[i]) &&
             cur_[i] != ';' && cur_[i] != '&') {
        i++;
      }

      *tok = cur_.substr(0, i);
      cur_ = cur_.substr(i);

      const char c = tok->get(0);
      if (c == '\'' || c == '"') {
        if (tok->size() < 2 || (*tok)[tok->size()-1] != c)
          return false;
        *tok = tok->substr(1, tok->size() - 2);
        return true;
      }

      return true;
    }

    void UngetToken(StringPiece tok) {
      CHECK(unget_tok_.empty());
      if (!tok.empty())
        unget_tok_ = tok;
    }

    bool ParseTest() {
      if (has_if_ || !fc_->testdir.empty())
        return false;
      StringPiece tok;
      if (!GetNextToken(&tok) || tok != "-d")
        return false;
      if (!GetNextToken(&tok) || tok.empty())
        return false;
      fc_->testdir = tok;
      return true;
    }

    Cond* ParseFact(StringPiece tok) {
      if (tok == "-not" || tok == "\\!") {
        if (!GetNextToken(&tok) || tok.empty())
          return NULL;
        unique_ptr<Cond> c(ParseFact(tok));
        if (!c.get())
          return NULL;
        return new NotCond(c.release());
      } else if (tok == "\\(") {
        if (!GetNextToken(&tok) || tok.empty())
          return NULL;
        unique_ptr<Cond> c(ParseExpr(tok));
        if (!GetNextToken(&tok) || tok != "\\)") {
          return NULL;
        }
        return c.release();
      } else if (tok == "-name") {
        if (!GetNextToken(&tok) || tok.empty())
          return NULL;
        return new NameCond(tok.as_string());
      } else if (tok == "-type") {
        if (!GetNextToken(&tok) || tok.empty())
          return NULL;
        char type;
        if (tok == "b")
          type = DT_BLK;
        else if (tok == "c")
          type = DT_CHR;
        else if (tok == "d")
          type = DT_DIR;
        else if (tok == "p")
          type = DT_FIFO;
        else if (tok == "l")
          type = DT_LNK;
        else if (tok == "f")
          type = DT_REG;
        else if (tok == "s")
          type = DT_SOCK;
        else
          return NULL;
        return new TypeCond(type);
      } else {
        UngetToken(tok);
        return NULL;
      }
    }

    Cond* ParseTerm(StringPiece tok) {
      unique_ptr<Cond> c(ParseFact(tok));
      if (!c.get())
        return NULL;
      while (true) {
        if (!GetNextToken(&tok))
          return NULL;
        if (tok != "-and" && tok != "-a") {
          UngetToken(tok);
          return c.release();
        }
        if (!GetNextToken(&tok) || tok.empty())
          return NULL;
        unique_ptr<Cond> r(ParseFact(tok));
        if (!r.get()) {
          return NULL;
        }
        c.reset(new AndCond(c.release(), r.release()));
      }
    }

    Cond* ParseExpr(StringPiece tok) {
      unique_ptr<Cond> c(ParseTerm(tok));
      if (!c.get())
        return NULL;
      while (true) {
        if (!GetNextToken(&tok))
          return NULL;
        if (tok != "-or" && tok != "-o") {
          UngetToken(tok);
          return c.release();
        }
        if (!GetNextToken(&tok) || tok.empty())
          return NULL;
        unique_ptr<Cond> r(ParseTerm(tok));
        if (!r.get()) {
          return NULL;
        }
        c.reset(new OrCond(c.release(), r.release()));
      }
    }

    // <expr> ::= <term> {<or> <term>}
    // <term> ::= <fact> {<and> <fact>}
    // <fact> ::= <not> <fact> | '\(' <expr> '\)' | <pred>
    // <not> ::= '-not' | '\!'
    // <and> ::= '-and' | '-a'
    // <or> ::= '-or' | '-o'
    // <pred> ::= <name> | <type> | <maxdepth>
    // <name> ::= '-name' NAME
    // <type> ::= '-type' TYPE
    // <maxdepth> ::= '-maxdepth' MAXDEPTH
    Cond* ParseFindCond(StringPiece tok) {
      return ParseExpr(tok);
    }

    bool ParseFind() {
      StringPiece tok;
      while (true) {
        if (!GetNextToken(&tok))
          return false;
        if (tok.empty() || tok == ";")
          return true;

        if (tok == "-L") {
          fc_->follows_symlinks = true;
        } else if (tok == "-prune") {
          if (!fc_->print_cond || fc_->prune_cond)
            return false;
          if (!GetNextToken(&tok) || tok != "-o")
            return false;
          fc_->prune_cond.reset(fc_->print_cond.release());
        } else if (tok == "-print") {
          if (!GetNextToken(&tok) || !tok.empty())
            return false;
          return true;
        } else if (tok == "-maxdepth") {
          if (!GetNextToken(&tok) || tok.empty())
            return false;
          const string& depth_str = tok.as_string();
          char* endptr;
          long d = strtol(depth_str.c_str(), &endptr, 10);
          if (endptr != depth_str.data() + depth_str.size() ||
              d < 0 || d > INT_MAX) {
            return false;
          }
          fc_->depth = d;
        } else if (tok[0] == '-' || tok == "\\(") {
          if (fc_->print_cond.get())
            return false;
          Cond* c = ParseFindCond(tok);
          if (!c)
            return false;
          fc_->print_cond.reset(c);
        } else {
          fc_->finddirs.push_back(tok);
        }
      }
    }

    bool ParseImpl() {
      while (true) {
        StringPiece tok;
        if (!GetNextToken(&tok))
          return false;

        if (tok.empty())
          return true;

        if (tok == "cd") {
          if (!GetNextToken(&tok) || tok.empty() || !fc_->chdir.empty())
            return false;
          fc_->chdir = tok;
          if (!GetNextToken(&tok) || (tok != ";" && tok != "&&"))
            return false;
        } else if (tok == "if") {
          if (!GetNextToken(&tok) || tok != "[")
            return false;
          if (!ParseTest())
            return false;
          if (!GetNextToken(&tok) || tok != "]")
            return false;
          if (!GetNextToken(&tok) || tok != ";")
            return false;
          if (!GetNextToken(&tok) || tok != "then")
            return false;
          has_if_ = true;
        } else if (tok == "test") {
          if (!fc_->chdir.empty())
            return false;
          if (!ParseTest())
            return false;
          if (!GetNextToken(&tok) || tok != "&&")
            return false;
        } else if (tok == "find") {
          if (!ParseFind())
            return false;
          if (has_if_) {
            if (!GetNextToken(&tok) || tok != "fi")
              return false;
          }
          if (!GetNextToken(&tok) || !tok.empty())
            return false;
          return true;
        }
      }
    }

    StringPiece cmd_;
    StringPiece cur_;
    FindCommand* fc_;
    bool has_if_;
    StringPiece unget_tok_;
  };

  DirentNode* ConstructDirectoryTree(const string& path) {
    DIR* dir = opendir(path.empty() ? "." : path.c_str());
    if (!dir)
      PERROR("opendir failed: %s", path.c_str());

    DirentDirNode* n = new DirentDirNode(path);

    struct dirent* ent;
    while ((ent = readdir(dir)) != NULL) {
      if (!strcmp(ent->d_name, ".") ||
          !strcmp(ent->d_name, "..") ||
          !strcmp(ent->d_name, ".repo") ||
          !strcmp(ent->d_name, ".git") ||
          !strcmp(ent->d_name, "out"))
        continue;

      string npath = path;
      if (!path.empty())
        npath += '/';
      npath += ent->d_name;

      DirentNode* c = NULL;
      if (ent->d_type == DT_DIR) {
        c = ConstructDirectoryTree(npath);
      } else if (ent->d_type == DT_LNK) {
        c = new DirentSymlinkNode(npath);
      } else {
        c = new DirentFileNode(npath, ent->d_type);
      }
      n->Add(ent->d_name, c);
    }
    closedir(dir);

    return n;
  }

  bool ParseFindCommand(StringPiece cmd, FindCommand* fc) {
    FindCommandParser fcp(cmd, fc);
    if (cmd.find("find ") == string::npos)
      return false;

    if (!fcp.Parse())
      return false;

    if (fc->finddirs.empty())
      fc->finddirs.push_back(".");
    return true;
  }

  unique_ptr<DirentNode> root_;
};

}  // namespace

FindEmulator* FindEmulator::Get() {
  return g_instance;
}

void InitFindEmulator() {
  new FindEmulatorImpl();
}