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 a given target depends on.
21#
22# i.e. the list of things that, if changed, could cause a change to a target.
23
24readonly me=$(basename "${0}")
25
26readonly usage="usage: ${me} {options} target [target...]
27
28Evaluate the transitive closure of files and ninja targets that one or more
29targets depend on.
30
31Dependency Options:
32
33  -(no)order_deps   Whether to include order-only dependencies. (Default false)
34  -(no)implicit     Whether to include implicit dependencies. (Default true)
35  -(no)explicit     Whether to include regular / explicit deps. (Default true)
36
37  -nofollow         Unanchored regular expression. Matching paths and targets
38                    always get reported. Their dependencies do not get reported
39                    unless first encountered in a 'container' file type.
40                    Multiple allowed and combined using '|'.
41                    e.g. -nofollow='*.so' not -nofollow='.so$'
42                    -nofollow='*.so|*.dex' or -nofollow='*.so' -nofollow='.dex'
43                    (Defaults to no matches)
44  -container        Unanchored regular expression. Matching file extensions get
45                    treated as 'container' files for -nofollow option.
46                    Multiple allowed and combines using '|'
47                    (Default 'apex|apk|zip|jar|tar|tgz')
48
49Output Options:
50
51  -(no)quiet        Suppresses progress output to stderr and interactive
52    alias -(no)q    prompts. By default, when stderr is a tty, progress gets
53                    reported to stderr; when both stderr and stdin are tty,
54                    the script asks user whether to delete intermediate files.
55                    When suppressed or not prompted, script always deletes the
56                    temporary / intermediate files.
57  -sep=<delim>      Use 'delim' as output field separator between notice
58                    checksum and notice filename in notice output.
59                    e.g. sep='\\t'
60                    (Default space)
61  -csv              Shorthand for -sep=','
62  -directories=<f>  Output directory names of dependencies to 'f'.
63    alias -d        User '/dev/stdout' to send directories to stdout. Defaults
64                    to no directory output.
65  -notices=<file>   Output license and notice file paths to 'file'.
66    alias -n        Use '/dev/stdout' to send notices to stdout. Defaults to no
67                    license/notice output.
68  -projects=<file>  Output git project names to 'file'. Use '/dev/stdout' to
69    alias -p        send projects to stdout. Defaults to no project output.
70  -targets=<fils>   Output target dependencies to 'file'. Use '/dev/stdout' to
71    alias -t        send targets to stdout.
72                    When no directory, notice, project or target output options
73                    given, defaults to stdout. Otherwise, defaults to no target
74                    output.
75
76At minimum, before running this script, you must first run:
77$ source build/envsetup.sh
78$ lunch
79$ m nothing
80to setup the build environment, choose a target platform, and build the ninja
81dependency graph.
82"
83
84function die() { echo -e "${*}" >&2; exit 2; }
85
86# Reads one input target per line from stdin; outputs (isnotice target) tuples.
87#
88# output target is a ninja target that the input target depends on
89# isnotice in {0,1} with 1 for output targets believed to be license or notice
90function getDeps() {
91    (tr '\n' '\0' | xargs -0 -r "${ninja_bin}" -f "${ninja_file}" -t query) \
92    | awk -v include_order="${include_order_deps}" \
93        -v include_implicit="${include_implicit_deps}" \
94        -v include_explicit="${include_deps}" \
95        -v containers="${container_types}" \
96    '
97      BEGIN {
98        ininput = 0
99        isnotice = 0
100        currFileName = ""
101        currExt = ""
102      }
103      $1 == "outputs:" {
104        ininput = 0
105      }
106      ininput == 0 && $0 ~ /^\S\S*:$/ {
107        isnotice = ($0 ~ /.*NOTICE.*[.]txt:$/)
108        currFileName = gensub(/^.*[/]([^/]*)[:]$/, "\\1", "g")
109        currExt = gensub(/^.*[.]([^./]*)[:]$/, "\\1", "g")
110      }
111      ininput != 0 && $1 !~ /^[|][|]?/ {
112        if (include_explicit == "true") {
113          fileName = gensub(/^.*[/]([^/]*)$/, "\\1", "g")
114          print ( \
115              (isnotice && $0 !~ /^\s*build[/]soong[/]scripts[/]/) \
116              || $0 ~ /NOTICE|LICEN[CS]E/ \
117              || $0 ~ /(notice|licen[cs]e)[.]txt/ \
118          )" "(fileName == currFileName||currExt ~ "^(" containers ")$")" "gensub(/^\s*/, "", "g")
119        }
120      }
121      ininput != 0 && $1 == "|" {
122        if (include_implicit == "true") {
123          fileName = gensub(/^.*[/]([^/]*)$/, "\\1", "g")
124          $1 = ""
125          print ( \
126              (isnotice && $0 !~ /^\s*build[/]soong[/]scripts[/]/) \
127              || $0 ~ /NOTICE|LICEN[CS]E/ \
128              || $0 ~ /(notice|licen[cs]e)[.]txt/ \
129          )" "(fileName == currFileName||currExt ~ "^(" containers ")$")" "gensub(/^\s*/, "", "g")
130        }
131      }
132      ininput != 0 && $1 == "||" {
133        if (include_order == "true") {
134          fileName = gensub(/^.*[/]([^/]*)$/, "\\1", "g")
135          $1 = ""
136          print ( \
137              (isnotice && $0 !~ /^\s*build[/]soong[/]scripts[/]/) \
138              || $0 ~ /NOTICE|LICEN[CS]E/ \
139              || $0 ~ /(notice|licen[cs]e)[.]txt/ \
140          )" "(fileName == currFileName||currExt ~ "^(" containers ")$")" "gensub(/^\s*/, "", "g")
141        }
142      }
143      $1 == "input:" {
144        ininput = 1
145      }
146    '
147}
148
149# Reads one input directory per line from stdin; outputs unique git projects.
150function getProjects() {
151    while read d; do
152        while [ "${d}" != '.' ] && [ "${d}" != '/' ]; do
153            if [ -d "${d}/.git/" ]; then
154                echo "${d}"
155                break
156            fi
157            d=$(dirname "${d}")
158        done
159    done | sort -u
160}
161
162
163if [ -z "${ANDROID_BUILD_TOP}" ]; then
164    die "${me}: Run 'lunch' to configure the build environment"
165fi
166
167if [ -z "${TARGET_PRODUCT}" ]; then
168    die "${me}: Run 'lunch' to configure the build environment"
169fi
170
171readonly ninja_file="${ANDROID_BUILD_TOP}/out/combined-${TARGET_PRODUCT}.ninja"
172if [ ! -f "${ninja_file}" ]; then
173    die "${me}: Run 'm nothing' to build the dependency graph"
174fi
175
176readonly ninja_bin="${ANDROID_BUILD_TOP}/prebuilts/build-tools/linux-x86/bin/ninja"
177if [ ! -x "${ninja_bin}" ]; then
178    die "${me}: Cannot find ninja executable expected at ${ninja_bin}"
179fi
180
181
182# parse the command-line
183
184declare -a targets # one or more targets to evaluate
185
186include_order_deps=false    # whether to trace through || "order dependencies"
187include_implicit_deps=true  # whether to trace through | "implicit deps"
188include_deps=true           # whether to trace through regular explicit deps
189quiet=false                 # whether to suppress progress
190
191projects_out=''             # where to output the list of projects
192directories_out=''          # where to output the list of directories
193targets_out=''              # where to output the list of targets/source files
194notices_out=''              # where to output the list of license/notice files
195
196sep=" "                     # separator between md5sum and notice filename
197
198nofollow=''                 # regularexp must fully match targets to skip
199
200container_types=''          # regularexp must full match file extension
201                            # defaults to 'apex|apk|zip|jar|tar|tgz' below.
202
203use_stdin=false             # whether to read targets from stdin i.e. target -
204
205while [ $# -gt 0 ]; do
206    case "${1:-}" in
207      -)
208        use_stdin=true
209      ;;
210      -*)
211        flag=$(expr "${1}" : '^-*\(.*\)$')
212        case "${flag:-}" in
213          order_deps)
214            include_order_deps=true;;
215          noorder_deps)
216            include_order_deps=false;;
217          implicit)
218            include_implicit_deps=true;;
219          noimplicit)
220            include_implicit_deps=false;;
221          explicit)
222            include_deps=true;;
223          noexplicit)
224            include_deps=false;;
225          csv)
226            sep=",";;
227          sep)
228            sep="${2?"${usage}"}"; shift;;
229          sep=)
230            sep=$(expr "${flag}" : '^sep=\(.*\)$');;
231          q) ;&
232          quiet)
233            quiet=true;;
234          noq) ;&
235          noquiet)
236            quiet=false;;
237          nofollow)
238            case "${nofollow}" in
239              '')
240                nofollow="${2?"${usage}"}";;
241              *)
242                nofollow="${nofollow}|${2?"${usage}"}";;
243            esac
244            shift
245          ;;
246          nofollow=*)
247            case "${nofollow}" in
248              '')
249                nofollow=$(expr "${flag}" : '^nofollow=\(.*\)$');;
250              *)
251                nofollow="${nofollow}|"$(expr "${flag}" : '^nofollow=\(.*\)$');;
252            esac
253          ;;
254          container)
255            container_types="${container_types}|${2?"${usage}"}";;
256          container=*)
257            container_types="${container_types}|"$(expr "${flag}" : '^container=\(.*\)$');;
258          p) ;&
259          projects)
260            projects_out="${2?"${usage}"}"; shift;;
261          p=*) ;&
262          projects=*)
263            projects_out=$(expr "${flag}" : '^.*=\(.*\)$');;
264          d) ;&
265          directores)
266            directories_out="${2?"${usage}"}"; shift;;
267          d=*) ;&
268          directories=*)
269            directories_out=$(expr "${flag}" : '^.*=\(.*\)$');;
270          t) ;&
271          targets)
272            targets_out="${2?"${usage}"}"; shift;;
273          t=*) ;&
274          targets=)
275            targets_out=$(expr "${flag}" : '^.*=\(.*\)$');;
276          n) ;&
277          notices)
278            notices_out="${2?"${usage}"}"; shift;;
279          n=*) ;&
280          notices=)
281            notices_out=$(expr "${flag}" : '^.*=\(.*\)$');;
282          *)
283            die "${usage}\n\nUnknown flag ${1}";;
284        esac
285      ;;
286      *)
287        targets+=("${1:-}")
288      ;;
289    esac
290    shift
291done
292
293
294# fail fast if command-line arguments are invalid
295
296if [ ! -v targets[0] ] && ! ${use_stdin}; then
297    die "${usage}\n\nNo target specified."
298fi
299
300if [ -z "${projects_out}" ] \
301  && [ -z "${directories_out}" ] \
302  && [ -z "${targets_out}" ] \
303  && [ -z "${notices_out}" ]
304then
305    targets_out='/dev/stdout'
306fi
307
308if [ -z "${container_types}" ]; then
309  container_types='apex|apk|zip|jar|tar|tgz'
310fi
311
312# showProgress when stderr is a tty
313if [ -t 2 ] && ! ${quiet}; then
314    showProgress=true
315else
316    showProgress=false
317fi
318
319# interactive when both stderr and stdin are tty
320if ${showProgress} && [ -t 0 ]; then
321    interactive=true
322else
323    interactive=false
324fi
325
326
327readonly tmpFiles=$(mktemp -d "${TMPDIR}.tdeps.XXXXXXXXX")
328if [ -z "${tmpFiles}" ]; then
329    die "${me}: unable to create temporary directory"
330fi
331
332# The deps files contain unique (isnotice target) tuples where
333# isnotice in {0,1} with 1 when ninja target 'target' is a license or notice.
334readonly oldDeps="${tmpFiles}/old"
335readonly newDeps="${tmpFiles}/new"
336readonly allDeps="${tmpFiles}/all"
337
338if ${use_stdin}; then # start deps by reading 1 target per line from stdin
339  awk '
340    NF > 0 {
341      print ( \
342          $0 ~ /NOTICE|LICEN[CS]E/ \
343          || $0 ~ /(notice|licen[cs]e)[.]txt/ \
344      )" "gensub(/\s*$/, "", "g", gensub(/^\s*/, "", "g"))
345    }
346  ' > "${newDeps}"
347else # start with no deps by clearing file
348  : > "${newDeps}"
349fi
350
351# extend deps by appending targets from command-line
352for idx in "${!targets[*]}"; do
353    isnotice='0'
354    case "${targets[${idx}]}" in
355      *NOTICE*) ;&
356      *LICEN[CS]E*) ;&
357      *notice.txt) ;&
358      *licen[cs]e.txt)
359        isnotice='1';;
360    esac
361    echo "${isnotice} 1 ${targets[${idx}]}" >> "${newDeps}"
362done
363
364# remove duplicates and start with new, old and all the same
365sort -u < "${newDeps}" > "${allDeps}"
366cp "${allDeps}" "${newDeps}"
367cp "${allDeps}" "${oldDeps}"
368
369# report depth of dependenciens when showProgress
370depth=0
371
372# 1st iteration always unfiltered
373filter='cat'
374while [ $(wc -l < "${newDeps}") -gt 0 ]; do
375    if ${showProgress}; then
376        echo "depth ${depth} has "$(wc -l < "${newDeps}")" targets" >&2
377        depth=$(expr ${depth} + 1)
378    fi
379    ( # recalculate dependencies by combining unique inputs of new deps w. old
380        set +e
381        sh -c "${filter}" < "${newDeps}" | cut -d\  -f3- | getDeps
382        set -e
383        cat "${oldDeps}"
384    ) | sort -u > "${allDeps}"
385    # recalculate new dependencies as net additions to old dependencies
386    set +e
387    diff "${oldDeps}" "${allDeps}" --old-line-format='' --new-line-format='%L' \
388      --unchanged-line-format='' > "${newDeps}"
389    set -e
390    # apply filters on subsequent iterations
391    case "${nofollow}" in
392      '')
393        filter='cat';;
394      *)
395        filter="egrep -v '^[01] 0 (${nofollow})$'"
396      ;;
397    esac
398    # recalculate old dependencies for next iteration
399    cp "${allDeps}" "${oldDeps}"
400done
401
402# found all deps -- clean up last iteration of old and new
403rm -f "${oldDeps}"
404rm -f "${newDeps}"
405
406if ${showProgress}; then
407    echo $(wc -l < "${allDeps}")" targets" >&2
408fi
409
410if [ -n "${targets_out}" ]; then
411    cut -d\  -f3- "${allDeps}" | sort -u > "${targets_out}"
412fi
413
414if [ -n "${directories_out}" ] \
415  || [ -n "${projects_out}" ] \
416  || [ -n "${notices_out}" ]
417then
418    readonly allDirs="${tmpFiles}/dirs"
419    (
420        cut -d\  -f3- "${allDeps}" | tr '\n' '\0' | xargs -0 dirname
421    ) | sort -u > "${allDirs}"
422    if ${showProgress}; then
423        echo $(wc -l < "${allDirs}")" directories" >&2
424    fi
425
426    case "${directories_out}" in
427      '')        : do nothing;;
428      *)
429        cat "${allDirs}" > "${directories_out}"
430      ;;
431    esac
432fi
433
434if [ -n "${projects_out}" ] \
435  || [ -n "${notices_out}" ]
436then
437    readonly allProj="${tmpFiles}/projects"
438    set +e
439    egrep -v '^out[/]' "${allDirs}" | getProjects > "${allProj}"
440    set -e
441    if ${showProgress}; then
442        echo $(wc -l < "${allProj}")" projects" >&2
443    fi
444
445    case "${projects_out}" in
446      '')        : do nothing;;
447      *)
448        cat "${allProj}" > "${projects_out}"
449      ;;
450    esac
451fi
452
453case "${notices_out}" in
454  '')        : do nothing;;
455  *)
456    readonly allNotice="${tmpFiles}/notices"
457    set +e
458    egrep '^1' "${allDeps}" | cut -d\  -f3- | egrep -v '^out/' > "${allNotice}"
459    set -e
460    cat "${allProj}" | while read proj; do
461        for f in LICENSE LICENCE NOTICE license.txt notice.txt; do
462            if [ -f "${proj}/${f}" ]; then
463                echo "${proj}/${f}"
464            fi
465        done
466    done >> "${allNotice}"
467    if ${showProgress}; then
468      echo $(cat "${allNotice}" | sort -u | wc -l)" notice targets" >&2
469    fi
470    readonly hashedNotice="${tmpFiles}/hashednotices"
471    ( # md5sum outputs checksum space indicator(space or *) filename newline
472        set +e
473        sort -u "${allNotice}" | tr '\n' '\0' | xargs -0 -r md5sum 2>/dev/null
474        set -e
475      # use sed to replace space and indicator with separator
476    ) > "${hashedNotice}"
477    if ${showProgress}; then
478        echo $(cut -d\  -f2- "${hashedNotice}" | sort -u | wc -l)" notice files" >&2
479        echo $(cut -d\  -f1 "${hashedNotice}" | sort -u | wc -l)" distinct notices" >&2
480    fi
481    sed 's/^\([^ ]*\) [* ]/\1'"${sep}"'/g' "${hashedNotice}" | sort > "${notices_out}"
482  ;;
483esac
484
485if ${interactive}; then
486    echo -n "$(date '+%F %-k:%M:%S') Delete ${tmpFiles} ? [n] " >&2
487    read answer
488    case "${answer}" in [yY]*) rm -fr "${tmpFiles}";; esac
489else
490    rm -fr "${tmpFiles}"
491fi
492