1#!/bin/bash
2
3set -eu
4
5# Copyright 2020 Google Inc. All rights reserved.
6#
7# Licensed under the Apache License, Version 2.0 (the "License");
8# you may not use this file except in compliance with the License.
9# You may obtain a copy of the License at
10#
11#     http://www.apache.org/licenses/LICENSE-2.0
12#
13# Unless required by applicable law or agreed to in writing, software
14# distributed under the License is distributed on an "AS IS" BASIS,
15# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16# See the License for the specific language governing permissions and
17# limitations under the License.
18
19# Tool to evaluate the transitive closure of the ninja dependency graph of the
20# files and targets depending on a given target.
21#
22# i.e. the list of things that could change after changing a target.
23
24readonly me=$(basename "${0}")
25
26readonly usage="usage: ${me} {options} target [target...]
27
28Evaluate the reverse transitive closure of ninja targets depending on one or
29more targets.
30
31Options:
32
33  -(no)quiet        Suppresses progress output to stderr and interactive
34    alias -(no)q    prompts. By default, when stderr is a tty, progress gets
35                    reported to stderr; when both stderr and stdin are tty,
36                    the script asks user whether to delete intermediate files.
37                    When suppressed or not prompted, script always deletes the
38                    temporary / intermediate files.
39  -sep=<delim>      Use 'delim' as output field separator between notice
40                    checksum and notice filename in notice output.
41                    e.g. sep='\t'
42                    (Default space)
43  -csv              Shorthand for -sep=','
44
45At minimum, before running this script, you must first run:
46$ source build/envsetup.sh
47$ lunch
48$ m nothing
49to setup the build environment, choose a target platform, and build the ninja
50dependency graph.
51"
52
53function die() { echo -e "${*}" >&2; exit 2; }
54
55# Reads one input target per line from stdin; outputs (isnotice target) tuples.
56#
57# output target is a ninja target that the input target depends on
58# isnotice in {0,1} with 1 for output targets believed to be license or notice
59#
60# only argument is the dependency depth indicator
61function getDeps() {
62    (tr '\n' '\0' | xargs -0 "${ninja_bin}" -f "${ninja_file}" -t query) \
63    | awk -v depth="${1}" '
64      BEGIN {
65        inoutput = 0
66      }
67      $0 ~ /^\S\S*:$/ {
68        inoutput = 0
69      }
70      inoutput != 0 {
71        print gensub(/^\s*/, "", "g")" "depth
72      }
73      $1 == "outputs:" {
74        inoutput = 1
75      }
76    '
77}
78
79
80if [ -z "${ANDROID_BUILD_TOP}" ]; then
81    die "${me}: Run 'lunch' to configure the build environment"
82fi
83
84if [ -z "${TARGET_PRODUCT}" ]; then
85    die "${me}: Run 'lunch' to configure the build environment"
86fi
87
88ninja_file="${ANDROID_BUILD_TOP}/out/combined-${TARGET_PRODUCT}.ninja"
89if [ ! -f "${ninja_file}" ]; then
90    die "${me}: Run 'm nothing' to build the dependency graph"
91fi
92
93ninja_bin="${ANDROID_BUILD_TOP}/prebuilts/build-tools/linux-x86/bin/ninja"
94if [ ! -x "${ninja_bin}" ]; then
95    die "${me}: Cannot find ninja executable expected at ${ninja_bin}"
96fi
97
98
99# parse the command-line
100
101declare -a targets # one or more targets to evaluate
102
103quiet=false      # whether to suppress progress
104
105sep=" "          # output separator between depth and target
106
107use_stdin=false  # whether to read targets from stdin i.e. target -
108
109while [ $# -gt 0 ]; do
110    case "${1:-}" in
111      -)
112        use_stdin=true
113      ;;
114      -*)
115        flag=$(expr "${1}" : '^-*\(.*\)$')
116        case "${flag:-}" in
117          q) ;&
118          quiet)
119            quiet=true;;
120          noq) ;&
121          noquiet)
122            quiet=false;;
123          csv)
124            sep=",";;
125          sep)
126            sep="${2?"${usage}"}"; shift;;
127          sep=*)
128            sep=$(expr "${flag}" : '^sep=\(.*\)$';;
129          *)
130            die "Unknown flag ${1}"
131          ;;
132        esac
133      ;;
134      *)
135        targets+=("${1:-}")
136      ;;
137    esac
138    shift
139done
140
141if [ ! -v targets[0] ] && ! ${use_stdin}; then
142    die "${usage}\n\nNo target specified."
143fi
144
145# showProgress when stderr is a tty
146if [ -t 2 ] && ! ${quiet}; then
147    showProgress=true
148else
149    showProgress=false
150fi
151
152# interactive when both stderr and stdin are tty
153if ${showProgress} && [ -t 0 ]; then
154    interactive=true
155else
156    interactive=false
157fi
158
159
160readonly tmpFiles=$(mktemp -d "${TMPDIR}.tdeps.XXXXXXXXX")
161if [ -z "${tmpFiles}" ]; then
162    die "${me}: unable to create temporary directory"
163fi
164
165# The deps files contain unique (isnotice target) tuples where
166# isnotice in {0,1} with 1 when ninja target `target` is a license or notice.
167readonly oldDeps="${tmpFiles}/old"
168readonly newDeps="${tmpFiles}/new"
169readonly allDeps="${tmpFiles}/all"
170
171if ${use_stdin}; then # start deps by reading 1 target per line from stdin
172  awk '
173    NF > 0 {
174      print gensub(/\s*$/, "", "g", gensub(/^\s*/, "", "g"))" "0
175    }
176  ' >"${newDeps}"
177else # start with no deps by clearing file
178  : >"${newDeps}"
179fi
180
181# extend deps by appending targets from command-line
182for idx in "${!targets[*]}"; do
183    echo "${targets[${idx}]} 0" >>"${newDeps}"
184done
185
186# remove duplicates and start with new, old and all the same
187sort -u <"${newDeps}" >"${allDeps}"
188cp "${allDeps}" "${newDeps}"
189cp "${allDeps}" "${oldDeps}"
190
191# report depth of dependenciens when showProgress
192depth=0
193
194while [ $(wc -l < "${newDeps}") -gt 0 ]; do
195    if ${showProgress}; then
196        echo "depth ${depth} has "$(wc -l < "${newDeps}")" targets" >&2
197    fi
198    depth=$(expr ${depth} + 1)
199    ( # recalculate dependencies by combining unique inputs of new deps w. old
200        cut -d\  -f1 "${newDeps}" | getDeps "${depth}"
201        cat "${oldDeps}"
202    ) | sort -n | awk '
203      BEGIN {
204        prev = ""
205      }
206      {
207        depth = $NF
208        $NF = ""
209        gsub(/\s*$/, "")
210        if ($0 != prev) {
211          print gensub(/\s*$/, "", "g")" "depth
212        }
213        prev = $0
214      }
215    ' >"${allDeps}"
216    # recalculate new dependencies as net additions to old dependencies
217    set +e
218    diff "${oldDeps}" "${allDeps}" --old-line-format='' \
219      --new-line-format='%L' --unchanged-line-format='' > "${newDeps}"
220    set -e
221    # recalculate old dependencies for next iteration
222    cp "${allDeps}" "${oldDeps}"
223done
224
225# found all deps -- clean up last iteration of old and new
226rm -f "${oldDeps}"
227rm -f "${newDeps}"
228
229if ${showProgress}; then
230    echo $(wc -l < "${allDeps}")" targets" >&2
231fi
232
233awk -v sep="${sep}" '{
234  depth = $NF
235  $NF = ""
236  gsub(/\s*$/, "")
237  print depth sep $0
238}' "${allDeps}" | sort -n
239
240if ${interactive}; then
241    echo -n "$(date '+%F %-k:%M:%S') Delete ${tmpFiles} ? [n] " >&2
242    read answer
243    case "${answer}" in [yY]*) rm -fr "${tmpFiles}";; esac
244else
245    rm -fr "${tmpFiles}"
246fi
247