From 6781451ab2e0bda097a699d216c092e6d3842aa1 Mon Sep 17 00:00:00 2001
From: isanae <14251494+isanae@users.noreply.github.com>
Date: Sat, 9 Jan 2021 15:07:20 -0500
Subject: handle cycles by putting parent ids in a set

---
 src/categories.cpp | 18 ++++++++++++++++--
 src/categories.h   |  5 +++--
 src/modinfo.cpp    |  2 +-
 3 files changed, 20 insertions(+), 5 deletions(-)

diff --git a/src/categories.cpp b/src/categories.cpp
index b1e08a3a..7952fed4 100644
--- a/src/categories.cpp
+++ b/src/categories.cpp
@@ -282,9 +282,23 @@ bool CategoryFactory::categoryExists(int id) const
 }
 
 
-bool CategoryFactory::isDecendantOf(int id, int parentID) const
+bool CategoryFactory::isDescendantOf(int id, int parentID) const
 {
+  // handles cycles
+  std::set<int> seen;
+  return isDescendantOfImpl(id, parentID, seen);
+}
+
+bool CategoryFactory::isDescendantOfImpl(
+  int id, int parentID, std::set<int>& seen) const
+{
+  if (!seen.insert(id).second) {
+    log::error("cycle in category: {}", id);
+    return false;
+  }
+
   std::map<int, unsigned int>::const_iterator iter = m_IDMap.find(id);
+
   if (iter != m_IDMap.end()) {
     unsigned int index = iter->second;
     if (m_Categories[index].m_ParentID == 0) {
@@ -292,7 +306,7 @@ bool CategoryFactory::isDecendantOf(int id, int parentID) const
     } else if (m_Categories[index].m_ParentID == parentID) {
       return true;
     } else {
-      return isDecendantOf(m_Categories[index].m_ParentID, parentID);
+      return isDescendantOfImpl(m_Categories[index].m_ParentID, parentID, seen);
     }
   } else {
     log::warn("{} is no valid category id", id);
diff --git a/src/categories.h b/src/categories.h
index e8ec763b..e4a3ede9 100644
--- a/src/categories.h
+++ b/src/categories.h
@@ -124,7 +124,7 @@ public:
    * @param parentID the parent id to test for
    * @return true if id is a child of parentID
    **/
-  bool isDecendantOf(int id, int parentID) const;
+  bool isDescendantOf(int id, int parentID) const;
 
   /**
    * @brief test if the specified category has child categories
@@ -209,7 +209,8 @@ private:
   std::map<int, unsigned int> m_NexusMap;
 
 private:
-
+  // called by isDescendantOf()
+  bool isDescendantOfImpl(int id, int parentID, std::set<int>& seen) const;
 };
 
 
diff --git a/src/modinfo.cpp b/src/modinfo.cpp
index a0382fe8..16fcf93a 100644
--- a/src/modinfo.cpp
+++ b/src/modinfo.cpp
@@ -516,7 +516,7 @@ bool ModInfo::categorySet(int categoryID) const
 {
   for (std::set<int>::const_iterator iter = m_Categories.begin(); iter != m_Categories.end(); ++iter) {
     if ((*iter == categoryID) ||
-        (CategoryFactory::instance().isDecendantOf(*iter, categoryID))) {
+        (CategoryFactory::instance().isDescendantOf(*iter, categoryID))) {
       return true;
     }
   }
-- 
cgit v1.3.1