File size: 4,692 Bytes
1dbc34b | 1 2 3 4 5 6 7 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 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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 | # @automaker/dependency-resolver
Feature dependency resolution using topological sorting.
## Overview
This package provides dependency resolution for AutoMaker features using Kahn's algorithm with priority-aware ordering. It ensures features are executed in the correct order based on their dependencies.
## Installation
```bash
npm install @automaker/dependency-resolver
```
## Exports
### Resolve Dependencies
Order features based on dependencies and priorities.
```typescript
import { resolveDependencies } from '@automaker/dependency-resolver';
import type { Feature } from '@automaker/types';
const features: Feature[] = [
{
id: 'database',
category: 'backend',
description: 'Setup database',
priority: 1,
},
{
id: 'auth',
category: 'backend',
description: 'Add authentication',
dependencies: ['database'],
priority: 2,
},
{
id: 'api',
category: 'backend',
description: 'Create API endpoints',
dependencies: ['auth'],
priority: 3,
},
];
const result = resolveDependencies(features);
console.log(result.orderedFeatures);
// [database, auth, api]
if (result.hasCycle) {
console.error('Circular dependency detected!');
console.error('Features in cycle:', result.cyclicFeatures);
}
```
### Check Dependencies Satisfied
Check if a feature's dependencies are satisfied.
```typescript
import { areDependenciesSatisfied } from '@automaker/dependency-resolver';
const allFeatures: Feature[] = [
{ id: 'database', status: 'completed', ... },
{ id: 'auth', status: 'pending', dependencies: ['database'], ... }
];
const authFeature = allFeatures.find(f => f.id === 'auth');
if (areDependenciesSatisfied(authFeature, allFeatures)) {
console.log('Auth feature is ready to execute');
} else {
console.log('Waiting for dependencies');
}
```
### Get Blocking Dependencies
Get list of incomplete dependencies blocking a feature.
```typescript
import { getBlockingDependencies } from '@automaker/dependency-resolver';
const blocking = getBlockingDependencies(feature, allFeatures);
if (blocking.length > 0) {
console.log(`Feature blocked by: ${blocking.join(', ')}`);
} else {
console.log('No blocking dependencies');
}
```
## Usage Example
```typescript
import {
resolveDependencies,
areDependenciesSatisfied,
getBlockingDependencies,
} from '@automaker/dependency-resolver';
import type { Feature } from '@automaker/types';
async function executeFeatures(features: Feature[]) {
// Resolve dependency order
const { orderedFeatures, hasCycle, cyclicFeatures } = resolveDependencies(features);
if (hasCycle) {
throw new Error(`Circular dependency: ${cyclicFeatures.join(' → ')}`);
}
// Execute in order
for (const feature of orderedFeatures) {
// Check if dependencies are satisfied
if (!areDependenciesSatisfied(feature, features)) {
const blocking = getBlockingDependencies(feature, features);
console.log(`Skipping ${feature.id}, blocked by: ${blocking.join(', ')}`);
continue;
}
// Execute feature
console.log(`Executing: ${feature.id}`);
await executeFeature(feature);
// Mark as completed
feature.status = 'completed';
}
}
```
## Algorithm
### Topological Sort (Kahn's Algorithm)
1. Calculate in-degree for each feature (number of dependencies)
2. Start with features that have no dependencies (in-degree = 0)
3. Process features in priority order
4. Remove processed features from dependency graph
5. Repeat until all features processed or cycle detected
### Priority Handling
- Features with lower priority numbers execute first
- When multiple features have same in-degree, priority determines order
- Features without explicit priority default to lowest priority
### Cycle Detection
- Detects circular dependencies
- Returns affected features in cycle
- Prevents infinite loops in execution
## Return Types
### DependencyResolutionResult
```typescript
interface DependencyResolutionResult {
orderedFeatures: Feature[]; // Features in execution order
hasCycle: boolean; // True if circular dependency detected
cyclicFeatures: string[]; // Feature IDs involved in cycle
}
```
## Edge Cases
### Missing Dependencies
Features with dependencies on non-existent features are treated as if the dependency is satisfied (allows flexibility).
### Self-Dependencies
Features depending on themselves are detected as cycles.
### Empty Dependencies Array
Treated same as no dependencies - feature is ready immediately.
## Dependencies
- `@automaker/types` - Feature type definition
## Used By
- `@automaker/server` - Auto-mode feature execution
- `@automaker/ui` - Board view feature ordering
|