Page MenuHome

Crash in new outliner show parenting hierarchy
Closed, ResolvedPublic

Description

System Information
Operating system: Linux-4.13.10-041310-generic-x86_64-with-debian-stretch-sid 64 Bits
Graphics card: GeForce GTX 1050/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 390.67

Blender Version
Broken: version: 2.80 (sub 59), branch: master, commit date: 2019-04-24 17:11, hash: rBa14735d11d2e
Worked: rBf2dc78f13fb7

Short description of error
The latest build crashes immediately, when loading the attached file. It works fine with yesterdays build.

Exact steps for others to reproduce the error

  • load the file

Event Timeline

Brecht Van Lommel (brecht) triaged this task as Confirmed, High priority.

Infinite recursion in outliner_make_object_parent_hierarchy_recursive.

I got the same error exactly once while testing, but was unable to recreate it. At the time I was playing with objects that had three levels of parenting (parent, son, grandson) and was moving them in various ways between two collections. But again, it only happened the once and I then spent about an hour trying to retrace my steps to make it happen again without success.

Brecht Van Lommel (brecht) renamed this task from attached file crashes immediately after loading to Crash in new outliner show parenting hierarchy.Apr 25 2019, 12:26 AM
Brecht Van Lommel (brecht) reopened this task as Open.

I've disabled the new feature temporarily since a simple fix wasn't obvious and it seems likely this happens in a lot of files.

The problem is that it's iterating over te_parent->subtree, while at the same time removing elements from it as tree_to_remove_objects_from.

Further there is a linear lookup to find tree elements corresponding to a child object, which causes O(n^2) time complexity overall and so poor scaling for many objects in a collection.

The more efficient solution that also fixes the crash could be:

  • Build a map from Object* to a list of TreeElement* matching the object.
  • For all objects in the tree lookup the parent in this map, and move or add tree elements as needed.

I managed to reproduce the issue in a simple file as well:

From factory startup:

  • Delete Collection (Delete hierarchy)
  • Add an object (e.g., Cube)
  • Add another object (e.g., Empty).
  • Parent the Cube to the Empty

Thanks for reverting the commit Brecht.