| 1 | package extension |
| 2 | |
| 3 | import ( |
| 4 | "fmt" |
| 5 | "slices" |
| 6 | "sort" |
| 7 | "strings" |
| 8 | |
| 9 | "reasonix/internal/extensioncontract" |
| 10 | ) |
| 11 | |
| 12 | // ComponentID is the stable identity of one lifecycle component (initially one |
| 13 | // native v2 sidecar runtime package, plus host-owned nodes). |
| 14 | type ComponentID string |
| 15 | |
| 16 | // ComponentState is the fixed lifecycle state machine. |
| 17 | type ComponentState string |
| 18 | |
| 19 | const ( |
| 20 | ComponentInactive ComponentState = "Inactive" |
| 21 | ComponentPreparing ComponentState = "Preparing" |
| 22 | ComponentActive ComponentState = "Active" |
| 23 | ComponentDraining ComponentState = "Draining" |
| 24 | ComponentFailed ComponentState = "Failed" |
| 25 | ) |
| 26 | |
| 27 | // ComponentDescriptor is the immutable description of one component used to |
| 28 | // build the dependency graph. It must not carry live handles. |
| 29 | type ComponentDescriptor struct { |
| 30 | ID ComponentID |
| 31 | Source ContributionSource |
| 32 | Requires []extensioncontract.Requirement |
| 33 | Provides []extensioncontract.Capability |
| 34 | Intercepts []InterceptorPoint |
| 35 | Replaces []Slot |
| 36 | // Priority participates in deterministic activation ordering. |
| 37 | Priority int |
| 38 | // Optional marks the whole component as non-blocking when it cannot activate. |
| 39 | Optional bool |
| 40 | } |
| 41 | |
| 42 | // ComponentEpoch is the dependency identity that forces consumer reload when |
| 43 | // it changes. Fiber UIDs alone are not enough. |
| 44 | type ComponentEpoch struct { |
| 45 | CapabilityKey extensioncontract.CapabilityKey |
| 46 | ProviderComponentID ComponentID |
| 47 | ProviderVersion string |
| 48 | ProviderSchemaHash string |
| 49 | } |
| 50 | |
| 51 | // String returns a stable epoch fingerprint. |
| 52 | func (e ComponentEpoch) String() string { |
| 53 | return fmt.Sprintf("%s|%s|%s|%s", e.CapabilityKey.String(), e.ProviderComponentID, e.ProviderVersion, e.ProviderSchemaHash) |
| 54 | } |
| 55 | |
| 56 | // DependencyGraph is the resolved capability graph for one generation. |
| 57 | type DependencyGraph struct { |
| 58 | Components map[ComponentID]ComponentDescriptor |
| 59 | // Edges maps consumer → providers it depends on. |
| 60 | Edges map[ComponentID][]ComponentID |
| 61 | // Providers maps capability key string → component IDs that provide it. |
| 62 | Providers map[string][]ComponentID |
| 63 | // Diagnostics collects optional-missing and non-fatal notes. |
| 64 | Diagnostics []string |
| 65 | } |
| 66 | |
| 67 | // GraphError is a hard dependency resolution failure. |
| 68 | type GraphError struct { |
| 69 | Reason string |
| 70 | Cycle []ComponentID |
| 71 | Detail string |
| 72 | } |
| 73 | |
| 74 | func (e *GraphError) Error() string { |
| 75 | if e == nil { |
| 76 | return "" |
| 77 | } |
| 78 | if len(e.Cycle) > 0 { |
| 79 | parts := make([]string, len(e.Cycle)) |
| 80 | for i, id := range e.Cycle { |
| 81 | parts[i] = string(id) |
| 82 | } |
| 83 | return fmt.Sprintf("extension: %s: %s", e.Reason, strings.Join(parts, " -> ")) |
| 84 | } |
| 85 | if e.Detail != "" { |
| 86 | return fmt.Sprintf("extension: %s: %s", e.Reason, e.Detail) |
| 87 | } |
| 88 | return "extension: " + e.Reason |
| 89 | } |
| 90 | |
| 91 | // BuildDependencyGraph validates descriptors, resolves requirements, detects |
| 92 | // required cycles, and records optional-missing diagnostics. |
| 93 | func BuildDependencyGraph(components []ComponentDescriptor) (*DependencyGraph, error) { |
| 94 | g := &DependencyGraph{ |
| 95 | Components: make(map[ComponentID]ComponentDescriptor, len(components)), |
| 96 | Edges: make(map[ComponentID][]ComponentID), |
| 97 | Providers: make(map[string][]ComponentID), |
| 98 | } |
| 99 | for _, c := range components { |
| 100 | if c.ID == "" { |
| 101 | return nil, &GraphError{Reason: "invalid_component", Detail: "empty component id"} |
| 102 | } |
| 103 | if _, dup := g.Components[c.ID]; dup { |
| 104 | return nil, &GraphError{Reason: "duplicate_component", Detail: string(c.ID)} |
| 105 | } |
| 106 | for _, p := range c.Provides { |
| 107 | if err := p.Validate(); err != nil { |
| 108 | return nil, &GraphError{Reason: "invalid_capability", Detail: err.Error()} |
| 109 | } |
| 110 | key := p.Key.String() |
| 111 | g.Providers[key] = append(g.Providers[key], c.ID) |
| 112 | } |
| 113 | for _, r := range c.Requires { |
| 114 | if err := r.Validate(); err != nil { |
| 115 | return nil, &GraphError{Reason: "invalid_requirement", Detail: err.Error()} |
| 116 | } |
| 117 | } |
| 118 | g.Components[c.ID] = c |
| 119 | } |
| 120 | |
| 121 | // Sort provider lists for determinism. |
| 122 | for k, ids := range g.Providers { |
| 123 | slices.Sort(ids) |
| 124 | g.Providers[k] = ids |
| 125 | } |
| 126 | |
| 127 | for _, c := range components { |
| 128 | for _, req := range c.Requires { |
| 129 | key := req.Key.String() |
| 130 | candidates := g.Providers[key] |
| 131 | var matched []ComponentID |
| 132 | for _, pid := range candidates { |
| 133 | prov := g.Components[pid] |
| 134 | if slices.ContainsFunc(prov.Provides, func(cap extensioncontract.Capability) bool { |
| 135 | return req.SatisfiedBy(cap) |
| 136 | }) { |
| 137 | matched = append(matched, pid) |
| 138 | } |
| 139 | } |
| 140 | if len(matched) == 0 { |
| 141 | if req.Optional { |
| 142 | g.Diagnostics = append(g.Diagnostics, fmt.Sprintf("optional dependency unsatisfied: %s requires %s", c.ID, key)) |
| 143 | continue |
| 144 | } |
| 145 | return nil, &GraphError{ |
| 146 | Reason: "dependency_unsatisfied", |
| 147 | Detail: fmt.Sprintf("%s requires %s", c.ID, key), |
| 148 | } |
| 149 | } |
| 150 | if len(matched) > 1 { |
| 151 | // Multiple providers for the same key without explicit selection. |
| 152 | parts := make([]string, len(matched)) |
| 153 | for i, id := range matched { |
| 154 | parts[i] = string(id) |
| 155 | } |
| 156 | return nil, &GraphError{ |
| 157 | Reason: "duplicate_provider", |
| 158 | Detail: fmt.Sprintf("%s: providers %s", key, strings.Join(parts, ", ")), |
| 159 | } |
| 160 | } |
| 161 | g.Edges[c.ID] = append(g.Edges[c.ID], matched[0]) |
| 162 | } |
| 163 | // Deterministic edge order. |
| 164 | if edges := g.Edges[c.ID]; len(edges) > 1 { |
| 165 | slices.Sort(edges) |
| 166 | g.Edges[c.ID] = edges |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | if cycle := detectRequiredCycle(g); len(cycle) > 0 { |
| 171 | return nil, &GraphError{Reason: "dependency_cycle", Cycle: cycle} |
| 172 | } |
| 173 | slices.Sort(g.Diagnostics) |
| 174 | return g, nil |
| 175 | } |
| 176 | |
| 177 | // ActivateOrder returns the deterministic topological activation order. |
| 178 | func (g *DependencyGraph) ActivateOrder() []ComponentID { |
| 179 | if g == nil { |
| 180 | return nil |
| 181 | } |
| 182 | return topoOrder(g, false) |
| 183 | } |
| 184 | |
| 185 | // DrainOrder returns reverse topological order for draining. |
| 186 | func (g *DependencyGraph) DrainOrder() []ComponentID { |
| 187 | if g == nil { |
| 188 | return nil |
| 189 | } |
| 190 | return topoOrder(g, true) |
| 191 | } |
| 192 | |
| 193 | // EpochFor returns the epoch identity a consumer should pin for req. |
| 194 | func (g *DependencyGraph) EpochFor(consumer ComponentID, req extensioncontract.Requirement) (ComponentEpoch, bool) { |
| 195 | if g == nil { |
| 196 | return ComponentEpoch{}, false |
| 197 | } |
| 198 | for _, pid := range g.Edges[consumer] { |
| 199 | prov := g.Components[pid] |
| 200 | for _, cap := range prov.Provides { |
| 201 | if req.SatisfiedBy(cap) { |
| 202 | return ComponentEpoch{ |
| 203 | CapabilityKey: cap.Key, |
| 204 | ProviderComponentID: pid, |
| 205 | ProviderVersion: cap.Version, |
| 206 | ProviderSchemaHash: cap.SchemaHash, |
| 207 | }, true |
| 208 | } |
| 209 | } |
| 210 | } |
| 211 | return ComponentEpoch{}, false |
| 212 | } |
| 213 | |
| 214 | func detectRequiredCycle(g *DependencyGraph) []ComponentID { |
| 215 | const ( |
| 216 | white = 0 |
| 217 | gray = 1 |
| 218 | black = 2 |
| 219 | ) |
| 220 | color := make(map[ComponentID]int, len(g.Components)) |
| 221 | var stack []ComponentID |
| 222 | var cycle []ComponentID |
| 223 | |
| 224 | var dfs func(ComponentID) bool |
| 225 | dfs = func(n ComponentID) bool { |
| 226 | color[n] = gray |
| 227 | stack = append(stack, n) |
| 228 | for _, m := range g.Edges[n] { |
| 229 | switch color[m] { |
| 230 | case gray: |
| 231 | // Extract cycle from stack. |
| 232 | for _, id := range slices.Backward(stack) { |
| 233 | cycle = append([]ComponentID{id}, cycle...) |
| 234 | if id == m { |
| 235 | break |
| 236 | } |
| 237 | } |
| 238 | cycle = append(cycle, m) |
| 239 | return true |
| 240 | case white: |
| 241 | if dfs(m) { |
| 242 | return true |
| 243 | } |
| 244 | } |
| 245 | } |
| 246 | stack = stack[:len(stack)-1] |
| 247 | color[n] = black |
| 248 | return false |
| 249 | } |
| 250 | |
| 251 | ids := make([]ComponentID, 0, len(g.Components)) |
| 252 | for id := range g.Components { |
| 253 | ids = append(ids, id) |
| 254 | } |
| 255 | slices.Sort(ids) |
| 256 | for _, id := range ids { |
| 257 | if color[id] == white { |
| 258 | if dfs(id) { |
| 259 | return cycle |
| 260 | } |
| 261 | } |
| 262 | } |
| 263 | return nil |
| 264 | } |
| 265 | |
| 266 | func topoOrder(g *DependencyGraph, reverse bool) []ComponentID { |
| 267 | // Kahn's algorithm with deterministic ready-set ordering. |
| 268 | indeg := make(map[ComponentID]int, len(g.Components)) |
| 269 | // Build reverse adjacency: provider → consumers (activation needs providers first). |
| 270 | // Edges are consumer → provider, so provider must activate before consumer. |
| 271 | consumersOf := make(map[ComponentID][]ComponentID) |
| 272 | for id := range g.Components { |
| 273 | indeg[id] = 0 |
| 274 | } |
| 275 | for consumer, providers := range g.Edges { |
| 276 | indeg[consumer] = len(providers) |
| 277 | for _, p := range providers { |
| 278 | consumersOf[p] = append(consumersOf[p], consumer) |
| 279 | } |
| 280 | } |
| 281 | for p, list := range consumersOf { |
| 282 | slices.Sort(list) |
| 283 | consumersOf[p] = list |
| 284 | } |
| 285 | |
| 286 | var ready []ComponentID |
| 287 | for id, d := range indeg { |
| 288 | if d == 0 { |
| 289 | ready = append(ready, id) |
| 290 | } |
| 291 | } |
| 292 | sortReady := func() { |
| 293 | sort.SliceStable(ready, func(i, j int) bool { |
| 294 | return componentLess(g, ready[i], ready[j]) |
| 295 | }) |
| 296 | } |
| 297 | sortReady() |
| 298 | |
| 299 | var order []ComponentID |
| 300 | for len(ready) > 0 { |
| 301 | n := ready[0] |
| 302 | ready = ready[1:] |
| 303 | order = append(order, n) |
| 304 | for _, c := range consumersOf[n] { |
| 305 | indeg[c]-- |
| 306 | if indeg[c] == 0 { |
| 307 | ready = append(ready, c) |
| 308 | sortReady() |
| 309 | } |
| 310 | } |
| 311 | } |
| 312 | if reverse { |
| 313 | for i, j := 0, len(order)-1; i < j; i, j = i+1, j-1 { |
| 314 | order[i], order[j] = order[j], order[i] |
| 315 | } |
| 316 | } |
| 317 | return order |
| 318 | } |
| 319 | |
| 320 | // componentLess implements the fixed sort: dependency rank, scope rank, |
| 321 | // priority, canonical component ID. Dependency rank is approximated by |
| 322 | // number of transitive providers (deeper deps first in activation). |
| 323 | func componentLess(g *DependencyGraph, a, b ComponentID) bool { |
| 324 | ra, rb := dependencyRank(g, a), dependencyRank(g, b) |
| 325 | if ra != rb { |
| 326 | return ra < rb |
| 327 | } |
| 328 | sa, sb := tierRank(g.Components[a].Source.Scope), tierRank(g.Components[b].Source.Scope) |
| 329 | if sa != sb { |
| 330 | // Higher scope rank first so project-owned nodes win ties predictably. |
| 331 | return sa > sb |
| 332 | } |
| 333 | pa, pb := g.Components[a].Priority, g.Components[b].Priority |
| 334 | if pa != pb { |
| 335 | return pa > pb |
| 336 | } |
| 337 | return a < b |
| 338 | } |
| 339 | |
| 340 | func dependencyRank(g *DependencyGraph, id ComponentID) int { |
| 341 | seen := map[ComponentID]bool{} |
| 342 | var walk func(ComponentID) int |
| 343 | walk = func(n ComponentID) int { |
| 344 | if seen[n] { |
| 345 | return 0 |
| 346 | } |
| 347 | seen[n] = true |
| 348 | max := 0 |
| 349 | for _, p := range g.Edges[n] { |
| 350 | if d := walk(p) + 1; d > max { |
| 351 | max = d |
| 352 | } |
| 353 | } |
| 354 | return max |
| 355 | } |
| 356 | return walk(id) |
| 357 | } |
| 358 |