| 1 | package plancontract |
| 2 | |
| 3 | // Ordered returns the steps in projection order: each phase in |
| 4 | // dependency-respecting declared order, followed by its own sub-steps in the |
| 5 | // same order. Render reads it to keep the approved document deterministic. |
| 6 | func (p Plan) Ordered() []Step { |
| 7 | if len(p.Steps) == 0 { |
| 8 | return nil |
| 9 | } |
| 10 | parents := phaseIDs(p.Steps) |
| 11 | phases := make([]Step, 0, len(p.Steps)) |
| 12 | children := make(map[string][]Step) |
| 13 | for i, s := range p.Steps { |
| 14 | if parents[i] == "" { |
| 15 | phases = append(phases, s) |
| 16 | continue |
| 17 | } |
| 18 | children[parents[i]] = append(children[parents[i]], s) |
| 19 | } |
| 20 | ordered, _ := sortSiblings(phases) |
| 21 | out := make([]Step, 0, len(p.Steps)) |
| 22 | for _, phase := range ordered { |
| 23 | out = append(out, phase) |
| 24 | kids, _ := sortSiblings(children[phase.ID]) |
| 25 | out = append(out, kids...) |
| 26 | } |
| 27 | return out |
| 28 | } |
| 29 | |
| 30 | // phaseIDs resolves each step to the id of the top-level phase it belongs to, |
| 31 | // or "" when the step is a phase itself. No parent, an unknown parent, and a |
| 32 | // parent chain that loops all mean the same thing, and nesting deeper than two |
| 33 | // levels flattens onto the top ancestor. |
| 34 | func phaseIDs(steps []Step) []string { |
| 35 | index := make(map[string]int, len(steps)) |
| 36 | for i, s := range steps { |
| 37 | index[s.ID] = i |
| 38 | } |
| 39 | out := make([]string, len(steps)) |
| 40 | const ( |
| 41 | todo = iota |
| 42 | resolving |
| 43 | done |
| 44 | ) |
| 45 | state := make([]int, len(steps)) |
| 46 | var resolve func(int) string |
| 47 | resolve = func(i int) string { |
| 48 | switch state[i] { |
| 49 | case done: |
| 50 | return out[i] |
| 51 | case resolving: |
| 52 | return "" |
| 53 | } |
| 54 | state[i] = resolving |
| 55 | if parent, ok := index[steps[i].ParentID]; ok && parent != i { |
| 56 | if top := resolve(parent); top != "" { |
| 57 | out[i] = top |
| 58 | } else { |
| 59 | out[i] = steps[parent].ID |
| 60 | } |
| 61 | } |
| 62 | if out[i] == steps[i].ID { |
| 63 | out[i] = "" |
| 64 | } |
| 65 | state[i] = done |
| 66 | return out[i] |
| 67 | } |
| 68 | for i := range steps { |
| 69 | resolve(i) |
| 70 | } |
| 71 | return out |
| 72 | } |
| 73 | |
| 74 | // siblingGroups partitions steps by phase, phases first, so a dependency check |
| 75 | // only ever compares steps that can actually be reordered against each other. |
| 76 | func siblingGroups(steps []Step) [][]Step { |
| 77 | if len(steps) == 0 { |
| 78 | return nil |
| 79 | } |
| 80 | parents := phaseIDs(steps) |
| 81 | phases := make([]Step, 0, len(steps)) |
| 82 | byPhase := make(map[string][]Step) |
| 83 | order := make([]string, 0, len(steps)) |
| 84 | for i, s := range steps { |
| 85 | if parents[i] == "" { |
| 86 | phases = append(phases, s) |
| 87 | continue |
| 88 | } |
| 89 | if _, ok := byPhase[parents[i]]; !ok { |
| 90 | order = append(order, parents[i]) |
| 91 | } |
| 92 | byPhase[parents[i]] = append(byPhase[parents[i]], s) |
| 93 | } |
| 94 | out := make([][]Step, 0, len(order)+1) |
| 95 | out = append(out, phases) |
| 96 | for _, phase := range order { |
| 97 | out = append(out, byPhase[phase]) |
| 98 | } |
| 99 | return out |
| 100 | } |
| 101 | |
| 102 | // sortSiblings orders one phase's steps so a step follows the siblings it |
| 103 | // depends on, breaking ties by declared order. Dependencies outside the sibling |
| 104 | // set are ignored — they cannot order anything here — and a cycle reports |
| 105 | // cyclic while still emitting every step, so ordering never drops work. |
| 106 | func sortSiblings(steps []Step) (ordered []Step, cyclic bool) { |
| 107 | if len(steps) < 2 { |
| 108 | return steps, false |
| 109 | } |
| 110 | index := make(map[string]int, len(steps)) |
| 111 | for i, s := range steps { |
| 112 | index[s.ID] = i |
| 113 | } |
| 114 | deps := make([][]int, len(steps)) |
| 115 | for i, s := range steps { |
| 116 | for _, dep := range s.DependsOn { |
| 117 | if j, ok := index[dep]; ok && j != i { |
| 118 | deps[i] = append(deps[i], j) |
| 119 | } |
| 120 | } |
| 121 | } |
| 122 | done := make([]bool, len(steps)) |
| 123 | out := make([]Step, 0, len(steps)) |
| 124 | for len(out) < len(steps) { |
| 125 | pick := -1 |
| 126 | for i := range steps { |
| 127 | if done[i] || !ready(deps[i], done) { |
| 128 | continue |
| 129 | } |
| 130 | pick = i |
| 131 | break |
| 132 | } |
| 133 | if pick < 0 { |
| 134 | for i := range steps { |
| 135 | if !done[i] { |
| 136 | out = append(out, steps[i]) |
| 137 | } |
| 138 | } |
| 139 | return out, true |
| 140 | } |
| 141 | done[pick] = true |
| 142 | out = append(out, steps[pick]) |
| 143 | } |
| 144 | return out, false |
| 145 | } |
| 146 | |
| 147 | func ready(deps []int, done []bool) bool { |
| 148 | for _, j := range deps { |
| 149 | if !done[j] { |
| 150 | return false |
| 151 | } |
| 152 | } |
| 153 | return true |
| 154 | } |
| 155 |