#!/usr/bin/env python

import os
from builtins import range
from functools import reduce
from typing import Any, Dict, List  # Needed for python 3.8 compatibility.
import functools
import json


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
#                   <__configuration/availability.h>.
# 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": {
                # Note LWG3887 Version macro for allocate_at_least
                "c++23": 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_min_max",
            "values": {"c++26": 202403}, # P0493R5: Atomic minimum/maximum
            "headers": ["atomic"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_atomic_ref",
            "values": {"c++20": 201806},
            "headers": ["atomic"],
        },
        {
            "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_VERSION) || _LIBCPP_AVAILABILITY_HAS_SYNC",
            "libcxx_guard": "_LIBCPP_AVAILABILITY_HAS_SYNC",
        },
        {
            "name": "__cpp_lib_barrier",
            "values": {"c++20": 201907},
            "headers": ["barrier"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && (!defined(_LIBCPP_VERSION) || _LIBCPP_AVAILABILITY_HAS_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && _LIBCPP_AVAILABILITY_HAS_SYNC",
        },
        {
            "name": "__cpp_lib_bind_back",
            "values": {
                "c++23": 202202,
                # "c++26": 202306,  # P2714R1 Bind front and back to NTTP callables
            },
            "headers": ["functional"],
        },
        {
            "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_new",
            "values": {"c++26": 202406},  # P2747R2 constexpr placement new
            "headers": ["new"],
            "unimplemented": True,
        },
        {
            "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_constrained_equality",
            "values": {"c++26": 202403}, # P2944R3: Comparisons for reference_wrapper
            "headers": ["optional", "tuple", "utility", "variant"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_containers_ranges",
            "values": {"c++23": 202202},
            "headers": [
                "deque",
                "forward_list",
                "list",
                "map",
                "queue",
                "set",
                "stack",
                "string",
                "unordered_map",
                "unordered_set",
                "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_debugging",
            "values": {
                "c++26": 202311, # P2546R5 Debugging Support
                # "c++26": 202403, # P2810R4: is_debugger_present is_replaceable
            },
            "headers": ["debugging"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_default_template_type_for_algorithm_values",
            "values": {"c++26": 202403}, # P2248R8: Enabling list-initialization for algorithms
            "headers": ["algorithm", "deque", "forward_list", "list", "ranges", "string", "vector"],
            "unimplemented": True,
        },
        {
            "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_VERSION) || (!defined(_LIBCPP_HAS_NO_FILESYSTEM) && _LIBCPP_AVAILABILITY_HAS_FILESYSTEM_LIBRARY)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_FILESYSTEM) && _LIBCPP_AVAILABILITY_HAS_FILESYSTEM_LIBRARY",
        },
        {
            "name": "__cpp_lib_format",
            "values": {
                "c++20": 202110,
                # "c++23": 202207, Not implemented P2419R2 Clarify handling of encodings in localized formatting of chrono types
                # "c++26": 202306, P2637R3 Member Visit (implemented)
                # "c++26": 202311, P2918R2 Runtime format strings II (implemented)
            },
            # 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"],
        },
        {
            "name": "__cpp_lib_format_path",
            "values": {"c++26": 202403},  # P2845R8: Formatting of std::filesystem::path
            "headers": ["filesystem"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_format_ranges",
            "values": {"c++23": 202207},
            "headers": ["format"],
        },
        {
            "name": "__cpp_lib_format_uchar",
            "values": {
                "c++20": 202311  # DR P2909R4 Fix formatting of code units as integers
            },
            "headers": [
                "format"  # TODO verify this entry since the paper was underspecified.
            ],
        },
        {
            "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_freestanding_algorithm",
            "values": {
                "c++26": 202311  # P2407R5 Freestanding Library: Partial Classes
            },
            "headers": ["algorithm"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_freestanding_array",
            "values": {
                "c++26": 202311  # P2407R5 Freestanding Library: Partial Classes
            },
            "headers": ["array"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_freestanding_cstring",
            "values": {
                "c++26": 202306  # P2338R4 Freestanding Library: Character primitives and the C library
                #        202311  # P2407R5 Freestanding Library: Partial Classes
            },
            "headers": ["cstring"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_freestanding_expected",
            "values": {
                "c++26": 202311  # P2833R2 Freestanding Library: inout expected span
            },
            "headers": ["expected"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_freestanding_mdspan",
            "values": {
                "c++26": 202311  # P2833R2 Freestanding Library: inout expected span
            },
            "headers": ["mdspan"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_freestanding_optional",
            "values": {
                "c++26": 202311  # P2407R5 Freestanding Library: Partial Classes
            },
            "headers": ["optional"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_freestanding_string_view",
            "values": {
                "c++26": 202311  # P2407R5 Freestanding Library: Partial Classes
            },
            "headers": ["string_view"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_freestanding_variant",
            "values": {
                "c++26": 202311  # P2407R5 Freestanding Library: Partial Classes
            },
            "headers": ["variant"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_fstream_native_handle",
            "values": {"c++26": 202306},  # P1759R6 Native handles and file streams
            "headers": ["fstream"],
            "test_suite_guard": "!defined(_LIBCPP_VERSION) || (!defined(_LIBCPP_HAS_NO_FILESYSTEM) && !defined(_LIBCPP_HAS_NO_LOCALIZATION))",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_FILESYSTEM) && !defined(_LIBCPP_HAS_NO_LOCALIZATION)",
        },
        {
            "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_generate_random",
            "values": {"c++26": 202403}, # P1068R11: Vector API for random number generation
            "headers": ["random"],
            "unimplemented": True,
        },
        {
            "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(_LIBCPP_VERSION) || (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_inplace_vector",
            "values": {"c++26": 202406},  # P0843R14 inplace_vector
            "headers": ["inplace_vector"],
            "unimplemented": True,
        },
        {
            "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_ios_noreplace",
            "values": {"c++23": 202207},
            "headers": ["ios"],
        },
        {
            "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_is_virtual_base_of",
            "values": {
                "c++26": 202406  # P2985R0 A type trait for detecting virtual base classes
            },
            "headers": ["type_traits"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_is_within_lifetime",
            # Note this name was changed from "__cpp_lib_within_lifetime" when the paper was adopted
            # https://github.com/cplusplus/draft/commit/0facada4cadd97e1ba15bfaea76a804f1dc5c309
            "values": {
                "c++26": 202306  # P2641R4 Checking if a union alternative is active
            },
            "headers": ["type_traits"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_jthread",
            "values": {"c++20": 201911},
            "headers": ["stop_token", "thread"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_HAS_NO_EXPERIMENTAL_STOP_TOKEN) && (!defined(_LIBCPP_VERSION) || _LIBCPP_AVAILABILITY_HAS_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && !defined(_LIBCPP_HAS_NO_EXPERIMENTAL_STOP_TOKEN) && _LIBCPP_AVAILABILITY_HAS_SYNC",
        },
        {
            "name": "__cpp_lib_latch",
            "values": {"c++20": 201907},
            "headers": ["latch"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && (!defined(_LIBCPP_VERSION) || _LIBCPP_AVAILABILITY_HAS_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && _LIBCPP_AVAILABILITY_HAS_SYNC",
        },
        {
            "name": "__cpp_lib_launder",
            "values": {"c++17": 201606},
            "headers": ["new"],
        },
        {
            "name": "__cpp_lib_linalg",
            "values": {
                "c++26": 202311  # P1673 A free function linear algebra interface based on the BLAS
            },
            "headers": ["linalg"],
            "unimplemented": True,
        },
        {
            "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,
                "c++26": 202406,  # P2389R2 dextents Index Type Parameter
            },
            "headers": ["mdspan"],
        },
        {
            "name": "__cpp_lib_memory_resource",
            "values": {"c++17": 201603},
            "headers": ["memory_resource"],
            "test_suite_guard": "!defined(_LIBCPP_VERSION) || _LIBCPP_AVAILABILITY_HAS_PMR",
            "libcxx_guard": "_LIBCPP_AVAILABILITY_HAS_PMR",
        },
        {
            "name": "__cpp_lib_modules",
            "values": {"c++23": 202207},
            "headers": [],
        },
        {
            "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_optional_range_support",
            "values": {"c++26": 202406},  # P3168R2 Give std::optional Range Support
            "headers": ["optional"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_out_ptr",
            "values": {
                "c++23": 202106,
                "c++26": 202311,  # P2833R2 Freestanding Library: inout expected span
            },
            "headers": ["memory"],
        },
        {
            "name": "__cpp_lib_parallel_algorithm",
            "values": {"c++17": 201603},
            "headers": ["algorithm", "numeric"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_philox_engine",
            "values": {
                "c++26": 202406
            },  # P2075R6 Philox as an extension of the C++ RNG engines
            # Note the paper mentions 202310L as value, which differs from the typical procedure.
            "headers": ["random"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_polymorphic_allocator",
            "values": {"c++20": 201902},
            "headers": ["memory_resource"],
            "test_suite_guard": "!defined(_LIBCPP_VERSION) || _LIBCPP_AVAILABILITY_HAS_PMR",
            "libcxx_guard": "_LIBCPP_AVAILABILITY_HAS_PMR",
        },
        {
            "name": "__cpp_lib_print",
            "values": {
                "c++23": 202207,
                # "c++26": 202403, # P3107R5: Permit an efficient implementation of std::print
                # "c++26": 202406, # P3235R3 std::print more types faster with less memory
            },
            "headers": ["ostream", "print"],
        },
        {
            "name": "__cpp_lib_quoted_string_io",
            "values": {"c++14": 201304},
            "headers": ["iomanip"],
            "test_suite_guard": "!defined(_LIBCPP_VERSION) || !defined(_LIBCPP_HAS_NO_LOCALIZATION)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_LOCALIZATION)",
        },
        {
            "name": "__cpp_lib_ranges",
            "values": {
                "c++20": 202207,
                # "c++23": 202302,  # Relaxing Ranges Just A Smidge
                # "c++26": 202406,  # P2997R1 Removing the common reference requirement from the indirectly invocable concepts (already implemented as a DR)
            },
            "headers": ["algorithm", "functional", "iterator", "memory", "ranges"],
        },
        {
            "name": "__cpp_lib_ranges_as_const",
            "values": {
                "c++23": 202207  # P2278R4 cbegin should always return a constant iterator
                #        202311  # DR P2836R1 std::basic_const_iterator should follow its underlying type’s convertibility
            },
            "headers": ["ranges"],
            "unimplemented": True,
        },
        {
            "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_concat",
            "values": {"c++26": 202403}, # P2542R8: views::concat
            "headers": ["ranges"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_ranges_contains",
            "values": {"c++23": 202207},
            "headers": ["algorithm"],
        },
        {
            "name": "__cpp_lib_ranges_find_last",
            "values": {"c++23": 202207},
            "headers": ["algorithm"],
        },
        {
            "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"],
        },
        {
            "name": "__cpp_lib_ranges_to_container",
            "values": {"c++23": 202202},
            "headers": ["ranges"],
        },
        {
            "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_reference_wrapper",
            "values": {"c++26": 202403}, # P2944R3: Comparisons for reference_wrapper
            "headers": ["functional"],
        },
        {
            "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_saturation_arithmetic",
            "values": {"c++26": 202311},  # P0543R3 Saturation arithmetic
            "headers": ["numeric"],
        },
        {
            "name": "__cpp_lib_scoped_lock",
            "values": {"c++17": 201703},
            "headers": ["mutex"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS)",
        },
        {
            "name": "__cpp_lib_semaphore",
            "values": {"c++20": 201907},
            "headers": ["semaphore"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && (!defined(_LIBCPP_VERSION) || _LIBCPP_AVAILABILITY_HAS_SYNC)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS) && _LIBCPP_AVAILABILITY_HAS_SYNC",
        },
        {
            "name": "__cpp_lib_senders",
            "values": {"c++26": 202406},  # P2300R10 std::execution
            "headers": ["execution"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_shared_mutex",
            "values": {"c++17": 201505},
            "headers": ["shared_mutex"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_THREADS)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS)",
        },
        {
            "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)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_THREADS)",
        },
        {
            "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"],
        },
        {
            "name": "__cpp_lib_span",
            "values": {
                "c++20": 202002,
                # "c++26": 202311,  # P2821R5 span.at()
                #          202311   # P2833R2 Freestanding Library: inout expected span
            },
            "headers": ["span"],
        },
        {
            "name": "__cpp_lib_span_at",
            "values": {"c++26": 202311},  # P2821R3 span.at()
            "headers": ["span"],
        },
        {
            "name": "__cpp_lib_span_initializer_list",
            "values": {"c++26": 202311},  # P2447R6 std::span over an initializer list
            "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"],
        },
        {
            "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,
                "c++26": 202403,  # P2591R5: Concatenation of strings and string views
            },
            "headers": ["string", "string_view"],
        },
        {
            "name": "__cpp_lib_submdspan",
            "values": {
                "c++26": 202306, # P2630R4: submdspan
                # "c++26": 202403, # P2642R6: Padded mdspan layouts
            },
            "headers": ["mdspan"],
            "unimplemented": True,
        },
        {
            "name": "__cpp_lib_syncbuf",
            "values": {"c++20": 201803},
            "headers": ["syncstream"],
            "test_suite_guard": "!defined(_LIBCPP_HAS_NO_EXPERIMENTAL_SYNCSTREAM)",
            "libcxx_guard": "!defined(_LIBCPP_HAS_NO_EXPERIMENTAL_SYNCSTREAM)",
        },
        {
            "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"],
        },
        {
            "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++26": 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_tuple_like",
            "values": {
                "c++23": 202207,  # P2165R4 Compatibility between tuple, pair and tuple-like objects
                "c++26": 202311,  # P2819R2 Add tuple protocol to complex (implemented)
            },
            "headers": ["map", "tuple", "unordered_map", "utility"],
            "unimplemented": True,
        },
        {
            "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,  # std::visit for classes derived from std::variant
                # "c++20": 202106,  # Fully constexpr std::variant
                # "c++26": 202306,  # Member visit (implemented)
            },
            "headers": ["variant"],
        },
        {
            "name": "__cpp_lib_void_t",
            "values": {"c++17": 201411},
            "headers": ["type_traits"],
        },
    ]
]

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

# 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"],
    "syncstream": ["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 <__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 get_ftms(
    data, std_dialects: List[str], use_implemented_status: bool
) -> Dict[str, Dict[str, Any]]:
    """Impementation for FeatureTestMacros.(standard|implemented)_ftms()."""
    result = dict()
    for feature in data:
        last = None
        entry = dict()
        implemented = True
        for std in std_dialects:
            if std not in feature["values"].keys():
                if last == None:
                    continue
                else:
                    entry[std] = last
            else:
                if implemented:
                    values = feature["values"][std]
                    assert len(values) > 0, f"{feature['name']}[{std}] has no entries"
                    for value in values:
                        papers = list(values[value])
                        assert (
                            len(papers) > 0
                        ), f"{feature['name']}[{std}][{value}] has no entries"
                        for paper in papers:
                            if use_implemented_status and not paper["implemented"]:
                                implemented = False
                                break
                        if implemented:
                            last = f"{value}L"
                        else:
                            break

                entry[std] = last
        result[feature["name"]] = entry

    return result


def generate_version_header_dialect_block(data: Dict[str, Any]) -> str:
    """Generates the contents of the version header for a dialect.

    This generates the contents of a
      #if  _LIBCPP_STD_VER >= XY
      #endif // _LIBCPP_STD_VER >= XY
    block.
    """
    result = ""
    for element in data:
        for ftm, entry in element.items():
            if not entry["implemented"]:
                # When a FTM is not implemented don't add the guards
                # or undefine the (possibly) defined macro.
                result += f'// define {ftm} {entry["value"]}\n'
            else:
                need_undef = entry["need_undef"]
                if entry["condition"]:
                    result += f'#  if {entry["condition"]}\n'
                    if entry["need_undef"]:
                        result += f"#    undef {ftm}\n"
                    result += f'#    define {ftm} {entry["value"]}\n'
                    result += f"#  endif\n"
                else:
                    if entry["need_undef"]:
                        result += f"#  undef {ftm}\n"
                    result += f'#  define {ftm} {entry["value"]}\n'

    return result


def generate_version_header_implementation(data: Dict[str, Dict[str, Any]]) -> str:
    """Generates the body of the version header."""

    template = """#if _LIBCPP_STD_VER >= {dialect}
{feature_test_macros}#endif // _LIBCPP_STD_VER >= {dialect}"""

    result = []
    for std, ftms in data.items():
        result.append(
            template.format(
                dialect=std,
                feature_test_macros=generate_version_header_dialect_block(ftms),
            )
        )

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


class FeatureTestMacros:
    """Provides all feature-test macro (FTM) output components.

    The class has several generators to use the feature-test macros in libc++:
    - FTM status page
    - The version header and its tests

    This class is not intended to duplicate
    https://isocpp.org/std/standing-documents/sd-6-sg10-feature-test-recommendations#library-feature-test-macros
    SD-FeatureTest: Feature-Test Macros and Policies

    Historically libc++ did not list all papers affecting a FTM, the new data
    structure is able to do that. However there is no intention to add the
    historical data. After papers have been implemented this information can be
    removed. For example, __cpp_lib_format's value 201907 requires 3 papers,
    once implemented it can be reduced to 1 paper and remove the paper number
    and title. This would reduce the size of the data.

    The input data is stored in the following JSON format:
    [ # A list with multiple feature-test macro entries.
      {
        # required
        # The name of the feature test macro. These names should be unique and
        # sorted in the list.
        "name": "__cpp_lib_any",

        # required
        # A map with the value of the FTM based on the language standard. Only
        # the versions in which the value of the FTM changes are listed. For
        # example, this macro's value does not change in C++20 so it does not
        # list C++20. If it changes in C++26, it will have entries for C++17 and
        # C++26.
        "values": {

          # required
          # The language standard, also named dialect in this class.
          "c++17": {

            # required
            # The value of the feature test macro. This contains an array with
            # one or more papers that need to be implemented before this value
            # is considered implemented.
            "201606": [
              {
                # optional
                # Contains the paper number that is part of the FTM version.
                "number": "P0220R1",

                # optional
                # Contains the title of the paper that is part of the FTM
                # version.
                "title": "Adopt Library Fundamentals V1 TS Components for C++17"

                # required
                # The implementation status of the paper.
                "implemented": true
              }
            ]
          }
        },

        # required
        # A sorted list of headers that should provide the FTM. The header
        # <version> is automatically added to this list. This list could be
        # empty. For example, __cpp_lib_modules is only present in version.
        # Requiring the field makes it easier to detect accidental omission.
        "headers": [
          "any"
        ],

        # optional, required when libcxx_guard is present
        # 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>.
        "test_suite_guard": "!defined(_LIBCPP_VERSION) || _LIBCPP_AVAILABILITY_HAS_PMR"

        # optional, required when test_suite_guard is present
        # 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>.
        "libcxx_guard": "_LIBCPP_AVAILABILITY_HAS_PMR"
      },
    ]
    """

    # The JSON data structure.
    __data = None

    def __init__(self, filename: str):
        """Initializes the class with the JSON data in the file 'filename'."""
        self.__data = json.load(open(filename))

    @functools.cached_property
    def std_dialects(self) -> List[str]:
        """Returns the C++ dialects avaiable.

        The available dialects are based on the 'c++xy' keys found the 'values'
        entries in '__data'. So when WG21 starts to feature-test macros for a
        future C++ Standard this dialect will automatically be available.

        The return value is a sorted list with the C++ dialects used. Since FTM
        were added in C++14 the list will not contain C++03 or C++11.
        """
        dialects = set()
        for feature in self.__data:
            keys = feature["values"].keys()
            assert len(keys) > 0, "'values' is empty"
            dialects |= keys

        return sorted(list(dialects))

    @functools.cached_property
    def standard_ftms(self) -> Dict[str, Dict[str, Any]]:
        """Returns the FTM versions per dialect in the Standard.

        This function does not use the 'implemented' flag. The output contains
        the versions used in the Standard. When a FTM in libc++ is not
        implemented according to the Standard to output may opt to show the
        expected value.

        The result is a dict with the following content
        - key: Name of the feature test macro.
        - value: A dict with the following content:
          * key: The version of the C++ dialect.
          * value: The value of the feature-test macro.
        """
        return get_ftms(self.__data, self.std_dialects, False)

    @functools.cached_property
    def implemented_ftms(self) -> Dict[str, Dict[str, Any]]:
        """Returns the FTM versions per dialect implemented in libc++.

        Unlike `get_std_dialect_versions` this function uses the 'implemented'
        flag. This returns the actual implementation status in libc++.

        The result is a dict with the following content
        - key: Name of the feature test macro.
        - value: A dict with the following content:
          * key: The version of the C++ dialect.
          * value: The value of the feature-test macro. When a feature-test
            macro is not implemented its value is None.
        """

        return get_ftms(self.__data, self.std_dialects, True)

    @functools.cached_property
    def ftm_metadata(self) -> Dict[str, Dict[str, Any]]:
        """Returns the metadata of the FTMs defined in the Standard.

        The metadata does not depend on the C++ dialect used.
        The result is a dict with the following contents:
        - key: Name of the feature test macro.
        - value: A dict with the following content:
          * headers: The list of headers that should provide the FTM
          * test_suite_guard: The condition for testing the FTM in the test suite.
          * test_suite_guard: The condition for testing the FTM in the version header.
        """
        result = dict()
        for feature in self.__data:
            entry = dict()
            entry["headers"] = feature["headers"]
            entry["test_suite_guard"] = feature.get("test_suite_guard", None)
            entry["libcxx_guard"] = feature.get("libcxx_guard", None)
            result[feature["name"]] = entry

        return result

    @property
    def version_header_implementation(self) -> Dict[str, List[Dict[str, Any]]]:
        """Generates the body of the version header."""
        result = dict()
        for std in self.std_dialects:
            result[get_std_number(std)] = list()

        for ftm, values in self.standard_ftms.items():
            need_undef = False
            last_value = None
            for std, value in values.items():
                # When a newer Standard does not change the value of the macro
                # there is no need to redefine it with the same value.
                if last_value and value == last_value:
                    continue
                last_value = value

                entry = dict()
                entry["value"] = value
                entry["implemented"] = self.implemented_ftms[ftm][std] != None
                entry["need_undef"] = need_undef
                entry["condition"] = self.ftm_metadata[ftm]["libcxx_guard"]

                need_undef = entry["implemented"]

                result[get_std_number(std)].append(dict({ftm: entry}))

        return result

    @property
    def version_header(self) -> str:
        """Generates the 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_VERSION
#define _LIBCPP_VERSION

#include <__config>

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

{feature_test_macros}

#endif // _LIBCPP_VERSION
"""
        return template.format(
            feature_test_macros=generate_version_header_implementation(
                self.version_header_implementation
            )
        )


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

    # Example how to use the new version header generation function to generate
    # the file.
    if False:
        ftm = FeatureTestMacros(
            os.path.join(
                source_root, "test", "libcxx", "feature_test_macro", "test_data.json"
            )
        )
        version_header_path = os.path.join(include_path, "version")
        with open(version_header_path, "w", newline="\n") as f:
            f.write(ftm.version_header)


if __name__ == "__main__":
    main()