From 827f4eb6a32ec66d8c13ab87447c06c7d0bb83b9 Mon Sep 17 00:00:00 2001
From: Peter Zotov <whitequark@whitequark.org>
Date: Thu, 18 Dec 2014 23:56:52 +0000
Subject: [PATCH] [cmake] Unbreak LLVM-Config.cmake / llvm_expand_dependencies.

The algorithm for sorting libraries in topological order, as
previously implemented, had a few issues:
  * It didn't make any sense.
  * It didn't actually sort libraries in topological order.
  * It hung on some inputs, e.g. "LLVMipo".

This commit replaces the old algorithm with a straightforward port
from llvm-config.cpp.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@224554 91177308-0d34-0410-b5e6-96231b3b80d8
---
 cmake/modules/LLVM-Config.cmake | 50 ++++++++++++++++++++-------------
 1 file changed, 30 insertions(+), 20 deletions(-)

diff --git a/cmake/modules/LLVM-Config.cmake b/cmake/modules/LLVM-Config.cmake
index e8c42fc8dc7..b24c12989fa 100644
--- a/cmake/modules/LLVM-Config.cmake
+++ b/cmake/modules/LLVM-Config.cmake
@@ -152,29 +152,39 @@ function(llvm_map_components_to_libnames out_libs)
   set(${out_libs} ${expanded_components} PARENT_SCOPE)
 endfunction()
 
+# Perform a post-order traversal of the dependency graph.
+# This duplicates the algorithm used by llvm-config, originally
+# in tools/llvm-config/llvm-config.cpp, function ComputeLibsForComponents.
+function(expand_topologically name required_libs visited_libs)
+  list(FIND visited_libs ${name} found)
+  if( found LESS 0 )
+    list(APPEND visited_libs ${name})
+    set(visited_libs ${visited_libs} PARENT_SCOPE)
+
+    get_property(lib_deps GLOBAL PROPERTY LLVMBUILD_LIB_DEPS_${name})
+    foreach( lib_dep ${lib_deps} )
+      expand_topologically(${lib_dep} "${required_libs}" "${visited_libs}")
+      set(required_libs ${required_libs} PARENT_SCOPE)
+      set(visited_libs ${visited_libs} PARENT_SCOPE)
+    endforeach()
+
+    list(APPEND required_libs ${name})
+    set(required_libs ${required_libs} PARENT_SCOPE)
+  endif()
+endfunction()
+
 # Expand dependencies while topologically sorting the list of libraries:
 function(llvm_expand_dependencies out_libs)
   set(expanded_components ${ARGN})
-  list(LENGTH expanded_components lst_size)
-  set(cursor 0)
-  set(processed)
-  while( cursor LESS lst_size )
-    list(GET expanded_components ${cursor} lib)
-    get_property(lib_deps GLOBAL PROPERTY LLVMBUILD_LIB_DEPS_${lib})
-    list(APPEND expanded_components ${lib_deps})
-    # Remove duplicates at the front:
-    list(REVERSE expanded_components)
-    list(REMOVE_DUPLICATES expanded_components)
-    list(REVERSE expanded_components)
-    list(APPEND processed ${lib})
-    # Find the maximum index that doesn't have to be re-processed:
-    while(NOT "${expanded_components}" MATCHES "^${processed}.*" )
-      list(REMOVE_AT processed -1)
-    endwhile()
-    list(LENGTH processed cursor)
-    list(LENGTH expanded_components lst_size)
-  endwhile( cursor LESS lst_size )
-  set(${out_libs} ${expanded_components} PARENT_SCOPE)
+
+  set(required_libs)
+  set(visited_libs)
+  foreach( lib ${expanded_components} )
+    expand_topologically(${lib} "${required_libs}" "${visited_libs}")
+  endforeach()
+
+  list(REVERSE required_libs)
+  set(${out_libs} ${required_libs} PARENT_SCOPE)
 endfunction()
 
 function(explicit_map_components_to_libraries out_libs)
-- 
2.34.1