1// Copyright 2019 Google Inc. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package status
16
17import (
18	"time"
19
20	"android/soong/ui/logger"
21)
22
23func NewCriticalPath(log logger.Logger) StatusOutput {
24	return &criticalPath{
25		log:     log,
26		running: make(map[*Action]time.Time),
27		nodes:   make(map[string]*node),
28		clock:   osClock{},
29	}
30}
31
32type criticalPath struct {
33	log logger.Logger
34
35	nodes   map[string]*node
36	running map[*Action]time.Time
37
38	start, end time.Time
39
40	clock clock
41}
42
43type clock interface {
44	Now() time.Time
45}
46
47type osClock struct{}
48
49func (osClock) Now() time.Time { return time.Now() }
50
51// A critical path node stores the critical path (the minimum time to build the node and all of its dependencies given
52// perfect parallelism) for an node.
53type node struct {
54	action             *Action
55	cumulativeDuration time.Duration
56	duration           time.Duration
57	input              *node
58}
59
60func (cp *criticalPath) StartAction(action *Action, counts Counts) {
61	start := cp.clock.Now()
62	if cp.start.IsZero() {
63		cp.start = start
64	}
65	cp.running[action] = start
66}
67
68func (cp *criticalPath) FinishAction(result ActionResult, counts Counts) {
69	if start, ok := cp.running[result.Action]; ok {
70		delete(cp.running, result.Action)
71
72		// Determine the input to this edge with the longest cumulative duration
73		var criticalPathInput *node
74		for _, input := range result.Action.Inputs {
75			if x := cp.nodes[input]; x != nil {
76				if criticalPathInput == nil || x.cumulativeDuration > criticalPathInput.cumulativeDuration {
77					criticalPathInput = x
78				}
79			}
80		}
81
82		end := cp.clock.Now()
83		duration := end.Sub(start)
84
85		cumulativeDuration := duration
86		if criticalPathInput != nil {
87			cumulativeDuration += criticalPathInput.cumulativeDuration
88		}
89
90		node := &node{
91			action:             result.Action,
92			cumulativeDuration: cumulativeDuration,
93			duration:           duration,
94			input:              criticalPathInput,
95		}
96
97		for _, output := range result.Action.Outputs {
98			cp.nodes[output] = node
99		}
100
101		cp.end = end
102	}
103}
104
105func (cp *criticalPath) Flush() {
106	criticalPath := cp.criticalPath()
107
108	if len(criticalPath) > 0 {
109		// Log the critical path to the verbose log
110		criticalTime := criticalPath[0].cumulativeDuration.Round(time.Second)
111		cp.log.Verbosef("critical path took %s", criticalTime.String())
112		if !cp.start.IsZero() {
113			elapsedTime := cp.end.Sub(cp.start).Round(time.Second)
114			cp.log.Verbosef("elapsed time %s", elapsedTime.String())
115			if elapsedTime > 0 {
116				cp.log.Verbosef("perfect parallelism ratio %d%%",
117					int(float64(criticalTime)/float64(elapsedTime)*100))
118			}
119		}
120		cp.log.Verbose("critical path:")
121		for i := len(criticalPath) - 1; i >= 0; i-- {
122			duration := criticalPath[i].duration
123			duration = duration.Round(time.Second)
124			seconds := int(duration.Seconds())
125			cp.log.Verbosef("   %2d:%02d %s",
126				seconds/60, seconds%60, criticalPath[i].action.Description)
127		}
128	}
129}
130
131func (cp *criticalPath) Message(level MsgLevel, msg string) {}
132
133func (cp *criticalPath) Write(p []byte) (n int, err error) { return len(p), nil }
134
135func (cp *criticalPath) criticalPath() []*node {
136	var max *node
137
138	// Find the node with the longest critical path
139	for _, node := range cp.nodes {
140		if max == nil || node.cumulativeDuration > max.cumulativeDuration {
141			max = node
142		}
143	}
144
145	// Follow the critical path back to the leaf node
146	var criticalPath []*node
147	node := max
148	for node != nil {
149		criticalPath = append(criticalPath, node)
150		node = node.input
151	}
152
153	return criticalPath
154}
155