{"id":106384,"date":"2022-03-25T07:00:00","date_gmt":"2022-03-25T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106384"},"modified":"2022-03-25T07:17:46","modified_gmt":"2022-03-25T14:17:46","slug":"20220325-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220325-00\/?p=106384","title":{"rendered":"Behind C++\/WinRT: How does C++\/WinRT get the list of implemented interfaces?"},"content":{"rendered":"<p>Last time, we <a title=\"Behind C++\/WinRT: How does C++\/WinRT decide which interfaces are implemented?\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220324-00\/?p=106381\"> looked at how C++\/WinRT decides which interfaces are implemented<\/a>. The <code>is_interface<\/code> type is just part of the larger template metaprogramming infrastructure inside C++\/WinRT.<\/p>\n<p>Today, we&#8217;ll reverse-engineer the <code>interface_<wbr \/>list&lt;...&gt;<\/code> template type, which holds a list of interfaces inside the <code>...<\/code>.<\/p>\n<pre>template &lt;typename...&gt; struct interface_list;\r\n\r\ntemplate &lt;&gt;\r\nstruct interface_list&lt;&gt;\r\n{\r\n    template &lt;typename T, typename Predicate&gt;\r\n    static constexpr void* find(const T*, const Predicate&amp;) noexcept\r\n    {\r\n        return nullptr;\r\n    }\r\n};\r\n<\/pre>\n<p>The base case is an empty interface list. In that case, there are no interfaces, and any attempt to find one always fails.<\/p>\n<pre>template &lt;typename First, typename ... Rest&gt;\r\nstruct interface_list&lt;First, Rest...&gt;\r\n{\r\n    template &lt;typename T, typename Predicate&gt;\r\n    static constexpr void* find(const T* obj, const Predicate&amp; pred) noexcept\r\n    {\r\n        if (pred.template test&lt;First&gt;())\r\n        {\r\n            return to_abi&lt;First&gt;(obj);\r\n        }\r\n        return interface_list&lt;Rest...&gt;::find(obj, pred);\r\n    }\r\n    using first_interface = First;\r\n};\r\n<\/pre>\n<p>The recursive case is an interface list of at least one element. That element is called <code>First<\/code>, and is given the member type name <code>first_<wbr \/>interface<\/code> for later extraction. The rest of the elements are called <code>Rest<\/code>.<\/p>\n<p>The <code>interface_<wbr \/>list&lt;...&gt;<\/code> has a <code>find<\/code> method that looks for the first interface that satisfies a given predicate. From the usage pattern, you can see that the expected pattern for the predicate is<\/p>\n<pre>class Predicate\r\n{\r\npublic:\r\n    template&lt;typename I&gt; bool test() const noexcept\r\n    {\r\n        return \"true\" if the interface \"I\" passes the test\r\n    }\r\n};\r\n<\/pre>\n<p>You can infer this because<\/p>\n<ul>\n<li>The <code>test<\/code> method must be public because we call it from outside the class.<\/li>\n<li>We call the <code>test&lt;First&gt;()<\/code> method, so the template parameter is the interface to test.<\/li>\n<li>The return value is used by the <code>if<\/code> statement, so it should be a <code>bool<\/code> (or at least be <code>bool<\/code>-like).<\/li>\n<li>We invoke it on a const <code>pred<\/code> object, so the method must be <code>const<\/code>.<\/li>\n<li>The containing function is <code>noexcept<\/code> so <code>test()<\/code> should be <code>noexcept<\/code> as well.<\/li>\n<\/ul>\n<p>In the base case, there are no interfaces, so clearly there are no matches, so it just returns <code>nullptr<\/code>.<\/p>\n<p>In the recursive case, it asks the predicate to test the first interface. If so, the we return <code>to_abi&lt;First&gt;(obj)<\/code>. Otherwise we call oureslves recursively to test the other interfaces.<\/p>\n<p>Template metaprogramming traditionally involves a lot of recursion.\u00b9<\/p>\n<p>The next helper is this guy:<\/p>\n<pre>template &lt;typename, typename&gt; struct interface_list_append_impl;\r\n\r\ntemplate &lt;typename... T, typename... U&gt;\r\nstruct interface_list_append_impl&lt;interface_list&lt;T...&gt;, interface_list&lt;U...&gt;&gt;\r\n{\r\n    using type = interface_list&lt;T..., U...&gt;;\r\n};\r\n<\/pre>\n<p>The <code>interface_<wbr \/>list_<wbr \/>append_<wbr \/>impl<\/code> class appends two interface lists. It extracts the interfaces from two interface lists (calling them <code>T...<\/code> and <code>U...<\/code>) and then creates a new interface list called <code>type<\/code> whose interfaces are the concatenation of <code>T...<\/code> and <code>U...<\/code>.<\/p>\n<p>To concatenate two interface lists, you would say<\/p>\n<pre>using result = interface_list_append_impl&lt;list1, list2&gt;::type;\r\n<\/pre>\n<p>Two patterns common to template metaprogramming are the &#8220;type&#8221; pattern and the &#8220;value&#8221; pattern. You create a class whose job is to perform some template metaprogramming task that produces a type or value. In order to express a type, you define a nested type called <code>type<\/code> which is aliased to to the produced type. And to express a value, you define a <code>static const<\/code> (or <code>constexpr<\/code> starting in C++11) member called <code>value<\/code> which has the produced value.<\/p>\n<p>The first complex operation on interface lists is filtering:<\/p>\n<pre>template &lt;template &lt;typename&gt; class, typename...&gt;\r\nstruct filter_impl;\r\n<\/pre>\n<p>This weird declaration says that <code>filter_<wbr \/>impl<\/code> is a templated class whose first template parameter is another template (which takes a single type template parameter), followed by zero or more additional types.<\/p>\n<p>Before implementing the <code>filter_<wbr \/>impl<\/code>, we give it a prettier name:<\/p>\n<pre>template &lt;template &lt;typename&gt; class Predicate, typename... T&gt;\r\nusing filter = typename filter_impl&lt;Predicate, unwrap_implements_t&lt;T&gt;...&gt;::type;\r\n<\/pre>\n<p>This is another common extension to the &#8220;type&#8221; and &#8220;value&#8221; patterns: Starting in C++11, you can define custom templated types or values that extract the type or value from the templated class. Here, we make <code>filter&lt;...&gt;<\/code> a typing-saver for <code>filter_impl&lt;...&gt;::type<\/code>, with the extra wrinkle that the types that come after the predicate pass through <code>unwrap_<wbr \/>implements_t<\/code>. (We&#8217;ll look at <code>unwrap_<wbr \/>implements_t<\/code> some other time. The focus here is on the interface list template metaprogramming.)<\/p>\n<p>This <code>using<\/code> statement also teaches us that the first template parameter is a predicate, seeing as it&#8217;s named <code>Predicate<\/code>.<\/p>\n<p>Okay, now we start implementing <code>filter_<wbr \/>impl<\/code>:<\/p>\n<pre>template &lt;template &lt;typename&gt; class Predicate&gt;\r\nstruct filter_impl&lt;Predicate&gt;\r\n{\r\n    using type = interface_list&lt;&gt;;\r\n};\r\n<\/pre>\n<p>The base case is filtering an empty list of types, which is easy: You get an empty interface list.<\/p>\n<p>Next comes the recursive case:<\/p>\n<pre>template &lt;template &lt;typename&gt; class Predicate, typename T, typename... Rest&gt;\r\nstruct filter_impl&lt;Predicate, T, Rest...&gt;\r\n{\r\n    using type = typename interface_list_append_impl&lt;\r\n        std::conditional_t&lt;\r\n        Predicate&lt;T&gt;::value,\r\n        interface_list&lt;winrt::impl::uncloak&lt;T&gt;&gt;,\r\n        interface_list&lt;&gt;\r\n        &gt;,\r\n        typename filter_impl&lt;Predicate, Rest...&gt;::type\r\n    &gt;::type;\r\n};\r\n<\/pre>\n<p>We test the predicate by looking for <code>Predicate&lt;T&gt;::value<\/code> and treating it as a <code>bool<\/code>. Therefore the <code>Predicate<\/code> is expected to follow the value pattern:<\/p>\n<pre>template&lt;typename I&gt;\r\nclass Predicate\r\n{\r\n    static constexpr bool value =\r\n        \"true\" if interface \"I\" satisfies the predicate;\r\n}\r\n<\/pre>\n<p><code>std::conditional_t<\/code> is a type-trait helper that is called like this:<\/p>\n<pre>std::conditional_t&lt;condition, if_true, if_false&gt;\r\n<\/pre>\n<p>If the condition is <code>true<\/code>, then the <code>std::conditional_t<\/code> resolves to the type <code>if_true.<\/code> Otherwise, it resolves to <code>if_false<\/code>.<\/p>\n<p>In this case, if the first interface in the interface list passes the test, then the <code>std::conditional_t<\/code> produces a single-element <code>interface_<wbr \/>list<\/code> consisting of the uncloaked version of the interface. (We&#8217;ll look at uncloaking later.) Otherwise, it produces a zero-element interface list.<\/p>\n<p>This interface list is then combined via <code>interface_<wbr \/>list_<wbr \/>append_<wbr \/>impl<\/code> with a recursive call to process the rest of the list, and we extract the resulting type.<\/p>\n<p>What this ultimately does is produce a type that is an <code>interface_<wbr \/>list<\/code> where the elements of the list are the interfaces which satisfy the predicate.<\/p>\n<p>Next comes an alternate way of invoking the filter:<\/p>\n<pre>template &lt;template &lt;typename&gt; class Predicate, typename ... T, typename ... Rest&gt;\r\nstruct filter_impl&lt;Predicate, interface_list&lt;T...&gt;, Rest...&gt;\r\n{\r\n    using type = typename interface_list_append_impl&lt;\r\n        filter&lt;Predicate, T...&gt;,\r\n        filter&lt;Predicate, Rest...&gt;\r\n    &gt;::type;\r\n};\r\n<\/pre>\n<p>This is a convenience helper which lets you apply a filter to an existing <code>interface_<wbr \/>list<\/code>, as well as optional additional types. It extracts the interfaces from the <code>interface_<wbr \/>list<\/code> and then filters them, and then also filters any additional types. (Since this is a recursive call, those additional types might themselves be <code>interface_<wbr \/>list<\/code> types, in which case the inner types will be extracted from those types as well.)<\/p>\n<p>And another convenience helper that will lead us to the answer to the puzzle we solved earlier this week:<\/p>\n<pre>template &lt;template &lt;typename&gt; class Predicate, typename D, typename ... I, typename ... Rest&gt;\r\nstruct filter_impl&lt;Predicate, winrt::implements&lt;D, I...&gt;, Rest...&gt;\r\n{\r\n    using type = typename interface_list_append_impl&lt;\r\n        filter&lt;Predicate, I...&gt;,\r\n        filter&lt;Predicate, Rest...&gt;\r\n    &gt;::type;\r\n};\r\n<\/pre>\n<p>If the first type after the predicate is an <code>implements<\/code>, it extracts the second and subsequent template parameters from the <code>implements<\/code> template type and filters those, and then continues recursively with any remaining types.<\/p>\n<p>We&#8217;re getting close to our goal of understanding the puzzle:<\/p>\n<pre>template &lt;typename T&gt;\r\nusing implemented_interfaces = filter&lt;is_interface, typename T::implements_type&gt;;\r\n<\/pre>\n<p>This defines a helper type <code>implements_<wbr \/>interfaces<\/code>: Given a type, it pulls out the <code>implements_<wbr \/>type<\/code> and filters it with the <code>is_<wbr \/>interface<\/code> predicate.<\/p>\n<p>The <code>implements_<wbr \/>type<\/code> is a type that the <code>implements&lt;&gt;<\/code> template defines so it can find itself later:<\/p>\n<pre>template &lt;typename D, typename... I&gt;\r\nstruct implements : impl::producers&lt;D, I...&gt;,\r\n                    impl::base_implements&lt;D, I...&gt;::type\r\n{\r\n...\r\npublic:\r\n\r\n    using implements_type = implements;\r\n ...\r\n};\r\n<\/pre>\n<p>Note that we are taking advantage of C++ <a href=\"https:\/\/en.cppreference.com\/w\/cpp\/language\/injected-class-name\"> injected class names<\/a> which lets us write <code>implements<\/code> instead of the longer <code>mplements&lt;D, I...&gt;<\/code>. (The reason we have an explicit <code>implements_type<\/code> subtype is that other classes in C++\/WinRT also define an <code>implements_type<\/code>, so this type name allows uniform access to the implemented thing.)<\/p>\n<p>The <code>is_<wbr \/>interface<\/code> class we discussed last time is the final piece of the puzzle: The interfaces <code>I...<\/code> passed to <code>implements&lt;D, I...&gt;<\/code> are filtered through <code>is_<wbr \/>interface<\/code> to produce an <code>interface_<wbr \/>list&lt;...&gt;<\/code> which holds all of the interfaces that are implemented.<\/p>\n<p>The error that we got was complaining that there was no definition for <code>first_<wbr \/>interface<\/code>, and from the definition at the start of this article, we see that the definition is present only if the interface list is nonempty.<\/p>\n<p>Putting it all together, we see that the error occurred because none of the <code>I...<\/code> types was recognized as an interface by <code>is_<wbr \/>interface<\/code>, so the interface list ended up empty, and in order to <code>make<\/code> an object, it has to implement at least one interface. (Because without any interfaces, what you have isn&#8217;t even a COM object.)<\/p>\n<p><b>Bonus chatter<\/b>: C++ template metaprogramming is like programming in Prolog without a debugger.<\/p>\n<p>\u00b9 The introduction of fold expressions in C++17 provides an opportunity to convert recursion to iteration. The trick is to rephrase your loop in terms of a fold expression. In this case, we could have written it as<\/p>\n<pre>template&lt;typename I, typename T, typename Predicate&gt;\r\nvoid find_interface_helper(\r\n    const T* obj, const Predicate&amp; pred,\r\n    bool&amp; found, void*&amp; result)\r\n    noexcept\r\n{\r\n    if (!found &amp;&amp; pred.template test&lt;I&gt;()) {\r\n        found = true;\r\n        result = to_abi&lt;I&gt;(obj);\r\n    }\r\n}\r\n\r\ntemplate &lt;typename...Interfaces&gt;\r\nstruct interface_list\r\n{\r\n    template &lt;typename T, typename Predicate&gt;\r\n    static constexpr void* find(const T* obj, const Predicate&amp; pred) noexcept\r\n    {\r\n        bool found = false;\r\n        void* result = nullptr;\r\n        (find_interface_helper&lt;Interfaces&gt;(obj, pred, found, result), ...);\r\n        return result;\r\n    }\r\n};\r\n<\/pre>\n<p>but it&#8217;s not clear that the effort was worth it. Fold expressions don&#8217;t have a way to <code>break<\/code> out of the loop, so we need a <code>found<\/code> variable that we use to cause the remaining calls to have no effect once a candidate is found.<\/p>\n<p>Aha, maybe we can fold using a short-circuiting operator. The short circuiting lets us &#8220;break&#8221; out of a &#8220;loop&#8221;.<\/p>\n<pre>template&lt;typename I, typename T, typename Predicate&gt;\r\nbool find_interface_helper(\r\n    const T* obj, const Predicate&amp; pred,\r\n    void*&amp; result) noexcept\r\n{\r\n    if (pred.template test&lt;I&gt;()) {\r\n        result = to_abi&lt;I&gt;(obj);\r\n        return true;\r\n    }\r\n    return false;\r\n}\r\n\r\ntemplate &lt;typename...Interfaces&gt;\r\nstruct interface_list\r\n{\r\n    template &lt;typename T, typename Predicate&gt;\r\n    static constexpr void* find(const T* obj, const Predicate&amp; pred) noexcept\r\n    {\r\n        void* result = nullptr;\r\n        (find_interface_helper&lt;Interfaces&gt;(obj, pred, result) || ...);\r\n        return result;\r\n    }\r\n};\r\n<\/pre>\n<p>And now we can inline the <code>find_<wbr \/>interface_<wbr \/>helper<\/code>:<\/p>\n<pre>template &lt;typename...Interfaces&gt;\r\nstruct interface_list\r\n{\r\n    template &lt;typename T, typename Predicate&gt;\r\n    static constexpr void* find(const T* obj, const Predicate&amp; pred) noexcept\r\n    {\r\n        void* result = nullptr;\r\n        ([&amp;] {\r\n            if (pred.template test&lt;Interfaces&gt;()) {\r\n                 result = to_abi&lt;Interfaces&gt;(obj);\r\n                return true;\r\n            }\r\n            return false;\r\n        }() || ...);\r\n        return result;\r\n    }\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Doing some template metaprogramming reverse engineering.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-106384","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Doing some template metaprogramming reverse engineering.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106384","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=106384"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106384\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=106384"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106384"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106384"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}