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/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;
-        id_list.push_back(std::make_pair(Component(object_id, Transform3d::Identity()), Transform3d::Identity()));
+        // A chain of component references longer than the number of objects has to visit an object
+        // 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/GCode/GCodeProcessor.cpp

@@ -2582,12 +2582,8 @@ void GCodeProcessorResult::reset() {
     //BBS: add mutex for protection of gcode result
     lock();
 
-    // release rather than clear: these two are sized by the print - one entry per move and one
-    // per g-code line - and a reset is where the memory is expected to go back to the allocator
-    // (see BackgroundSlicingProcess::apply()). The capacity would not be reused anyway: the
-    // result is refilled by move-assigning the processor's own result.
-    moves = std::vector<MoveVertex>();
-    lines_ends = std::vector<size_t>();
+    moves.clear();
+    lines_ends.clear();
     printable_area = Pointfs();
     //BBS: add bed exclude area
     bed_exclude_area = Pointfs();

src/libslic3r/GCode/GCodeProcessor.hpp

@@ -369,56 +369,6 @@ class Print;
             initial_layer_time = other.initial_layer_time;
 #if ENABLE_GCODE_VIEWER_STATISTICS
             time = other.time;
-#endif
-            return *this;
-        }
-        // Orca: the user-declared copy assignment above suppresses the implicit move assignment, so
-        // `*result = std::move(processor.extract_result())` used to deep copy 'moves' (one MoveVertex
-        // per move, gigabytes on a large print) while the source stayed alive. This moves exactly the
-        // same members as the copy above, with the same omissions, so the members the copy leaves
-        // untouched on the target are left untouched here too.
-        GCodeProcessorResult& operator=(GCodeProcessorResult &&other)
-        {
-            filename = std::move(other.filename);
-            id = other.id;
-            moves = std::move(other.moves);
-            lines_ends = std::move(other.lines_ends);
-            printable_area = std::move(other.printable_area);
-            bed_exclude_area = std::move(other.bed_exclude_area);
-            wrapping_exclude_area = std::move(other.wrapping_exclude_area);
-            toolpath_outside = other.toolpath_outside;
-            label_object_enabled = other.label_object_enabled;
-            long_retraction_when_cut = other.long_retraction_when_cut;
-            timelapse_warning_code = other.timelapse_warning_code;
-            printable_height = other.printable_height;
-            settings_ids = std::move(other.settings_ids);
-            filaments_count = other.filaments_count;
-            extruder_colors = std::move(other.extruder_colors);
-            filament_diameters = std::move(other.filament_diameters);
-            filament_densities = std::move(other.filament_densities);
-            filament_costs = std::move(other.filament_costs);
-            print_statistics = std::move(other.print_statistics);
-            custom_gcode_per_print_z = std::move(other.custom_gcode_per_print_z);
-            spiral_vase_mode = other.spiral_vase_mode;
-            warnings = std::move(other.warnings);
-            bed_type = other.bed_type;
-            gcode_check_result = std::move(other.gcode_check_result);
-            limit_filament_maps = std::move(other.limit_filament_maps);
-            filament_printable_reuslt = std::move(other.filament_printable_reuslt);
-            nozzle_group_result = std::move(other.nozzle_group_result);
-            extruder_types = std::move(other.extruder_types);
-            printer_extruder_variant = std::move(other.printer_extruder_variant);
-            printer_extruder_id = std::move(other.printer_extruder_id);
-            layer_filaments = std::move(other.layer_filaments);
-            filament_change_sequence = std::move(other.filament_change_sequence);
-            used_mixed_filaments = std::move(other.used_mixed_filaments);
-            nozzle_change_sequence = std::move(other.nozzle_change_sequence);
-            optimal_assignment = std::move(other.optimal_assignment);
-            filament_change_count_map = std::move(other.filament_change_count_map);
-            skippable_part_time = std::move(other.skippable_part_time);
-            initial_layer_time = other.initial_layer_time;
-#if ENABLE_GCODE_VIEWER_STATISTICS
-            time = other.time;
 #endif
             return *this;
         }

src/libvgcode/src/ViewerImpl.cpp

@@ -883,17 +883,15 @@ void ViewerImpl::reset()
     m_used_extruders.clear();
     m_total_time = { 0.0f, 0.0f };
     m_travels_time = { 0.0f, 0.0f };
+    m_vertices.clear();
+    m_vertices_colors.clear();
     // swap rather than clear: these are sized by the print, and a reset means the memory
     // should go back, not sit reserved until the next load
-    std::vector<PathVertex>().swap(m_vertices);
-    std::vector<float>().swap(m_vertices_colors);
     for (std::vector<float>& times : m_layer_start_times)
         std::vector<float>().swap(times);
     std::vector<uint32_t>().swap(m_layer_first_vertex);
     std::vector<float>().swap(m_colors_scratch);
-    // BitSet::clear() only zeroes the bits, it keeps the blocks allocated; load() builds a new
-    // bitset anyway and it is never read while m_vertices is empty
-    m_valid_lines_bitset = BitSet<>();
+    m_valid_lines_bitset.clear();
 #if VGCODE_ENABLE_COG_AND_TOOL_MARKERS
     m_cog_marker.reset();
 #endif // VGCODE_ENABLE_COG_AND_TOOL_MARKERS
@@ -1814,7 +1812,6 @@ size_t ViewerImpl::get_used_cpu_memory() const
     ret += sizeof(m_extrusion_roles_colors);
     ret += sizeof(m_options_colors);
     ret += STDVEC_MEMSIZE(m_vertices, PathVertex);
-    ret += STDVEC_MEMSIZE(m_vertices_colors, float);
     for (const std::vector<float>& times : m_layer_start_times)
         ret += STDVEC_MEMSIZE(times, float);
     ret += STDVEC_MEMSIZE(m_layer_first_vertex, uint32_t);

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");