Home | History | Annotate | Download | only in core 
      1 # Copyright (C) 2012 The Android Open Source Project
      2 #
      3 # Licensed under the Apache License, Version 2.0 (the "License");
      4 # you may not use this file except in compliance with the License.
      5 # You may obtain a copy of the License at
      6 #
      7 #      http://www.apache.org/licenses/LICENSE-2.0
      8 #
      9 # Unless required by applicable law or agreed to in writing, software
     10 # distributed under the License is distributed on an "AS IS" BASIS,
     11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 # See the License for the specific language governing permissions and
     13 # limitations under the License.
     14 #
     15 # Definitions of various graph-related generic functions, used by
     16 # ndk-build internally.
     17 #
     18 
     19 # Coding style note:
     20 #
     21 # All internal variables in this file begin with '_ndk_mod_'
     22 # All internal functions in this file begin with '-ndk-mod-'
     23 #
     24 
     25 # Set this to true if you want to debug the functions here.
     26 _ndk_mod_debug := $(if $(NDK_DEBUG_MODULES),true)
     27 _ndk_topo_debug := $(if $(NDK_DEBUG_TOPO),true)
     28 
     29 # Use $(call -ndk-mod-debug,<message>) to print a debug message only
     30 # if _ndk_mod_debug is set to 'true'. Useful for debugging the functions
     31 # available here.
     32 #
     33 ifeq (true,$(_ndk_mod_debug))
     34 -ndk-mod-debug = $(info $1)
     35 else
     36 -ndk-mod-debug := $(empty)
     37 endif
     38 
     39 ifeq (true,$(_ndk_topo_debug))
     40 -ndk-topo-debug = $(info $1)
     41 else
     42 -ndk-topo-debug = $(empty)
     43 endif
     44 
     45 #######################################################################
     46 # Filter a list of module with a predicate function
     47 # $1: list of module names.
     48 # $2: predicate function, will be called with $(call $2,<name>), if the
     49 #     result is not empty, <name> will be added to the result.
     50 # Out: subset of input list, where each item passes the predicate.
     51 #######################################################################
     52 -ndk-mod-filter = $(strip \
     53     $(foreach _ndk_mod_filter_n,$1,\
     54         $(if $(call $2,$(_ndk_mod_filter_n)),$(_ndk_mod_filter_n))\
     55     ))
     56 
     57 -test-ndk-mod-filter = \
     58     $(eval -local-func = $$(call seq,foo,$$1))\
     59     $(call test-expect,,$(call -ndk-mod-filter,,-local-func))\
     60     $(call test-expect,foo,$(call -ndk-mod-filter,foo,-local-func))\
     61     $(call test-expect,foo,$(call -ndk-mod-filter,foo bar,-local-func))\
     62     $(call test-expect,foo foo,$(call -ndk-mod-filter,aaa foo bar foo,-local-func))\
     63     $(eval -local-func = $$(call sne,foo,$$1))\
     64     $(call test-expect,,$(call -ndk-mod-filter,,-local-func))\
     65     $(call test-expect,,$(call -ndk-mod-filter,foo,-local-func))\
     66     $(call test-expect,bar,$(call -ndk-mod-filter,foo bar,-local-func))\
     67     $(call test-expect,aaa bar,$(call -ndk-mod-filter,aaa foo bar,-local-func))
     68 
     69 
     70 #######################################################################
     71 # Filter out a list of modules with a predicate function
     72 # $1: list of module names.
     73 # $2: predicate function, will be called with $(call $2,<name>), if the
     74 #     result is not empty, <name> will be added to the result.
     75 # Out: subset of input list, where each item doesn't pass the predicate.
     76 #######################################################################
     77 -ndk-mod-filter-out = $(strip \
     78     $(foreach _ndk_mod_filter_n,$1,\
     79         $(if $(call $2,$(_ndk_mod_filter_n)),,$(_ndk_mod_filter_n))\
     80     ))
     81 
     82 -test-ndk-mod-filter-out = \
     83     $(eval -local-func = $$(call seq,foo,$$1))\
     84     $(call test-expect,,$(call -ndk-mod-filter-out,,-local-func))\
     85     $(call test-expect,,$(call -ndk-mod-filter-out,foo,-local-func))\
     86     $(call test-expect,bar,$(call -ndk-mod-filter-out,foo bar,-local-func))\
     87     $(call test-expect,aaa bar,$(call -ndk-mod-filter-out,aaa foo bar foo,-local-func))\
     88     $(eval -local-func = $$(call sne,foo,$$1))\
     89     $(call test-expect,,$(call -ndk-mod-filter-out,,-local-func))\
     90     $(call test-expect,foo,$(call -ndk-mod-filter-out,foo,-local-func))\
     91     $(call test-expect,foo,$(call -ndk-mod-filter-out,foo bar,-local-func))\
     92     $(call test-expect,foo foo,$(call -ndk-mod-filter-out,aaa foo bar foo,-local-func))
     93 
     94 
     95 #######################################################################
     96 # Find the first item in a list that checks a valid predicate.
     97 # $1: list of names.
     98 # $2: predicate function, will be called with $(call $2,<name>), if the
     99 #     result is not empty, <name> will be added to the result.
    100 # Out: subset of input list.
    101 #######################################################################
    102 -ndk-mod-find-first = $(firstword $(call -ndk-mod-filter,$1,$2))
    103 
    104 -test-ndk-mod-find-first.empty = \
    105     $(eval -local-pred = $$(call seq,foo,$$1))\
    106     $(call test-expect,,$(call -ndk-mod-find-first,,-local-pred))\
    107     $(call test-expect,,$(call -ndk-mod-find-first,bar,-local-pred))
    108 
    109 -test-ndk-mod-find-first.simple = \
    110     $(eval -local-pred = $$(call seq,foo,$$1))\
    111     $(call test-expect,foo,$(call -ndk-mod-find-first,foo,-local-pred))\
    112     $(call test-expect,foo,$(call -ndk-mod-find-first,aaa foo bar,-local-pred))\
    113     $(call test-expect,foo,$(call -ndk-mod-find-first,aaa foo foo bar,-local-pred))
    114 
    115 ########################################################################
    116 # Many tree walking operations require setting a 'visited' flag on
    117 # specific graph nodes. The following helper functions help implement
    118 # this while hiding details to the callers.
    119 #
    120 # Technical note:
    121 #  _ndk_mod_tree_visited.<name> will be 'true' if the node was visited,
    122 #  or empty otherwise.
    123 #
    124 #  _ndk_mod_tree_visitors lists all visited nodes, used to clean all
    125 #  _ndk_mod_tree_visited.<name> variables in -ndk-mod-tree-setup-visit.
    126 #
    127 #######################################################################
    128 
    129 # Call this before tree traversal.
    130 -ndk-mod-tree-setup-visit = \
    131     $(foreach _ndk_mod_tree_visitor,$(_ndk_mod_tree_visitors),\
    132         $(eval _ndk_mod_tree_visited.$$(_ndk_mod_tree_visitor) :=))\
    133     $(eval _ndk_mod_tree_visitors :=)
    134 
    135 # Returns non-empty if a node was visited.
    136 -ndk-mod-tree-is-visited = \
    137     $(_ndk_mod_tree_visited.$1)
    138 
    139 # Set the visited state of a node to 'true'
    140 -ndk-mod-tree-set-visited = \
    141     $(eval _ndk_mod_tree_visited.$1 := true)\
    142     $(eval _ndk_mod_tree_visitors += $1)
    143 
    144 ########################################################################
    145 # Many graph walking operations require a work queue and computing
    146 # dependencies / children nodes. Here are a few helper functions that
    147 # can be used to make their code clearer. This uses a few global
    148 # variables that should be defined as follows during the operation:
    149 #
    150 #  _ndk_mod_module     current graph node name.
    151 #  _ndk_mod_wq         current node work queue.
    152 #  _ndk_mod_list       current result (list of nodes).
    153 #  _ndk_mod_depends    current graph node's children.
    154 #                      you must call -ndk-mod-get-depends to set this.
    155 #
    156 #######################################################################
    157 
    158 # Pop first item from work-queue into _ndk_mod_module.
    159 -ndk-mod-pop-first = \
    160     $(eval _ndk_mod_module := $$(call first,$$(_ndk_mod_wq)))\
    161     $(eval _ndk_mod_wq     := $$(call rest,$$(_ndk_mod_wq)))
    162 
    163 -test-ndk-mod-pop-first = \
    164     $(eval _ndk_mod_wq := A B C)\
    165     $(call -ndk-mod-pop-first)\
    166     $(call test-expect,A,$(_ndk_mod_module))\
    167     $(call test-expect,B C,$(_ndk_mod_wq))\
    168 
    169 
    170 # Push list of items at the back of the work-queue.
    171 -ndk-mod-push-back = \
    172     $(eval _ndk_mod_wq := $(strip $(_ndk_mod_wq) $1))
    173 
    174 -test-ndk-mod-push-back = \
    175   $(eval _ndk_mod_wq := A B C)\
    176   $(call -ndk-mod-push-back, D    E)\
    177   $(call test-expect,A B C D E,$(_ndk_mod_wq))
    178 
    179 # Set _ndk_mod_depends to the direct dependencies of _ndk_mod_module
    180 -ndk-mod-get-depends = \
    181     $(eval _ndk_mod_depends := $$(call $$(_ndk_mod_deps_func),$$(_ndk_mod_module)))
    182 
    183 # Set _ndk_mod_depends to the direct dependencies of _ndk_mod_module that
    184 # are not already in _ndk_mod_list.
    185 -ndk-mod-get-new-depends = \
    186     $(call -ndk-mod-get-depends)\
    187     $(eval _ndk_mod_depends := $$(filter-out $$(_ndk_mod_list),$$(_ndk_mod_depends)))
    188 
    189 ##########################################################################
    190 # Compute the transitive closure
    191 # $1: list of modules.
    192 # $2: dependency function, $(call $2,<module>) should return all the
    193 #     module that <module> depends on.
    194 # Out: transitive closure of all modules from those in $1. Always includes
    195 #      the modules in $1. Order is random.
    196 #
    197 # Implementation note:
    198 #   we use the -ndk-mod-tree-xxx functions to flag 'visited' nodes
    199 #   in the graph. A node is visited once it has been put into the work
    200 #   queue. For each item in the work queue, get the dependencies and
    201 #   append all those that were not visited yet.
    202 #######################################################################
    203 -ndk-mod-get-closure = $(strip \
    204     $(eval _ndk_mod_wq :=)\
    205     $(eval _ndk_mod_list :=)\
    206     $(eval _ndk_mod_deps_func := $2)\
    207     $(call -ndk-mod-tree-setup-visit)\
    208     $(foreach _ndk_mod_module,$1,\
    209         $(call -ndk-mod-closure-visit,$(_ndk_mod_module))\
    210     )\
    211     $(call -ndk-mod-closure-recursive)\
    212     $(eval _ndk_mod_deps :=)\
    213     $(_ndk_mod_list)\
    214     )
    215 
    216 # Used internally to visit a new node during -ndk-mod-get-closure.
    217 # This appends the node to the work queue, and set its 'visit' flag.
    218 -ndk-mod-closure-visit = \
    219     $(call -ndk-mod-push-back,$1)\
    220     $(call -ndk-mod-tree-set-visited,$1)
    221 
    222 -ndk-mod-closure-recursive = \
    223     $(call -ndk-mod-pop-first)\
    224     $(eval _ndk_mod_list += $$(_ndk_mod_module))\
    225     $(call -ndk-mod-get-depends)\
    226     $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
    227         $(if $(call -ndk-mod-tree-is-visited,$(_ndk_mod_dep)),,\
    228         $(call -ndk-mod-closure-visit,$(_ndk_mod_dep))\
    229         )\
    230     )\
    231     $(if $(_ndk_mod_wq),$(call -ndk-mod-closure-recursive))
    232 
    233 -test-ndk-mod-get-closure.empty = \
    234     $(eval -local-deps = $$($$1_depends))\
    235     $(call test-expect,,$(call -ndk-mod-get-closure,,-local-deps))
    236 
    237 -test-ndk-mod-get-closure.single = \
    238     $(eval -local-deps = $$($$1_depends))\
    239     $(eval A_depends :=)\
    240     $(call test-expect,A,$(call -ndk-mod-get-closure,A,-local-deps))
    241 
    242 -test-ndk-mod-get-closure.double = \
    243     $(eval -local-deps = $$($$1_depends))\
    244     $(eval A_depends := B)\
    245     $(eval B_depends :=)\
    246     $(call test-expect,A B,$(call -ndk-mod-get-closure,A,-local-deps))
    247 
    248 -test-ndk-mod-get-closure.circular-deps = \
    249     $(eval -local-deps = $$($$1_depends))\
    250     $(eval A_depends := B)\
    251     $(eval B_depends := C)\
    252     $(eval C_depends := A)\
    253     $(call test-expect,A B C,$(call -ndk-mod-get-closure,A,-local-deps))
    254 
    255 -test-ndk-mod-get-closure.ABCDE = \
    256     $(eval -local-deps = $$($$1_depends))\
    257     $(eval A_depends := B C)\
    258     $(eval B_depends := D)\
    259     $(eval C_depends := D E)\
    260     $(eval D_depends :=)\
    261     $(eval E_depends :=)\
    262     $(call test-expect,A B C D E,$(call -ndk-mod-get-closure,A,-local-deps))
    263 
    264 
    265 #########################################################################
    266 # For topological sort, we need to count the number of incoming edges
    267 # in each graph node. The following helper functions implement this and
    268 # hide implementation details.
    269 #
    270 # Count the number of incoming edges for each node during topological
    271 # sort with a string of xxxxs. I.e.:
    272 #  0 edge  -> ''
    273 #  1 edge  -> 'x'
    274 #  2 edges -> 'xx'
    275 #  3 edges -> 'xxx'
    276 #  etc.
    277 #########################################################################
    278 
    279 # zero the incoming edge counter for module $1
    280 -ndk-mod-topo-zero-incoming = \
    281     $(eval _ndk_mod_topo_incoming.$1 :=)
    282 
    283 # increment the incoming edge counter for module $1
    284 -ndk-mod-topo-increment-incoming = \
    285     $(eval _ndk_mod_topo_incoming.$1 := $$(_ndk_mod_topo_incoming.$1)x)
    286 
    287 # decrement the incoming edge counter for module $1
    288 -ndk-mod-topo-decrement-incoming = \
    289     $(eval _ndk_mod_topo_incoming.$1 := $$(_ndk_mod_topo_incoming.$1:%x=%))
    290 
    291 # return non-empty if the module $1's incoming edge counter is > 0
    292 -ndk-mod-topo-has-incoming = $(_ndk_mod_topo_incoming.$1)
    293 
    294 # Find first node in a list that has zero incoming edges.
    295 # $1: list of nodes
    296 # Out: first node that has zero incoming edges, or empty.
    297 -ndk-mod-topo-find-first-zero-incoming = $(firstword $(call -ndk-mod-filter-out,$1,-ndk-mod-topo-has-incoming))
    298 
    299 # Only use for debugging:
    300 -ndk-mod-topo-dump-count = \
    301     $(foreach _ndk_mod_module,$1,\
    302         $(info .. $(_ndk_mod_module) incoming='$(_ndk_mod_topo_incoming.$(_ndk_mod_module))'))
    303 
    304 
    305 
    306 #########################################################################
    307 # Return the topologically ordered closure of all nodes from a top-level
    308 # one. This means that a node A, in the result, will always appear after
    309 # node B if A depends on B. Assumes that the graph is a DAG (if there are
    310 # circular dependencies, this property cannot be guaranteed, but at least
    311 # the function should not loop infinitely).
    312 #
    313 # $1: top-level node name.
    314 # $2: dependency function, i.e. $(call $2,<name>) returns the children
    315 #     nodes for <name>.
    316 # Return: list of nodes, include $1, which will always be the first.
    317 #########################################################################
    318 -ndk-mod-get-topo-list = $(strip \
    319     $(eval _ndk_mod_top_module := $1)\
    320     $(eval _ndk_mod_deps_func := $2)\
    321     $(eval _ndk_mod_nodes := $(call -ndk-mod-get-closure,$1,$2))\
    322     $(call -ndk-mod-topo-count,$(_ndk_mod_nodes))\
    323     $(eval _ndk_mod_list :=)\
    324     $(eval _ndk_mod_wq := $(call -ndk-mod-topo-find-first-zero-incoming,$(_ndk_mod_nodes)))\
    325     $(call -ndk-mod-topo-sort)\
    326     $(_ndk_mod_list) $(_ndk_mod_nodes)\
    327     )
    328 
    329 # Given a closure list of nodes, count their incoming edges.
    330 # $1: list of nodes, must be a graph closure.
    331 -ndk-mod-topo-count = \
    332     $(foreach _ndk_mod_module,$1,\
    333         $(call -ndk-mod-topo-zero-incoming,$(_ndk_mod_module)))\
    334     $(foreach _ndk_mod_module,$1,\
    335         $(call -ndk-mod-get-depends)\
    336         $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
    337         $(call -ndk-mod-topo-increment-incoming,$(_ndk_mod_dep))\
    338         )\
    339     )
    340 
    341 -ndk-mod-topo-sort = \
    342     $(call -ndk-topo-debug,-ndk-mod-topo-sort: wq='$(_ndk_mod_wq)' list='$(_ndk_mod_list)')\
    343     $(call -ndk-mod-pop-first)\
    344     $(if $(_ndk_mod_module),\
    345         $(eval _ndk_mod_list += $(_ndk_mod_module))\
    346         $(eval _ndk_mod_nodes := $(filter-out $(_ndk_mod_module),$(_ndk_mod_nodes)))\
    347         $(call -ndk-mod-topo-decrement-incoming,$(_ndk_mod_module))\
    348         $(call -ndk-mod-get-depends)\
    349         $(call -ndk-topo-debug,-ndk-mod-topo-sort:   deps='$(_ndk_mod_depends)')\
    350         $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
    351             $(call -ndk-mod-topo-decrement-incoming,$(_ndk_mod_dep))\
    352             $(if $(call -ndk-mod-topo-has-incoming,$(_ndk_mod_dep)),,\
    353                 $(call -ndk-mod-push-back,$(_ndk_mod_dep))\
    354             )\
    355         )\
    356         $(call -ndk-mod-topo-sort)\
    357     )
    358 
    359 
    360 -test-ndk-mod-get-topo-list.empty = \
    361     $(eval -local-deps = $$($$1_depends))\
    362     $(call test-expect,,$(call -ndk-mod-get-topo-list,,-local-deps))
    363 
    364 -test-ndk-mod-get-topo-list.single = \
    365     $(eval -local-deps = $$($$1_depends))\
    366     $(eval A_depends :=)\
    367     $(call test-expect,A,$(call -ndk-mod-get-topo-list,A,-local-deps))
    368 
    369 -test-ndk-mod-get-topo-list.no-infinite-loop = \
    370     $(eval -local-deps = $$($$1_depends))\
    371     $(eval A_depends := B)\
    372     $(eval B_depends := C)\
    373     $(eval C_depends := A)\
    374     $(call test-expect,A B C,$(call -ndk-mod-get-topo-list,A,-local-deps))
    375 
    376 -test-ndk-mod-get-topo-list.ABC = \
    377     $(eval -local-deps = $$($$1_depends))\
    378     $(eval A_depends := B C)\
    379     $(eval B_depends :=)\
    380     $(eval C_depends := B)\
    381     $(call test-expect,A C B,$(call -ndk-mod-get-topo-list,A,-local-deps))
    382 
    383 -test-ndk-mod-get-topo-list.ABCD = \
    384     $(eval -local-deps = $$($$1_depends))\
    385     $(eval A_depends := B C)\
    386     $(eval B_depends := D)\
    387     $(eval C_depends := B)\
    388     $(eval D_depends :=)\
    389     $(call test-expect,A C B D,$(call -ndk-mod-get-topo-list,A,-local-deps))
    390 
    391 -test-ndk-mod-get-topo-list.ABC.circular = \
    392     $(eval -local-deps = $$($$1_depends))\
    393     $(eval A_depends := B)\
    394     $(eval B_depends := C)\
    395     $(eval C_depends := B)\
    396     $(call test-expect,A B C,$(call -ndk-mod-get-topo-list,A,-local-deps))
    397 
    398 #########################################################################
    399 # Return the topologically ordered closure of all dependencies from a
    400 # top-level node.
    401 #
    402 # $1: top-level node name.
    403 # $2: dependency function, i.e. $(call $2,<name>) returns the children
    404 #     nodes for <name>.
    405 # Return: list of nodes, include $1, which will never be included.
    406 #########################################################################
    407 -ndk-mod-get-topological-depends = $(call rest,$(call -ndk-mod-get-topo-list,$1,$2))
    408 
    409 -test-ndk-mod-get-topological-depends.simple = \
    410     $(eval -local-get-deps = $$($$1_depends))\
    411     $(eval A_depends := B)\
    412     $(eval B_depends :=)\
    413     $(eval topo_deps := $$(call -ndk-mod-get-topological-depends,A,-local-get-deps))\
    414     $(call test-expect,B,$(topo_deps),topo dependencies)
    415 
    416 -test-ndk-mod-get-topological-depends.ABC = \
    417     $(eval -local-get-deps = $$($$1_depends))\
    418     $(eval A_depends := B C)\
    419     $(eval B_depends :=)\
    420     $(eval C_depends := B)\
    421     $(eval bfs_deps := $$(call -ndk-mod-get-bfs-depends,A,-local-get-deps))\
    422     $(eval topo_deps := $$(call -ndk-mod-get-topological-depends,A,-local-get-deps))\
    423     $(call test-expect,B C,$(bfs_deps),dfs dependencies)\
    424     $(call test-expect,C B,$(topo_deps),topo dependencies)
    425 
    426 -test-ndk-mod-get-topological-depends.circular = \
    427     $(eval -local-get-deps = $$($$1_depends))\
    428     $(eval A_depends := B)\
    429     $(eval B_depends := C)\
    430     $(eval C_depends := B)\
    431     $(eval bfs_deps := $$(call -ndk-mod-get-bfs-depends,A,-local-get-deps))\
    432     $(eval topo_deps := $$(call -ndk-mod-get-topological-depends,A,-local-get-deps))\
    433     $(call test-expect,B C,$(bfs_deps),dfs dependencies)\
    434     $(call test-expect,B C,$(topo_deps),topo dependencies)
    435 
    436 #########################################################################
    437 # Return breadth-first walk of a graph, starting from an arbitrary
    438 # node.
    439 #
    440 # This performs a breadth-first walk of the graph and will return a
    441 # list of nodes. Note that $1 will always be the first in the list.
    442 #
    443 # $1: root node name.
    444 # $2: dependency function, i.e. $(call $2,<name>) returns the nodes
    445 #     that <name> depends on.
    446 # Result: list of dependent modules, $1 will be part of it.
    447 #########################################################################
    448 -ndk-mod-get-bfs-list = $(strip \
    449     $(eval _ndk_mod_wq := $(call strip-lib-prefix,$1)) \
    450     $(eval _ndk_mod_deps_func := $2)\
    451     $(eval _ndk_mod_list :=)\
    452     $(call -ndk-mod-tree-setup-visit)\
    453     $(call -ndk-mod-tree-set-visited,$(_ndk_mod_wq))\
    454     $(call -ndk-mod-bfs-recursive) \
    455     $(_ndk_mod_list))
    456 
    457 # Recursive function used to perform a depth-first scan.
    458 # Must initialize _ndk_mod_list, _ndk_mod_field, _ndk_mod_wq
    459 # before calling this.
    460 -ndk-mod-bfs-recursive = \
    461     $(call -ndk-mod-debug,-ndk-mod-bfs-recursive wq='$(_ndk_mod_wq)' list='$(_ndk_mod_list)' visited='$(_ndk_mod_tree_visitors)')\
    462     $(call -ndk-mod-pop-first)\
    463     $(eval _ndk_mod_list += $$(_ndk_mod_module))\
    464     $(call -ndk-mod-get-depends)\
    465     $(call -ndk-mod-debug,.  node='$(_ndk_mod_module)' deps='$(_ndk_mod_depends)')\
    466     $(foreach _ndk_mod_child,$(_ndk_mod_depends),\
    467         $(if $(call -ndk-mod-tree-is-visited,$(_ndk_mod_child)),,\
    468             $(call -ndk-mod-tree-set-visited,$(_ndk_mod_child))\
    469             $(call -ndk-mod-push-back,$(_ndk_mod_child))\
    470         )\
    471     )\
    472     $(if $(_ndk_mod_wq),$(call -ndk-mod-bfs-recursive))
    473 
    474 -test-ndk-mod-get-bfs-list.empty = \
    475     $(eval -local-deps = $$($$1_depends))\
    476     $(call test-expect,,$(call -ndk-mod-get-bfs-list,,-local-deps))
    477 
    478 -test-ndk-mod-get-bfs-list.A = \
    479     $(eval -local-deps = $$($$1_depends))\
    480     $(eval A_depends :=)\
    481     $(call test-expect,A,$(call -ndk-mod-get-bfs-list,A,-local-deps))
    482 
    483 -test-ndk-mod-get-bfs-list.ABCDEF = \
    484     $(eval -local-deps = $$($$1_depends))\
    485     $(eval A_depends := B C)\
    486     $(eval B_depends := D E)\
    487     $(eval C_depends := F E)\
    488     $(eval D_depends :=)\
    489     $(eval E_depends :=)\
    490     $(eval F_depends :=)\
    491     $(call test-expect,A B C D E F,$(call -ndk-mod-get-bfs-list,A,-local-deps))
    492 
    493 #########################################################################
    494 # Return breadth-first walk of a graph, starting from an arbitrary
    495 # node.
    496 #
    497 # This performs a breadth-first walk of the graph and will return a
    498 # list of nodes. Note that $1 will _not_ be part of the list.
    499 #
    500 # $1: root node name.
    501 # $2: dependency function, i.e. $(call $2,<name>) returns the nodes
    502 #     that <name> depends on.
    503 # Result: list of dependent modules, $1 will not be part of it.
    504 #########################################################################
    505 -ndk-mod-get-bfs-depends = $(call rest,$(call -ndk-mod-get-bfs-list,$1,$2))
    506 
    507 -test-ndk-mod-get-bfs-depends.simple = \
    508     $(eval -local-deps-func = $$($$1_depends))\
    509     $(eval A_depends := B)\
    510     $(eval B_depends :=)\
    511     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    512     $(call test-expect,B,$(deps))
    513 
    514 -test-ndk-mod-get-bfs-depends.ABC = \
    515     $(eval -local-deps-func = $$($$1_depends))\
    516     $(eval A_depends := B C)\
    517     $(eval B_depends :=)\
    518     $(eval C_depends := B)\
    519     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    520     $(call test-expect,B C,$(deps))\
    521 
    522 -test-ndk-mod-get-bfs-depends.ABCDE = \
    523     $(eval -local-deps-func = $$($$1_depends))\
    524     $(eval A_depends := B C)\
    525     $(eval B_depends := D)\
    526     $(eval C_depends := D E F)\
    527     $(eval D_depends :=)\
    528     $(eval E_depends :=)\
    529     $(eval F_depends :=)\
    530     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    531     $(call test-expect,B C D E F,$(deps))\
    532 
    533 -test-ndk-mod-get-bfs-depends.loop = \
    534     $(eval -local-deps-func = $$($$1_depends))\
    535     $(eval A_depends := B)\
    536     $(eval B_depends := A)\
    537     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    538     $(call test-expect,B,$(deps))
    539