Page MenuHomePhabricator

[llvm] Let SmallVector construct from any Iterable
AbandonedPublic

Authored by gchatelet on May 19 2021, 4:53 AM.

Details

Reviewers
courbet
Summary

SmallVector can be constructed from llvm::iterable_range but not from other ranges.
This patch allows to construct SmallVector from any Iterable type.

Diff Detail

Event Timeline

gchatelet created this revision.May 19 2021, 4:53 AM
gchatelet requested review of this revision.May 19 2021, 4:53 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 19 2021, 4:53 AM
gchatelet updated this revision to Diff 346409.May 19 2021, 4:56 AM
  • Remove dependency on iterable_range header
gchatelet updated this revision to Diff 346657.May 20 2021, 1:32 AM
  • Remove dependency on iterable_range header
  • Simplified implementation, added tests
Herald added a project: Restricted Project. · View Herald TranscriptMay 20 2021, 1:32 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript
gchatelet updated this revision to Diff 346669.May 20 2021, 2:34 AM
  • Forward argument
fhahn added a subscriber: fhahn.May 20 2021, 3:35 AM
fhahn added inline comments.
clang/include/clang/Basic/Module.h
98 ↗(On Diff #346669)

how is this related?

llvm/tools/llvm-xray/xray-converter.cpp
161

how is this related?

gchatelet added inline comments.May 20 2021, 4:22 AM
clang/include/clang/Basic/Module.h
98 ↗(On Diff #346669)

how is this related?

I'm glad you ask! I'm still investigating the errors that led to this addition (and the one in llvm/tools/llvm-xray/xray-converter.cpp) but I suspect this is due to the recursive nature of these classes.
Both Module and StackIdData contains self-referencing SmallVector. It is unclear to me why the compiler is trying to instantiate the newly added SmallVector constructor during type declaration.

I'll post the compiler errors below the additions.

98 ↗(On Diff #346669)
FAILED: tools/clang/lib/Lex/CMakeFiles/obj.clangLex.dir/HeaderSearch.cpp.o 
/redacted/build-llvm/download/clang/bin/clang++ --sysroot=/redacted/build-llvm/download/sysroot -DGTEST_HAS_RTTI=0 -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/clang/lib/Lex -I/redacted/git/llvm-project/clang/lib/Lex -I/redacted/git/llvm-project/clang/include -Itools/clang/include -Iinclude -I/redacted/git/llvm-project/llvm/include -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -fno-common -Woverloaded-virtual -Wno-nested-anon-types -O3 -DNDEBUG  -fno-exceptions -fno-rtti -std=c++14 -MD -MT tools/clang/lib/Lex/CMakeFiles/obj.clangLex.dir/HeaderSearch.cpp.o -MF tools/clang/lib/Lex/CMakeFiles/obj.clangLex.dir/HeaderSearch.cpp.o.d -o tools/clang/lib/Lex/CMakeFiles/obj.clangLex.dir/HeaderSearch.cpp.o -c /redacted/git/llvm-project/clang/lib/Lex/HeaderSearch.cpp
In file included from /redacted/git/llvm-project/clang/lib/Lex/HeaderSearch.cpp:13:
In file included from /redacted/git/llvm-project/clang/include/clang/Lex/HeaderSearch.h:16:
In file included from /redacted/git/llvm-project/clang/include/clang/Basic/SourceLocation.h:19:
/redacted/git/llvm-project/llvm/include/llvm/Support/PointerLikeTypeTraits.h:61:28: error: invalid application of 'alignof' to an incomplete type 'clang::Module'
      detail::ConstantLog2<alignof(T)>::value;
                           ^~~~~~~~~~
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:23:33: note: in instantiation of template class 'llvm::PointerLikeTypeTraits<clang::Module *>' requested here
    std::next(std::declval<I>()),
                                ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:36:39: note: while substituting explicitly-specified template arguments into function template 'is_forward_iterator' 
struct is_forward_iterator : decltype(detail::is_forward_iterator<I>(0)) {};
                                      ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:46:42: note: in instantiation of template class 'llvm::is_forward_iterator<const llvm::PointerIntPair<clang::Module *, 1, bool> *>' requested here
                                         llvm::is_forward_iterator<I>{});
                                         ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:51:37: note: while substituting deduced template arguments into function template 'is_range_iterable' [with T = const llvm::SmallVector<llvm::PointerIntPair<clang::Module *, 1, bool>, 2> &, I = (no value)]
struct is_range_iterable : decltype(detail::is_range_iterable<T>(0)) {};
                                    ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/SmallVector.h:1194:30: note: in instantiation of template class 'llvm::is_range_iterable<const llvm::SmallVector<llvm::PointerIntPair<clang::Module *, 1, bool>, 2> &>' requested here
      std::enable_if_t<llvm::is_range_iterable<Iterable>::value, bool> = true)
                             ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/SmallVector.h:1168:22: note: while substituting deduced template arguments into function template 'SmallVector' [with Iterable = const llvm::SmallVector<llvm::PointerIntPair<clang::Module *, 1, bool>, 2> &]
class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
                     ^
/redacted/git/llvm-project/clang/include/clang/Basic/Module.h:96:7: note: while declaring the implicit copy constructor for 'Module'
class Module {
      ^
/redacted/git/llvm-project/clang/include/clang/Basic/Module.h:96:7: note: definition of 'clang::Module' is not complete until the closing '}'
1 error generated.
llvm/tools/llvm-xray/xray-converter.cpp
161
FAILED: tools/llvm-xray/CMakeFiles/llvm-xray.dir/xray-converter.cpp.o 
/redacted/build-llvm/download/clang/bin/clang++ --sysroot=/redacted/build-llvm/download/sysroot -DGTEST_HAS_RTTI=0 -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Itools/llvm-xray -I/redacted/git/llvm-project/llvm/tools/llvm-xray -Iinclude -I/redacted/git/llvm-project/llvm/include -fPIC -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wc++98-compat-extra-semi -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -DNDEBUG  -fno-exceptions -fno-rtti -std=c++14 -MD -MT tools/llvm-xray/CMakeFiles/llvm-xray.dir/xray-converter.cpp.o -MF tools/llvm-xray/CMakeFiles/llvm-xray.dir/xray-converter.cpp.o.d -o tools/llvm-xray/CMakeFiles/llvm-xray.dir/xray-converter.cpp.o -c /redacted/git/llvm-project/llvm/tools/llvm-xray/xray-converter.cpp
In file included from /redacted/git/llvm-project/llvm/tools/llvm-xray/xray-converter.cpp:14:
/redacted/git/llvm-project/llvm/tools/llvm-xray/trie-node.h:41:18: error: field has incomplete type '(anonymous namespace)::StackIdData'
  AssociatedData ExtraData;
                 ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:23:33: note: in instantiation of template class 'TrieNode<(anonymous namespace)::StackIdData>' requested here
    std::next(std::declval<I>()),
                                ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:36:39: note: while substituting explicitly-specified template arguments into function template 'is_forward_iterator' 
struct is_forward_iterator : decltype(detail::is_forward_iterator<I>(0)) {};
                                      ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:46:42: note: in instantiation of template class 'llvm::is_forward_iterator<TrieNode<(anonymous namespace)::StackIdData> *const *>' requested here
                                         llvm::is_forward_iterator<I>{});
                                         ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/IterableTraits.h:51:37: note: while substituting deduced template arguments into function template 'is_range_iterable' [with T = const llvm::SmallVector<TrieNode<(anonymous namespace)::StackIdData> *, 4> &, I = (no value)]
struct is_range_iterable : decltype(detail::is_range_iterable<T>(0)) {};
                                    ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/SmallVector.h:1194:30: note: in instantiation of template class 'llvm::is_range_iterable<const llvm::SmallVector<TrieNode<(anonymous namespace)::StackIdData> *, 4> &>' requested here
      std::enable_if_t<llvm::is_range_iterable<Iterable>::value, bool> = true)
                             ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/SmallVector.h:1168:22: note: while substituting deduced template arguments into function template 'SmallVector' [with Iterable = const llvm::SmallVector<TrieNode<(anonymous namespace)::StackIdData> *, 4> &]
class LLVM_GSL_OWNER SmallVector : public SmallVectorImpl<T>,
                     ^
/redacted/git/llvm-project/llvm/tools/llvm-xray/xray-converter.cpp:160:8: note: while declaring the implicit copy constructor for 'StackIdData'
struct StackIdData {
       ^
/redacted/git/llvm-project/llvm/tools/llvm-xray/xray-converter.cpp:160:8: note: definition of '(anonymous namespace)::StackIdData' is not complete until the closing '}'
/redacted/git/llvm-project/llvm/tools/llvm-xray/xray-converter.cpp:225:15: error: no matching member function for call to 'push_front'
    NodeStore.push_front({FuncId, Parent, {}, {(*id_counter)++, {}}});
    ~~~~~~~~~~^~~~~~~~~~
/redacted/build-llvm/download/sysroot/usr/lib/gcc/x86_64-linux-gnu/7/../../../../include/c++/7/bits/forward_list.h:822:7: note: candidate function not viable: cannot convert initializer list argument to 'const TrieNode<(anonymous namespace)::StackIdData>'
      push_front(const _Tp& __val)
      ^
/redacted/build-llvm/download/sysroot/usr/lib/gcc/x86_64-linux-gnu/7/../../../../include/c++/7/bits/forward_list.h:829:7: note: candidate function not viable: cannot convert initializer list argument to 'TrieNode<(anonymous namespace)::StackIdData>'
      push_front(_Tp&& __val)
      ^
/redacted/git/llvm-project/llvm/tools/llvm-xray/xray-converter.cpp:232:13: error: no matching member function for call to 'push_front'
  NodeStore.push_front({FuncId, Parent, {}, {stack_id, std::move(siblings)}});
  ~~~~~~~~~~^~~~~~~~~~
/redacted/build-llvm/download/sysroot/usr/lib/gcc/x86_64-linux-gnu/7/../../../../include/c++/7/bits/forward_list.h:822:7: note: candidate function not viable: cannot convert initializer list argument to 'const TrieNode<(anonymous namespace)::StackIdData>'
      push_front(const _Tp& __val)
      ^
/redacted/build-llvm/download/sysroot/usr/lib/gcc/x86_64-linux-gnu/7/../../../../include/c++/7/bits/forward_list.h:829:7: note: candidate function not viable: cannot convert initializer list argument to 'TrieNode<(anonymous namespace)::StackIdData>'
      push_front(_Tp&& __val)
      ^
3 errors generated.
Quuxplusone added inline comments.
llvm/include/llvm/ADT/IterableTraits.h
18–32

Instead of all this, I would recommend

template<class It>
using is_input_iterator = std::is_base_of<std::input_iterator_tag, typename std::iterator_traits<It>::iterator_category>;

template<class R>
using iterator_type_of = std::decay_t<decltype(std::begin(std::declval<R>()))>;

template<class R, class IsInputIterable = std::true_type>
struct is_range_iterable : std::false_type {};

template<class R>
struct is_range_iterable<R, typename is_input_iterator<iterator_type_of<R>>::type> : std::true_type {};

(Notice that we're supposed to be checking for input iterability, not forward iterability. But also, the right way to see if something is an input iterator is not to check an ad-hoc bunch of operators like * and !=, but simply to check its STL iterator category.)

However, in real life, I personally would reject this patch, because I think "saving a couple of calls to begin/end at the call site" is not worth the peril of letting people accidentally write e.g.

SmallVector<SomeKindaString> v("hello world");
assert(v.size() == 12);  // elements are "h"s, "e"s, "l"s, etc.
llvm/include/llvm/ADT/SmallVector.h
1190–1191

Watch out: this greedy constructor template will be used for non-const copy construction, e.g.

SmallVector<int> x;
SmallVector<int> y = x;  // calls SmallVector<int>::SmallVector<SmallVector<int>&>(SmallVector<int>&, bool),
// which is a better match than SmallVector<int>::SmallVector(const SmallVector<int>&)
courbet added inline comments.Jun 3 2021, 12:37 AM
clang/include/clang/Basic/Module.h
98 ↗(On Diff #346669)

For reference, the issue is that std::next takes its parameter by value: https://godbolt.org/z/531f3f86s.

(though I'm not sure we want to move forward with this patch given @Quuxplusone's comments)

@Quuxplusone thx a lot for the comment. It is very relevant and I agree that this addition may be dangerous.
The intend was to prevent adding more constructors (and dependencies) to SmallVector in D102679.
I can try to see what it takes to call begin and end explicitly.

@gchatelet: Thanks for the link to D102679 — that seems like very relevant background info I didn't have! Having looked through D102679, though, I don't see how it would benefit from D102760 — in fact, D102679 updates some tests to wisely stop depending on the ability to construct SmallVector from a range (and goes to using begin/end pairs instead — good!).
So I think D102679 is a good idea (modulo the review comments I just left), and I continue to think that this D102760 is a bad idea that should be abandoned.

gchatelet abandoned this revision.Jun 7 2021, 7:46 AM

@gchatelet: Thanks for the link to D102679 — that seems like very relevant background info I didn't have! Having looked through D102679, though, I don't see how it would benefit from D102760 — in fact, D102679 updates some tests to wisely stop depending on the ability to construct SmallVector from a range (and goes to using begin/end pairs instead — good!).

Yes these (recent) changes are based on your comments : )

So I think D102679 is a good idea (modulo the review comments I just left), and I continue to think that this D102760 is a bad idea that should be abandoned.

This is my plan indeed. Thx for your insights. I really appreciate it.
I wanted to see the impact of removing the constructor first, it's very minor so I'll go ahead and abandon this change.