Class: Rhino::Blueprint::Sorter

Inherits:
Object
  • Object
show all
Defined in:
lib/rhino/blueprint/sorter.rb

Overview

Orders blueprints so that a referenced model’s table is created before any model whose migration adds a foreign key to it (parents before children).

Foreign keys are taken from foreignId columns that carry a foreign_model mapping to another model in the same generation set. References that impose no ordering are ignored:

- self-references (a model's FK to its own table — one migration),
- references to models NOT in this set (e.g. Organization/User, whose
  tables are created by +rhino:install+, not the blueprint run).

Uses Kahn’s algorithm with a stable tie-break: among models with no remaining unmet dependency, the one earliest in the input order wins. The input is already alphabetical (by file name), so the output stays alphabetical wherever relationships don’t force a reorder.

A circular FK dependency (A -> B -> A) has no linear migration order. Such models are emitted in a deterministic best-effort order and reported via #cycles so the caller can warn (one side should be a nullable/deferred FK).

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Sorter

Returns a new instance of Sorter.



28
29
30
 
# File 'lib/rhino/blueprint/sorter.rb', line 28

def initialize
  @cycles = []
end

Instance Attribute Details

#cycles ⇒ Object (readonly)

Model names involved in a circular foreign-key dependency during the last #sort (empty when the dependency graph is acyclic).



26
27
28
 
# File 'lib/rhino/blueprint/sorter.rb', line 26

def cycles
  @cycles
end

Instance Method Details

#sort(blueprints) ⇒ Array<Hash>

Re-order blueprints into a valid migration sequence (parents first).

Parameters:

  • blueprints (Array<Hash>) —

    normalized blueprints (each with a :model name and :columns).

Returns:

  • (Array<Hash>) —

    the blueprints, re-ordered.



37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/rhino/blueprint/sorter.rb', line 37

def sort(blueprints)
  @cycles = []
  return blueprints.dup if blueprints.length < 2

  by_model = {}
  blueprints.each do |bp|
    model = bp[:model]
    by_model[model] ||= bp if model
  end

  dependents = {}
  indegree = {}
  by_model.each_key do |m|
    dependents[m] = []
    indegree[m] = 0
  end

  by_model.each do |model, bp|
    seen = {}
    dependency_models(bp).each do |ref|
      next if ref == model || !by_model.key?(ref) || seen[ref]

      seen[ref] = true
      dependents[ref] << model
      indegree[model] += 1
    end
  end

  input_order = by_model.keys

  # Record the models that actually participate in a cycle (reachable from
  # themselves), in input order, so the caller can warn about the full cycle.
  input_order.each do |model|
    @cycles << model if reachable_from_self?(model, dependents)
  end

  ordered = []
  resolved = {}
  while ordered.length < by_model.length
    # Earliest-input model with all dependencies already emitted...
    pick = input_order.find { |m| !resolved[m] && indegree[m].zero? }
    # ...or, when a cycle blocks the graph, the earliest unresolved model
    # (deterministic cycle-break; the cycle itself is reported via #cycles).
    pick ||= input_order.find { |m| !resolved[m] }

    ordered << by_model[pick]
    resolved[pick] = true
    dependents[pick].each { |child| indegree[child] -= 1 }
  end

  ordered
end