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#
33ifeq (true,$(_ndk_mod_debug))
34-ndk-mod-debug = $(info $1)
35else
36-ndk-mod-debug := $(empty)
37endif
38
39ifeq (true,$(_ndk_topo_debug))
40-ndk-topo-debug = $(info $1)
41else
42-ndk-topo-debug = $(empty)
43endif
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