🔨 TAREA 6: Build Order Calculator¶

Status: ✅ COMPLETE Version: 1.0.0 Coverage Target: >90%

📋 Overview¶

Topological sort-based build order calculator with parallel build optimization, time estimation, and incremental rebuild support.

Purpose: - Calculate optimal module compilation order - Enable parallel builds (maximize CPU utilization) - Estimate build times - Support incremental builds - Generate build scripts (shell, Make, CMake)

🚀 Quick Start¶

#include "build_order.hpp"

using namespace audiolab::hierarchy;

// Create modules
std::map<std::string, ModuleMetadata> modules = /* ... */;
auto graph = DependencyGraph::build_from_modules(modules);

// Calculate build order
BuildOrderCalculator calculator;
BuildConfig config = BuildConfig::parallel(4);  // 4 parallel jobs

auto order_opt = calculator.calculate(modules, graph, config);

if (order_opt) {
    std::cout << order_opt->to_string();
}

🎯 Features¶

1. Topological Sort (Kahn's Algorithm)¶

Complexity: O(V + E)

auto order = calculator.calculate_sequential(modules, graph);
// Returns nullopt if cycles detected

2. Parallel Build Optimization¶

BuildConfig config = BuildConfig::parallel(8);  // 8 jobs
config.optimize_for_time = true;
config.respect_level_boundaries = true;  // L0 before L1, etc.

auto order = calculator.calculate(modules, graph, config);

Output: - Stage 0: A, B (parallel) - Stage 1: C, D (parallel) - Stage 2: E

3. Build Time Estimation¶

// Estimates based on level:
// L0: 5s, L1: 10s, L2: 20s, L3: 30s
// +5s per 10 dependencies

auto& stats = order->statistics;
std::cout << "Sequential: " << stats.estimated_time_sequential << "s\n";
std::cout << "Parallel:   " << stats.estimated_time_parallel << "s\n";
std::cout << "Speedup:    " << stats.parallelization_factor << "x\n";

4. Critical Path Analysis¶

auto critical_path = calculator.find_critical_path(modules, graph);
// Returns longest dependency chain

5. Incremental Builds¶

IncrementalBuildCalculator inc_calculator;
std::set<std::string> changed{"ModuleA", "ModuleB"};

// Find all modules that need rebuilding
auto rebuild_set = inc_calculator.calculate_rebuild_set(changed, graph);

// Calculate build order for incremental rebuild
auto inc_order = inc_calculator.calculate_incremental_order(changed, modules, graph);

6. Build Script Generation¶

// Shell script
std::string script = BuildScriptGenerator::generate_shell_script(order);

// Makefile
std::string makefile = BuildScriptGenerator::generate_makefile(order, modules);

// CMake
std::string cmake = BuildScriptGenerator::generate_cmake_target(order);

// JSON manifest
std::string json = BuildScriptGenerator::generate_json_manifest(order);

📊 Build Statistics¶

struct BuildStats {
    size_t total_modules;
    size_t total_dependencies;
    size_t critical_path_length;         // Longest chain
    size_t max_parallelism;              // Max modules in parallel
    double estimated_time_sequential;    // Sequential build time
    double estimated_time_parallel;      // Parallel build time
    double parallelization_factor;       // Speedup (seq/par)
};

🧪 Testing¶

ctest -R test_build_order -V

Coverage: >90% Test Cases: 30+

📚 API Reference¶

BuildOrderCalculator¶

class BuildOrderCalculator {
public:
    std::optional<BuildOrder> calculate(...);
    std::optional<std::vector<std::string>> calculate_sequential(...);
    bool is_buildable(const DependencyGraph& graph);
    std::vector<std::string> find_critical_path(...);
};

BuildConfig¶

struct BuildConfig {
    size_t max_parallel_jobs = 1;
    bool optimize_for_time = true;
    bool respect_level_boundaries = true;

    static BuildConfig sequential();     // 1 job
    static BuildConfig parallel(size_t jobs = 4);
};

BuildOrder¶

struct BuildOrder {
    std::vector<std::string> sequential_order;
    std::vector<BuildStage> parallel_stages;
    BuildStats statistics;
    BuildConfig config;

    std::string to_string() const;
    std::string to_makefile(const std::string& cmd = "make") const;
    std::string to_cmake() const;
};

🔗 Dependencies¶

05_01_00_level_definitions (TAREA 1)
05_01_02_validation_engine (TAREA 3)
C++20 compiler
Catch2 v3 (testing)

✅ Success Criteria¶

Status: ✅ COMPLETE Version: 1.0.0 Last Updated: 2025-10-10