Fix dependency graph computation in ndk-build
This introduces a new definitions-graph.mk file providing
proper topological sorting (with wild unit tests for it),
and make the rest of ndk-build use it.
This solves the incorrect dependency computation demonstrated
by the 'topological-sort' test, which is no longer in BROKEN_BUILD
state after this change. For more information, see
http://b.android.com/39378
Note that this also simplifies the build process a little, i.e.:
- if a shared library or executable depends on several
static libraries, try to build them in parallel, even
if one depends on the other.
- better computation of the list of whole static libraries.
in general, whole libraries are treated like regular ones
now when it comes to computing dependencies. Only at
link time, the libraries that are tagged as 'whole will
be put in a separate function.
There is no unit test for this, I probably need to add
one.
Change-Id: I36d9179e53b0b7bcb7de50e2a1a769c231c28201
diff --git a/build/core/build-binary.mk b/build/core/build-binary.mk
index 45107db..1fa3021 100644
--- a/build/core/build-binary.mk
+++ b/build/core/build-binary.mk
@@ -283,18 +283,6 @@
# Handle the static and shared libraries this module depends on
#
-# Transitive closure of static libraries
-LOCAL_STATIC_LIBRARIES := $(call module-get-depends,$(LOCAL_STATIC_LIBRARIES),STATIC_LIBRARIES)
-LOCAL_WHOLE_STATIC_LIBRARIES := $(call module-get-depends,$(LOCAL_WHOLE_STATIC_LIBRARIES),WHOLE_STATIC_LIBRARIES)
-
-static_libraries := $(call map,module-get-built,$(LOCAL_STATIC_LIBRARIES))
-whole_static_libraries := $(call map,module-get-built,$(LOCAL_WHOLE_STATIC_LIBRARIES))
-
-shared_libraries := $(call map,module-get-built,$(LOCAL_SHARED_LIBRARIES))\
- $(TARGET_PREBUILT_SHARED_LIBRARIES)
-
-$(LOCAL_BUILT_MODULE): $(static_libraries) $(whole_static_libraries) $(shared_libraries)
-
# If LOCAL_LDLIBS contains anything like -l<library> then
# prepend a -L$(SYSROOT)/usr/lib to it to ensure that the linker
# looks in the right location
@@ -303,20 +291,6 @@
LOCAL_LDLIBS := -L$(call host-path,$(SYSROOT)/usr/lib) $(LOCAL_LDLIBS)
endif
-# The list of object/static/shared libraries passed to the linker when
-# building shared libraries and executables. order is important.
-#
-# Cannot use immediate evaluation because PRIVATE_LIBGCC may not be defined at this point.
-linker_objects_and_libraries = $(strip $(call TARGET-get-linker-objects-and-libraries,\
- $(LOCAL_OBJECTS), \
- $(static_libraries), \
- $(whole_static_libraries), \
- $(shared_libraries)))
-
-# The list of object files sent to 'ar' when building static libraries
-#
-ar_objects := $(call host-path,$(LOCAL_OBJECTS))
-
# When LOCAL_SHORT_COMMANDS is defined to 'true' we are going to write the
# list of all object files and/or static/shared libraries that appear on the
# command line to a file, then use the @<listfile> syntax to invoke it.
@@ -328,39 +302,10 @@
ifndef LOCAL_SHORT_COMMANDS
LOCAL_SHORT_COMMANDS := $(strip $(NDK_APP_SHORT_COMMANDS))
endif
-ifeq ($(LOCAL_SHORT_COMMANDS),true)
- # For static and whole static libraries
- ifneq (,$(filter STATIC_LIBRARY WHOLE_STATIC_LIBRARY,$(call module-get-class,$(LOCAL_MODULE))))
- $(call ndk_log,Building static library module '$(LOCAL_MODULE)' with linker list file)
- ar_options := $(ar_objects)
- ar_list_file := $(LOCAL_OBJS_DIR)/archiver.list
- ar_objects := @$(call host-path,$(ar_list_file))
- $(call generate-list-file,$(ar_options),$(ar_list_file))
-
- $(LOCAL_BUILT_MODULE): $(ar_list_file)
- endif
-
- # For shared libraries and executables
- ifneq (,$(filter SHARED_LIBRARY EXECUTABLE,$(call module-get-class,$(LOCAL_MODULE))))
- $(call ndk_log,Building ELF binary module '$(LOCAL_MODULE)' with linker list file)
- linker_options := $(linker_objects_and_libraries)
- linker_list_file := $(LOCAL_OBJS_DIR)/linker.list
- linker_objects_and_libraries := @$(call host-path,$(linker_list_file))
-
- $(call generate-list-file,$(linker_options),$(linker_list_file))
-
- $(LOCAL_BUILT_MODULE): $(linker_list_file)
- endif
-
-endif
$(call generate-file-dir,$(LOCAL_BUILT_MODULE))
-$(LOCAL_BUILT_MODULE): PRIVATE_STATIC_LIBRARIES := $(static_libraries)
-$(LOCAL_BUILT_MODULE): PRIVATE_WHOLE_STATIC_LIBRARIES := $(whole_static_libraries)
-$(LOCAL_BUILT_MODULE): PRIVATE_SHARED_LIBRARIES := $(shared_libraries)
-$(LOCAL_BUILT_MODULE): PRIVATE_OBJECTS := $(LOCAL_OBJECTS)
-$(LOCAL_BUILT_MODULE): PRIVATE_LINKER_OBJECTS_AND_LIBRARIES := $(linker_objects_and_libraries)
+$(LOCAL_BUILT_MODULE): PRIVATE_OBJECTS := $(LOCAL_OBJECTS)
$(LOCAL_BUILT_MODULE): PRIVATE_LIBGCC := $(TARGET_LIBGCC)
$(LOCAL_BUILT_MODULE): PRIVATE_LD := $(TARGET_LD)
@@ -370,29 +315,137 @@
$(LOCAL_BUILT_MODULE): PRIVATE_NAME := $(notdir $(LOCAL_BUILT_MODULE))
$(LOCAL_BUILT_MODULE): PRIVATE_CXX := $(TARGET_CXX)
$(LOCAL_BUILT_MODULE): PRIVATE_CC := $(TARGET_CC)
-$(LOCAL_BUILT_MODULE): PRIVATE_AR := $(TARGET_AR) $(TARGET_ARFLAGS)
-$(LOCAL_BUILT_MODULE): PRIVATE_AR_OBJECTS := $(ar_objects)
$(LOCAL_BUILT_MODULE): PRIVATE_SYSROOT := $(SYSROOT)
-$(LOCAL_BUILT_MODULE): PRIVATE_BUILD_SHARED_LIB := $(cmd-build-shared-library)
-$(LOCAL_BUILT_MODULE): PRIVATE_BUILD_STATIC_LIB := $(cmd-build-static-library)
-$(LOCAL_BUILT_MODULE): PRIVATE_BUILD_EXECUTABLE := $(cmd-build-executable)
+
+ifeq ($(call module-get-class,$(LOCAL_MODULE)),STATIC_LIBRARY)
#
-# If this is a static library module
+# This is a static library module, things are very easy. We only need
+# to build the object files and archive them with 'ar'. Note that module
+# dependencies can be ignored here, i.e. if the module depends on other
+# static or shared libraries, there is no need to actually build them
+# before, so don't add Make dependencies to them.
#
-ifeq ($(call module-get-class,$(LOCAL_MODULE)),STATIC_LIBRARY)
+# In other words, consider the following graph:
+#
+# libfoo.so -> libA.a ->libB.a
+#
+# then libA.a and libB.a can be built in parallel, only linking libfoo.so
+# depends on their completion.
+#
+
+ar_objects := $(call host-path,$(LOCAL_OBJECTS))
+
+ifeq ($(LOCAL_SHORT_COMMANDS),true)
+ $(call ndk_log,Building static library module '$(LOCAL_MODULE)' with linker list file)
+ ar_list_file := $(LOCAL_OBJS_DIR)/archiver.list
+ $(call generate-list-file,$(ar_objects),$(ar_list_file))
+ ar_objects := @$(call host-path,$(ar_list_file))
+ $(LOCAL_BUILT_MODULE): $(ar_list_file)
+endif
+
+$(LOCAL_BUILT_MODULE): PRIVATE_AR := $(TARGET_AR) $(TARGET_ARFLAGS)
+$(LOCAL_BUILT_MODULE): PRIVATE_AR_OBJECTS := $(ar_objects)
+$(LOCAL_BUILT_MODULE): PRIVATE_BUILD_STATIC_LIB := $(cmd-build-static-library)
+
$(LOCAL_BUILT_MODULE): $(LOCAL_OBJECTS)
@ $(HOST_ECHO) "StaticLibrary : $(PRIVATE_NAME)"
$(hide) $(call host-rm,$@)
$(hide) $(PRIVATE_BUILD_STATIC_LIB)
ALL_STATIC_LIBRARIES += $(LOCAL_BUILT_MODULE)
+
+endif
+
+ifneq (,$(filter SHARED_LIBRARY EXECUTABLE,$(call module-get-class,$(LOCAL_MODULE))))
+
+#
+# This is a shared library or an executable, so computing dependencies properly is
+# crucial. The general rule to apply is the following:
+#
+# - collect the list of all static libraries that need to be part
+# of the link, and in the right order. To do so, get the transitive
+# closure of LOCAL_STATIC_LIBRARIES and LOCAL_WHOLE_STATIC_LIBRARIES
+# and ensure they are ordered topologically.
+#
+# - collect the list of all shared libraries that need to be part of
+# the link. This is the transitive closure of the list of
+# LOCAL_SHARED_LIBRARIES for the module and all its dependent static
+# libraries identified in the step above. Of course, need to be
+# ordered topologically too.
+#
+# - add Make dependencies to ensure that all these libs are built
+# before the module itself too.
+#
+# A few quick examples:
+#
+# main.exe -> libA.a -> libB.a -> libfoo.so -> libC.a
+#
+# static_libs(main.exe) = libA.a libB.a (i.e. no libC.a)
+# shared_libs(main.exe) = libfoo.so
+# static_libs(libfoo.so) = libC.a
+#
+# main.exe -> libA.a ---> libB.a
+# | ^
+# v |
+# libC.a ------
+#
+# static_libs(main.exe) = libA.a libC.a libB.a
+# (i.e. libB.a must appear after all libraries that depend on it).
+#
+all_libs := $(call module-get-link-libs,$(LOCAL_MODULE))
+shared_libs := $(call module-filter-shared-libraries,$(all_libs))
+static_libs := $(call module-filter-static-libraries,$(all_libs))
+whole_static_libs := $(call module-extract-whole-static-libs,$(LOCAL_MODULE),$(static_libs))
+static_libs := $(filter-out $(whole_static_libs),$(static_libs))
+
+$(call -ndk-mod-debug,module $(LOCAL_MODULE) [$(LOCAL_BUILT_MODULE)])
+$(call -ndk-mod-debug,. all_libs='$(all_libs)')
+$(call -ndk-mod-debug,. shared_libs='$(shared_libs)')
+$(call -ndk-mod-debug,. static_libs='$(static_libs)')
+$(call -ndk-mod-debug,. whole_static_libs='$(whole_static_libs)')
+
+shared_libs := $(call map,module-get-built,$(shared_libs))\
+ $(TARGET_PREBUILT_SHARED_LIBRARIES)
+static_libs := $(call map,module-get-built,$(static_libs))
+whole_static_libs := $(call map,module-get-built,$(whole_static_libs))
+
+$(call -ndk-mod-debug,. built_shared_libs='$(shared_libs)')
+$(call -ndk-mod-debug,. built_static_libs='$(static_libs)')
+$(call -ndk-mod-debug,. built_whole_static_libs='$(whole_static_libs)')
+
+ifeq ($(LOCAL_SHORT_COMMANDS),true)
+ $(call ndk_log,Building ELF binary module '$(LOCAL_MODULE)' with linker list file)
+ linker_options := $(linker_objects_and_libraries)
+ linker_list_file := $(LOCAL_OBJS_DIR)/linker.list
+ linker_objects_and_libraries := @$(call host-path,$(linker_list_file))
+ $(call generate-list-file,$(linker_options),$(linker_list_file))
+ $(LOCAL_BUILT_MODULE): $(linker_list_file)
+endif
+
+# The list of object/static/shared libraries passed to the linker when
+# building shared libraries and executables. order is important.
+#
+# Cannot use immediate evaluation because PRIVATE_LIBGCC may not be defined at this point.
+linker_objects_and_libraries = $(strip $(call TARGET-get-linker-objects-and-libraries,\
+ $(LOCAL_OBJECTS), \
+ $(static_libs), \
+ $(whole_static_libs), \
+ $(shared_libs)))
+
+$(LOCAL_BUILT_MODULE): $(shared_libs) $(static_libs) $(whole_static_libs)
+$(LOCAL_BUILT_MODULE): PRIVATE_LINKER_OBJECTS_AND_LIBRARIES := $(linker_objects_and_libraries)
+$(LOCAL_BUILT_MODULE): PRIVATE_STATIC_LIBRARIES := $(static_libs)
+$(LOCAL_BUILT_MODULE): PRIVATE_WHOLE_STATIC_LIBRARIES := $(whole_static_libs))
+$(LOCAL_BUILT_MODULE): PRIVATE_SHARED_LIBRARIES := $(shared_libs))
+
endif
#
# If this is a shared library module
#
ifeq ($(call module-get-class,$(LOCAL_MODULE)),SHARED_LIBRARY)
+$(LOCAL_BUILT_MODULE): PRIVATE_BUILD_SHARED_LIB := $(cmd-build-shared-library)
$(LOCAL_BUILT_MODULE): $(LOCAL_OBJECTS)
@ $(HOST_ECHO) "SharedLibrary : $(PRIVATE_NAME)"
$(hide) $(PRIVATE_BUILD_SHARED_LIB)
@@ -404,6 +457,7 @@
# If this is an executable module
#
ifeq ($(call module-get-class,$(LOCAL_MODULE)),EXECUTABLE)
+$(LOCAL_BUILT_MODULE): PRIVATE_BUILD_EXECUTABLE := $(cmd-build-executable)
$(LOCAL_BUILT_MODULE): $(LOCAL_OBJECTS)
@ $(HOST_ECHO) "Executable : $(PRIVATE_NAME)"
$(hide) $(PRIVATE_BUILD_EXECUTABLE)
diff --git a/build/core/definitions-graph.mk b/build/core/definitions-graph.mk
new file mode 100644
index 0000000..6652a1f
--- /dev/null
+++ b/build/core/definitions-graph.mk
@@ -0,0 +1,523 @@
+# Copyright (C) 2012 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+#
+# Definitions of various graph-related generic functions, used by
+# ndk-build internally.
+#
+
+# Coding style note:
+#
+# All internal variables in this file begin with '_ndk_mod_'
+# All internal functions in this file begin with '-ndk-mod-'
+#
+
+# Set this to true if you want to debug the functions here.
+_ndk_mod_debug := $(if $(NDK_DEBUG_MODULES),true)
+_ndk_topo_debug := $(if $(NDK_DEBUG_TOPO),true)
+
+# Use $(call -ndk-mod-debug,<message>) to print a debug message only
+# if _ndk_mod_debug is set to 'true'. Useful for debugging the functions
+# available here.
+#
+ifeq (true,$(_ndk_mod_debug))
+-ndk-mod-debug = $(info $1)
+else
+-ndk-mod-debug := $(empty)
+endif
+
+ifeq (true,$(_ndk_topo_debug))
+-ndk-topo-debug = $(info $1)
+else
+-ndk-topo-debug = $(empty)
+endif
+
+#######################################################################
+# Filter a list of module with a predicate function
+# $1: list of module names.
+# $2: predicate function, will be called with $(call $2,<name>), if the
+# result is not empty, <name> will be added to the result.
+# Out: subset of input list, where each item passes the predicate.
+#######################################################################
+-ndk-mod-filter = $(strip \
+ $(foreach _ndk_mod_filter_n,$1,\
+ $(if $(call $2,$(_ndk_mod_filter_n)),$(_ndk_mod_filter_n))\
+ ))
+
+-test-ndk-mod-filter = \
+ $(eval -local-func = $$(call seq,foo,$$1))\
+ $(call test-expect,,$(call -ndk-mod-filter,,-local-func))\
+ $(call test-expect,foo,$(call -ndk-mod-filter,foo,-local-func))\
+ $(call test-expect,foo,$(call -ndk-mod-filter,foo bar,-local-func))\
+ $(call test-expect,foo foo,$(call -ndk-mod-filter,aaa foo bar foo,-local-func))\
+ $(eval -local-func = $$(call sne,foo,$$1))\
+ $(call test-expect,,$(call -ndk-mod-filter,,-local-func))\
+ $(call test-expect,,$(call -ndk-mod-filter,foo,-local-func))\
+ $(call test-expect,bar,$(call -ndk-mod-filter,foo bar,-local-func))\
+ $(call test-expect,aaa bar,$(call -ndk-mod-filter,aaa foo bar,-local-func))
+
+
+#######################################################################
+# Filter out a list of modules with a predicate function
+# $1: list of module names.
+# $2: predicate function, will be called with $(call $2,<name>), if the
+# result is not empty, <name> will be added to the result.
+# Out: subset of input list, where each item doesn't pass the predicate.
+#######################################################################
+-ndk-mod-filter-out = $(strip \
+ $(foreach _ndk_mod_filter_n,$1,\
+ $(if $(call $2,$(_ndk_mod_filter_n)),,$(_ndk_mod_filter_n))\
+ ))
+
+-test-ndk-mod-filter-out = \
+ $(eval -local-func = $$(call seq,foo,$$1))\
+ $(call test-expect,,$(call -ndk-mod-filter-out,,-local-func))\
+ $(call test-expect,,$(call -ndk-mod-filter-out,foo,-local-func))\
+ $(call test-expect,bar,$(call -ndk-mod-filter-out,foo bar,-local-func))\
+ $(call test-expect,aaa bar,$(call -ndk-mod-filter-out,aaa foo bar foo,-local-func))\
+ $(eval -local-func = $$(call sne,foo,$$1))\
+ $(call test-expect,,$(call -ndk-mod-filter-out,,-local-func))\
+ $(call test-expect,foo,$(call -ndk-mod-filter-out,foo,-local-func))\
+ $(call test-expect,foo,$(call -ndk-mod-filter-out,foo bar,-local-func))\
+ $(call test-expect,foo foo,$(call -ndk-mod-filter-out,aaa foo bar foo,-local-func))
+
+
+#######################################################################
+# Find the first item in a list that checks a valid predicate.
+# $1: list of names.
+# $2: predicate function, will be called with $(call $2,<name>), if the
+# result is not empty, <name> will be added to the result.
+# Out: subset of input list.
+#######################################################################
+-ndk-mod-find-first = $(firstword $(call -ndk-mod-filter,$1,$2))
+
+-test-ndk-mod-find-first.empty = \
+ $(eval -local-pred = $$(call seq,foo,$$1))\
+ $(call test-expect,,$(call -ndk-mod-find-first,,-local-pred))\
+ $(call test-expect,,$(call -ndk-mod-find-first,bar,-local-pred))
+
+-test-ndk-mod-find-first.simple = \
+ $(eval -local-pred = $$(call seq,foo,$$1))\
+ $(call test-expect,foo,$(call -ndk-mod-find-first,foo,-local-pred))\
+ $(call test-expect,foo,$(call -ndk-mod-find-first,aaa foo bar,-local-pred))\
+ $(call test-expect,foo,$(call -ndk-mod-find-first,aaa foo foo bar,-local-pred))
+
+########################################################################
+# Many tree walking operations require setting a 'visited' flag on
+# specific graph nodes. The following helper functions help implement
+# this while hiding details to the callers.
+#
+# Technical note:
+# _ndk_mod_tree_visited.<name> will be 'true' if the node was visited,
+# or empty otherwise.
+#
+# _ndk_mod_tree_visitors lists all visited nodes, used to clean all
+# _ndk_mod_tree_visited.<name> variables in -ndk-mod-tree-setup-visit.
+#
+#######################################################################
+
+# Call this before tree traversal.
+-ndk-mod-tree-setup-visit = \
+ $(foreach _ndk_mod_tree_visitor,$(_ndk_mod_tree_visitors),\
+ $(eval _ndk_mod_tree_visited.$$(_ndk_mod_tree_visitor) :=))\
+ $(eval _ndk_mod_tree_visitors :=)
+
+# Returns non-empty if a node was visited.
+-ndk-mod-tree-is-visited = \
+ $(_ndk_mod_tree_visited.$1)
+
+# Set the visited state of a node to 'true'
+-ndk-mod-tree-set-visited = \
+ $(eval _ndk_mod_tree_visited.$1 := true)\
+ $(eval _ndk_mod_tree_visitors += $1)
+
+########################################################################
+# Many graph walking operations require a work queue and computing
+# dependencies / children nodes. Here are a few helper functions that
+# can be used to make their code clearer. This uses a few global
+# variables that should be defined as follows during the operation:
+#
+# _ndk_mod_module current graph node name.
+# _ndk_mod_wq current node work queue.
+# _ndk_mod_list current result (list of nodes).
+# _ndk_mod_depends current graph node's children.
+# you must call -ndk-mod-get-depends to set this.
+#
+#######################################################################
+
+# Pop first item from work-queue into _ndk_mod_module.
+-ndk-mod-pop-first = \
+ $(eval _ndk_mod_module := $$(call first,$$(_ndk_mod_wq)))\
+ $(eval _ndk_mod_wq := $$(call rest,$$(_ndk_mod_wq)))
+
+-test-ndk-mod-pop-first = \
+ $(eval _ndk_mod_wq := A B C)\
+ $(call -ndk-mod-pop-first)\
+ $(call test-expect,A,$(_ndk_mod_module))\
+ $(call test-expect,B C,$(_ndk_mod_wq))\
+
+
+# Push list of items at the back of the work-queue.
+-ndk-mod-push-back = \
+ $(eval _ndk_mod_wq := $(strip $(_ndk_mod_wq) $1))
+
+-test-ndk-mod-push-back = \
+ $(eval _ndk_mod_wq := A B C)\
+ $(call -ndk-mod-push-back, D E)\
+ $(call test-expect,A B C D E,$(_ndk_mod_wq))
+
+# Set _ndk_mod_depends to the direct dependencies of _ndk_mod_module
+-ndk-mod-get-depends = \
+ $(eval _ndk_mod_depends := $$(call $$(_ndk_mod_deps_func),$$(_ndk_mod_module)))
+
+# Set _ndk_mod_depends to the direct dependencies of _ndk_mod_module that
+# are not already in _ndk_mod_list.
+-ndk-mod-get-new-depends = \
+ $(call -ndk-mod-get-depends)\
+ $(eval _ndk_mod_depends := $$(filter-out $$(_ndk_mod_list),$$(_ndk_mod_depends)))
+
+##########################################################################
+# Compute the transitive closure
+# $1: list of modules.
+# $2: dependency function, $(call $2,<module>) should return all the
+# module that <module> depends on.
+# Out: transitive closure of all modules from those in $1. Always includes
+# the modules in $1. Order is random.
+#
+# Implementation note:
+# we use the -ndk-mod-tree-xxx functions to flag 'visited' nodes
+# in the graph. A node is visited once it has been put into the work
+# queue. For each item in the work queue, get the dependencies and
+# append all those that were not visited yet.
+#######################################################################
+-ndk-mod-get-closure = $(strip \
+ $(eval _ndk_mod_wq :=)\
+ $(eval _ndk_mod_list :=)\
+ $(eval _ndk_mod_deps_func := $2)\
+ $(call -ndk-mod-tree-setup-visit)\
+ $(foreach _ndk_mod_module,$1,\
+ $(call -ndk-mod-closure-visit,$(_ndk_mod_module))\
+ )\
+ $(call -ndk-mod-closure-recursive)\
+ $(eval _ndk_mod_deps :=)\
+ $(_ndk_mod_list)\
+ )
+
+# Used internally to visit a new node during -ndk-mod-get-closure.
+# This appends the node to the work queue, and set its 'visit' flag.
+-ndk-mod-closure-visit = \
+ $(call -ndk-mod-push-back,$1)\
+ $(call -ndk-mod-tree-set-visited,$1)
+
+-ndk-mod-closure-recursive = \
+ $(call -ndk-mod-pop-first)\
+ $(eval _ndk_mod_list += $$(_ndk_mod_module))\
+ $(call -ndk-mod-get-depends)\
+ $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
+ $(if $(call -ndk-mod-tree-is-visited,$(_ndk_mod_dep)),,\
+ $(call -ndk-mod-closure-visit,$(_ndk_mod_dep))\
+ )\
+ )\
+ $(if $(_ndk_mod_wq),$(call -ndk-mod-closure-recursive))
+
+-test-ndk-mod-get-closure.empty = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(call test-expect,,$(call -ndk-mod-get-closure,,-local-deps))
+
+-test-ndk-mod-get-closure.single = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends :=)\
+ $(call test-expect,A,$(call -ndk-mod-get-closure,A,-local-deps))
+
+-test-ndk-mod-get-closure.double = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends := B)\
+ $(eval B_depends :=)\
+ $(call test-expect,A B,$(call -ndk-mod-get-closure,A,-local-deps))
+
+-test-ndk-mod-get-closure.circular-deps = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends := B)\
+ $(eval B_depends := C)\
+ $(eval C_depends := A)\
+ $(call test-expect,A B C,$(call -ndk-mod-get-closure,A,-local-deps))
+
+-test-ndk-mod-get-closure.ABCDE = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends := B C)\
+ $(eval B_depends := D)\
+ $(eval C_depends := D E)\
+ $(eval D_depends :=)\
+ $(eval E_depends :=)\
+ $(call test-expect,A B C D E,$(call -ndk-mod-get-closure,A,-local-deps))
+
+
+#########################################################################
+# For topological sort, we need to count the number of incoming edges
+# in each graph node. The following helper functions implement this and
+# hide implementation details.
+#
+# Count the number of incoming edges for each node during topological
+# sort with a string of xxxxs. I.e.:
+# 0 edge -> ''
+# 1 edge -> 'x'
+# 2 edges -> 'xx'
+# 3 edges -> 'xxx'
+# etc.
+#########################################################################
+
+# zero the incoming edge counter for module $1
+-ndk-mod-topo-zero-incoming = \
+ $(eval _ndk_mod_topo_incoming.$1 :=)
+
+# increment the incoming edge counter for module $1
+-ndk-mod-topo-increment-incoming = \
+ $(eval _ndk_mod_topo_incoming.$1 := $$(_ndk_mod_topo_incoming.$1)x)
+
+# decrement the incoming edge counter for module $1
+-ndk-mod-topo-decrement-incoming = \
+ $(eval _ndk_mod_topo_incoming.$1 := $$(_ndk_mod_topo_incoming.$1:%x=%))
+
+# return non-empty if the module $1's incoming edge counter is > 0
+-ndk-mod-topo-has-incoming = $(_ndk_mod_topo_incoming.$1)
+
+# Find first node in a list that has zero incoming edges.
+# $1: list of nodes
+# Out: first node that has zero incoming edges, or empty.
+-ndk-mod-topo-find-first-zero-incoming = $(firstword $(call -ndk-mod-filter-out,$1,-ndk-mod-topo-has-incoming))
+
+# Only use for debugging:
+-ndk-mod-topo-dump-count = \
+ $(foreach _ndk_mod_module,$1,\
+ $(info .. $(_ndk_mod_module) incoming='$(_ndk_mod_topo_incoming.$(_ndk_mod_module))'))
+
+
+
+#########################################################################
+# Return the topologically ordered closure of all nodes from a top-level
+# one. This means that a node A, in the result, will always appear after
+# node B if A depends on B. Assumes that the graph is a DAG (if there are
+# circular dependencies, this property cannot be guaranteed, but at least
+# the function should not loop infinitely).
+#
+# $1: top-level node name.
+# $2: dependency function, i.e. $(call $2,<name>) returns the children
+# nodes for <name>.
+# Return: list of nodes, include $1, which will always be the first.
+#########################################################################
+-ndk-mod-get-topo-list = $(strip \
+ $(eval _ndk_mod_top_module := $1)\
+ $(eval _ndk_mod_deps_func := $2)\
+ $(eval _ndk_mod_nodes := $(call -ndk-mod-get-closure,$1,$2))\
+ $(call -ndk-mod-topo-count,$(_ndk_mod_nodes))\
+ $(eval _ndk_mod_list :=)\
+ $(eval _ndk_mod_wq := $(call -ndk-mod-topo-find-first-zero-incoming,$(_ndk_mod_nodes)))\
+ $(if $(_ndk_mod_wq),\
+ $(call -ndk-mod-topo-sort)\
+ $(_ndk_mod_list)\
+ ,\
+ $(_ndk_mod_nodes)\
+ ))
+
+# Given a closure list of nodes, count their incoming edges.
+# $1: list of nodes, must be a graph closure.
+-ndk-mod-topo-count = \
+ $(foreach _ndk_mod_module,$1,\
+ $(call -ndk-mod-topo-zero-incoming,$(_ndk_mod_module)))\
+ $(foreach _ndk_mod_module,$1,\
+ $(call -ndk-mod-get-depends)\
+ $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
+ $(call -ndk-mod-topo-increment-incoming,$(_ndk_mod_dep))\
+ )\
+ )
+
+-ndk-mod-topo-sort = \
+ $(call -ndk-topo-debug,-ndk-mod-topo-sort: wq='$(_ndk_mod_wq)' list='$(_ndk_mod_list)')\
+ $(call -ndk-mod-pop-first)\
+ $(if $(_ndk_mod_module),\
+ $(eval _ndk_mod_list += $(_ndk_mod_module))\
+ $(call -ndk-mod-topo-decrement-incoming,$(_ndk_mod_module))\
+ $(call -ndk-mod-get-depends)\
+ $(call -ndk-topo-debug,-ndk-mod-topo-sort: deps='$(_ndk_mod_depends)')\
+ $(foreach _ndk_mod_dep,$(_ndk_mod_depends),\
+ $(call -ndk-mod-topo-decrement-incoming,$(_ndk_mod_dep))\
+ $(if $(call -ndk-mod-topo-has-incoming,$(_ndk_mod_dep)),,\
+ $(call -ndk-mod-push-back,$(_ndk_mod_dep))\
+ )\
+ )\
+ $(call -ndk-mod-topo-sort)\
+ )
+
+
+-test-ndk-mod-get-topo-list.empty = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(call test-expect,,$(call -ndk-mod-get-topo-list,,-local-deps))
+
+-test-ndk-mod-get-topo-list.single = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends :=)\
+ $(call test-expect,A,$(call -ndk-mod-get-topo-list,A,-local-deps))
+
+-test-ndk-mod-get-topo-list.no-infinite-loop = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends := B)\
+ $(eval B_depends := C)\
+ $(eval C_depends := A)\
+ $(call test-expect,A B C,$(call -ndk-mod-get-topo-list,A,-local-deps))
+
+-test-ndk-mod-get-topo-list.ABC = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends := B C)\
+ $(eval B_depends :=)\
+ $(eval C_depends := B)\
+ $(call test-expect,A C B,$(call -ndk-mod-get-topo-list,A,-local-deps))
+
+-test-ndk-mod-get-topo-list.ABCD = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends := B C)\
+ $(eval B_depends := D)\
+ $(eval C_depends := B)\
+ $(eval D_depends :=)\
+ $(call test-expect,A C B D,$(call -ndk-mod-get-topo-list,A,-local-deps))
+
+#########################################################################
+# Return the topologically ordered closure of all dependencies from a
+# top-level node.
+#
+# $1: top-level node name.
+# $2: dependency function, i.e. $(call $2,<name>) returns the children
+# nodes for <name>.
+# Return: list of nodes, include $1, which will never be included.
+#########################################################################
+-ndk-mod-get-topological-depends = $(call rest,$(call -ndk-mod-get-topo-list,$1,$2))
+
+-test-ndk-mod-get-topological-depends.simple = \
+ $(eval -local-get-deps = $$($$1_depends))\
+ $(eval A_depends := B)\
+ $(eval B_depends :=)\
+ $(eval topo_deps := $$(call -ndk-mod-get-topological-depends,A,-local-get-deps))\
+ $(call test-expect,B,$(topo_deps),topo dependencies)
+
+-test-ndk-mod-get-topological-depends.ABC = \
+ $(eval -local-get-deps = $$($$1_depends))\
+ $(eval A_depends := B C)\
+ $(eval B_depends :=)\
+ $(eval C_depends := B)\
+ $(eval bfs_deps := $$(call -ndk-mod-get-bfs-depends,A,-local-get-deps))\
+ $(eval topo_deps := $$(call -ndk-mod-get-topological-depends,A,-local-get-deps))\
+ $(call test-expect,B C,$(bfs_deps),dfs dependencies)\
+ $(call test-expect,C B,$(topo_deps),topo dependencies)
+
+#########################################################################
+# Return breadth-first walk of a graph, starting from an arbitrary
+# node.
+#
+# This performs a breadth-first walk of the graph and will return a
+# list of nodes. Note that $1 will always be the first in the list.
+#
+# $1: root node name.
+# $2: dependency function, i.e. $(call $2,<name>) returns the nodes
+# that <name> depends on.
+# Result: list of dependent modules, $1 will be part of it.
+#########################################################################
+-ndk-mod-get-bfs-list = $(strip \
+ $(eval _ndk_mod_wq := $(call strip-lib-prefix,$1)) \
+ $(eval _ndk_mod_deps_func := $2)\
+ $(eval _ndk_mod_list :=)\
+ $(call -ndk-mod-tree-setup-visit)\
+ $(call -ndk-mod-tree-set-visited,$(_ndk_mod_wq))\
+ $(call -ndk-mod-bfs-recursive) \
+ $(_ndk_mod_list))
+
+# Recursive function used to perform a depth-first scan.
+# Must initialize _ndk_mod_list, _ndk_mod_field, _ndk_mod_wq
+# before calling this.
+-ndk-mod-bfs-recursive = \
+ $(call -ndk-mod-debug,-ndk-mod-bfs-recursive wq='$(_ndk_mod_wq)' list='$(_ndk_mod_list)' visited='$(_ndk_mod_tree_visitors)')\
+ $(call -ndk-mod-pop-first)\
+ $(eval _ndk_mod_list += $$(_ndk_mod_module))\
+ $(call -ndk-mod-get-depends)\
+ $(call -ndk-mod-debug,. node='$(_ndk_mod_module)' deps='$(_ndk_mod_depends)')\
+ $(foreach _ndk_mod_child,$(_ndk_mod_depends),\
+ $(if $(call -ndk-mod-tree-is-visited,$(_ndk_mod_child)),,\
+ $(call -ndk-mod-tree-set-visited,$(_ndk_mod_child))\
+ $(call -ndk-mod-push-back,$(_ndk_mod_child))\
+ )\
+ )\
+ $(if $(_ndk_mod_wq),$(call -ndk-mod-bfs-recursive))
+
+-test-ndk-mod-get-bfs-list.empty = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(call test-expect,,$(call -ndk-mod-get-bfs-list,,-local-deps))
+
+-test-ndk-mod-get-bfs-list.A = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends :=)\
+ $(call test-expect,A,$(call -ndk-mod-get-bfs-list,A,-local-deps))
+
+-test-ndk-mod-get-bfs-list.ABCDEF = \
+ $(eval -local-deps = $$($$1_depends))\
+ $(eval A_depends := B C)\
+ $(eval B_depends := D E)\
+ $(eval C_depends := F E)\
+ $(eval D_depends :=)\
+ $(eval E_depends :=)\
+ $(eval F_depends :=)\
+ $(call test-expect,A B C D E F,$(call -ndk-mod-get-bfs-list,A,-local-deps))
+
+#########################################################################
+# Return breadth-first walk of a graph, starting from an arbitrary
+# node.
+#
+# This performs a breadth-first walk of the graph and will return a
+# list of nodes. Note that $1 will _not_ be part of the list.
+#
+# $1: root node name.
+# $2: dependency function, i.e. $(call $2,<name>) returns the nodes
+# that <name> depends on.
+# Result: list of dependent modules, $1 will not be part of it.
+#########################################################################
+-ndk-mod-get-bfs-depends = $(call rest,$(call -ndk-mod-get-bfs-list,$1,$2))
+
+-test-ndk-mod-get-bfs-depends.simple = \
+ $(eval -local-deps-func = $$($$1_depends))\
+ $(eval A_depends := B)\
+ $(eval B_depends :=)\
+ $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
+ $(call test-expect,B,$(deps))
+
+-test-ndk-mod-get-bfs-depends.ABC = \
+ $(eval -local-deps-func = $$($$1_depends))\
+ $(eval A_depends := B C)\
+ $(eval B_depends :=)\
+ $(eval C_depends := B)\
+ $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
+ $(call test-expect,B C,$(deps))\
+
+-test-ndk-mod-get-bfs-depends.ABCDE = \
+ $(eval -local-deps-func = $$($$1_depends))\
+ $(eval A_depends := B C)\
+ $(eval B_depends := D)\
+ $(eval C_depends := D E F)\
+ $(eval D_depends :=)\
+ $(eval E_depends :=)\
+ $(eval F_depends :=)\
+ $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
+ $(call test-expect,B C D E F,$(deps))\
+
+-test-ndk-mod-get-bfs-depends.loop = \
+ $(eval -local-deps-func = $$($$1_depends))\
+ $(eval A_depends := B)\
+ $(eval B_depends := A)\
+ $(eval deps := $$(call -ndk-mod-get-bfs-depends,A,-local-deps-func))\
+ $(call test-expect,B,$(deps))
diff --git a/build/core/definitions-host.mk b/build/core/definitions-host.mk
index 136252a..c215687 100644
--- a/build/core/definitions-host.mk
+++ b/build/core/definitions-host.mk
@@ -121,16 +121,16 @@
endif
# -----------------------------------------------------------------------------
-# Function : copy-if-differ
+# Function : host-copy-if-differ
# Arguments: 1: source file
# 2: destination file
-# Usage : $(call copy-if-differ,<src-file>,<dst-file>)
+# Usage : $(call host-copy-if-differ,<src-file>,<dst-file>)
# Rationale: This function copy source file to destination file if contents are
# different.
# -----------------------------------------------------------------------------
ifeq ($(HOST_OS),windows)
-copy-if-differ = $(HOST_CMP) -s $1 $2 > NUL || copy /b/y $(subst /,\,"$1" "$2") > NUL
+host-copy-if-differ = $(HOST_CMP) -s $1 $2 > NUL || copy /b/y $(subst /,\,"$1" "$2") > NUL
else
-copy-if-differ = $(HOST_CMP) -s $1 $2 > /dev/null 2>&1 || cp -f $1 $2
+host-copy-if-differ = $(HOST_CMP) -s $1 $2 > /dev/null 2>&1 || cp -f $1 $2
endif
diff --git a/build/core/definitions-utils.mk b/build/core/definitions-utils.mk
index 23f70ca..0f24404 100644
--- a/build/core/definitions-utils.mk
+++ b/build/core/definitions-utils.mk
@@ -150,68 +150,6 @@
$(call test-expect,foo,$(call parent-dir,foo/bar))\
$(call test-expect,foo,$(call parent-dir,foo/bar/))
-
-###########################################################################
-# Internal function used by modules-get-closure
-# Compute the closure of a node in a graph.
-# $1: list of graph nodes
-# $2: dependency function, i.e. $(call $2,<name>) should return the list
-# of nodes that <name> depends on.
-# Out: list of nodes. This are all the nodes that depend on those in $1
-# transitively.
-#
-get-closure = $(strip \
- $(eval __closure_list := $1) \
- $(eval __closure_wq := $1) \
- $(eval __closure_deps_func := $2) \
- $(call get-closure-recursive)\
- $(__closure_list))
-
-# Note the tricky use of conditional recursion to work around the fact that
-# the GNU Make language does not have any conditional looping construct
-# like 'while'.
-get-closure-recursive = \
- $(eval __closure_node := $(call first,$(__closure_wq)))\
- $(eval __closure_wq := $(call rest,$(__closure_wq)))\
- $(eval __closure_depends := $(call $(__closure_deps_func),$(__closure_node)))\
- $(eval __closure_new := $(filter-out $(__closure_list),$(__closure_depends)))\
- $(eval __closure_list += $(__closure_new))\
- $(eval __closure_wq := $(strip $(__closure_wq) $(__closure_new)))\
- $(if $(__closure_wq),$(call get-closure-recursive))
-
--test-get-closure.empty = \
- $(eval deps = $$($$1_depends))\
- $(call test-expect,$(call get-closure,,deps))\
-
--test-get-closure.A = \
- $(eval deps = $$($$1_depends))\
- $(eval A_depends :=)\
- $(call test-expect,A,$(call get-closure,A,deps))
-
--test-get-closure.ABC = \
- $(eval deps = $$($$1_depends))\
- $(eval A_depends := B)\
- $(eval B_depends := C)\
- $(eval C_depends :=)\
- $(call test-expect,A B C,$(call get-closure,A,deps))
-
--test-get-closure.ABC_circular = \
- $(eval deps = $$($$1_depends))\
- $(eval A_depends := B)\
- $(eval B_depends := C)\
- $(eval C_depends := A)\
- $(call test-expect,A B C,$(call get-closure,A,deps))
-
--test-get-closure.ABCDEF = \
- $(eval deps = $$($$1_depends))\
- $(eval A_depends := B C)\
- $(eval B_depends := D E)\
- $(eval C_depends := E F)\
- $(eval D_depends :=)\
- $(eval E_depends :=)\
- $(eval F_depends :=)\
- $(call test-expect,A B C D E F,$(call get-closure,A,deps))
-
# -----------------------------------------------------------------------------
# Strip any 'lib' prefix in front of a given string.
#
diff --git a/build/core/definitions.mk b/build/core/definitions.mk
index 65ade40..f139aea 100644
--- a/build/core/definitions.mk
+++ b/build/core/definitions.mk
@@ -21,6 +21,7 @@
include $(BUILD_SYSTEM)/definitions-tests.mk
include $(BUILD_SYSTEM)/definitions-utils.mk
include $(BUILD_SYSTEM)/definitions-host.mk
+include $(BUILD_SYSTEM)/definitions-graph.mk
# -----------------------------------------------------------------------------
# Macro : this-makefile
@@ -298,7 +299,7 @@
$(call list-file-maybe-gen-1000,5,$1)
$$(__list_file): $$(__list_file).tmp
- $$(hide) $$(call copy-if-differ,$$@.tmp,$$@)
+ $$(hide) $$(call host-copy-if-differ,$$@.tmp,$$@)
$$(hide) $$(call host-rm,$$@.tmp)
endef
@@ -594,6 +595,145 @@
module-add-depends-any = \
$(eval __ndk_modules.$1.$3 += $(filter-out $(__ndk_modules.$1.$3),$2))
+
+# -----------------------------------------------------------------------------
+# Returns non-empty if a module is a static library
+# Arguments: 1: module name
+# Returns : non-empty iff the module is a static library.
+# Usage : $(if $(call module-is-static-library,<name>),...)
+# -----------------------------------------------------------------------------
+module-is-static-library = $(strip \
+ $(filter STATIC_LIBRARY PREBUILT_STATIC_LIBRARY,\
+ $(call module-get-class,$1)))
+
+# -----------------------------------------------------------------------------
+# Returns non-empty if a module is a shared library
+# Arguments: 1: module name
+# Returns : non-empty iff the module is a shared library.
+# Usage : $(if $(call module-is-shared-library,<name>),...)
+# -----------------------------------------------------------------------------
+module-is-shared-library = $(strip \
+ $(filter SHARED_LIBRARY PREBUILT_SHARED_LIBRARY,\
+ $(call module-get-class,$1)))
+
+# -----------------------------------------------------------------------------
+# Filter a list of module names to retain only the static libraries.
+# Arguments: 1: module name list
+# Returns : input list modules which are static libraries.
+# -----------------------------------------------------------------------------
+module-filter-static-libraries = $(call filter-by,$1,module-is-static-library)
+
+# -----------------------------------------------------------------------------
+# Filter a list of module names to retain only the shared libraries.
+# Arguments: 1: module name list
+# Returns : input list modules which are shared libraries.
+# -----------------------------------------------------------------------------
+module-filter-shared-libraries = $(call filter-by,$1,module-is-shared-library)
+
+# -----------------------------------------------------------------------------
+# Return the LOCAL_STATIC_LIBRARIES for a given module.
+# Arguments: 1: module name
+# Returns : List of static library modules.
+# -----------------------------------------------------------------------------
+module-get-static-libs = $(__ndk_modules.$1.STATIC_LIBRARIES)
+
+# -----------------------------------------------------------------------------
+# Return the LOCAL_WHOLE_STATIC_LIBRARIES for a given module.
+# Arguments: 1: module name
+# Returns : List of whole static library modules.
+# -----------------------------------------------------------------------------
+module-get-whole-static-libs = $(__ndk_modules.$1.WHOLE_STATIC_LIBRARIES)
+
+# -----------------------------------------------------------------------------
+# Return all static libraries for a given module.
+# Arguments: 1: module name
+# Returns : List of static library modules (whole or not).
+# -----------------------------------------------------------------------------
+module-get-all-static-libs = $(strip \
+ $(__ndk_modules.$1.STATIC_LIBRARIES) \
+ $(__ndk_modules.$1.WHOLE_STATIC_LIBRARIES))
+
+# -----------------------------------------------------------------------------
+# Return the list of LOCAL_SHARED_LIBRARIES for a given module.
+# Arguments: 1: module name
+# Returns : List of shared library modules.
+# -----------------------------------------------------------------------------
+module-get-shared-libs = $(__ndk_modules.$1.SHARED_LIBRARIES)
+
+# -----------------------------------------------------------------------------
+# Return the list of all libraries a modules depends directly on.
+# This is the concatenation of its LOCAL_STATIC_LIBRARIES,
+# LOCAL_WHOLE_STATIC_LIBRARIES, and LOCAL_SHARED_LIBRARIES variables.
+# Arguments: 1: module name
+# Returns : List of library modules (static or shared).
+# -----------------------------------------------------------------------------
+module-get-direct-libs = $(strip \
+ $(__ndk_modules.$1.STATIC_LIBRARIES) \
+ $(__ndk_modules.$1.WHOLE_STATIC_LIBRARIES) \
+ $(__ndk_modules.$1.SHARED_LIBRARIES))
+
+
+# -----------------------------------------------------------------------------
+# Computes the full closure of a module and its dependencies. Order is
+# defined by a breadth-first walk of the graph.
+# $1 will be the first item in the result.
+#
+# Arguments: 1: module name
+# Returns : List of all modules $1 depends on.
+#
+# Note: Do not use this to determine build dependencies. The returned list
+# is much too large for this. For example consider the following
+# dependency graph:
+#
+# main.exe -> libA.a -> libfoo.so -> libB.a
+#
+# This function will return all four modules in the result, while
+# at link time building main.exe only requires the first three.
+#
+# -----------------------------------------------------------------------------
+module-get-all-dependencies = $(call -ndk-mod-get-closure,$1,module-get-depends)
+
+# -----------------------------------------------------------------------------
+# Compute the list of all static and shared libraries required to link a
+# given module.
+#
+# Note that the result is topologically ordered, i.e. if library A depends
+# on library B, then A will always appear after B in the result.
+#
+# Arguments: 1: module name
+# Returns : List of all library $1 depends at link time.
+#
+# Note: This doesn't differentiate between regular and whole static
+# libraries. Use module-extract-whole-static-libs to filter the
+# result returned by this function.
+# -----------------------------------------------------------------------------
+module-get-link-libs = $(strip \
+ $(eval _ndk_mod_link_module := $1) \
+ $(call -ndk-mod-get-topological-depends,$1,-ndk-mod-link-deps))
+
+# Special dependency function used by nodule-get-link-libs.
+# The rules to follow are the following:
+# - if $1 is the link module, or if it is a static library, then all
+# direct dependencies.
+# - otherwise, the module is a shared library, don't add build deps.
+-ndk-mod-link-deps = \
+ $(if $(call seq,$1,$(_ndk_mod_link_module))$(call module-is-static-library,$1),\
+ $(call module-get-direct-libs,$1))
+
+# -----------------------------------------------------------------------------
+# This function is used to extract the list of static libraries that need
+# to be linked as whole, i.e. placed in a special section on the final
+# link command.
+# Arguments: $1: module name.
+# $2: list of all static link-time libraries (regular or whole).
+# Returns : list of static libraries from '$2' that need to be linked
+# as whole.
+# -----------------------------------------------------------------------------
+module-extract-whole-static-libs = $(strip \
+ $(eval _ndk_mod_whole_all := $(call map,module-get-whole-static-libs,$1 $2))\
+ $(eval _ndk_mod_whole_result := $(filter $(_ndk_mod_whole_all),$2))\
+ $(_ndk_mod_whole_result))
+
# Used to recompute all dependencies once all module information has been recorded.
#
modules-compute-dependencies = \
@@ -608,34 +748,7 @@
module-get-installed = $(__ndk_modules.$1.INSTALLED)
-# -----------------------------------------------------------------------------
-# Function : modules-get-all-dependencies
-# Arguments: 1: list of module names
-# Returns : List of all the modules $1 depends on transitively.
-# Usage : $(call modules-all-get-dependencies,<list of module names>)
-# Rationale: This computes the closure of all module dependencies starting from $1
-# -----------------------------------------------------------------------------
-module-get-all-dependencies = $(strip \
- $(call modules-get-closure,$1,depends))
-
-modules-get-closure = $(strip \
- $(eval __module_closure_field := $2)\
- $(call get-closure,$1,-module-closure-depends))
-
-# Used internally by modules-get-closure, this is a dependency function
-# to be used with get-closure.
--module-closure-depends = $(__ndk_modules.$1.$(__module_closure_field))
-
-# -----------------------------------------------------------------------------
-# Function : module-get-depends
-# Arguments: 1: list of module names
-# 2: local module type (e.g. SHARED_LIBRARIES)
-# Returns : List all the <local-type> modules $1 depends on transitively.
-# Usage : $(call module-get-depends,<list of module names>,<local-type>)
-# Rationale: This computes the closure of all local module dependencies starting from $1
-# -----------------------------------------------------------------------------
-module-get-depends = $(strip $(call modules-get-closure,$1,$2))
-
+module-get-depends = $(__ndk_modules.$1.depends)
# -----------------------------------------------------------------------------
# Function : modules-get-all-installable
@@ -646,7 +759,7 @@
# -----------------------------------------------------------------------------
# For now, only the closure of LOCAL_SHARED_LIBRARIES is enough
modules-get-all-installable = $(strip \
- $(foreach __alldep,$(call module-get-depends,$1,depends),\
+ $(foreach __alldep,$(call module-get-all-dependencies,$1),\
$(if $(call module-is-installable,$(__alldep)),$(__alldep))\
))
@@ -916,6 +1029,18 @@
$(eval LOCAL_OBJS_DIR := $(TARGET_OBJS)/$(LOCAL_MODULE))
# -----------------------------------------------------------------------------
+# Compute the real path of a prebuilt file.
+#
+# Function : local-prebuilt-path
+# Arguments: 1: prebuilt path (as listed in $(LOCAL_SRC_FILES))
+# Returns : full path. If $1 begins with a /, the path is considered
+# absolute and returned as-is. Otherwise, $(LOCAL_PATH)/$1 is
+# returned instead.
+# Usage : $(call local-prebuilt-path,$(LOCAL_SRC_FILES))
+# -----------------------------------------------------------------------------
+local-prebuilt-path = $(if $(filter /%,$1),$1,$(LOCAL_PATH)/$1)
+
+# -----------------------------------------------------------------------------
# This is used to strip any lib prefix from LOCAL_MODULE, then check that
# the corresponding module name is not already defined.
#
diff --git a/tests/build/topological-sort/BROKEN_BUILD b/tests/build/topological-sort/BROKEN_BUILD
deleted file mode 100644
index e69de29..0000000
--- a/tests/build/topological-sort/BROKEN_BUILD
+++ /dev/null
diff --git a/tests/build/topological-sort/jni/main.c b/tests/build/topological-sort/jni/main.c
index dcc85dc..3f20987 100644
--- a/tests/build/topological-sort/jni/main.c
+++ b/tests/build/topological-sort/jni/main.c
@@ -1,3 +1,5 @@
+#include <stdio.h>
+
#include "foo.h"
#include "bar.h"
