[cfe-dev] cyclic dependencies in building modules

[Sean Silva]

On Wed, Jan 28, 2015 at 11:58 PM, Thompson, John <
John_Thompson at playstation.sony.com> wrote:

>  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


>
>
> I would also like to minimize major changes to the headers.
>
>
>
> Thanks.
>
>
>
> -John
>
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20150129/1c81dbe5/attachment.html>