[libcxx] adds an include-what-you-use (IWYU) mapping file

[cjdb]

Summary

This makes it possible for programmers to run IWYU and get more accurate
standard library inclusions. Prior to this commit, the following program
would be transformed thusly:

cpp
// Before
 #include <algorithm>
 #include <vector>

void f() {
  auto v = std::vector{0, 1};
  std::find(std::ranges::begin(v), std::ranges::end(v), 0);
}

cpp
// After
 #include <__algorithm/find.h>
 #include <__ranges/access.h>
 #include <vector>
...

There are two ways to fix this issue: to use comment pragmas
on every private include, or to write a canonical mapping file
that provides the tool with a manual on how libc++ is laid out. Due to
the complexity of libc++, this commit opts for the latter, to maximise
correctness and minimise developer burden.

To mimimise developer updates to the file, it makes use of wildcards
that match everything within listed subdirectories. A script has also
been added to ensure that the mapping is always fresh in CI, and makes
the process a single step.

Finally, documentation has been added to inform users that IWYU is
supported, and what they need to do in order to leverage the mapping
file.

Closes #56937.

[ldionne]

Thanks! I think I really like this. We could also potentially use this as a tool to aid our removal of transitive includes -- arguably, if we provide a tool to automatically fix people's code, it may become more reasonable to break people's code through transitive include removals a bit more eagerly. I'm not suggesting we do that for now, just mentioning it.

libcxx/include/libcxx.imp

2

This patch doesn't ship this file with the libc++ headers. Did you mean to do that?

libcxx/utils/generate_iwyu_mapping.py

2

Just to clarify, we will not need to change this script unless we add a new detail header at the top level (which should be rare), right?

[cjdb]

• adds libcxx.imp to include/CMakeLists.txt
• implements panic()
• regenerates libcxx.imp so that it has a newline before EOF

[cjdb]

I'm not suggesting we do that for now, just mentioning it.

Ack. Some thoughts below for when you do entertain this more seriously.

In D138189#3933948, @ldionne wrote:

Thanks! I think I really like this. We could also potentially use this as a tool to aid our removal of transitive includes -- arguably, if we provide a tool to automatically fix people's code, it may become more reasonable to break people's code through transitive include removals a bit more eagerly.

Before committing to this, it'd be good to survey the trust folks have in IWYU (my hunch is that it's very low); and to keep the transitive headers for multiple years behind a macro, for folks unable to use IWYU for whatever reason (e.g. perhaps a library doesn't have a mapping file and has lots of detail headers that make using IWYU unreasonable).

libcxx/include/libcxx.imp

2

Oops, nice catch!

libcxx/utils/generate_iwyu_mapping.py

2

Yeah, that and if a specific directory needs mapping (e.g. say you add __detail/).

[cjdb]

• cleans up documentation issue

[cjdb]

• edits generate_header_tests.py so that it excludes libcxx.imp, which isn't a header

[cjdb]

• teaches lint_headers.sh.py about libcxx.imp

[ldionne]

Thanks!

LGTM, but can you please undo the formatting-only changes in libcxx/utils/generate_header_tests.py? I don't want to block the review on this so I'm approving right away, but I'd like those to be undone and pursued in a separate patch (if at all -- IMO the previous formatting was fine).

[jloser]

Thanks so much for working on this, @cjdb! I'm excited to try it out.

[cjdb]

In D138189#3938244, @ldionne wrote:

Thanks!

LGTM, but can you please undo the formatting-only changes in libcxx/utils/generate_header_tests.py? I don't want to block the review on this so I'm approving right away, but I'd like those to be undone and pursued in a separate patch (if at all -- IMO the previous formatting was fine).

Yeah, sorry about that: my browser autoformats on save and since there's no .pyformat yapf just does whatever. I'll fix it up!

Before submitting: is the clang-cl static CI job a concern?

[philnik]

In D138189#3940081, @cjdb wrote:

In D138189#3938244, @ldionne wrote:

Thanks!

LGTM, but can you please undo the formatting-only changes in libcxx/utils/generate_header_tests.py? I don't want to block the review on this so I'm approving right away, but I'd like those to be undone and pursued in a separate patch (if at all -- IMO the previous formatting was fine).

Yeah, sorry about that: my browser autoformats on save and since there's no .pyformat yapf just does whatever. I'll fix it up!

Before submitting: is the clang-cl static CI job a concern?

Looks unrelated, I think you can land with @ldionne's comments addressed.

[ldionne]

libcxx/utils/generate_iwyu_mapping.py

38

It seems that this is only supported starting with Python 3.10.

I'm not sure what's the oldest version that LLVM supports, but I think it's older than 3.10, so I'll change this to an if-else chain. No action item, I just wanted to give a heads up.

[cjdb]

libcxx/utils/generate_iwyu_mapping.py

38

Thanks, I'll keep this in mind for next time. I was a bit apprehensive about using the feature because it was so new, but it looked like CI was happy with it, so I thought it would be okay.

libcxx/docs/UsingLibcxx.rst

 provide pretty-printers itself. Those can be used as:
 
 .. code-block:: bash
 
   $ gdb -ex "source <libcxx>/utils/gdb/libcxx/printers.py" \
         -ex "python register_libcxx_printer_loader()" \
         <args>
 
+.. _include-what-you-use:
+
+include-what-you-use (IWYU)
+===========================
+
+libc++ provides an IWYU `mapping file <https://github.com/include-what-you-use/include-what-you-use/blob/master/docs/IWYUMappings.md>`,
+which drastically improves the accuracy of the tool when using libc++. To use the mapping file with
+IWYU, you should run the tool like so:
+
+.. code-block:: bash
+
+  $ include-what-you-use -Xiwyu /path/to/libcxx/include/libcxx.imp file.cpp
+
+If you would prefer to not use that flag, then you can replace ``/path/to/include-what-you-use/share/libcxx.imp```
+file with the libc++-provided ``libcxx.imp`` file.
 
 .. _assertions-mode:
 
 Enabling the "safe libc++" mode
 ===============================
 
 Libc++ contains a number of assertions whose goal is to catch undefined behavior in the
 library, usually caused by precondition violations. Those assertions do not aim to be

libcxx/include/CMakeLists.txt

set(files
   inttypes.h
   iomanip
   ios
   iosfwd
   iostream
   istream
   iterator
   latch
+  libcxx.imp
   limits
   limits.h
   list
   locale
   locale.h
   map
   math.h
   memory

libcxx/include/libcxx.imp

+[
+  { include: [ "<__bits>", "private", "<bits>", "public" ] },
+  { include: [ "<__hash_table>", "private", "<unordered_map>", "public" ] },
+  { include: [ "<__hash_table>", "private", "<unordered_set>", "public" ] },
+  { include: [ "<__locale>", "private", "<locale>", "public" ] },
+  { include: [ "<__node_handle>", "private", "<map>", "public" ] },
+  { include: [ "<__node_handle>", "private", "<set>", "public" ] },
+  { include: [ "<__node_handle>", "private", "<unordered_map>", "public" ] },
+  { include: [ "<__node_handle>", "private", "<unordered_set>", "public" ] },
+  { include: [ "<__split_buffer>", "private", "<deque>", "public" ] },
+  { include: [ "<__split_buffer>", "private", "<vector>", "public" ] },
+  { include: [ "<__std_stream>", "private", "<iostream>", "public" ] },
+  { include: [ "<__threading_support>", "private", "<atomic>", "public" ] },
+  { include: [ "<__threading_support>", "private", "<mutex>", "public" ] },
+  { include: [ "<__threading_support>", "private", "<semaphore>", "public" ] },
+  { include: [ "<__threading_support>", "private", "<thread>", "public" ] },
+  { include: [ "<__tree>", "private", "<map>", "public" ] },
+  { include: [ "<__tree>", "private", "<set>", "public" ] },
+  { include: [ "@<__algorithm/.*>", "private", "<algorithm>", "public" ] },
+  { include: [ "@<__bit/.*>", "private", "<bit>", "public" ] },
+  { include: [ "@<__charconv/.*>", "private", "<charconv>", "public" ] },
+  { include: [ "@<__chrono/.*>", "private", "<chrono>", "public" ] },
+  { include: [ "@<__compare/.*>", "private", "<compare>", "public" ] },
+  { include: [ "@<__concepts/.*>", "private", "<concepts>", "public" ] },
+  { include: [ "@<__coroutine/.*>", "private", "<coroutine>", "public" ] },
+  { include: [ "@<__debug_utils/.*>", "private", "<debug_utils>", "public" ] },
+  { include: [ "@<__filesystem/.*>", "private", "<filesystem>", "public" ] },
+  { include: [ "@<__format/.*>", "private", "<format>", "public" ] },
+  { include: [ "@<__functional/.*>", "private", "<functional>", "public" ] },
+  { include: [ "@<__fwd/.*>", "private", "<fwd>", "public" ] },
+  { include: [ "@<__ios/.*>", "private", "<ios>", "public" ] },
+  { include: [ "@<__iterator/.*>", "private", "<iterator>", "public" ] },
+  { include: [ "@<__memory/.*>", "private", "<memory>", "public" ] },
+  { include: [ "@<__memory_resource/.*>", "private", "<memory_resource>", "public" ] },
+  { include: [ "@<__numeric/.*>", "private", "<numeric>", "public" ] },
+  { include: [ "@<__random/.*>", "private", "<random>", "public" ] },
+  { include: [ "@<__ranges/.*>", "private", "<ranges>", "public" ] },
+  { include: [ "@<__string/.*>", "private", "<string>", "public" ] },
+  { include: [ "@<__support/.*>", "private", "<support>", "public" ] },
+  { include: [ "@<__thread/.*>", "private", "<thread>", "public" ] },
+  { include: [ "@<__tuple/.*>", "private", "<tuple>", "public" ] },
+  { include: [ "@<__type_traits/.*>", "private", "<type_traits>", "public" ] },
+  { include: [ "@<__utility/.*>", "private", "<utility>", "public" ] },
+  { include: [ "@<__variant/.*>", "private", "<variant>", "public" ] },
+]

libcxx/test/libcxx/lint/lint_headers.sh.py

 # RUN: %{python} %s
 
 # Verify that each run of consecutive #include directives
 # in each libcxx/include/ header is maintained in alphabetical order.
 
 import glob
 import os
 import re
 
 
 def exclude_from_consideration(path):
     return (
         path.endswith('.txt') or
         path.endswith('.modulemap.in') or
         os.path.basename(path) == '__config' or
         os.path.basename(path) == '__config_site.in' or
+        os.path.basename(path) == 'libcxx.imp' or
         not os.path.isfile(path)
     )
 
 
 def check_for_pragma_GCC_system_header(pretty_fname, lines):
     if pretty_fname not in ['__undef_macros']:
         for line in lines:
             if re.match('# *pragma GCC system_header\n', line):

libcxx/utils/CMakeLists.txt

 
 add_custom_target(libcxx-generate-escaped-output-table
     COMMAND
         "${Python3_EXECUTABLE}"
         "${LIBCXX_SOURCE_DIR}/utils/generate_escaped_output_table.py"
         "${LIBCXX_SOURCE_DIR}/include/__format/escaped_output_table.h"
     COMMENT "Generate the escaped output header")
 
+add_custom_target(libcxx-generate-iwyu-mapping
+    COMMAND
+        "${Python3_EXECUTABLE}"
+        "${LIBCXX_SOURCE_DIR}/utils/generate_iwyu_mapping.py"
+    COMMENT "Generate the mapping file for include-what-you-use")
+
 add_custom_target(libcxx-generate-files
     DEPENDS libcxx-generate-public-header-transitive-inclusion-tests
             libcxx-generate-public-header-tests
             libcxx-generate-feature-test-macros
             libcxx-generate-extended-grapheme-cluster-tables
             libcxx-generate-extended-grapheme-cluster-tests
             libcxx-generate-escaped-output-table
+            libcxx-generate-iwyu-mapping
     COMMENT "Create all the auto-generated files in libc++ and its tests.")

libcxx/utils/generate_header_tests.py

def produce(test_file, variables):
     script = find_script(test_file)
     result = execute_script(script, variables)
     new_content = generate_new_file(test_file, result)
     with open(test_file, 'w', newline='\n') as f:
         f.write(new_content)
 
 def is_header(file):
     """Returns whether the given file is a header (i.e. not a directory or the modulemap file)."""
-    return not file.is_dir() and not file.name == 'module.modulemap.in'
+    return not file.is_dir() and not file.name == 'module.modulemap.in' and file.name != 'libcxx.imp'
+
 
 def main():
     monorepo_root = pathlib.Path(os.path.dirname(os.path.dirname(os.path.dirname(os.path.abspath(__file__)))))
     include = pathlib.Path(os.path.join(monorepo_root, 'libcxx', 'include'))
     test = pathlib.Path(os.path.join(monorepo_root, 'libcxx', 'test'))
     assert(monorepo_root.exists())
 
     toplevel_headers     = sorted(str(p.relative_to(include)) for p in include.glob('[a-z]*') if is_header(p))

libcxx/utils/generate_iwyu_mapping.py

+#!/usr/bin/env python
+
+import os, pathlib, sys
+
+def generate(private, public):
+    return f'{{ include: [ "{private}", "private", "<{public}>", "public" ] }}'
+
+
+def panic(file):
+    print(f'========== {__file__} error ==========', file=sys.stderr)
+    print(f'\tFile \'{file}\' is a top-level detail header without a mapping', file=sys.stderr)
+    sys.exit(1)
+
+
+def generate_map(include):
+    detail_files = []
+    detail_directories = []
+    c_headers = []
+
+    for i in include.iterdir():
+        if i.is_dir() and i.name.startswith('__'):
+            detail_directories.append(f'{i.name}')
+            continue
+
+        if i.name.startswith('__'):
+            detail_files.append(i.name)
+            continue
+
+        if i.name.endswith('.h'):
+            c_headers.append(i.name)
+
+    result = []
+    for i in detail_directories:
+        result.append(f'{generate(f"@<{i}/.*>", i[2:])},')
+
+    for i in detail_files:
+        public = []
+        match i:
+            case '__assert': continue
+            case '__availability': continue
+            case '__bit_reference': continue
+            case '__bits': public = ['bits']
+            case '__bsd_locale_defaults.h': continue
+            case '__bsd_locale_fallbacks.h': continue
+            case '__config_site.in': continue
+            case '__config': continue
+            case '__debug': continue
+            case '__errc': continue
+            case '__hash_table': public = ['unordered_map', 'unordered_set']
+            case '__locale': public = ['locale']
+            case '__mbstate_t.h': continue
+            case '__mutex_base': continue
+            case '__node_handle': public = ['map', 'set', 'unordered_map', 'unordered_set']
+            case '__split_buffer': public = ['deque', 'vector']
+            case '__std_stream': public = ['iostream']
+            case '__threading_support': public = ['atomic', 'mutex', 'semaphore', 'thread']
+            case '__tree': public = ['map', 'set']
+            case '__undef_macros': continue
+            case '__verbose_abort': continue
+            case _: panic()
+
+        for p in public:
+            result.append(f'{generate(f"<{i}>", p)},')
+
+    result.sort()
+    return result
+
+def main():
+    monorepo_root = pathlib.Path(os.path.dirname(os.path.dirname(os.path.dirname(os.path.abspath(__file__)))))
+    assert(monorepo_root.exists())
+    include = pathlib.Path(os.path.join(monorepo_root, 'libcxx', 'include'))
+
+    mapping = generate_map(include)
+    data = '[\n  ' + '\n  '.join(mapping) + '\n]\n'
+    with open(f'{include}/libcxx.imp', 'w') as f:
+        f.write(data)
+
+
+if __name__ == '__main__':
+    main()