#!/usr/bin/env python

import os
from builtins import range
from functools import reduce


def get_libcxx_paths():
    utils_path = os.path.dirname(os.path.abspath(__file__))
    script_name = os.path.basename(__file__)
    assert os.path.exists(utils_path)
    src_root = os.path.dirname(utils_path)
    include_path = os.path.join(src_root, "include")
    assert os.path.exists(include_path)
    docs_path = os.path.join(src_root, "docs")
    assert os.path.exists(docs_path)
    macro_test_path = os.path.join(
        src_root,
        "test",
        "std",
        "language.support",
        "support.limits",
        "support.limits.general",
    )
    assert os.path.exists(macro_test_path)
    assert os.path.exists(
        os.path.join(macro_test_path, "version.version.compile.pass.cpp")
    )
    return script_name, src_root, include_path, docs_path, macro_test_path


script_name, source_root, include_path, docs_path, macro_test_path = get_libcxx_paths()


def has_header(h):
    h_path = os.path.join(include_path, h)
    return os.path.exists(h_path)


def add_version_header(tc):
    tc["headers"].append("version")
    return tc


# ================  ============================================================
# Field             Description
# ================  ============================================================
# name              The name of the feature-test macro.
# values            A dict whose keys are C++ versions and whose values are the
#                   value of the feature-test macro for that C++ version.
#                   (TODO: This isn't a very clean model for feature-test
#                   macros affected by multiple papers.)
# headers           An array with the headers that should provide the
#                   feature-test macro.
# test_suite_guard  An optional string field. When this field is provided,
#                   `libcxx_guard` must also be provided. This field is used
#                   only to generate the unit tests for the feature-test macros.
#                   It can't depend on macros defined in <__config> because the
#                   `test/std/` parts of the test suite are intended to be
#                   portable to any C++ standard library implementation, not
#                   just libc++. It may depend on
#                    * macros defined by the compiler itself, or
#                    * macros generated by CMake.
#                   In some cases we add also depend on macros defined in <__availability>.
# libcxx_guard      An optional string field. When this field is provided,
#                   `test_suite_guard` must also be provided. This field is used
#                   only to guard the feature-test macro in <version>. It may
#                   be the same as `test_suite_guard`, or it may depend on
#                   macros defined in <__config>.
# unimplemented     An optional Boolean field with the value `True`. This field
#                   is only used when a feature isn't fully implemented. Once
#                   you've fully implemented the feature, you should remove
#                   this field.
# ================  ============================================================
feature_test_macros = [
    add_version_header(x)
    for x in [
        {
            "name": "__cpp_lib_adaptor_iterator_pair_constructor",
            "values": {"c++23": 202106},
            "headers": ["queue", "stack"],
        },
        {
            "name": "__cpp_lib_addressof_constexpr",
            "values": {"c++17": 201603},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_allocate_at_least",
            "values": {
                          "c++23": 202106,
                          # Note LWG3887 Version macro for allocate_at_least
                          #"c++26": 202302, # P2652R2 Disallow User Specialization of allocator_traits
                      },
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_allocator_traits_is_always_equal",
            "values": {"c++17": 201411},
            "headers": [
                "deque",
                "forward_list",
                "list",
                "map",
                "memory",
                "scoped_allocator",
                "set",
                "string",
                "unordered_map",
                "unordered_set",
                "vector",
            ],
        },
        {
            "name": "__cpp_lib_any",
            "values": {"c++17": 201606},
            "headers": ["any"],
        },
        {
            "name": "__cpp_lib_apply",
            "values": {"c++17": 201603},
            "headers": ["tuple"],
        },
        {
            "name": "__cpp_lib_array_constexpr",
            "values": {"c++17": 201603, "c++20": 201811},
            "headers": ["array", "iterator"],
        },
        {
            "name": "__cpp_lib_as_const",
            "values": {"c++17": 201510},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_associative_heterogeneous_erasure",
            "values": {"c++23": 202110},
            "headers": ["map", "set", "unordered_map", "unordered_set"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_associative_heterogeneous_insertion",
            "values": {"c++26": 202306}, # P2363R5 Extending associative containers with the remaining heterogeneous overloads
            "headers": ["map", "set", "unordered_map", "unordered_set"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_assume_aligned",
            "values": {"c++20": 201811},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_atomic_flag_test",
            "values": {"c++20": 201907},
            "headers": ["atomic"],
        },
        {
            "name": "__cpp_lib_atomic_float",
            "values": {"c++20": 201711},
            "headers": ["atomic"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_atomic_is_always_lock_free",
            "values": {"c++17": 201603},
            "headers": ["atomic"],
        },
        {
            "name": "__cpp_lib_atomic_lock_free_type_aliases",
            "values": {"c++20": 201907},
            "headers": ["atomic"],
        },
        {
            "name": "__cpp_lib_atomic_ref",
            "values": {"c++20": 201806},
            "headers": ["atomic"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_atomic_shared_ptr",
            "values": {"c++20": 201711},
            "headers": ["atomic"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_atomic_value_initialization",
            "values": {"c++20": 201911},
            "headers": ["atomic", "memory"],
        },
        {
            "name": "__cpp_lib_atomic_wait",
            "values": {"c++20": 201907},
            "headers": ["atomic"],
            "test_suite_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
        },
        {
            "name": "__cpp_lib_barrier",
            "values": {"c++20": 201907},
            "headers": ["barrier"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
        },
        {
            "name": "__cpp_lib_bind_back",
            "values": {
                          "c++23": 202202,
                          "c++26": 202306, # P2714R1 Bind front and back to NTTP callables
                      },
            "headers": ["functional"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_bind_front",
            "values": {
                          "c++20": 201907,
                          "c++26": 202306, # P2714R1 Bind front and back to NTTP callables
                      },
            "headers": ["functional"],
        },
        {
            "name": "__cpp_lib_bit_cast",
            "values": {"c++20": 201806},
            "headers": ["bit"],
        },
        {
            "name": "__cpp_lib_bitops",
            "values": {"c++20": 201907},
            "headers": ["bit"],
        },
        {
            "name": "__cpp_lib_bitset",
            "values": {"c++26": 202306}, # P2697R1 Interfacing bitset with string_view
            "headers": ["bitset"],
        },
        {
            "name": "__cpp_lib_bool_constant",
            "values": {"c++17": 201505},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_bounded_array_traits",
            "values": {"c++20": 201902},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_boyer_moore_searcher",
            "values": {"c++17": 201603},
            "headers": ["functional"],
        },
        {
            "name": "__cpp_lib_byte",
            "values": {"c++17": 201603},
            "headers": ["cstddef"],
        },
        {
            "name": "__cpp_lib_byteswap",
            "values": {"c++23": 202110},
            "headers": ["bit"],
        },
        {
            "name": "__cpp_lib_char8_t",
            "values": {"c++20": 201907},
            "headers": [
                "atomic",
                "filesystem",
                "istream",
                "limits",
                "locale",
                "ostream",
                "string",
                "string_view",
            ],
            "test_suite_guard": "defined(__cpp_char8_t)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_CHAR8_T)",
        },
        {
            "name": "__cpp_lib_chrono",
            "values": {
                          "c++17": 201611,
                          #"c++26": 202306, # P2592R3 Hashing support for std::chrono value classes
                      },
            "headers": ["chrono"],
        },
        {
            "name": "__cpp_lib_chrono_udls",
            "values": {"c++14": 201304},
            "headers": ["chrono"],
        },
        {
            "name": "__cpp_lib_clamp",
            "values": {"c++17": 201603},
            "headers": ["algorithm"],
        },
        {
            "name": "__cpp_lib_complex_udls",
            "values": {"c++14": 201309},
            "headers": ["complex"],
        },
        {
            "name": "__cpp_lib_concepts",
            "values": {"c++20": 202002},
            "headers": ["concepts"],
        },
        {
            "name": "__cpp_lib_constexpr_algorithms",
            "values": {
                          "c++20": 201806,
                          #"c++26": 202306, # P2562R1 constexpr Stable Sorting
                      },
            "headers": ["algorithm", "utility"],
        },
        {
            "name": "__cpp_lib_constexpr_bitset",
            "values": {"c++23": 202207},
            "headers": ["bitset"],
        },
        {
            "name": "__cpp_lib_constexpr_charconv",
            "values": {"c++23": 202207},
            "headers": ["charconv"],
        },
        {
            "name": "__cpp_lib_constexpr_cmath",
            "values": {"c++23": 202202},
            "headers": ["cmath", "cstdlib"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_constexpr_complex",
            "values": {"c++20": 201711},
            "headers": ["complex"],
        },
        {
            "name": "__cpp_lib_constexpr_dynamic_alloc",
            "values": {"c++20": 201907},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_constexpr_functional",
            "values": {"c++20": 201907},
            "headers": ["functional"],
        },
        {
            "name": "__cpp_lib_constexpr_iterator",
            "values": {"c++20": 201811},
            "headers": ["iterator"],
        },
        {
            "name": "__cpp_lib_constexpr_memory",
            "values": {"c++20": 201811, "c++23": 202202},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_constexpr_numeric",
            "values": {"c++20": 201911},
            "headers": ["numeric"],
        },
        {
            "name": "__cpp_lib_constexpr_string",
            "values": {"c++20": 201907},
            "headers": ["string"],
        },
        {
            "name": "__cpp_lib_constexpr_string_view",
            "values": {"c++20": 201811},
            "headers": ["string_view"],
        },
        {
            "name": "__cpp_lib_constexpr_tuple",
            "values": {"c++20": 201811},
            "headers": ["tuple"],
        },
        {
            "name": "__cpp_lib_constexpr_typeinfo",
            "values": {"c++23": 202106},
            "headers": ["typeinfo"],
        },
        {
            "name": "__cpp_lib_constexpr_utility",
            "values": {"c++20": 201811},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_constexpr_vector",
            "values": {"c++20": 201907},
            "headers": ["vector"],
        },
        {
            "name": "__cpp_lib_copyable_function",
            "values": {"c++26": 202306}, # P2548R6 copyable_function
            "headers": ["functional"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_coroutine",
            "values": {"c++20": 201902},
            "headers": ["coroutine"],
        },
        {
            "name": "__cpp_lib_destroying_delete",
            "values": {"c++20": 201806},
            "headers": ["new"],
            "test_suite_guard": "TEST_STD_VER > 17 && defined(__cpp_impl_destroying_delete) && __cpp_impl_destroying_delete >= 201806L",
            "libcxx_guard": "_LIBCPP_STD_VER >= 20 && defined(__cpp_impl_destroying_delete) && __cpp_impl_destroying_delete >= 201806L",
        },
        {
            "name": "__cpp_lib_enable_shared_from_this",
            "values": {"c++17": 201603},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_endian",
            "values": {"c++20": 201907},
            "headers": ["bit"],
        },
        {
            "name": "__cpp_lib_erase_if",
            "values": {"c++20": 202002},
            "headers": [
                "deque",
                "forward_list",
                "list",
                "map",
                "set",
                "string",
                "unordered_map",
                "unordered_set",
                "vector",
            ],
        },
        {
            "name": "__cpp_lib_exchange_function",
            "values": {"c++14": 201304},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_execution",
            "values": {"c++17": 201603, "c++20": 201902},
            "headers": ["execution"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_expected",
            "values": {"c++23": 202211},
            "headers": ["expected"],
        },
        {
            "name": "__cpp_lib_filesystem",
            "values": {"c++17": 201703},
            "headers": ["filesystem"],
            "test_suite_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_FILESYSTEM_LIBRARY)",
            "libcxx_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_FILESYSTEM_LIBRARY)",
        },
        {
            "name": "__cpp_lib_format",
            "values": {
                # "c++20": 201907 Not implemented P1361R2 Integration of chrono with text formatting
                # "c++20": 202106 Fully implemented
                # "c++20": 202110 Not implemented P2372R3 Fixing locale handling in chrono formatters
                "c++20": 202106,
                # "c++23": 202207, Not implemented P2419R2 Clarify handling of encodings in localized formatting of chrono types
            },
            # Note these three papers are adopted at the June 2023 meeting and have sequential numbering
            # 202304 P2510R3 Formatting pointers (Implemented)
            # 202305 P2757R3 Type-checking format args
            # 202306 P2637R3 Member Visit
            "headers": ["format"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_format_ranges",
            "values": {"c++23": 202207},
            "headers": ["format"],
        },
        {
            "name": "__cpp_lib_formatters",
            "values": {"c++23": 202302},
            "headers": ["stacktrace", "thread"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_forward_like",
            "values": {"c++23": 202207},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_fstream_native_handle",
            "values": {"c++26": 202306}, # P1759R6 Native handles and file streams
            "headers": ["fstream"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_function_ref",
            "values": {"c++26": 202306}, # P0792R14 function_ref: a type-erased callable reference
            "headers": ["functional"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_gcd_lcm",
            "values": {"c++17": 201606},
            "headers": ["numeric"],
        },
        {
            "name": "__cpp_lib_generic_associative_lookup",
            "values": {"c++14": 201304},
            "headers": ["map", "set"],
        },
        {
            "name": "__cpp_lib_generic_unordered_lookup",
            "values": {"c++20": 201811},
            "headers": ["unordered_map", "unordered_set"],
        },
        {
            "name": "__cpp_lib_hardware_interference_size",
            "values": {"c++17": 201703},
            "test_suite_guard": "defined(__GCC_DESTRUCTIVE_SIZE) && defined(__GCC_CONSTRUCTIVE_SIZE)",
            "libcxx_guard": "defined(__GCC_DESTRUCTIVE_SIZE) && defined(__GCC_CONSTRUCTIVE_SIZE)",
            "headers": ["new"],
        },
        {
            "name": "__cpp_lib_has_unique_object_representations",
            "values": {"c++17": 201606},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_hazard_pointer",
            "values": {"c++26": 202306},  # P2530R3 Hazard Pointers for C++26
            "headers": ["hazard_pointer"],# TODO verify this entry since the paper was underspecified.
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_hypot",
            "values": {"c++17": 201603},
            "headers": ["cmath"],
        },
        {
            "name": "__cpp_lib_incomplete_container_elements",
            "values": {"c++17": 201505},
            "headers": ["forward_list", "list", "vector"],
        },
        {
            "name": "__cpp_lib_int_pow2",
            "values": {"c++20": 202002},
            "headers": ["bit"],
        },
        {
            "name": "__cpp_lib_integer_comparison_functions",
            "values": {"c++20": 202002},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_integer_sequence",
            "values": {"c++14": 201304},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_integral_constant_callable",
            "values": {"c++14": 201304},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_interpolate",
            "values": {"c++20": 201902},
            "headers": ["cmath", "numeric"],
        },
        {
            "name": "__cpp_lib_invoke",
            "values": {"c++17": 201411},
            "headers": ["functional"],
        },
        {
            "name": "__cpp_lib_invoke_r",
            "values": {"c++23": 202106},
            "headers": ["functional"],
        },
        {
            "name": "__cpp_lib_is_aggregate",
            "values": {"c++17": 201703},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_is_constant_evaluated",
            "values": {"c++20": 201811},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_is_final",
            "values": {"c++14": 201402},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_is_invocable",
            "values": {"c++17": 201703},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_is_layout_compatible",
            "values": {"c++20": 201907},
            "headers": ["type_traits"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_is_nothrow_convertible",
            "values": {"c++20": 201806},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_is_null_pointer",
            "values": {"c++14": 201309},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_is_pointer_interconvertible",
            "values": {"c++20": 201907},
            "headers": ["type_traits"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_is_scoped_enum",
            "values": {"c++23": 202011},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_is_swappable",
            "values": {"c++17": 201603},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_jthread",
            "values": {"c++20": 201911},
            "headers": ["stop_token", "thread"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS)",
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_latch",
            "values": {"c++20": 201907},
            "headers": ["latch"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
        },
        {
            "name": "__cpp_lib_launder",
            "values": {"c++17": 201606},
            "headers": ["new"],
        },
        {
            "name": "__cpp_lib_list_remove_return_type",
            "values": {"c++20": 201806},
            "headers": ["forward_list", "list"],
        },
        {
            "name": "__cpp_lib_logical_traits",
            "values": {"c++17": 201510},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_make_from_tuple",
            "values": {"c++17": 201606},
            "headers": ["tuple"],
        },
        {
            "name": "__cpp_lib_make_reverse_iterator",
            "values": {"c++14": 201402},
            "headers": ["iterator"],
        },
        {
            "name": "__cpp_lib_make_unique",
            "values": {"c++14": 201304},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_map_try_emplace",
            "values": {"c++17": 201411},
            "headers": ["map"],
        },
        {
            "name": "__cpp_lib_math_constants",
            "values": {"c++20": 201907},
            "headers": ["numbers"],
        },
        {
            "name": "__cpp_lib_math_special_functions",
            "values": {"c++17": 201603},
            "headers": ["cmath"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_mdspan",
            "values": {"c++23": 202207},
            "headers": ["mdspan"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_memory_resource",
            "values": {"c++17": 201603},
            "headers": ["memory_resource"],
            "test_suite_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_PMR)",
            "libcxx_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_PMR)",
        },
        {
            "name": "__cpp_lib_move_iterator_concept",
            "values": {"c++20": 202207},
            "headers": ["iterator"],
        },
        {
            "name": "__cpp_lib_move_only_function",
            "values": {"c++23": 202110},
            "headers": ["functional"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_node_extract",
            "values": {"c++17": 201606},
            "headers": ["map", "set", "unordered_map", "unordered_set"],
        },
        {
            "name": "__cpp_lib_nonmember_container_access",
            "values": {"c++17": 201411},
            "headers": [
                "array",
                "deque",
                "forward_list",
                "iterator",
                "list",
                "map",
                "regex",
                "set",
                "string",
                "unordered_map",
                "unordered_set",
                "vector",
            ],
        },
        {
            "name": "__cpp_lib_not_fn",
            "values": {
                          "c++17": 201603,
                          #"c++26": 202306, # P2714R1 Bind front and back to NTTP callables
                      },
            "headers": ["functional"],
        },
        {
            "name": "__cpp_lib_null_iterators",
            "values": {"c++14": 201304},
            "headers": ["iterator"],
        },
        {
            "name": "__cpp_lib_optional",
            "values": {"c++17": 201606, "c++23": 202110},
            "headers": ["optional"],
        },
        {
            "name": "__cpp_lib_out_ptr",
            "values": {"c++23": 202106},
            "headers": ["memory"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_parallel_algorithm",
            "values": {"c++17": 201603},
            "headers": ["algorithm", "numeric"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_polymorphic_allocator",
            "values": {"c++20": 201902},
            "headers": ["memory_resource"],
            "test_suite_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_PMR)",
            "libcxx_guard": "!defined(_LIBCPP_AVAILABILITY_HAS_NO_PMR)",
        },
        {
            "name": "__cpp_lib_print",
            "values": {"c++23": 202207},
            "headers": ["ostream", "print"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_quoted_string_io",
            "values": {"c++14": 201304},
            "headers": ["iomanip"],
        },
        {
            "name": "__cpp_lib_ranges",
            "values": {"c++20": 202207},
            "headers": ["algorithm", "functional", "iterator", "memory", "ranges"],
        },
        {
            "name": "__cpp_lib_ranges_as_rvalue",
            "values": {"c++23": 202207},
            "headers": ["ranges"],
        },
        {
            "name": "__cpp_lib_ranges_chunk",
            "values": {"c++23": 202202},
            "headers": ["ranges"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ranges_chunk_by",
            "values": {"c++23": 202202},
            "headers": ["ranges"],
        },
        {
            "name": "__cpp_lib_ranges_iota",
            "values": {"c++23": 202202},
            "headers": ["numeric"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ranges_join_with",
            "values": {"c++23": 202202},
            "headers": ["ranges"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ranges_repeat",
            "values": { "c++23": 202207},
            "headers": ["ranges"],
        },
        {
            "name": "__cpp_lib_ranges_slide",
            "values": {"c++23": 202202},
            "headers": ["ranges"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ranges_starts_ends_with",
            "values": {"c++23": 202106},
            "headers": ["algorithm"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ranges_to_container",
            "values": {"c++23": 202202},
            "headers": [
                "deque",
                "forward_list",
                "list",
                "map",
                "queue",
                "ranges",
                "set",
                "stack",
                "string",
                "unordered_map",
                "unordered_set",
                "vector",
            ],
        },
        {
            "name": "__cpp_lib_ranges_zip",
            "values": {"c++23": 202110},
            "headers": ["ranges", "tuple", "utility"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ratio",
            "values": {"c++26": 202306}, # P2734R0 Adding the new SI prefixes
            "headers": ["ratio"],
        },
        {
            "name": "__cpp_lib_raw_memory_algorithms",
            "values": {"c++17": 201606},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_rcu",
            "values": {"c++26": 202306}, # P2545R4 Read-Copy Update (RCU)
            "headers": ["rcu"],          # TODO verify this entry since the paper was underspecified.
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_reference_from_temporary",
            "values": {"c++23": 202202},
            "headers": ["type_traits"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_remove_cvref",
            "values": {"c++20": 201711},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_result_of_sfinae",
            "values": {"c++14": 201210},
            "headers": ["functional", "type_traits"],
        },
        {
            "name": "__cpp_lib_robust_nonmodifying_seq_ops",
            "values": {"c++14": 201304},
            "headers": ["algorithm"],
        },
        {
            "name": "__cpp_lib_sample",
            "values": {"c++17": 201603},
            "headers": ["algorithm"],
        },
        {
            "name": "__cpp_lib_scoped_lock",
            "values": {"c++17": 201703},
            "headers": ["mutex"],
        },
        {
            "name": "__cpp_lib_semaphore",
            "values": {"c++20": 201907},
            "headers": ["semaphore"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SYNC)",
        },
        {
            "name": "__cpp_lib_shared_mutex",
            "values": {"c++17": 201505},
            "headers": ["shared_mutex"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SHARED_MUTEX)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SHARED_MUTEX)",
        },
        {
            "name": "__cpp_lib_shared_ptr_arrays",
            "values": {"c++17": 201611, "c++20": 201707},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_shared_ptr_weak_type",
            "values": {"c++17": 201606},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_shared_timed_mutex",
            "values": {"c++14": 201402},
            "headers": ["shared_mutex"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SHARED_MUTEX)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_AVAILABILITY_HAS_NO_SHARED_MUTEX)",
        },
        {
            "name": "__cpp_lib_shift",
            "values": {"c++20": 201806},
            "headers": ["algorithm"],
        },
        {
            "name": "__cpp_lib_smart_ptr_for_overwrite",
            "values": {"c++20": 202002},
            "headers": ["memory"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_smart_ptr_owner_equality",
            "values": {"c++26": 202306}, # P1901R2 Enabling the Use of weak_ptr as Keys in Unordered Associative Containers
            "headers": ["memory"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_source_location",
            "values": {"c++20": 201907},
            "headers": ["source_location"],
            "test_suite_guard": "__has_builtin(__builtin_source_location) && !(defined(TEST_APPLE_CLANG_VER) && TEST_APPLE_CLANG_VER <= 1403)",
            "libcxx_guard": "__has_builtin(__builtin_source_location) && !(defined(_LIBCPP_APPLE_CLANG_VER) && _LIBCPP_APPLE_CLANG_VER <= 1403)",
        },
        {
            "name": "__cpp_lib_span",
            "values": {"c++20": 202002},
            "headers": ["span"],
        },
        {
            "name": "__cpp_lib_spanstream",
            "values": {"c++23": 202106},
            "headers": ["spanstream"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ssize",
            "values": {"c++20": 201902},
            "headers": ["iterator"],
        },
        {
            "name": "__cpp_lib_sstream_from_string_view",
            "values": {"c++26": 202306},  # P2495R3 Interfacing stringstreams with string_view
            "headers": ["sstream"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_stacktrace",
            "values": {"c++23": 202011},
            "headers": ["stacktrace"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_starts_ends_with",
            "values": {"c++20": 201711},
            "headers": ["string", "string_view"],
        },
        {
            "name": "__cpp_lib_stdatomic_h",
            "values": {"c++23": 202011},
            "headers": ["stdatomic.h"],
        },
        {
            "name": "__cpp_lib_string_contains",
            "values": {"c++23": 202011},
            "headers": ["string", "string_view"],
        },
        {
            "name": "__cpp_lib_string_resize_and_overwrite",
            "values": {"c++23": 202110},
            "headers": ["string"],
        },
        {
            "name": "__cpp_lib_string_udls",
            "values": {"c++14": 201304},
            "headers": ["string"],
        },
        {
            "name": "__cpp_lib_string_view",
            "values": {"c++17": 201606, "c++20": 201803},
            "headers": ["string", "string_view"],
        },
        {
            "name": "__cpp_lib_submdspan",
            "values": {"c++26": 202306}, # P2630R4 submdspan
            "headers": ["mdspan"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_syncbuf",
            "values": {"c++20": 201803},
            "headers": ["syncstream"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_text_encoding",
            "values": {"c++26": 202306}, # P1885R12 Naming Text Encodings to Demystify Them
            "headers": ["text_encoding"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_three_way_comparison",
            "values": {"c++20": 201907},
            "headers": ["compare"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_to_address",
            "values": {"c++20": 201711},
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_to_array",
            "values": {"c++20": 201907},
            "headers": ["array"],
        },
        {
            "name": "__cpp_lib_to_chars",
            "values": {
                         "c++17": 201611,
                         "c++26": 202306, # P2497R0 Testing for success or failure of <charconv> functions
                      },
            "headers": ["charconv"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_to_string",
            "values": {"c++23": 202306}, # P2587R3 to_string or not to_string
            "headers": ["string"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_to_underlying",
            "values": {"c++23": 202102},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_transformation_trait_aliases",
            "values": {"c++14": 201304},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_transparent_operators",
            "values": {"c++14": 201210, "c++17": 201510},
            "headers": ["functional", "memory"],
        },
        {
            "name": "__cpp_lib_tuple_element_t",
            "values": {"c++14": 201402},
            "headers": ["tuple"],
        },
        {
            "name": "__cpp_lib_tuples_by_type",
            "values": {"c++14": 201304},
            "headers": ["tuple", "utility"],
        },
        {
            "name": "__cpp_lib_type_identity",
            "values": {"c++20": 201806},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_type_trait_variable_templates",
            "values": {"c++17": 201510},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_uncaught_exceptions",
            "values": {"c++17": 201411},
            "headers": ["exception"],
        },
        {
            "name": "__cpp_lib_unordered_map_try_emplace",
            "values": {"c++17": 201411},
            "headers": ["unordered_map"],
        },
        {
            "name": "__cpp_lib_unreachable",
            "values": {"c++23": 202202},
            "headers": ["utility"],
        },
        {
            "name": "__cpp_lib_unwrap_ref",
            "values": {"c++20": 201811},
            "headers": ["functional"],
        },
        {
            "name": "__cpp_lib_variant",
            "values": {"c++17": 202102},
            "headers": ["variant"],
        },
        {
            "name": "__cpp_lib_void_t",
            "values": {"c++17": 201411},
            "headers": ["type_traits"],
        },
        {
            "name": "__cpp_lib_within_lifetime",
            "values": {"c++26": 202306}, # P2641R4 Checking if a union alternative is active
            "headers": ["type_traits"],
            "unimplemented": True,
        },
    ]
]

assert feature_test_macros == sorted(feature_test_macros, key=lambda tc: tc["name"])
assert all(tc["headers"] == sorted(tc["headers"]) for tc in feature_test_macros)
assert all(
    ("libcxx_guard" in tc) == ("test_suite_guard" in tc) for tc in feature_test_macros
)
assert all(
    all(
        key
        in [
            "name",
            "values",
            "headers",
            "libcxx_guard",
            "test_suite_guard",
            "unimplemented",
        ]
        for key in tc.keys()
    )
    for tc in feature_test_macros
)

# Map from each header to the Lit annotations that should be used for
# tests that include that header.
#
# For example, when threads are not supported, any test that includes
# <thread> should be marked as UNSUPPORTED, because including <thread>
# is a hard error in that case.
lit_markup = {
    "barrier": ["UNSUPPORTED: no-threads"],
    "filesystem": ["UNSUPPORTED: no-filesystem"],
    "fstream": ["UNSUPPORTED: no-localization"],
    "iomanip": ["UNSUPPORTED: no-localization"],
    "ios": ["UNSUPPORTED: no-localization"],
    "iostream": ["UNSUPPORTED: no-localization"],
    "istream": ["UNSUPPORTED: no-localization"],
    "latch": ["UNSUPPORTED: no-threads"],
    "locale": ["UNSUPPORTED: no-localization"],
    "mutex": ["UNSUPPORTED: no-threads"],
    "ostream": ["UNSUPPORTED: no-localization"],
    "print": ["UNSUPPORTED: no-filesystem"],
    "regex": ["UNSUPPORTED: no-localization"],
    "semaphore": ["UNSUPPORTED: no-threads"],
    "shared_mutex": ["UNSUPPORTED: no-threads"],
    "sstream": ["UNSUPPORTED: no-localization"],
    "stdatomic.h": ["UNSUPPORTED: no-threads"],
    "stop_token": ["UNSUPPORTED: no-threads"],
    "thread": ["UNSUPPORTED: no-threads"],
}


def get_std_dialects():
    std_dialects = ["c++14", "c++17", "c++20", "c++23", "c++26"]
    return list(std_dialects)


def get_first_std(d):
    for s in get_std_dialects():
        if s in d.keys():
            return s
    return None


def get_last_std(d):
    rev_dialects = get_std_dialects()
    rev_dialects.reverse()
    for s in rev_dialects:
        if s in d.keys():
            return s
    return None


def get_std_before(d, std):
    std_dialects = get_std_dialects()
    candidates = std_dialects[0 : std_dialects.index(std)]
    candidates.reverse()
    for cand in candidates:
        if cand in d.keys():
            return cand
    return None


def get_value_before(d, std):
    new_std = get_std_before(d, std)
    if new_std is None:
        return None
    return d[new_std]


def get_for_std(d, std):
    # This catches the C++11 case for which there should be no defined feature
    # test macros.
    std_dialects = get_std_dialects()
    if std not in std_dialects:
        return None
    # Find the value for the newest C++ dialect between C++14 and std
    std_list = list(std_dialects[0 : std_dialects.index(std) + 1])
    std_list.reverse()
    for s in std_list:
        if s in d.keys():
            return d[s]
    return None


def get_std_number(std):
    return std.replace("c++", "")


"""
  Functions to produce the <version> header
"""


def produce_macros_definition_for_std(std):
    result = ""
    indent = 55
    for tc in feature_test_macros:
        if std not in tc["values"]:
            continue
        inner_indent = 1
        if "test_suite_guard" in tc.keys():
            result += "# if %s\n" % tc["libcxx_guard"]
            inner_indent += 2
        if get_value_before(tc["values"], std) is not None:
            assert "test_suite_guard" not in tc.keys()
            result += "# undef  %s\n" % tc["name"]
        line = "#%sdefine %s" % ((" " * inner_indent), tc["name"])
        line += " " * (indent - len(line))
        line += " %sL" % tc["values"][std]
        if "unimplemented" in tc.keys():
            line = "// " + line
        result += line
        result += "\n"
        if "test_suite_guard" in tc.keys():
            result += "# endif\n"
    return result.strip()


def produce_macros_definitions():
    macro_definition_template = """#if _LIBCPP_STD_VER >= {std_number}
{macro_definition}
#endif"""

    macros_definitions = []
    for std in get_std_dialects():
        macros_definitions.append(
            macro_definition_template.format(
                std_number=get_std_number(std),
                macro_definition=produce_macros_definition_for_std(std),
            )
        )

    return "\n\n".join(macros_definitions)


def chunks(l, n):
    """Yield successive n-sized chunks from l."""
    for i in range(0, len(l), n):
        yield l[i : i + n]


def produce_version_synopsis():
    indent = 56
    header_indent = 56 + len("20XXYYL ")
    result = ""

    def indent_to(s, val):
        if len(s) >= val:
            return s
        s += " " * (val - len(s))
        return s

    line = indent_to("Macro name", indent) + "Value"
    line = indent_to(line, header_indent) + "Headers"
    result += line + "\n"
    for tc in feature_test_macros:
        prev_defined_std = get_last_std(tc["values"])
        line = "{name: <{indent}}{value}L ".format(
            name=tc["name"], indent=indent, value=tc["values"][prev_defined_std]
        )
        headers = list(tc["headers"])
        headers.remove("version")
        for chunk in chunks(headers, 3):
            line = indent_to(line, header_indent)
            chunk = ["<%s>" % header for header in chunk]
            line += " ".join(chunk)
            result += line
            result += "\n"
            line = ""
        while True:
            prev_defined_std = get_std_before(tc["values"], prev_defined_std)
            if prev_defined_std is None:
                break
            result += "%s%sL // %s\n" % (
                indent_to("", indent),
                tc["values"][prev_defined_std],
                prev_defined_std.replace("c++", "C++"),
            )
    return result


def produce_version_header():
    template = """// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef _LIBCPP_VERSIONH
#define _LIBCPP_VERSIONH

/*
  version synopsis

{synopsis}

*/

#include <__assert> // all public C++ headers provide the assertion handler
#include <__config>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#  pragma GCC system_header
#endif

// clang-format off

{cxx_macros}

// clang-format on

#endif // _LIBCPP_VERSIONH
"""

    version_str = template.format(
        synopsis=produce_version_synopsis().strip(),
        cxx_macros=produce_macros_definitions(),
    )
    version_header_path = os.path.join(include_path, "version")
    with open(version_header_path, "w", newline="\n") as f:
        f.write(version_str)


"""
    Functions to produce test files
"""

test_types = {
    "undefined": """
# ifdef {name}
#   error "{name} should not be defined before {std_first}"
# endif
""",
    "test_suite_guard": """
# if {test_suite_guard}
#   ifndef {name}
#     error "{name} should be defined in {std}"
#   endif
#   if {name} != {value}
#     error "{name} should have the value {value} in {std}"
#   endif
# else
#   ifdef {name}
#     error "{name} should not be defined when the requirement '{test_suite_guard}' is not met!"
#   endif
# endif
""",
    "unimplemented": """
# if !defined(_LIBCPP_VERSION)
#   ifndef {name}
#     error "{name} should be defined in {std}"
#   endif
#   if {name} != {value}
#     error "{name} should have the value {value} in {std}"
#   endif
# else // _LIBCPP_VERSION
#   ifdef {name}
#     error "{name} should not be defined because it is unimplemented in libc++!"
#   endif
# endif
""",
    "defined": """
# ifndef {name}
#   error "{name} should be defined in {std}"
# endif
# if {name} != {value}
#   error "{name} should have the value {value} in {std}"
# endif
""",
}


def generate_std_test(test_list, std):
    result = ""
    for tc in test_list:
        val = get_for_std(tc["values"], std)
        if val is not None:
            val = "%sL" % val
        if val is None:
            result += test_types["undefined"].format(
                name=tc["name"], std_first=get_first_std(tc["values"])
            )
        elif "unimplemented" in tc.keys():
            result += test_types["unimplemented"].format(
                name=tc["name"], value=val, std=std
            )
        elif "test_suite_guard" in tc.keys():
            result += test_types["test_suite_guard"].format(
                name=tc["name"],
                value=val,
                std=std,
                test_suite_guard=tc["test_suite_guard"],
            )
        else:
            result += test_types["defined"].format(name=tc["name"], value=val, std=std)
    return result.strip()


def generate_std_tests(test_list):
    std_tests_template = """#if TEST_STD_VER < {first_std_number}

{pre_std_test}

{other_std_tests}

#elif TEST_STD_VER > {penultimate_std_number}

{last_std_test}

#endif // TEST_STD_VER > {penultimate_std_number}"""

    std_dialects = get_std_dialects()

    other_std_tests = []
    for std in std_dialects[:-1]:
        other_std_tests.append("#elif TEST_STD_VER == " + get_std_number(std))
        other_std_tests.append(generate_std_test(test_list, std))

    std_tests = std_tests_template.format(
        first_std_number=get_std_number(std_dialects[0]),
        pre_std_test=generate_std_test(test_list, "c++11"),
        other_std_tests="\n\n".join(other_std_tests),
        penultimate_std_number=get_std_number(std_dialects[-2]),
        last_std_test=generate_std_test(test_list, std_dialects[-1]),
    )

    return std_tests


def generate_synopsis(test_list):
    max_name_len = max([len(tc["name"]) for tc in test_list])
    indent = max_name_len + 8

    def mk_line(prefix, suffix):
        return "{prefix: <{max_len}}{suffix}\n".format(
            prefix=prefix, suffix=suffix, max_len=indent
        )

    result = ""
    result += mk_line("/*  Constant", "Value")
    for tc in test_list:
        prefix = "    %s" % tc["name"]
        for std in [s for s in get_std_dialects() if s in tc["values"].keys()]:
            result += mk_line(
                prefix, "%sL [%s]" % (tc["values"][std], std.replace("c++", "C++"))
            )
            prefix = ""
    result += "*/"
    return result


def produce_tests():
    headers = set([h for tc in feature_test_macros for h in tc["headers"]])
    for h in headers:
        test_list = [tc for tc in feature_test_macros if h in tc["headers"]]
        if not has_header(h):
            for tc in test_list:
                assert "unimplemented" in tc.keys()
            continue
        markup = "\n".join("// " + tag for tag in lit_markup.get(h, []))
        test_body = """//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// WARNING: This test was generated by {script_name}
// and should not be edited manually.
//
// clang-format off
{markup}
// <{header}>

// Test the feature test macros defined by <{header}>

{synopsis}

#include <{header}>
#include "test_macros.h"

{cxx_tests}

""".format(
            script_name=script_name,
            header=h,
            markup=("\n{}\n".format(markup) if markup else ""),
            synopsis=generate_synopsis(test_list),
            cxx_tests=generate_std_tests(test_list),
        )
        test_name = "{header}.version.compile.pass.cpp".format(header=h)
        out_path = os.path.join(macro_test_path, test_name)
        with open(out_path, "w", newline="\n") as f:
            f.write(test_body)


"""
    Produce documentation for the feature test macros
"""


def make_widths(grid):
    widths = []
    for i in range(0, len(grid[0])):
        cell_width = 2 + max(
            reduce(lambda x, y: x + y, [[len(row[i])] for row in grid], [])
        )
        widths += [cell_width]
    return widths


def create_table(grid, indent):
    indent_str = " " * indent
    col_widths = make_widths(grid)
    result = [indent_str + add_divider(col_widths, 2)]
    header_flag = 2
    for row_i in range(0, len(grid)):
        row = grid[row_i]
        line = indent_str + " ".join(
            [pad_cell(row[i], col_widths[i]) for i in range(0, len(row))]
        )
        result.append(line.rstrip())
        if row_i == len(grid) - 1:
            header_flag = 2
        if row[0].startswith("**"):
            header_flag += 1
        separator = indent_str + add_divider(col_widths, header_flag)
        result.append(separator.rstrip())
        header_flag = 0
    return "\n".join(result)


def add_divider(widths, header_flag):
    if header_flag == 3:
        return "=".join(["=" * w for w in widths])
    if header_flag == 2:
        return " ".join(["=" * w for w in widths])
    if header_flag == 1:
        return "-".join(["-" * w for w in widths])
    else:
        return " ".join(["-" * w for w in widths])


def pad_cell(s, length, left_align=True):
    padding = (length - len(s)) * " "
    return s + padding


def get_status_table():
    table = [["Macro Name", "Value"]]
    for std in get_std_dialects():
        table += [["**" + std.replace("c++", "C++ ") + "**", ""]]
        for tc in feature_test_macros:
            if std not in tc["values"].keys():
                continue
            value = "``%sL``" % tc["values"][std]
            if "unimplemented" in tc.keys():
                value = "*unimplemented*"
            table += [["``%s``" % tc["name"], value]]
    return table


def produce_docs():
    doc_str = """.. _FeatureTestMacroTable:

==========================
Feature Test Macro Support
==========================

.. contents::
   :local:

Overview
========

This file documents the feature test macros currently supported by libc++.

.. _feature-status:

Status
======

.. table:: Current Status
    :name: feature-status-table
    :widths: auto

{status_tables}

""".format(
        status_tables=create_table(get_status_table(), 4)
    )

    table_doc_path = os.path.join(docs_path, "FeatureTestMacroTable.rst")
    with open(table_doc_path, "w", newline="\n") as f:
        f.write(doc_str)


def main():
    produce_version_header()
    produce_tests()
    produce_docs()


if __name__ == "__main__":
    main()