Add a regression test for a cyclic component reference

Stores a painted cube, points its component back at the object that holds it and
expects the load to fail. Without the bound the test does not finish: the work
list grows until the process is killed.

src/libslic3r/Config.cpp

@@ -304,7 +304,8 @@ ConfigOption* ConfigOptionDef::create_default_option() const
             return new ConfigOptionEnumGeneric(this->enum_keys_map, this->default_value->getInt());
 
         if (type == coEnums) {
-            if (this->default_value->nullable()) {
+            auto dft = this->default_value->clone();
+            if (dft->nullable()) {
                 ConfigOptionEnumsGenericNullable *opt = dynamic_cast<ConfigOptionEnumsGenericNullable *>(this->default_value->clone());
                 opt->keys_map = this->enum_keys_map;
                 return opt;
@@ -313,6 +314,7 @@ ConfigOption* ConfigOptionDef::create_default_option() const
                 opt->keys_map = this->enum_keys_map;
                 return opt;
             }
+            delete dft;
         }
 
         return this->default_value->clone();

src/libslic3r/Format/bbs_3mf.cpp

@@ -1340,7 +1340,7 @@ void PlateData::parse_filament_info(GCodeProcessorResult *result)
 
         bool _handle_start_relationship(const char** attributes, unsigned int num_attributes);
 
-        void _generate_current_object_list(std::vector<Component> &sub_objects, Id object_id, IdToCurrentObjectMap& current_objects);
+        bool _generate_current_object_list(std::vector<Component> &sub_objects, Id object_id, IdToCurrentObjectMap& current_objects);
         bool _generate_volumes_new(ModelObject& object, const std::vector<Component> &sub_objects, const ObjectMetadata::VolumeMetadataList& volumes, ConfigSubstitutionContext& config_substitutions);
         //bool _generate_volumes(ModelObject& object, const Geometry& geometry, const ObjectMetadata::VolumeMetadataList& volumes, ConfigSubstitutionContext& config_substitutions);
 
@@ -2055,7 +2055,8 @@ void PlateData::parse_filament_info(GCodeProcessorResult *result)
                         return false;
                     }
                     std::vector<Component> object_id_list;
-                    _generate_current_object_list(object_id_list, object.first, m_current_objects);
+                    if (!_generate_current_object_list(object_id_list, object.first, m_current_objects))
+                        return false;
 
                     ObjectMetadata::VolumeMetadataList volumes;
                     ObjectMetadata::VolumeMetadataList* volumes_ptr = nullptr;
@@ -2154,7 +2155,8 @@ void PlateData::parse_filament_info(GCodeProcessorResult *result)
             }*/
 
             std::vector<Component> object_id_list;
-            _generate_current_object_list(object_id_list, object.first, m_current_objects);
+            if (!_generate_current_object_list(object_id_list, object.first, m_current_objects))
+                return false;
 
             ObjectMetadata::VolumeMetadataList volumes;
             ObjectMetadata::VolumeMetadataList* volumes_ptr = nullptr;
@@ -5002,31 +5004,45 @@ void PlateData::parse_filament_info(GCodeProcessorResult *result)
         return true;
     }
 
-    void _BBS_3MF_Importer::_generate_current_object_list(std::vector<Component> &sub_objects, Id object_id, IdToCurrentObjectMap &current_objects)
+    bool _BBS_3MF_Importer::_generate_current_object_list(std::vector<Component> &sub_objects, Id object_id, IdToCurrentObjectMap &current_objects)
     {
-        std::list<std::pair<Component, Transform3d>> id_list;
+        // A chain of component references longer than the number of objects has to visit an object
-        id_list.push_back(std::make_pair(Component(object_id, Transform3d::Identity()), Transform3d::Identity()));
+        // twice, so the component graph contains a cycle and the expansion below would not stop.
+        const size_t max_depth = current_objects.size();
+        // An acyclic graph may still expand exponentially, so bound the number of expanded components
+        // as well. Way above the number of parts of any real object.
+        static constexpr size_t max_components = 100000;
 
+        std::list<std::tuple<Component, Transform3d, size_t>> id_list;
+        id_list.push_back(std::make_tuple(Component(object_id, Transform3d::Identity()), Transform3d::Identity(), 0));
+
+        size_t num_components = 0;
         while (!id_list.empty())
         {
             auto current_item = id_list.front();
-            Component current_id = current_item.first;
+            Component current_id = std::get<0>(current_item);
             id_list.pop_front();
+            if (std::get<2>(current_item) > max_depth || ++ num_components > max_components) {
+                add_error("invalid 3mf: cyclic or too deeply nested components");
+                sub_objects.clear();
+                return false;
+            }
             IdToCurrentObjectMap::iterator current_object = current_objects.find(current_id.object_id);
             if (current_object != current_objects.end()) {
                 //found one
                 if (!current_object->second.components.empty()) {
                     for (const Component &comp : current_object->second.components) {
-                        id_list.push_back(std::pair(comp, current_item.second * comp.transform));
+                        id_list.push_back(std::make_tuple(comp, std::get<1>(current_item) * comp.transform, std::get<2>(current_item) + 1));
                     }
                 }
                 else if (!(current_object->second.geometry.empty())) {
                     //CurrentObject* ptr = &(current_objects[current_id]);
                     //CurrentObject* ptr2 = &(current_object->second);
-                    sub_objects.push_back({ current_object->first, current_item.second});
+                    sub_objects.push_back({ current_object->first, std::get<1>(current_item)});
                 }
             }
         }
+        return true;
     }
 
     bool _BBS_3MF_Importer::_generate_volumes_new(ModelObject& object, const std::vector<Component> &sub_objects, const ObjectMetadata::VolumeMetadataList& volumes, ConfigSubstitutionContext& config_substitutions)

src/libslic3r/Model.cpp

@@ -2087,6 +2087,11 @@ void ModelVolume::reset_extra_facets()
     this->seam_facets.reset();
     this->mmu_segmentation_facets.reset();
     this->fuzzy_skin_facets.reset();
+    // Texture-displacement paint data has no remap-across-topology-change support yet (see
+    // build_texture_displacement()'s documented limitation), so it must be dropped here rather
+    // than left referring to a mesh that no longer matches it.
+    for (int i = 0; i < int(TEXTURE_DISPLACEMENT_MAX_LAYERS); ++i)
+        this->texture_displacement_facet(i).reset();
 }
 
 std::optional<TriangleSelector::SavedPainting> ModelVolume::save_painting() const
@@ -2648,14 +2653,9 @@ std::vector<int> ModelVolume::get_extruders() const
         return std::vector<int>();
 
     if (mmu_segmentation_facets.timestamp() != mmuseg_ts) {
+        std::vector<indexed_triangle_set> its_per_type;
         mmuseg_extruders.clear();
         mmuseg_ts = mmu_segmentation_facets.timestamp();
-        // ORCA: without painting data every facet keeps its default (NONE) state, so no extruder
-        // other than the volume's own one can be painted on it. Skip get_facets() then: it builds a
-        // TriangleSelector with one node per facet over the whole mesh (tens of MiB on a dense one)
-        // only to hand back empty sets for every extruder.
-        if (! mmu_segmentation_facets.empty()) {
-            std::vector<indexed_triangle_set> its_per_type;
         mmu_segmentation_facets.get_facets(*this, its_per_type);
         for (int idx = 1; idx < its_per_type.size(); idx++) {
             indexed_triangle_set& its = its_per_type[idx];
@@ -2665,7 +2665,6 @@ std::vector<int> ModelVolume::get_extruders() const
             mmuseg_extruders.push_back(idx);
         }
     }
-    }
 
     std::vector<int> volume_extruders = mmuseg_extruders;
 
@@ -2995,6 +2994,11 @@ void ModelVolume::assign_new_unique_ids_recursive()
     seam_facets.set_new_unique_id();
     mmu_segmentation_facets.set_new_unique_id();
     fuzzy_skin_facets.set_new_unique_id();
+    // As set_new_unique_id() already does: the undo/redo stack stores FacetsAnnotation contents keyed
+    // by ObjectID, so a clone left sharing these ids with its source can be handed the source's mask
+    // on an undo - after which a paint mask and the mesh it was recorded against no longer match.
+    for (int i = 0; i < int(TEXTURE_DISPLACEMENT_MAX_LAYERS); ++i)
+        texture_displacement_facet(i).set_new_unique_id();
 }
 
 void ModelVolume::rotate(double angle, Axis axis)
@@ -3632,11 +3636,6 @@ ModelInstanceEPrintVolumeState ModelInstance::calc_print_volume_state(const Buil
 
 indexed_triangle_set FacetsAnnotation::get_facets(const ModelVolume& mv, EnforcerBlockerType type) const
 {
-    // ORCA: nothing is painted, so only the NONE state can have facets. Answering for any other
-    // state needs no TriangleSelector (one node per facet of the whole mesh) at all.
-    if (this->empty() && type != EnforcerBlockerType::NONE)
-        return {};
-
     TriangleSelector selector(mv.mesh());
     // Reset of TriangleSelector is done inside TriangleSelector's constructor, so we don't need it to perform it again in deserialize().
     selector.deserialize(m_data, false);

tests/libslic3r/test_3mf.cpp

@@ -27,6 +27,7 @@
 #include <Eigen/Geometry>
 #include <type_traits> // for std::enable_if_t
 #include <typeinfo>    // for typeid
+#include <regex>
 
 namespace Catch {
     template <typename T>
@@ -321,6 +322,30 @@ TEST_CASE("A project with a plate id below 1 fails to load", "[3mf][Regression]"
     REQUIRE_FALSE(loaded);
 }
 
+TEST_CASE("A project whose components reference themselves fails to load", "[3mf][Regression]")
+{
+    ScopedTemporaryFile temp(".3mf");
+    store_painted_cube(temp.string());
+
+    // Point the component back at the object that holds it. Expanding that reference used to push
+    // into the work list forever, growing it until the process ran out of memory.
+    REQUIRE(rewrite_3mf_entries(temp.string(), [](std::string& name, std::string& data) {
+        if (!boost::algorithm::ends_with(name, "3dmodel.model"))
+            return false;
+        std::smatch match;
+        if (!std::regex_search(data, match, std::regex("<object id=\"([0-9]+)\"[^>]*>\\s*<components")))
+            return false;
+        data = std::regex_replace(data, std::regex("objectid=\"[0-9]+\""), "objectid=\"" + match[1].str() + "\"");
+        return true;
+    }));
+
+    ScopedTemporaryDir backup_dir("orca_cycle_dst");
+    Model              model;
+    bool               loaded = true;
+    REQUIRE_NOTHROW(loaded = load_project(temp.string(), model, backup_dir));
+    REQUIRE_FALSE(loaded);
+}
+
 TEST_CASE("A project with malformed paint data loads without the damaged facet", "[3mf][Regression]")
 {
     ScopedTemporaryFile temp(".3mf");