CMake: Sort a list of target considering their dependencies

Question

I have a huge CMake project with lots of libraries. At some point, I end up with a, let's say randomly ordered, list of libraries. And I need to sort them considering their dependencies (sorted in build order: a libraries appears necessarily after the libraries it depends on).

For example, if I have:

target_link_libraries (lib2 lib1) # lib2 needs lib1
target_link_libraries (lib3 lib1) # lib3 needs lib1
target_link_libraries (lib4 lib2) # lib4 needs lib2, so it also needs lib1

I need a function that would, using CMake native functions (because dependencies are stored somewhere in Cmake environment), sort:

lib4;lib3;lib2;lib1

into one of the following (all being valid as a compilation order):

lib1;lib2;lib3;lib4
lib1;lib2;lib4;lib3
lib1;lib3;lib2;lib4

List of **direct** link dependencies is accessible via `LINK_LIBRARIES` target's property. If your project doesn't use [generator-expressions](https://cmake.org/cmake/help/v3.0/manual/cmake-generator-expressions.7.html), you may recursively traverse this property and extract full map of libraries dependencies. Using this map you can easily sort libraries. — Tsyvarev, Jan 06 '16 at 17:47
But in case of regular expressions, [it seems](http://stackoverflow.com/questions/32756195/recursive-list-of-link-libraries-in-cmake) there is no reliable way to get full list of of dependencies for given target. Also, with using regular expressions, compilation order isn't defined at configure stage, because it depends from some parameters (like `CMAKE_BUILD_TYPE`) which are defined after. So your list just doesn't exist. — Tsyvarev, Jan 06 '16 at 17:53
I don't think we are using this expression stuff. However, I'm not sure doing the sort with only direct link knowledge will be that obvious (specially in CMake, I would be more confident in C...). I'll give it a try unless you post a proposal as a solution ;-) I would be very happy to accept it... — jpo38, Jan 06 '16 at 20:04

score 2 · Accepted Answer · answered Jan 07 '16 at 14:38

List of direct dependencies is stored in LINK_LIBRARIES target's property. So, if your project doesn't use generator-expressions, you may collect list of all dependencies using recursive traversal over this property. Function compute_links store all links, which are targets, into LINK_LIBRARIES_ALL target's property:

define_property(TARGET PROPERTY LINK_LIBRARIES_ALL
    BRIEF_DOCS "List of all targets, linked to this one"
    FULL_DOCS "List of all targets, linked to this one"
)

# Compute list of all target links (direct and indirect) for given library
# Result is stored in LINK_LIBRARIES_ALL target property.
function(compute_links lib)
    if(${lib}_IN_PROGRESS)
        message(FATAL_ERROR "Circular dependency for library '${lib}'")
    endif()
    # Immediately return if output property is already set.
    get_property(complete TARGET ${lib} PROPERTY LINK_LIBRARIES_ALL SET)
    if(completed)
        return()
    endif()
    # Initialize output property.
    set_property(TARGET ${lib} PROPERTY LINK_LIBRARIES_ALL "")

    set(${lib}_IN_PROGRESS 1) # Prevent recursion for the same lib

    get_target_property(links ${lib} LINK_LIBRARIES)

    if(NOT links) 
        return() # Do not iterate over `-NOTFOUND` value in case of absence of the property.
    endif()

    # For each direct link append it and its links
    foreach(link ${links})
        if(TARGET ${link}) # Collect only target links
            compute_links(${link})
            get_target_property(link_links_all ${link} LINK_LIBRARIES_ALL)
            set_property(TARGET ${lib} APPEND PROPERTY
                LINK_LIBRARIES_ALL ${link} ${link_links_all}
            )
        elseif(link MATCHES "$<")
            message(STATUS "Library '${lib}' uses link '${link}'.")
            message(FATAL_ERROR "Algorithm doesn't work with generator expressions.")
        endif()
    endforeach(link ${links})
    # Remove duplicates
    get_target_property(links_all ${lib} LINK_LIBRARIES_ALL)
    list(REMOVE_DUPLICATES links_all)
    set_property(TARGET ${lib} PROPERTY LINK_LIBRARIES_ALL ${links_all})
endfunction()

Resulted lists can be used for sort libraries in compilation order:

# Sort given list of targets, so for any target its links come before the target itself.
#
# Uses selection sort (stable).
function(sort_links targets_list)
    # Special case of empty input list. Futher code assumes list to be non-empty.
    if(NOT ${targets_list})
        return()
    endif()

    foreach(link ${${targets_list}})
        compute_links(${link})
    endforeach()

    set(output_list)
    set(current_input_list ${${targets_list}})

    list(LENGTH current_input_list current_len)
    while(NOT current_len EQUAL 1)
        # Assume first element as minimal
        list(GET current_input_list 0 min_elem)
        set(min_index 0)
        get_target_property(min_links ${min_elem} LINK_LIBRARIES_ALL)
        # Check that given element is actually minimal
        set(index 0)
        foreach(link ${current_input_list})
            if(index) # First iteration should always fail, so skip it.
                list(FIND min_links ${link} find_index)
                if(NOT find_index EQUAL "-1")
                    # Choose linked library as new minimal element.
                    set(min_elem ${link})
                    set(min_index ${index})
                    get_target_property(min_links ${min_elem} LINK_LIBRARIES_ALL)
                endif(NOT find_index EQUAL "-1")
            endif()
            math(EXPR index "${index}+1")
        endforeach(link ${current_input_list})
        # Move minimal element from the input list to the output one.
        list(APPEND output_list ${min_elem})
        list(REMOVE_AT current_input_list ${min_index})
        math(EXPR current_len "${current_len}-1")
    endwhile()
    # Directly append the only element in the current input list to the resulted variable.
    set(${targets_list} ${output_list} ${current_input_list} PARENT_SCOPE)
endfunction(sort_links)

Having

target_link_libraries (lib2 lib1) # lib2 needs lib1
target_link_libraries (lib3 lib1) # lib3 needs lib1
target_link_libraries (lib4 lib2) # lib4 needs lib2, so it also needs lib1

set(libs lib4 lib3 lib2 lib1)
message(Before sort: ${libs})
sort_links(libs)
message(After sort: ${libs})

Will produce:

Before sort: lib4;lib3;lib2;lib1
After sort: lib1;lib2;lib4;lib3

Thanks. I won't get a chance to test that because my answer's code is simplier and works so far ;-) But you definitely deserve to get the answer accepted for the time you spent on that ;-) — jpo38, Jan 07 '16 at 15:59

jpo38 · Answer 2 · 2016-01-07T08:56:36.577

With Tsyvarev help, here is a sort by dependency function.

It goes through the list in incremental order and move to the end of list any library found which appears too early (depends on a library present at a upper position in the list)

function( sort_dep_list the_list )

    list(LENGTH the_list cur_size)
    message( "Unordred list was ${the_list} (size is ${cur_size})")

    list( REMOVE_DUPLICATES the_list )

    set( index 0 )
    while ( 1 )

        list(LENGTH the_list cur_size)
        if ( ${index} EQUAL ${cur_size} )
            break()
        endif()

        list( GET the_list ${index} currently_checked_lib )

        message( "Testing ${currently_checked_lib} dependency order (index ${index})" )

        set ( changed_order 0 )

        get_target_property( currently_checked_lib_dep_list ${currently_checked_lib} LINK_LIBRARIES )

        if ( NOT "${currently_checked_lib_dep_list}" STREQUAL "" )

            set ( used_lib_last_index ${index} )
            foreach( used IN LISTS currently_checked_lib_dep_list )

                list( FIND the_list ${used} used_pos )

                #message( "${used} index is ${used_pos}" )

                if ( ${used_pos} GREATER ${used_lib_last_index} )
                    set( used_lib_last_index ${used_pos} )
                endif()

            endforeach()

            message( "${currently_checked_lib} last dependency index is ${used_lib_last_index}" )

            if ( ${used_lib_last_index} GREATER ${index} )

                message( "${currently_checked_lib} (index ${index}) uses a library at index ${used_lib_last_index}, ${currently_checked_lib} will be moved to end of list" )

                list( APPEND the_list ${currently_checked_lib} )
                list( REMOVE_AT the_list ${index} )

                message( "Modified list is ${the_list} (size is ${cur_size})")

                # Flag that index should not be incremented
                set ( changed_order 1 )
            endif()

        endif()

        if ( ${changed_order} EQUAL 0 )
            # Everything's fine, move to next index:
            math( EXPR index ${index}+1 )
        endif()

    endwhile()

    list(LENGTH the_list cur_size)
    message( "Ordered list is ${the_list} (size is ${cur_size})" )

endfunction()

With the OP example, intermediates and final lists will be:

lib4;lib3;lib2;lib1 < original list
lib3;lib2;lib1;lib4 < lib4 moved to tail because it depends on lib2
lib2;lib1;lib4;lib3 < lib3 moved to tail because it depends on lib1
lib1;lib4;lib3;lib2 < lib2 moved to tail because it depends on lib1
lib1;lib3;lib2;lib4 < final: ordered

CMake: Sort a list of target considering their dependencies

2 Answers2