reverse-deps.sh 6.7 KB

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