Google Git
Sign in
android / platform / build / blueprint / 9793b0a5e0fd75bc956230a7b262e14947799d2e
commit9793b0a5e0fd75bc956230a7b262e14947799d2e[log] [tgz]
authorColin Cross <ccross@android.com>Tue Apr 27 15:20:15 2021 -0700
committerColin Cross <ccross@android.com>Wed Apr 28 09:40:47 2021 -0700
treedfadde4729dc704bd33da6cb672f20d7b1fbf42c
parent9021eef07bd99c1dfb70db51d5d8a98491899ec3 [diff]
Speed up finding dependency cycles

parallelVisit supports mutating the dependency graph while it is being
visited by proceeding until there are no modules with their dependencies
satisfied, and then checking if there are modules that haven't been
visited yet.  If so, it assumes there was a newly introduced dependency
cycle and tries to find it to return as an error.

Finding the dependency cycle could traverse outside of the cycle.
If the dependency cycle occurs near the bottom of the dependency graph,
that traversal could be both long and wide, leading to very long
runtimes.

Memoize traversed modules that were not found to be part of the
dependency cycle to prevent repeated traversals.

Fixes: 186572387
Test: introduce cycle into libc, m nothing
Test: Test_parallelVisit
Change-Id: I38d0749dbedffbe8a39e433d97fbe08486451321
1 file changed
tree: dfadde4729dc704bd33da6cb672f20d7b1fbf42c
  1. .github/
  2. bootstrap/
  3. bpfmt/
  4. bpmodify/
  5. deptools/
  6. gotestmain/
  7. gotestrunner/
  8. loadplugins/
  9. microfactory/
  10. parser/
  11. pathtools/
  12. proptools/
  13. tests/
  14. .gitignore
  15. .gofmt.sh
  16. blueprint.bash
  17. blueprint_impl.bash
  18. Blueprints
  19. bootstrap.bash
  20. CODEOWNERS
  21. context.go
  22. context_test.go
  23. CONTRIBUTING.md
  24. doc.go
  25. glob.go
  26. glob_test.go
  27. go.mod
  28. LICENSE
  29. live_tracker.go
  30. mangle.go
  31. module_ctx.go
  32. module_ctx_test.go
  33. name_interface.go
  34. ninja_defs.go
  35. ninja_strings.go
  36. ninja_strings_test.go
  37. ninja_writer.go
  38. ninja_writer_test.go
  39. OWNERS
  40. package_ctx.go
  41. PREUPLOAD.cfg
  42. provider.go
  43. provider_test.go
  44. README.md
  45. scope.go
  46. singleton_ctx.go
  47. splice_modules_test.go
  48. visit_test.go
README.md

Blueprint Build System

Blueprint is being archived on 2021 May 3.

On 2021 May 3, we will be archiving the Blueprint project. This means it will not be possible to file new issues or open new pull requests for this GitHub project. As the project is being archived, patches -- including security patches -- will not be applied after May 3. The source tree will remain available, but changes to Blueprint in AOSP will not be merged here and Blueprint's source tree in AOSP will eventually stop being usable outside of Android.

Whereas there are no meta-build systems one can use as a drop-in replacement for Blueprint, there are a number of build systems that can be used:

  • Bazel, Google's multi-language build tool to build and test software of any size, quickly and reliably
  • Soong, for building the Android operating system itself
  • CMake, an open-source, cross-platform family of tools designed to build, test and package software
  • Buck, a fast build system that encourages the creation of small, reusable modules over a variety of platforms and languages
  • The venerable GNU Make