cyclic dependencies in building modules

I’m experimenting with trying to use separate module maps in my three include directories, as a possible alternative to my one module map approach in a common parent directory.

Isn’t there some way we could support cyclic dependencies in building modules?

It seems that cycles are okay in sub-modules, but not in top-level modules.

It seems the only way to work around having cycles in separate directories is to make lots of smaller top-level modules. But then because they are not submodules any more, cycles within an include directory start popping up. For example:

While building module ‘limits’ imported from target/include/srclimits_h.cpp:1:

While building module ‘xstddef’ imported from D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/limits:17:

While building module ‘initializer_list’ imported from D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/xstddef:162:

While building module ‘type_traits’ imported from D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/initializer_list:5:

In file included from :1:

D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/type_traits:12:10: fatal error: cyclic dependency in module

‘xstddef’: xstddef → initializer_list → type_traits → xstddef

#include

^

D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/initializer_list:5:10: fatal error: could not build module

‘type_traits’

#include <type_traits>


D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/xstddef:162:11: fatal error: could not build module

'initializer_list'

#include <initializer_list>

Or is using lots of small top-level modules a bad idea because of the cost in performance when dealing with separate module files?

I would also like to minimize major changes to the headers.

Thanks.

-John

I’m experimenting with trying to use separate module maps in my three
include directories, as a possible alternative to my one module map
approach in a common parent directory.

Isn’t there some way we could support cyclic dependencies in building
modules?

Not implicitly, no -- by the time we notice we've got a cyclic dependency,
we've already got separate Clang threads (or maybe processes) building each
of the separate .pcm files involved in the cycle.

However... we could support some way for top-level modules to specify that
they are only one part of a .pcm file, and build all the modules in that
.pcm file in one go, as if they were a single top-level module. The current
coupling of .pcm files to top-level modules is in no way fundamental, and
is probably not a good idea.

It seems that cycles are okay in sub-modules, but not in top-level modules.

Right; top-level modules and submodules are fundamentally different things
right now. The easiest way to understand this is to think of a top-level
module as acting like a translation unit into which all of the constituent
files are included, and submodules as merely being visibility groups within
their top-level module.

It seems the only way to work around having cycles in separate directories

is to make lots of smaller top-level modules. But then because they are
not submodules any more, cycles within an include directory start popping
up.

The way this is supposed to work is that each separate logical layer of the
code gets its own set of top-level modules. By definition, if there are
cycles between groups of files, those files are in the same layer;
therefore, they should be part of the same top-level module.

To give you an idea, in my module maps for glibc, and the OS X module maps
for their system, the entire C standard library is modeled as a single
top-level module. libc++'s module map provides only one top-level module.
LLVM and Clang's module maps provide one top-level module for each
directory under include/llvm and include/clang, respectively.

  For example:

While building module 'limits' imported from
target/include/srclimits_h.cpp:1:

While building module 'xstddef' imported from D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/limits:17:

While building module 'initializer_list' imported from
D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/xstddef:162:

While building module 'type_traits' imported from D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/initializer_list:5:

In file included from <module-includes>:1:

D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/type_traits:12:10: fatal error: cyclic
dependency in module

      'xstddef': xstddef -> initializer_list -> type_traits -> xstddef

#include <xstddef>

         ^

D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/initializer_list:5:10: fatal error: could
not build module

      'type_traits'

#include <type_traits>

~~~~~~~~^

D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/xstddef:162:11:
fatal error: could not build module

      'initializer_list'

#include <initializer_list>

Or is using lots of small top-level modules a bad idea because of the cost
in performance when dealing with separate module files?

Yes, that's certainly a cost to keep in mind. In this case, it seems that
at least xstddef and initializer_list should be in the same module (and I'm
trying hard not to comment on the brokenness of your #include cycle...).

I’m experimenting with trying to use separate module maps in my three
include directories, as a possible alternative to my one module map
approach in a common parent directory.

Isn’t there some way we could support cyclic dependencies in building
modules?

It seems that cycles are okay in sub-modules, but not in top-level modules.

It seems the only way to work around having cycles in separate directories
is to make lots of smaller top-level modules. But then because they are
not submodules any more, cycles within an include directory start popping
up.

What you can do is to create a graph of the inclusions between headers, and
then run a strongly-connected components algorithm over it (e.g.
http://llvm.org/docs/doxygen/html/SCCIterator_8h.html or your favorite
graph library). The graph of top-level module dependencies must be a
directed acyclic graph. Ideally, the header dependency graph would be
acyclic (hence each header would be its own SCC), so we would have complete
freedom in partitioning the graph into connected components that would each
become a top-level module (for example, to accommodate multiple include
directories). However, in the non-ideal case where we have nontrivial
SCC's, all headers in a given SCC must be within the same top-level module.

Evidently, if headers from two different include directories are contained
within a single SCC then that is a problem; however once you identify such
an SCC, it should be easy to isolate the recursive dependency and break it.

For example:

While building module 'limits' imported from
target/include/srclimits_h.cpp:1:

While building module 'xstddef' imported from D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/limits:17:

While building module 'initializer_list' imported from
D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/xstddef:162:

While building module 'type_traits' imported from D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/initializer_list:5:

In file included from <module-includes>:1:

D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/type_traits:12:10: fatal error: cyclic
dependency in module

      'xstddef': xstddef -> initializer_list -> type_traits -> xstddef

#include <xstddef>

         ^

D:\usr\local\psp2\ORBIS
SDKs\2.000_pre_mod/target/include/initializer_list:5:10: fatal error: could
not build module

      'type_traits'

#include <type_traits>

~~~~~~~~^

D:\usr\local\psp2\ORBIS SDKs\2.000_pre_mod/target/include/xstddef:162:11:
fatal error: could not build module

      'initializer_list'

#include <initializer_list>

Or is using lots of small top-level modules a bad idea because of the cost
in performance when dealing with separate module files?

Generally, the performance to be gained from avoiding re-inclusion is so
tremendous that I would avoid worrying about creating a small, fixed number
of top-level modules.

-- Sean Silva