Resolve circular dependencies

qgis · Dec 5, 2016 · 4c0f4ee · 4c0f4ee
1 parent b065ede
commit 4c0f4ee
Show file tree

Hide file tree

Showing 4 changed files with 107 additions and 5 deletions.
diff --git a/python/core/qgstaskmanager.sip b/python/core/qgstaskmanager.sip
@@ -212,6 +212,13 @@ class QgsTaskManager : QObject
     //! Returns true if all dependencies for the specified task are satisfied
     bool dependenciesSatisified( long taskId ) const;
 
+    //! Returns the set of task IDs on which a task is dependent
+    //! @note not available in Python bindings
+    //QSet< long > dependencies( long taskId ) const;
+
+    //! Will return true if the specified task has circular dependencies
+    bool hasCircularDependencies( long taskId ) const;
+
   signals:
 
     //! Will be emitted when a task reports a progress change

diff --git a/src/core/qgstaskmanager.cpp b/src/core/qgstaskmanager.cpp
@@ -135,6 +135,11 @@ long QgsTaskManager::addTask( QgsTask* task, const QgsTaskList& dependencies )
     mTaskDependencies.insert( mNextTaskId, dependencies );
   }
 
+  if ( hasCircularDependencies( mNextTaskId ) )
+  {
+    task->cancel();
+  }
+
   emit taskAdded( mNextTaskId );
   processQueue();
 
@@ -222,6 +227,55 @@ bool QgsTaskManager::dependenciesSatisified( long taskId ) const
   return true;
 }
 
+QSet<long> QgsTaskManager::dependencies( long taskId ) const
+{
+  QSet<long> results;
+  if ( resolveDependencies( taskId, taskId, results ) )
+    return results;
+  else
+    return QSet<long>();
+}
+
+bool QgsTaskManager::resolveDependencies( long firstTaskId, long currentTaskId, QSet<long>& results ) const
+{
+  if ( !mTaskDependencies.contains( currentTaskId ) )
+    return true;
+
+  Q_FOREACH ( QgsTask* task, mTaskDependencies.value( currentTaskId ) )
+  {
+    long dependentTaskId = taskId( task );
+    if ( dependentTaskId >= 0 )
+    {
+      if ( dependentTaskId == firstTaskId )
+        // circular
+        return false;
+
+      //add task as dependent
+      results.insert( dependentTaskId );
+      //plus all its other dependencies
+      QSet< long > newTaskDeps;
+      if ( !resolveDependencies( firstTaskId, dependentTaskId, newTaskDeps ) )
+        return false;
+
+      if ( newTaskDeps.contains( firstTaskId ) )
+      {
+        // circular
+        return false;
+      }
+
+      results.unite( newTaskDeps );
+    }
+  }
+
+  return true;
+}
+
+bool QgsTaskManager::hasCircularDependencies( long taskId ) const
+{
+  QSet< long > d;
+  return !resolveDependencies( taskId, taskId, d );
+}
+
 void QgsTaskManager::taskProgressChanged( double progress )
 {
   QgsTask* task = qobject_cast< QgsTask* >( sender() );

diff --git a/src/core/qgstaskmanager.h b/src/core/qgstaskmanager.h
@@ -243,6 +243,13 @@ class CORE_EXPORT QgsTaskManager : public QObject
     //! Returns true if all dependencies for the specified task are satisfied
     bool dependenciesSatisified( long taskId ) const;
 
+    //! Returns the set of task IDs on which a task is dependent
+    //! @note not available in Python bindings
+    QSet< long > dependencies( long taskId ) const;
+
+    //! Will return true if the specified task has circular dependencies
+    bool hasCircularDependencies( long taskId ) const;
+
   signals:
 
     //! Will be emitted when a task reports a progress change
@@ -298,6 +305,8 @@ class CORE_EXPORT QgsTaskManager : public QObject
     //! which are dependent on
     void cancelDependentTasks( long taskId );
 
+    bool resolveDependencies( long firstTaskId, long currentTaskId, QSet< long >& results ) const;
+
 };
 
 #endif //QGSTASKMANAGER_H
diff --git a/tests/src/core/testqgstaskmanager.cpp b/tests/src/core/testqgstaskmanager.cpp
@@ -373,9 +373,18 @@ void TestQgsTaskManager::dependancies()
   TestTask* grandChildTask = new TestTask();
   grandChildTask->hold();
 
-  manager.addTask( task, QgsTaskList() << childTask );
-  manager.addTask( childTask, QgsTaskList() << grandChildTask );
-  manager.addTask( grandChildTask );
+  long taskId = manager.addTask( task, QgsTaskList() << childTask );
+  long childTaskId = manager.addTask( childTask, QgsTaskList() << grandChildTask );
+  long grandChildTaskId = manager.addTask( grandChildTask );
+
+  // check dependency resolution
+  QCOMPARE( manager.dependencies( grandChildTaskId ), QSet< long >() );
+  QCOMPARE( manager.dependencies( childTaskId ), QSet< long >() << grandChildTaskId );
+  QCOMPARE( manager.dependencies( taskId ), QSet< long >() << childTaskId << grandChildTaskId );
+
+  QVERIFY( !manager.hasCircularDependencies( taskId ) );
+  QVERIFY( !manager.hasCircularDependencies( childTaskId ) );
+  QVERIFY( !manager.hasCircularDependencies( grandChildTaskId ) );
 
   grandChildTask->cancel();
   QCOMPARE( childTask->status(), QgsTask::Terminated );
@@ -385,8 +394,8 @@ void TestQgsTaskManager::dependancies()
   task = new TestTask();
   childTask = new TestTask();
   childTask->hold();
-  long taskId = manager.addTask( task, QgsTaskList() << childTask );
-  long childTaskId = manager.addTask( childTask );
+  taskId = manager.addTask( task, QgsTaskList() << childTask );
+  childTaskId = manager.addTask( childTask );
   QVERIFY( !manager.dependenciesSatisified( taskId ) );
   QVERIFY( manager.dependenciesSatisified( childTaskId ) );
 
@@ -406,6 +415,29 @@ void TestQgsTaskManager::dependancies()
   //wait for task to spin up
   while ( !task->isActive() ) {}
   QCOMPARE( task->status(), QgsTask::Running );
+  task->emitTaskCompleted();
+
+
+  // test circular dependency detection
+  task = new TestTask();
+  task->hold();
+  childTask = new TestTask();
+  childTask->hold();
+  grandChildTask = new TestTask();
+  grandChildTask->hold();
+
+  taskId = manager.addTask( task, QgsTaskList() << childTask );
+  childTaskId = manager.addTask( childTask, QgsTaskList() << grandChildTask );
+  grandChildTaskId = manager.addTask( grandChildTask, QgsTaskList() << task );
+
+  QVERIFY( manager.hasCircularDependencies( taskId ) );
+  QVERIFY( manager.hasCircularDependencies( childTaskId ) );
+  QVERIFY( manager.hasCircularDependencies( grandChildTaskId ) );
+
+  //expect all these circular tasks to be terminated
+  QCOMPARE( task->status(), QgsTask::Terminated );
+  QCOMPARE( childTask->status(), QgsTask::Terminated );
+  QCOMPARE( grandChildTask->status(), QgsTask::Terminated );
 }