From 72b3dae6aa936e9eabf4c22e5602c572a9756cbe Mon Sep 17 00:00:00 2001 From: Robert Iannucci Date: Mon, 18 Mar 2013 09:53:53 -0700 Subject: Fix duplicate edge Pool crash in the minimally invasive way --- src/build.cc | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/src/build.cc b/src/build.cc index 701fa92..2910385 100644 --- a/src/build.cc +++ b/src/build.cc @@ -418,6 +418,12 @@ Edge* Plan::FindWork() { void Plan::ScheduleWork(Edge* edge) { Pool* pool = edge->pool(); if (pool->ShouldDelayEdge()) { + // The graph is not completely clean. Some Nodes have duplicate Out edges. + // We need to explicitly ignore these here, otherwise their work will get + // scheduled twice (see https://github.com/martine/ninja/pull/519) + if (ready_.count(edge)) { + return; + } pool->DelayEdge(edge); pool->RetrieveReadyEdges(&ready_); } else { -- cgit v0.12 From 8e70a53058a74d3582c609fd9f7c133dae7387b4 Mon Sep 17 00:00:00 2001 From: Robert Iannucci Date: Mon, 18 Mar 2013 10:36:23 -0700 Subject: Fix Pool to use a set internally --- src/state.cc | 19 ++++++++++++++----- src/state.h | 6 ++++-- 2 files changed, 18 insertions(+), 7 deletions(-) diff --git a/src/state.cc b/src/state.cc index b5d2622..cd43e0d 100644 --- a/src/state.cc +++ b/src/state.cc @@ -35,23 +35,25 @@ void Pool::EdgeFinished(const Edge& edge) { void Pool::DelayEdge(Edge* edge) { assert(depth_ != 0); - delayed_.push_back(edge); + delayed_.insert(edge); } void Pool::RetrieveReadyEdges(set* ready_queue) { - while (!delayed_.empty()) { - Edge* edge = delayed_.front(); + set::iterator it = delayed_.begin(); + while (it != delayed_.end()) { + Edge* edge = *it; if (current_use_ + edge->weight() > depth_) break; - delayed_.pop_front(); ready_queue->insert(edge); EdgeScheduled(*edge); + ++it; } + delayed_.erase(delayed_.begin(), it); } void Pool::Dump() const { printf("%s (%d/%d) ->\n", name_.c_str(), current_use_, depth_); - for (deque::const_iterator it = delayed_.begin(); + for (set::const_iterator it = delayed_.begin(); it != delayed_.end(); ++it) { printf("\t"); @@ -59,6 +61,13 @@ void Pool::Dump() const { } } +bool Pool::WeightedEdgeCmp(const Edge* a, const Edge* b) { + if (!a) return b; + if (!b) return false; + int weight_diff = a->weight() - b->weight(); + return ((weight_diff < 0) || (weight_diff == 0 && a < b)); +} + Pool State::kDefaultPool("", 0); const Rule State::kPhonyRule("phony"); diff --git a/src/state.h b/src/state.h index 0a2e890..279a64a 100644 --- a/src/state.h +++ b/src/state.h @@ -39,7 +39,7 @@ struct Rule; /// completes). struct Pool { explicit Pool(const string& name, int depth) - : name_(name), current_use_(0), depth_(depth) { } + : name_(name), current_use_(0), depth_(depth), delayed_(&WeightedEdgeCmp) { } // A depth of 0 is infinite bool is_valid() const { return depth_ >= 0; } @@ -74,7 +74,9 @@ struct Pool { int current_use_; int depth_; - deque delayed_; + static bool WeightedEdgeCmp(const Edge* a, const Edge* b); + + set delayed_; }; /// Global state (file status, loaded rules) for a single run. -- cgit v0.12 From f31836a18621a5477ae6888d832afb96f1a56f52 Mon Sep 17 00:00:00 2001 From: Robert Iannucci Date: Sat, 23 Mar 2013 14:31:05 -0700 Subject: Fix debug build on linux (type strictness). --- src/state.cc | 4 ++-- src/state.h | 3 ++- 2 files changed, 4 insertions(+), 3 deletions(-) diff --git a/src/state.cc b/src/state.cc index cd43e0d..9f46fee 100644 --- a/src/state.cc +++ b/src/state.cc @@ -39,7 +39,7 @@ void Pool::DelayEdge(Edge* edge) { } void Pool::RetrieveReadyEdges(set* ready_queue) { - set::iterator it = delayed_.begin(); + DelayedEdges::iterator it = delayed_.begin(); while (it != delayed_.end()) { Edge* edge = *it; if (current_use_ + edge->weight() > depth_) @@ -53,7 +53,7 @@ void Pool::RetrieveReadyEdges(set* ready_queue) { void Pool::Dump() const { printf("%s (%d/%d) ->\n", name_.c_str(), current_use_, depth_); - for (set::const_iterator it = delayed_.begin(); + for (DelayedEdges::const_iterator it = delayed_.begin(); it != delayed_.end(); ++it) { printf("\t"); diff --git a/src/state.h b/src/state.h index 279a64a..7e3aead 100644 --- a/src/state.h +++ b/src/state.h @@ -76,7 +76,8 @@ struct Pool { static bool WeightedEdgeCmp(const Edge* a, const Edge* b); - set delayed_; + typedef set DelayedEdges; + DelayedEdges delayed_; }; /// Global state (file status, loaded rules) for a single run. -- cgit v0.12 From 55be532e10777b050da68e3baede42181202558c Mon Sep 17 00:00:00 2001 From: Robert Iannucci Date: Sat, 23 Mar 2013 14:35:10 -0700 Subject: Add regression test --- src/build_test.cc | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 74 insertions(+) diff --git a/src/build_test.cc b/src/build_test.cc index 59c4c53..40a82ed 100644 --- a/src/build_test.cc +++ b/src/build_test.cc @@ -302,6 +302,80 @@ TEST_F(PlanTest, PoolsWithDepthTwo) { ASSERT_FALSE(plan_.FindWork()); } +TEST_F(PlanTest, PoolWithRedundantEdges) { + ASSERT_NO_FATAL_FAILURE(AssertParse(&state_, + "pool compile\n" + " depth = 1\n" + "rule gen_foo\n" + " command = touch foo.cpp\n" + "rule gen_bar\n" + " command = touch bar.cpp\n" + "rule echo\n" + " command = echo $out > $out\n" + "build foo.cpp.obj: echo foo.cpp || foo.cpp\n" + " pool = compile\n" + "build bar.cpp.obj: echo bar.cpp || bar.cpp\n" + " pool = compile\n" + "build libfoo.a: echo foo.cpp.obj bar.cpp.obj\n" + "build foo.cpp: gen_foo\n" + "build bar.cpp: gen_bar\n" + "build all: phony libfoo.a\n")); + GetNode("foo.cpp")->MarkDirty(); + GetNode("foo.cpp.obj")->MarkDirty(); + GetNode("bar.cpp")->MarkDirty(); + GetNode("bar.cpp.obj")->MarkDirty(); + GetNode("libfoo.a")->MarkDirty(); + GetNode("all")->MarkDirty(); + string err; + EXPECT_TRUE(plan_.AddTarget(GetNode("all"), &err)); + ASSERT_EQ("", err); + ASSERT_TRUE(plan_.more_to_do()); + + Edge* edge = NULL; + + edge = plan_.FindWork(); + ASSERT_TRUE(edge); + ASSERT_EQ("foo.cpp", edge->outputs_[0]->path()); + plan_.EdgeFinished(edge); + + edge = plan_.FindWork(); + ASSERT_TRUE(edge); + ASSERT_EQ("foo.cpp", edge->inputs_[0]->path()); + ASSERT_EQ("foo.cpp", edge->inputs_[1]->path()); + ASSERT_EQ("foo.cpp.obj", edge->outputs_[0]->path()); + plan_.EdgeFinished(edge); + + edge = plan_.FindWork(); + ASSERT_TRUE(edge); + ASSERT_EQ("bar.cpp", edge->outputs_[0]->path()); + plan_.EdgeFinished(edge); + + edge = plan_.FindWork(); + ASSERT_TRUE(edge); + ASSERT_EQ("bar.cpp", edge->inputs_[0]->path()); + ASSERT_EQ("bar.cpp", edge->inputs_[1]->path()); + ASSERT_EQ("bar.cpp.obj", edge->outputs_[0]->path()); + plan_.EdgeFinished(edge); + + edge = plan_.FindWork(); + ASSERT_TRUE(edge); + ASSERT_EQ("foo.cpp.obj", edge->inputs_[0]->path()); + ASSERT_EQ("bar.cpp.obj", edge->inputs_[1]->path()); + ASSERT_EQ("libfoo.a", edge->outputs_[0]->path()); + plan_.EdgeFinished(edge); + + edge = plan_.FindWork(); + ASSERT_TRUE(edge); + ASSERT_EQ("libfoo.a", edge->inputs_[0]->path()); + ASSERT_EQ("all", edge->outputs_[0]->path()); + plan_.EdgeFinished(edge); + + edge = plan_.FindWork(); + ASSERT_FALSE(edge); + ASSERT_FALSE(plan_.more_to_do()); +} + + struct BuildTest : public StateTestWithBuiltinRules, public CommandRunner { BuildTest() : config_(MakeConfig()), -- cgit v0.12