func()

in pkg/task/taskset.go [157:243]
71 lines of code
15 McCabe index (conditional complexity)

func (s *TaskSet) sortTaskGraph() *sortTaskResult {
	// To check if there were no cyclic task path or missing inputs,
	// perform the topological sorting algorithm known as Kahn's algorithm
	// Reference: https://en.wikipedia.org/wiki/Topological_sorting
	nonResolvedTasksMap := map[string]UntypedTask{}
	currentMissingTaskDependencies := map[string]map[string]interface{}{}
	currentMissingTaskSourceCount := map[string]int{}
	taskCount := 0

	// Initialize currentMissingTaskDependencies and currentMissingTaskSourceCount for all tasks.
	for _, task := range s.tasks {
		taskID := task.UntypedID()

		sourceCount := 0
		missingDependencies := map[string]interface{}{}
		for _, dependency := range task.Dependencies() {
			if _, found := missingDependencies[dependency.ReferenceIDString()]; !found {
				missingDependencies[dependency.ReferenceIDString()] = struct{}{}
				sourceCount += 1
			}
		}
		currentMissingTaskDependencies[taskID.String()] = missingDependencies
		nonResolvedTasksMap[taskID.String()] = task
		currentMissingTaskSourceCount[taskID.String()] = sourceCount
		taskCount += 1
	}

	topologicalSortedTasks := []UntypedTask{}
	for i := 0; i < taskCount; i++ {
		var nextTaskID string = "N/A"
		for _, taskId := range sortedMapKeys(nonResolvedTasksMap) { // Needs task sorting to get the same result every time.
			if currentMissingTaskSourceCount[taskId] == 0 {
				nextTaskID = taskId
			}
		}

		if nextTaskID != "N/A" {
			nextTask := nonResolvedTasksMap[nextTaskID]
			delete(nonResolvedTasksMap, nextTaskID)
			removingDependencyId := nextTask.UntypedID().ReferenceIDString()
			for taskId := range nonResolvedTasksMap {
				if _, exist := currentMissingTaskDependencies[taskId][removingDependencyId]; exist {
					delete(currentMissingTaskDependencies[taskId], removingDependencyId)
					currentMissingTaskSourceCount[taskId]--
				}
			}
			topologicalSortedTasks = append(topologicalSortedTasks, nextTask)
		} else {
			// Failed to perform topological sort.
			// Gathers the cause of the failure.
			missingTaskIdsInMap := map[string]interface{}{}
			for taskId := range nonResolvedTasksMap {
				for dependency := range currentMissingTaskDependencies[taskId] {
					missingTaskIdsInMap[dependency] = struct{}{}
				}
			}
			for _, task := range nonResolvedTasksMap {
				delete(missingTaskIdsInMap, task.UntypedID().ReferenceIDString())
			}

			missingSources := []taskid.UntypedTaskReference{}
			for source := range missingTaskIdsInMap {
				missingSources = append(missingSources, taskid.NewTaskReference[any](source))
			}

			if len(missingSources) == 0 {
				// If there are no missing dependencies but still can't resolve the graph,
				// it means there is a cyclic dependency
				return getSortTaskResultWithDetailCyclicDependency(nonResolvedTasksMap, currentMissingTaskDependencies, missingSources)
			}

			return &sortTaskResult{
				Runnable:               false,
				TopologicalSortedTasks: nil,
				CyclicDependencyPath:   "",
				MissingDependencies:    missingSources,
			}
		}
	}

	return &sortTaskResult{
		Runnable:               true,
		TopologicalSortedTasks: topologicalSortedTasks,
		MissingDependencies:    []taskid.UntypedTaskReference{},
		CyclicDependencyPath:   "",
	}
}