# 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)))\
    $(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))\
        $(eval _ndk_mod_nodes := $(filter-out $(_ndk_mod_module),$(_ndk_mod_nodes)))\
        $(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))

-test-ndk-mod-get-topo-list.ABC.circular = \
    $(eval -local-deps = $$($$1_depends))\
    $(eval A_depends := B)\
    $(eval B_depends := C)\
    $(eval C_depends := B)\
    $(call test-expect,A B C,$(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)

-test-ndk-mod-get-topological-depends.circular = \
    $(eval -local-get-deps = $$($$1_depends))\
    $(eval A_depends := B)\
    $(eval B_depends := C)\
    $(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,B C,$(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))