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     $(if $(_ndk_mod_wq),\
    326         $(call -ndk-mod-topo-sort)\
    327         $(_ndk_mod_list)\
    328     ,\
    329         $(_ndk_mod_nodes)\
    330     ))
    331 
    332 # Given a closure list of nodes, count their incoming edges.
    333 # $1: list of nodes, must be a graph closure.
    334 -ndk-mod-topo-count = \
    335     $(foreach _ndk_mod_module,$1,\
    336         $(call -ndk-mod-topo-zero-incoming,$(_ndk_mod_module)))\
    337     $(foreach _ndk_mod_module,$1,\
    338         $(call -ndk-mod-get-depends)\
    339         $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
    340         $(call -ndk-mod-topo-increment-incoming,$(_ndk_mod_dep))\
    341         )\
    342     )
    343 
    344 -ndk-mod-topo-sort = \
    345     $(call -ndk-topo-debug,-ndk-mod-topo-sort: wq='$(_ndk_mod_wq)' list='$(_ndk_mod_list)')\
    346     $(call -ndk-mod-pop-first)\
    347     $(if $(_ndk_mod_module),\
    348         $(eval _ndk_mod_list += $(_ndk_mod_module))\
    349         $(call -ndk-mod-topo-decrement-incoming,$(_ndk_mod_module))\
    350         $(call -ndk-mod-get-depends)\
    351         $(call -ndk-topo-debug,-ndk-mod-topo-sort:   deps='$(_ndk_mod_depends)')\
    352         $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
    353             $(call -ndk-mod-topo-decrement-incoming,$(_ndk_mod_dep))\
    354             $(if $(call -ndk-mod-topo-has-incoming,$(_ndk_mod_dep)),,\
    355                 $(call -ndk-mod-push-back,$(_ndk_mod_dep))\
    356             )\
    357         )\
    358         $(call -ndk-mod-topo-sort)\
    359     )
    360 
    361 
    362 -test-ndk-mod-get-topo-list.empty = \
    363     $(eval -local-deps = $$($$1_depends))\
    364     $(call test-expect,,$(call -ndk-mod-get-topo-list,,-local-deps))
    365 
    366 -test-ndk-mod-get-topo-list.single = \
    367     $(eval -local-deps = $$($$1_depends))\
    368     $(eval A_depends :=)\
    369     $(call test-expect,A,$(call -ndk-mod-get-topo-list,A,-local-deps))
    370 
    371 -test-ndk-mod-get-topo-list.no-infinite-loop = \
    372     $(eval -local-deps = $$($$1_depends))\
    373     $(eval A_depends := B)\
    374     $(eval B_depends := C)\
    375     $(eval C_depends := A)\
    376     $(call test-expect,A B C,$(call -ndk-mod-get-topo-list,A,-local-deps))
    377 
    378 -test-ndk-mod-get-topo-list.ABC = \
    379     $(eval -local-deps = $$($$1_depends))\
    380     $(eval A_depends := B C)\
    381     $(eval B_depends :=)\
    382     $(eval C_depends := B)\
    383     $(call test-expect,A C B,$(call -ndk-mod-get-topo-list,A,-local-deps))
    384 
    385 -test-ndk-mod-get-topo-list.ABCD = \
    386     $(eval -local-deps = $$($$1_depends))\
    387     $(eval A_depends := B C)\
    388     $(eval B_depends := D)\
    389     $(eval C_depends := B)\
    390     $(eval D_depends :=)\
    391     $(call test-expect,A C B D,$(call -ndk-mod-get-topo-list,A,-local-deps))
    392 
    393 #########################################################################
    394 # Return the topologically ordered closure of all dependencies from a
    395 # top-level node.
    396 #
    397 # $1: top-level node name.
    398 # $2: dependency function, i.e. $(call $2,<name>) returns the children
    399 #     nodes for <name>.
    400 # Return: list of nodes, include $1, which will never be included.
    401 #########################################################################
    402 -ndk-mod-get-topological-depends = $(call rest,$(call -ndk-mod-get-topo-list,$1,$2))
    403 
    404 -test-ndk-mod-get-topological-depends.simple = \
    405     $(eval -local-get-deps = $$($$1_depends))\
    406     $(eval A_depends := B)\
    407     $(eval B_depends :=)\
    408     $(eval topo_deps := $$(call -ndk-mod-get-topological-depends,A,-local-get-deps))\
    409     $(call test-expect,B,$(topo_deps),topo dependencies)
    410 
    411 -test-ndk-mod-get-topological-depends.ABC = \
    412     $(eval -local-get-deps = $$($$1_depends))\
    413     $(eval A_depends := B C)\
    414     $(eval B_depends :=)\
    415     $(eval C_depends := B)\
    416     $(eval bfs_deps := $$(call -ndk-mod-get-bfs-depends,A,-local-get-deps))\
    417     $(eval topo_deps := $$(call -ndk-mod-get-topological-depends,A,-local-get-deps))\
    418     $(call test-expect,B C,$(bfs_deps),dfs dependencies)\
    419     $(call test-expect,C B,$(topo_deps),topo dependencies)
    420 
    421 #########################################################################
    422 # Return breadth-first walk of a graph, starting from an arbitrary
    423 # node.
    424 #
    425 # This performs a breadth-first walk of the graph and will return a
    426 # list of nodes. Note that $1 will always be the first in the list.
    427 #
    428 # $1: root node name.
    429 # $2: dependency function, i.e. $(call $2,<name>) returns the nodes
    430 #     that <name> depends on.
    431 # Result: list of dependent modules, $1 will be part of it.
    432 #########################################################################
    433 -ndk-mod-get-bfs-list = $(strip \
    434     $(eval _ndk_mod_wq := $(call strip-lib-prefix,$1)) \
    435     $(eval _ndk_mod_deps_func := $2)\
    436     $(eval _ndk_mod_list :=)\
    437     $(call -ndk-mod-tree-setup-visit)\
    438     $(call -ndk-mod-tree-set-visited,$(_ndk_mod_wq))\
    439     $(call -ndk-mod-bfs-recursive) \
    440     $(_ndk_mod_list))
    441 
    442 # Recursive function used to perform a depth-first scan.
    443 # Must initialize _ndk_mod_list, _ndk_mod_field, _ndk_mod_wq
    444 # before calling this.
    445 -ndk-mod-bfs-recursive = \
    446     $(call -ndk-mod-debug,-ndk-mod-bfs-recursive wq='$(_ndk_mod_wq)' list='$(_ndk_mod_list)' visited='$(_ndk_mod_tree_visitors)')\
    447     $(call -ndk-mod-pop-first)\
    448     $(eval _ndk_mod_list += $$(_ndk_mod_module))\
    449     $(call -ndk-mod-get-depends)\
    450     $(call -ndk-mod-debug,.  node='$(_ndk_mod_module)' deps='$(_ndk_mod_depends)')\
    451     $(foreach _ndk_mod_child,$(_ndk_mod_depends),\
    452         $(if $(call -ndk-mod-tree-is-visited,$(_ndk_mod_child)),,\
    453             $(call -ndk-mod-tree-set-visited,$(_ndk_mod_child))\
    454             $(call -ndk-mod-push-back,$(_ndk_mod_child))\
    455         )\
    456     )\
    457     $(if $(_ndk_mod_wq),$(call -ndk-mod-bfs-recursive))
    458 
    459 -test-ndk-mod-get-bfs-list.empty = \
    460     $(eval -local-deps = $$($$1_depends))\
    461     $(call test-expect,,$(call -ndk-mod-get-bfs-list,,-local-deps))
    462 
    463 -test-ndk-mod-get-bfs-list.A = \
    464     $(eval -local-deps = $$($$1_depends))\
    465     $(eval A_depends :=)\
    466     $(call test-expect,A,$(call -ndk-mod-get-bfs-list,A,-local-deps))
    467 
    468 -test-ndk-mod-get-bfs-list.ABCDEF = \
    469     $(eval -local-deps = $$($$1_depends))\
    470     $(eval A_depends := B C)\
    471     $(eval B_depends := D E)\
    472     $(eval C_depends := F E)\
    473     $(eval D_depends :=)\
    474     $(eval E_depends :=)\
    475     $(eval F_depends :=)\
    476     $(call test-expect,A B C D E F,$(call -ndk-mod-get-bfs-list,A,-local-deps))
    477 
    478 #########################################################################
    479 # Return breadth-first walk of a graph, starting from an arbitrary
    480 # node.
    481 #
    482 # This performs a breadth-first walk of the graph and will return a
    483 # list of nodes. Note that $1 will _not_ be part of the list.
    484 #
    485 # $1: root node name.
    486 # $2: dependency function, i.e. $(call $2,<name>) returns the nodes
    487 #     that <name> depends on.
    488 # Result: list of dependent modules, $1 will not be part of it.
    489 #########################################################################
    490 -ndk-mod-get-bfs-depends = $(call rest,$(call -ndk-mod-get-bfs-list,$1,$2))
    491 
    492 -test-ndk-mod-get-bfs-depends.simple = \
    493     $(eval -local-deps-func = $$($$1_depends))\
    494     $(eval A_depends := B)\
    495     $(eval B_depends :=)\
    496     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    497     $(call test-expect,B,$(deps))
    498 
    499 -test-ndk-mod-get-bfs-depends.ABC = \
    500     $(eval -local-deps-func = $$($$1_depends))\
    501     $(eval A_depends := B C)\
    502     $(eval B_depends :=)\
    503     $(eval C_depends := B)\
    504     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    505     $(call test-expect,B C,$(deps))\
    506 
    507 -test-ndk-mod-get-bfs-depends.ABCDE = \
    508     $(eval -local-deps-func = $$($$1_depends))\
    509     $(eval A_depends := B C)\
    510     $(eval B_depends := D)\
    511     $(eval C_depends := D E F)\
    512     $(eval D_depends :=)\
    513     $(eval E_depends :=)\
    514     $(eval F_depends :=)\
    515     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    516     $(call test-expect,B C D E F,$(deps))\
    517 
    518 -test-ndk-mod-get-bfs-depends.loop = \
    519     $(eval -local-deps-func = $$($$1_depends))\
    520     $(eval A_depends := B)\
    521     $(eval B_depends := A)\
    522     $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
    523     $(call test-expect,B,$(deps))
    524