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 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

(limited to 'src/categories.cpp')

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);
-- 
cgit v1.3.1