Function dependencyIsCircular

src/dependency.cpp:42–82

/////////////////////////////////////////////////////////////////////////// Returns true if the supplied task adds a cycle to the dependency chain.

////////////////////////////////////////////////////////////////////////////////
// Returns true if the supplied task adds a cycle to the dependency chain.
bool dependencyIsCircular(const Task& task) {
  // A new task has no UUID assigned yet, and therefore cannot be part of any
  // dependency chain.
  if (task.has("uuid")) {
    auto task_uuid = task.get("uuid");

    std::stack<Task> s;
    s.push(task);

    std::unordered_set<std::string> visited;
    visited.insert(task_uuid);

    while (!s.empty()) {
      Task& current = s.top();
      auto deps_current = current.getDependencyUUIDs();

      // This is a basic depth first search that always terminates given the
      // fact that we do not visit any task twice
      for (const auto& dep : deps_current) {
        if (Context::getContext().tdb2.get(dep, current)) {
          auto current_uuid = current.get("uuid");

          if (task_uuid == current_uuid) {
            // Cycle found, initial task reached for the second time!
            return true;
          }

          if (visited.find(current_uuid) == visited.end()) {
            // Push the task to the stack, if it has not been processed yet
            s.push(current);
            visited.insert(current_uuid);
          }
        }
      }

      s.pop();
    }
  }

  return false;
}

////////////////////////////////////////////////////////////////////////////////
// Determine whether a dependency chain is being broken, assuming that 'task' is