[C++] Introduce FindEmulator to speed up find command
diff --git a/Makefile b/Makefile
index 5b0f4f7..81eaaf3 100644
--- a/Makefile
+++ b/Makefile
@@ -22,6 +22,7 @@
file.cc \
file_cache.cc \
fileutil.cc \
+ find.cc \
flags.cc \
func.cc \
main.cc \
diff --git a/find.cc b/find.cc
new file mode 100644
index 0000000..77c72a6
--- /dev/null
+++ b/find.cc
@@ -0,0 +1,684 @@
+// 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) {
+ }
+ ~FindCommand() {
+ }
+
+ StringPiece chdir;
+ StringPiece testdir;
+ vector<StringPiece> finddirs;
+ bool follows_symlinks;
+ unique_ptr<Cond> print_cond;
+ unique_ptr<Cond> prune_cond;
+};
+
+class DirentNode {
+ public:
+ virtual ~DirentNode() = default;
+
+ virtual const DirentNode* FindDir(StringPiece) const {
+ return NULL;
+ }
+ virtual bool RunFind(const FindCommand& fc,
+ 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,
+ 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,
+ 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);
+
+ 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, 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,
+ string* path, string* out) const {
+ unsigned char type = DT_LNK;
+ if (fc.follows_symlinks) {
+ // TODO
+ LOG("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;
+ }
+
+ for (StringPiece finddir : fc.finddirs) {
+ const DirentNode* base = root_->FindDir(ConcatDir(fc.chdir, finddir));
+ if (!base) {
+ string s = "testdir/../testdir";
+ NormalizePath(&s);
+ LOG("FindEmulator: Find dir (%s) not found: %s",
+ ConcatDir(fc.chdir, finddir).c_str(), cmd.c_str());
+ return false;
+ }
+
+ string path = finddir.as_string();
+ if (!base->RunFind(fc, &path, out)) {
+ LOG("FindEmulator: RunFind failed: %s", cmd.c_str());
+ 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> '\)' | <name> | <type>
+ // <not> ::= '-not' | '\!'
+ // <and> ::= '-and' | '-a'
+ // <or> ::= '-or' | '-o'
+ // <name> ::= '-name' NAME
+ // <type> ::= '-type' TYPE
+ 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") {
+ // TODO
+ return false;
+ } 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();
+}
diff --git a/find.h b/find.h
new file mode 100644
index 0000000..3ec1a4d
--- /dev/null
+++ b/find.h
@@ -0,0 +1,36 @@
+// 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.
+
+#ifndef FIND_H_
+#define FIND_H_
+
+#include <string>
+
+using namespace std;
+
+class FindEmulator {
+ public:
+ virtual ~FindEmulator() = default;
+
+ virtual bool HandleFind(const string& cmd, string* out) = 0;
+
+ static FindEmulator* Get();
+
+ protected:
+ FindEmulator() = default;
+};
+
+void InitFindEmulator();
+
+#endif // FIND_H_
diff --git a/func.cc b/func.cc
index 9ed5ab1..d85f6f7 100644
--- a/func.cc
+++ b/func.cc
@@ -28,6 +28,7 @@
#include "ast.h"
#include "eval.h"
+#include "find.h"
#include "log.h"
#include "parser.h"
#include "stats.h"
@@ -412,6 +413,19 @@
}
}
+//#define TEST_FIND_EMULATOR
+
+#ifdef TEST_FIND_EMULATOR
+static string SortWordsInString(StringPiece s) {
+ vector<string> toks;
+ for (StringPiece tok : WordScanner(s)) {
+ toks.push_back(tok.as_string());
+ }
+ sort(toks.begin(), toks.end());
+ return JoinStrings(toks, " ");
+}
+#endif
+
void ShellFunc(const vector<Value*>& args, Evaluator* ev, string* s) {
shared_ptr<string> cmd = args[0]->Eval(ev);
if (ev->avoid_io()) {
@@ -421,8 +435,21 @@
return;
}
- COLLECT_STATS_WITH_SLOW_REPORT("func shell time", cmd->c_str());
LOG("ShellFunc: %s", cmd->c_str());
+
+#ifdef TEST_FIND_EMULATOR
+ bool need_check = false;
+ string out2;
+ if (FindEmulator::Get()->HandleFind(*cmd, &out2)) {
+ need_check = true;
+ }
+#else
+ if (FindEmulator::Get()->HandleFind(*cmd, s))
+ return;
+#endif
+
+
+ COLLECT_STATS_WITH_SLOW_REPORT("func shell time", cmd->c_str());
string out;
// TODO: Handle $(SHELL).
FILE* fp = popen(cmd->c_str(), "r");
@@ -442,6 +469,18 @@
if (out[i] == '\n')
out[i] = ' ';
}
+
+#ifdef TEST_FIND_EMULATOR
+ if (need_check) {
+ string sorted = SortWordsInString(out);
+ out2 = SortWordsInString(out2);
+ if (sorted != out2) {
+ ERROR("FindEmulator is broken: %s\n%s\nvs\n%s",
+ cmd->c_str(), sorted.c_str(), out2.c_str());
+ }
+ }
+#endif
+
*s += out;
}
diff --git a/main.cc b/main.cc
index 31a0d23..1984b88 100644
--- a/main.cc
+++ b/main.cc
@@ -26,6 +26,7 @@
#include "file.h"
#include "file_cache.h"
#include "fileutil.h"
+#include "find.h"
#include "flags.h"
#include "func.h"
#include "log.h"
@@ -249,6 +250,8 @@
vector<Symbol> targets;
vector<StringPiece> cl_vars;
ParseCommandLine(argc, argv, &targets, &cl_vars);
+ // This depends on command line flags.
+ InitFindEmulator();
int r = Run(targets, cl_vars);
Quit();
return r;
diff --git a/strutil.cc b/strutil.cc
index 7042b3a..442b4bb 100644
--- a/strutil.cc
+++ b/strutil.cc
@@ -253,6 +253,41 @@
return s.substr(0, found);
}
+void NormalizePath(string* o, size_t start_index) {
+ size_t j = start_index;
+ size_t prev_start = start_index;
+ for (size_t i = start_index; i <= o->size(); i++) {
+ char c = (*o)[i];
+ if (c != '/' && c != 0) {
+ (*o)[j] = c;
+ j++;
+ continue;
+ }
+
+ StringPiece prev_dir = StringPiece(o->data() + prev_start, j - prev_start);
+ if (prev_dir == ".") {
+ j--;
+ } else if (prev_dir == "..") {
+ j -= 4;
+ j = o->rfind('/', j);
+ if (j == string::npos) {
+ j = start_index;
+ } else {
+ j++;
+ }
+ } else if (!prev_dir.empty()) {
+ if (c) {
+ (*o)[j] = c;
+ j++;
+ }
+ }
+ prev_start = j;
+ }
+ if (j > 1 && (*o)[j-1] == '/')
+ j--;
+ o->resize(j);
+}
+
void AbsPath(StringPiece s, string* o) {
if (s.get(0) == '/') {
o->clear();
@@ -268,39 +303,7 @@
*o += '/';
}
AppendString(s, o);
-
- size_t j = 1;
- size_t prev_start = 1;
- for (size_t i = 1; i <= o->size(); i++) {
- char c = (*o)[i];
- if (c != '/' && c != 0) {
- (*o)[j] = c;
- j++;
- continue;
- }
-
- StringPiece prev_dir = StringPiece(o->data() + prev_start, j - prev_start);
- if (prev_dir == ".") {
- j--;
- } else if (prev_dir == "..") {
- j -= 4;
- j = o->rfind('/', j);
- if (j == string::npos) {
- j = 1;
- } else {
- j++;
- }
- } else if (!prev_dir.empty()) {
- if (c) {
- (*o)[j] = c;
- j++;
- }
- }
- prev_start = j;
- }
- if (j > 1 && (*o)[j-1] == '/')
- j--;
- o->resize(j);
+ NormalizePath(o, 1);
}
template<typename Cond>
diff --git a/strutil.h b/strutil.h
index 6a51ee7..b0ea67b 100644
--- a/strutil.h
+++ b/strutil.h
@@ -116,6 +116,7 @@
StringPiece Basename(StringPiece s);
StringPiece GetExt(StringPiece s);
StringPiece StripExt(StringPiece s);
+void NormalizePath(string* o, size_t start_index = 0);
void AbsPath(StringPiece s, string* o);
size_t FindOutsideParen(StringPiece s, char c);
diff --git a/testcase/find_command.mk b/testcase/find_command.mk
new file mode 100644
index 0000000..5fe85bc
--- /dev/null
+++ b/testcase/find_command.mk
@@ -0,0 +1,69 @@
+# TODO(go): This test is only for ckati.
+
+define run_find
+@echo $$ '$(strip $(1))'
+@echo $(sort $(shell $(1)))
+endef
+
+test1:
+ mkdir testdir
+ touch testdir/file1
+ touch testdir/file2
+ mkdir testdir/dir1
+ touch testdir/dir1/file1
+ touch testdir/dir1/file2
+ mkdir testdir/dir2
+ touch testdir/dir2/file1
+ touch testdir/dir2/file2
+ ln -s ../dir1/file1 testdir/dir2/link1
+ ln -s ../../testdir/dir1 testdir/dir2/link2
+ ln -s broken testdir/dir2/link3
+
+test2:
+ @echo no options
+ $(call run_find, find testdir)
+ $(call run_find, find .)
+ $(call run_find, find ./)
+ $(call run_find, find .///)
+ $(call run_find, find )
+ $(call run_find, find ./.)
+ $(call run_find, find ././)
+ $(call run_find, find testdir/../testdir)
+ @echo print
+ $(call run_find, find testdir -print)
+ @echo conditiions
+ $(call run_find, find testdir -name foo)
+ $(call run_find, find testdir -name file1)
+ $(call run_find, find testdir -name "file1")
+ $(call run_find, find testdir -name "file1")
+ $(call run_find, find testdir -name "*1")
+ $(call run_find, find testdir -name "*1" -and -name "file*")
+ $(call run_find, find testdir -name "*1" -or -name "file*")
+ $(call run_find, find testdir -name "*1" -or -type f)
+ $(call run_find, find testdir -name "*1" -or -not -type f)
+ $(call run_find, find testdir -name "*1" -or \! -type f)
+ $(call run_find, find testdir -name "*1" -or -type d)
+ $(call run_find, find testdir -name "*1" -or -type l)
+ $(call run_find, find testdir -name "*1" -a -type l -o -name "dir*")
+ $(call run_find, find testdir -name "dir*" -o -name "*1" -a -type l)
+ $(call run_find, find testdir \( -name "dir*" -o -name "*1" \) -a -type f)
+ @echo cd
+ $(call run_find, cd testdir && find)
+ $(call run_find, cd testdir/// && find .)
+ $(call run_find, cd testdir && find ../testdir)
+ @echo test
+ $(call run_find, test -d testdir && find testdir)
+ $(call run_find, if [ -d testdir ] ; then find testdir ; fi)
+ $(call run_find, if [ -d testdir ]; then find testdir; fi)
+ $(call run_find, if [ -d testdir ]; then cd testdir && find .; fi)
+ @echo prune
+ $(call run_find, find testdir -name dir2 -prune -o -name file1)
+ @echo multi
+ $(call run_find, find testdir testdir)
+ @echo symlink
+ $(call run_find, find -L testdir -type f)
+ $(call run_find, find -L testdir -type d)
+ $(call run_find, find -L testdir -type l)
+ $(call run_find, cd testdir; find -L . -type f)
+ $(call run_find, cd testdir; find -L . -type d)
+ $(call run_find, cd testdir; find -L . -type l)