ext/alloc_traits.h suggested when indexing std::vector<std::string>

[GoogleCodeExporter]

(extracted from issue #163)

--
../hc/hc.cpp:1154:24: warning: 
__gnu_cxx::__alloc_traits<std::allocator<std::basic_string<char> > 
>::value_type is defined in <ext/alloc_traits.h>, which isn't directly 
#included.
../hc/hc.cpp:1215:31: warning: 
__gnu_cxx::__alloc_traits<std::allocator<std::basic_string<char> > 
>::value_type is defined in <ext/alloc_traits.h>, which isn't directly 
#included.
../hc/hc.cpp:1219:38: warning: 
__gnu_cxx::__alloc_traits<std::allocator<std::basic_string<char> > 
>::value_type is defined in <ext/alloc_traits.h>, which isn't directly 
#included.

../hc/hc.cpp should add these lines:
#include <ext/alloc_traits.h>           // for __alloc_traits<>::value_type
--

IWYU should not suggest including ext/alloc_traits, which is a private header.

> ../hc/hc.cpp:1154:24: ...
> ../hc/hc.cpp:1215:31: ...
> ../hc/hc.cpp:1219:38: ...

All these three point to indexing into a vector of strings;

  std::vector<std::string> title;
  ...

  title[count][len] = '\0'; // <- alloc_traits is required here.

(see 
https://github.com/LegalizeAdulthood/iterated-dynamics/blob/master/hc/hc.cpp#L11
54, line numbers are off by one, so I'm probably linking to the wrong revision, 
but this is good enough)

IWYU log attached.

Original issue reported on code.google.com by kim.gras...@gmail.com on 3 Jan 2015 at 12:17

Attachments:

• verbose-7.txt.gz

[GoogleCodeExporter]

Kim, you are right. All the lines in question are indexing into a vector of 
strings and doing something with returned value. Link to the right revision is 
https://github.com/LegalizeAdulthood/iterated-dynamics/blob/97459e23a88337fd66eb
9f0e3739d85102241c55/hc/hc.cpp#L1154

I think that __alloc_traits appears because std::vector::operator[] has return 
type `reference` [1]
    reference operator[](size_type __n)

where `reference` is
    typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>  _Alloc_traits;
    ...
    typedef typename _Alloc_traits::reference          reference;

operator[] returns __alloc_traits<>::value_type and it is full used because on 
returned value we call another operator[], length(), c_str().

These are all my findings so far. I don't know how we encountered 
__alloc_traits<>::value_type instead of std::string or std::basic_string<char>. 
And I was unable to reproduce this issue with libstdc++ 4.8, though it looks a 
lot like 4.7 in "bits/stl_vector.h". Useful link for others and for myself in 
the future - The GNU C++ Library API Reference [2].

[1] https://gcc.gnu.org/onlinedocs/gcc-4.7.4/libstdc++/api/a01379_source.html
[2] https://gcc.gnu.org/onlinedocs/libstdc++/api.html

Original comment by vsap...@gmail.com on 19 Jan 2015 at 12:58

[GoogleCodeExporter]

Interesting. This is vaguely related to issue #169 where a traits typedef is 
also considered the "primary" symbol, instead of the template argument type.

I don't know if they have the same root cause, but it might be related.

Original comment by kim.gras...@gmail.com on 19 Jan 2015 at 7:36

[GoogleCodeExporter]

I was kinda able to reproduce the bug with libc++. I'm not sure if it is the 
same bug, but for the code like `lines[0].length();` IWYU recommends to keep 
#include <vector> for vector, std::__vector_base<>::value_type. Comparing 
libstdc++ 4.2.1 and libc++ has revealed the following:

// libstdc++
(lldb) call type->dump()
SubstTemplateTypeParmType 0x10532f780 'class std::basic_string<char>' sugar
|-TemplateTypeParmType 0x10516cac0 '_Tp' dependent depth 0 index 0
| `-TemplateTypeParm 0x10516ca80 '_Tp'
`-RecordType 0x10505ea00 'class std::basic_string<char>'
  `-ClassTemplateSpecialization 0x10505e8f0 'basic_string'

// libc++
(lldb) call type->dump()
TypedefType 0x104b7f4d0 'value_type' sugar
|-Typedef 0x10408cdc0 'value_type'
`-SubstTemplateTypeParmType 0x10408cd80 'class std::__1::basic_string<char>' 
sugar
  |-TemplateTypeParmType 0x104b0c9b0 '_Tp' dependent depth 0 index 0
  | `-TemplateTypeParm 0x104b0c970 '_Tp'
  `-RecordType 0x105835fb0 'class std::__1::basic_string<char>'
    `-ClassTemplateSpecialization 0x105835ea0 'basic_string'

As far as I understand, Clang unwraps the chain of typedefs for libstdc++ and 
partially unwraps it for libc++. How exactly Clang is doing it and why it stops 
for libc++ is something I need to investigate more. I've tried to follow 
typedefs chain (see attached patch) and it fixes the issue with 
__vector_base::value_type, but breaks IWYU in other places.

Original comment by vsap...@gmail.com on 26 Jan 2015 at 12:44

Attachments:

• go_through_typedefs_experiment.patch

[GoogleCodeExporter]

I think I've found the reason for different libc++ and libstdc++ behavior. In 
Sema::CreateOverloadedArraySubscriptExpr() we have [1]

    QualType ResultTy = FnDecl->getReturnType();
    ...
    ResultTy = ResultTy.getNonLValueExprType(Context);

Resulting ResultTy is dumped in my previous comment. As for 
FnDecl->getReturnType() I have

// libstdc++
(lldb) call FnDecl->getReturnType().getTypePtr()->dump()
TypedefType 0x104886880 'reference' sugar
|-Typedef 0x104883570 'reference'
`-ElaboratedType 0x104883520 'typename _Tp_alloc_type::reference' sugar
  `-TypedefType 0x104883500 'reference' sugar
    |-Typedef 0x1048806c0 'reference'
    `-LValueReferenceType 0x104880680 'class std::basic_string<char> &'
      `-SubstTemplateTypeParmType 0x1041d5780 'class std::basic_string<char>' sugar
        |-TemplateTypeParmType 0x105131ec0 '_Tp' dependent depth 0 index 0
        | `-TemplateTypeParm 0x105131e80 '_Tp'
        `-RecordType 0x10580be00 'class std::basic_string<char>'
          `-ClassTemplateSpecialization 0x10580bcf0 'basic_string'

// libc++
(lldb) call FnDecl->getReturnType().getTypePtr()->dump()
TypedefType 0x1043c7460 'reference' sugar
|-Typedef 0x1043bf280 'reference'
`-ElaboratedType 0x1043bf230 'typename __base::reference' sugar
  `-TypedefType 0x1043bf210 'reference' sugar
    |-Typedef 0x105976730 'reference'
    `-LValueReferenceType 0x1059766f0 'value_type &'
      `-TypedefType 0x1059766d0 'value_type' sugar
        |-Typedef 0x1043ba9c0 'value_type'
        `-SubstTemplateTypeParmType 0x1043ba980 'class std::__1::basic_string<char>' sugar
          |-TemplateTypeParmType 0x105122db0 '_Tp' dependent depth 0 index 0
          | `-TemplateTypeParm 0x105122d70 '_Tp'
          `-RecordType 0x1040617b0 'class std::__1::basic_string<char>'
            `-ClassTemplateSpecialization 0x1040616a0 'basic_string'

As far as I can tell, we end up using type which is written with &. In 
libstdc++ 4.2.1 it is "class std::basic_string<char>" and in libc++ it is 
"value_type". And in fact in libstdc++ 4.2.1 we have
    typedef _Tp&       reference;

and in libc++
    typedef _Tp                                      value_type;
    typedef value_type&                              reference;

Reading libstdc++ 4.8.3 code has revealed it is similar to libc++:
    #if __cplusplus >= 201103L
        typedef typename _Base_type::value_type         value_type;
        typedef value_type&                             reference;
    #else...

and I was able to reproduce the original issue with -std=c++11.

My current plan is to get underlying type for typedefs in templates in case 
typedef depends on template arguments. Not sure if this approach covers all 
cases, we'll see how it plays out.

[1] http://clang.llvm.org/doxygen/SemaOverload_8cpp_source.html#l11466

Original comment by vsap...@gmail.com on 2 Feb 2015 at 1:56

[GoogleCodeExporter]

Great detective work! Suggested solution sounds right.

Original comment by kim.gras...@gmail.com on 3 Feb 2015 at 4:58