File: CriticalBuildPath.swift

package info (click to toggle)
swiftlang 6.0.3-2
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 2,519,992 kB
  • sloc: cpp: 9,107,863; ansic: 2,040,022; asm: 1,135,751; python: 296,500; objc: 82,456; f90: 60,502; lisp: 34,951; pascal: 19,946; sh: 18,133; perl: 7,482; ml: 4,937; javascript: 4,117; makefile: 3,840; awk: 3,535; xml: 914; fortran: 619; cs: 573; ruby: 573
file content (104 lines) | stat: -rw-r--r-- 4,333 bytes parent folder | download
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
// This source file is part of the Swift.org open source project
//
// Copyright 2019 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for Swift project authors

// The Swift package has llbuildSwift as module
#if SWIFT_PACKAGE
import llbuild
import llbuildSwift
#else
import llbuild
#endif

/// Defines the most expensive dependency chain of a build executed by llbuild
/// based on the build database.
public struct CriticalBuildPath {
    /// An element in the chain consisting of the key being built and its result
    public struct Element {
        /// The built key
        public let key: BuildKey
        /// The build result of the built key
        public let result: RuleResult
    }
    /// The overall duration of the path, calculated as the sum of all element's durations
    public let duration: Double
    /// The elements of the chain in order.
    /// Each subsequent element has a dependency on its predecessor.
    public let elements: [Element]
    
    /// The solver is used for the actual calculation and offers access to the caches it builds up
    public final class Solver {
        /// Fast lookup for all keys and their result
        public let keyResultsLookup: IdentifierFactory<BuildDBKeysWithResult.Element>
        /// Fast lookup for all keys without result
        public let keyLookup: IdentifierFactory<BuildKey>
        /// The elements of the underlying, generic implementation of the algorithm
        private let pathElements: [CriticalPath.Element]
        
        /// Initializes a new CriticalBuildPath.Solver with a collection of keys and their results.
        /// This can get very expensive for huge collections as the fast lookups are being built up in here.
        public init<C>(keys: C) where C: Collection, C.Element == BuildDBKeysWithResult.Element {
            // Create infrastructure for mapping between path pointer and keys/results
            let keyResultsLookup = IdentifierFactory(keys)
            self.keyResultsLookup = keyResultsLookup
            let keyLookup = IdentifierFactory(keys.lazy.map({ $0.key }))
            self.keyLookup = keyLookup
            // Create the pointer elements for the algorithm
            self.pathElements = keys.map { element -> CriticalPath.Element in
                let identifier = keyResultsLookup.identifier(element: element)
                let result = element.result
                return .init(identifier: identifier,
                             weight: result.duration,
                             dependencies: result.dependencies.map(keyLookup.identifier(element:)))
            }
        }
        
        /// Executes the actual path solving algorithm and returns the most expensive path.
        public func run() -> CriticalBuildPath {
            let criticalPath = calculateCriticalPath(pathElements)
            // Map back from the pointer elements to the actual elements
            let elements = criticalPath.elements.map { element -> Element in
                let element = keyResultsLookup.element(id: element.identifier)
                return Element(key: element.key, result: element.result)
            }
            return CriticalBuildPath(duration: criticalPath.weight, elements: elements)
        }
    }
}

/// CriticalBuildPath allows iterating over all elements
extension CriticalBuildPath: Collection {
    public typealias Index = Array<Element>.Index
    
    public var startIndex: Index {
        return elements.startIndex
    }
    
    public var endIndex: Index {
        return elements.endIndex
    }
    
    public subscript(position: Index) -> Element {
        return elements[position]
    }
    
    public func index(after i: Index) -> Index {
        return elements.index(after: i)
    }
}

extension CriticalBuildPath.Element: CustomStringConvertible {
    public var description: String {
        return "<Element key=\(key) result=\(result)>"
    }
}

extension CriticalBuildPath: CustomStringConvertible {
    public var description: String {
        return "<CriticalBuildPath duration=\(duration)sec elements=[\n\(elements.map({ "\t" + $0.description }).joined(separator: "\n"))\n])>"
    }
}