https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103240
--- Comment #7 from frankhb1989 at gmail dot com ---
(In reply to Jonathan Wakely from comment #6)
> What are the mangled type names that are unordered? (that's all you need to
> describe, everything about flat_map and partition_point is irrelevant; just
> tell us which names are unordered).
Here are the pair of the unordered names in the actual case:
1.
St5_BindIFPFN3NPL15ReductionStatusERNS0_8TermNodeERNS0_11ContextNodeEESt17reference_wrapperIS2_ESt12_PlaceholderILi1EEEE
2.
St5_BindIFZN3NPL2A112_GLOBAL__N_113DoDefineOrSetILb0EE4CallIJEEENS0_15ReductionStatusERNS0_8TermNodeERNS0_11ContextNodeESt10shared_ptrINS0_11EnvironmentEES8_DpOT_EUlRKS7_RKSD_E_S7_SD_EE
Here is the reduced program (exactly from the actual case) to show the sequence
and the ordering:
#include <iostream>
#include <typeinfo>
#include <typeindex>
#include <cassert>
#include <vector>
#include <functional>
#include <memory>
std::vector<std::type_index> v;
namespace ystdex
{
template<typename, typename>
struct expanded_caller
{};
}
namespace NPL
{
enum class ReductionStatus
{
Clean
};
struct TermNode
{};
struct ContextNode
{};
struct Environment
{};
namespace A1
{
template<typename T>
void
bar()
{
static struct Init
{
Init()
{
// std::cout << typeid(T).name() << std::endl;
v.push_back(typeid(T));
}
} init;
}
template<typename C>
void
foo(C&&)
{
bar<ystdex::expanded_caller<ReductionStatus(ContextNode&), C>>();
}
template<typename C>
void
foo2(C&&)
{
bar<C>();
}
namespace
{
struct EvalSequence
{};
}
namespace
{
template<bool = false>
struct DoDefineOrSet
{
template<typename... A>
static ReductionStatus
Call(TermNode& term, ContextNode& ctx, std::shared_ptr<Environment> p,
TermNode& t, A&&... args)
{
foo2(std::bind([&](const TermNode& saved,
const std::shared_ptr<Environment>& p_e, const A&...){
return ReductionStatus::Clean;
}, std::move(t), std::move(p), std::move(args)...));
return ReductionStatus::Clean;
}
};
template<unsigned long long, unsigned long long>
ReductionStatus
LambdaVauWithEnvironment(TermNode&, ContextNode&, bool)
{
[]{};
foo([]{});
return ReductionStatus::Clean;
}
}
}
ReductionStatus
f1(TermNode&, ContextNode&)
{
return ReductionStatus::Clean;
}
}
int main()
{
using namespace std;
using namespace placeholders;
using namespace NPL;
using namespace A1;
TermNode t;
ContextNode c;
cout << "__GXX_TYPEINFO_EQUALITY_INLINE = " <<
__GXX_TYPEINFO_EQUALITY_INLINE << endl;
cout << "__GXX_MERGED_TYPEINFO_NAMES = " << __GXX_MERGED_TYPEINFO_NAMES
<< endl;
foo2(bind(f1, ref(t), _1));
foo2(EvalSequence{});
DoDefineOrSet<false>::Call(t, c, {}, t);
LambdaVauWithEnvironment<1, 1>(t, c, true);
for(auto& id : v)
cout << "i = " << (&id - &v[0]) << ", v[i] = " << id.name() <<
endl;
for(std::size_t i = 0; i < v.size(); ++i)
for(auto j = i; j < v.size(); ++j)
if(i != j)
cout << "i = " << i << ", " << "j = " << j <<
", v[i] < v[j] = " << (v[i] < v[j]) << ", v[j] < v[i] = " << (v[j] < v[i]) <<
endl;
}
// g++ -std=c++11 -U__GXX_TYPEINFO_EQUALITY_INLINE
-D__GXX_TYPEINFO_EQUALITY_INLINE=0 -U__GXX_MERGED_TYPEINFO_NAMES
-D__GXX_MERGED_TYPEINFO_NAMES=0 a.cc
This is tested with x86_64-w64-mingw32-g++. Linking may fail on platforms where
libstdc++ is configured without the out-of-line definition of
std::type_info::before. Here is the output:
__GXX_TYPEINFO_EQUALITY_INLINE = 0
__GXX_MERGED_TYPEINFO_NAMES = 0
i = 0, v[i] =
St5_BindIFPFN3NPL15ReductionStatusERNS0_8TermNodeERNS0_11ContextNodeEESt17reference_wrapperIS2_ESt12_PlaceholderILi1EEEE
i = 1, v[i] = N3NPL2A112_GLOBAL__N_112EvalSequenceE
i = 2, v[i] =
St5_BindIFZN3NPL2A112_GLOBAL__N_113DoDefineOrSetILb0EE4CallIJEEENS0_15ReductionStatusERNS0_8TermNodeERNS0_11ContextNodeESt10shared_ptrINS0_11EnvironmentEES8_DpOT_EUlRKS7_RKSD_E_S7_SD_EE
i = 3, v[i] =
N6ystdex15expanded_callerIFN3NPL15ReductionStatusERNS1_11ContextNodeEEZNS1_2A112_GLOBAL__N_124LambdaVauWithEnvironmentILy1ELy1EEES2_RNS1_8TermNodeES4_bEUlvE0_EE
i = 0, j = 1, v[i] < v[j] = 0, v[j] < v[i] = 1
i = 0, j = 2, v[i] < v[j] = 1, v[j] < v[i] = 1
i = 0, j = 3, v[i] < v[j] = 0, v[j] < v[i] = 1
i = 1, j = 2, v[i] < v[j] = 0, v[j] < v[i] = 1
i = 1, j = 3, v[i] < v[j] = 0, v[j] < v[i] = 1
i = 2, j = 3, v[i] < v[j] = 0, v[j] < v[i] = 1
The unordered pair occurs iff. __GXX_TYPEINFO_EQUALITY_INLINE == 0, i.e. the
out-of-line definition is used, and regardless to the value of
__GXX_MERGED_TYPEINFO_NAMES (either 0 or 1).
The sequence (v[0], v[1], ...) here is exactly the inserted one in the actual
case, where the underlying sequence (of type vector<type_index>) using
less<type_index> as key_compare. Insertions of v[0] and v[1] are OK, and then
insertion of v[2] breaks the assumption of ordering in the vector. At this
point it is already corrupted. Assuming it is correct when
__GXX_TYPEINFO_EQUALITY_INLINE == 1, !(v[0] < v[2]) should hold, so the
resulted ordered vector is (v[2], v[1], v[0]) rather than the buggy (v[1],
v[2], v[0]). In this case, given that all elements are different, the further
insertions would not fail, as the container just contains all elements with an
arbitrary order. The bug would not show until some operations like find or
lower_bound. However, for some reasons (address space layout?), in the actual
case, the order is reversed. Then there occurs the pair where (!(v[0] < v[2])
&& !(v[2] < v[0])), which is treated as equivalent keys as per the assumption
of the ordered container. Thus, the insertion fail immediately.
>
> Is this using the inline implementation? (I assume so, otherwise redefining
> __GXX_MERGED_TYPEINFO_NAMES won't do anything). How does forcing address
> comparisons for all types solve anything? That isn't just "not enough in
> general" it's **wrong** in general.
As above, I've later tested all 4 combinations for sure. Accidentally the
inline definition of std::type_info::before does the right thing (hopefully),
so __GXX_TYPEINFO_EQUALITY_INLINE == 1 just works. Otherwise there would be no
easy workaround without the modification on the standard headers.
Forcing address comparisons is wrong in general, but with some additional
assumptions to rule out all potential offending features, then all type_info
objects follow ODR in the strict sense, so this just works. When this is an
issue, __GXX_TYPEINFO_EQUALITY_INLINE == 1 && __GXX_MERGED_TYPEINFO_NAMES == 0
should be safe for all names not from unnamed namespaces. This is a real
problem for MinGW (at least with GNU ld which does not perform ICF on PE/COFF
AFAIK), where __GXX_TYPEINFO_EQUALITY_INLINE == 1 &&
__GXX_MERGED_TYPEINFO_NAMES == 1 causes something like &typeid(shared_ptr<...>)
not unique across module boundaries, and my code fails elsewhere due to this
reason.
>
> I don't think that's correct. We can only do a pointer comparison if both
> strings begin with '*'. If we compared pointers for "*foo" and "bar" (where
> "bar" is not unique), we might have "*foo" < "bar" in one TU and "*foo" >
> "bar" in another TU where "bar" has a different address. We need to do a
> string comparison if either of them is not unique. Which is what the inline
> implementation does.
>
> It also correctly handles the problem case described by Richard Smith,
> because all unique names start with '*' and all non-unique names start with
> one of [A-Za-z_], and those are ordered after '*', at least for ASCII and
> UTF-8.
>
OK, it is just a bit difficult to reason about. The rule of '*' seems not in
the Itanium ABI spec. Is there any normative documentation out of the GCC repo?
(BTW, IIRC Clang++ just does not yet implement things about '*'.)
> I agree there are issues with the non-inline implementation. We could just
> make it match the inline one:
>
> --- a/libstdc++-v3/libsupc++/tinfo2.cc
> +++ b/libstdc++-v3/libsupc++/tinfo2.cc
> @@ -33,15 +33,11 @@ using std::type_info;
> bool
> type_info::before (const type_info &arg) const _GLIBCXX_NOEXCEPT
> {
> -#if __GXX_MERGED_TYPEINFO_NAMES
> - return name () < arg.name ();
> -#else
> - /* The name() method will strip any leading '*' prefix. Therefore
> - take care to look at __name rather than name() when looking for
> - the "pointer" prefix. */
> - return (__name[0] == '*') ? name () < arg.name ()
> - : __builtin_strcmp (name (), arg.name ()) < 0;
> +#if !__GXX_MERGED_TYPEINFO_NAMES
> + if (__name[0] == '*' || arg.__name[0] == '*')
> + return __builtin_strcmp (__name, arg.__name) < 0;
> #endif
> + return __name < arg.__name
> }
>
> #endif
LGTM.
