diff options
Diffstat (limited to 'src')
33 files changed, 1052 insertions, 405 deletions
diff --git a/src/browse.py b/src/browse.py index 4b4faa8..64a16f2 100755 --- a/src/browse.py +++ b/src/browse.py @@ -193,6 +193,8 @@ class RequestHandler(httpserver.BaseHTTPRequestHandler): parser = argparse.ArgumentParser(prog='ninja -t browse') parser.add_argument('--port', '-p', default=8000, type=int, help='Port number to use (default %(default)d)') +parser.add_argument('--hostname', '-a', default='localhost', type=str, + help='Hostname to bind to (default %(default)s)') parser.add_argument('--no-browser', action='store_true', help='Do not open a webbrowser on startup.') @@ -205,9 +207,11 @@ parser.add_argument('initial_target', default='all', nargs='?', args = parser.parse_args() port = args.port -httpd = httpserver.HTTPServer(('',port), RequestHandler) +hostname = args.hostname +httpd = httpserver.HTTPServer((hostname,port), RequestHandler) try: - hostname = socket.gethostname() + if hostname == "": + hostname = socket.gethostname() print('Web server running on %s:%d, ctl-C to abort...' % (hostname,port) ) print('Web server pid %d' % os.getpid(), file=sys.stderr ) if not args.no_browser: diff --git a/src/build.cc b/src/build.cc index 64710dd..61ef0e8 100644 --- a/src/build.cc +++ b/src/build.cc @@ -20,6 +20,11 @@ #include <stdlib.h> #include <functional> +#ifdef _WIN32 +#include <fcntl.h> +#include <io.h> +#endif + #if defined(__SVR4) && defined(__sun) #include <sys/termios.h> #endif @@ -155,7 +160,17 @@ void BuildStatus::BuildEdgeFinished(Edge* edge, final_output = StripAnsiEscapeCodes(output); else final_output = output; + +#ifdef _WIN32 + // Fix extra CR being added on Windows, writing out CR CR LF (#773) + _setmode(_fileno(stdout), _O_BINARY); // Begin Windows extra CR fix +#endif + printer_.PrintOnNewLine(final_output); + +#ifdef _WIN32 + _setmode(_fileno(stdout), _O_TEXT); // End Windows extra CR fix +#endif } } @@ -275,27 +290,30 @@ void BuildStatus::PrintStatus(Edge* edge, EdgeStatus status) { Plan::Plan() : command_edges_(0), wanted_edges_(0) {} +void Plan::Reset() { + command_edges_ = 0; + wanted_edges_ = 0; + ready_.clear(); + want_.clear(); +} + bool Plan::AddTarget(Node* node, string* err) { - vector<Node*> stack; - return AddSubTarget(node, &stack, err); + return AddSubTarget(node, NULL, err); } -bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) { +bool Plan::AddSubTarget(Node* node, Node* dependent, string* err) { Edge* edge = node->in_edge(); if (!edge) { // Leaf node. if (node->dirty()) { string referenced; - if (!stack->empty()) - referenced = ", needed by '" + stack->back()->path() + "',"; + if (dependent) + referenced = ", needed by '" + dependent->path() + "',"; *err = "'" + node->path() + "'" + referenced + " missing " "and no known rule to make it"; } return false; } - if (CheckDependencyCycle(node, *stack, err)) - return false; - if (edge->outputs_ready()) return false; // Don't need to do anything. @@ -319,50 +337,15 @@ bool Plan::AddSubTarget(Node* node, vector<Node*>* stack, string* err) { if (!want_ins.second) return true; // We've already processed the inputs. - stack->push_back(node); for (vector<Node*>::iterator i = edge->inputs_.begin(); i != edge->inputs_.end(); ++i) { - if (!AddSubTarget(*i, stack, err) && !err->empty()) + if (!AddSubTarget(*i, node, err) && !err->empty()) return false; } - assert(stack->back() == node); - stack->pop_back(); return true; } -bool Plan::CheckDependencyCycle(Node* node, const vector<Node*>& stack, - string* err) { - vector<Node*>::const_iterator start = stack.begin(); - while (start != stack.end() && (*start)->in_edge() != node->in_edge()) - ++start; - if (start == stack.end()) - return false; - - // Build error string for the cycle. - vector<Node*> cycle(start, stack.end()); - cycle.push_back(node); - - if (cycle.front() != cycle.back()) { - // Consider - // build a b: cat c - // build c: cat a - // stack will contain [b, c], node will be a. To not print b -> c -> a, - // shift by one to get c -> a -> c which makes the cycle clear. - cycle.erase(cycle.begin()); - cycle.push_back(cycle.front()); - assert(cycle.front() == cycle.back()); - } - - *err = "dependency cycle: "; - for (vector<Node*>::const_iterator i = cycle.begin(); i != cycle.end(); ++i) { - if (i != cycle.begin()) - err->append(" -> "); - err->append((*i)->path()); - } - return true; -} - Edge* Plan::FindWork() { if (ready_.empty()) return NULL; @@ -618,9 +601,10 @@ Node* Builder::AddTarget(const string& name, string* err) { } bool Builder::AddTarget(Node* node, string* err) { + if (!scan_.RecomputeDirty(node, err)) + return false; + if (Edge* in_edge = node->in_edge()) { - if (!scan_.RecomputeDirty(in_edge, err)) - return false; if (in_edge->outputs_ready()) return true; // Nothing to do. } @@ -793,9 +777,10 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) { return true; } - // Restat the edge outputs, if necessary. - TimeStamp restat_mtime = 0; - if (edge->GetBindingBool("restat") && !config_.dry_run) { + // Restat the edge outputs + TimeStamp output_mtime = 0; + bool restat = edge->GetBindingBool("restat"); + if (!config_.dry_run) { bool node_cleaned = false; for (vector<Node*>::iterator o = edge->outputs_.begin(); @@ -803,7 +788,9 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) { TimeStamp new_mtime = disk_interface_->Stat((*o)->path(), err); if (new_mtime == -1) return false; - if ((*o)->mtime() == new_mtime) { + if (new_mtime > output_mtime) + output_mtime = new_mtime; + if ((*o)->mtime() == new_mtime && restat) { // The rule command did not change the output. Propagate the clean // state through the build graph. // Note that this also applies to nonexistent outputs (mtime == 0). @@ -814,6 +801,7 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) { } if (node_cleaned) { + TimeStamp restat_mtime = 0; // If any output was cleaned, find the most recent mtime of any // (existing) non-order-only input or the depfile. for (vector<Node*>::iterator i = edge->inputs_.begin(); @@ -837,6 +825,8 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) { // The total number of edges in the plan may have changed as a result // of a restat. status_->PlanHasTotalEdges(plan_.command_edge_count()); + + output_mtime = restat_mtime; } } @@ -849,7 +839,7 @@ bool Builder::FinishCommand(CommandRunner::Result* result, string* err) { if (scan_.build_log()) { if (!scan_.build_log()->RecordCommand(edge, start_time, end_time, - restat_mtime)) { + output_mtime)) { *err = string("Error writing to build log: ") + strerror(errno); return false; } @@ -918,7 +908,7 @@ bool Builder::ExtractDeps(CommandRunner::Result* result, deps_nodes->reserve(deps.ins_.size()); for (vector<StringPiece>::iterator i = deps.ins_.begin(); i != deps.ins_.end(); ++i) { - unsigned int slash_bits; + uint64_t slash_bits; if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits, err)) return false; diff --git a/src/build.h b/src/build.h index 66ce607..43786f1 100644 --- a/src/build.h +++ b/src/build.h @@ -71,10 +71,11 @@ struct Plan { /// Number of edges with commands to run. int command_edge_count() const { return command_edges_; } + /// Reset state. Clears want and ready sets. + void Reset(); + private: - bool AddSubTarget(Node* node, vector<Node*>* stack, string* err); - bool CheckDependencyCycle(Node* node, const vector<Node*>& stack, - string* err); + bool AddSubTarget(Node* node, Node* dependent, string* err); void NodeFinished(Node* node); /// Submits a ready edge as a candidate for execution. diff --git a/src/build_log.cc b/src/build_log.cc index 8a52514..333915a 100644 --- a/src/build_log.cc +++ b/src/build_log.cc @@ -105,7 +105,7 @@ BuildLog::LogEntry::LogEntry(const string& output) BuildLog::LogEntry::LogEntry(const string& output, uint64_t command_hash, int start_time, int end_time, TimeStamp restat_mtime) : output(output), command_hash(command_hash), - start_time(start_time), end_time(end_time), restat_mtime(restat_mtime) + start_time(start_time), end_time(end_time), mtime(restat_mtime) {} BuildLog::BuildLog() @@ -145,7 +145,7 @@ bool BuildLog::OpenForWrite(const string& path, const BuildLogUser& user, } bool BuildLog::RecordCommand(Edge* edge, int start_time, int end_time, - TimeStamp restat_mtime) { + TimeStamp mtime) { string command = edge->EvaluateCommand(true); uint64_t command_hash = LogEntry::HashCommand(command); for (vector<Node*>::iterator out = edge->outputs_.begin(); @@ -162,7 +162,7 @@ bool BuildLog::RecordCommand(Edge* edge, int start_time, int end_time, log_entry->command_hash = command_hash; log_entry->start_time = start_time; log_entry->end_time = end_time; - log_entry->restat_mtime = restat_mtime; + log_entry->mtime = mtime; if (log_file_) { if (!WriteEntry(log_file_, *log_entry)) @@ -314,7 +314,7 @@ bool BuildLog::Load(const string& path, string* err) { entry->start_time = start_time; entry->end_time = end_time; - entry->restat_mtime = restat_mtime; + entry->mtime = restat_mtime; if (log_version >= 5) { char c = *end; *end = '\0'; entry->command_hash = (uint64_t)strtoull(start, NULL, 16); @@ -354,7 +354,7 @@ BuildLog::LogEntry* BuildLog::LookupByOutput(const string& path) { bool BuildLog::WriteEntry(FILE* f, const LogEntry& entry) { return fprintf(f, "%d\t%d\t%d\t%s\t%" PRIx64 "\n", - entry.start_time, entry.end_time, entry.restat_mtime, + entry.start_time, entry.end_time, entry.mtime, entry.output.c_str(), entry.command_hash) > 0; } diff --git a/src/build_log.h b/src/build_log.h index 785961e..5268fab 100644 --- a/src/build_log.h +++ b/src/build_log.h @@ -45,7 +45,7 @@ struct BuildLog { bool OpenForWrite(const string& path, const BuildLogUser& user, string* err); bool RecordCommand(Edge* edge, int start_time, int end_time, - TimeStamp restat_mtime = 0); + TimeStamp mtime = 0); void Close(); /// Load the on-disk log. @@ -56,7 +56,7 @@ struct BuildLog { uint64_t command_hash; int start_time; int end_time; - TimeStamp restat_mtime; + TimeStamp mtime; static uint64_t HashCommand(StringPiece command); @@ -64,7 +64,7 @@ struct BuildLog { bool operator==(const LogEntry& o) { return output == o.output && command_hash == o.command_hash && start_time == o.start_time && end_time == o.end_time && - restat_mtime == o.restat_mtime; + mtime == o.mtime; } explicit LogEntry(const string& output); diff --git a/src/build_log_perftest.cc b/src/build_log_perftest.cc index 185c512..b4efb1d 100644 --- a/src/build_log_perftest.cc +++ b/src/build_log_perftest.cc @@ -92,7 +92,7 @@ bool WriteTestData(string* err) { log.RecordCommand(state.edges_[i], /*start_time=*/100 * i, /*end_time=*/100 * i + 1, - /*restat_mtime=*/0); + /*mtime=*/0); } return true; diff --git a/src/build_log_test.cc b/src/build_log_test.cc index f4c9044..ad30380 100644 --- a/src/build_log_test.cc +++ b/src/build_log_test.cc @@ -181,7 +181,7 @@ TEST_F(BuildLogTest, SpacesInOutputV4) { ASSERT_TRUE(e); ASSERT_EQ(123, e->start_time); ASSERT_EQ(456, e->end_time); - ASSERT_EQ(456, e->restat_mtime); + ASSERT_EQ(456, e->mtime); ASSERT_NO_FATAL_FAILURE(AssertHash("command", e->command_hash)); } @@ -205,14 +205,14 @@ TEST_F(BuildLogTest, DuplicateVersionHeader) { ASSERT_TRUE(e); ASSERT_EQ(123, e->start_time); ASSERT_EQ(456, e->end_time); - ASSERT_EQ(456, e->restat_mtime); + ASSERT_EQ(456, e->mtime); ASSERT_NO_FATAL_FAILURE(AssertHash("command", e->command_hash)); e = log.LookupByOutput("out2"); ASSERT_TRUE(e); ASSERT_EQ(456, e->start_time); ASSERT_EQ(789, e->end_time); - ASSERT_EQ(789, e->restat_mtime); + ASSERT_EQ(789, e->mtime); ASSERT_NO_FATAL_FAILURE(AssertHash("command2", e->command_hash)); } @@ -240,7 +240,7 @@ TEST_F(BuildLogTest, VeryLongInputLine) { ASSERT_TRUE(e); ASSERT_EQ(456, e->start_time); ASSERT_EQ(789, e->end_time); - ASSERT_EQ(789, e->restat_mtime); + ASSERT_EQ(789, e->mtime); ASSERT_NO_FATAL_FAILURE(AssertHash("command2", e->command_hash)); } diff --git a/src/build_test.cc b/src/build_test.cc index 640e1b0..a0f898f 100644 --- a/src/build_test.cc +++ b/src/build_test.cc @@ -185,59 +185,6 @@ TEST_F(PlanTest, DoubleDependent) { ASSERT_FALSE(edge); // done } -TEST_F(PlanTest, DependencyCycle) { - ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -"build out: cat mid\n" -"build mid: cat in\n" -"build in: cat pre\n" -"build pre: cat out\n")); - GetNode("out")->MarkDirty(); - GetNode("mid")->MarkDirty(); - GetNode("in")->MarkDirty(); - GetNode("pre")->MarkDirty(); - - string err; - EXPECT_FALSE(plan_.AddTarget(GetNode("out"), &err)); - ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err); -} - -TEST_F(PlanTest, CycleInEdgesButNotInNodes1) { - string err; - ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -"build a b: cat a\n")); - EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err)); - ASSERT_EQ("dependency cycle: a -> a", err); -} - -TEST_F(PlanTest, CycleInEdgesButNotInNodes2) { - string err; - ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -"build b a: cat a\n")); - EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err)); - ASSERT_EQ("dependency cycle: a -> a", err); -} - -TEST_F(PlanTest, CycleInEdgesButNotInNodes3) { - string err; - ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -"build a b: cat c\n" -"build c: cat a\n")); - EXPECT_FALSE(plan_.AddTarget(GetNode("b"), &err)); - ASSERT_EQ("dependency cycle: c -> a -> c", err); -} - -TEST_F(PlanTest, CycleInEdgesButNotInNodes4) { - string err; - ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -"build d: cat c\n" -"build c: cat b\n" -"build b: cat a\n" -"build a e: cat d\n" -"build f: cat e\n")); - EXPECT_FALSE(plan_.AddTarget(GetNode("f"), &err)); - ASSERT_EQ("dependency cycle: d -> c -> b -> a -> d", err); -} - void PlanTest::TestPoolWithDepthOne(const char* test_case) { ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, test_case)); GetNode("out1")->MarkDirty(); @@ -608,7 +555,8 @@ bool FakeCommandRunner::StartCommand(Edge* edge) { edge->rule().name() == "cat_rsp_out" || edge->rule().name() == "cc" || edge->rule().name() == "touch" || - edge->rule().name() == "touch-interrupt") { + edge->rule().name() == "touch-interrupt" || + edge->rule().name() == "touch-fail-tick2") { for (vector<Node*>::iterator out = edge->outputs_.begin(); out != edge->outputs_.end(); ++out) { fs_->Create((*out)->path(), ""); @@ -649,7 +597,8 @@ bool FakeCommandRunner::WaitForCommand(Result* result) { return true; } - if (edge->rule().name() == "fail") + if (edge->rule().name() == "fail" || + (edge->rule().name() == "touch-fail-tick2" && fs_->now_ == 2)) result->status = ExitFailure; else result->status = ExitSuccess; @@ -1258,6 +1207,82 @@ TEST_F(BuildWithLogTest, NotInLogButOnDisk) { EXPECT_TRUE(builder_.AlreadyUpToDate()); } +TEST_F(BuildWithLogTest, RebuildAfterFailure) { + ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, +"rule touch-fail-tick2\n" +" command = touch-fail-tick2\n" +"build out1: touch-fail-tick2 in\n")); + + string err; + + fs_.Create("in", ""); + + // Run once successfully to get out1 in the log + EXPECT_TRUE(builder_.AddTarget("out1", &err)); + EXPECT_TRUE(builder_.Build(&err)); + EXPECT_EQ("", err); + EXPECT_EQ(1u, command_runner_.commands_ran_.size()); + + command_runner_.commands_ran_.clear(); + state_.Reset(); + builder_.Cleanup(); + builder_.plan_.Reset(); + + fs_.Tick(); + fs_.Create("in", ""); + + // Run again with a failure that updates the output file timestamp + EXPECT_TRUE(builder_.AddTarget("out1", &err)); + EXPECT_FALSE(builder_.Build(&err)); + EXPECT_EQ("subcommand failed", err); + EXPECT_EQ(1u, command_runner_.commands_ran_.size()); + + command_runner_.commands_ran_.clear(); + state_.Reset(); + builder_.Cleanup(); + builder_.plan_.Reset(); + + fs_.Tick(); + + // Run again, should rerun even though the output file is up to date on disk + EXPECT_TRUE(builder_.AddTarget("out1", &err)); + EXPECT_FALSE(builder_.AlreadyUpToDate()); + EXPECT_TRUE(builder_.Build(&err)); + EXPECT_EQ(1u, command_runner_.commands_ran_.size()); + EXPECT_EQ("", err); +} + +TEST_F(BuildWithLogTest, RebuildWithNoInputs) { + ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, +"rule touch\n" +" command = touch\n" +"build out1: touch\n" +"build out2: touch in\n")); + + string err; + + fs_.Create("in", ""); + + EXPECT_TRUE(builder_.AddTarget("out1", &err)); + EXPECT_TRUE(builder_.AddTarget("out2", &err)); + EXPECT_TRUE(builder_.Build(&err)); + EXPECT_EQ("", err); + EXPECT_EQ(2u, command_runner_.commands_ran_.size()); + + command_runner_.commands_ran_.clear(); + state_.Reset(); + + fs_.Tick(); + + fs_.Create("in", ""); + + EXPECT_TRUE(builder_.AddTarget("out1", &err)); + EXPECT_TRUE(builder_.AddTarget("out2", &err)); + EXPECT_TRUE(builder_.Build(&err)); + EXPECT_EQ("", err); + EXPECT_EQ(1u, command_runner_.commands_ran_.size()); +} + TEST_F(BuildWithLogTest, RestatTest) { ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, "rule true\n" @@ -1438,7 +1463,7 @@ TEST_F(BuildWithLogTest, RestatMissingInput) { // the right mtime BuildLog::LogEntry* log_entry = build_log_.LookupByOutput("out1"); ASSERT_TRUE(NULL != log_entry); - ASSERT_EQ(restat_mtime, log_entry->restat_mtime); + ASSERT_EQ(restat_mtime, log_entry->mtime); // Now remove a file, referenced from depfile, so that target becomes // dirty, but the output does not change @@ -1455,7 +1480,7 @@ TEST_F(BuildWithLogTest, RestatMissingInput) { // Check that the logfile entry remains correctly set log_entry = build_log_.LookupByOutput("out1"); ASSERT_TRUE(NULL != log_entry); - ASSERT_EQ(restat_mtime, log_entry->restat_mtime); + ASSERT_EQ(restat_mtime, log_entry->mtime); } struct BuildDryRun : public BuildWithLogTest { @@ -1669,8 +1694,8 @@ TEST_F(BuildTest, InterruptCleanup) { TEST_F(BuildTest, StatFailureAbortsBuild) { const string kTooLongToStat(400, 'i'); ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, -("build " + kTooLongToStat + ": cat " + kTooLongToStat + "\n").c_str())); - // Also cyclic, for good measure. +("build " + kTooLongToStat + ": cat in\n").c_str())); + fs_.Create("in", ""); // This simulates a stat failure: fs_.files_[kTooLongToStat].mtime = -1; diff --git a/src/canon_perftest.cc b/src/canon_perftest.cc index 389ac24..03f4a2f 100644 --- a/src/canon_perftest.cc +++ b/src/canon_perftest.cc @@ -33,7 +33,7 @@ int main() { for (int j = 0; j < 5; ++j) { const int kNumRepetitions = 2000000; int64_t start = GetTimeMillis(); - unsigned int slash_bits; + uint64_t slash_bits; for (int i = 0; i < kNumRepetitions; ++i) { CanonicalizePath(buf, &len, &slash_bits, &err); } diff --git a/src/clparser.cc b/src/clparser.cc index f73a8c1..7994c06 100644 --- a/src/clparser.cc +++ b/src/clparser.cc @@ -18,8 +18,12 @@ #include <assert.h> #include <string.h> +#include "metrics.h" +#include "string_piece_util.h" + #ifdef _WIN32 #include "includes_normalize.h" +#include "string_piece.h" #else #include "util.h" #endif @@ -53,7 +57,7 @@ string CLParser::FilterShowIncludes(const string& line, // static bool CLParser::IsSystemInclude(string path) { - transform(path.begin(), path.end(), path.begin(), ::tolower); + transform(path.begin(), path.end(), path.begin(), ToLowerASCII); // TODO: this is a heuristic, perhaps there's a better way? return (path.find("program files") != string::npos || path.find("microsoft visual studio") != string::npos); @@ -61,7 +65,7 @@ bool CLParser::IsSystemInclude(string path) { // static bool CLParser::FilterInputFilename(string line) { - transform(line.begin(), line.end(), line.begin(), ::tolower); + transform(line.begin(), line.end(), line.begin(), ToLowerASCII); // TODO: other extensions, like .asm? return EndsWith(line, ".c") || EndsWith(line, ".cc") || @@ -72,9 +76,15 @@ bool CLParser::FilterInputFilename(string line) { // static bool CLParser::Parse(const string& output, const string& deps_prefix, string* filtered_output, string* err) { + METRIC_RECORD("CLParser::Parse"); + // Loop over all lines in the output to process them. assert(&output != filtered_output); size_t start = 0; +#ifdef _WIN32 + IncludesNormalize normalizer("."); +#endif + while (start < output.size()) { size_t end = output.find_first_of("\r\n", start); if (end == string::npos) @@ -85,12 +95,12 @@ bool CLParser::Parse(const string& output, const string& deps_prefix, if (!include.empty()) { string normalized; #ifdef _WIN32 - if (!IncludesNormalize::Normalize(include, NULL, &normalized, err)) + if (!normalizer.Normalize(include, &normalized, err)) return false; #else // TODO: should this make the path relative to cwd? normalized = include; - unsigned int slash_bits; + uint64_t slash_bits; if (!CanonicalizePath(&normalized, &slash_bits, err)) return false; #endif diff --git a/src/clparser_perftest.cc b/src/clparser_perftest.cc new file mode 100644 index 0000000..7ac5230 --- /dev/null +++ b/src/clparser_perftest.cc @@ -0,0 +1,157 @@ +// Copyright 2017 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. + +#include <stdio.h> +#include <stdlib.h> + +#include "clparser.h" +#include "metrics.h" + +int main(int argc, char* argv[]) { + // Output of /showIncludes from #include <iostream> + string perf_testdata = + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\iostream\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\istream\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ostream\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ios\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocnum\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\climits\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\yvals.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xkeycheck.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\crtdefs.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\sal.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ConcurrencySal.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vadefs.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\use_ansi.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\limits.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cmath\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\math.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xtgmath.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xtr1common\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstdlib\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\stdlib.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_malloc.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_search.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\stddef.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wstdlib.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstdio\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\stdio.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wstdio.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_stdio_config.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\streambuf\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xiosbase\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocale\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstring\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\string.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_memory.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_memcpy_s.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\errno.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_string.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wstring.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\stdexcept\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\exception\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\type_traits\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xstddef\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstddef\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\initializer_list\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\malloc.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_exception.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\eh.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_terminate.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xstring\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xmemory0\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cstdint\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\stdint.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\limits\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ymath.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cfloat\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\float.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cwchar\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\wchar.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wconio.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wctype.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wdirect.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wio.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_share.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wprocess.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\corecrt_wtime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\sys/stat.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\sys/types.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\new\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_new.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xutility\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\utility\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\iosfwd\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\crtdbg.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_new_debug.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xatomic0.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\intrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\setjmp.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\immintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\wmmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\nmmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\smmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\tmmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\pmmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\emmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xmmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\mmintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\ammintrin.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\mm3dnow.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\typeinfo\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime_typeinfo.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\vcruntime.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocinfo\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xlocinfo.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\ctype.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\locale.h\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\xfacet\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\system_error\r\n" + "Note: including file: C:\\Program Files (x86)\\Microsoft Visual Studio 14.0\\VC\\INCLUDE\\cerrno\r\n" + "Note: including file: C:\\Program Files (x86)\\Windows Kits\\10\\include\\10.0.10240.0\\ucrt\\share.h\r\n"; + + for (int limit = 1 << 10; limit < (1<<20); limit *= 2) { + int64_t start = GetTimeMillis(); + for (int rep = 0; rep < limit; ++rep) { + string output; + string err; + + CLParser parser; + if (!parser.Parse(perf_testdata, "", &output, &err)) { + printf("%s\n", err.c_str()); + return 1; + } + } + int64_t end = GetTimeMillis(); + + if (end - start > 2000) { + int delta_ms = (int)(end - start); + printf("Parse %d times in %dms avg %.1fus\n", + limit, delta_ms, float(delta_ms * 1000) / limit); + break; + } + } + + return 0; +} diff --git a/src/disk_interface.cc b/src/disk_interface.cc index 451a9b4..28530b1 100644 --- a/src/disk_interface.cc +++ b/src/disk_interface.cc @@ -28,6 +28,7 @@ #include <direct.h> // _mkdir #endif +#include "metrics.h" #include "util.h" namespace { @@ -80,20 +81,15 @@ TimeStamp StatSingleFile(const string& path, string* err) { return TimeStampFromFileTime(attrs.ftLastWriteTime); } -#ifdef _MSC_VER -#pragma warning(push) -#pragma warning(disable: 4996) // GetVersionExA is deprecated post SDK 8.1. -#endif bool IsWindows7OrLater() { - OSVERSIONINFO version_info = { sizeof(version_info) }; - if (!GetVersionEx(&version_info)) - Fatal("GetVersionEx: %s", GetLastErrorString().c_str()); - return version_info.dwMajorVersion > 6 || - (version_info.dwMajorVersion == 6 && version_info.dwMinorVersion >= 1); + OSVERSIONINFOEX version_info = + { sizeof(OSVERSIONINFOEX), 6, 1, 0, 0, {0}, 0, 0, 0, 0, 0}; + DWORDLONG comparison = 0; + VER_SET_CONDITION(comparison, VER_MAJORVERSION, VER_GREATER_EQUAL); + VER_SET_CONDITION(comparison, VER_MINORVERSION, VER_GREATER_EQUAL); + return VerifyVersionInfo( + &version_info, VER_MAJORVERSION | VER_MINORVERSION, comparison); } -#ifdef _MSC_VER -#pragma warning(pop) -#endif bool StatAllFilesInDir(const string& dir, map<string, TimeStamp>* stamps, string* err) { @@ -153,6 +149,7 @@ bool DiskInterface::MakeDirs(const string& path) { // RealDiskInterface ----------------------------------------------------------- TimeStamp RealDiskInterface::Stat(const string& path, string* err) const { + METRIC_RECORD("node stat"); #ifdef _WIN32 // MSDN: "Naming Files, Paths, and Namespaces" // http://msdn.microsoft.com/en-us/library/windows/desktop/aa365247(v=vs.85).aspx @@ -190,6 +187,11 @@ TimeStamp RealDiskInterface::Stat(const string& path, string* err) const { *err = "stat(" + path + "): " + strerror(errno); return -1; } + // Some users (Flatpak) set mtime to 0, this should be harmless + // and avoids conflicting with our return value of 0 meaning + // that it doesn't exist. + if (st.st_mtime == 0) + return 1; return st.st_mtime; #endif } diff --git a/src/disk_interface_test.cc b/src/disk_interface_test.cc index 7187bdf..d7fb8f8 100644 --- a/src/disk_interface_test.cc +++ b/src/disk_interface_test.cc @@ -245,7 +245,7 @@ TEST_F(StatTest, Simple) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_EQ(2u, stats_.size()); ASSERT_EQ("out", stats_[0]); ASSERT_EQ("in", stats_[1]); @@ -261,7 +261,7 @@ TEST_F(StatTest, TwoStep) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_EQ(3u, stats_.size()); ASSERT_EQ("out", stats_[0]); ASSERT_TRUE(GetNode("out")->dirty()); @@ -281,7 +281,7 @@ TEST_F(StatTest, Tree) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_EQ(1u + 6u, stats_.size()); ASSERT_EQ("mid1", stats_[1]); ASSERT_TRUE(GetNode("mid1")->dirty()); @@ -302,7 +302,7 @@ TEST_F(StatTest, Middle) { EXPECT_TRUE(out->Stat(this, &err)); EXPECT_EQ("", err); ASSERT_EQ(1u, stats_.size()); - scan_.RecomputeDirty(out->in_edge(), NULL); + scan_.RecomputeDirty(out, NULL); ASSERT_FALSE(GetNode("in")->dirty()); ASSERT_TRUE(GetNode("mid")->dirty()); ASSERT_TRUE(GetNode("out")->dirty()); diff --git a/src/graph.cc b/src/graph.cc index f1d9ca2..7dd9491 100644 --- a/src/graph.cc +++ b/src/graph.cc @@ -28,24 +28,47 @@ #include "util.h" bool Node::Stat(DiskInterface* disk_interface, string* err) { - METRIC_RECORD("node stat"); return (mtime_ = disk_interface->Stat(path_, err)) != -1; } -bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { +bool DependencyScan::RecomputeDirty(Node* node, string* err) { + vector<Node*> stack; + return RecomputeDirty(node, &stack, err); +} + +bool DependencyScan::RecomputeDirty(Node* node, vector<Node*>* stack, + string* err) { + Edge* edge = node->in_edge(); + if (!edge) { + // If we already visited this leaf node then we are done. + if (node->status_known()) + return true; + // This node has no in-edge; it is dirty if it is missing. + if (!node->StatIfNecessary(disk_interface_, err)) + return false; + if (!node->exists()) + EXPLAIN("%s has no in-edge and is missing", node->path().c_str()); + node->set_dirty(!node->exists()); + return true; + } + + // If we already finished this edge then we are done. + if (edge->mark_ == Edge::VisitDone) + return true; + + // If we encountered this edge earlier in the call stack we have a cycle. + if (!VerifyDAG(node, stack, err)) + return false; + + // Mark the edge temporarily while in the call stack. + edge->mark_ = Edge::VisitInStack; + stack->push_back(node); + bool dirty = false; edge->outputs_ready_ = true; edge->deps_missing_ = false; // Load output mtimes so we can compare them to the most recent input below. - // RecomputeDirty() recursively walks the graph following the input nodes - // of |edge| and the in_edges of these nodes. It uses the stat state of each - // node to mark nodes as visited and doesn't traverse across nodes that have - // been visited already. To make sure that every edge is visited only once - // (important because an edge's deps are loaded every time it's visited), mark - // all outputs of |edge| visited as a first step. This ensures that edges - // with multiple inputs and outputs are visited only once, even in cyclic - // graphs. for (vector<Node*>::iterator o = edge->outputs_.begin(); o != edge->outputs_.end(); ++o) { if (!(*o)->StatIfNecessary(disk_interface_, err)) @@ -64,19 +87,9 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { Node* most_recent_input = NULL; for (vector<Node*>::iterator i = edge->inputs_.begin(); i != edge->inputs_.end(); ++i) { - if (!(*i)->status_known()) { - if (!(*i)->StatIfNecessary(disk_interface_, err)) - return false; - if (Edge* in_edge = (*i)->in_edge()) { - if (!RecomputeDirty(in_edge, err)) - return false; - } else { - // This input has no in-edge; it is dirty if it is missing. - if (!(*i)->exists()) - EXPLAIN("%s has no in-edge and is missing", (*i)->path().c_str()); - (*i)->set_dirty(!(*i)->exists()); - } - } + // Visit this input. + if (!RecomputeDirty(*i, stack, err)) + return false; // If an input is not ready, neither are our outputs. if (Edge* in_edge = (*i)->in_edge()) { @@ -119,9 +132,47 @@ bool DependencyScan::RecomputeDirty(Edge* edge, string* err) { if (dirty && !(edge->is_phony() && edge->inputs_.empty())) edge->outputs_ready_ = false; + // Mark the edge as finished during this walk now that it will no longer + // be in the call stack. + edge->mark_ = Edge::VisitDone; + assert(stack->back() == node); + stack->pop_back(); + return true; } +bool DependencyScan::VerifyDAG(Node* node, vector<Node*>* stack, string* err) { + Edge* edge = node->in_edge(); + assert(edge != NULL); + + // If we have no temporary mark on the edge then we do not yet have a cycle. + if (edge->mark_ != Edge::VisitInStack) + return true; + + // We have this edge earlier in the call stack. Find it. + vector<Node*>::iterator start = stack->begin(); + while (start != stack->end() && (*start)->in_edge() != edge) + ++start; + assert(start != stack->end()); + + // Make the cycle clear by reporting its start as the node at its end + // instead of some other output of the starting edge. For example, + // running 'ninja b' on + // build a b: cat c + // build c: cat a + // should report a -> c -> a instead of b -> c -> a. + *start = node; + + // Construct the error message rejecting the cycle. + *err = "dependency cycle: "; + for (vector<Node*>::const_iterator i = start; i != stack->end(); ++i) { + err->append((*i)->path()); + err->append(" -> "); + } + err->append((*start)->path()); + return false; +} + bool DependencyScan::RecomputeOutputsDirty(Edge* edge, Node* most_recent_input, bool* outputs_dirty, string* err) { string command = edge->EvaluateCommand(/*incl_rsp_file=*/true); @@ -169,7 +220,7 @@ bool DependencyScan::RecomputeOutputDirty(Edge* edge, bool used_restat = false; if (edge->GetBindingBool("restat") && build_log() && (entry = build_log()->LookupByOutput(output->path()))) { - output_mtime = entry->restat_mtime; + output_mtime = entry->mtime; used_restat = true; } @@ -183,17 +234,29 @@ bool DependencyScan::RecomputeOutputDirty(Edge* edge, } } - // May also be dirty due to the command changing since the last build. - // But if this is a generator rule, the command changing does not make us - // dirty. - if (!edge->GetBindingBool("generator") && build_log()) { + if (build_log()) { + bool generator = edge->GetBindingBool("generator"); if (entry || (entry = build_log()->LookupByOutput(output->path()))) { - if (BuildLog::LogEntry::HashCommand(command) != entry->command_hash) { + if (!generator && + BuildLog::LogEntry::HashCommand(command) != entry->command_hash) { + // May also be dirty due to the command changing since the last build. + // But if this is a generator rule, the command changing does not make us + // dirty. EXPLAIN("command line changed for %s", output->path().c_str()); return true; } + if (most_recent_input && entry->mtime < most_recent_input->mtime()) { + // May also be dirty due to the mtime in the log being older than the + // mtime of the most recent input. This can occur even when the mtime + // on disk is newer if a previous run wrote to the output file but + // exited with an error or was interrupted. + EXPLAIN("recorded mtime of %s older than most recent input %s (%d vs %d)", + output->path().c_str(), most_recent_input->path().c_str(), + entry->mtime, most_recent_input->mtime()); + return true; + } } - if (!entry) { + if (!entry && !generator) { EXPLAIN("command line not found in log for %s", output->path().c_str()); return true; } @@ -348,10 +411,10 @@ bool Edge::use_console() const { } // static -string Node::PathDecanonicalized(const string& path, unsigned int slash_bits) { +string Node::PathDecanonicalized(const string& path, uint64_t slash_bits) { string result = path; #ifdef _WIN32 - unsigned int mask = 1; + uint64_t mask = 1; for (char* c = &result[0]; (c = strchr(c, '/')) != NULL;) { if (slash_bits & mask) *c = '\\'; @@ -420,10 +483,12 @@ bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path, return false; } - unsigned int unused; + uint64_t unused; if (!CanonicalizePath(const_cast<char*>(depfile.out_.str_), - &depfile.out_.len_, &unused, err)) + &depfile.out_.len_, &unused, err)) { + *err = path + ": " + *err; return false; + } // Check that this depfile matches the edge's output, if not return false to // mark the edge as dirty. @@ -442,7 +507,7 @@ bool ImplicitDepLoader::LoadDepFile(Edge* edge, const string& path, // Add all its in-edges. for (vector<StringPiece>::iterator i = depfile.ins_.begin(); i != depfile.ins_.end(); ++i, ++implicit_dep) { - unsigned int slash_bits; + uint64_t slash_bits; if (!CanonicalizePath(const_cast<char*>(i->str_), &i->len_, &slash_bits, err)) return false; diff --git a/src/graph.h b/src/graph.h index add8d3d..586c588 100644 --- a/src/graph.h +++ b/src/graph.h @@ -21,6 +21,7 @@ using namespace std; #include "eval_env.h" #include "timestamp.h" +#include "util.h" struct BuildLog; struct DiskInterface; @@ -33,7 +34,7 @@ struct State; /// Information about a node in the dependency graph: the file, whether /// it's dirty, mtime, etc. struct Node { - Node(const string& path, unsigned int slash_bits) + Node(const string& path, uint64_t slash_bits) : path_(path), slash_bits_(slash_bits), mtime_(-1), @@ -76,8 +77,8 @@ struct Node { return PathDecanonicalized(path_, slash_bits_); } static string PathDecanonicalized(const string& path, - unsigned int slash_bits); - unsigned int slash_bits() const { return slash_bits_; } + uint64_t slash_bits); + uint64_t slash_bits() const { return slash_bits_; } TimeStamp mtime() const { return mtime_; } @@ -101,7 +102,7 @@ private: /// Set bits starting from lowest for backslashes that were normalized to /// forward slashes by CanonicalizePath. See |PathDecanonicalized|. - unsigned int slash_bits_; + uint64_t slash_bits_; /// Possible values of mtime_: /// -1: file hasn't been examined @@ -127,7 +128,13 @@ private: /// An edge in the dependency graph; links between Nodes using Rules. struct Edge { - Edge() : rule_(NULL), pool_(NULL), env_(NULL), + enum VisitMark { + VisitNone, + VisitInStack, + VisitDone + }; + + Edge() : rule_(NULL), pool_(NULL), env_(NULL), mark_(VisitNone), outputs_ready_(false), deps_missing_(false), implicit_deps_(0), order_only_deps_(0), implicit_outs_(0) {} @@ -155,6 +162,7 @@ struct Edge { vector<Node*> inputs_; vector<Node*> outputs_; BindingEnv* env_; + VisitMark mark_; bool outputs_ready_; bool deps_missing_; @@ -245,11 +253,12 @@ struct DependencyScan { disk_interface_(disk_interface), dep_loader_(state, deps_log, disk_interface) {} + /// Update the |dirty_| state of the given node by inspecting its input edge. /// Examine inputs, outputs, and command lines to judge whether an edge /// needs to be re-run, and update outputs_ready_ and each outputs' |dirty_| /// state accordingly. /// Returns false on failure. - bool RecomputeDirty(Edge* edge, string* err); + bool RecomputeDirty(Node* node, string* err); /// Recompute whether any output of the edge is dirty, if so sets |*dirty|. /// Returns false on failure. @@ -268,6 +277,9 @@ struct DependencyScan { } private: + bool RecomputeDirty(Node* node, vector<Node*>* stack, string* err); + bool VerifyDAG(Node* node, vector<Node*>* stack, string* err); + /// Recompute whether a given single output should be marked dirty. /// Returns true if so. bool RecomputeOutputDirty(Edge* edge, Node* most_recent_input, diff --git a/src/graph_test.cc b/src/graph_test.cc index be08b19..d4d2824 100644 --- a/src/graph_test.cc +++ b/src/graph_test.cc @@ -30,9 +30,8 @@ TEST_F(GraphTest, MissingImplicit) { fs_.Create("in", ""); fs_.Create("out", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); // A missing implicit dep *should* make the output dirty. @@ -49,9 +48,8 @@ TEST_F(GraphTest, ModifiedImplicit) { fs_.Tick(); fs_.Create("implicit", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); // A modified implicit dep should make the output dirty. @@ -70,9 +68,8 @@ TEST_F(GraphTest, FunkyMakefilePath) { fs_.Tick(); fs_.Create("implicit.h", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); // implicit.h has changed, though our depfile refers to it with a @@ -94,9 +91,8 @@ TEST_F(GraphTest, ExplicitImplicit) { fs_.Tick(); fs_.Create("data", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); // We have both an implicit and an explicit dep on implicit.h. @@ -123,9 +119,8 @@ TEST_F(GraphTest, ImplicitOutputMissing) { fs_.Create("in", ""); fs_.Create("out", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out")->dirty()); @@ -140,9 +135,8 @@ TEST_F(GraphTest, ImplicitOutputOutOfDate) { fs_.Create("in", ""); fs_.Create("out", ""); - Edge* edge = GetNode("out")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out")->dirty()); @@ -165,9 +159,8 @@ TEST_F(GraphTest, ImplicitOutputOnlyMissing) { "build | out.imp: cat in\n")); fs_.Create("in", ""); - Edge* edge = GetNode("out.imp")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out.imp")->dirty()); @@ -180,9 +173,8 @@ TEST_F(GraphTest, ImplicitOutputOnlyOutOfDate) { fs_.Tick(); fs_.Create("in", ""); - Edge* edge = GetNode("out.imp")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.imp"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out.imp")->dirty()); @@ -198,9 +190,8 @@ TEST_F(GraphTest, PathWithCurrentDirectory) { fs_.Create("out.o.d", "out.o: foo.cc\n"); fs_.Create("out.o", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); @@ -247,9 +238,8 @@ TEST_F(GraphTest, DepfileWithCanonicalizablePath) { fs_.Create("out.o.d", "out.o: bar/../foo.cc\n"); fs_.Create("out.o", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); @@ -268,15 +258,14 @@ TEST_F(GraphTest, DepfileRemoved) { fs_.Create("out.o.d", "out.o: foo.h\n"); fs_.Create("out.o", ""); - Edge* edge = GetNode("out.o")->in_edge(); string err; - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_FALSE(GetNode("out.o")->dirty()); state_.Reset(); fs_.RemoveFile("out.o.d"); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("out.o"), &err)); ASSERT_EQ("", err); EXPECT_TRUE(GetNode("out.o")->dirty()); } @@ -323,8 +312,7 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) { "build n2: phony n1\n" ); string err; - Edge* edge = GetNode("n2")->in_edge(); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); + EXPECT_TRUE(scan_.RecomputeDirty(GetNode("n2"), &err)); ASSERT_EQ("", err); Plan plan_; @@ -335,6 +323,55 @@ TEST_F(GraphTest, NestedPhonyPrintsDone) { ASSERT_FALSE(plan_.more_to_do()); } +TEST_F(GraphTest, DependencyCycle) { + AssertParse(&state_, +"build out: cat mid\n" +"build mid: cat in\n" +"build in: cat pre\n" +"build pre: cat out\n"); + + string err; + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("out"), &err)); + ASSERT_EQ("dependency cycle: out -> mid -> in -> pre -> out", err); +} + +TEST_F(GraphTest, CycleInEdgesButNotInNodes1) { + string err; + AssertParse(&state_, +"build a b: cat a\n"); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err)); + ASSERT_EQ("dependency cycle: a -> a", err); +} + +TEST_F(GraphTest, CycleInEdgesButNotInNodes2) { + string err; + ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, +"build b a: cat a\n")); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err)); + ASSERT_EQ("dependency cycle: a -> a", err); +} + +TEST_F(GraphTest, CycleInEdgesButNotInNodes3) { + string err; + ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, +"build a b: cat c\n" +"build c: cat a\n")); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("b"), &err)); + ASSERT_EQ("dependency cycle: a -> c -> a", err); +} + +TEST_F(GraphTest, CycleInEdgesButNotInNodes4) { + string err; + ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, +"build d: cat c\n" +"build c: cat b\n" +"build b: cat a\n" +"build a e: cat d\n" +"build f: cat e\n")); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("f"), &err)); + ASSERT_EQ("dependency cycle: a -> d -> c -> b -> a", err); +} + // Verify that cycles in graphs with multiple outputs are handled correctly // in RecomputeDirty() and don't cause deps to be loaded multiple times. TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) { @@ -347,13 +384,13 @@ TEST_F(GraphTest, CycleWithLengthZeroFromDepfile) { fs_.Create("dep.d", "a: b\n"); string err; - Edge* edge = GetNode("a")->in_edge(); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err)); + ASSERT_EQ("dependency cycle: b -> b", err); // Despite the depfile causing edge to be a cycle (it has outputs a and b, // but the depfile also adds b as an input), the deps should have been loaded // only once: + Edge* edge = GetNode("a")->in_edge(); EXPECT_EQ(1, edge->inputs_.size()); EXPECT_EQ("b", edge->inputs_[0]->path()); } @@ -372,13 +409,13 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfile) { fs_.Create("dep.d", "a: c\n"); string err; - Edge* edge = GetNode("a")->in_edge(); - EXPECT_TRUE(scan_.RecomputeDirty(edge, &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("a"), &err)); + ASSERT_EQ("dependency cycle: b -> c -> b", err); // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b, // but c's in_edge has b as input but the depfile also adds |edge| as // output)), the deps should have been loaded only once: + Edge* edge = GetNode("a")->in_edge(); EXPECT_EQ(1, edge->inputs_.size()); EXPECT_EQ("c", edge->inputs_[0]->path()); } @@ -399,8 +436,8 @@ TEST_F(GraphTest, CycleWithLengthOneFromDepfileOneHopAway) { fs_.Create("dep.d", "a: c\n"); string err; - EXPECT_TRUE(scan_.RecomputeDirty(GetNode("d")->in_edge(), &err)); - ASSERT_EQ("", err); + EXPECT_FALSE(scan_.RecomputeDirty(GetNode("d"), &err)); + ASSERT_EQ("dependency cycle: b -> c -> b", err); // Despite the depfile causing edge to be a cycle (|edge| has outputs a and b, // but c's in_edge has b as input but the depfile also adds |edge| as diff --git a/src/includes_normalize-win32.cc b/src/includes_normalize-win32.cc index ca35012..459329b 100644 --- a/src/includes_normalize-win32.cc +++ b/src/includes_normalize-win32.cc @@ -15,6 +15,7 @@ #include "includes_normalize.h" #include "string_piece.h" +#include "string_piece_util.h" #include "util.h" #include <algorithm> @@ -25,8 +26,39 @@ namespace { -/// Return true if paths a and b are on the same Windows drive. +bool IsPathSeparator(char c) { + return c == '/' || c == '\\'; +} + +// Return true if paths a and b are on the same windows drive. +// Return false if this funcation cannot check +// whether or not on the same windows drive. +bool SameDriveFast(StringPiece a, StringPiece b) { + if (a.size() < 3 || b.size() < 3) { + return false; + } + + if (!islatinalpha(a[0]) || !islatinalpha(b[0])) { + return false; + } + + if (ToLowerASCII(a[0]) != ToLowerASCII(b[0])) { + return false; + } + + if (a[1] != ':' || b[1] != ':') { + return false; + } + + return IsPathSeparator(a[2]) && IsPathSeparator(b[2]); +} + +// Return true if paths a and b are on the same Windows drive. bool SameDrive(StringPiece a, StringPiece b) { + if (SameDriveFast(a, b)) { + return true; + } + char a_absolute[_MAX_PATH]; char b_absolute[_MAX_PATH]; GetFullPathName(a.AsString().c_str(), sizeof(a_absolute), a_absolute, NULL); @@ -38,34 +70,57 @@ bool SameDrive(StringPiece a, StringPiece b) { return _stricmp(a_drive, b_drive) == 0; } -} // anonymous namespace +// Check path |s| is FullPath style returned by GetFullPathName. +// This ignores difference of path separator. +// This is used not to call very slow GetFullPathName API. +bool IsFullPathName(StringPiece s) { + if (s.size() < 3 || + !islatinalpha(s[0]) || + s[1] != ':' || + !IsPathSeparator(s[2])) { + return false; + } + + // Check "." or ".." is contained in path. + for (size_t i = 2; i < s.size(); ++i) { + if (!IsPathSeparator(s[i])) { + continue; + } + + // Check ".". + if (i + 1 < s.size() && s[i+1] == '.' && + (i + 2 >= s.size() || IsPathSeparator(s[i+2]))) { + return false; + } -string IncludesNormalize::Join(const vector<string>& list, char sep) { - string ret; - for (size_t i = 0; i < list.size(); ++i) { - ret += list[i]; - if (i != list.size() - 1) - ret += sep; + // Check "..". + if (i + 2 < s.size() && s[i+1] == '.' && s[i+2] == '.' && + (i + 3 >= s.size() || IsPathSeparator(s[i+3]))) { + return false; + } } - return ret; -} -vector<string> IncludesNormalize::Split(const string& input, char sep) { - vector<string> elems; - stringstream ss(input); - string item; - while (getline(ss, item, sep)) - elems.push_back(item); - return elems; + return true; } -string IncludesNormalize::ToLower(const string& s) { - string ret; - transform(s.begin(), s.end(), back_inserter(ret), ::tolower); - return ret; +} // anonymous namespace + +IncludesNormalize::IncludesNormalize(const string& relative_to) { + relative_to_ = AbsPath(relative_to); + split_relative_to_ = SplitStringPiece(relative_to_, '/'); } string IncludesNormalize::AbsPath(StringPiece s) { + if (IsFullPathName(s)) { + string result = s.AsString(); + for (size_t i = 0; i < result.size(); ++i) { + if (result[i] == '\\') { + result[i] = '/'; + } + } + return result; + } + char result[_MAX_PATH]; GetFullPathName(s.AsString().c_str(), sizeof(result), result, NULL); for (char* c = result; *c; ++c) @@ -74,28 +129,31 @@ string IncludesNormalize::AbsPath(StringPiece s) { return result; } -string IncludesNormalize::Relativize(StringPiece path, const string& start) { - vector<string> start_list = Split(AbsPath(start), '/'); - vector<string> path_list = Split(AbsPath(path), '/'); +string IncludesNormalize::Relativize( + StringPiece path, const vector<StringPiece>& start_list) { + string abs_path = AbsPath(path); + vector<StringPiece> path_list = SplitStringPiece(abs_path, '/'); int i; for (i = 0; i < static_cast<int>(min(start_list.size(), path_list.size())); ++i) { - if (ToLower(start_list[i]) != ToLower(path_list[i])) + if (!EqualsCaseInsensitiveASCII(start_list[i], path_list[i])) { break; + } } - vector<string> rel_list; + vector<StringPiece> rel_list; + rel_list.reserve(start_list.size() - i + path_list.size() - i); for (int j = 0; j < static_cast<int>(start_list.size() - i); ++j) rel_list.push_back(".."); for (int j = i; j < static_cast<int>(path_list.size()); ++j) rel_list.push_back(path_list[j]); if (rel_list.size() == 0) return "."; - return Join(rel_list, '/'); + return JoinStringPiece(rel_list, '/'); } -bool IncludesNormalize::Normalize(const string& input, const char* relative_to, - string* result, string* err) { +bool IncludesNormalize::Normalize(const string& input, + string* result, string* err) const { char copy[_MAX_PATH + 1]; size_t len = input.size(); if (len > _MAX_PATH) { @@ -103,20 +161,16 @@ bool IncludesNormalize::Normalize(const string& input, const char* relative_to, return false; } strncpy(copy, input.c_str(), input.size() + 1); - unsigned int slash_bits; + uint64_t slash_bits; if (!CanonicalizePath(copy, &len, &slash_bits, err)) return false; StringPiece partially_fixed(copy, len); + string abs_input = AbsPath(partially_fixed); - string curdir; - if (!relative_to) { - curdir = AbsPath("."); - relative_to = curdir.c_str(); - } - if (!SameDrive(partially_fixed, relative_to)) { + if (!SameDrive(abs_input, relative_to_)) { *result = partially_fixed.AsString(); return true; } - *result = Relativize(partially_fixed, relative_to); + *result = Relativize(abs_input, split_relative_to_); return true; } diff --git a/src/includes_normalize.h b/src/includes_normalize.h index 98e912f..3811e53 100644 --- a/src/includes_normalize.h +++ b/src/includes_normalize.h @@ -21,15 +21,19 @@ struct StringPiece; /// Utility functions for normalizing include paths on Windows. /// TODO: this likely duplicates functionality of CanonicalizePath; refactor. struct IncludesNormalize { + /// Normalize path relative to |relative_to|. + IncludesNormalize(const string& relative_to); + // Internal utilities made available for testing, maybe useful otherwise. - static string Join(const vector<string>& list, char sep); - static vector<string> Split(const string& input, char sep); - static string ToLower(const string& s); static string AbsPath(StringPiece s); - static string Relativize(StringPiece path, const string& start); + static string Relativize(StringPiece path, + const vector<StringPiece>& start_list); /// Normalize by fixing slashes style, fixing redundant .. and . and makes the - /// path relative to |relative_to|. - static bool Normalize(const string& input, const char* relative_to, - string* result, string* err); + /// path |input| relative to |this->relative_to_| and store to |result|. + bool Normalize(const string& input, string* result, string* err) const; + + private: + string relative_to_; + vector<StringPiece> split_relative_to_; }; diff --git a/src/includes_normalize_test.cc b/src/includes_normalize_test.cc index f18795c..0bb14ec 100644 --- a/src/includes_normalize_test.cc +++ b/src/includes_normalize_test.cc @@ -18,6 +18,7 @@ #include <direct.h> +#include "string_piece_util.h" #include "test.h" #include "util.h" @@ -26,13 +27,14 @@ namespace { string GetCurDir() { char buf[_MAX_PATH]; _getcwd(buf, sizeof(buf)); - vector<string> parts = IncludesNormalize::Split(string(buf), '\\'); - return parts[parts.size() - 1]; + vector<StringPiece> parts = SplitStringPiece(buf, '\\'); + return parts[parts.size() - 1].AsString(); } string NormalizeAndCheckNoError(const string& input) { string result, err; - EXPECT_TRUE(IncludesNormalize::Normalize(input.c_str(), NULL, &result, &err)); + IncludesNormalize normalizer("."); + EXPECT_TRUE(normalizer.Normalize(input, &result, &err)); EXPECT_EQ("", err); return result; } @@ -40,8 +42,8 @@ string NormalizeAndCheckNoError(const string& input) { string NormalizeRelativeAndCheckNoError(const string& input, const string& relative_to) { string result, err; - EXPECT_TRUE(IncludesNormalize::Normalize(input.c_str(), relative_to.c_str(), - &result, &err)); + IncludesNormalize normalizer(relative_to); + EXPECT_TRUE(normalizer.Normalize(input, &result, &err)); EXPECT_EQ("", err); return result; } @@ -76,34 +78,6 @@ TEST(IncludesNormalize, Case) { EXPECT_EQ("A/B", NormalizeAndCheckNoError("A\\./B")); } -TEST(IncludesNormalize, Join) { - vector<string> x; - EXPECT_EQ("", IncludesNormalize::Join(x, ':')); - x.push_back("alpha"); - EXPECT_EQ("alpha", IncludesNormalize::Join(x, ':')); - x.push_back("beta"); - x.push_back("gamma"); - EXPECT_EQ("alpha:beta:gamma", IncludesNormalize::Join(x, ':')); -} - -TEST(IncludesNormalize, Split) { - EXPECT_EQ("", IncludesNormalize::Join(IncludesNormalize::Split("", '/'), - ':')); - EXPECT_EQ("a", IncludesNormalize::Join(IncludesNormalize::Split("a", '/'), - ':')); - EXPECT_EQ("a:b:c", - IncludesNormalize::Join( - IncludesNormalize::Split("a/b/c", '/'), ':')); -} - -TEST(IncludesNormalize, ToLower) { - EXPECT_EQ("", IncludesNormalize::ToLower("")); - EXPECT_EQ("stuff", IncludesNormalize::ToLower("Stuff")); - EXPECT_EQ("stuff and things", IncludesNormalize::ToLower("Stuff AND thINGS")); - EXPECT_EQ("stuff 3and thin43gs", - IncludesNormalize::ToLower("Stuff 3AND thIN43GS")); -} - TEST(IncludesNormalize, DifferentDrive) { EXPECT_EQ("stuff.h", NormalizeRelativeAndCheckNoError("p:\\vs08\\stuff.h", "p:\\vs08")); @@ -129,8 +103,9 @@ TEST(IncludesNormalize, LongInvalidPath) { "instead of /Zi, but expect a similar error when you link your program."; // Too long, won't be canonicalized. Ensure doesn't crash. string result, err; + IncludesNormalize normalizer("."); EXPECT_FALSE( - IncludesNormalize::Normalize(kLongInputString, NULL, &result, &err)); + normalizer.Normalize(kLongInputString, &result, &err)); EXPECT_EQ("path too long", err); const char kExactlyMaxPath[] = diff --git a/src/manifest_parser.cc b/src/manifest_parser.cc index d6dcf22..2164921 100644 --- a/src/manifest_parser.cc +++ b/src/manifest_parser.cc @@ -212,7 +212,7 @@ bool ManifestParser::ParseDefault(string* err) { do { string path = eval.Evaluate(env_); string path_err; - unsigned int slash_bits; // Unused because this only does lookup. + uint64_t slash_bits; // Unused because this only does lookup. if (!CanonicalizePath(&path, &slash_bits, &path_err)) return lexer_.Error(path_err, err); if (!state_->AddDefault(path, &path_err)) @@ -342,7 +342,7 @@ bool ManifestParser::ParseEdge(string* err) { for (size_t i = 0, e = outs.size(); i != e; ++i) { string path = outs[i].Evaluate(env); string path_err; - unsigned int slash_bits; + uint64_t slash_bits; if (!CanonicalizePath(&path, &slash_bits, &path_err)) return lexer_.Error(path_err, err); if (!state_->AddOut(edge, path, slash_bits)) { @@ -375,7 +375,7 @@ bool ManifestParser::ParseEdge(string* err) { for (vector<EvalString>::iterator i = ins.begin(); i != ins.end(); ++i) { string path = i->Evaluate(env); string path_err; - unsigned int slash_bits; + uint64_t slash_bits; if (!CanonicalizePath(&path, &slash_bits, &path_err)) return lexer_.Error(path_err, err); state_->AddIn(edge, path, slash_bits); diff --git a/src/minidump-win32.cc b/src/minidump-win32.cc index c611919..1efb085 100644 --- a/src/minidump-win32.cc +++ b/src/minidump-win32.cc @@ -34,7 +34,7 @@ void CreateWin32MiniDump(_EXCEPTION_POINTERS* pep) { char temp_path[MAX_PATH]; GetTempPath(sizeof(temp_path), temp_path); char temp_file[MAX_PATH]; - sprintf(temp_file, "%s\\ninja_crash_dump_%d.dmp", + sprintf(temp_file, "%s\\ninja_crash_dump_%lu.dmp", temp_path, GetCurrentProcessId()); // Delete any previous minidump of the same name. diff --git a/src/ninja.cc b/src/ninja.cc index 25eafe8..54de7b9 100644 --- a/src/ninja.cc +++ b/src/ninja.cc @@ -233,7 +233,7 @@ int GuessParallelism() { /// Returns true if the manifest was rebuilt. bool NinjaMain::RebuildManifest(const char* input_file, string* err) { string path = input_file; - unsigned int slash_bits; // Unused because this path is only used for lookup. + uint64_t slash_bits; // Unused because this path is only used for lookup. if (!CanonicalizePath(&path, &slash_bits, err)) return false; Node* node = state_.LookupNode(path); @@ -247,15 +247,24 @@ bool NinjaMain::RebuildManifest(const char* input_file, string* err) { if (builder.AlreadyUpToDate()) return false; // Not an error, but we didn't rebuild. - // Even if the manifest was cleaned by a restat rule, claim that it was - // rebuilt. Not doing so can lead to crashes, see - // https://github.com/ninja-build/ninja/issues/874 - return builder.Build(err); + if (!builder.Build(err)) + return false; + + // The manifest was only rebuilt if it is now dirty (it may have been cleaned + // by a restat). + if (!node->dirty()) { + // Reset the state to prevent problems like + // https://github.com/ninja-build/ninja/issues/874 + state_.Reset(); + return false; + } + + return true; } Node* NinjaMain::CollectTarget(const char* cpath, string* err) { string path = cpath; - unsigned int slash_bits; + uint64_t slash_bits; if (!CanonicalizePath(&path, &slash_bits, err)) return NULL; @@ -533,21 +542,51 @@ int NinjaMain::ToolTargets(const Options* options, int argc, char* argv[]) { } } -void PrintCommands(Edge* edge, set<Edge*>* seen) { +enum PrintCommandMode { PCM_Single, PCM_All }; +void PrintCommands(Edge* edge, set<Edge*>* seen, PrintCommandMode mode) { if (!edge) return; if (!seen->insert(edge).second) return; - for (vector<Node*>::iterator in = edge->inputs_.begin(); - in != edge->inputs_.end(); ++in) - PrintCommands((*in)->in_edge(), seen); + if (mode == PCM_All) { + for (vector<Node*>::iterator in = edge->inputs_.begin(); + in != edge->inputs_.end(); ++in) + PrintCommands((*in)->in_edge(), seen, mode); + } if (!edge->is_phony()) puts(edge->EvaluateCommand().c_str()); } int NinjaMain::ToolCommands(const Options* options, int argc, char* argv[]) { + // The clean tool uses getopt, and expects argv[0] to contain the name of + // the tool, i.e. "commands". + ++argc; + --argv; + + PrintCommandMode mode = PCM_All; + + optind = 1; + int opt; + while ((opt = getopt(argc, argv, const_cast<char*>("hs"))) != -1) { + switch (opt) { + case 's': + mode = PCM_Single; + break; + case 'h': + default: + printf("usage: ninja -t commands [options] [targets]\n" +"\n" +"options:\n" +" -s only print the final command to build [target], not the whole chain\n" + ); + return 1; + } + } + argv += optind; + argc -= optind; + vector<Node*> nodes; string err; if (!CollectTargetsFromArgs(argc, argv, &nodes, &err)) { @@ -557,7 +596,7 @@ int NinjaMain::ToolCommands(const Options* options, int argc, char* argv[]) { set<Edge*> seen; for (vector<Node*>::iterator in = nodes.begin(); in != nodes.end(); ++in) - PrintCommands((*in)->in_edge(), &seen); + PrintCommands((*in)->in_edge(), &seen, mode); return 0; } diff --git a/src/state.cc b/src/state.cc index d539e7b..9b3c7e1 100644 --- a/src/state.cc +++ b/src/state.cc @@ -100,7 +100,7 @@ Edge* State::AddEdge(const Rule* rule) { return edge; } -Node* State::GetNode(StringPiece path, unsigned int slash_bits) { +Node* State::GetNode(StringPiece path, uint64_t slash_bits) { Node* node = LookupNode(path); if (node) return node; @@ -134,13 +134,13 @@ Node* State::SpellcheckNode(const string& path) { return result; } -void State::AddIn(Edge* edge, StringPiece path, unsigned int slash_bits) { +void State::AddIn(Edge* edge, StringPiece path, uint64_t slash_bits) { Node* node = GetNode(path, slash_bits); edge->inputs_.push_back(node); node->AddOutEdge(edge); } -bool State::AddOut(Edge* edge, StringPiece path, unsigned int slash_bits) { +bool State::AddOut(Edge* edge, StringPiece path, uint64_t slash_bits) { Node* node = GetNode(path, slash_bits); if (node->in_edge()) return false; @@ -184,8 +184,10 @@ vector<Node*> State::DefaultNodes(string* err) const { void State::Reset() { for (Paths::iterator i = paths_.begin(); i != paths_.end(); ++i) i->second->ResetState(); - for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) + for (vector<Edge*>::iterator e = edges_.begin(); e != edges_.end(); ++e) { (*e)->outputs_ready_ = false; + (*e)->mark_ = Edge::VisitNone; + } } void State::Dump() { diff --git a/src/state.h b/src/state.h index b530207..54e9dc5 100644 --- a/src/state.h +++ b/src/state.h @@ -23,6 +23,7 @@ using namespace std; #include "eval_env.h" #include "hash_map.h" +#include "util.h" struct Edge; struct Node; @@ -93,12 +94,12 @@ struct State { Edge* AddEdge(const Rule* rule); - Node* GetNode(StringPiece path, unsigned int slash_bits); + Node* GetNode(StringPiece path, uint64_t slash_bits); Node* LookupNode(StringPiece path) const; Node* SpellcheckNode(const string& path); - void AddIn(Edge* edge, StringPiece path, unsigned int slash_bits); - bool AddOut(Edge* edge, StringPiece path, unsigned int slash_bits); + void AddIn(Edge* edge, StringPiece path, uint64_t slash_bits); + bool AddOut(Edge* edge, StringPiece path, uint64_t slash_bits); bool AddDefault(StringPiece path, string* error); /// Reset state. Keeps all nodes and edges, but restores them to the diff --git a/src/string_piece.h b/src/string_piece.h index b1bf105..031bda4 100644 --- a/src/string_piece.h +++ b/src/string_piece.h @@ -25,6 +25,8 @@ using namespace std; /// externally. It is useful for reducing the number of std::strings /// we need to allocate. struct StringPiece { + typedef const char* const_iterator; + StringPiece() : str_(NULL), len_(0) {} /// The constructors intentionally allow for implicit conversions. @@ -46,6 +48,22 @@ struct StringPiece { return len_ ? string(str_, len_) : string(); } + const_iterator begin() const { + return str_; + } + + const_iterator end() const { + return str_ + len_; + } + + char operator[](size_t pos) const { + return str_[pos]; + } + + size_t size() const { + return len_; + } + const char* str_; size_t len_; }; diff --git a/src/string_piece_util.cc b/src/string_piece_util.cc new file mode 100644 index 0000000..8e1ecfd --- /dev/null +++ b/src/string_piece_util.cc @@ -0,0 +1,78 @@ +// Copyright 2017 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. + +#include "string_piece_util.h" + +#include <algorithm> +#include <string> +#include <vector> +using namespace std; + +vector<StringPiece> SplitStringPiece(StringPiece input, char sep) { + vector<StringPiece> elems; + elems.reserve(count(input.begin(), input.end(), sep) + 1); + + StringPiece::const_iterator pos = input.begin(); + + for (;;) { + const char* next_pos = find(pos, input.end(), sep); + if (next_pos == input.end()) { + elems.push_back(StringPiece(pos, input.end() - pos)); + break; + } + elems.push_back(StringPiece(pos, next_pos - pos)); + pos = next_pos + 1; + } + + return elems; +} + +string JoinStringPiece(const vector<StringPiece>& list, char sep) { + if (list.size() == 0){ + return ""; + } + + string ret; + + { + size_t cap = list.size() - 1; + for (size_t i = 0; i < list.size(); ++i) { + cap += list[i].len_; + } + ret.reserve(cap); + } + + for (size_t i = 0; i < list.size(); ++i) { + if (i != 0) { + ret += sep; + } + ret.append(list[i].str_, list[i].len_); + } + + return ret; +} + +bool EqualsCaseInsensitiveASCII(StringPiece a, StringPiece b) { + if (a.len_ != b.len_) { + return false; + } + + for (size_t i = 0; i < a.len_; ++i) { + if (ToLowerASCII(a.str_[i]) != ToLowerASCII(b.str_[i])) { + return false; + } + } + + return true; +} diff --git a/src/string_piece_util.h b/src/string_piece_util.h new file mode 100644 index 0000000..2e40b9f --- /dev/null +++ b/src/string_piece_util.h @@ -0,0 +1,34 @@ +// Copyright 2017 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 NINJA_STRINGPIECE_UTIL_H_ +#define NINJA_STRINGPIECE_UTIL_H_ + +#include <string> +#include <vector> + +#include "string_piece.h" +using namespace std; + +vector<StringPiece> SplitStringPiece(StringPiece input, char sep); + +string JoinStringPiece(const vector<StringPiece>& list, char sep); + +inline char ToLowerASCII(char c) { + return (c >= 'A' && c <= 'Z') ? (c + ('a' - 'A')) : c; +} + +bool EqualsCaseInsensitiveASCII(StringPiece a, StringPiece b); + +#endif // NINJA_STRINGPIECE_UTIL_H_ diff --git a/src/string_piece_util_test.cc b/src/string_piece_util_test.cc new file mode 100644 index 0000000..648c647 --- /dev/null +++ b/src/string_piece_util_test.cc @@ -0,0 +1,129 @@ +// Copyright 2017 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. + +#include "string_piece_util.h" + +#include "test.h" + +TEST(StringPieceUtilTest, SplitStringPiece) { + { + string input("a:b:c"); + vector<StringPiece> list = SplitStringPiece(input, ':'); + + EXPECT_EQ(list.size(), 3); + + EXPECT_EQ(list[0], "a"); + EXPECT_EQ(list[1], "b"); + EXPECT_EQ(list[2], "c"); + } + + { + string empty(""); + vector<StringPiece> list = SplitStringPiece(empty, ':'); + + EXPECT_EQ(list.size(), 1); + + EXPECT_EQ(list[0], ""); + } + + { + string one("a"); + vector<StringPiece> list = SplitStringPiece(one, ':'); + + EXPECT_EQ(list.size(), 1); + + EXPECT_EQ(list[0], "a"); + } + + { + string sep_only(":"); + vector<StringPiece> list = SplitStringPiece(sep_only, ':'); + + EXPECT_EQ(list.size(), 2); + + EXPECT_EQ(list[0], ""); + EXPECT_EQ(list[1], ""); + } + + { + string sep(":a:b:c:"); + vector<StringPiece> list = SplitStringPiece(sep, ':'); + + EXPECT_EQ(list.size(), 5); + + EXPECT_EQ(list[0], ""); + EXPECT_EQ(list[1], "a"); + EXPECT_EQ(list[2], "b"); + EXPECT_EQ(list[3], "c"); + EXPECT_EQ(list[4], ""); + } +} + +TEST(StringPieceUtilTest, JoinStringPiece) { + { + string input("a:b:c"); + vector<StringPiece> list = SplitStringPiece(input, ':'); + + EXPECT_EQ("a:b:c", JoinStringPiece(list, ':')); + EXPECT_EQ("a/b/c", JoinStringPiece(list, '/')); + } + + { + string empty(""); + vector<StringPiece> list = SplitStringPiece(empty, ':'); + + EXPECT_EQ("", JoinStringPiece(list, ':')); + } + + { + vector<StringPiece> empty_list; + + EXPECT_EQ("", JoinStringPiece(empty_list, ':')); + } + + { + string one("a"); + vector<StringPiece> single_list = SplitStringPiece(one, ':'); + + EXPECT_EQ("a", JoinStringPiece(single_list, ':')); + } + + { + string sep(":a:b:c:"); + vector<StringPiece> list = SplitStringPiece(sep, ':'); + + EXPECT_EQ(":a:b:c:", JoinStringPiece(list, ':')); + } +} + +TEST(StringPieceUtilTest, ToLowerASCII) { + EXPECT_EQ('a', ToLowerASCII('A')); + EXPECT_EQ('z', ToLowerASCII('Z')); + EXPECT_EQ('a', ToLowerASCII('a')); + EXPECT_EQ('z', ToLowerASCII('z')); + EXPECT_EQ('/', ToLowerASCII('/')); + EXPECT_EQ('1', ToLowerASCII('1')); +} + +TEST(StringPieceUtilTest, EqualsCaseInsensitiveASCII) { + EXPECT_TRUE(EqualsCaseInsensitiveASCII("abc", "abc")); + EXPECT_TRUE(EqualsCaseInsensitiveASCII("abc", "ABC")); + EXPECT_TRUE(EqualsCaseInsensitiveASCII("abc", "aBc")); + EXPECT_TRUE(EqualsCaseInsensitiveASCII("AbC", "aBc")); + EXPECT_TRUE(EqualsCaseInsensitiveASCII("", "")); + + EXPECT_FALSE(EqualsCaseInsensitiveASCII("a", "ac")); + EXPECT_FALSE(EqualsCaseInsensitiveASCII("/", "\\")); + EXPECT_FALSE(EqualsCaseInsensitiveASCII("1", "10")); +} diff --git a/src/subprocess-posix.cc b/src/subprocess-posix.cc index 5ffe85b..1de22c3 100644 --- a/src/subprocess-posix.cc +++ b/src/subprocess-posix.cc @@ -73,8 +73,6 @@ bool Subprocess::Start(SubprocessSet* set, const string& command) { // default action in the new process image, so no explicit // POSIX_SPAWN_SETSIGDEF parameter is needed. - // TODO: Consider using POSIX_SPAWN_USEVFORK on Linux with glibc? - if (!use_console_) { // Put the child in its own process group, so ctrl-c won't reach it. flags |= POSIX_SPAWN_SETPGROUP; @@ -90,9 +88,14 @@ bool Subprocess::Start(SubprocessSet* set, const string& command) { Fatal("posix_spawn_file_actions_adddup2: %s", strerror(errno)); if (posix_spawn_file_actions_adddup2(&action, output_pipe[1], 2) != 0) Fatal("posix_spawn_file_actions_adddup2: %s", strerror(errno)); + if (posix_spawn_file_actions_addclose(&action, output_pipe[1]) != 0) + Fatal("posix_spawn_file_actions_addclose: %s", strerror(errno)); // In the console case, output_pipe is still inherited by the child and // closed when the subprocess finishes, which then notifies ninja. } +#ifdef POSIX_SPAWN_USEVFORK + flags |= POSIX_SPAWN_USEVFORK; +#endif if (posix_spawnattr_setflags(&attr, flags) != 0) Fatal("posix_spawnattr_setflags: %s", strerror(errno)); diff --git a/src/util.cc b/src/util.cc index e31fd1f..ae94d34 100644 --- a/src/util.cc +++ b/src/util.cc @@ -90,7 +90,7 @@ void Error(const char* msg, ...) { fprintf(stderr, "\n"); } -bool CanonicalizePath(string* path, unsigned int* slash_bits, string* err) { +bool CanonicalizePath(string* path, uint64_t* slash_bits, string* err) { METRIC_RECORD("canonicalize str"); size_t len = path->size(); char* str = 0; @@ -102,20 +102,15 @@ bool CanonicalizePath(string* path, unsigned int* slash_bits, string* err) { return true; } +static bool IsPathSeparator(char c) { #ifdef _WIN32 -static unsigned int ShiftOverBit(int offset, unsigned int bits) { - // e.g. for |offset| == 2: - // | ... 9 8 7 6 5 4 3 2 1 0 | - // \_________________/ \_/ - // above below - // So we drop the bit at offset and move above "down" into its place. - unsigned int above = bits & ~((1 << (offset + 1)) - 1); - unsigned int below = bits & ((1 << offset) - 1); - return (above >> 1) | below; -} + return c == '/' || c == '\\'; +#else + return c == '/'; #endif +} -bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, +bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits, string* err) { // WARNING: this function is performance-critical; please benchmark // any changes you make to it. @@ -125,7 +120,7 @@ bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, return false; } - const int kMaxPathComponents = 30; + const int kMaxPathComponents = 60; char* components[kMaxPathComponents]; int component_count = 0; @@ -134,37 +129,13 @@ bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, const char* src = start; const char* end = start + *len; + if (IsPathSeparator(*src)) { #ifdef _WIN32 - unsigned int bits = 0; - unsigned int bits_mask = 1; - int bits_offset = 0; - // Convert \ to /, setting a bit in |bits| for each \ encountered. - for (char* c = path; c < end; ++c) { - switch (*c) { - case '\\': - bits |= bits_mask; - *c = '/'; - // Intentional fallthrough. - case '/': - bits_mask <<= 1; - bits_offset++; - } - } - if (bits_offset > 32) { - *err = "too many path components"; - return false; - } - bits_offset = 0; -#endif - if (*src == '/') { -#ifdef _WIN32 - bits_offset++; // network path starts with // - if (*len > 1 && *(src + 1) == '/') { + if (*len > 1 && IsPathSeparator(*(src + 1))) { src += 2; dst += 2; - bits_offset++; } else { ++src; ++dst; @@ -177,24 +148,16 @@ bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, while (src < end) { if (*src == '.') { - if (src + 1 == end || src[1] == '/') { + if (src + 1 == end || IsPathSeparator(src[1])) { // '.' component; eliminate. src += 2; -#ifdef _WIN32 - bits = ShiftOverBit(bits_offset, bits); -#endif continue; - } else if (src[1] == '.' && (src + 2 == end || src[2] == '/')) { + } else if (src[1] == '.' && (src + 2 == end || IsPathSeparator(src[2]))) { // '..' component. Back up if possible. if (component_count > 0) { dst = components[component_count - 1]; src += 3; --component_count; -#ifdef _WIN32 - bits = ShiftOverBit(bits_offset, bits); - bits_offset--; - bits = ShiftOverBit(bits_offset, bits); -#endif } else { *dst++ = *src++; *dst++ = *src++; @@ -204,11 +167,8 @@ bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, } } - if (*src == '/') { + if (IsPathSeparator(*src)) { src++; -#ifdef _WIN32 - bits = ShiftOverBit(bits_offset, bits); -#endif continue; } @@ -217,11 +177,8 @@ bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, components[component_count] = dst; ++component_count; - while (*src != '/' && src != end) + while (src != end && !IsPathSeparator(*src)) *dst++ = *src++; -#ifdef _WIN32 - bits_offset++; -#endif *dst++ = *src++; // Copy '/' or final \0 character as well. } @@ -232,6 +189,20 @@ bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, *len = dst - start - 1; #ifdef _WIN32 + uint64_t bits = 0; + uint64_t bits_mask = 1; + + for (char* c = start; c < start + *len; ++c) { + switch (*c) { + case '\\': + bits |= bits_mask; + *c = '/'; + // Intentional fallthrough. + case '/': + bits_mask <<= 1; + } + } + *slash_bits = bits; #else *slash_bits = 0; @@ -471,7 +442,7 @@ void Win32Fatal(const char* function) { } #endif -static bool islatinalpha(int c) { +bool islatinalpha(int c) { // isalpha() is locale-dependent. return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } @@ -585,6 +556,13 @@ double GetLoadAverage() { // Calculation taken from comment in libperfstats.h return double(cpu_stats.loadavg[0]) / double(1 << SBITS); } +#elif defined(__UCLIBC__) +double GetLoadAverage() { + struct sysinfo si; + if (sysinfo(&si) != 0) + return -0.0f; + return 1.0 / (1 << SI_LOAD_SHIFT) * si.loads[0]; +} #else double GetLoadAverage() { double loadavg[3] = { 0.0f, 0.0f, 0.0f }; @@ -43,8 +43,8 @@ void Error(const char* msg, ...); /// Canonicalize a path like "foo/../bar.h" into just "bar.h". /// |slash_bits| has bits set starting from lowest for a backslash that was /// normalized to a forward slash. (only used on Windows) -bool CanonicalizePath(string* path, unsigned int* slash_bits, string* err); -bool CanonicalizePath(char* path, size_t* len, unsigned int* slash_bits, +bool CanonicalizePath(string* path, uint64_t* slash_bits, string* err); +bool CanonicalizePath(char* path, size_t* len, uint64_t* slash_bits, string* err); /// Appends |input| to |*result|, escaping according to the whims of either @@ -70,6 +70,8 @@ const char* SpellcheckStringV(const string& text, /// Like SpellcheckStringV, but takes a NULL-terminated list. const char* SpellcheckString(const char* text, ...); +bool islatinalpha(int c); + /// Removes all Ansi escape codes (http://www.termsys.demon.co.uk/vtansi.htm). string StripAnsiEscapeCodes(const string& in); diff --git a/src/util_test.cc b/src/util_test.cc index 33a4107..b4b7516 100644 --- a/src/util_test.cc +++ b/src/util_test.cc @@ -19,7 +19,7 @@ namespace { bool CanonicalizePath(string* path, string* err) { - unsigned int unused; + uint64_t unused; return ::CanonicalizePath(path, &unused, err); } @@ -177,7 +177,7 @@ TEST(CanonicalizePath, PathSamplesWindows) { TEST(CanonicalizePath, SlashTracking) { string path; string err; - unsigned int slash_bits; + uint64_t slash_bits; path = "foo.h"; err = ""; EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err)); @@ -263,7 +263,7 @@ TEST(CanonicalizePath, SlashTracking) { TEST(CanonicalizePath, CanonicalizeNotExceedingLen) { // Make sure searching \/ doesn't go past supplied len. char buf[] = "foo/bar\\baz.h\\"; // Last \ past end. - unsigned int slash_bits; + uint64_t slash_bits; string err; size_t size = 13; EXPECT_TRUE(::CanonicalizePath(buf, &size, &slash_bits, &err)); @@ -274,33 +274,60 @@ TEST(CanonicalizePath, CanonicalizeNotExceedingLen) { TEST(CanonicalizePath, TooManyComponents) { string path; string err; - unsigned int slash_bits; + uint64_t slash_bits; - // 32 is OK. - path = "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./x.h"; + // 64 is OK. + path = "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./" + "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./x.h"; EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err)); + EXPECT_EQ(slash_bits, 0x0); // Backslashes version. path = - "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\." - "\\a\\.\\a\\.\\a\\.\\a\\.\\x.h"; + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\" + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\" + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\" + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\x.h"; + + EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err)); + EXPECT_EQ(slash_bits, 0xffffffff); + + // 65 is OK if #component is less than 60 after path canonicalization. + err = ""; + path = "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./" + "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./x/y.h"; EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err)); - EXPECT_EQ(slash_bits, 0xffff); + EXPECT_EQ(slash_bits, 0x0); - // 33 is not. + // Backslashes version. err = ""; path = - "a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/./a/x.h"; - EXPECT_FALSE(CanonicalizePath(&path, &slash_bits, &err)); - EXPECT_EQ(err, "too many path components"); + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\" + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\" + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\" + "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\x\\y.h"; + EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err)); + EXPECT_EQ(slash_bits, 0x1ffffffff); + + + // 59 after canonicalization is OK. + err = ""; + path = "a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/" + "a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/a/x/y.h"; + EXPECT_EQ(58, std::count(path.begin(), path.end(), '/')); + EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err)); + EXPECT_EQ(slash_bits, 0x0); // Backslashes version. err = ""; path = - "a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\.\\a\\." - "\\a\\.\\a\\.\\a\\.\\a\\.\\a\\x.h"; - EXPECT_FALSE(CanonicalizePath(&path, &slash_bits, &err)); - EXPECT_EQ(err, "too many path components"); + "a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\" + "a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\" + "a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\a\\" + "a\\a\\a\\a\\a\\a\\a\\a\\a\\x\\y.h"; + EXPECT_EQ(58, std::count(path.begin(), path.end(), '\\')); + EXPECT_TRUE(CanonicalizePath(&path, &slash_bits, &err)); + EXPECT_EQ(slash_bits, 0x3ffffffffffffff); } #endif @@ -326,7 +353,7 @@ TEST(CanonicalizePath, NotNullTerminated) { string path; string err; size_t len; - unsigned int unused; + uint64_t unused; path = "foo/. bar/."; len = strlen("foo/."); // Canonicalize only the part before the space. diff --git a/src/version.cc b/src/version.cc index eafa082..ad2d09f 100644 --- a/src/version.cc +++ b/src/version.cc @@ -18,7 +18,7 @@ #include "util.h" -const char* kNinjaVersion = "1.7.2"; +const char* kNinjaVersion = "1.8.0"; void ParseVersion(const string& version, int* major, int* minor) { size_t end = version.find('.'); |