transitive-deps.sh 16 KB

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