Module: Bosh::Cli::DependencyHelper

Included in:
Command::Release::CreateRelease, ReleaseBuilder, ReleaseTarball
Defined in:
lib/cli/dependency_helper.rb

Instance Method Summary collapse

Instance Method Details

#tsort_packages(map) ⇒ Object

Expects package dependency graph { “A” => [“B”, “C”], “B” => [“C”, “D”] }



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/cli/dependency_helper.rb', line 8

def tsort_packages(map)
  resolved = Set.new
  in_degree = { }
  graph = { }

  map.keys.sort.each do |package|
    dependencies = map[package]
    graph[package] ||= Set.new
    in_degree[package] = dependencies.size

    resolved << package if in_degree[package] == 0

    # Reverse edges to avoid dfs
    dependencies.each do |dependency|
      unless map.has_key?(dependency)
        raise MissingDependency, ("Package '%s' depends on " +
            "missing package '%s'") % [package, dependency]
      end

      graph[dependency] ||= Set.new
      graph[dependency] << package
    end
  end

  sorted = []

  until resolved.empty?
    p = resolved.first
    resolved.delete(p)

    sorted << p

    graph[p].each do |v|
      in_degree[v] -= 1
      resolved << v if in_degree[v] == 0
    end
    graph[p].clear
  end

  # each_pair gives different (correct) results in 1.8 in 1.9,
  # stabilizing for tests
  graph.keys.sort.each do |v|
    e = graph[v]
    unless e.empty?
      raise CircularDependency, ("Cannot resolve dependencies for '%s': " +
          "circular dependency with '%s'") % [v, e.first]
    end
  end

  sorted
end