Make all task lists std::set instead of std::list to make sure to not contain duplicates.

9 files changed, 106 insertions, 99 deletions

diff --git a/src/build.cc b/src/build.cc
index 8adbc54..b0b4d06 100644
--- a/src/build.cc
+++ b/src/build.cc
@@ -9,13 +9,14 @@
 #include <chrono>
 #include <set>
 #include <thread>
+#include <list>
 
 using namespace std::chrono_literals;
 
 int build(const Settings& settings,
           const std::string& name,
-          const std::list<std::shared_ptr<Task>>& tasks,
-          const std::list<std::shared_ptr<Task>>& all_tasks,
+          const std::set<std::shared_ptr<Task>>& tasks,
+          const std::set<std::shared_ptr<Task>>& all_tasks,
           bool dryrun)
 {
 	if(settings.verbose > 1)
@@ -23,12 +24,12 @@ int build(const Settings& settings,
 		std::cout << "Building '" << name << "'\n";
 	}
 
-	std::list<std::shared_ptr<Task>> dirtyTasks;
+	std::set<std::shared_ptr<Task>> dirtyTasks;
 	for(auto task : tasks)
 	{
 		if(task->dirty())
 		{
-			dirtyTasks.push_back(task);
+			dirtyTasks.insert(task);
 		}
 	}
 
@@ -155,7 +156,7 @@ std::set<std::shared_ptr<Task>> getDepTasks(std::shared_ptr<Task> task)
 
 int build(const Settings& settings,
           const std::string& name,
-          const std::list<std::shared_ptr<Task>>& all_tasks,
+          const std::set<std::shared_ptr<Task>>& all_tasks,
           bool dryrun)
 {
 	bool task_found{false};
@@ -172,10 +173,10 @@ int build(const Settings& settings,
 			task_found = true;
 
 			auto depSet = getDepTasks(task);
-			std::list<std::shared_ptr<Task>> ts;
+			std::set<std::shared_ptr<Task>> ts;
 			for(const auto& task : depSet)
 			{
-				ts.push_back(task);
+				ts.insert(task);
 			}
 
 			auto ret = build(settings, name, ts, all_tasks, dryrun);
@@ -200,11 +201,11 @@ int build(const Settings& settings,
 int build(const Settings& settings,
           const std::string& name,
           const std::vector<Target>& targets,
-          const std::list<std::shared_ptr<Task>>& all_tasks,
+          const std::set<std::shared_ptr<Task>>& all_tasks,
           bool dryrun)
 {
 	bool task_found{false};
-	std::list<std::shared_ptr<Task>> ts;
+	std::set<std::shared_ptr<Task>> ts;
 
 	for(const auto& target : targets)
 	{
@@ -218,7 +219,7 @@ int build(const Settings& settings,
 				auto depSet = getDepTasks(task);
 				for(const auto& task : depSet)
 				{
-					ts.push_back(task);
+					ts.insert(task);
 				}
 			}
 		}
diff --git a/src/build.h b/src/build.h
index 7be7517..f3a1419 100644
--- a/src/build.h
+++ b/src/build.h
@@ -4,7 +4,7 @@
 #pragma once
 
 #include <string>
-#include <list>
+#include <set>
 #include <memory>
 
 #include "task.h"
@@ -14,19 +14,19 @@
 //! Dry-run returns number of dirty tasks but otherwise does nothing.
 int build(const Settings& settings,
           const std::string& name,
-          const std::list<std::shared_ptr<Task>>& tasks,
-          const std::list<std::shared_ptr<Task>>& all_tasks,
+          const std::set<std::shared_ptr<Task>>& tasks,
+          const std::set<std::shared_ptr<Task>>& all_tasks,
           bool dryrun = false);
 
 //! Dry-run returns number of dirty tasks but otherwise does nothing.
 int build(const Settings& settings,
           const std::string& name,
-          const std::list<std::shared_ptr<Task>>& all_tasks,
+          const std::set<std::shared_ptr<Task>>& all_tasks,
           bool dryrun = false);
 
 //! Dry-run returns number of dirty tasks but otherwise does nothing.
 int build(const Settings& settings,
           const std::string& name,
           const std::vector<Target>& targets,
-          const std::list<std::shared_ptr<Task>>& all_tasks,
+          const std::set<std::shared_ptr<Task>>& all_tasks,
           bool dryrun = false);
diff --git a/src/task.cc b/src/task.cc
index 8a9eefa..b8fce06 100644
--- a/src/task.cc
+++ b/src/task.cc
@@ -12,7 +12,7 @@ Task::Task(const BuildConfiguration& config)
 {
 }
 
-int Task::registerDepTasks(const std::list<std::shared_ptr<Task>>& tasks)
+int Task::registerDepTasks(const std::set<std::shared_ptr<Task>>& tasks)
 {
 	for(const auto& depStr : depends())
 	{
@@ -21,7 +21,7 @@ int Task::registerDepTasks(const std::list<std::shared_ptr<Task>>& tasks)
 		{
 			if(task->target() == depStr)
 			{
-				dependsTasks.push_back(task);
+				dependsTasks.insert(task);
 				found = true;
 			}
 		}
@@ -146,7 +146,7 @@ std::string Task::compiler() const
 	}
 }
 
-std::list<std::shared_ptr<Task>> Task::getDependsTasks()
+std::set<std::shared_ptr<Task>> Task::getDependsTasks()
 {
 	return dependsTasks;
 }
diff --git a/src/task.h b/src/task.h
index 4cbd126..47f4d1b 100644
--- a/src/task.h
+++ b/src/task.h
@@ -6,7 +6,7 @@
 #include <vector>
 #include <string>
 #include <atomic>
-#include <list>
+#include <set>
 #include <memory>
 
 #include "libctor.h"
@@ -25,7 +25,7 @@ class Task
 public:
 	Task(const BuildConfiguration& config);
 
-	int registerDepTasks(const std::list<std::shared_ptr<Task>>& tasks);
+	int registerDepTasks(const std::set<std::shared_ptr<Task>>& tasks);
 
 	virtual std::string name() const;
 	bool dirty();
@@ -52,7 +52,7 @@ public:
 	OutputSystem outputSystem() const;
 	std::string compiler() const;
 
-	std::list<std::shared_ptr<Task>> getDependsTasks();
+	std::set<std::shared_ptr<Task>> getDependsTasks();
 
 	virtual std::string source() const { return {}; }
 
@@ -62,7 +62,7 @@ protected:
 	virtual bool dirtyInner() { return false; }
 
 	std::vector<std::string> dependsStr;
-	std::list<std::shared_ptr<Task>> dependsTasks;
+	std::set<std::shared_ptr<Task>> dependsTasks;
 	const BuildConfiguration& config;
 	TargetType target_type{TargetType::Auto};
 	Language source_language{Language::Auto};
diff --git a/src/tasks.cc b/src/tasks.cc
index 8ab296f..8bb8de6 100644
--- a/src/tasks.cc
+++ b/src/tasks.cc
@@ -5,6 +5,7 @@
 
 #include <filesystem>
 #include <deque>
+#include <list>
 #include <iostream>
 #include <algorithm>
 
@@ -76,9 +77,9 @@ const std::deque<Target>& getTargets(const Settings& settings,
 	return targets;
 }
 
-std::list<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
-                                             const Settings& settings,
-                                             const std::string& sourceDir)
+std::set<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
+                                            const Settings& settings,
+                                            const std::string& sourceDir)
 {
 	std::filesystem::path targetFile(config.target);
 
@@ -106,12 +107,12 @@ std::list<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
 	}
 
 	std::vector<std::string> objects;
-	std::list<std::shared_ptr<Task>> tasks;
+	std::set<std::shared_ptr<Task>> tasks;
 	for(const auto& file : config.sources)
 	{
-		tasks.emplace_back(std::make_shared<TaskCC>(config, settings,
-		                                            sourceDir, file));
-		objects.push_back(tasks.back()->target());
+		auto task = std::make_shared<TaskCC>(config, settings, sourceDir, file);
+		tasks.insert(task);
+		objects.push_back(task->target());
 	}
 
 	switch(target_type)
@@ -121,8 +122,8 @@ std::list<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
 		break;
 
 	case TargetType::StaticLibrary:
-		tasks.emplace_back(std::make_shared<TaskAR>(config, settings, config.target,
-		                                            objects, sourceDir));
+		tasks.insert(std::make_shared<TaskAR>(config, settings, config.target,
+		                                      objects, sourceDir));
 		break;
 #ifndef BOOTSTRAP
 	case TargetType::DynamicLibrary:
@@ -132,14 +133,14 @@ std::list<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
 			std::cerr << "Dynamic library target must have 'lib' prefix\n";
 			exit(1);
 		}
-		tasks.emplace_back(std::make_shared<TaskSO>(config, settings, config.target,
-		                                            objects, sourceDir));
+		tasks.insert(std::make_shared<TaskSO>(config, settings, config.target,
+		                                      objects, sourceDir));
 		break;
 
 	case TargetType::Executable:
 	case TargetType::UnitTest:
-		tasks.emplace_back(std::make_shared<TaskLD>(config, settings, config.target,
-		                                            objects, sourceDir));
+		tasks.insert(std::make_shared<TaskLD>(config, settings, config.target,
+		                                      objects, sourceDir));
 		break;
 
 	case TargetType::Object:
@@ -153,8 +154,8 @@ std::list<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
 	return tasks;
 }
 
-std::shared_ptr<Task> getNextTask(const std::list<std::shared_ptr<Task>>& allTasks,
-                                  std::list<std::shared_ptr<Task>>& dirtyTasks)
+std::shared_ptr<Task> getNextTask(const std::set<std::shared_ptr<Task>>& allTasks,
+                                  std::set<std::shared_ptr<Task>>& dirtyTasks)
 {
 	for(auto dirtyTask = dirtyTasks.begin();
 	    dirtyTask != dirtyTasks.end();
@@ -172,12 +173,12 @@ std::shared_ptr<Task> getNextTask(const std::list<std::shared_ptr<Task>>& allTas
 	return nullptr;
 }
 
-std::list<std::shared_ptr<Task>> getTasks(const Settings& settings,
-                                          const std::vector<std::string> names,
-                                          bool resolve_externals)
+std::set<std::shared_ptr<Task>> getTasks(const Settings& settings,
+                                         const std::vector<std::string> names,
+                                         bool resolve_externals)
 {
 	auto& targets = getTargets(settings, resolve_externals);
-	std::list<std::shared_ptr<Task>> tasks;
+	std::set<std::shared_ptr<Task>> tasks;
 	for(const auto& target : targets)
 	{
 		if(names.empty() ||
@@ -185,7 +186,7 @@ std::list<std::shared_ptr<Task>> getTasks(const Settings& settings,
 		{
 			std::vector<std::string> objects;
 			auto t = taskFactory(target.config, settings, target.path);
-			tasks.insert(tasks.end(), t.begin(), t.end());
+			tasks.insert(t.begin(), t.end());
 		}
 	}
 
diff --git a/src/tasks.h b/src/tasks.h
index f2a77d4..c547432 100644
--- a/src/tasks.h
+++ b/src/tasks.h
@@ -4,7 +4,7 @@
 #pragma once
 
 #include <string>
-#include <list>
+#include <set>
 #include <memory>
 #include <deque>
 
@@ -27,17 +27,17 @@ const std::deque<Target>& getTargets(const Settings& settings,
 //! fulfilled.
 //! The returned task is removed from the dirty list.
 //! Return nullptr if no dirty task is ready.
-std::shared_ptr<Task> getNextTask(const std::list<std::shared_ptr<Task>>& allTasks,
-                                  std::list<std::shared_ptr<Task>>& dirtyTasks);
+std::shared_ptr<Task> getNextTask(const std::set<std::shared_ptr<Task>>& allTasks,
+                                  std::set<std::shared_ptr<Task>>& dirtyTasks);
 
 //! Get list of tasks filtered by name including each of their direct
 //! dependency tasks (ie. objects tasks from their sources).
-std::list<std::shared_ptr<Task>> getTasks(const Settings& settings,
-                                          const std::vector<std::string> names = {},
-                                          bool resolve_externals = true);
+std::set<std::shared_ptr<Task>> getTasks(const Settings& settings,
+                                         const std::vector<std::string> names = {},
+                                         bool resolve_externals = true);
 
 //! Generate list of targets from a single configuration, including the final
 //! link target and all its objects files (if any).
-std::list<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
-                                             const Settings& settings,
-                                             const std::string& sourceDir);
+std::set<std::shared_ptr<Task>> taskFactory(const BuildConfiguration& config,
+                                            const Settings& settings,
+                                            const std::string& sourceDir);
diff --git a/src/unittest.cc b/src/unittest.cc
index ade2d0a..d02e4f2 100644
--- a/src/unittest.cc
+++ b/src/unittest.cc
@@ -9,7 +9,7 @@
 #include "settings.h"
 #include "task.h"
 
-int runUnitTests(std::list<std::shared_ptr<Task>>& tasks,
+int runUnitTests(std::set<std::shared_ptr<Task>>& tasks,
                  const Settings& settings)
 {
 	bool ok{true};
diff --git a/src/unittest.h b/src/unittest.h
index 7eef0e2..8dee33c 100644
--- a/src/unittest.h
+++ b/src/unittest.h
@@ -3,11 +3,11 @@
 // See accompanying file LICENSE for details.
 #pragma once
 
-#include <list>
+#include <set>
 #include <memory>
 
 class Task;
 class Settings;
 
-int runUnitTests(std::list<std::shared_ptr<Task>>& tasks,
+int runUnitTests(std::set<std::shared_ptr<Task>>& tasks,
                  const Settings& settings);
diff --git a/test/tasks_test.cc b/test/tasks_test.cc
index 8a15fcd..0eac0a0 100644
--- a/test/tasks_test.cc
+++ b/test/tasks_test.cc
@@ -37,6 +37,19 @@ BuildConfigurations ctorTestConfigs2()
 REG(ctorTestConfigs1);
 REG(ctorTestConfigs2);
 
+std::size_t count(const std::set<std::shared_ptr<Task>>& tasks,
+                  const std::string& name)
+{
+	auto cnt{0u};
+	for(const auto& task : tasks)
+	{
+		if(task->target() == name)
+		{
+			cnt++;
+		}
+	}
+	return cnt;
+}
 
 class TestTask
 	: public Task
@@ -100,30 +113,22 @@ public:
 		{
 			auto tasks = getTasks(settings);
 			uASSERT_EQUAL(6u, tasks.size());
-			auto task = tasks.begin();
-			uASSERT_EQUAL("foo/test/target1-foo_cc.o"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target1-bar_c.o"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target1"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target2"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target3"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target4"s, (*task)->target());
+			// Note: count() is used here because the order of
+			// std::set<std::shared_ptr<T>> is not deterministic.
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target1"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target2"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target3"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target4"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target1-foo_cc.o"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target1-bar_c.o"s));
 		}
 		{
 			auto tasks = getTasks(settings, {"target1", "target3"});
 			uASSERT_EQUAL(4u, tasks.size());
-			auto task = tasks.begin();
-			uASSERT_EQUAL("foo/test/target1-foo_cc.o"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target1-bar_c.o"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target1"s, (*task)->target());
-			task++;
-			uASSERT_EQUAL("foo/test/target3"s, (*task)->target());
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target1"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target3"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target1-foo_cc.o"s));
+			uASSERT_EQUAL(1u, count(tasks, "foo/test/target1-bar_c.o"s));
 		}
 		{
 			auto tasks = getTasks(settings, {"no-such-target"});
@@ -137,8 +142,8 @@ public:
 		Settings settings{};
 
 		{ // Zero (Empty)
-			std::list<std::shared_ptr<Task>> allTasks;
-			std::list<std::shared_ptr<Task>> dirtyTasks;
+			std::set<std::shared_ptr<Task>> allTasks;
+			std::set<std::shared_ptr<Task>> dirtyTasks;
 
 			for(auto& task : dirtyTasks)
 			{
@@ -151,10 +156,10 @@ public:
 		{ // Zero (One task, no dirty)
 			auto task1 = std::make_shared<TestTask>("task1", false);
 
-			std::list<std::shared_ptr<Task>> allTasks;
-			allTasks.push_back(task1);
+			std::set<std::shared_ptr<Task>> allTasks;
+			allTasks.insert(task1);
 
-			std::list<std::shared_ptr<Task>> dirtyTasks;
+			std::set<std::shared_ptr<Task>> dirtyTasks;
 
 			for(auto& task : dirtyTasks)
 			{
@@ -167,11 +172,11 @@ public:
 		{ // One (One task, one dirty)
 			auto task1 = std::make_shared<TestTask>("task1", true);
 
-			std::list<std::shared_ptr<Task>> allTasks;
-			allTasks.push_back(task1);
+			std::set<std::shared_ptr<Task>> allTasks;
+			allTasks.insert(task1);
 
-			std::list<std::shared_ptr<Task>> dirtyTasks;
-			dirtyTasks.push_back(task1);
+			std::set<std::shared_ptr<Task>> dirtyTasks;
+			dirtyTasks.insert(task1);
 
 			for(auto& task : dirtyTasks)
 			{
@@ -186,12 +191,12 @@ public:
 			auto task1 = std::make_shared<TestTask>("task1", false);
 			auto task2 = std::make_shared<TestTask>("task2", true);
 
-			std::list<std::shared_ptr<Task>> allTasks;
-			allTasks.push_back(task1);
-			allTasks.push_back(task2);
+			std::set<std::shared_ptr<Task>> allTasks;
+			allTasks.insert(task1);
+			allTasks.insert(task2);
 
-			std::list<std::shared_ptr<Task>> dirtyTasks;
-			dirtyTasks.push_back(task2);
+			std::set<std::shared_ptr<Task>> dirtyTasks;
+			dirtyTasks.insert(task2);
 
 			for(auto& task : dirtyTasks)
 			{
@@ -208,12 +213,12 @@ public:
 			std::vector<std::string> deps = {"task1"};
 			auto task2 = std::make_shared<TestTask>("task2", true, deps);
 
-			std::list<std::shared_ptr<Task>> allTasks;
-			allTasks.push_back(task1);
-			allTasks.push_back(task2);
+			std::set<std::shared_ptr<Task>> allTasks;
+			allTasks.insert(task1);
+			allTasks.insert(task2);
 
-			std::list<std::shared_ptr<Task>> dirtyTasks;
-			dirtyTasks.push_back(task2);
+			std::set<std::shared_ptr<Task>> dirtyTasks;
+			dirtyTasks.insert(task2);
 
 			for(auto& task : dirtyTasks)
 			{
@@ -230,13 +235,13 @@ public:
 			std::vector<std::string> deps = {"task1"};
 			auto task2 = std::make_shared<TestTask>("task2", true, deps);
 
-			std::list<std::shared_ptr<Task>> allTasks;
-			allTasks.push_back(task2);
-			allTasks.push_back(task1);
+			std::set<std::shared_ptr<Task>> allTasks;
+			allTasks.insert(task2);
+			allTasks.insert(task1);
 
-			std::list<std::shared_ptr<Task>> dirtyTasks;
-			dirtyTasks.push_back(task2);
-			dirtyTasks.push_back(task1);
+			std::set<std::shared_ptr<Task>> dirtyTasks;
+			dirtyTasks.insert(task2);
+			dirtyTasks.insert(task1);
 
 			for(auto& task : dirtyTasks)
 			{