func ResolveRepoDeps()

in newt/deprepo/deprepo.go [212:350]
99 lines of code
14 McCabe index (conditional complexity)

func ResolveRepoDeps(dg DepGraph) (VersionMap, []Conflict) {
	// Represents an entry in the working set.
	type WSNode struct {
		highPrio  bool   // If true, always "wins" without conflict.
		dependent RVPair // Repo that expresses this dependency.
		dependee  RVPair // Repo that is depended on.
	}

	ws := map[string]WSNode{}        // Working set (key=dependent).
	cm := map[string]*Conflict{}     // Conflict map (key=dependee).
	visited := map[string]struct{}{} // Tracks which nodes have been visited.

	// Updates (or inserts a new) conflict object into the conflict map (cm).
	addConflict := func(dependent RVPair, dependee RVPair) {
		c := cm[dependee.Name]
		if c == nil {
			wsn := ws[dependee.Name]

			c = &Conflict{
				DependeeName: repoNameString(dependee.Name),
				Entries: []ConflictEntry{
					ConflictEntry{
						Dependent: RVPair{
							Name: repoNameString(wsn.dependent.Name),
							Ver:  wsn.dependent.Ver,
						},
						DependeeVer: wsn.dependee.Ver,
					},
				},
			}
			cm[dependee.Name] = c
		}

		c.Entries = append(c.Entries, ConflictEntry{
			Dependent:   dependent,
			DependeeVer: dependee.Ver,
		})
	}

	// Attempts to add a single node to the working set.  In case of a
	// conflict, the conflict map is updated instead.
	addWsNode := func(dependent RVPair, dependee RVPair) {
		old, ok := ws[dependee.Name]
		if !ok {
			// This is the first time we've seen this repo.
			ws[dependee.Name] = WSNode{
				highPrio:  false,
				dependent: dependent,
				dependee:  dependee,
			}
			return
		}

		if newtutil.CompareRepoVersions(old.dependee.Ver, dependee.Ver) == 0 {
			// We have already seen this exact dependency.  Ignore the
			// duplicate.
			return
		}

		// There is already a dependency for a different version of this repo.
		// Handle the conflict.
		if old.highPrio {
			// Root commit dependencies take priority over all others.
			log.Debugf("discarding repo dependency in favor "+
				"of root override: dep=%s->%s root=%s->%s",
				dependent.String(), dependee.String(),
				old.dependent.String(), old.dependee.String())
		} else {
			addConflict(dependent, dependee)
		}
	}

	// Adds one entry to the working set (ws) for each of the given repo's
	// dependencies.
	visit := func(rvp RVPair) {
		nodes := dg[rvp]
		for _, node := range nodes {
			addWsNode(rvp, node)
		}

		visited[rvp.Name] = struct{}{}
	}

	// Insert all the root dependencies (dependencies in `project.yml`) into
	// the working set.  A root dependency is "high priority" if it points to a
	// git commit rather than a version number.
	rootDeps := dg[RVPair{}]
	for _, dep := range rootDeps {
		ws[dep.Name] = WSNode{
			highPrio:  dep.Ver.Commit != "",
			dependent: RVPair{Name: rootDependencyName},
			dependee:  dep,
		}
	}

	// Repeatedly iterate through the working set, visiting each unvisited
	// node.  Stop looping when an iteration produces no new nodes.
	for len(visited) < len(ws) {
		// Iterate the working set in a consistent order.  The order doesn't
		// matter for well-defined projects.  For invalid projects, different
		// iteration orders can result in different conflicts being reported.
		names := make([]string, 0, len(ws))
		for name, _ := range ws {
			names = append(names, name)
		}
		sort.Strings(names)

		for _, name := range names {
			wsn := ws[name]
			if _, ok := visited[name]; !ok {
				visit(wsn.dependee)
			}
		}
	}

	// It is an error if any conflicts were detected.
	if len(cm) > 0 {
		var cs []Conflict
		for _, c := range cm {
			c.SortEntries()
			cs = append(cs, *c)
		}

		sort.Slice(cs, func(i int, j int) bool {
			return strings.Compare(cs[i].DependeeName, cs[j].DependeeName) < 0
		})

		return nil, cs
	}

	// The working set now contains the target version of each repo in the
	// project.
	vm := VersionMap{}
	for name, wsn := range ws {
		vm[name] = wsn.dependee.Ver
	}

	return vm, nil
}