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/Layer.cpp

@@ -360,7 +360,7 @@ void Layer::simplify_support_entity_collection(ExtrusionEntityCollection* entity
 //BBS: method to simplify support path
 void Layer::simplify_support_path(ExtrusionPath * path)
 {
-    const PrintConfig &print_config = this->object()->print()->config();
+    const auto print_config = this->object()->print()->config();
     const bool spiral_mode = print_config.spiral_mode;
     const bool enable_arc_fitting = print_config.enable_arc_fitting;
     const auto scaled_resolution = scaled<double>(print_config.resolution.value);
@@ -375,7 +375,7 @@ void Layer::simplify_support_path(ExtrusionPath * path)
 //BBS: method to simplify support path
 void Layer::simplify_support_multi_path(ExtrusionMultiPath* multipath)
 {
-    const PrintConfig &print_config = this->object()->print()->config();
+    const auto print_config = this->object()->print()->config();
     const bool spiral_mode = print_config.spiral_mode;
     const bool enable_arc_fitting = print_config.enable_arc_fitting;
     const auto scaled_resolution = scaled<double>(print_config.resolution.value);
@@ -392,7 +392,7 @@ void Layer::simplify_support_multi_path(ExtrusionMultiPath* multipath)
 //BBS: method to simplify support path
 void Layer::simplify_support_loop(ExtrusionLoop* loop)
 {
-    const PrintConfig &print_config = this->object()->print()->config();
+    const auto print_config = this->object()->print()->config();
     const bool spiral_mode = print_config.spiral_mode;
     const bool enable_arc_fitting = print_config.enable_arc_fitting;
     const auto scaled_resolution = scaled<double>(print_config.resolution.value);

src/libslic3r/LayerRegion.cpp

@@ -1074,7 +1074,7 @@ void LayerRegion::simplify_entity_collection(ExtrusionEntityCollection* entity_c
 
 void LayerRegion::simplify_path(ExtrusionPath* path)
 {
-    const PrintConfig &print_config = this->layer()->object()->print()->config();
+    const auto print_config = this->layer()->object()->print()->config();
     const bool spiral_mode = print_config.spiral_mode;
     const bool enable_arc_fitting = print_config.enable_arc_fitting;
     const auto scaled_resolution = scaled<double>(print_config.resolution.value);
@@ -1092,7 +1092,7 @@ void LayerRegion::simplify_path(ExtrusionPath* path)
 
 void LayerRegion::simplify_multi_path(ExtrusionMultiPath* multipath)
 {
-    const PrintConfig &print_config = this->layer()->object()->print()->config();
+    const auto print_config = this->layer()->object()->print()->config();
     const bool spiral_mode = print_config.spiral_mode;
     const bool enable_arc_fitting = print_config.enable_arc_fitting;
     const auto scaled_resolution = scaled<double>(print_config.resolution.value);
@@ -1112,7 +1112,7 @@ void LayerRegion::simplify_multi_path(ExtrusionMultiPath* multipath)
 
 void LayerRegion::simplify_loop(ExtrusionLoop* loop)
 {
-    const PrintConfig &print_config = this->layer()->object()->print()->config();
+    const auto print_config = this->layer()->object()->print()->config();
     const bool spiral_mode = print_config.spiral_mode;
     const bool enable_arc_fitting = print_config.enable_arc_fitting;
     const auto scaled_resolution = scaled<double>(print_config.resolution.value);

src/libslic3r/Print.cpp

@@ -2604,11 +2604,6 @@ void Print::auto_assign_extruders(ModelObject* model_object) const
 
 void  PrintObject::set_shared_object(PrintObject *object)
 {
-    // Orca: from now on m_layers / m_support_layers only alias the shared object's layers, so release the
-    // ones this object still owns (it may have sliced itself before it became shareable again).
-    // Both are no-ops once m_shared_object is set, so this cannot free layers owned by another object.
-    clear_support_layers();
-    clear_layers();
     m_shared_object = object;
     BOOST_LOG_TRIVIAL(info) << __FUNCTION__ << boost::format(": this=%1%, found shared object from %2%")%this%m_shared_object;
 }
@@ -4334,9 +4329,9 @@ bool Print::is_dynamic_group_reorder() const
     return true;
 }
 
-int Print::get_filament_config_indx(int filament_id, int layer_id)
+int Print::get_filament_config_indx(int filament_id, int layer_id, bool use_cache)
 {
-    return get_config_index(filament_id, layer_id, m_config.filament_extruder_variant.values, m_filament_self_index, m_filament_index_map);
+    return get_config_index(filament_id, layer_id, m_config.filament_extruder_variant.values, m_filament_self_index, use_cache ? &m_filament_index_map : nullptr);
 }
 
 void Print::update_filament_self_index_cache()
@@ -4379,7 +4374,7 @@ int Print::get_nozzle_config_index(int filament_id, int layer_id)
     return get_config_index(filament_id, layer_id, m_default_region_config.print_extruder_variant.values, m_default_region_config.print_extruder_id.values, m_nozzle_index_map);
 }
 
-int Print::get_config_index(int filament_id, int layer_id, const std::vector<std::string> &variant_list, const std::vector<int>& self_index_list, FilamentIndexMap &index_map)
+int Print::get_config_index(int filament_id, int layer_id, const std::vector<std::string> &variant_list, const std::vector<int>& self_index_list, FilamentIndexMap *index_map)
 {
     auto group_result = get_layered_nozzle_group_result();
     // Orca: defensive — when no grouping producer has published a result yet, fall back to the
@@ -4390,7 +4385,8 @@ int Print::get_config_index(int filament_id, int layer_id, const std::vector<std
     if (!nozzle_info.has_value()) {
         // Orca: this fallback runs per-filament/per-layer in the g-code hot path — log once per filament
         // (reset each slice) instead of flooding thousands of identical lines that bury the real error.
-        if (m_missing_nozzle_group_logged.insert(filament_id).second)
+        // Without the cache, the log set is left alone too; the cached caller reports the same filament.
+        if (index_map && m_missing_nozzle_group_logged.insert(filament_id).second)
             BOOST_LOG_TRIVIAL(error) << __FUNCTION__
                                      << boost::format(", Line %1%: could not found group_nozzle_info corresponding to filament_id %2%, layer_id %3% (further occurrences for this filament suppressed)") % __LINE__ % filament_id %
                                             layer_id;
@@ -4399,15 +4395,17 @@ int Print::get_config_index(int filament_id, int layer_id, const std::vector<std
 
     ExtruderType     extruder_type      = ExtruderType(m_config.extruder_type.get_at(nozzle_info->extruder_id));
     NozzleVolumeType nozzle_volume_type = nozzle_info->volume_type;
+    if (!index_map)
+        return get_config_index_base(nozzle_volume_type, extruder_type, filament_id + 1, variant_list, self_index_list);
 
     FilamentIndexKey key{filament_id, extruder_type, nozzle_volume_type};
-    auto             iter = index_map.find(key);
-    if (iter == index_map.end()) {
+    auto             iter = index_map->find(key);
+    if (iter == index_map->end()) {
         int index = get_config_index_base(nozzle_volume_type, extruder_type, filament_id + 1, variant_list, self_index_list);
-        index_map[key] = index;
+        (*index_map)[key] = index;
         return index;
     } else {
-        return index_map[key];
+        return iter->second;
     }
 }
 

src/libslic3r/PrintObject.cpp

@@ -987,9 +987,6 @@ void PrintObject::generate_support_material()
             this->_generate_support_material();
             m_print->throw_if_canceled();
         }
-        // Orca: the tree support collision/avoidance caches and support nodes are only used while this step runs
-        // (detect_overhangs() rebuilds them from scratch), so don't keep them resident until the next slice.
-        this->clear_tree_support_preview_cache();
         this->set_done(posSupportMaterial);
     }
 }

src/libslic3r/PrintObjectSlice.cpp

@@ -1346,7 +1346,7 @@ void PrintObject::slice_volumes()
                         if (min_growth < 0.f || elfoot > 0.f) {
                             // Apply the negative XY compensation. (the ones that is <0)
                             ExPolygons trimming;
-                            const float eps = float(scale_(m_config.slice_closing_radius.value) * 1.5);
+                            static const float eps = float(scale_(m_config.slice_closing_radius.value) * 1.5);
                             if (elfoot > 0.f) {
                                 ExPolygons expolygons_to_compensate = offset_ex(layer->merged(eps), -eps);
                                 lslices_elfoot_uncompensated[layer_id] = expolygons_to_compensate;

src/libslic3r/Support/TreeSupport.cpp

@@ -1820,15 +1820,37 @@ coordf_t TreeSupport::get_radius(const SupportNode* node)
     return node->radius;
 }
 
-// Orca: these are hit up to several times per node per layer in drop_nodes(), so hand out a
-// reference into the TreeSupportData cache instead of copying the ExPolygons out of it.
-const ExPolygons& TreeSupport::get_avoidance(coordf_t radius, size_t obj_layer_nr)
+ExPolygons TreeSupport::get_avoidance(coordf_t radius, size_t obj_layer_nr)
 {
+#if USE_SUPPORT_3D
+    if (m_model_volumes) {
+        bool on_build_plate = m_object_config->support_on_build_plate_only.value;
+        const Polygons& avoid_polys = m_model_volumes->getAvoidance(radius, obj_layer_nr, TreeSupport3D::TreeModelVolumes::AvoidanceType::FastSafe, on_build_plate, true);
+        ExPolygons expolys;
+        for (auto& poly : avoid_polys)
+            expolys.emplace_back(std::move(poly));
+        return expolys;
+    }
+    return ExPolygons();
+#else
     return m_ts_data->get_avoidance(radius, obj_layer_nr);
+#endif
 }
-const ExPolygons& TreeSupport::get_collision(coordf_t radius, size_t layer_nr)
+ExPolygons TreeSupport::get_collision(coordf_t radius, size_t layer_nr)
 {
+#if USE_SUPPORT_3D
+    if (m_model_volumes) {
+        bool on_build_plate = m_object_config->support_on_build_plate_only.value;
+        const Polygons& collision_polys = m_model_volumes->getCollision(radius, layer_nr, true);
+        ExPolygons expolys;
+        for (auto& poly : collision_polys)
+            expolys.emplace_back(std::move(poly));
+        return expolys;
+    }
+#else
     return m_ts_data->get_collision(radius, layer_nr);
+#endif
+    return ExPolygons();
 }
 Polygons TreeSupport::get_collision_polys(coordf_t radius, size_t layer_nr)
 {
@@ -2617,11 +2639,7 @@ void TreeSupport::draw_circles()
 #endif  // SUPPORT_TREE_DEBUG_TO_SVG
 
     SupportLayerPtrs& ts_layers = m_object->support_layers();
-    // Orca: the vector owns its layers, so the dropped ones have to be deleted, not just unlinked.
-    // std::stable_partition (unlike std::remove_if) leaves exactly the dropped layers in the tail.
-    auto iter = std::stable_partition(ts_layers.begin(), ts_layers.end(), [](SupportLayer* ts_layer) { return ts_layer->height >= EPSILON; });
-    for (auto it = iter; it != ts_layers.end(); ++it)
-        delete *it;
+    auto iter = std::remove_if(ts_layers.begin(), ts_layers.end(), [](SupportLayer* ts_layer) { return ts_layer->height < EPSILON; });
     ts_layers.erase(iter, ts_layers.end());
     for (int layer_nr = 0; layer_nr < ts_layers.size(); layer_nr++) {
         ts_layers[layer_nr]->upper_layer = layer_nr != ts_layers.size() - 1 ? ts_layers[layer_nr + 1] : nullptr;
@@ -2864,7 +2882,7 @@ void TreeSupport::drop_nodes()
                     //Insert a completely new node and let both original nodes fade.
                     Point next_position = (node.position + neighbours[0]) / 2; //Average position of the two nodes.
                     coordf_t next_radius = calc_radius(node.dist_mm_to_top+height_next);
-                    const ExPolygons& avoid_layer = get_avoidance(next_radius, obj_layer_nr_next);
+                    auto avoid_layer = get_avoidance(next_radius, obj_layer_nr_next);
                     if (group_index == 0)
                     {
                         //Avoid collisions.
@@ -3051,7 +3069,7 @@ void TreeSupport::drop_nodes()
                 }
 #endif
                 coordf_t next_radius = calc_radius(node.dist_mm_to_top + height_next);
-                const ExPolygons& avoidance_next = get_avoidance(next_radius, obj_layer_nr_next);
+                auto avoidance_next = get_avoidance(next_radius, obj_layer_nr_next);
 
                 Point  to_outside         = projection_onto(avoidance_next, node.position);
                 Point  direction_to_outer = to_outside - node.position;
@@ -3105,7 +3123,7 @@ void TreeSupport::drop_nodes()
                         if (is_outside) { next_layer_vertex = candidate_vertex; }
                     }
                 }
-                const ExPolygons& next_collision = get_collision(0, obj_layer_nr_next);
+                auto              next_collision = get_collision(0, obj_layer_nr_next);
                 const bool   to_buildplate  = !is_inside_ex(m_ts_data->m_layer_outlines[obj_layer_nr_next], next_layer_vertex);
                 // don't increase radius if next node will collide partially with the object (STUDIO-7883)
                 to_outside             = projection_onto(next_collision, next_layer_vertex);

src/libslic3r/Support/TreeSupport.hpp

@@ -511,9 +511,9 @@ private:
     coordf_t calc_branch_radius(coordf_t base_radius, coordf_t mm_to_top, double diameter_angle_scale_factor, bool use_min_distance=true);
     coordf_t   calc_radius(coordf_t mm_to_top);
     coordf_t get_radius(const SupportNode* node);
-    const ExPolygons& get_avoidance(coordf_t radius, size_t obj_layer_nr);
+    ExPolygons get_avoidance(coordf_t radius, size_t obj_layer_nr);
     // layer's expolygon expanded by radius+m_xy_distance
-    const ExPolygons& get_collision(coordf_t radius, size_t layer_nr);
+    ExPolygons get_collision(coordf_t radius, size_t layer_nr);
     // get Polygons instead of ExPolygons
     Polygons get_collision_polys(coordf_t radius, size_t layer_nr);
 

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