Rust-bindgen: Infinite recursion in bindgen::ir::ty::Type::safe_canonical_type

[jonhoo]

Input C++ Header and Bindgen Invocation

It's... complicated. If you have Bazel installed, then check out the rust branch of https://github.com/jonhoo/ray/. The header file being compiled is rust/sys/wrapper.h, though it has transitive includes that go deep into the dependency graph of ray. The best way I know of to get those dependencies is by running

bazel build -s //rust:ray_sys_bindgen

Killing that once it says

[X / Y] Executing genrule //rust:ray_sys_bindgen

Then look for

(cd <long-path-prefix>/execroot/com_github_ray_project_ray && \

Change into that directory manually, and then run:

$ bindgen rust/sys/wrapper.h -o bazel-out/k8-opt/bin/rust/sys/src/lib.rs --enable-cxx-namespaces -- --std=c++17 -x c++ -Isrc/ -Iexternal/plasma/cpp/src/ -Iexternal/boost/ -Iexternal/com_github_grpc_grpc/include/ -Iexternal/com_github_google_flatbuffers/include/ -Iexternal/com_google_absl/ -Iexternal/boringssl/src/third_party/googletest/include/ -Iexternal/com_google_protobuf/src/ -Ibazel-out/k8-opt/bin/src/ -Ibazel-o
ut/k8-opt/bin/ -Isrc/ray/thirdparty/ae/

Actual Results

Bindgen takes _forever_ to run. With --time-passes, I see:

  time:   908.100 ms.   parse
  time:   210.326 ms.   resolve_typerefs
  time:     1.565 ms.   compute_bitfield_units
  time:     0.000 ms.   process_replacements
  time:     5.361 ms.   deanonymize_fields
  time:   478.479 ms.   compute_whitelisted_and_codegen_items
  time:    84.449 ms.   compute_has_vtable
  time:   262.273 ms.   compute_sizedness
  time:    88.773 ms.   compute_has_destructor
  time:   353.122 ms.   find_used_template_parameters

The process is at 100% CPU load on a single core, but produces no further output for a long time. At the time of writing, I have waited for 10 minutes with no progress. Profiling shows basically all time spent in bindgen::ir::ty::Type::canonical_type, called from this stack:

#3  bindgen::ir::ty::Type::safe_canonical_type (self=<optimized out>, ctx=0x7ffc16e7c640) at src/ir/ty.rs:366
#4  bindgen::ir::ty::Type::canonical_type (self=<optimized out>, ctx=0x7ffc16e7c640) at src/ir/ty.rs:330
#5  0x000055f97f48d07a in bindgen::ir::analysis::derive::CannotDerive::constrain_type (self=0x7ffc16e7c250, item=0x7f544f9298f8, ty=<optimized out>) at src/ir/analysis/derive.rs:211
#6  <bindgen::ir::analysis::derive::CannotDerive as bindgen::ir::analysis::MonotoneFramework>::constrain (self=0x7ffc16e7c250, id=...) at src/ir/analysis/derive.rs:660
#7  0x000055f97f483df6 in bindgen::ir::analysis::analyze (extra=...) at src/ir/analysis/mod.rs:166
#8  0x000055f97f427c97 in bindgen::ir::context::BindgenContext::compute_cannot_derive_debug (self=0x7ffc16e7c640) at src/ir/context.rs:2438
#9  0x000055f97f3fee6e in bindgen::ir::context::BindgenContext::gen (self=..., cb=...) at src/ir/context.rs:1198
#10 0x000055f97f3d68ff in bindgen::codegen::codegen (context=...) at src/codegen/mod.rs:3744
#11 bindgen::Bindings::generate (options=...) at src/lib.rs:2052
#12 bindgen::Builder::generate (self=...) at src/lib.rs:1375
#13 0x000055f97f35c4ec in bindgen::main::{{closure}} () at src/main.rs:53
#14 std::panicking::try::do_call (data=0x7ffc16e811b0 "\b\000") at /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libstd/panicking.rs:292
#15 0x000055f97f58596a in __rust_maybe_catch_panic () at src/libpanic_unwind/lib.rs:80
#16 0x000055f97f356991 in std::panicking::try (f=...) at /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libstd/panicking.rs:271
#17 std::panic::catch_unwind (f=...) at /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libstd/panic.rs:394
#18 bindgen::main () at src/main.rs:52

Expected Results

This should complete faster?

[jonhoo]

It's now been running for 25 minutes. I'll leave it running until it finishes to see if that gives me anything more.

[jonhoo]

It is still running, 8h35m later. Something is definitely very wrong.

[jonhoo]

Doing some gdb debugging, it looks like there's infinite recursion going on here:
https://github.com/rust-lang/rust-bindgen/blob/5f4dc4f458f0fd14beafbacb8bb20a5a4d139cd5/src/ir/ty.rs#L366

Specifically, here is the cycle step-by-step:

bindgen::ir::ty::Type::safe_canonical_type (self=0x7f544f9262a8, ctx=0x7ffc16e7c640) at src/ir/ty.rs:344
344                 TypeKind::TypeParam |
(gdb) step
bindgen::ir::ty::Type::safe_canonical_type (self=0x7f544f9262a8, ctx=0x7ffc16e7c640) at src/ir/ty.rs:366
366                     ctx.resolve_type(inner).safe_canonical_type(ctx)
(gdb) step
bindgen::ir::context::BindgenContext::resolve_type (self=0x7ffc16e7c640, type_id=...) at src/ir/ty.rs:366
366                     ctx.resolve_type(inner).safe_canonical_type(ctx)
(gdb) step
bindgen::ir::context::BindgenContext::resolve_item (self=0x7ffc16e7c640, item_id=...) at src/ir/context.rs:1488
1488            let item_id = item_id.into();
(gdb) step
1489            match self.resolve_item_fallible(item_id) {
(gdb) step
bindgen::ir::context::BindgenContext::resolve_item_fallible (self=0x7ffc16e7c640, id=...) at src/ir/context.rs:1489
1489            match self.resolve_item_fallible(item_id) {
(gdb) step
core::slice::<impl [T]>::get (self=..., index=311083) at src/ir/context.rs:1489
1489            match self.resolve_item_fallible(item_id) {
(gdb) step
<usize as core::slice::SliceIndex<[T]>>::get (self=311083, slice=...) at /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libcore/slice/mod.rs:2684
2684    /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libcore/slice/mod.rs: No such file or directory.
(gdb) step
bindgen::ir::context::BindgenContext::resolve_item_fallible (self=0x7ffc16e7c640, id=...) at src/ir/context.rs:1481
1481            self.items.get(id.into().0)?.as_ref()
(gdb) step
core::option::Option<T>::as_ref (self=<optimized out>) at /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libcore/option.rs:266
266     /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libcore/option.rs: No such file or directory.
(gdb) step
bindgen::ir::context::BindgenContext::resolve_type (self=0x7ffc16e7c640, type_id=...) at src/ir/context.rs:1455
1455            self.resolve_item(type_id).kind().expect_type()
(gdb) step
bindgen::ir::item_kind::ItemKind::expect_type (self=<optimized out>) at src/ir/context.rs:1455
1455            self.resolve_item(type_id).kind().expect_type()
(gdb) step
bindgen::ir::item_kind::ItemKind::as_type (self=<optimized out>) at src/ir/item_kind.rs:83
83                  ItemKind::Type(ref ty) => Some(ty),
(gdb) step
bindgen::ir::item_kind::ItemKind::expect_type (self=<optimized out>) at src/ir/item_kind.rs:105
105             self.as_type().expect("Not a type")
(gdb) step
core::option::Option<T>::expect (msg=..., self=...) at /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libcore/option.rs:344
344     /rustc/5242afe811c2648baf158eee28143c9facc350ee/src/libcore/option.rs: No such file or directory.
(gdb) step
bindgen::ir::item_kind::ItemKind::expect_type (self=<optimized out>) at src/ir/item_kind.rs:105
105             self.as_type().expect("Not a type")
(gdb) step
bindgen::ir::item_kind::ItemKind::as_type (self=<optimized out>) at src/ir/item_kind.rs:83
83                  ItemKind::Type(ref ty) => Some(ty),
(gdb) step
bindgen::ir::ty::Type::safe_canonical_type (self=0x7f544f9262a8, ctx=0x7ffc16e7c640) at src/ir/ty.rs:344
344                 TypeKind::TypeParam |

[jonhoo]

More specifically, the source of the recursion is that in
https://github.com/rust-lang/rust-bindgen/blob/5f4dc4f458f0fd14beafbacb8bb20a5a4d139cd5/src/ir/ty.rs#L366

ctx.resolve_type(inner) == self

[jonhoo]

Slightly smaller reproducing example: clone protobuf and run:

$ bindgen src/google/protobuf/map_type_handler.h -- --std=c++17 -x c++ -I./src/

Still working on minimizing further. The recursion seems to happen due to the type TypeOnMemory.

[jonhoo]

All right, here's an even smaller reproduction:

#include <algorithm>

$ bindgen input.h  -- --std=c++17 -x c++

(note that it does not happen with c++14)

[jonhoo]

And so, we arrive at:

template <typename _Key, bool _Unique_keys = _Key::foo>
struct _Map_base {};

template <typename _Key>
struct _Map_base<_Key, true> {
public:
  using key_type = _Key;
  void at(const key_type &__k);
};

template <typename _Key>
void _Map_base<_Key, true>::at(const key_type &__k) {}

Which makes bindgen spin forever with

$ bindgen input.h  -- --std=c++11 -x c++

(and indeed any C++ --std)

[jonhoo]

@emilio Sorry for all the noise! Hopefully that last reproducing example might help you get somewhere. I'm not familiar enough with the codebase to even make a guess as to where this goes wrong.

[emilio]

Ah, interesting, no problem! That reduced test-case is really useful.

So this is a cycle in bindgen's type graph, looks like. We should get this fixed.

[jonhoo]

If you fix the above, I would also try the more macro version I give in https://github.com/rust-lang/rust-bindgen/issues/1679#issuecomment-554158106, since I have a sneaking suspicion that there are in fact _two_ distinct infinite recursion things going on here. The minimal reproduction may only hit one of them.

[jonhoo]

@emilio I don't know how much I can be of help here given my limited knowledge of C++ template programming, but is there anything I can do to help make the fixing process easier?

[emilio]

@emilio I don't know how much I can be of help here given my limited knowledge of C++ template programming, but is there anything I can do to help make the fixing process easier?

Well, I probably just need some time debugging this on gdb / rr. Unfortunately finding time for bindgen is not the easiest thing at the moment :)

[emilio]

Took a quick look and the issue is that we end up with a type alias pointing to itself (for key_type)... Not 100% sure what's the fix yet though.

[jonhoo]

Maybe it'd be worthwhile to bring this up in the Call for Participation part of This Week in Rust?

[emilio]

Sure, that'd be great! I landed an assertion that makes much easier to spot the bug in 0c36e388dbf8ac0830c24f70c06c6a18f5cd7537.

Partial template specialization is quite a mess, and clang sometimes has very weird stuff in the AST, so I wouldn't recommend debugging this to someone not familiar with C++. But I'm happy to help either way.