# HG changeset patch
# User Teemu Piippo <teemu.s.piippo@gmail.com>
# Date 1654950024 -10800
# Node ID ee5758ddb6d2bdda0fdd18126125dcf7713b3136
# Parent  27259810da6d1c7a4a11c0b30f9e741ae2f20748
Rewrite prune to use graphs rather than O(n²) searches

diff -r 27259810da6d -r ee5758ddb6d2 src/basics.h
--- a/src/basics.h	Sat Jun 11 14:30:30 2022 +0300
+++ b/src/basics.h	Sat Jun 11 15:20:24 2022 +0300
@@ -20,6 +20,7 @@
 #include <algorithm>
 #include <cmath>
 #include <compare>
+#include <deque>
 #include <memory>
 #include <optional>
 #include <set>
@@ -184,7 +185,7 @@
 struct TypeValue
 {
 	T value;
-	auto operator<=>(TypeValue other) const = default;
+	auto operator<=>(const TypeValue& other) const = default;
 };
 
 template<typename T, typename R>
@@ -323,3 +324,13 @@
 	value += element;
 	return value;
 }
+
+template<typename T>
+struct GraphEdge
+{
+	T from;
+	T to;
+};
+
+template<typename T>
+using Graph = std::deque<GraphEdge<T>>;
diff -r 27259810da6d -r ee5758ddb6d2 src/documentmanager.cpp
--- a/src/documentmanager.cpp	Sat Jun 11 14:30:30 2022 +0300
+++ b/src/documentmanager.cpp	Sat Jun 11 15:20:24 2022 +0300
@@ -20,6 +20,7 @@
 #include <QDir>
 #include <QFileInfo>
 #include <QSaveFile>
+#include <deque>
 #include "documentmanager.h"
 #include "parser.h"
 
@@ -255,51 +256,49 @@
 		.arg(missingString);
 }
 
-/**
- * @brief Cleans up and erases models that are no longer required.
- */
-void DocumentManager::prune()
+template<typename T, typename K>
+void removeFromSet(std::set<T>& set, K&& valueToRemove)
 {
-	for (auto it = this->openModels.begin(); it != this->openModels.end(); ++it)
-	{
-		// Find models that are not edited by the user and are not needed by any other model
-		if (true
-			and it->second.opentype == OpenType::AutomaticallyOpened
-			and not this->isReferencedByAnything(it->first)
-		) {
-			// Remove the model
-			this->openModels.erase(it);
-			// We need to start over now. It is possible that other models that
-			// previously were referenced by the model we just erased have
-			// become prunable. Moreover, our iterator is invalid now and we
-			// cannot continue in this loop.
-			this->prune();
-			break;
-		}
+	const auto it = std::lower_bound(set.begin(), set.end(), valueToRemove);
+	if (it != set.end() and *it == valueToRemove) {
+		set.erase(it);
 	}
 }
 
-/**
- * @brief Finds out whether the specified model id is referenced by any other model
- * @param modelId
- * @returns bool
- */
-bool DocumentManager::isReferencedByAnything(const ModelId modelId) const
+//! @brief Cleans up and erases models that are no longer required.
+void DocumentManager::prune()
 {
-	for (auto& haystackModelPair : this->openModels)
-	{
-		if (haystackModelPair.first != modelId)
-		{
-			for (auto& dependencyPair : haystackModelPair.second.dependencies)
-			{
-				if (dependencyPair.second == modelId)
-				{
-					return true;
-				}
+	Graph<ModelId> dependencyGraph;
+	forValueInMap(this->openModels, [&dependencyGraph](const ModelInfo& info) {
+		forValueInMap(info.dependencies, [&dependencyGraph, &info](ModelId dep){
+			dependencyGraph.push_back({.from = info.id, .to = dep});
+		});
+	});
+	std::set<ModelId> autoOpened;
+	forValueInMap(this->openModels, [&autoOpened](const ModelInfo& info) {
+		if (info.opentype == OpenType::AutomaticallyOpened) {
+			autoOpened.insert(info.id);
+		}
+	});
+	bool repeat = true;
+	while (repeat) {
+		repeat = false;
+		std::set<ModelId> prunable = autoOpened;
+		for (const auto& pair : dependencyGraph) {
+			removeFromSet(prunable, pair.to);
+		}
+		for (ModelId idToPrune : prunable) {
+			auto it = this->openModels.find(idToPrune);
+			if (it != this->openModels.end()) {
+				this->openModels.erase(it);
 			}
+			removeFromSet(autoOpened, idToPrune);
+			std::erase_if(dependencyGraph, [&idToPrune](const GraphEdge<ModelId>& edge) {
+				return edge.from == idToPrune;
+			});
+			repeat = true;
 		}
 	}
-	return false;
 }
 
 void DocumentManager::makePolygonCacheForModel(const ModelId modelId)
diff -r 27259810da6d -r ee5758ddb6d2 src/documentmanager.h
--- a/src/documentmanager.h	Sat Jun 11 14:30:30 2022 +0300
+++ b/src/documentmanager.h	Sat Jun 11 15:20:24 2022 +0300
@@ -65,7 +65,6 @@
 	void collectReferences(QSet<QString> &referenced, const QString& name, const Model* model);
 	void updateDependencies(ModelInfo* model);
 	void prune();
-	bool isReferencedByAnything(const ModelId modelId) const;
 	void makePolygonCacheForModel(const ModelId modelId);
 };