Merge branch 'main' into perf/slicing-optimizations

Unknown options and missing option values now stop the script instead of being ignored.

build_release_macos.sh

@@ -47,7 +47,7 @@ while getopts ":dpa:snt:xbc:i:j:Tuh" opt; do
     u )
         export BUILD_TARGET="universal"
         ;;
-    h ) echo "Usage: ./build_release_macos.sh [-d]"
+    h ) echo "Usage: ./build_release_macos.sh [-d] [-- CMAKE_ARGS...]"
         echo "   -d: Build deps only"
         echo "   -a: Set ARCHITECTURE (arm64 or x86_64 or universal)"
         echo "   -s: Build slicer only"
@@ -60,13 +60,33 @@ while getopts ":dpa:snt:xbc:i:j:Tuh" opt; do
         echo "   -i: Add a prefix to ignore during CMake dependency discovery (repeatable), defaults to /opt/local:/usr/local:/opt/homebrew"
         echo "   -j: Set the number of parallel build jobs (CMAKE_BUILD_PARALLEL_LEVEL)"
         echo "   -T: Build and run tests (set ORCA_TESTS_BUILD_ONLY=1 to build without running)"
+        echo "   -- CMAKE_ARGS...: pass everything after '--' to the cmake configure step of the deps (-d) and slicer (-s) builds,"
+        echo "       e.g. -DDESTDIR=<dir> for the deps, -DCMAKE_PREFIX_PATH=<dir>/usr/local -DSLIC3R_PCH=OFF for the slicer, --fresh."
+        echo "       They come last on the cmake command line. Use absolute paths: cmake runs in the build directory."
         exit 0
         ;;
+    : )
+        echo "Option -${OPTARG} requires an argument, aborting."
+        exit 1
+        ;;
     * )
+        echo "Unknown option -${OPTARG}, aborting. CMake arguments must follow '--'."
+        exit 1
         ;;
   esac
 done
 
+# getopts stops at '--'; whatever follows is handed to cmake unchanged.
+if [[ ${OPTIND} -le $# ]] ; then
+    separator_index=$((OPTIND-1))
+    if [[ "${!separator_index}" != "--" ]] ; then
+        echo "Unexpected argument '${!OPTIND}': cmake arguments must follow '--', aborting."
+        exit 1
+    fi
+fi
+shift $((OPTIND-1))
+EXTRA_CMAKE_ARGS=("$@")
+
 # Set defaults
 
 if [ -z "$ARCH" ]; then
@@ -211,7 +231,8 @@ function build_deps() {
                         -DCMAKE_OSX_DEPLOYMENT_TARGET="${OSX_DEPLOYMENT_TARGET}" \
                         -DCMAKE_IGNORE_PREFIX_PATH="${CMAKE_IGNORE_PREFIX_PATH}" \
                         "${CMAKE_CCACHE_ARGS[@]}" \
-                        ${CMAKE_POLICY_COMPAT}
+                        ${CMAKE_POLICY_COMPAT} \
+                        "${EXTRA_CMAKE_ARGS[@]}"
                 fi
                 cmake --build . --config "$BUILD_CONFIG" --target deps
             )
@@ -314,7 +335,8 @@ function build_slicer() {
                     -DCMAKE_OSX_DEPLOYMENT_TARGET="${OSX_DEPLOYMENT_TARGET}" \
                     -DCMAKE_IGNORE_PREFIX_PATH="${CMAKE_IGNORE_PREFIX_PATH}" \
                     "${CMAKE_CCACHE_ARGS[@]}" \
-                    ${CMAKE_POLICY_COMPAT}
+                    ${CMAKE_POLICY_COMPAT} \
+                    "${EXTRA_CMAKE_ARGS[@]}"
             fi
             cmake --build . --config "$BUILD_CONFIG" --target "$SLICER_BUILD_TARGET"
         )

docs/HLSD/polygon-clipping.md

@@ -62,6 +62,23 @@ Clipper2 behaves differently by default, the wrapper adjusts it.
   clip do not leave slivers.
 - Open polylines are clipped with the non-zero rule and keep their direction.
 
+### Tiled booleans
+
+The sweep slows down with the number of edges crossing a scan line, so a layer
+cut into thousands of pieces makes every whole-layer boolean expensive.
+`diff_ex_by_piece()` and `intersection_ex_by_piece()` take a subject of
+non-overlapping `ExPolygons`, group them into tiles with
+`ClipperUtils::tile_expolygons()`, and run each tile in parallel against only
+the clip polygons near it, cut to the tile's box. Below 128 pieces there is a
+single tile, and they are the plain `diff_ex()` / `intersection_ex()`.
+
+The result covers the same area as the plain call. Without the safety offset
+the rings are the same. With it, each tile unites only the clip polygons near
+it, so a clip edge that the whole-layer union splits where it crosses a distant
+clip polygon stays whole, and a crossing with the subject can round 1 unit
+differently. The tiles' results are concatenated in tile order, so the order of
+the output `ExPolygons` differs from the plain call.
+
 ### Offsets
 
 - Before offsetting, input vertices closer than

src/libslic3r/ClipperUtils.cpp

@@ -9,6 +9,8 @@
 #include <numeric>
 #include <unordered_map>
 
+#include <tbb/parallel_for.h>
+
 #include "ClipperUtils.hpp"
 #include "BoundingBox.hpp"
 #include "ExPolygon.hpp"
@@ -800,6 +802,72 @@ Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r
     { return _clipper_ex(ctIntersection, ClipperUtils::SurfacesProvider(subject), ClipperUtils::SurfacesProvider(clip), do_safety_offset); }
 Slic3r::ExPolygons intersection_ex(const Slic3r::SurfacesPtr &subject, const Slic3r::ExPolygons &clip, ApplySafetyOffset do_safety_offset)
     { return _clipper_ex(ctIntersection, ClipperUtils::SurfacesPtrProvider(subject), ClipperUtils::ExPolygonsProvider(clip), do_safety_offset); }
+
+namespace ClipperUtils {
+    std::vector<ExPolygonsTile> tile_expolygons(const ExPolygons &expolygons, size_t per_tile)
+    {
+        BoundingBox              extent;
+        std::vector<BoundingBox> bboxes;
+        bboxes.reserve(expolygons.size());
+        for (const ExPolygon &expoly : expolygons) {
+            bboxes.emplace_back(get_extents(expoly));
+            extent.merge(bboxes.back());
+        }
+        if (! extent.defined)
+            return {};
+        const int     tiles  = std::clamp(int(std::sqrt(double(expolygons.size()) / double(std::max<size_t>(per_tile, 1)))), 1, 32);
+        const Point   size   = extent.size();
+        const coord_t tile_w = std::max<coord_t>(1, size.x() / tiles + 1), tile_h = std::max<coord_t>(1, size.y() / tiles + 1);
+        std::vector<ExPolygonsTile> out(size_t(tiles * tiles));
+        for (size_t i = 0; i < expolygons.size(); ++ i) {
+            const Point c = bboxes[i].center();
+            ExPolygonsTile &tile = out[size_t(std::clamp(int((c.y() - extent.min.y()) / tile_h), 0, tiles - 1) * tiles +
+                                              std::clamp(int((c.x() - extent.min.x()) / tile_w), 0, tiles - 1))];
+            tile.members.emplace_back(i);
+            tile.bbox.merge(bboxes[i]);
+        }
+        out.erase(std::remove_if(out.begin(), out.end(), [](const ExPolygonsTile &tile) { return tile.members.empty(); }), out.end());
+        return out;
+    }
+}
+
+static Slic3r::ExPolygons clipper_ex_by_piece(ClipType clipType, const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
+{
+    // A few dozen subject ExPolygons to a tile, each tile one Clipper call with the clip cut to the tile's box.
+    const std::vector<ClipperUtils::ExPolygonsTile> tiles = ClipperUtils::tile_expolygons(subject, 32);
+    // One tile is the plain call: cutting the clip would only cost time.
+    if (tiles.size() <= 1)
+        return _clipper_ex(clipType, ClipperUtils::ExPolygonsProvider(subject), ClipperUtils::PolygonsProvider(clip), do_safety_offset);
+    std::vector<BoundingBox> clip_bboxes;
+    clip_bboxes.reserve(clip.size());
+    for (const Polygon &polygon : clip)
+        clip_bboxes.emplace_back(get_extents(polygon));
+
+    std::vector<Slic3r::ExPolygons> out_tiles(tiles.size());
+    tbb::parallel_for(size_t(0), tiles.size(), [&](size_t tile_idx) {
+        const ClipperUtils::ExPolygonsTile &tile = tiles[tile_idx];
+        Slic3r::ExPolygons local_subject;
+        local_subject.reserve(tile.members.size());
+        for (size_t i : tile.members)
+            local_subject.emplace_back(subject[i]);
+        // Grown so that the cut edges of the clip stay clear of the subject, also after the safety offset.
+        const BoundingBox bbox = tile.bbox.inflated(SCALED_EPSILON);
+        Polygons local_clip;
+        for (size_t i = 0; i < clip.size(); ++i)
+            if (clip_bboxes[i].overlap(bbox))
+                if (Polygon clipped = ClipperUtils::clip_clipper_polygon_with_subject_bbox(clip[i], bbox); ! clipped.empty())
+                    local_clip.emplace_back(std::move(clipped));
+        out_tiles[tile_idx] = _clipper_ex(clipType, ClipperUtils::ExPolygonsProvider(local_subject), ClipperUtils::PolygonsProvider(local_clip), do_safety_offset);
+    });
+    Slic3r::ExPolygons out;
+    for (Slic3r::ExPolygons &out_tile : out_tiles)
+        append(out, std::move(out_tile));
+    return out;
+}
+Slic3r::ExPolygons diff_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
+    { return clipper_ex_by_piece(ctDifference, subject, clip, do_safety_offset); }
+Slic3r::ExPolygons intersection_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset)
+    { return clipper_ex_by_piece(ctIntersection, subject, clip, do_safety_offset); }
 // May be used to "heal" unusual models (3DLabPrints etc.) by providing fill_type (pftEvenOdd, pftNonZero, pftPositive, pftNegative).
 Slic3r::ExPolygons union_ex(const Slic3r::Polygons &subject, PolyFillType fill_type)
     { return _clipper_ex(ctUnion, ClipperUtils::PolygonsProvider(subject), ClipperUtils::EmptyPathsProvider(), ApplySafetyOffset::No, fill_type); }

src/libslic3r/ClipperUtils.hpp

@@ -5,6 +5,7 @@
 #include "Polyline.hpp"
 #include "Line.hpp"
 #include "libslic3r.h"
+#include "BoundingBox.hpp"
 #include "ExPolygon.hpp"
 #include "Polygon.hpp"
 #include "Surface.hpp"
@@ -332,6 +333,15 @@ namespace ClipperUtils {
     [[nodiscard]] Polygons clip_clipper_polygons_with_subject_bbox(const ExPolygon &src, const BoundingBox &bbox, const bool get_entire_polygons = false);
     [[nodiscard]] Polygons clip_clipper_polygons_with_subject_bbox(const ExPolygons &src, const BoundingBox &bbox, const bool get_entire_polygons = false);
 
+    // Splits ExPolygons into tiles by the centres of their boxes, about `per_tile` of them to a tile, to run Clipper on a
+    // layer of many pieces tile by tile. Returns the non-empty tiles, each with the indices of its ExPolygons and their box.
+    struct ExPolygonsTile
+    {
+        BoundingBox         bbox;
+        std::vector<size_t> members;
+    };
+    [[nodiscard]] std::vector<ExPolygonsTile> tile_expolygons(const ExPolygons &expolygons, size_t per_tile);
+
     }
 
 // offset Polygons
@@ -527,6 +537,11 @@ Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r
 Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r::ExPolygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
 Slic3r::ExPolygons intersection_ex(const Slic3r::Surfaces &subject, const Slic3r::Surfaces &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
 Slic3r::ExPolygons intersection_ex(const Slic3r::SurfacesPtr &subject, const Slic3r::ExPolygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
+// diff_ex() / intersection_ex() of the subject split into tiles, each against only the part of the clip near it, the tiles in
+// parallel. The same area as the operation on the whole subject when its ExPolygons do not overlap, and much faster for a
+// subject of thousands of pieces spread over a layer: Clipper slows down with the number of edges crossing a scan line.
+Slic3r::ExPolygons diff_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
+Slic3r::ExPolygons intersection_ex_by_piece(const Slic3r::ExPolygons &subject, const Slic3r::Polygons &clip, ApplySafetyOffset do_safety_offset = ApplySafetyOffset::No);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polylines &subject, const Slic3r::Polygon &clip);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polyline &subject, const Slic3r::ExPolygon &clip);
 Slic3r::Polylines  intersection_pl(const Slic3r::Polylines &subject, const Slic3r::ExPolygon &clip);

src/libslic3r/Config.hpp

@@ -377,7 +377,8 @@ public:
     virtual void set(const ConfigOption* rhs, size_t start, size_t len)                                                     = 0;
     virtual void set_with_restore(const ConfigOptionVectorBase* rhs, std::vector<int>& restore_index, int stride)           = 0;
     virtual void set_with_restore_2(const ConfigOptionVectorBase* rhs, std::vector<int>& restore_index, int start, int len, bool skip_error = false) = 0;
-    virtual void set_only_diff(const ConfigOptionVectorBase* rhs, std::vector<int>& diff_index, int stride)                 = 0;
+    // keep_nil: copy a nil column from rhs as well, for options whose nil means "disabled" rather than "inherit".
+    virtual void set_only_diff(const ConfigOptionVectorBase* rhs, std::vector<int>& diff_index, int stride, bool keep_nil = false) = 0;
     virtual void set_to_index(const ConfigOptionVectorBase* rhs, std::vector<int>& dest_index, int stride) = 0;
     virtual void set_with_nil(const ConfigOptionVectorBase* rhs, const ConfigOptionVectorBase* inherits, int stride)        = 0;
     // Resize the vector of values, copy the newly added values from opt_default if provided.
@@ -580,7 +581,7 @@ public:
     //set a item related with extruder variants when loading user config, only set the different value of some extruder
     //rhs: item from user config
     //diff_index: which index in this vector need to be set
-    virtual void set_only_diff(const ConfigOptionVectorBase* rhs, std::vector<int>& diff_index, int stride) override
+    virtual void set_only_diff(const ConfigOptionVectorBase* rhs, std::vector<int>& diff_index, int stride, bool keep_nil) override
     {
         if (rhs->type() == this->type()) {
             // Assign the first value of the rhs vector.
@@ -592,7 +593,7 @@ public:
             for (size_t i = 0; i < diff_index.size(); i++) {
                 if (diff_index[i] != -1) {
                     for (size_t j = 0; j < stride; j++) {
-                        if (!other->is_nil(diff_index[i] * stride))
+                        if (keep_nil || !other->is_nil(diff_index[i] * stride))
                             this->values[i * stride + j] = other->values[diff_index[i] * stride + j];
                     }
                 }
@@ -841,8 +842,12 @@ public:
     {
         UNUSED(append);
         std::istringstream iss(str);
-        iss >> this->value;
+        double value;
-        return !iss.fail();
+        iss >> value;
+        if (iss.fail())
+            return false;
+        this->value = value;
+        return true;
     }
 
     bool operator==(const ConfigOption &rhs) const override
@@ -1033,8 +1038,12 @@ public:
     {
         UNUSED(append);
         std::istringstream iss(str);
-        iss >> this->value;
+        int value;
-        return !iss.fail();
+        iss >> value;
+        if (iss.fail())
+            return false;
+        this->value = value;
+        return true;
     }
 
     ConfigOptionInt& operator=(const ConfigOption *opt)
@@ -1252,8 +1261,12 @@ public:
         UNUSED(append);
         // don't try to parse the trailing % since it's optional
         std::istringstream iss(str);
-        iss >> this->value;
+        double value;
-        return !iss.fail();
+        iss >> value;
+        if (iss.fail())
+            return false;
+        this->value = value;
+        return true;
     }
 
 private:
@@ -1365,10 +1378,14 @@ public:
     bool deserialize(const std::string &str, bool append = false) override
     {
         UNUSED(append);
-        this->percent = str.find_first_of("%") != std::string::npos;
         std::istringstream iss(str);
-        iss >> this->value;
+        double value;
-        return !iss.fail();
+        iss >> value;
+        if (iss.fail())
+            return false;
+        this->value   = value;
+        this->percent = str.find_first_of("%") != std::string::npos;
+        return true;
     }
 
 private:
@@ -1538,8 +1555,12 @@ public:
     {
         UNUSED(append);
         char dummy;
-        return sscanf(str.data(), " %lf , %lf %c", &this->value(0), &this->value(1), &dummy) == 2 ||
+        Vec2d value;
-               sscanf(str.data(), " %lf x %lf %c", &this->value(0), &this->value(1), &dummy) == 2;
+        if (sscanf(str.data(), " %lf , %lf %c", &value(0), &value(1), &dummy) != 2 &&
+            sscanf(str.data(), " %lf x %lf %c", &value(0), &value(1), &dummy) != 2)
+            return false;
+        this->value = value;
+        return true;
     }
 
 private:
@@ -1658,8 +1679,12 @@ public:
     {
         UNUSED(append);
         char dummy;
-        return sscanf(str.data(), " %lf , %lf , %lf %c", &this->value(0), &this->value(1), &this->value(2), &dummy) == 3 ||
+        Vec3d value;
-               sscanf(str.data(), " %lf x %lf x %lf %c", &this->value(0), &this->value(1), &this->value(2), &dummy) == 3;
+        if (sscanf(str.data(), " %lf , %lf , %lf %c", &value(0), &value(1), &value(2), &dummy) != 3 &&
+            sscanf(str.data(), " %lf x %lf x %lf %c", &value(0), &value(1), &value(2), &dummy) != 3)
+            return false;
+        this->value = value;
+        return true;
     }
 
 private:

src/libslic3r/Fill/Fill.cpp

@@ -22,6 +22,8 @@
 #include "../PrintConfig.hpp"
 #include "../Surface.hpp"
 
+#include <tbb/parallel_for.h>
+
 #include "AABBTreeLines.hpp"
 #include "libslic3r/Config.hpp"
 #include "libslic3r/ExPolygon.hpp"
@@ -675,24 +677,28 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
     if (!line_based_pattern) {
         const coord_t scaled_spacing = scaled<coord_t>(fill.params.spacing);
 
-        for (const ExPolygon &expolygon : fill.expolygons) {
+        // Each expolygon is split on its own, so they run in parallel and are collected in their original order.
+        std::vector<std::pair<ExPolygons, ExPolygons>> split_parts(fill.expolygons.size()); // normal, narrow
+        tbb::parallel_for(size_t(0), fill.expolygons.size(), [&](size_t idx) {
+            const ExPolygon &expolygon = fill.expolygons[idx];
             Polygons filled_area = to_polygons(expolygon);
 
             // "Core" area: open (erode+dilate) to drop thin features, then clamp back to the original polygon.
             Polygons inner_area  = intersection(filled_area, opening(filled_area, scaled_spacing, scaled_spacing));
 
             if (inner_area.empty()) {
-                narrow_infill.emplace_back(expolygon);
+                split_parts[idx].second.emplace_back(expolygon);
-                continue;
+                return;
             }
 
             ExPolygons inner_ex = union_ex(inner_area);
             ExPolygons expolys{expolygon};
-            ExPolygons narrow_ex = diff_ex(expolys, inner_ex);
+            split_parts[idx].second = diff_ex(expolys, inner_ex);         // narrow infill area
-            ExPolygons normal_ex = intersection_ex(expolys, inner_ex);
+            split_parts[idx].first  = intersection_ex(expolys, inner_ex); // normal infill area
-
+        });
-            append(normal_infill, normal_ex); // normal infill area
+        for (auto &[normal_ex, narrow_ex] : split_parts) {
-            append(narrow_infill, narrow_ex); // narrow infill area
+            append(normal_infill, std::move(normal_ex));
+            append(narrow_infill, std::move(narrow_ex));
         }
 
         return;
@@ -714,7 +720,10 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
     }
     const double aligning_angle = -base_angle + PI;
 
-	for (const ExPolygon &expolygon : fill.expolygons) {
+    // Each expolygon is reconstructed on its own, so they run in parallel and are collected in their original order.
+    std::vector<Polygons> split_reconstructed(fill.expolygons.size());
+    tbb::parallel_for(size_t(0), fill.expolygons.size(), [&](size_t expolygon_idx) {
+        const ExPolygon &expolygon = fill.expolygons[expolygon_idx];
         Polygons filled_area = to_polygons(expolygon);
         polygons_rotate(filled_area, aligning_angle);
         BoundingBox bb = get_extents(filled_area);
@@ -845,8 +854,10 @@ void split_solid_surface(size_t layer_id, const SurfaceFill &fill, ExPolygons &n
             }
         }
 
-        polygons_append(normal_fill_areas, reconstructed_area);
+        split_reconstructed[expolygon_idx] = std::move(reconstructed_area);
-    }
+    });
+    for (Polygons &reconstructed_area : split_reconstructed)
+        polygons_append(normal_fill_areas, std::move(reconstructed_area));
 
     polygons_rotate(normal_fill_areas, -aligning_angle);
 
@@ -1473,7 +1484,15 @@ void Layer::make_fills(const FillAdaptive::RegionOctrees* fill_octrees, FillLigh
             f->set_bounding_box(body >= 0 ? this->object()->separated_body_bboxes()[body] : bbox);
             f->adapt_fill_octree = octrees ? octrees->get(body) : nullptr;
 
-            f->no_overlap_expolygons = intersection_ex(surface_fill.no_overlap_expolygons, ExPolygons() = {expoly}, ApplySafetyOffset::Yes);
+            // Only the part of the layer-wide no-overlap area under this expolygon matters, so clip it to the
+            // expolygon's box first (padded past the safety offset, which grows the clip side). The result is
+            // identical; the cost is not: a layer split into many small fills, e.g. by colour painting,
+            // otherwise intersects every one of them with the whole layer.
+            BoundingBox no_overlap_bbox = get_extents(expoly);
+            no_overlap_bbox.offset(SCALED_EPSILON);
+            f->no_overlap_expolygons = intersection_ex(
+                ClipperUtils::clip_clipper_polygons_with_subject_bbox(surface_fill.no_overlap_expolygons, no_overlap_bbox),
+                ExPolygons() = {expoly}, ApplySafetyOffset::Yes);
             if (params.symmetric_infill_y_axis) {
                 params.symmetric_y_axis = f->extended_object_bounding_box().center().x();
                 expoly.symmetric_y(params.symmetric_y_axis);

src/libslic3r/GCode/OrderingStrategies.cpp

@@ -6,6 +6,7 @@
 #include "../ShortestPath.hpp"
 #include "libslic3r/Point.hpp"
 #include "libslic3r/PrintConfig.hpp"
+#include "libslic3r/libslic3r.h"
 
 #include <algorithm>
 #include <cassert>
@@ -141,15 +142,87 @@ bool tsp_remove_crossings(std::vector<size_t>& path, const Points& centers)
         return {std::numeric_limits<size_t>::max(), std::numeric_limits<size_t>::max()};
     };
 
+    // For many islands, the same scan with the edges binned in a uniform grid over their boxes, so each edge is only tested against the edges sharing a
+    // cell with it - two edges whose boxes overlap always do. It returns the same crossing as the all-pairs scan
+    // (smallest i, then smallest j), so the result is unchanged. The all-pairs scan is quadratic in the edge count and
+    // runs again after every reversal; rebuilding the grid costs more than it saves below the threshold.
+    constexpr size_t grid_min_size = 500;
+    BoundingBox extent;
+    for (size_t idx : path)
+        extent.merge(centers[idx]);
+    const int     grid_n = std::clamp(int(std::sqrt(double(pn))), 1, 256);
+    const coord_t cell_w = std::max<coord_t>(1, (extent.max.x() - extent.min.x()) / grid_n + 1);
+    const coord_t cell_h = std::max<coord_t>(1, (extent.max.y() - extent.min.y()) / grid_n + 1);
+    const auto    for_cells = [&](const Point& a, const Point& b, auto&& fn) {
+        const int x0 = int((std::min(a.x(), b.x()) - extent.min.x()) / cell_w), x1 = int((std::max(a.x(), b.x()) - extent.min.x()) / cell_w);
+        const int y0 = int((std::min(a.y(), b.y()) - extent.min.y()) / cell_h), y1 = int((std::max(a.y(), b.y()) - extent.min.y()) / cell_h);
+        for (int y = y0; y <= y1; ++y)
+            for (int x = x0; x <= x1; ++x)
+                fn(y * grid_n + x);
+    };
+    std::vector<std::vector<size_t>> edge_cells(size_t(grid_n) * grid_n);
+
+    auto find_crossing_grid = [&]() -> std::pair<size_t, size_t> {
+        for (std::vector<size_t>& cell : edge_cells)
+            cell.clear();
+        for (size_t j = 0; j < n_edges; ++j)
+            for_cells(centers[path[j]], centers[path[(j + 1) % pn]], [&](int cell) { edge_cells[cell].emplace_back(j); });
+
+        for (size_t i = 0; i < n_edges; ++i) {
+            const Point& ai = centers[path[i]];
+            const Point& bi = centers[path[(i + 1) % pn]];
+
+            size_t first_j = std::numeric_limits<size_t>::max();
+            for_cells(ai, bi, [&](int cell) {
+                for (size_t j : edge_cells[cell]) {
+                    if (j < i + 2 || j >= first_j) continue;
+                    // Skip the (0, pn-1) pair: edges (0,1) and (pn-1,0) share node 0.
+                    if (i == 0 && j == pn - 1) continue;
+
+                    const Point& aj = centers[path[j]];
+                    const Point& bj = centers[path[(j + 1) % pn]];
+
+                    if (!bboxes_overlap(ai, bi, aj, bj)) continue;
+                    if (Geometry::segments_intersect(ai, bi, aj, bj))
+                        first_j = j;
+                }
+            });
+            if (first_j != std::numeric_limits<size_t>::max())
+                return {i, first_j};
+        }
+        return {std::numeric_limits<size_t>::max(), std::numeric_limits<size_t>::max()};
+    };
+
     // Process crossings one at a time: find first, reverse it, restart scan.
     // Cap iterations to prevent infinite loops on collinear/overlapping segments.
-    int max_iters = static_cast<int>(pn * pn);
+    const int max_iters = static_cast<int>(pn * pn);
     bool improved = false;
-    while (max_iters-- > 0) {
+    // Reversing between two segments that only touch or overlap along a line need not remove the intersection, so on
-        auto [ci, cj] = find_crossing();
+    // islands laid out on a regular grid (a tiled texture, an array of parts) the loop can cycle through the same
-        if (ci == std::numeric_limits<size_t>::max()) break;
+    // orderings until the pn * pn cap. Once an ordering repeats the rest of the loop is periodic, so only the steps
-        improved = true;
+    // to the ordering the capped loop would have stopped on are taken.
+    std::unordered_map<uint64_t, int> seen_paths; // path hash -> reversals done when it was reached
+    const auto path_hash = [&path]() {
+        uint64_t h = 1469598103934665603ull; // FNV-1a
+        for (size_t idx : path)
+            h = (h ^ uint64_t(idx)) * 1099511628211ull;
+        return h;
+    };
+    const auto reverse_first_crossing = [&]() {
+        auto [ci, cj] = pn >= grid_min_size ? find_crossing_grid() : find_crossing();
+        if (ci == std::numeric_limits<size_t>::max())
+            return false;
         std::reverse(path.begin() + ci + 1, path.begin() + cj + 1);
+        return true;
+    };
+    seen_paths.emplace(path_hash(), 0);
+    for (int iter = 1; iter <= max_iters && reverse_first_crossing(); ++iter) {
+        improved = true;
+        if (auto [it, inserted] = seen_paths.emplace(path_hash(), iter); !inserted) {
+            for (int steps = (max_iters - iter) % (iter - it->second); steps > 0; --steps)
+                reverse_first_crossing();
+            break;
+        }
     }
     return improved;
 }

src/libslic3r/GCode/SeamPlacer.cpp

@@ -29,6 +29,7 @@
 #include <memory>
 #include <random>
 #include <algorithm>
+#include <limits>
 #include <queue>
 #include <string>
 #include <unordered_map>
@@ -1207,21 +1208,21 @@ std::optional<std::pair<size_t, size_t>> SeamPlacer::find_next_seam_in_layer(
     const size_t layer_idx, const float max_distance,
     const SeamPlacerImpl::SeamComparator &comparator) const {
   using namespace SeamPlacerImpl;
-  std::vector<size_t> nearby_points_indices = find_nearby_points(*layers[layer_idx].points_tree, projected_position,
+  // Find the best nearby point and the nearest one. A layer of a fine relief has tens of thousands of candidates within
-                                                                 max_distance);
+  // the radius, so they are looked at as the search finds them rather than collected into a vector first.
-
+  constexpr size_t none = std::numeric_limits<size_t>::max();
-  if (nearby_points_indices.empty()) {
+  size_t best_nearby_point_index = none;
-    return {};
+  size_t nearest_point_index = none;
+  visit_nearby_points(*layers[layer_idx].points_tree, projected_position, max_distance,
+                      [&layers, &comparator, &projected_position, layer_idx, &best_nearby_point_index, &nearest_point_index]
+                      (size_t nearby_point_index) {
+    if (best_nearby_point_index == none) {
+      // The first point found starts both, as the first of the collected ones did.
+      best_nearby_point_index = nearest_point_index = nearby_point_index;
     }
-
-  size_t best_nearby_point_index = nearby_points_indices[0];
-  size_t nearest_point_index = nearby_points_indices[0];
-
-  // Now find best nearby point, nearest point, and corresponding indices
-  for (const size_t &nearby_point_index : nearby_points_indices) {
     const SeamCandidate &point = layers[layer_idx].points[nearby_point_index];
     if (point.perimeter.finalized) {
-      continue; // skip over finalized perimeters, try to find some that is not finalized
+      return; // skip over finalized perimeters, try to find some that is not finalized
     }
     if (comparator.is_first_better(point, layers[layer_idx].points[best_nearby_point_index],
                                    projected_position.head<2>())
@@ -1233,6 +1234,10 @@ std::optional<std::pair<size_t, size_t>> SeamPlacer::find_next_seam_in_layer(
         || layers[layer_idx].points[nearest_point_index].perimeter.finalized) {
       nearest_point_index = nearby_point_index;
     }
+  });
+
+  if (best_nearby_point_index == none) {
+    return {};
   }
 
   const SeamCandidate &best_nearby_point = layers[layer_idx].points[best_nearby_point_index];

src/libslic3r/KDTreeIndirect.hpp

@@ -318,6 +318,36 @@ std::vector<size_t> find_nearby_points(const KDTreeIndirectType &kdtree, const P
     return visitor.result;
 }
 
+// Visits the points within max_distance of center, in the order find_nearby_points() would collect them, and hands
+// each of them to `visitor_fn` instead of returning them all: a search over a dense set spends more on collecting the
+// points into a vector than on the search itself, and its caller usually keeps only a few of them.
+template<typename KDTreeIndirectType, typename PointType, typename VisitorFn>
+void visit_nearby_points(const KDTreeIndirectType &kdtree, const PointType &center,
+                         const typename KDTreeIndirectType::CoordType &max_distance, VisitorFn visitor_fn)
+{
+    using CoordType = typename KDTreeIndirectType::CoordType;
+
+    struct Visitor {
+        const KDTreeIndirectType &kdtree;
+        const PointType           center;
+        const CoordType           max_distance_squared;
+        VisitorFn                 visitor_fn;
+
+        unsigned int operator()(size_t idx, size_t dimension) {
+            auto dist = CoordType(0);
+            for (size_t i = 0; i < KDTreeIndirectType::NumDimensions; ++i) {
+                CoordType d = center[i] - kdtree.coordinate(idx, i);
+                dist += d * d;
+            }
+            if (dist < max_distance_squared)
+                visitor_fn(idx);
+            return kdtree.descent_mask(center[dimension], max_distance_squared, idx, dimension);
+        }
+    } visitor { kdtree, center, max_distance * max_distance, visitor_fn };
+
+    kdtree.visit(visitor);
+}
+
 template<typename KDTreeIndirectType, typename PointType>
 std::vector<size_t> find_nearby_points(const KDTreeIndirectType &kdtree, const PointType &center,
                                        const typename KDTreeIndirectType::CoordType& max_distance)

src/libslic3r/LayerRegion.cpp

@@ -99,10 +99,11 @@ void LayerRegion::slices_to_fill_surfaces_clipped()
         by_surface[size_t(surface.surface_type)].emplace_back(&surface);
     // Trim surfaces by the fill_boundaries.
     this->fill_surfaces.surfaces.clear();
+    const Polygons fill_boundaries = to_polygons(this->fill_expolygons);
     for (size_t surface_type = 0; surface_type < size_t(stCount); ++ surface_type) {
         const SurfacesPtr &this_surfaces = by_surface[surface_type];
         if (! this_surfaces.empty())
-            this->fill_surfaces.append(intersection_ex(this_surfaces, this->fill_expolygons), SurfaceType(surface_type));
+            this->fill_surfaces.append(intersection_ex_by_piece(to_expolygons(this_surfaces), fill_boundaries), SurfaceType(surface_type));
     }
 }
 

src/libslic3r/MultiMaterialSegmentation.cpp

@@ -22,6 +22,7 @@
 #include "Surface.hpp"
 #include "libslic3r.h"
 
+#include <numeric>
 #include <cmath>
 #include <cstddef>
 #include <list>
@@ -1361,10 +1362,15 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
     }
 #endif // MM_SEGMENTATION_DEBUG_TOP_BOTTOM
 
-    // When the upper surface of an object is occluded, it should no longer be considered the upper surface
+    // When the upper surface of an object is occluded, it should no longer be considered the upper surface.
+    // Every (colour, layer) pair is trimmed on its own, so they all run at once: the painted faces of a finely
+    // textured part project hundreds of thousands of triangles onto one layer, which used to be trimmed serially.
     {
-        for (size_t extruder_idx = 0; extruder_idx < num_facets_states; ++extruder_idx) {
+        const size_t occluded_pairs = num_facets_states * layers.size();
-            for (size_t layer_idx = 0; layer_idx < layers.size(); ++layer_idx) {
+        tbb::parallel_for(tbb::blocked_range<size_t>(0, occluded_pairs), [&](const tbb::blocked_range<size_t> &range) {
+            for (size_t pair_idx = range.begin(); pair_idx < range.end(); ++pair_idx) {
+                const size_t extruder_idx = pair_idx / layers.size();
+                const size_t layer_idx    = pair_idx % layers.size();
                 if (!top_raw[extruder_idx].empty() && !top_raw[extruder_idx][layer_idx].empty() && layer_idx + 1 < layers.size()) {
                     top_raw[extruder_idx][layer_idx] = diff(top_raw[extruder_idx][layer_idx], input_expolygons[layer_idx + 1]);
                 }
@@ -1372,7 +1378,7 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                     bottom_raw[extruder_idx][layer_idx] = diff(bottom_raw[extruder_idx][layer_idx], input_expolygons[layer_idx - 1]);
                 }
             }
-        }
+        });
     }
 
     std::vector<std::vector<ExPolygons>> triangles_by_color_bottom(num_facets_states);
@@ -1430,11 +1436,58 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
         return out;
     };
 
+    // Projects a painted top or bottom face `ex` of layer `layer_idx` onto the shell layers below or above it (in
+    // `shell_layers`, nearest first), one more perimeter in on each, stopping at the first layer where nothing is left.
+    // Only the slices within the deepest offset of `ex` (three times that with the miter joins) decide the result, so the
+    // work is done per tile of `ex`'s ExPolygons on the slices cut to the tile's box grown by that much: the same result, but
+    // each Clipper call stays the size of a tile rather than of a layer cut through a fine relief, and the tiles run in
+    // parallel.
+    const auto project_to_shells = [&input_expolygons](const ExPolygons &ex, size_t layer_idx, const std::vector<size_t> &shell_layers,
+                                                       const LayerColorStat &stat, ShellProjections &dst) {
+        std::vector<float> offsets(shell_layers.size());
+        float              offset = 0.f;
+        for (size_t i = 0; i < shell_layers.size(); ++i) {
+            //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
+            offset -= (stat.extrusion_spacing + stat.extrusion_width);
+            offsets[i] = offset;
+        }
+        if (offsets.empty())
+            return;
+        const coord_t reach = coord_t(std::ceil(DefaultMiterLimit * std::abs(offsets.back()))) + 10 * SCALED_EPSILON;
+        const std::vector<ClipperUtils::ExPolygonsTile> tiles = ClipperUtils::tile_expolygons(ex, 16);
+        // [shell layer][tile]
+        std::vector<std::vector<ExPolygons>> shells(shell_layers.size(), std::vector<ExPolygons>(tiles.size()));
+        tbb::parallel_for(size_t(0), tiles.size(), [&](size_t tile_idx) {
+            const ClipperUtils::ExPolygonsTile &tile = tiles[tile_idx];
+            const BoundingBox                   bbox = tile.bbox.inflated(reach);
+            ExPolygons                          tile_ex;
+            tile_ex.reserve(tile.members.size());
+            for (size_t i : tile.members)
+                tile_ex.emplace_back(ex[i]);
+            Polygons layer_slices_trimmed = ClipperUtils::clip_clipper_polygons_with_subject_bbox(input_expolygons[layer_idx], bbox);
+            for (size_t i = 0; i < shell_layers.size() && ! layer_slices_trimmed.empty(); ++i) {
+                const ExPolygons trimmed = intersection_ex(layer_slices_trimmed, ClipperUtils::clip_clipper_polygons_with_subject_bbox(input_expolygons[shell_layers[i]], bbox));
+                shells[i][tile_idx]  = opening_ex(intersection_ex(tile_ex, offset_ex(trimmed, offsets[i])), stat.small_region_threshold);
+                layer_slices_trimmed = to_polygons(trimmed);
+            }
+        });
+        for (size_t i = 0; i < shell_layers.size(); ++i) {
+            ExPolygons shell;
+            for (ExPolygons &tile_shell : shells[i])
+                append(shell, std::move(tile_shell));
+            if (shell.empty())
+                break;
+            dst.emplace_back(shell_layers[i], std::move(shell));
+        }
+    };
+
     tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&num_layers, &num_facets_states, &layer_color_stat, &top_raw, &triangles_by_color_top,
-                                                                  &throw_on_cancel_callback, &input_expolygons, &bottom_raw, &triangles_by_color_bottom,
+                                                                  &throw_on_cancel_callback, &bottom_raw, &triangles_by_color_bottom, &project_to_shells,
                                                                   &shell_triangles_by_color_top, &shell_triangles_by_color_bottom](const tbb::blocked_range<size_t> &range) {
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++ layer_idx) {
-            for (size_t color_idx = 0; color_idx < num_facets_states; ++color_idx) {
+            // Each colour writes only its own vectors, so the colours run in parallel: a painted top or bottom face
+            // projects onto a single layer, which otherwise did all of its colours on one thread.
+            tbb::parallel_for(size_t(0), size_t(num_facets_states), [&](size_t color_idx) {
                 throw_on_cancel_callback();
                 LayerColorStat stat = layer_color_stat(layer_idx, color_idx);
                 if (std::vector<Polygons> &top = top_raw[color_idx]; ! top.empty() && ! top[layer_idx].empty())
@@ -1443,18 +1496,10 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                         top_ex = opening_ex(top_ex, stat.small_region_threshold);
                         if (! top_ex.empty()) {
                             append(triangles_by_color_top[color_idx][layer_idx], top_ex);
-                            float offset = 0.f;
+                            std::vector<size_t> shell_layers;
-                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
+                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx)
-                            for (int last_idx = int(layer_idx) - 1; last_idx > std::max(int(layer_idx - stat.top_shell_layers), int(0)); --last_idx) {
+                                shell_layers.emplace_back(size_t(last_idx));
-                                //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
+                            project_to_shells(top_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_top[color_idx][layer_idx]);
-                                //offset -= stat.extrusion_width ;
-                                offset -= (stat.extrusion_spacing + stat.extrusion_width);
-                                layer_slices_trimmed = intersection_ex(layer_slices_trimmed, input_expolygons[last_idx]);
-                                ExPolygons last = opening_ex(intersection_ex(top_ex, offset_ex(layer_slices_trimmed, offset)), stat.small_region_threshold);
-                                if (last.empty())
-                                    break;
-                                shell_triangles_by_color_top[color_idx][layer_idx].emplace_back(size_t(last_idx), std::move(last));
-                            }
                         }
                     }
                 if (std::vector<Polygons> &bottom = bottom_raw[color_idx]; ! bottom.empty() && ! bottom[layer_idx].empty())
@@ -1463,21 +1508,13 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                         bottom_ex = opening_ex(bottom_ex, stat.small_region_threshold);
                         if (! bottom_ex.empty()) {
                             append(triangles_by_color_bottom[color_idx][layer_idx], bottom_ex);
-                            float offset = 0.f;
+                            std::vector<size_t> shell_layers;
-                            ExPolygons layer_slices_trimmed = input_expolygons[layer_idx];
+                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx)
-                            for (size_t last_idx = layer_idx + 1; last_idx < std::min(layer_idx + stat.bottom_shell_layers, num_layers); ++last_idx) {
+                                shell_layers.emplace_back(last_idx);
-                                //BBS: offset width should be 2*spacing to avoid too narrow area which has overlap of wall line
+                            project_to_shells(bottom_ex, layer_idx, shell_layers, stat, shell_triangles_by_color_bottom[color_idx][layer_idx]);
-                                //offset -= stat.extrusion_width;
-                                offset -= (stat.extrusion_spacing + stat.extrusion_width);
-                                layer_slices_trimmed = intersection_ex(layer_slices_trimmed, input_expolygons[last_idx]);
-                                ExPolygons last = opening_ex(intersection_ex(bottom_ex, offset_ex(layer_slices_trimmed, offset)), stat.small_region_threshold);
-                                if (last.empty())
-                                    break;
-                                shell_triangles_by_color_bottom[color_idx][layer_idx].emplace_back(last_idx, std::move(last));
-                            }
-                        }
                         }
                     }
+            });
         }
     });
 
@@ -1498,20 +1535,23 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                                                                   &shell_top_by_layer, &shell_bottom_by_layer](const tbb::blocked_range<size_t> &range) {
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++ layer_idx) {
             throw_on_cancel_callback();
-            ExPolygons painted_exploys;
+            // The per-colour unions below are independent of each other, so they run in parallel (a painted top or
-            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx) {
+            // bottom face puts all of its colours on one layer); whatever combines the colours stays in colour order.
+            const auto merge_colour_union = [&](size_t color_idx) {
                 auto &self = triangles_by_color_merged[color_idx][layer_idx];
                 append(self, std::move(triangles_by_color_bottom[color_idx][layer_idx]));
                 append(self, std::move(triangles_by_color_top[color_idx][layer_idx]));
                 self = union_ex(self);
+            };
+            tbb::parallel_for(size_t(0), triangles_by_color_merged.size(), merge_colour_union);
 
-                append(painted_exploys, self);
+            ExPolygons painted_exploys;
-            }
+            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx)
-
+                append(painted_exploys, triangles_by_color_merged[color_idx][layer_idx]);
             painted_exploys = union_ex(painted_exploys);
 
             //BBS: merge the top and bottom shell layers
-            for (size_t color_idx = 0; color_idx < triangles_by_color_merged.size(); ++color_idx) {
+            tbb::parallel_for(size_t(0), triangles_by_color_merged.size(), [&](size_t color_idx) {
                 auto &self = triangles_by_color_merged[color_idx][layer_idx];
 
                 auto top_area    = diff_ex(union_ex(shell_top_by_layer[color_idx][layer_idx]), painted_exploys);
@@ -1520,7 +1560,7 @@ static inline std::vector<std::vector<ExPolygons>> segmentation_top_and_bottom_l
                 append(self, top_area);
                 append(self, bottom_area);
                 self = union_ex(self);
-            }
+            });
             // Trim one region by the other if some of the regions overlap.
             ExPolygons painted_regions;
             for (size_t color_idx = 1; color_idx < triangles_by_color_merged.size(); ++color_idx) {
@@ -1887,7 +1927,69 @@ static void remove_multiple_edges_in_vertices(MMU_Graph &graph, const std::vecto
     }
 }
 
-static std::vector<std::vector<ExPolygons>> merge_segmented_layers(const std::vector<std::vector<ExPolygons>> &segmented_regions,
+
+// Finds the islands (layer ExPolygons) a region piece overlaps. A top or bottom region is projected from the neighbouring
+// layers and may reach past the island it belongs to, or over several islands.
+class IslandLocator
+{
+public:
+    explicit IslandLocator(const ExPolygons &islands) : m_islands(islands)
+    {
+        m_bboxes.reserve(islands.size());
+        for (const ExPolygon &island : islands) {
+            m_bboxes.emplace_back(get_extents(island));
+            m_extent.merge(m_bboxes.back());
+        }
+        if (!m_extent.defined)
+            return;
+        const Point size = m_extent.size();
+        m_cell_w = std::max<coord_t>(1, size.x() / GRID + 1);
+        m_cell_h = std::max<coord_t>(1, size.y() / GRID + 1);
+        m_grid.assign(GRID * GRID, {});
+        for (size_t i = 0; i < m_bboxes.size(); ++i)
+            for_cells(m_bboxes[i], [&](int cell) { m_grid[cell].emplace_back(i); });
+    }
+
+    void find(const ExPolygon &piece, std::vector<size_t> &out) const
+    {
+        out.clear();
+        const BoundingBox bbox = get_extents(piece);
+        if (!m_extent.defined || !m_extent.overlap(bbox))
+            return;
+        for_cells(bbox, [&](int cell) {
+            for (size_t i : m_grid[cell])
+                if (m_bboxes[i].overlap(bbox))
+                    out.emplace_back(i);
+        });
+        sort_remove_duplicates(out);
+        if (out.size() > 1)
+            out.erase(std::remove_if(out.begin(), out.end(), [&](size_t i) {
+                const BoundingBox common(m_bboxes[i].min.cwiseMax(bbox.min), m_bboxes[i].max.cwiseMin(bbox.max));
+                return intersection(ClipperUtils::clip_clipper_polygons_with_subject_bbox(piece, common.inflated(SCALED_EPSILON)),
+                                    ClipperUtils::clip_clipper_polygons_with_subject_bbox(m_islands[i], common.inflated(SCALED_EPSILON))).empty();
+            }), out.end());
+    }
+
+private:
+    static constexpr int GRID = 64;
+    template<typename Fn> void for_cells(const BoundingBox &bb, Fn &&fn) const
+    {
+        const int x0 = std::clamp(int((bb.min.x() - m_extent.min.x()) / m_cell_w), 0, GRID - 1), x1 = std::clamp(int((bb.max.x() - m_extent.min.x()) / m_cell_w), 0, GRID - 1);
+        const int y0 = std::clamp(int((bb.min.y() - m_extent.min.y()) / m_cell_h), 0, GRID - 1), y1 = std::clamp(int((bb.max.y() - m_extent.min.y()) / m_cell_h), 0, GRID - 1);
+        for (int y = y0; y <= y1; ++y)
+            for (int x = x0; x <= x1; ++x)
+                fn(y * GRID + x);
+    }
+
+    const ExPolygons                &m_islands;
+    std::vector<BoundingBox>         m_bboxes;
+    BoundingBox                      m_extent;
+    coord_t                          m_cell_w = 1, m_cell_h = 1;
+    std::vector<std::vector<size_t>> m_grid;
+};
+
+static std::vector<std::vector<ExPolygons>> merge_segmented_layers(const std::vector<ExPolygons>              &input_expolygons,
+                                                                   const std::vector<std::vector<ExPolygons>> &segmented_regions,
                                                                    std::vector<std::vector<ExPolygons>>      &&top_and_bottom_layers,
                                                                    const size_t                                num_facets_states,
                                                                    const std::function<void()>                &throw_on_cancel_callback)
@@ -1898,33 +2000,91 @@ static std::vector<std::vector<ExPolygons>> merge_segmented_layers(const std::ve
     assert(!top_and_bottom_layers.size() || num_facets_states == top_and_bottom_layers.size());
 
     BOOST_LOG_TRIVIAL(debug) << "Print object segmentation - Merging segmented layers in parallel - Begin";
-    tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&segmented_regions, &top_and_bottom_layers, &segmented_regions_merged, &num_facets_states, &throw_on_cancel_callback](const tbb::blocked_range<size_t> &range) {
+    // Every region of a layer is merged together with the regions of the islands it overlaps, and the islands are further
+    // apart than the dimple removal below reaches, so this gives the same result as merging the layer at once. On a layer
+    // cut through a fine relief every region shares thousands of hole contours with every other, and Clipper, splitting
+    // and re-linking one huge polygon over and over, took anything up to half an hour for a layer; per island each operation
+    // stays the size of the island, and the islands run in parallel.
+    tbb::parallel_for(tbb::blocked_range<size_t>(0, num_layers), [&](const tbb::blocked_range<size_t> &range) {
         for (size_t layer_idx = range.begin(); layer_idx < range.end(); ++layer_idx) {
             assert(segmented_regions[layer_idx].size() == num_facets_states);
-            // Zero is skipped because it is the default color of the volume
-            for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id) {
             throw_on_cancel_callback();
-                if (!segmented_regions[layer_idx][extruder_id].empty()) {
+            // Group the islands joined by a region overlapping several of them; the last group takes the regions lying
-                    ExPolygons segmented_regions_trimmed = segmented_regions[layer_idx][extruder_id];
+            // outside every island.
-                    if (!top_and_bottom_layers.empty()) {
+            const ExPolygons   &islands = input_expolygons[layer_idx];
-                        for (const std::vector<ExPolygons> &top_and_bottom_by_extruder : top_and_bottom_layers) {
+            const IslandLocator locator(islands);
-                            if (!top_and_bottom_by_extruder[layer_idx].empty() && !segmented_regions_trimmed.empty()) {
+            std::vector<size_t> parent(islands.size() + 1);
-                                segmented_regions_trimmed = diff_ex(segmented_regions_trimmed, top_and_bottom_by_extruder[layer_idx]);
+            std::iota(parent.begin(), parent.end(), 0);
-                            }
+            const auto root = [&parent](size_t i) {
-                        }
+                while (parent[i] != i)
+                    i = parent[i] = parent[parent[i]];
+                return i;
+            };
+            // Islands of every piece: side regions of colours 1.., then top/bottom regions of colours 0..
+            std::vector<const ExPolygon *> pieces;
+            for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id)
+                for (const ExPolygon &piece : segmented_regions[layer_idx][extruder_id])
+                    pieces.emplace_back(&piece);
+            if (!top_and_bottom_layers.empty())
+                for (size_t color_idx = 0; color_idx < num_facets_states; ++color_idx)
+                    for (const ExPolygon &piece : top_and_bottom_layers[color_idx][layer_idx])
+                        pieces.emplace_back(&piece);
+            std::vector<std::vector<size_t>> overlapped(pieces.size());
+            tbb::parallel_for(size_t(0), pieces.size(), [&](size_t i) { locator.find(*pieces[i], overlapped[i]); });
+            std::vector<size_t> piece_island(pieces.size());
+            for (size_t i = 0; i < pieces.size(); ++i) {
+                piece_island[i] = overlapped[i].empty() ? islands.size() : overlapped[i].front();
+                for (size_t island : overlapped[i])
+                    parent[root(island)] = root(piece_island[i]);
             }
+            std::vector<size_t> bucket_of(parent.size(), size_t(-1));
+            size_t              num_buckets = 0;
+            for (size_t i = 0; i < parent.size(); ++i)
+                if (size_t &b = bucket_of[root(i)]; b == size_t(-1))
+                    b = num_buckets++;
 
-                    segmented_regions_merged[layer_idx][extruder_id - 1] = std::move(segmented_regions_trimmed);
+            // [bucket][colour]
-                }
+            std::vector<std::vector<ExPolygons>> sides(num_buckets, std::vector<ExPolygons>(num_facets_states));
+            std::vector<std::vector<ExPolygons>> tops(num_buckets, std::vector<ExPolygons>(num_facets_states));
+            size_t                               piece_idx = 0;
+            for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id)
+                for (const ExPolygon &piece : segmented_regions[layer_idx][extruder_id])
+                    sides[bucket_of[root(piece_island[piece_idx++])]][extruder_id].emplace_back(piece);
+            if (!top_and_bottom_layers.empty())
+                for (size_t color_idx = 0; color_idx < num_facets_states; ++color_idx)
+                    for (const ExPolygon &piece : top_and_bottom_layers[color_idx][layer_idx])
+                        tops[bucket_of[root(piece_island[piece_idx++])]][color_idx].emplace_back(piece);
 
-                if (!top_and_bottom_layers.empty() && !top_and_bottom_layers[extruder_id][layer_idx].empty()) {
+            // Side regions minus the top/bottom regions of every colour.
-                    bool was_top_and_bottom_empty = segmented_regions_merged[layer_idx][extruder_id - 1].empty();
+            std::vector<std::vector<ExPolygons>> merged(num_buckets, std::vector<ExPolygons>(num_facets_states));
-                    append(segmented_regions_merged[layer_idx][extruder_id - 1], top_and_bottom_layers[extruder_id][layer_idx]);
+            tbb::parallel_for(size_t(0), num_buckets, [&](size_t bucket) {
+                Polygons tops_all;
+                for (const ExPolygons &t : tops[bucket])
+                    polygons_append(tops_all, t);
+                for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id)
+                    if (!sides[bucket][extruder_id].empty())
+                        merged[bucket][extruder_id] = tops_all.empty() ? std::move(sides[bucket][extruder_id]) :
+                                                                         diff_ex_by_piece(sides[bucket][extruder_id], tops_all);
+            });
 
-                    // Remove dimples (#7235) appearing after merging side segmentation of the model with tops and bottoms painted layers.
+            // Then this colour's top/bottom regions, with the dimples removed (#7235) when the layer has side regions left.
-                    if (!was_top_and_bottom_empty)
+            for (size_t extruder_id = 1; extruder_id < num_facets_states; ++extruder_id) {
-                        segmented_regions_merged[layer_idx][extruder_id - 1] = offset2_ex(union_ex(segmented_regions_merged[layer_idx][extruder_id - 1]), float(SCALED_EPSILON), -float(SCALED_EPSILON));
+                if (top_and_bottom_layers.empty() || top_and_bottom_layers[extruder_id][layer_idx].empty()) {
+                    for (size_t bucket = 0; bucket < num_buckets; ++bucket)
+                        append(segmented_regions_merged[layer_idx][extruder_id - 1], std::move(merged[bucket][extruder_id]));
+                    continue;
                 }
+                bool was_top_and_bottom_empty = true;
+                for (size_t bucket = 0; bucket < num_buckets && was_top_and_bottom_empty; ++bucket)
+                    was_top_and_bottom_empty = merged[bucket][extruder_id].empty();
+                tbb::parallel_for(size_t(0), num_buckets, [&](size_t bucket) {
+                    ExPolygons &region = merged[bucket][extruder_id];
+                    append(region, tops[bucket][extruder_id]);
+                    if (!was_top_and_bottom_empty && !region.empty())
+                        region = offset2_ex(union_ex(region), float(SCALED_EPSILON), -float(SCALED_EPSILON));
+                });
+                for (size_t bucket = 0; bucket < num_buckets; ++bucket)
+                    append(segmented_regions_merged[layer_idx][extruder_id - 1], std::move(merged[bucket][extruder_id]));
             }
         }
     }); // end of parallel_for
@@ -2212,16 +2372,56 @@ std::vector<std::vector<ExPolygons>> segmentation_by_painting(const PrintObject
 
                 assert(!color_poly.empty());
                 assert(!color_poly.front().empty());
-                if (has_layer_only_one_color(color_poly)) {
+                // Each island (an ExPolygon with its holes) is segmented on its own. Any point of an island is closer to
-                    // If the whole layer is painted using the same color, it is not needed to construct a Voronoi diagram for the segmentation of this layer.
+                // that island's contours than to any other island's - the way out crosses its own boundary first - so its
-                    segmented_regions[layer_idx][size_t(color_poly.front().front().color)] = input_expolygons[layer_idx];
+                // Voronoi cells, and with them its colour regions, depend on nothing else. A layer cut through a fine relief
-                } else {
+                // has thousands of islands, and one Voronoi diagram over all of them degenerated into overlapping regions
-                    MMU_Graph graph = build_graph(layer_idx, color_poly);
+                // that every boolean afterwards had to untangle. Per island the diagrams stay small and the islands run in
-                    remove_multiple_edges_in_vertices(graph, color_poly);
+                // parallel; an island in a single colour needs no diagram at all.
-                    graph.remove_nodes_with_one_arc();
+                const ExPolygons                      &islands = input_expolygons[layer_idx];
-                    segmented_regions[layer_idx] = extract_colored_segments(graph, num_facets_states);
+                std::vector<std::pair<size_t, size_t>> island_contours(islands.size()); // [first, last) into color_poly
-                    //segmented_regions[layer_idx] = extract_colored_segments(color_poly, num_extruders, layer_idx);
+                {
+                    // The same order EdgeGrid::Grid::create() lists the contours in, and so colorize_contours().
+                    size_t idx = 0;
+                    for (size_t island_idx = 0; island_idx < islands.size(); ++island_idx) {
+                        const size_t first = idx;
+                        if (!islands[island_idx].contour.empty())
+                            ++idx;
+                        for (const Polygon &hole : islands[island_idx].holes)
+                            if (!hole.empty())
+                                ++idx;
+                        island_contours[island_idx] = {first, idx};
                     }
+                    assert(idx == color_poly.size());
+                }
+                std::vector<std::vector<ExPolygons>> island_regions(islands.size());
+                tbb::parallel_for(size_t(0), islands.size(), [&](size_t island_idx) {
+                    const auto [first, last] = island_contours[island_idx];
+                    if (first == last)
+                        return;
+                    const std::vector<ColoredLines> island_poly(color_poly.begin() + first, color_poly.begin() + last);
+                    std::vector<ExPolygons>        &regions = island_regions[island_idx];
+                    if (has_layer_only_one_color(island_poly)) {
+                        regions.assign(num_facets_states, ExPolygons());
+                        regions[size_t(island_poly.front().front().color)].emplace_back(islands[island_idx]);
+                    } else {
+                        MMU_Graph graph = build_graph(layer_idx, island_poly);
+                        remove_multiple_edges_in_vertices(graph, island_poly);
+                        graph.remove_nodes_with_one_arc();
+                        regions = extract_colored_segments(graph, num_facets_states);
+                        // The faces of one colour tile it without overlapping; merged here, where an island is small,
+                        // every later boolean gets a few regions instead of thousands of faces sharing their edges. An
+                        // island with many holes keeps its faces: merged, each colour would be one region with thousands
+                        // of holes, and subtracting from that is far slower than from the faces one at a time.
+                        if (island_poly.size() <= 64)
+                            for (ExPolygons &faces : regions)
+                                if (faces.size() > 1)
+                                    faces = union_ex(faces);
+                    }
+                });
+                for (std::vector<ExPolygons> &regions : island_regions)
+                    for (size_t color_idx = 0; color_idx < regions.size(); ++color_idx)
+                        append(segmented_regions[layer_idx][color_idx], std::move(regions[color_idx]));
 
 #ifdef MM_SEGMENTATION_DEBUG_REGIONS
                 export_regions_to_svg(debug_out_path("3-mm-regions-sides-%d-%d.svg", layer_idx, iRun), segmented_regions[layer_idx], input_expolygons[layer_idx]);
@@ -2244,7 +2444,7 @@ std::vector<std::vector<ExPolygons>> segmentation_by_painting(const PrintObject
         throw_on_cancel_callback();
     }
 
-    std::vector<std::vector<ExPolygons>> segmented_regions_merged = merge_segmented_layers(segmented_regions, std::move(top_and_bottom_layers), num_facets_states, throw_on_cancel_callback);
+    std::vector<std::vector<ExPolygons>> segmented_regions_merged = merge_segmented_layers(input_expolygons, segmented_regions, std::move(top_and_bottom_layers), num_facets_states, throw_on_cancel_callback);
     throw_on_cancel_callback();
 
 #ifdef MM_SEGMENTATION_DEBUG_REGIONS

src/libslic3r/MultiPoint.hpp

@@ -23,11 +23,15 @@ public:
     
     MultiPoint() {}
     MultiPoint(const MultiPoint &other) : points(other.points) {}
-    MultiPoint(MultiPoint &&other) : points(std::move(other.points)) {}
+    MultiPoint(MultiPoint &&other) noexcept : points(std::move(other.points)) {}
     MultiPoint(std::initializer_list<Point> list) : points(list) {}
     explicit MultiPoint(const Points &_points) : points(_points) {}
+    // Without it, the derived classes' move constructors passing std::move(points) here copied them, which
+    // also means a moved-from Polygon or Polyline is now really empty where it used to silently keep its
+    // points: a use-after-move anywhere in the tree that happened to work before now sees nothing.
+    explicit MultiPoint(Points &&_points) noexcept : points(std::move(_points)) {}
     MultiPoint& operator=(const MultiPoint &other) { points = other.points; return *this; }
-    MultiPoint& operator=(MultiPoint &&other) { points = std::move(other.points); return *this; }
+    MultiPoint& operator=(MultiPoint &&other) noexcept { points = std::move(other.points); return *this; }
     virtual ~MultiPoint() = default;
     void scale(double factor);
     void scale(double factor_x, double factor_y);

src/libslic3r/PerimeterGenerator.cpp

@@ -32,6 +32,8 @@
 #include <tuple>
 #include <unordered_set>
 #include <thread>
+#include <tbb/blocked_range.h>
+#include <tbb/parallel_for.h>
 #include <vector>
 #include "libslic3r.h"
 #include <utility>
@@ -2583,7 +2585,22 @@ void PerimeterGenerator::process_arachne()
     const bool only_one_wall_first_layer = this->config->only_one_wall_first_layer && has_bottom_shell_layers(*this->config);
     // we need to process each island separately because we might have different
     // extra perimeters for each one
-    for (const Surface& surface : all_surfaces) {
+    // Each island is independent up to its outputs, so they are generated in parallel - a layer split into thousands
+    // of islands (e.g. by colour painting) otherwise ran on one thread - and the outputs are then committed in the
+    // original island order, which is what the extra overhang perimeters (applied to the last island's loops and to
+    // all fill surfaces so far) depend on.
+    struct ArachneSurfaceResult
+    {
+        ExtrusionEntityCollection loops;
+        bool                      has_loops = false;
+        ExPolygons                infill;
+        ExPolygons                no_overlap;
+    };
+    std::vector<ArachneSurfaceResult> results(all_surfaces.size());
+    tbb::parallel_for(tbb::blocked_range<size_t>(0, all_surfaces.size()), [&](const tbb::blocked_range<size_t> &range) {
+      for (size_t surface_idx = range.begin(); surface_idx < range.end(); ++surface_idx) {
+        const Surface        &surface = all_surfaces[surface_idx];
+        ArachneSurfaceResult &result  = results[surface_idx];
             coord_t bead_width_0 = ext_perimeter_spacing;
             // detect how many perimeters must be generated for this island
             int loop_number = this->config->wall_loops + surface.extra_perimeters - 1; // 0-indexed loops
@@ -2765,7 +2782,7 @@ void PerimeterGenerator::process_arachne()
                 static int iRun = 0;
                 export_perimeters_to_svg(debug_out_path("arachne-perimeters-%d-%d.svg", layer_id, iRun++), to_polygons(last), perimeters, union_ex(wallToolPaths.getInnerContour()));
             }
-#endif
+    #endif
 
             // All closed ExtrusionLine should have the same the first and the last point.
             // But in rare cases, Arachne produce ExtrusionLine marked as closed but without
@@ -2893,10 +2910,10 @@ void PerimeterGenerator::process_arachne()
                     // Get searching thresholds. For an external perimeter we take the external perimeter spacing/2 plus the internal perimeter spacing/2 and expand by the factor
                     // rounding errors. When precise wall is enabled, the external perimeter full spacing is used.
                     coord_t threshold_external = (apply_precise_outer_wall)
-                    // Precise outer wall ⇒ use “full external spacing”
+                        // Precise outer wall: use the full external spacing
                         ? ( this->ext_perimeter_flow.scaled_spacing()
                             + this->perimeter_flow.scaled_spacing()/2.0 )
-                    // Normal ⇒ half ext spacing + half int spacing
+                        // Normal: half ext spacing plus half int spacing
                         : ( this->ext_perimeter_flow.scaled_spacing()/2.0
                             + this->perimeter_flow.scaled_spacing()/2.0 );
                 
@@ -2986,7 +3003,8 @@ void PerimeterGenerator::process_arachne()
                                         this->config->overhang_reverse_internal_only);
                 }
                 defer_unsupported_loops(*this, extrusion_coll);
-            this->loops->append(extrusion_coll);
+                result.loops     = std::move(extrusion_coll);
+                result.has_loops = true;
             }
 
             const coord_t spacing = (perimeters.size() == 1) ? ext_perimeter_spacing2 : perimeter_spacing;
@@ -3029,9 +3047,7 @@ void PerimeterGenerator::process_arachne()
             if (!top_expolygons.empty()) {
                 infill_exp = union_ex(infill_exp, offset_ex(top_expolygons, double(top_inset)));
             }
-        this->fill_surfaces->append(infill_exp, stInternal);
+            result.infill = std::move(infill_exp);
-
-        apply_extra_perimeters(infill_exp);
 
             // BBS: get the no-overlap infill expolygons
             {
@@ -3042,9 +3058,18 @@ void PerimeterGenerator::process_arachne()
                     float(+min_perimeter_infill_spacing / 2.));
                 if (!top_expolygons.empty())
                     polyWithoutOverlap = union_ex(polyWithoutOverlap, top_expolygons);
-            this->fill_no_overlap->insert(this->fill_no_overlap->end(), polyWithoutOverlap.begin(), polyWithoutOverlap.end());
+                result.no_overlap = std::move(polyWithoutOverlap);
             }
       }
+    });
+    for (ArachneSurfaceResult &result : results) {
+        if (result.has_loops)
+            // Moved, not copied: append(const ExtrusionEntity &) clones the whole wall tree of the island.
+            this->loops->append(std::move(result.loops));
+        this->fill_surfaces->append(result.infill, stInternal);
+        apply_extra_perimeters(result.infill);
+        append(*this->fill_no_overlap, std::move(result.no_overlap));
+    }
 }
 
 bool PerimeterGeneratorLoop::is_internal_contour() const

src/libslic3r/Polygon.hpp

@@ -34,7 +34,7 @@ public:
     explicit Polygon(const Points &points) : MultiPoint(points) {}
 	Polygon(std::initializer_list<Point> points) : MultiPoint(points) {}
     Polygon(const Polygon &other) : MultiPoint(other.points) {}
-    Polygon(Polygon &&other) : MultiPoint(std::move(other.points)) {}
+    Polygon(Polygon &&other) noexcept : MultiPoint(std::move(other.points)) {}
 	static Polygon new_scale(const std::vector<Vec2d> &points) { 
         Polygon pgn;
         pgn.points.reserve(points.size());
@@ -43,7 +43,7 @@ public:
 		return pgn;
 	}
     Polygon& operator=(const Polygon &other) { points = other.points; return *this; }
-    Polygon& operator=(Polygon &&other) { points = std::move(other.points); return *this; }
+    Polygon& operator=(Polygon &&other) noexcept { points = std::move(other.points); return *this; }
 
     Point& operator[](Points::size_type idx) { return this->points[idx]; }
     const Point& operator[](Points::size_type idx) const { return this->points[idx]; }

src/libslic3r/Polyline.hpp

@@ -26,7 +26,7 @@ class Polyline : public MultiPoint {
 public:
     Polyline() {};
     Polyline(const Polyline& other) : MultiPoint(other.points), fitting_result(other.fitting_result) {}
-    Polyline(Polyline &&other) : MultiPoint(std::move(other.points)), fitting_result(std::move(other.fitting_result))  {}
+    Polyline(Polyline &&other) noexcept : MultiPoint(std::move(other.points)), fitting_result(std::move(other.fitting_result))  {}
     Polyline(std::initializer_list<Point> list) : MultiPoint(list) { 
         fitting_result.clear();
     }
@@ -47,7 +47,7 @@ public:
         fitting_result = other.fitting_result;
         return *this;
     }
-    Polyline& operator=(Polyline&& other) {
+    Polyline& operator=(Polyline&& other) noexcept {
         points = std::move(other.points);
         fitting_result = std::move(other.fitting_result);
         return *this;

src/libslic3r/Preset.cpp

@@ -797,7 +797,7 @@ bool Preset::save(DynamicPrintConfig* parent_config)
         {
             ConfigOption *opt_src = config.option(option);
             ConfigOption *opt_dst = temp_config.option(option, true);
-            if (opt_dst->is_scalar() || !(opt_dst->nullable()))
+            if (opt_dst->is_scalar() || !(opt_dst->nullable()) || is_filament_extruder_override_key(option))
                 opt_dst->set(opt_src);
             else {
                 ConfigOptionVectorBase* opt_vec_src = static_cast<ConfigOptionVectorBase*>(opt_src);
@@ -2132,7 +2132,7 @@ Preset* PresetCollection::get_preset_differed_for_save(Preset& preset)
         {
             ConfigOption *opt_src = preset.config.option(option);
             ConfigOption *opt_dst = temp_config.option(option, true);
-            if (opt_dst->is_scalar() || !(opt_dst->nullable()))
+            if (opt_dst->is_scalar() || !(opt_dst->nullable()) || is_filament_extruder_override_key(option))
                 opt_dst->set(opt_src);
             else {
                 ConfigOptionVectorBase* opt_vec_src = static_cast<ConfigOptionVectorBase*>(opt_src);
@@ -2199,9 +2199,12 @@ int PresetCollection::get_differed_values_to_update(Preset& preset, std::map<std
         // option's non-nil default (e.g. filament_retract_before_wipe -> 100%), silently
         // resurrecting an override the user turned off. See GitHub issue on Retract Before Wipe.
         if (m_type == Preset::TYPE_FILAMENT) {
-            for (const std::string& opt_key : filament_extruder_override_keys) {
+            for (const std::string& opt_key : preset.config.keys()) {
-                if (key_values.count(opt_key))
+                if (!is_filament_extruder_override_key(opt_key) || key_values.count(opt_key))
-                    continue; // already carried by the diff
+                    continue; // not an override, or already carried by the diff
+                const ConfigOptionDef *def = print_config_def.get(opt_key);
+                if (def == nullptr || !def->default_value || def->default_value->is_nil())
+                    continue; // the option's default is nil too, so an absent key cannot come back as a value
                 const auto* opt_vec = dynamic_cast<const ConfigOptionVectorBase*>(preset.config.option(opt_key));
                 if (opt_vec == nullptr)
                     continue;

src/libslic3r/PrintConfig.cpp

@@ -119,12 +119,18 @@ const std::vector<std::string> filament_extruder_override_keys = {
 };
 
 // Some filament override parameters are generated from filament_extruder_override_keys,
-// while filament_retract_length_nc is defined separately. Keep the generator list
+// while filament_retract_length_nc and the ironing overrides are defined separately.
-// unchanged and use this helper for behavior checks that need the full override set.
+// Keep the generator list unchanged and use this helper for behavior checks that need
+// the full override set. A nil in one of these keys means the override is disabled, so
+// child presets store and load it verbatim instead of treating nil as "inherit".
 bool is_filament_extruder_override_key(const std::string &opt_key)
 {
     return std::find(filament_extruder_override_keys.begin(), filament_extruder_override_keys.end(), opt_key) != filament_extruder_override_keys.end() ||
-           opt_key == "filament_retract_length_nc";
+           opt_key == "filament_retract_length_nc" ||
+           opt_key == "filament_ironing_flow" ||
+           opt_key == "filament_ironing_spacing" ||
+           opt_key == "filament_ironing_inset" ||
+           opt_key == "filament_ironing_speed";
 }
 
 size_t get_extruder_index(const GCodeConfig& config, unsigned int filament_id)
@@ -12272,7 +12278,8 @@ void DynamicPrintConfig::update_diff_values_to_child_config(DynamicPrintConfig&
                     opt_src->set(opt_target);
                 }
                 else
-                    opt_vec_src->set_only_diff(opt_vec_dest, variant_index, stride);
+                    // An override's nil means "disabled" and is the child's value; every other nil column inherits.
+                    opt_vec_src->set_only_diff(opt_vec_dest, variant_index, stride, is_filament_extruder_override_key(opt));
             }
         }
     }

src/libslic3r/PrintObject.cpp

@@ -50,6 +50,7 @@
 #include <cstdlib>
 #include <cstdint>
 #include <float.h>
+#include <array>
 #include <functional>
 #include <ios>
 #include <iomanip>
@@ -76,6 +77,7 @@
 #include <Eigen/Core>
 
 #include <tbb/parallel_for.h>
+#include <tbb/parallel_invoke.h>
 #include <tbb/spin_mutex.h>
 #include <tbb/concurrent_unordered_set.h>
 
@@ -1930,7 +1932,9 @@ void PrintObject::detect_surfaces_type()
     bool interface_shells = ! spiral_mode && m_config.interface_shells.value;
     size_t num_layers     = spiral_mode ? std::min(size_t(this->printing_region(0).config().bottom_shell_layers), m_layers.size()) : m_layers.size();
 
-    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
+    // The regions of a layer do not see each other here, and a layer cut through a fine relief takes far longer than the
+    // others, so the regions run next to each other instead of one after another, each still over all layers.
+    tbb::parallel_for(size_t(0), this->num_printing_regions(), [&](size_t region_id) {
         BOOST_LOG_TRIVIAL(debug) << "Detecting solid surfaces for region " << region_id << " in parallel - start";
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
         for (Layer *layer : m_layers)
@@ -1988,7 +1992,7 @@ void PrintObject::detect_surfaces_type()
                     if (upper_layer) {
                         ExPolygons upper_slices = interface_shells ?
                             diff_ex(layerm_slices_surfaces, upper_layer->m_regions[region_id]->slices.surfaces, ApplySafetyOffset::Yes) :
-                            diff_ex(layerm_slices_surfaces, upper_layer->lslices, ApplySafetyOffset::Yes);
+                            diff_ex_by_piece(layerm_slices_surfaces, to_polygons(upper_layer->lslices), ApplySafetyOffset::Yes);
                         surfaces_append(top, opening_ex(upper_slices, offset), stTop);
                     } else {
                         // if no upper layer, all surfaces of this one are solid
@@ -2014,7 +2018,7 @@ void PrintObject::detect_surfaces_type()
                         surfaces_append(
                             bottom,
                             opening_ex(
-                                diff_ex(layerm_slices_surfaces, lower_layer->lslices, ApplySafetyOffset::Yes),
+                                diff_ex_by_piece(layerm_slices_surfaces, to_polygons(lower_layer->lslices), ApplySafetyOffset::Yes),
                                 offset),
                             surface_type_bottom_other);
                         // if user requested internal shells, we need to identify surfaces
@@ -2045,34 +2049,44 @@ void PrintObject::detect_surfaces_type()
                     // and top surfaces; let's do an intersection to discover them and consider them
                     // as bottom surfaces (to allow for bridge detection)
                     if (! top.empty() && ! bottom.empty()) {
-                        const auto cracks = intersection_ex(top, bottom);
+                        const auto cracks = intersection_ex_by_piece(to_expolygons(top), to_polygons(bottom));
                         if (!cracks.empty()) {
                             if (lower_layer) { // Only detect small cracks for non-first layer, because first layer should always be bottom
                                 const float small_crack_threshold = -layerm->flow(frExternalPerimeter).scaled_width() * 1.5;
                                 
+                                // Only the bottom surfaces near a crack can take part: one that contains it must contain its box,
+                                // and one whose box misses the grown crack is left unchanged by removing it. A layer cut through
+                                // a fine relief has thousands of both, which made this loop quadratic.
                                 for (const auto& crack : cracks) {
                                     if (offset_ex(crack, small_crack_threshold).empty()) {
                                         // For small cracks, if it's part of a large bottom surface, then it should be added to bottom as well
-                                        if (std::any_of(bottom.begin(), bottom.end(), [&crack, small_crack_threshold](const Surface& s) {
+                                        const BoundingBox crack_bbox = get_extents(crack);
+                                        if (std::any_of(bottom.begin(), bottom.end(), [&crack, &crack_bbox, small_crack_threshold](const Surface& s) {
                                                 const auto& se = s.expolygon;
-                                                return diff_ex(crack, se, ApplySafetyOffset::Yes).empty()
+                                                return get_extents(se).inflated(SCALED_EPSILON).contains(crack_bbox)
+                                                    && diff_ex(crack, se, ApplySafetyOffset::Yes).empty()
                                                     && se.area() > crack.area() * 2
                                                     && !offset_ex(diff_ex(se, crack), small_crack_threshold).empty();
                                         })) continue;
 
                                         // Crack too small, leave it as part of the top surface, remove it from bottom surfaces
+                                        const ExPolygons  grown_crack = offset_ex(crack, -small_crack_threshold);
+                                        const BoundingBox grown_bbox  = get_extents(grown_crack);
                                         Surfaces bot_tmp;
                                         for (auto& b : bottom) {
-                                            surfaces_append(bot_tmp, diff_ex(b.expolygon, offset_ex(crack, -small_crack_threshold)), b.surface_type);
+                                            if (get_extents(b.expolygon).overlap(grown_bbox))
+                                                surfaces_append(bot_tmp, diff_ex(b.expolygon, grown_crack), b.surface_type);
+                                            else
+                                                bot_tmp.emplace_back(std::move(b));
                                         }
                                         bottom = std::move(bot_tmp);
                                     }
                                 }
                             }
 
-                            Polygons top_polygons = to_polygons(std::move(top));
+                            ExPolygons top_expolygons = to_expolygons(std::move(top));
                             top.clear();
-                            surfaces_append(top, diff_ex(top_polygons, bottom), stTop);
+                            surfaces_append(top, diff_ex_by_piece(top_expolygons, to_polygons(bottom)), stTop);
                         }
                     }
 
@@ -2163,7 +2177,7 @@ void PrintObject::detect_surfaces_type()
                     {
                         Polygons topbottom = to_polygons(top);
                         polygons_append(topbottom, to_polygons(bottom));
-                        surfaces_append(surfaces_out, diff_ex(surfaces_prev_expolys, topbottom), stInternal);
+                        surfaces_append(surfaces_out, diff_ex_by_piece(surfaces_prev_expolys, topbottom), stInternal);
                     }
 
                     surfaces_append(surfaces_out, std::move(top));
@@ -2340,29 +2354,31 @@ void PrintObject::detect_surfaces_type()
                 }
             }
             );
-            // ==============================================================================================================
-            // === ORCA: Interim workaround - for now the new stInternalAfterExternalBridge surfaace is re-classified  ==============
-            // === back to a bottom bridge. As a starting point, this improves bridging reliability as it extrudes ==========
-            // === two external bridge layers. However, TODO: Implement a new surface type throughout the codebase ==========
-            // ==============================================================================================================
-            for (size_t region_id = 0; region_id < this->num_printing_regions(); ++region_id) {
-                tbb::parallel_for( tbb::blocked_range<size_t>(0, m_layers.size()), [this, region_id](const tbb::blocked_range<size_t> &range) {
-                    for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++idx_layer) {
-                        Surfaces &surfs = m_layers[idx_layer]->m_regions[region_id]->slices.surfaces;
-                        for (Surface &s : surfs) {
-                            if (s.surface_type == stInternalAfterExternalBridge) {
-                                s.surface_type = stBottomBridge;
-                            }
-                        }
-                    }
-                }
-              );
-            }
         }
         // ==============================================================================================================
         // === ORCA: End of second external bridge layer changes  =======================================================
         // ==============================================================================================================
         
+    }); // for each this->print->region_count
+
+    // ==============================================================================================================
+    // === ORCA: Interim workaround - for now the new stInternalAfterExternalBridge surfaace is re-classified  ==============
+    // === back to a bottom bridge. As a starting point, this improves bridging reliability as it extrudes ==========
+    // === two external bridge layers. However, TODO: Implement a new surface type throughout the codebase ==========
+    // ==============================================================================================================
+    // Once all the regions have their second bridge layer, and before their slices are trimmed into fill surfaces below.
+    if ((this->config().enable_extra_bridge_layer.value == eblApplyToAll) || (this->config().enable_extra_bridge_layer.value == eblExternalBridgeOnly)) {
+        tbb::parallel_for(tbb::blocked_range<size_t>(0, m_layers.size()), [this](const tbb::blocked_range<size_t> &range) {
+            for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++idx_layer)
+                for (LayerRegion *layerm : m_layers[idx_layer]->regions())
+                    for (Surface &s : layerm->slices.surfaces)
+                        if (s.surface_type == stInternalAfterExternalBridge)
+                            s.surface_type = stBottomBridge;
+        });
+        m_print->throw_if_canceled();
+    }
+
+    tbb::parallel_for(size_t(0), this->num_printing_regions(), [&](size_t region_id) {
         BOOST_LOG_TRIVIAL(debug) << "Detecting solid surfaces for region " << region_id << " - clipping in parallel - start";
         // Fill in layerm->fill_surfaces by trimming the layerm->slices by the cummulative layerm->fill_surfaces.
         tbb::parallel_for(
@@ -2379,7 +2395,7 @@ void PrintObject::detect_surfaces_type()
             });
         m_print->throw_if_canceled();
         BOOST_LOG_TRIVIAL(debug) << "Detecting solid surfaces for region " << region_id << " - clipping in parallel - end";
-    } // for each this->print->region_count
+    });
 
     // Mark the object to have the region slices classified (typed, which also means they are split based on whether they are supported, bridging, top layers etc.)
     m_typed_slices = true;
@@ -2446,8 +2462,10 @@ void PrintObject::process_external_surfaces()
 	    BOOST_LOG_TRIVIAL(debug) << "Collecting surfaces covered with extrusions in parallel - end";
 	}
 
-	for (size_t region_id = 0; region_id < this->num_printing_regions(); ++region_id) {
+    BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces in parallel - start";
-        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - start";
+    // The regions of a layer do not see each other here, and a layer cut through a fine relief takes far longer than the
+    // others, so the regions run next to each other instead of one after another, each still over all layers.
+    tbb::parallel_for(size_t(0), this->num_printing_regions(), [this, &surfaces_covered](size_t region_id) {
         tbb::parallel_for(
             tbb::blocked_range<size_t>(0, m_layers.size()),
             [this, &surfaces_covered, region_id](const tbb::blocked_range<size_t>& range) {
@@ -2462,9 +2480,9 @@ void PrintObject::process_external_surfaces()
                 }
             }
         );
+    });
     m_print->throw_if_canceled();
-        BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces for region " << region_id << " in parallel - end";
+    BOOST_LOG_TRIVIAL(debug) << "Processing external surfaces in parallel - end";
-    }
 }
 
 void PrintObject::discover_vertical_shells()
@@ -2503,10 +2521,10 @@ void PrintObject::discover_vertical_shells()
             // The "ensure vertical wall thickness" feature is not applicable to any of the regions. Quit.
             return;
         BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells in parallel - start : cache top / bottom";
-        //FIXME Improve the heuristics for a grain size.
+        // One layer per task: on a layer cut through a fine relief the unions below take far longer than elsewhere, and a
-        size_t grain_size = std::max(num_layers / 16, size_t(1));
+        // few such layers next to each other must not end up in one task.
         tbb::parallel_for(
-            tbb::blocked_range<size_t>(0, num_layers, grain_size),
+            tbb::blocked_range<size_t>(0, num_layers, 1),
             [this, &cache_top_botom_regions](const tbb::blocked_range<size_t>& range) {
                 const std::initializer_list<SurfaceType> surfaces_bottom { stBottom, stBottomBridge };
                 const size_t num_regions = this->num_printing_regions();
@@ -2514,26 +2532,38 @@ void PrintObject::discover_vertical_shells()
                     m_print->throw_if_canceled();
                     const Layer                      &layer = *m_layers[idx_layer];
                     DiscoverVerticalShellsCacheEntry &cache = cache_top_botom_regions[idx_layer];
-                    // Simulate single set of perimeters over all merged regions.
+                    const auto top_bottom_expansion = [&layer](size_t region_id) {
-                    float                             perimeter_offset = 0.f;
+                        return float(layer.m_regions[region_id]->flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
-                    float                             perimeter_min_spacing = FLT_MAX;
+                    };
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     static size_t debug_idx = 0;
                     ++ debug_idx;
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-                    for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
+                    // The top surfaces, the bottom surfaces and the holes are independent of each other.
-                        LayerRegion &layerm               = *layer.m_regions[region_id];
+                    tbb::parallel_invoke(
-                        float        top_bottom_expansion = float(layerm.flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
+                        [&]() {
-                        // Top surfaces.
+                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
-                        append(cache.top_surfaces, offset(layerm.slices.filter_by_type(stTop), top_bottom_expansion));
+                                append(cache.top_surfaces, offset(layer.m_regions[region_id]->slices.filter_by_type(stTop), top_bottom_expansion(region_id)));
 //                              append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
-                        // Bottom surfaces.
+                            // Save some computing time by reducing the number of polygons.
-                        append(cache.bottom_surfaces, offset(layerm.slices.filter_by_types(surfaces_bottom), top_bottom_expansion));
+                            cache.top_surfaces = union_(cache.top_surfaces);
+                        },
+                        [&]() {
+                            for (size_t region_id = 0; region_id < num_regions; ++ region_id)
+                                append(cache.bottom_surfaces, offset(layer.m_regions[region_id]->slices.filter_by_types(surfaces_bottom), top_bottom_expansion(region_id)));
 //                              append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
+                            cache.bottom_surfaces = union_(cache.bottom_surfaces);
+                        },
+                        [&]() {
+                            // Simulate single set of perimeters over all merged regions.
+                            float perimeter_offset      = 0.f;
+                            float perimeter_min_spacing = FLT_MAX;
+                            for (size_t region_id = 0; region_id < num_regions; ++ region_id) {
+                                const LayerRegion &layerm = *layer.m_regions[region_id];
                                 // Calculate the maximum perimeter offset as if the slice was extruded with a single extruder only.
                                 // First find the maxium number of perimeters per region slice.
                                 unsigned int perimeters = 0;
-                        for (Surface &s : layerm.slices.surfaces)
+                                for (const Surface &s : layerm.slices.surfaces)
                                     perimeters = std::max<unsigned int>(perimeters, s.extra_perimeters);
                                 perimeters += layerm.region().config().wall_loops.value;
                                 // Then calculate the infill offset.
@@ -2546,9 +2576,6 @@ void PrintObject::discover_vertical_shells()
                                 }
                                 polygons_append(cache.holes, to_polygons(layerm.fill_expolygons));
                             }
-                    // Save some computing time by reducing the number of polygons.
-                    cache.top_surfaces    = union_(cache.top_surfaces);
-                    cache.bottom_surfaces = union_(cache.bottom_surfaces);
                             // For a multi-material print, simulate perimeter / infill split as if only a single extruder has been used for the whole print.
                             if (perimeter_offset > 0.) {
                                 // The layer.lslices are forced to merge by expanding them first.
@@ -2564,106 +2591,32 @@ void PrintObject::discover_vertical_shells()
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
                             }
                             cache.holes = union_(cache.holes);
+                        });
                 }
             });
         m_print->throw_if_canceled();
         BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells in parallel - end : cache top / bottom";
     }
 
-    for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
+    // With one top/bottom cache for all regions, the shell and hole accumulation in the loop below depends on nothing
-        const PrintRegion &region = this->printing_region(region_id);
+    // region-specific but the shell settings and the external perimeter spacing, so a region sharing them with an earlier
-        if (region.config().ensure_vertical_shell_thickness.value != evstAll )
+    // one reuses its result instead of repeating it: that accumulation is a union over several layers of top/bottom
-            // This region will be handled by discover_horizontal_shells().
+    // surfaces, and a multi-material print has a region per filament.
-            continue;
+    using AccumulationKey = std::array<double, 5>;
-
+    struct ShellAccumulation
-        //FIXME Improve the heuristics for a grain size.
+    {
-        size_t grain_size = std::max(num_layers / 16, size_t(1));
+        AccumulationKey key;
-
-        if (! top_bottom_surfaces_all_regions) {
-            // This is either a single material print, or a multi-material print and interface_shells are enabled, meaning that the vertical shell thickness
-            // is calculated over a single material.
-            BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells for region " << region_id << " in parallel - start : cache top / bottom";
-            tbb::parallel_for(
-                tbb::blocked_range<size_t>(0, num_layers, grain_size),
-                [this, region_id, &cache_top_botom_regions](const tbb::blocked_range<size_t>& range) {
-                    const std::initializer_list<SurfaceType> surfaces_bottom { stBottom, stBottomBridge };
-                    for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++ idx_layer) {
-                        m_print->throw_if_canceled();
-                        Layer       &layer                = *m_layers[idx_layer];
-                        LayerRegion &layerm               = *layer.m_regions[region_id];
-                        float        top_bottom_expansion = float(layerm.flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
-                        // Top surfaces.
-                        auto &cache = cache_top_botom_regions[idx_layer];
-                        cache.top_surfaces = offset(layerm.slices.filter_by_type(stTop), top_bottom_expansion);
-//                        append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
-                        // Bottom surfaces.
-                        cache.bottom_surfaces = offset(layerm.slices.filter_by_types(surfaces_bottom), top_bottom_expansion);
-//                        append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
-                        // Holes over all regions. Only collect them once, they are valid for all region_id iterations.
-                        if (cache.holes.empty()) {
-                            for (size_t region_id = 0; region_id < layer.regions().size(); ++ region_id)
-                                polygons_append(cache.holes, to_polygons(layer.regions()[region_id]->fill_expolygons));
-                        }
-                    }
-                });
-            m_print->throw_if_canceled();
-            BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells for region " << region_id << " in parallel - end : cache top / bottom";
-        }
-
-        BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells for region " << region_id << " in parallel - start : ensure vertical wall thickness";
-        grain_size = 1;
-        tbb::parallel_for(
-            tbb::blocked_range<size_t>(0, num_layers, grain_size),
-            [this, region_id, &cache_top_botom_regions]
-            (const tbb::blocked_range<size_t>& range) {
-                // printf("discover_vertical_shells from %d to %d\n", range.begin(), range.end());
-                for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++ idx_layer) {
-                    m_print->throw_if_canceled();
-#ifdef SLIC3R_DEBUG_SLICE_PROCESSING
-        			static size_t debug_idx = 0;
-        			++ debug_idx;
-#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-
-                    Layer       	        *layer          = m_layers[idx_layer];
-                    LayerRegion 	        *layerm         = layer->m_regions[region_id];
-                    const PrintRegionConfig &region_config  = layerm->region().config();
-
-#ifdef SLIC3R_DEBUG_SLICE_PROCESSING
-                    layerm->export_region_slices_to_svg_debug("3_discover_vertical_shells-initial");
-                    layerm->export_region_fill_surfaces_to_svg_debug("3_discover_vertical_shells-initial");
-#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-
-                    Flow         solid_infill_flow   = layerm->flow(frSolidInfill);
-                    coord_t      infill_line_spacing = solid_infill_flow.scaled_spacing();
-                    // Find a union of perimeters below / above this surface to guarantee a minimum shell thickness.
         Polygons        shell;
         Polygons        holes;
-#ifdef SLIC3R_DEBUG_SLICE_PROCESSING
+    };
-                    ExPolygons shell_ex;
+    const auto accumulation_key = [](const PrintRegionConfig &region_config, const LayerRegion *layerm) {
-#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
+        return AccumulationKey{ double(region_config.top_shell_layers.value), region_config.top_shell_thickness.value,
-                    float min_perimeter_infill_spacing = float(infill_line_spacing) * 1.05f;
+                                double(region_config.bottom_shell_layers.value), region_config.bottom_shell_thickness.value,
-#if 0
+                                double(layerm->flow(frExternalPerimeter).scaled_spacing()) };
-// #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
+    };
-                    {
+    const auto accumulate_shell = [this, &cache_top_botom_regions](size_t idx_layer, const PrintRegionConfig &region_config,
-        				Slic3r::SVG svg_cummulative(debug_out_path("discover_vertical_shells-perimeters-before-union-run%d.svg", debug_idx), this->bounding_box());
+                                                                   const LayerRegion *layerm, Polygons &shell, Polygons &holes) {
-                        for (int n = (int)idx_layer - n_extra_bottom_layers; n <= (int)idx_layer + n_extra_top_layers; ++ n) {
+        const Layer *layer = m_layers[idx_layer];
-                            if (n < 0 || n >= (int)m_layers.size())
-                                continue;
-                            ExPolygons &expolys = m_layers[n]->perimeter_expolygons;
-                            for (size_t i = 0; i < expolys.size(); ++ i) {
-        						Slic3r::SVG svg(debug_out_path("discover_vertical_shells-perimeters-before-union-run%d-layer%d-expoly%d.svg", debug_idx, n, i), get_extents(expolys[i]));
-                                svg.draw(expolys[i]);
-                                svg.draw_outline(expolys[i].contour, "black", scale_(0.05));
-                                svg.draw_outline(expolys[i].holes, "blue", scale_(0.05));
-                                svg.Close();
-
-                                svg_cummulative.draw(expolys[i]);
-                                svg_cummulative.draw_outline(expolys[i].contour, "black", scale_(0.05));
-                                svg_cummulative.draw_outline(expolys[i].holes, "blue", scale_(0.05));
-                            }
-                        }
-                    }
-#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
     			        polygons_append(holes, cache_top_botom_regions[idx_layer].holes);
                         auto combine_holes = [&holes](const Polygons &holes2) {
                             if (holes.empty() || holes2.empty())
@@ -2738,6 +2691,141 @@ void PrintObject::discover_vertical_shells()
                                     (i > ibottom || bottom_z - m_layers[i]->print_z < region_config.bottom_shell_thickness - EPSILON))
                                     combine_holes(cache_top_botom_regions[i].holes);
     	                }
+    };
+    std::vector<std::vector<ShellAccumulation>> shell_accumulations(top_bottom_surfaces_all_regions ? num_layers : 0);
+    if (! shell_accumulations.empty()) {
+        // Every (layer, key) pair is accumulated once, before the regions, so that nothing in the loop below is shared
+        // between them and they can run next to each other.
+        std::vector<std::array<size_t, 3>> todo; // layer, its slot, a region holding the key
+        for (size_t idx_layer = 0; idx_layer < num_layers; ++ idx_layer) {
+            std::vector<ShellAccumulation> &accumulations = shell_accumulations[idx_layer];
+            for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id) {
+                if (this->printing_region(region_id).config().ensure_vertical_shell_thickness.value != evstAll)
+                    continue;
+                const LayerRegion    *layerm = m_layers[idx_layer]->m_regions[region_id];
+                const AccumulationKey key    = accumulation_key(layerm->region().config(), layerm);
+                if (std::none_of(accumulations.begin(), accumulations.end(), [&key](const ShellAccumulation &a) { return a.key == key; })) {
+                    todo.push_back({ idx_layer, accumulations.size(), region_id });
+                    accumulations.push_back({ key, {}, {} });
+                }
+            }
+        }
+        tbb::parallel_for(size_t(0), todo.size(), [this, &todo, &shell_accumulations, &accumulate_shell](size_t i) {
+            m_print->throw_if_canceled();
+            const LayerRegion *layerm = m_layers[todo[i][0]]->m_regions[todo[i][2]];
+            ShellAccumulation &out    = shell_accumulations[todo[i][0]][todo[i][1]];
+            accumulate_shell(todo[i][0], layerm->region().config(), layerm, out.shell, out.holes);
+        });
+        m_print->throw_if_canceled();
+    }
+
+    const auto process_region = [&](size_t region_id) {
+        const PrintRegion &region = this->printing_region(region_id);
+        if (region.config().ensure_vertical_shell_thickness.value != evstAll )
+            // This region will be handled by discover_horizontal_shells().
+            return;
+
+        //FIXME Improve the heuristics for a grain size.
+        size_t grain_size = std::max(num_layers / 16, size_t(1));
+
+        if (! top_bottom_surfaces_all_regions) {
+            // This is either a single material print, or a multi-material print and interface_shells are enabled, meaning that the vertical shell thickness
+            // is calculated over a single material.
+            BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells for region " << region_id << " in parallel - start : cache top / bottom";
+            tbb::parallel_for(
+                tbb::blocked_range<size_t>(0, num_layers, grain_size),
+                [this, region_id, &cache_top_botom_regions](const tbb::blocked_range<size_t>& range) {
+                    const std::initializer_list<SurfaceType> surfaces_bottom { stBottom, stBottomBridge };
+                    for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++ idx_layer) {
+                        m_print->throw_if_canceled();
+                        Layer       &layer                = *m_layers[idx_layer];
+                        LayerRegion &layerm               = *layer.m_regions[region_id];
+                        float        top_bottom_expansion = float(layerm.flow(frSolidInfill).scaled_spacing()) * top_bottom_expansion_coeff;
+                        // Top surfaces.
+                        auto &cache = cache_top_botom_regions[idx_layer];
+                        cache.top_surfaces = offset(layerm.slices.filter_by_type(stTop), top_bottom_expansion);
+//                        append(cache.top_surfaces, offset(layerm.fill_surfaces.filter_by_type(stTop), top_bottom_expansion));
+                        // Bottom surfaces.
+                        cache.bottom_surfaces = offset(layerm.slices.filter_by_types(surfaces_bottom), top_bottom_expansion);
+//                        append(cache.bottom_surfaces, offset(layerm.fill_surfaces.filter_by_types(surfaces_bottom), top_bottom_expansion));
+                        // Holes over all regions. Only collect them once, they are valid for all region_id iterations.
+                        if (cache.holes.empty()) {
+                            for (size_t region_id = 0; region_id < layer.regions().size(); ++ region_id)
+                                polygons_append(cache.holes, to_polygons(layer.regions()[region_id]->fill_expolygons));
+                        }
+                    }
+                });
+            m_print->throw_if_canceled();
+            BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells for region " << region_id << " in parallel - end : cache top / bottom";
+        }
+
+        BOOST_LOG_TRIVIAL(debug) << "Discovering vertical shells for region " << region_id << " in parallel - start : ensure vertical wall thickness";
+        grain_size = 1;
+        tbb::parallel_for(
+            tbb::blocked_range<size_t>(0, num_layers, grain_size),
+            [this, region_id, &shell_accumulations, &accumulation_key, &accumulate_shell]
+            (const tbb::blocked_range<size_t>& range) {
+                // printf("discover_vertical_shells from %d to %d\n", range.begin(), range.end());
+                for (size_t idx_layer = range.begin(); idx_layer < range.end(); ++ idx_layer) {
+                    m_print->throw_if_canceled();
+#ifdef SLIC3R_DEBUG_SLICE_PROCESSING
+        			static size_t debug_idx = 0;
+        			++ debug_idx;
+#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
+
+                    Layer       	        *layer          = m_layers[idx_layer];
+                    LayerRegion 	        *layerm         = layer->m_regions[region_id];
+                    const PrintRegionConfig &region_config  = layerm->region().config();
+
+#ifdef SLIC3R_DEBUG_SLICE_PROCESSING
+                    layerm->export_region_slices_to_svg_debug("3_discover_vertical_shells-initial");
+                    layerm->export_region_fill_surfaces_to_svg_debug("3_discover_vertical_shells-initial");
+#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
+
+                    Flow         solid_infill_flow   = layerm->flow(frSolidInfill);
+                    coord_t      infill_line_spacing = solid_infill_flow.scaled_spacing();
+                    // Find a union of perimeters below / above this surface to guarantee a minimum shell thickness.
+                    Polygons shell;
+                    Polygons holes;
+#ifdef SLIC3R_DEBUG_SLICE_PROCESSING
+                    ExPolygons shell_ex;
+#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
+                    float min_perimeter_infill_spacing = float(infill_line_spacing) * 1.05f;
+#if 0
+// #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
+                    {
+        				Slic3r::SVG svg_cummulative(debug_out_path("discover_vertical_shells-perimeters-before-union-run%d.svg", debug_idx), this->bounding_box());
+                        for (int n = (int)idx_layer - n_extra_bottom_layers; n <= (int)idx_layer + n_extra_top_layers; ++ n) {
+                            if (n < 0 || n >= (int)m_layers.size())
+                                continue;
+                            ExPolygons &expolys = m_layers[n]->perimeter_expolygons;
+                            for (size_t i = 0; i < expolys.size(); ++ i) {
+        						Slic3r::SVG svg(debug_out_path("discover_vertical_shells-perimeters-before-union-run%d-layer%d-expoly%d.svg", debug_idx, n, i), get_extents(expolys[i]));
+                                svg.draw(expolys[i]);
+                                svg.draw_outline(expolys[i].contour, "black", scale_(0.05));
+                                svg.draw_outline(expolys[i].holes, "blue", scale_(0.05));
+                                svg.Close();
+
+                                svg_cummulative.draw(expolys[i]);
+                                svg_cummulative.draw_outline(expolys[i].contour, "black", scale_(0.05));
+                                svg_cummulative.draw_outline(expolys[i].holes, "blue", scale_(0.05));
+                            }
+                        }
+                    }
+#endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
+                    const AccumulationKey key = accumulation_key(region_config, layerm);
+                    const ShellAccumulation *reused = shell_accumulations.empty() ? nullptr :
+                        [&]() -> const ShellAccumulation * {
+                            for (const ShellAccumulation &a : shell_accumulations[idx_layer])
+                                if (a.key == key)
+                                    return &a;
+                            return nullptr;
+                        }();
+                    if (reused != nullptr) {
+                        shell = reused->shell;
+                        holes = reused->holes;
+                    } else
+                        accumulate_shell(idx_layer, region_config, layerm, shell, holes);
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     {
         				Slic3r::SVG svg(debug_out_path("discover_vertical_shells-perimeters-before-union-%d.svg", debug_idx), get_extents(shell));
@@ -2831,11 +2919,8 @@ void PrintObject::discover_vertical_shells()
                         Polygons object_volume;
                         Polygons internal_volume;
                         {
-                            Polygons shrinked_bottom_slice = idx_layer > 0 ? to_polygons(m_layers[idx_layer - 1]->lslices) : Polygons{};
+                            if (idx_layer > 0 && idx_layer + 1 < m_layers.size())
-                            Polygons shrinked_upper_slice  = (idx_layer + 1) < m_layers.size() ?
+                                object_volume = to_polygons(intersection_ex_by_piece(m_layers[idx_layer - 1]->lslices, to_polygons(m_layers[idx_layer + 1]->lslices)));
-                                                                 to_polygons(m_layers[idx_layer + 1]->lslices) :
-                                                                 Polygons{};
-                            object_volume = intersection(shrinked_bottom_slice, shrinked_upper_slice);
                             internal_volume = closing(polygonsInternal, SCALED_EPSILON);
                         }
 
@@ -2846,15 +2931,34 @@ void PrintObject::discover_vertical_shells()
                         //      the in-model condition is there due to small sloping surfaces, e.g. top of the hull of the benchy
                         //   2. the area does not fully cover an internal polygon
                         //         This is there mainly for a very thin parts, where the solid layers would be missing if the part area is quite small
+                        // Both tests below compare a small piece against the whole layer. Done literally, that is
+                        // quadratic in the number of pieces, which is what a layer split up by colour painting has,
+                        // so each is restricted to the part of the layer near the piece with an identical result:
+                        // object_volume is clipped to the piece's box, and only the internal polygons whose box meets
+                        // the expanded piece take part in the count, since the others pass through the difference
+                        // unchanged and add the same number to both sides of it.
+                        std::vector<BoundingBox> internal_bboxes;
+                        internal_bboxes.reserve(internal_volume.size());
+                        for (const Polygon &poly : internal_volume)
+                            internal_bboxes.emplace_back(get_extents(poly));
                         regularized_shell.erase(std::remove_if(regularized_shell.begin(), regularized_shell.end(),
-                                                               [&internal_volume, &min_perimeter_infill_spacing,
+                                                               [&internal_volume, &internal_bboxes, &min_perimeter_infill_spacing,
                                                                 &object_volume](const ExPolygon &p) {
-                                                                   return (p.area() < min_perimeter_infill_spacing * scaled(1.5) ||
+                                                                   const bool small = p.area() < min_perimeter_infill_spacing * scaled(1.5) ||
                                                                                       (p.area() < min_perimeter_infill_spacing * scaled(8.0) &&
-                                                                            diff(to_polygons(p), object_volume).empty())) &&
+                                                                                       diff(to_polygons(p),
-                                                                          diff(internal_volume,
+                                                                                            ClipperUtils::clip_clipper_polygons_with_subject_bbox(
-                                                                               expand(to_polygons(p), min_perimeter_infill_spacing))
+                                                                                                object_volume, get_extents(p).inflated(SCALED_EPSILON)))
-                                                                                  .size() >= internal_volume.size();
+                                                                                           .empty());
+                                                                   if (!small)
+                                                                       return false;
+                                                                   const Polygons    expanded = expand(to_polygons(p), min_perimeter_infill_spacing);
+                                                                   const BoundingBox bbox     = get_extents(expanded);
+                                                                   Polygons          nearby;
+                                                                   for (size_t i = 0; i < internal_volume.size(); ++i)
+                                                                       if (internal_bboxes[i].overlap(bbox))
+                                                                           nearby.emplace_back(internal_volume[i]);
+                                                                   return diff(nearby, expanded).size() >= nearby.size();
                                                                }),
                                                 regularized_shell.end());
                     }
@@ -2876,8 +2980,9 @@ void PrintObject::discover_vertical_shells()
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
 
                     // Trim the internal & internalvoid by the shell.
-                    Slic3r::ExPolygons new_internal = diff_ex(layerm->fill_surfaces.filter_by_type(stInternal), regularized_shell);
+                    const Polygons     regularized_shell_polygons = to_polygons(regularized_shell);
-                    Slic3r::ExPolygons new_internal_void = diff_ex(layerm->fill_surfaces.filter_by_type(stInternalVoid), regularized_shell);
+                    Slic3r::ExPolygons new_internal = diff_ex_by_piece(to_expolygons(layerm->fill_surfaces.filter_by_type(stInternal)), regularized_shell_polygons);
+                    Slic3r::ExPolygons new_internal_void = diff_ex_by_piece(to_expolygons(layerm->fill_surfaces.filter_by_type(stInternalVoid)), regularized_shell_polygons);
 
 #ifdef SLIC3R_DEBUG_SLICE_PROCESSING
                     {
@@ -2904,7 +3009,15 @@ void PrintObject::discover_vertical_shells()
 			layerm->export_region_fill_surfaces_to_svg_debug("3_discover_vertical_shells-final");
 		}
 #endif /* SLIC3R_DEBUG_SLICE_PROCESSING */
-    } // for each region
+    }; // for each region
+    if (top_bottom_surfaces_all_regions)
+        // Nothing is shared between the regions, and a layer cut through a fine relief takes far longer than the others,
+        // so they run next to each other instead of one after another.
+        tbb::parallel_for(size_t(0), this->num_printing_regions(), process_region);
+    else
+        // Here every region fills the one top/bottom cache with its own surfaces first.
+        for (size_t region_id = 0; region_id < this->num_printing_regions(); ++ region_id)
+            process_region(region_id);
 } // void PrintObject::discover_vertical_shells()
 
 // #define DEBUG_BRIDGE_OVER_INFILL
@@ -3425,6 +3538,16 @@ void PrintObject::bridge_over_infill()
                 vertical_lines[i].b = Point{x, y_max};
             }
 
+            // The vertical lines only span the bridged area's x range, so anchors entirely outside it can never be
+            // hit. Leaving them out gives the same intersections without building a tree over the whole layer's
+            // boundary for every bridge.
+            const coord_t scan_x_min = bb_x.min.x();
+            const coord_t scan_x_max = bb_x.min.x() + coord_t(n_vlines) * scan_spacing;
+            anchors.erase(std::remove_if(anchors.begin(), anchors.end(),
+                                         [scan_x_min, scan_x_max](const Line &l) {
+                                             return std::max(l.a.x(), l.b.x()) < scan_x_min || std::min(l.a.x(), l.b.x()) > scan_x_max;
+                                         }),
+                          anchors.end());
             auto anchors_and_walls_tree = AABBTreeLines::LinesDistancer<Line>{std::move(anchors)};
             auto bridged_area_tree      = AABBTreeLines::LinesDistancer<Line>{to_lines(bridged_area)};
 
@@ -3669,26 +3792,58 @@ void PrintObject::bridge_over_infill()
 
                 std::vector<CandidateSurface> expanded_surfaces;
                 expanded_surfaces.reserve(surfaces_by_layer[lidx].size());
+                // The expanded fill boundary depends only on the bridging flow, and total_fill_area is not
+                // modified below, so build it once per spacing rather than once per candidate. A layer split
+                // into many candidates (e.g. by colour painting) otherwise repeats a layer-wide offset for each.
+                std::map<coord_t, Polylines> boundary_by_spacing;
+                // expansion_area is a clean, non-overlapping set, so cutting a bridge out of it only changes the
+                // polygons near that bridge. The rest are passed through untouched instead of being fed to Clipper
+                // with the whole layer again for every candidate.
+                // Not `near`/`far`: the Windows headers still define those as macros, and they expand to
+                // nothing, which turns the declaration below into an empty one.
+                const auto split_near = [](const Polygons &polys, const BoundingBox &bbox, Polygons &rest) {
+                    Polygons nearby;
+                    for (const Polygon &p : polys)
+                        (get_extents(p).overlap(bbox) ? nearby : rest).emplace_back(p);
+                    return nearby;
+                };
                 for (const CandidateSurface &candidate : surfaces_by_layer[lidx]) {
                     const auto &region_config = candidate.region->region().config();
                     const bool turning_pattern = region_config.sparse_infill_pattern == ipHilbertCurve ||
                                                  region_config.sparse_infill_pattern == ipOctagramSpiral;
                     const Flow &flow              = candidate.region->bridging_flow(frSolidInfill, true);
-                    ExPolygons bridge_components = intersection_ex(expand(candidate.new_polys, flow.scaled_spacing()), deep_infill_area);
+                    const Polygons expanded_polys = expand(candidate.new_polys, flow.scaled_spacing());
+                    // deep_infill_area and internal_unsupported_area cover the whole layer; only their part under
+                    // this candidate can change the results, so they are clipped to its box first.
+                    ExPolygons bridge_components;
+                    if (!expanded_polys.empty())
+                        bridge_components = intersection_ex(expanded_polys,
+                                                            ClipperUtils::clip_clipper_polygons_with_subject_bbox(
+                                                                deep_infill_area, get_extents(expanded_polys).inflated(SCALED_EPSILON)));
                     // Orca: Filter whole bridge areas so their holes remain holes.
                     bridge_components.erase(std::remove_if(bridge_components.begin(), bridge_components.end(),
                                                            [&internal_unsupported_area](const ExPolygon &component) {
-                                                               return intersection_ex(component, internal_unsupported_area).empty();
+                                                               return intersection_ex(component, ClipperUtils::clip_clipper_polygons_with_subject_bbox(
+                                                                                                     internal_unsupported_area,
+                                                                                                     get_extents(component).inflated(SCALED_EPSILON)))
+                                                                   .empty();
                                                            }),
                                             bridge_components.end());
                     Polygons area_to_be_bridge = to_polygons(std::move(bridge_components));
 
-                    Polygons limiting_area = union_(area_to_be_bridge, expansion_area);
-
                     if (area_to_be_bridge.empty())
                         continue;
 
-                    Polylines boundary_plines = to_polylines(expand(total_fill_area, 1.3f * flow.scaled_spacing()));
+                    // Not split like the cut of expansion_area below: the whole limiting area is grown by 30% of the spacing,
+                    // which merges neighbouring polygons, and any of its boundary can anchor the bridge.
+                    Polygons limiting_area = union_(area_to_be_bridge, expansion_area);
+
+                    auto boundary_it = boundary_by_spacing.find(flow.scaled_spacing());
+                    if (boundary_it == boundary_by_spacing.end())
+                        boundary_it = boundary_by_spacing
+                                          .emplace(flow.scaled_spacing(), to_polylines(expand(total_fill_area, 1.3f * flow.scaled_spacing())))
+                                          .first;
+                    Polylines boundary_plines = boundary_it->second;
                     {
                         Polylines limiting_plines = to_polylines(expand(limiting_area, 0.3f * flow.scaled_spacing()));
                         boundary_plines.insert(boundary_plines.end(), limiting_plines.begin(), limiting_plines.end());
@@ -3764,9 +3919,12 @@ void PrintObject::bridge_over_infill()
                     // Check collision with other expanded surfaces
                     {
                         bool     reconstruct       = false;
-                        Polygons tmp_expanded_area = expand(bridging_area, 3.0f * flow.scaled_spacing());
+                        Polygons          tmp_expanded_area = expand(bridging_area, 3.0 * flow.scaled_spacing());
+                        const BoundingBox tmp_expanded_bbox = get_extents(tmp_expanded_area);
                         for (const CandidateSurface &s : expanded_surfaces) {
-                            if (!intersection(s.new_polys, tmp_expanded_area).empty()) {
+                            // Surfaces whose boxes miss each other cannot intersect, which is most pairs on a busy layer.
+                            if (get_extents(s.new_polys).overlap(tmp_expanded_bbox) &&
+                                !intersection(s.new_polys, tmp_expanded_area).empty()) {
                                 bridging_angle = s.bridge_angle;
                                 reconstruct    = true;
                                 break;
@@ -3790,10 +3948,20 @@ void PrintObject::bridge_over_infill()
                         bridging_area = union_(bridging_area, construct_anchored_polygon(bridging_area, to_lines(boundary_plines), flow,
                                                                                        bridging_angle, scan_spacing, true));
                     }
-                    bridging_area          = intersection(bridging_area, limiting_area);
+                    // Each of these meets one bridge with the whole layer, so the layer side is first cut down to the
-                    bridging_area          = intersection(bridging_area, total_fill_area);
+                    // bridge's box (and expansion_area split as above); the result is the same.
-                    bridging_area          = diff(bridging_area, total_top_area);
+                    if (!bridging_area.empty()) {
-                    expansion_area         = diff(expansion_area, bridging_area);
+                        const BoundingBox bridging_bbox = get_extents(bridging_area).inflated(SCALED_EPSILON);
+                        bridging_area = intersection(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(limiting_area, bridging_bbox));
+                        bridging_area = intersection(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(total_fill_area, bridging_bbox));
+                        bridging_area = diff(bridging_area, ClipperUtils::clip_clipper_polygons_with_subject_bbox(total_top_area, bridging_bbox));
+                    }
+                    if (!bridging_area.empty()) {
+                        Polygons       kept;
+                        const Polygons cut = split_near(expansion_area, get_extents(bridging_area).inflated(SCALED_EPSILON), kept);
+                        append(kept, diff(cut, bridging_area));
+                        expansion_area = std::move(kept);
+                    }
 
 #ifdef DEBUG_BRIDGE_OVER_INFILL
                     debug_draw(std::to_string(lidx) + "_" + std::to_string(cluster_idx) + "_" + std::to_string(job_idx) + "_" + "_expanded_bridging" +  std::to_string(r),

src/libslic3r/Support/SupportMaterial.cpp

@@ -1004,9 +1004,9 @@ public:
                 ::fread(&y, sizeof(coord_t), 1, file);
                 poly.points.emplace_back(Point(x * scale, y * scale));
             }
+            printf("Polygon %d, area: %lf\n", i, area(poly.points));
             if (which == -1 || which == i)
                 m_support_polygons_deserialized.emplace_back(std::move(poly));
-            printf("Polygon %d, area: %lf\n", i, area(poly.points));
         }
         ::fread(&n_polygons, 4, 1, file);
         m_trimming_polygons_deserialized.reserve(n_polygons);

src/libslic3r/Support/TreeSupport.cpp

@@ -996,16 +996,46 @@ void TreeSupport::detect_overhangs(bool check_support_necessity/* = false*/)
                 if (is_auto(stype) && config_detect_sharp_tails)
                 {
                     // BBS detect sharp tail
-                    for (const ExPolygon& expoly : curr_polys) {
-                        bool  is_sharp_tail = false;
-                        // 1. nothing below
-                        // this is a sharp tail region if it's floating and non-ignorable.
                     // On a belt, "below" has to include the belt itself and the
                     // shear-advanced lower layer, or every belt-contact island reads as
                     // a sharp tail -- which is what the empty-predecessor skip above was
                     // really masking. effective_lower is exactly that notion of below.
                     const ExPolygons &tail_lower = belt_ovh_active ? effective_lower : lower_polys;
-                        if (!overlaps(offset_ex(expoly, 0.1 * extrusion_width_scaled), tail_lower)) {
+                    // Each island is tested only against the lower islands whose box meets its own; overlaps() tries
+                    // every pair, which is quadratic in the island counts of the two layers.
+                    std::vector<BoundingBox> lower_bboxes;
+                    lower_bboxes.reserve(tail_lower.size());
+                    for (const ExPolygon &lower : tail_lower)
+                        lower_bboxes.emplace_back(get_extents(lower));
+                    for (const ExPolygon& expoly : curr_polys) {
+                        bool  is_sharp_tail = false;
+                        // 1. nothing below
+                        // this is a sharp tail region if it's floating and non-ignorable
+                        const ExPolygons  expanded = offset_ex(expoly, 0.1 * extrusion_width_scaled);
+                        const BoundingBox bbox     = get_extents(expanded);
+                        ExPolygons        lower_nearby;
+                        for (size_t i = 0; i < tail_lower.size(); ++i)
+                            if (lower_bboxes[i].overlap(bbox))
+                                lower_nearby.emplace_back(tail_lower[i]);
+                        // As overlaps(expanded, lower_nearby), with each lower island cut to the island's box first:
+                        // below a fine relief the lower layer is a few islands with thousands of holes, and the whole
+                        // of that boundary would otherwise be intersected once per island above.
+                        const auto overlaps_nearby = [&]() {
+                            for (const ExPolygon &a : expanded) {
+                                if (a.empty())
+                                    continue;
+                                const BoundingBox a_bbox = get_extents(a);
+                                for (const ExPolygon &b : lower_nearby) {
+                                    if (b.empty() || !get_extents(b).overlap(a_bbox))
+                                        continue;
+                                    const Polygons b_near = ClipperUtils::clip_clipper_polygons_with_subject_bbox(b, a_bbox.inflated(SCALED_EPSILON));
+                                    if (!intersection_pl(to_polylines(b_near), a).empty() || b.contains(a.contour.points.front()))
+                                        return true;
+                                }
+                            }
+                            return false;
+                        };
+                        if (!overlaps_nearby()) {
                             is_sharp_tail = !offset_ex(expoly, -0.1 * extrusion_width_scaled).empty();
                         }
 

src/libslic3r/Surface.hpp

@@ -68,7 +68,7 @@ public:
             thickness(other.thickness), thickness_layers(other.thickness_layers),
             bridge_angle(other.bridge_angle), extra_perimeters(other.extra_perimeters)
         {};
-    Surface(Surface &&rhs)
+    Surface(Surface &&rhs) noexcept
         : surface_type(rhs.surface_type), expolygon(std::move(rhs.expolygon)),
             thickness(rhs.thickness), thickness_layers(rhs.thickness_layers),
             bridge_angle(rhs.bridge_angle), extra_perimeters(rhs.extra_perimeters)
@@ -94,7 +94,7 @@ public:
         return *this;
     }
 
-    Surface& operator=(Surface &&rhs)
+    Surface& operator=(Surface &&rhs) noexcept
     {
         surface_type     = rhs.surface_type;
         expolygon        = std::move(rhs.expolygon);

src/libslic3r/libslic3r.h

@@ -167,10 +167,10 @@ inline void append(std::vector<T, Alloc> &dest, std::vector<T, Alloc> &&src)
 {
     if (dest.empty())
         dest = std::move(src);
-    else {
+    else
-        dest.reserve(dest.size() + src.size());
+        // insert() grows the capacity geometrically; reserving exactly the new size reallocated on every call, which
-        std::move(std::begin(src), std::end(src), std::back_inserter(dest));
+        // made appending piece by piece quadratic.
-    }
+        dest.insert(dest.end(), std::make_move_iterator(src.begin()), std::make_move_iterator(src.end()));
     src.clear();
     src.shrink_to_fit();
 }

src/slic3r/plugin/PluginAuditManager.cpp

@@ -11,6 +11,7 @@
 #include <boost/log/trivial.hpp>
 
 #include <algorithm>
+#include <cassert>
 #include <cctype>
 #include <cstddef>
 #include <cstdlib>
@@ -130,6 +131,20 @@ static AuditEventCategory event_category(const std::string& event_name)
     return it == audit_event_categories.end() ? AuditEventCategory::None : it->second;
 }
 
+// Events the 3.12 stdlib raises with sys.audit() inside the function that performs the whole
+// operation, so the raising frame bounds everything the operation does. Every other mapped event
+// is a primitive raised from C, whose current frame is whatever Python code called it -- possibly
+// a library loop over many targets -- so it never marks an operation. glob.glob and glob.glob/2
+// are raised in iglob(), which returns its lazy generator before any directory is listed.
+static const std::unordered_set<std::string> operation_root_events{
+    "urllib.Request",      "http.client.connect",   "os.walk",          "os.fwalk",
+    "glob.glob",           "glob.glob/2",           "pathlib.Path.glob", "pathlib.Path.rglob",
+    "subprocess.Popen",    "pty.spawn",             "tempfile.mkstemp", "tempfile.mkdtemp",
+    "shutil.copyfile",     "shutil.copymode",       "shutil.copystat",  "shutil.copytree",
+    "shutil.chown",        "shutil.move",           "shutil.rmtree",    "shutil.make_archive",
+    "shutil.unpack_archive",
+};
+
 // True for the categories whose targets are filesystem paths, as opposed to a network
 // address or a process command line -- the deny-path and allowed-root checks only make sense
 // against a path.
@@ -146,6 +161,24 @@ static bool is_fs_category(AuditEventCategory category)
     }
 }
 
+// The category's name in a saved event grant, e.g. "FsRead" in "FsRead:open".
+static const char* category_name(AuditEventCategory category)
+{
+    switch (category) {
+    case AuditEventCategory::FsRead:         return "FsRead";
+    case AuditEventCategory::FsReadWrite:    return "FsReadWrite";
+    case AuditEventCategory::FsCreate:       return "FsCreate";
+    case AuditEventCategory::FsDelete:       return "FsDelete";
+    case AuditEventCategory::Http:           return "Http";
+    case AuditEventCategory::Socket:         return "Socket";
+    case AuditEventCategory::ProcessCreate:  return "ProcessCreate";
+    case AuditEventCategory::ProcessReplace: return "ProcessReplace";
+    case AuditEventCategory::Threading:      return "Threading";
+    case AuditEventCategory::None:           break;
+    }
+    return "None";
+}
+
 // ---------------------------------------------------------------------------
 // Path safety
 // ---------------------------------------------------------------------------
@@ -215,26 +248,50 @@ bool is_inside_allowed_root(const boost::filesystem::path& candidate, const boos
 thread_local std::string PluginAuditManager::m_current_plugin_key = "";
 thread_local std::string PluginAuditManager::m_current_capability_name = "";
 thread_local std::vector<AllowedRoot> PluginAuditManager::m_scoped_allowed_roots;
+thread_local std::vector<PyObject*> PluginAuditManager::m_root_frames;
+thread_local int PluginAuditManager::m_releasing_frames = 0;
 thread_local bool PluginAuditManager::m_audit_denial_pending = false;
 thread_local bool PluginAuditManager::m_has_last_violation = false;
 thread_local AuditViolation PluginAuditManager::m_last_violation;
 
 ScopedPluginAuditContext::ScopedPluginAuditContext(const std::string& plugin_key,
                                                    const std::string& capability_name)
-    : m_previous_id(PluginAuditManager::instance().current_plugin())
+    : m_plugin_key(plugin_key)
+    , m_capability(capability_name)
+    , m_previous_id(PluginAuditManager::instance().current_plugin())
     , m_previous_capability(PluginAuditManager::instance().current_capability())
     , m_previous_scoped_roots(PluginAuditManager::m_scoped_allowed_roots)
+    , m_previous_root_frames(std::move(PluginAuditManager::m_root_frames))
 {
     PluginAuditManager::instance().set_current_plugin(plugin_key);
     PluginAuditManager::instance().set_current_capability(capability_name);
     PluginAuditManager::m_scoped_allowed_roots.clear();
+    PluginAuditManager::m_root_frames.clear();
 }
 
 ScopedPluginAuditContext::~ScopedPluginAuditContext()
 {
-    PluginAuditManager::instance().set_current_plugin(m_previous_id);
+    PluginAuditManager& mgr = PluginAuditManager::instance();
-    PluginAuditManager::instance().set_current_capability(m_previous_capability);
+
+    // Let this scope's root frames go while it is still the current context, and as its own
+    // plugin: the trampoline's denial path clears the key before the scope ends, and a finalizer
+    // must never be judged as the outer plugin, or bypass the audit when there is none. A
+    // finalizer may record a new root frame, so repeat until none is held.
+    if (!PluginAuditManager::m_root_frames.empty()) {
+        assert(PyGILState_Check());
+        mgr.set_current_plugin(m_plugin_key);
+        mgr.set_current_capability(m_capability);
+        while (!PluginAuditManager::m_root_frames.empty()) {
+            std::vector<PyObject*> frames = std::move(PluginAuditManager::m_root_frames);
+            PluginAuditManager::m_root_frames.clear();
+            mgr.release_frames(frames);
+        }
+    }
+
+    mgr.set_current_plugin(m_previous_id);
+    mgr.set_current_capability(m_previous_capability);
     PluginAuditManager::m_scoped_allowed_roots = std::move(m_previous_scoped_roots);
+    PluginAuditManager::m_root_frames          = std::move(m_previous_root_frames);
 }
 
 // ---------------------------------------------------------------------------
@@ -298,14 +355,16 @@ std::vector<std::string> PluginAuditManager::default_denied_filenames()
     // AppConfig::config_path() picks .conf vs .ini on the USE_JSON_CONFIG ifdef and the app key
     // on its mode, and is a non-static member we cannot call without an instance. Denying all
     // four names is cheaper and more robust than replicating that; the two unused names cost one
-    // string comparison each.  Single-sourced here so install_hook() and the tests seed from the
+    // string comparison each. Keep the plugin install-state sidecar here too: it controls which
-    // same list and cannot drift apart.
+    // packages load on startup and must remain host-managed. Single-sourced so install_hook() and
+    // the tests seed from the same list and cannot drift apart.
     return {
         SLIC3R_APP_KEY ".conf",
         GCODEVIEWER_APP_KEY ".conf",
         SLIC3R_APP_KEY ".ini",
         GCODEVIEWER_APP_KEY ".ini",
         secret_constants::USER_SECRET_FILENAME,
+        ".install_state.json",
     };
 }
 
@@ -575,34 +634,6 @@ bool PluginAuditManager::last_violation(AuditViolation& violation) const
     return true;
 }
 
-bool PluginAuditManager::has_approved_ancestor(const std::string&              plugin_key,
-                                               const std::vector<std::string>& call_site_ids) const
-{
-    if (plugin_key.empty() || call_site_ids.empty())
-        return false;
-
-    std::lock_guard<std::mutex> lock(m_mutex);
-    auto it = m_approved_call_sites.find(plugin_key);
-    if (it == m_approved_call_sites.end())
-        return false;
-
-    for (const auto& id : call_site_ids)
-        if (it->second.count(id))
-            return true;
-    return false;
-}
-
-void PluginAuditManager::record_approved_call_sites(const std::string&              plugin_key,
-                                                     const std::vector<std::string>& call_site_ids)
-{
-    if (plugin_key.empty() || call_site_ids.empty())
-        return;
-
-    std::lock_guard<std::mutex> lock(m_mutex);
-    auto& approved = m_approved_call_sites[plugin_key];
-    approved.insert(call_site_ids.begin(), call_site_ids.end());
-}
-
 // ---------------------------------------------------------------------------
 // The C-level audit hook
 // ---------------------------------------------------------------------------
@@ -663,40 +694,88 @@ std::string python_str(PyObject* object)
     return result;
 }
 
-std::vector<std::string> call_site_identities(const std::string& plugin_root)
+// The interpreter's stdlib folders, and the site-packages folders inside them that hold
-{
+// third-party code, both resolved. Set by install_hook(); like the verdict cache below, only
-    std::vector<std::string> ids;
+// touched while the GIL is held.
-    if (plugin_root.empty())
+static std::vector<boost::filesystem::path>   s_stdlib_dirs;
-        return ids;
+static std::vector<boost::filesystem::path>   s_site_package_dirs;
+static std::unordered_map<std::string, bool>  s_stdlib_file_verdicts; // co_filename -> is stdlib
 
+void collect_stdlib_dirs()
+{
+    s_stdlib_dirs.clear();
+    s_site_package_dirs.clear();
+    s_stdlib_file_verdicts.clear();
+
+    PyObject* sysconfig = PyImport_ImportModule("sysconfig");
+    PyObject* paths     = sysconfig ? PyObject_CallMethod(sysconfig, "get_paths", nullptr) : nullptr;
+    if (paths && PyDict_Check(paths)) {
+        const auto collect = [paths](const char* key, std::vector<boost::filesystem::path>& out) {
+            const std::string dir = python_unicode(PyDict_GetItemString(paths, key)); // borrowed
+            if (dir.empty())
+                return;
+            boost::system::error_code ec;
+            const boost::filesystem::path resolved = boost::filesystem::weakly_canonical(dir, ec);
+            out.push_back(ec ? boost::filesystem::path(dir) : resolved);
+        };
+        collect("stdlib", s_stdlib_dirs);
+        collect("platstdlib", s_stdlib_dirs);
+        collect("purelib", s_site_package_dirs);
+        collect("platlib", s_site_package_dirs);
+    }
+    Py_XDECREF(paths);
+    Py_XDECREF(sysconfig);
+    if (PyErr_Occurred()) {
+        PyErr_Clear();
+        BOOST_LOG_TRIVIAL(error) << "[AUDIT] Failed to read the stdlib folders from sysconfig";
+    }
+}
+
+bool is_stdlib_frame(PyObject* frame)
+{
+    PyCodeObject* code = PyFrame_GetCode(reinterpret_cast<PyFrameObject*>(frame)); // new reference
+    const std::string filename = python_unicode(code->co_filename);
+    Py_DECREF(code);
+    return PluginAuditManager::is_stdlib_file(filename);
+}
+
+// The frames on this thread's Python stack, innermost first. The pointers stay valid while the
+// caller runs, because a running activation keeps its frame object alive.
+std::vector<PyObject*> stack_frames()
+{
+    std::vector<PyObject*> frames;
     PyFrameObject* frame = PyEval_GetFrame(); // borrowed reference
     Py_XINCREF(frame);                        // normalize to an owned reference for the loop below
-
     while (frame) {
-        PyCodeObject* code     = PyFrame_GetCode(frame); // new reference
+        frames.push_back(reinterpret_cast<PyObject*>(frame));
-        const std::string filename = python_unicode(reinterpret_cast<PyObject*>(code->co_filename));
-        const bool is_plugin_frame = !filename.empty() && boost::algorithm::starts_with(filename, plugin_root);
-
-        std::string id;
-        if (!is_plugin_frame && !filename.empty()) {
-            const std::string funcname = python_unicode(reinterpret_cast<PyObject*>(code->co_name));
-            id = filename + ":" + funcname + ":" + std::to_string(code->co_firstlineno);
-        }
-        Py_DECREF(code);
-
         PyFrameObject* back = PyFrame_GetBack(frame); // new reference, or nullptr at the top of the stack
         Py_DECREF(frame);
         frame = back;
-
-        if (is_plugin_frame)
-            break;
-        if (!id.empty())
-            ids.push_back(std::move(id));
     }
+    return frames;
+}
 
-    Py_XDECREF(frame); // only holds a reference here if the loop exited via break
+// Moves the held root frames whose operation has returned from `held` to `dropped`. A suspended
+// generator's frame (os.walk between two items) is off the stack, but its operation resumes, so
+// it stays held until the scope ends.
+void take_returned_frames(std::vector<PyObject*>& held, std::vector<PyObject*>& dropped)
+{
+    if (held.empty())
+        return;
 
-    return ids;
+    const std::vector<PyObject*> stack = stack_frames();
+    const auto running = [&stack](PyObject* frame) {
+        if (std::find(stack.begin(), stack.end(), frame) != stack.end())
+            return true;
+        // NULL once the generator has finished or been deleted: its frame then owns its own data.
+        PyObject* generator = PyFrame_GetGenerator(reinterpret_cast<PyFrameObject*>(frame)); // new reference
+        const bool suspended = generator != nullptr;
+        Py_XDECREF(generator);
+        return suspended;
+    };
+    const auto returned = std::stable_partition(held.begin(), held.end(), running);
+    dropped.insert(dropped.end(), returned, held.end());
+    held.erase(returned, held.end());
 }
 
 static const std::unordered_set<std::string> two_path_fs_events{
@@ -717,12 +796,15 @@ static const std::unordered_map<std::string, std::vector<Py_ssize_t>> audit_targ
     {"socket.getnameinfo", {0}},
     {"socket.getservbyname", {0}},
     {"socket.getservbyport", {0}},
+    {"socket.sendto", {1}},
+    {"socket.sendmsg", {1}},
 
     {"os.system", {0}},
     {"subprocess.Popen", {1, 0}},
     {"os.posix_spawn", {1, 0}},
     {"os.spawn", {2, 1}},
     {"os.startfile", {0}},
+    {"os.startfile/2", {0}},
     {"pty.spawn", {0}},
     {"_winapi.CreateProcess", {1, 0}},
     {"_posixsubprocess.fork_exec", {0}},
@@ -767,7 +849,11 @@ std::vector<std::string> audit_targets(const std::string& event_name, AuditEvent
     const auto it = audit_target_arg_indices.find(event_name);
     if (it != audit_target_arg_indices.end()) {
         for (const Py_ssize_t index : it->second) {
-            std::string value = python_str(tuple_item(args, index));
+            // None is an argument left out (sendmsg without an address), not a target named "None".
+            PyObject* const item = tuple_item(args, index);
+            if (item == Py_None)
+                continue;
+            std::string value = python_str(item);
             if (!value.empty()) {
                 targets.push_back(std::move(value));
                 break;
@@ -778,8 +864,14 @@ std::vector<std::string> audit_targets(const std::string& event_name, AuditEvent
     return targets;
 }
 
-std::vector<std::string>* permission_list_for(AuditEventCategory category, PluginPermissions& permissions)
+// The saved list that grants an event: its category's target list, or the event-grant list for
+// an event with no target. Kept apart, so that no grant doubles as a target of the same name (an
+// os.fork grant is not an os.exec of a command named "os.fork").
+std::vector<std::string>* permission_list_for(AuditEventCategory category, bool by_event, PluginPermissions& permissions)
 {
+    if (by_event)
+        return &permissions.events;
+
     switch (category) {
     case AuditEventCategory::FsRead:        return &permissions.fs_read;
     case AuditEventCategory::FsReadWrite:   return &permissions.fs_readwrite;
@@ -792,6 +884,13 @@ std::vector<std::string>* permission_list_for(AuditEventCategory category, Plugi
     }
 }
 
+// An event with no target is granted by its effective category and name, e.g. "FsRead:open"
+// for a read of a file descriptor, which does not grant a write of one ("FsReadWrite:open").
+std::string event_grant_key(AuditEventCategory category, const std::string& event_name)
+{
+    return std::string(category_name(category)) + ":" + event_name;
+}
+
 bool has_permission(const std::vector<std::string>& granted, const std::string& target)
 {
     return std::find(granted.begin(), granted.end(), target) != granted.end();
@@ -902,22 +1001,25 @@ bool prompt_for_targets(AuditEventCategory category, const std::string& plugin_n
 
 // Records a grant in the plugin's sidecar so it is not asked again. Reads the install state
 // freshly because the async prompt outlives the caller's stack copy of it.
-void persist_grant(const std::string& plugin_key, AuditEventCategory category, const std::vector<std::string>& targets)
+void persist_grant(const std::string& plugin_key, AuditEventCategory category, bool by_event, const std::vector<std::string>& keys)
 {
     PluginInstallState state;
     if (!PluginManager::instance().get_install_state(plugin_key, state))
         return;
 
-    std::vector<std::string>* permission_list = permission_list_for(category, state.permissions);
+    std::vector<std::string>* permission_list = permission_list_for(category, by_event, state.permissions);
     if (!permission_list)
         return;
 
-    for (const auto& target : targets)
+    for (const auto& key : keys)
-        persist_permission(plugin_key, state, *permission_list, target);
+        persist_permission(plugin_key, state, *permission_list, key);
 }
 
-// Requests permission for an audited event, returning true when it is already granted or the user
+static PluginAuditManager::PermissionPrompt s_permission_prompt_for_testing;
-// approves an inline prompt.
+
+// Asks the user to grant an audited event, returning true when they approve an inline prompt.
+// `keys` are what a Yes saves: the unresolved targets, or the event-grant key when the event has
+// no target (by_event), which the prompt does not show as a target.
 //
 // An audited event can fire on a thread the UI thread may itself be blocked waiting on: the
 // SlicingPipeline hook runs on the slicing worker thread (see PluginHooks.cpp), and
@@ -929,56 +1031,205 @@ void persist_grant(const std::string& plugin_key, AuditEventCategory category, c
 // prompt); the grant is persisted once the user accepts, so a later attempt succeeds without
 // re-prompting.
 bool request_permission(AuditEventCategory category, const std::string& plugin_key, const std::string& plugin_name,
-                        const std::string& event_name, const std::vector<std::string>& unresolved)
+                        const std::string& event_name, bool by_event, const std::vector<std::string>& keys)
 {
+    const std::vector<std::string> shown = by_event ? std::vector<std::string>{} : keys;
+
+    if (s_permission_prompt_for_testing)
+        return s_permission_prompt_for_testing(event_name, shown);
+
     if (wxTheApp == nullptr || GUI::wxGetApp().is_closing())
         return false;
 
     if (wxIsMainThread())
-        return prompt_for_targets(category, plugin_name, event_name, unresolved);
+        return prompt_for_targets(category, plugin_name, event_name, shown);
 
-    GUI::wxGetApp().CallAfter([category, plugin_key, plugin_name, event_name, unresolved]() {
+    GUI::wxGetApp().CallAfter([category, plugin_key, plugin_name, event_name, by_event, keys, shown]() {
         if (wxTheApp == nullptr || GUI::wxGetApp().is_closing())
             return;
-        if (prompt_for_targets(category, plugin_name, event_name, unresolved))
+        if (prompt_for_targets(category, plugin_name, event_name, shown))
-            persist_grant(plugin_key, category, unresolved);
+            persist_grant(plugin_key, category, by_event, keys);
     });
     return false;
 }
 
+// Decides an event that no allowed root or running operation covers: a saved grant allows it,
+// otherwise the user is asked and a Yes is saved.
 int decide_audited_event(PluginAuditManager&             mgr,
                          PluginInstallState&              state,
                          const std::string&                plugin_key,
                          const std::string&                plugin_name,
                          const std::string&                event_name,
                          AuditEventCategory                category,
-                         const std::vector<std::string>&   targets,
+                         const std::vector<std::string>&   targets)
-                         std::vector<std::string>*         permission_list,
-                         const std::vector<std::string>&   call_site_ids)
 {
-    std::vector<std::string> unresolved = targets;
+    const bool                     by_event = targets.empty();
+    const std::vector<std::string> keys     = by_event ? std::vector<std::string>{event_grant_key(category, event_name)} : targets;
+    std::vector<std::string>*      permission_list = permission_list_for(category, by_event, state.permissions);
+
+    std::vector<std::string> unresolved = keys;
     if (permission_list) {
         unresolved.clear();
-        for (const auto& target : targets)
+        for (const auto& key : keys)
-            if (!has_permission(*permission_list, target))
+            if (!has_permission(*permission_list, key))
-                unresolved.push_back(target);
+                unresolved.push_back(key);
-        if (!targets.empty() && unresolved.empty())
+        if (unresolved.empty())
             return 0;
     }
 
-    if (!request_permission(category, plugin_key, plugin_name, event_name, unresolved))
+    // Letting a root frame go runs finalizers inside a scope destructor or another event's hook,
+    // where no dialog may open: what they do must already be granted.
+    if (mgr.releasing_frames())
+        return report_denied(mgr, event_name, {false, "audit permission required"});
+
+    if (!request_permission(category, plugin_key, plugin_name, event_name, by_event, unresolved))
         return report_denied(mgr, event_name, {false, "audit permission required"});
 
     if (permission_list)
-        for (const auto& target : unresolved)
+        for (const auto& key : unresolved)
-            persist_permission(plugin_key, state, *permission_list, target);
+            persist_permission(plugin_key, state, *permission_list, key);
-
-    mgr.record_approved_call_sites(plugin_key, call_site_ids);
     return 0;
 }
 
+// Judges an audited event raised while a plugin context is active.
+int audit_plugin_event(PluginAuditManager& mgr, const std::string& event_name, AuditEventCategory event_type, PyObject* args)
+{
+    const bool                      fs_category = is_fs_category(event_type);
+    const std::vector<std::string>  targets      = audit_targets(event_name, event_type, args);
+
+    // A denied path (secrets, certificates, config files -- see is_denied_path) is an
+    // unconditional block: checked before the running-operation check below, so no granted
+    // operation can launder access to one, and before the allowed-root shortcut further down,
+    // so an allowed root (e.g. the read-only resources folder) cannot make a denied path
+    // underneath it reachable.
+    if (fs_category) {
+        for (const auto& target : targets) {
+            if (mgr.is_denied_path(boost::filesystem::path(target)))
+                return report_denied(mgr, event_name, {false, "denied path"}, target);
+        }
+    }
+
+    // A nested event of an operation already granted, e.g. socket.connect inside an approved
+    // urlopen(), is not asked again. urllib.Request is always judged on its own URL, so a
+    // redirect or a nested urlopen() inside a running request is not covered by it.
+    if (event_name != "urllib.Request" && mgr.covered_by_root_frame())
+        return 0;
+
+    // A filesystem target that resolves entirely inside a pre-determined allowed root -- the
+    // plugin system's own data_dir() tree (which holds each plugin's storage folder and the
+    // installed/system profile cache), the read-only bundled resources folder, or a per-call
+    // scoped root such as the current G-code folder -- is part of the plugin system's normal
+    // workflow and does not need a prompt.
+    if (fs_category && !targets.empty()) {
+        const bool is_write = event_type != AuditEventCategory::FsRead;
+        const bool all_inside_allowed_root =
+            std::all_of(targets.begin(), targets.end(), [&](const std::string& target) {
+                return mgr.check_path_access(boost::filesystem::path(target), is_write).allowed;
+            });
+        if (all_inside_allowed_root)
+            return 0;
+    }
+
+    PluginInstallState state;
+    const bool have_install_state = PluginManager::instance().get_install_state(mgr.current_plugin(), state);
+    if (!have_install_state) {
+        BOOST_LOG_TRIVIAL(warning) << __FUNCTION__ << " Failed to get install state for " << mgr.current_plugin();
+    }
+
+    const std::string plugin_name = state.plugin_name.empty() ? mgr.current_plugin() : state.plugin_name;
+
+    const int result = decide_audited_event(mgr, state, mgr.current_plugin(), plugin_name, event_name, event_type, targets);
+
+    // A granted operation covers its nested events while it runs. A targetless grant names no
+    // operation, so it covers nothing else.
+    if (result == 0 && !targets.empty() && operation_root_events.count(event_name))
+        mgr.record_root_frame();
+    return result;
+}
+
 } // namespace PluginAuditDetail
 
+void PluginAuditManager::record_root_frame()
+{
+    PyObject* frame = reinterpret_cast<PyObject*>(PyEval_GetFrame()); // borrowed reference
+    if (!frame || !PluginAuditDetail::is_stdlib_frame(frame))
+        return;
+    if (std::find(m_root_frames.begin(), m_root_frames.end(), frame) != m_root_frames.end())
+        return; // glob.glob and glob.glob/2 share a frame
+    Py_INCREF(frame);
+    m_root_frames.push_back(frame);
+}
+
+bool PluginAuditManager::covered_by_root_frame() const
+{
+    if (m_root_frames.empty())
+        return false;
+
+    // Only stdlib frames may sit between the event and the operation: plugin or library code
+    // the operation calls back into (an os.walk onerror, a urllib handler) acts on its own.
+    for (PyObject* frame : PluginAuditDetail::stack_frames()) {
+        if (std::find(m_root_frames.begin(), m_root_frames.end(), frame) != m_root_frames.end())
+            return true;
+        if (!PluginAuditDetail::is_stdlib_frame(frame))
+            return false;
+    }
+    return false;
+}
+
+bool PluginAuditManager::releasing_frames() const { return m_releasing_frames > 0; }
+
+bool PluginAuditManager::is_stdlib_file(const std::string& filename)
+{
+    // Frozen stdlib modules (os, posixpath, codecs, ...) carry a pseudo filename.
+    if (boost::algorithm::starts_with(filename, "<frozen "))
+        return true;
+    if (filename.empty() || filename.front() == '<')
+        return false;
+
+    // Both sides are resolved: co_filename follows the Python home as it was given, which may
+    // be a symlink.
+    const auto [it, inserted] = PluginAuditDetail::s_stdlib_file_verdicts.try_emplace(filename, false);
+    if (inserted) {
+        const boost::filesystem::path file(filename);
+        const auto inside_any = [&file](const std::vector<boost::filesystem::path>& dirs) {
+            return std::any_of(dirs.begin(), dirs.end(),
+                               [&file](const boost::filesystem::path& dir) { return is_inside_allowed_root(file, dir); });
+        };
+        it->second = inside_any(PluginAuditDetail::s_stdlib_dirs) && !inside_any(PluginAuditDetail::s_site_package_dirs);
+    }
+    return it->second;
+}
+
+void PluginAuditManager::release_frames(std::vector<PyObject*>& frames)
+{
+    if (frames.empty())
+        return;
+
+    // A finalizer's own denial must neither replace the PermissionError of the event being
+    // decided nor leave a stale denial behind for the next call.
+    PyObject* const      error          = PyErr_GetRaisedException();
+    const bool           denial_pending = m_audit_denial_pending;
+    const bool           has_violation  = m_has_last_violation;
+    const AuditViolation violation      = m_last_violation;
+
+    std::vector<PyObject*> released;
+    released.swap(frames);
+    ++m_releasing_frames;
+    for (PyObject* frame : released)
+        Py_DECREF(frame);
+    --m_releasing_frames;
+
+    m_audit_denial_pending = denial_pending;
+    m_has_last_violation   = has_violation;
+    m_last_violation       = violation;
+    PyErr_SetRaisedException(error);
+}
+
+void PluginAuditManager::set_permission_prompt_for_testing(PermissionPrompt prompt)
+{
+    PluginAuditDetail::s_permission_prompt_for_testing = std::move(prompt);
+}
+
 int PluginAuditManager::audit_hook(const char* event, PyObject* args, void* user_data)
 {
     auto* mgr = static_cast<PluginAuditManager*>(user_data);
@@ -1006,62 +1257,20 @@ int PluginAuditManager::audit_hook(const char* event, PyObject* args, void* user
     if (event_type == AuditEventCategory::None)
         return 0;
 
-    const bool                      fs_category = is_fs_category(event_type);
+    // Root frames whose operation has returned are let go once this event is decided, so that a
-    const std::vector<std::string>  targets      = PluginAuditDetail::audit_targets(event_name, event_type, args);
+    // finalizer they run re-enters a hook whose held frames are already consistent.
-
+    std::vector<PyObject*> returned_frames;
-    // A denied path (secrets, certificates, config files -- see is_denied_path) is an
+    PluginAuditDetail::take_returned_frames(m_root_frames, returned_frames);
-    // unconditional block: checked before the ancestor-cascade check below, so a cascade
+    const int result = PluginAuditDetail::audit_plugin_event(*mgr, event_name, event_type, args);
-    // approval recorded for an unrelated action can never launder access to one, and before
+    mgr->release_frames(returned_frames);
-    // the allowed-root shortcut further down, so an allowed root (e.g. the read-only resources
+    return result;
-    // folder) cannot make a denied path underneath it reachable.
-    if (fs_category) {
-        for (const auto& target : targets) {
-            if (mgr->is_denied_path(boost::filesystem::path(target)))
-                return PluginAuditDetail::report_denied(*mgr, event_name, {false, "denied path"}, target);
-        }
-    }
-
-    PluginDescriptor plugin_descriptor;
-    PluginManager::instance().try_get_plugin_descriptor(mgr->current_plugin(), plugin_descriptor);
-
-    // Some plugins call other audited events, e.g. urlib.request will call socket.connect. So this is so that if urlib.request
-    // was already approved, socket.connect won't trigger another permission dialog.
-    const std::vector<std::string> call_site_ids =
-        PluginAuditDetail::call_site_identities(plugin_descriptor.plugin_root);
-    if (mgr->has_approved_ancestor(mgr->current_plugin(), call_site_ids))
-        return 0;
-
-    // A filesystem target that resolves entirely inside a pre-determined allowed root -- the
-    // plugin system's own data_dir() tree (which holds each plugin's storage folder and the
-    // installed/system profile cache), the read-only bundled resources folder, or a per-call
-    // scoped root such as the current G-code folder -- is part of the plugin system's normal
-    // workflow and does not need a prompt.
-    if (fs_category && !targets.empty()) {
-        const bool is_write = event_type != AuditEventCategory::FsRead;
-        const bool all_inside_allowed_root =
-            std::all_of(targets.begin(), targets.end(), [&](const std::string& target) {
-                return mgr->check_path_access(boost::filesystem::path(target), is_write).allowed;
-            });
-        if (all_inside_allowed_root)
-            return 0;
-    }
-
-    PluginInstallState state;
-    const bool have_install_state = PluginManager::instance().get_install_state(mgr->current_plugin(), state);
-    if (!have_install_state) {
-        BOOST_LOG_TRIVIAL(warning) << __FUNCTION__ << " Failed to get install state for " << mgr->current_plugin();
-    }
-
-    const std::string plugin_name = state.plugin_name.empty() ? mgr->current_plugin() : state.plugin_name;
-
-    std::vector<std::string>* permission_list = PluginAuditDetail::permission_list_for(event_type, state.permissions);
-
-    return PluginAuditDetail::decide_audited_event(*mgr, state, mgr->current_plugin(), plugin_name, event_name,
-                                                    event_type, targets, permission_list, call_site_ids);
 }
 
 void PluginAuditManager::install_hook()
 {
+    // Tells the stdlib's own frames apart, for the operation-root frames (see record_root_frame).
+    PluginAuditDetail::collect_stdlib_dirs();
+
     // data_dir() is the primary globally-allowed root during plugin execution: read+write. It
     // covers the plugin system's own workflow needs -- each plugin's storage folder
     // (data_dir()/orca_plugins) and the installed/system profile cache (data_dir()/system) --
@@ -1076,8 +1285,9 @@ void PluginAuditManager::install_hook()
     // "cert" denied-path keyword seeded below.
     add_global_allowed_root(resources_dir(), /*allow_write=*/false);
 
-    // The user's app config and cloud credentials live directly inside data_dir(), so the
+    // The user's app config and cloud credentials live directly inside data_dir(), and plugin
-    // root just granted would otherwise expose them to any plugin.  Deny them by name.
+    // install state lives beneath it, so the root just granted would otherwise expose them to
+    // plugins. Deny them by name.
     //
     // Seeded here rather than by each secret's owner because install_hook() runs during lazy
     // interpreter init and therefore provably precedes any plugin bytecode, whereas

src/slic3r/plugin/PluginAuditManager.hpp

@@ -4,10 +4,9 @@
 // Via pybind11 so this file requests the same python3xx.lib as everything else.
 #include <boost/filesystem/path.hpp>
 #include <pybind11/conduit/wrap_include_python_h.h>
+#include <functional>
 #include <mutex>
 #include <string>
-#include <unordered_map>
-#include <unordered_set>
 #include <vector>
 
 #include <boost/filesystem.hpp>
@@ -144,15 +143,26 @@ public:
     void clear_last_violation();
     bool last_violation(AuditViolation& violation) const;
 
-    // --- call-site cascade cache ---
+    // --- operation-root frames ---
-    // A single plugin action often fires several nested CPython audit events as it passes
+    // One stdlib operation fires several nested audit events as it passes through lower layers:
-    // through stdlib layers (urllib.request calling http.client calling socket, for example).
+    // urlopen() raises urllib.Request, then http.client and socket events. When an operation's
-    // Once the user approves one event, every stdlib frame still on the stack for that call
+    // own root event is granted (by a saved grant or the user), the stdlib frame that raised it
-    // is recorded here by (filename, function, first line) identity. A later event whose own
+    // is held, and a later event whose stack reaches that frame through stdlib frames only is
-    // ancestor chain still contains one of those frames is the same logical action seen from
+    // part of the same operation, so it is allowed without a prompt of its own. Plugin or
-    // a deeper layer, so it is auto-approved instead of prompting again.
+    // library code the operation calls back into is judged on its own. A frame is let go once it
-    bool has_approved_ancestor(const std::string& plugin_key, const std::vector<std::string>& call_site_ids) const;
+    // returns, a suspended generator's (os.walk) when the audit scope ends. Letting a frame go may
-    void record_approved_call_sites(const std::string& plugin_key, const std::vector<std::string>& call_site_ids);
+    // run finalizers of objects its locals held; they are judged as the plugin and never prompt.
+    void record_root_frame();
+    bool covered_by_root_frame() const;
+    bool releasing_frames() const;
+
+    // True when code from `filename` (a code object's co_filename) is the interpreter's own
+    // stdlib: the only code a root frame's coverage passes through. Valid after install_hook().
+    static bool is_stdlib_file(const std::string& filename);
+
+    // Answers permission prompts in place of the dialog, for tests. Production never sets it.
+    using PermissionPrompt = std::function<bool(const std::string& event_name, const std::vector<std::string>& targets)>;
+    static void set_permission_prompt_for_testing(PermissionPrompt prompt);
 
     bool verbose_events = true;
 
@@ -163,24 +173,32 @@ private:
 
     static int audit_hook(const char* event, PyObject* args, void* user_data);
 
+    // Drops the references in `frames`, keeping the caller's error and denial state intact.
+    void release_frames(std::vector<PyObject*>& frames);
+
     static thread_local std::string                   m_current_plugin_key;
     static thread_local std::string                   m_current_capability_name;
     static thread_local std::vector<AllowedRoot>       m_scoped_allowed_roots;
+    static thread_local std::vector<PyObject*>         m_root_frames; // strong references
+    static thread_local int                            m_releasing_frames;
     static thread_local bool                           m_audit_denial_pending;
     static thread_local bool                           m_has_last_violation;
     static thread_local AuditViolation                 m_last_violation;
 
-    // mutable: is_denied_filename() and has_approved_ancestor() are const queries that must lock.
+    // mutable: is_denied_filename() is a const query that must lock.
     mutable std::mutex m_mutex;
     std::vector<AllowedRoot>             m_global_allowed_roots;
     std::vector<std::string>             m_denied_filenames;
     std::vector<std::string>             m_denied_path_keywords;
-    std::unordered_map<std::string, std::unordered_set<std::string>> m_approved_call_sites; // plugin_key -> call-site ids
 };
 
 // RAII guard that sets the current plugin key and capability name, restoring the previous
 // pair on scope exit. `capability_name` may be empty for calls that are not scoped to a
 // single capability.
+//
+// Each scope owns the root frames recorded inside it and lets them go, as its own plugin, before
+// restoring the outer context. That needs the GIL whenever a frame is still held, so construct
+// the scope after the GIL guard, to be destroyed before it.
 class ScopedPluginAuditContext
 {
 public:
@@ -194,9 +212,12 @@ public:
     ScopedPluginAuditContext& operator=(const ScopedPluginAuditContext&) = delete;
 
 private:
+    std::string                   m_plugin_key;
+    std::string                   m_capability;
     std::string                   m_previous_id;
     std::string                   m_previous_capability;
     std::vector<AllowedRoot>      m_previous_scoped_roots;
+    std::vector<PyObject*>        m_previous_root_frames;
 };
 
 } // namespace Slic3r

src/slic3r/plugin/PluginFsUtils.cpp

@@ -808,6 +808,7 @@ bool read_install_state(const boost::filesystem::path& plugin_dir, PluginInstall
             read_string_list("network_socket", parsed.permissions.network_socket);
             read_string_list("process", parsed.permissions.process);
             read_string_list("threading", parsed.permissions.threading);
+            read_string_list("events", parsed.permissions.events);
         }
 
         if (state.contains("enabled") && state["enabled"].is_boolean())
@@ -852,6 +853,7 @@ bool write_install_state(const boost::filesystem::path& plugin_dir, const Plugin
         {"network_socket", state.permissions.network_socket},
         {"process", state.permissions.process},
         {"threading", state.permissions.threading},
+        {"events", state.permissions.events},
     };
 
     nlohmann::json capabilities = nlohmann::json::array();

src/slic3r/plugin/PluginFsUtils.hpp

@@ -104,6 +104,8 @@ struct PluginPermissions
     std::vector<std::string> network_socket;
     std::vector<std::string> process;
     std::vector<std::string> threading;
+    // Grants for audit events that expose no target, keyed "<category>:<event>" (e.g. "Socket:socket.__new__").
+    std::vector<std::string> events;
 };
 
 struct PluginInstallState {

src/slic3r/plugin/PyPluginTrampoline.hpp

@@ -102,9 +102,9 @@ public:
     // mistake), both fall back to the base's empty object rather than writing `"cap_config": null`.
     nlohmann::json get_default_config() const override
     {
+        pybind11::gil_scoped_acquire gil;
         ORCA_PY_AUDIT_SCOPE();
         try {
-            pybind11::gil_scoped_acquire gil;
             pybind11::function override = pybind11::get_override(static_cast<const Base*>(this), "get_default_config");
             if (!override)
                 return Base::get_default_config();

src/slic3r/plugin/pluginTypes/printerAgent/PrinterAgentPluginCapabilityTrampoline.hpp

@@ -282,11 +282,11 @@ public:
     int request_bind_ticket(std::string* ticket) override
     {
         try {
-            ORCA_PY_AUDIT_SCOPE();
             ::Slic3r::PluginCapabilityInterface::RefCounter _orca_ref_counter(*this);
             ::Slic3r::PythonGILState gil;
             if (!gil)
                 throw std::runtime_error("Python interpreter is shutting down");
+            ORCA_PY_AUDIT_SCOPE();
             pybind11::function override =
                 pybind11::get_override(static_cast<const PrinterAgentPluginCapability*>(this), "request_bind_ticket");
             if (!override)

tests/libslic3r/CMakeLists.txt

@@ -42,6 +42,7 @@ add_executable(${_TEST_NAME}_tests
     test_fill_plane_path.cpp
     test_adaptive_infill_field.cpp
     test_geometry.cpp
+    test_kdtree.cpp
     test_imex_arrange.cpp
     test_imex_helpers.cpp
     test_imex_zones.cpp

tests/libslic3r/test_clipper_utils.cpp

@@ -7,11 +7,14 @@
 #include "libslic3r/libslic3r.h"
 #include <numeric>
 #include <iostream>
+#include <utility>
 #include <boost/filesystem.hpp>
 #include <utility>
 #include <vector>
+#include <cstdlib>
 
 #include <catch2/catch_test_macros.hpp>
+#include <catch2/generators/catch_generators.hpp>
 #include <catch2/catch_approx.hpp>
 #include "libslic3r/ClipperUtils.hpp"
 #include "libslic3r/ExPolygon.hpp"
@@ -300,3 +303,90 @@ TEST_CASE("Top level expolygons of an even-odd union", "[ClipperUtils]") {
     REQUIRE(area_sum == Catch::Approx(area(top_level) + area(nested)));
     REQUIRE(top_level_expolygons(reference).size() == 1);
 }
+
+// Rings flattened to x,y,x,y... and sorted, with each ring rotated to start at its lowest point: two
+// encodings of the same geometry compare equal however the pieces came back or wherever a ring started.
+static std::vector<std::vector<coord_t>> canonical_rings(const ExPolygons &expolygons)
+{
+    std::vector<std::vector<coord_t>> rings;
+    const auto add = [&rings](const Polygon &poly) {
+        if (poly.points.empty())
+            return;
+        Points pts = poly.points;
+        std::rotate(pts.begin(),
+                    std::min_element(pts.begin(), pts.end(), [](const Point &a, const Point &b) {
+                        return std::make_pair(a.x(), a.y()) < std::make_pair(b.x(), b.y());
+                    }),
+                    pts.end());
+        std::vector<coord_t> flat;
+        flat.reserve(pts.size() * 2);
+        for (const Point &p : pts) {
+            flat.emplace_back(p.x());
+            flat.emplace_back(p.y());
+        }
+        rings.emplace_back(std::move(flat));
+    };
+    for (const ExPolygon &expoly : expolygons) {
+        add(expoly.contour);
+        for (const Polygon &hole : expoly.holes)
+            add(hole);
+    }
+    std::sort(rings.begin(), rings.end());
+    return rings;
+}
+
+// The same rings, every coordinate within `tolerance`.
+static bool same_rings(const ExPolygons &a, const ExPolygons &b, coord_t tolerance)
+{
+    const std::vector<std::vector<coord_t>> ra = canonical_rings(a), rb = canonical_rings(b);
+    return std::equal(ra.begin(), ra.end(), rb.begin(), rb.end(), [tolerance](const std::vector<coord_t> &x, const std::vector<coord_t> &y) {
+        return std::equal(x.begin(), x.end(), y.begin(), y.end(), [tolerance](coord_t u, coord_t v) { return std::abs(u - v) <= tolerance; });
+    });
+}
+
+TEST_CASE("Tiled diff and intersection return the same polygons as the plain calls", "[ClipperUtils]") {
+    // A grid of disjoint framed squares, enough of them to be split into several tiles.
+    const int  n    = 40;
+    const coord_t cell = scaled<coord_t>(2.), side = scaled<coord_t>(1.5), frame = scaled<coord_t>(0.3);
+    ExPolygons subject;
+    for (int y = 0; y < n; ++ y)
+        for (int x = 0; x < n; ++ x) {
+            const Point o(x * cell, y * cell);
+            ExPolygon square(Polygon({ o, o + Point(side, 0), o + Point(side, side), o + Point(0, side) }));
+            Polygon hole({ o + Point(frame, frame), o + Point(frame, side - frame), o + Point(side - frame, side - frame), o + Point(side - frame, frame) });
+            square.holes.emplace_back(std::move(hole));
+            subject.emplace_back(std::move(square));
+        }
+    // Clip polygons crossing many squares, one of them large with holes of its own.
+    Polygons clip;
+    const coord_t span = n * cell;
+    for (int i = 0; i < 8; ++ i) {
+        const coord_t y0 = coord_t(i) * span / 8, y1 = y0 + scaled<coord_t>(0.9);
+        clip.emplace_back(Polygon({ Point(- cell, y0), Point(span, y0 + cell * 3), Point(span, y1 + cell * 3), Point(- cell, y1) }));
+    }
+    ExPolygon big(Polygon({ Point(span / 4, span / 4), Point(3 * span / 4, span / 4), Point(3 * span / 4, 3 * span / 4), Point(span / 4, 3 * span / 4) }));
+    for (int i = 0; i < 4; ++ i) {
+        const Point o(span / 4 + scaled<coord_t>(3.1) + i * scaled<coord_t>(9.7), span / 4 + scaled<coord_t>(5.3));
+        big.holes.emplace_back(Polygon({ o, o + Point(0, scaled<coord_t>(20.)), o + Point(scaled<coord_t>(5.), scaled<coord_t>(20.)), o + Point(scaled<coord_t>(5.), 0) }));
+    }
+    polygons_append(clip, to_polygons(big));
+
+    const ApplySafetyOffset safety = GENERATE(ApplySafetyOffset::No, ApplySafetyOffset::Yes);
+
+    // The point of the fixture: below 128 pieces the helpers fall back to a single tile and the tiled
+    // path under test is never taken.
+    REQUIRE(ClipperUtils::tile_expolygons(subject, 32).size() > 1);
+
+    // With the safety offset a tile unites fewer clip polygons, so Clipper2 can round a crossing 1 unit differently.
+    const coord_t tolerance = safety == ApplySafetyOffset::Yes ? 1 : 0;
+
+    const ExPolygons diff_plain = diff_ex(subject, clip, safety);
+    const ExPolygons diff_tiled = diff_ex_by_piece(subject, clip, safety);
+    REQUIRE(area(diff_plain) > 0.);
+    CHECK(same_rings(diff_tiled, diff_plain, tolerance));
+
+    const ExPolygons intersection_plain = intersection_ex(subject, clip, safety);
+    const ExPolygons intersection_tiled = intersection_ex_by_piece(subject, clip, safety);
+    REQUIRE(area(intersection_plain) > 0.);
+    CHECK(same_rings(intersection_tiled, intersection_plain, tolerance));
+}

tests/libslic3r/test_config.cpp

@@ -1263,6 +1263,55 @@ TEST_CASE("read_cli rejects an invalid scalar numeric value", "[Config]") {
     REQUIRE_FALSE(config.read_cli(3, argv, &extra, &keys));
 }
 
+TEST_CASE("A scalar option keeps its value when deserializing fails", "[Config]") {
+    using Catch::Matchers::WithinAbs;
+
+    SECTION("float") {
+        ConfigOptionFloat opt(7.5);
+        REQUIRE_FALSE(opt.deserialize("abc"));
+        CHECK_THAT(opt.value, WithinAbs(7.5, 1e-9));
+    }
+    SECTION("int") {
+        ConfigOptionInt opt(3);
+        REQUIRE_FALSE(opt.deserialize("abc"));
+        CHECK(opt.value == 3);
+    }
+    SECTION("percent") {
+        ConfigOptionPercent opt(40.);
+        REQUIRE_FALSE(opt.deserialize("abc%"));
+        CHECK_THAT(opt.value, WithinAbs(40., 1e-9));
+    }
+    SECTION("float or percent") {
+        ConfigOptionFloatOrPercent opt(0.4, false);
+        REQUIRE_FALSE(opt.deserialize("abc%"));
+        CHECK_THAT(opt.value, WithinAbs(0.4, 1e-9));
+        CHECK_FALSE(opt.percent);
+    }
+    SECTION("point") {
+        ConfigOptionPoint opt(Vec2d(1., 2.));
+        REQUIRE_FALSE(opt.deserialize("5,abc"));
+        CHECK(opt.value == Vec2d(1., 2.));
+    }
+    SECTION("point3") {
+        ConfigOptionPoint3 opt(Vec3d(1., 2., 3.));
+        REQUIRE_FALSE(opt.deserialize("5,6,abc"));
+        CHECK(opt.value == Vec3d(1., 2., 3.));
+    }
+}
+
+TEST_CASE("A scalar option still takes a valid value", "[Config]") {
+    using Catch::Matchers::WithinAbs;
+
+    ConfigOptionFloatOrPercent opt(0.4, false);
+    REQUIRE(opt.deserialize("50%"));
+    CHECK_THAT(opt.value, WithinAbs(50., 1e-9));
+    CHECK(opt.percent);
+
+    ConfigOptionPoint point;
+    REQUIRE(point.deserialize("3x4"));
+    CHECK(point.value == Vec2d(3., 4.));
+}
+
 TEST_CASE("read_cli appends values when a vector option is repeated", "[Config]") {
     Slic3r::DynamicPrintConfig config;
     t_config_option_keys extra, keys;
@@ -1678,3 +1727,75 @@ TEST_CASE("Default options of enum lists get their definition's keys map", "[Con
     }
     CHECK(enum_lists > 0);
 }
+
+TEST_CASE("A disabled filament override survives the merge with a parent that sets it", "[Config][Variant]")
+{
+    std::set<std::string>      no_keys;
+    Slic3r::DynamicPrintConfig parent;
+    parent.set_deserialize_strict("filament_retract_before_wipe", "100%");
+    parent.set_deserialize_strict("filament_ironing_flow", "15%");
+    Slic3r::DynamicPrintConfig child;
+    child.set_deserialize_strict("filament_retract_before_wipe", "nil");
+    child.set_deserialize_strict("filament_ironing_flow", "nil");
+    parent.update_diff_values_to_child_config(child, "", "filament_extruder_variant",
+                                              Slic3r::filament_options_with_variant, no_keys);
+    CHECK(parent.opt_serialize("filament_retract_before_wipe") == "nil");
+    CHECK(parent.opt_serialize("filament_ironing_flow") == "nil");
+}
+
+SCENARIO("A two-variant child's disabled override column is matched to the parent's variant by name", "[Config][Variant]")
+{
+    std::set<std::string> no_keys;
+    GIVEN("A two-variant filament parent") {
+        Slic3r::DynamicPrintConfig parent;
+        parent.set_deserialize_strict("filament_extruder_variant", "Direct Drive Standard;Direct Drive High Flow");
+        parent.set_deserialize_strict("filament_retract_before_wipe", "100%,100%");
+        parent.set_deserialize_strict("filament_flow_ratio", "1,1");
+        WHEN("the child disables the override on one variant and leaves a plain option nil on it") {
+            Slic3r::DynamicPrintConfig child;
+            child.set_deserialize_strict("filament_extruder_variant", "Direct Drive Standard;Direct Drive High Flow");
+            child.set_deserialize_strict("filament_retract_before_wipe", "nil,100%");
+            child.set_deserialize_strict("filament_flow_ratio", "nil,1.1");
+            parent.update_diff_values_to_child_config(child, "", "filament_extruder_variant",
+                                                      Slic3r::filament_options_with_variant, no_keys);
+            THEN("the override column is disabled while the plain option's nil column inherits") {
+                CHECK(parent.opt_serialize("filament_retract_before_wipe") == "nil,100%");
+                CHECK(parent.opt_serialize("filament_flow_ratio") == "1,1.1");
+            }
+        }
+        WHEN("the child lists the same variants in the other order") {
+            Slic3r::DynamicPrintConfig child;
+            child.set_deserialize_strict("filament_extruder_variant", "Direct Drive High Flow;Direct Drive Standard");
+            child.set_deserialize_strict("filament_retract_before_wipe", "70%,nil");
+            child.set_deserialize_strict("filament_flow_ratio", "1.1,nil");
+            parent.update_diff_values_to_child_config(child, "", "filament_extruder_variant",
+                                                      Slic3r::filament_options_with_variant, no_keys);
+            THEN("columns are matched by variant name, the disabled one included") {
+                CHECK(parent.opt_serialize("filament_retract_before_wipe") == "nil,70%");
+                CHECK(parent.opt_serialize("filament_flow_ratio") == "1,1.1");
+            }
+        }
+        WHEN("the child was saved with a single variant") {
+            Slic3r::DynamicPrintConfig child;
+            child.set_deserialize_strict("filament_extruder_variant", "Direct Drive Standard");
+            child.set_deserialize_strict("filament_retract_before_wipe", "nil");
+            parent.update_diff_values_to_child_config(child, "", "filament_extruder_variant",
+                                                      Slic3r::filament_options_with_variant, no_keys);
+            THEN("its one value applies to every variant of that extruder, as slicing does") {
+                CHECK(parent.opt_serialize("filament_retract_before_wipe") == "nil,nil");
+            }
+        }
+    }
+}
+
+TEST_CASE("Every listed filament override is nullable", "[Config]")
+{
+    std::set<std::string> overrides(Slic3r::filament_extruder_override_keys.begin(), Slic3r::filament_extruder_override_keys.end());
+    overrides.insert({ "filament_retract_length_nc", "filament_ironing_flow", "filament_ironing_spacing", "filament_ironing_inset", "filament_ironing_speed" });
+    for (const auto &[key, def] : Slic3r::print_config_def.options) {
+        INFO(key);
+        CHECK(Slic3r::is_filament_extruder_override_key(key) == (overrides.count(key) == 1));
+        if (overrides.count(key) == 1)
+            CHECK(def.nullable);
+    }
+}

tests/libslic3r/test_kdtree.cpp

@@ -0,0 +1,72 @@
+#include <catch2/catch_all.hpp>
+
+#include <numeric>
+#include <random>
+#include <vector>
+#include <algorithm>
+#include <cstddef>
+
+#include <catch2/catch_test_macros.hpp>
+#include <catch2/generators/catch_generators.hpp>
+
+#include "libslic3r/KDTreeIndirect.hpp"
+#include "libslic3r/Point.hpp"
+
+using namespace Slic3r;
+
+TEST_CASE("Visiting the nearby points gives what collecting them gives", "[KDTree]") {
+    std::mt19937                          rng(19937);
+    std::uniform_real_distribution<float> coord(-50.f, 50.f);
+    // Points in a box, so that a radius search returns anything from none of them to all of them.
+    std::vector<Vec3f> points(2000);
+    for (Vec3f &p : points)
+        p = Vec3f(coord(rng), coord(rng), coord(rng));
+
+    auto coordinate = [&points](size_t idx, size_t dimension) { return points[idx](int(dimension)); };
+    KDTreeIndirect<3, float, decltype(coordinate)> tree(coordinate);
+    std::vector<size_t> indices(points.size());
+    std::iota(indices.begin(), indices.end(), 0);
+    tree.build(indices);
+
+    const float radius = GENERATE(0.5f, 5.f, 25.f, 200.f);
+    for (int i = 0; i < 20; ++ i) {
+        const Vec3f center(coord(rng), coord(rng), coord(rng));
+
+        const std::vector<size_t> collected = find_nearby_points(tree, center, radius);
+        std::vector<size_t>       visited;
+        visit_nearby_points(tree, center, radius, [&visited](size_t idx) { visited.emplace_back(idx); });
+
+        // Same points, and in the same order: a caller that keeps the first of several equally good ones
+        // must get the same answer either way.
+        REQUIRE(visited == collected);
+    }
+}
+
+TEST_CASE("A radius search returns every point within the radius and no other", "[KDTree]") {
+    std::mt19937                          rng(2024);
+    std::uniform_real_distribution<float> coord(-20.f, 20.f);
+    std::vector<Vec3f> points(500);
+    for (Vec3f &p : points)
+        p = Vec3f(coord(rng), coord(rng), coord(rng));
+
+    auto coordinate = [&points](size_t idx, size_t dimension) { return points[idx](int(dimension)); };
+    KDTreeIndirect<3, float, decltype(coordinate)> tree(coordinate);
+    std::vector<size_t> indices(points.size());
+    std::iota(indices.begin(), indices.end(), 0);
+    tree.build(indices);
+
+    const Vec3f center(1.f, -2.f, 3.f);
+    const float radius = 7.f;
+
+    std::vector<size_t> expected;
+    for (size_t i = 0; i < points.size(); ++ i)
+        if ((points[i] - center).squaredNorm() < radius * radius)
+            expected.emplace_back(i);
+
+    std::vector<size_t> visited;
+    visit_nearby_points(tree, center, radius, [&visited](size_t idx) { visited.emplace_back(idx); });
+    std::sort(visited.begin(), visited.end());
+
+    REQUIRE(! expected.empty());
+    REQUIRE(visited == expected);
+}

tests/libslic3r/test_preset_bundle_loading.cpp

@@ -8417,3 +8417,58 @@ TEST_CASE("An empty choice list in a G-code's settings keeps the value it had be
     CHECK(config.opt_serialize("nozzle_volume_type") == "High Flow");
     CHECK(config.option<ConfigOptionStrings>("filament_multi_colour")->values.empty());
 }
+
+TEST_CASE("A disabled filament override is saved and reloaded column by column", "[Preset][Bundle]")
+{
+    ScopedPresetDataDir data_dir;
+    PresetBundle        bundle;
+
+    Preset &parent = add_inmemory_preset(bundle.filaments, "Parent PLA @System");
+    parent.config.option<ConfigOptionStrings>("filament_extruder_variant", true)->values = { "Direct Drive Standard", "Direct Drive High Flow" };
+    parent.config.option<ConfigOptionPercentsNullable>("filament_retract_before_wipe", true)->values = { 100., 100. };
+    parent.config.option<ConfigOptionFloatsNullable>("filament_flow_ratio", true)->values = { 1., 1. };
+
+    // The child turns the override off on the first variant and changes a plain option on the second.
+    const fs::path file = data_dir.tmp.path() / PRESET_FILAMENT_NAME / "Child PLA.json";
+    Preset         child(Preset::TYPE_FILAMENT, "Child PLA");
+    child.file    = file.string();
+    child.version = *Semver::parse("1.0.0");
+    child.config  = parent.config;
+    child.config.option<ConfigOptionString>(BBL_JSON_KEY_INHERITS, true)->value = parent.name;
+    child.config.option<ConfigOptionPercentsNullable>("filament_retract_before_wipe")->set_at_to_nil(0);
+    child.config.option<ConfigOptionFloatsNullable>("filament_flow_ratio")->values = { 1., 1.1 };
+    REQUIRE(child.save(&parent.config));
+
+    // On disk the override keeps every column, so its nil can only mean "off"; a plain
+    // option still stores nil for the columns that match the parent.
+    DynamicPrintConfig                 saved;
+    std::map<std::string, std::string> key_values;
+    std::string                        reason;
+    saved.load_from_json(file.string(), ForwardCompatibilitySubstitutionRule::EnableSilent, key_values, reason);
+    REQUIRE(reason.empty());
+    CHECK(saved.opt_serialize("filament_retract_before_wipe") == "nil,100%");
+    CHECK(saved.opt_serialize("filament_flow_ratio") == "nil,1.1");
+
+    PresetsConfigSubstitutions substitutions;
+    bundle.filaments.load_presets(data_dir.tmp.path().string(), PRESET_FILAMENT_NAME, substitutions,
+                                  ForwardCompatibilitySubstitutionRule::EnableSilent);
+    const Preset *loaded = bundle.filaments.find_preset("Child PLA");
+    REQUIRE(loaded != nullptr);
+    CHECK(loaded->config.opt_serialize("filament_retract_before_wipe") == "nil,100%");
+    CHECK(loaded->config.opt_serialize("filament_flow_ratio") == "1,1.1");
+}
+
+TEST_CASE("The cloud diff force-emits a disabled override only where the cloud would fill a value in", "[Preset][Bundle]")
+{
+    PresetBundle bundle;
+    add_inmemory_preset(bundle.filaments, "Parent PLA @System");
+    Preset &child = add_inmemory_preset(bundle.filaments, "Child PLA", "Parent PLA @System");
+    // Every override is nil in both parent and child, so none is in the plain diff.
+    std::map<std::string, std::string> key_values;
+    REQUIRE(bundle.filaments.get_differed_values_to_update(child, key_values) >= 0);
+    // Retract Before Wipe defaults to 100%: an absent key would come back as 100%, so nil is sent.
+    CHECK(key_values.count("filament_retract_before_wipe") == 1);
+    CHECK(key_values["filament_retract_before_wipe"] == "nil");
+    // An ironing override defaults to nil: an absent key stays nil, so it is not sent.
+    CHECK(key_values.count("filament_ironing_flow") == 0);
+}

tests/slic3rutils/test_plugin_audit.cpp

@@ -1,22 +1,48 @@
 #include <boost/filesystem/path.hpp>
 #include <boost/filesystem/operations.hpp>
+#include <boost/system/error_code.hpp>
 #include <catch2/catch_all.hpp>
 
 #include <libslic3r/Utils.hpp>
 #include <libslic3r/libslic3r.h>         // GCODEVIEWER_APP_KEY, SLIC3R_APP_KEY (via libslic3r_version.h)
 #include <slic3r/plugin/PluginAuditManager.hpp>
+#include <slic3r/plugin/PluginFsUtils.hpp>
+#include <slic3r/plugin/PluginManager.hpp>
+#include <slic3r/plugin/PythonInterpreter.hpp>
+#include <slic3r/plugin/PythonPluginBridge.hpp>
+#include <slic3r/plugin/PythonPluginInterface.hpp>
+#include <slic3r/Utils/IPrinterAgent.hpp>
 #include <slic3r/Utils/OrcaCloudServiceAgent.hpp> // secret_constants::USER_SECRET_FILENAME
 
+#include <catch2/catch_message.hpp>
 #include <catch2/catch_test_macros.hpp>
+#include <catch2/matchers/catch_matchers.hpp>
+#include <catch2/matchers/catch_matchers_string.hpp>
 #include "libslic3r_version.h"
 #include "plugin_test_utils.hpp"
+#include "test_utils.hpp"
 
 #include <boost/filesystem.hpp>
+#include <nlohmann/json.hpp>
+#include <pybind11/cast.h>
+#include <pybind11/embed.h>
+#include <pybind11/eval.h>
+#include <pybind11/gil.h>
+#include <pybind11/pybind11.h>
+#include <pybind11/pytypes.h>
+#include <pybind11/stl.h>
 
+#include <fstream>
+#include <functional>
+#include <ios>
+#include <memory>
 #include <string>
+#include <utility>
+#include <vector>
 
 using namespace Slic3r;
 namespace fs = boost::filesystem;
+namespace py = pybind11;
 
 namespace {
 
@@ -43,7 +69,7 @@ void seed_denied_keywords()
 
 } // namespace
 
-TEST_CASE("Plugin audit denies app config and token filenames anywhere", "[audit]")
+TEST_CASE("Plugin audit denies host-managed filenames anywhere", "[audit]")
 {
     seed_denied_names();
     const PluginAuditManager& mgr = PluginAuditManager::instance();
@@ -55,6 +81,7 @@ TEST_CASE("Plugin audit denies app config and token filenames anywhere", "[audit
         CHECK(mgr.is_denied_filename(fs::path(SLIC3R_APP_KEY ".ini")));
         CHECK(mgr.is_denied_filename(fs::path(GCODEVIEWER_APP_KEY ".ini")));
         CHECK(mgr.is_denied_filename(fs::path(secret_constants::USER_SECRET_FILENAME)));
+        CHECK(mgr.is_denied_filename(fs::path(".install_state.json")));
     }
 
     SECTION("companions holding the same secrets are denied by the prefix rule")
@@ -110,6 +137,7 @@ TEST_CASE("Plugin audit deny beats allowed roots", "[audit]")
 
     const fs::path conf  = fs::path(data_dir()) / (SLIC3R_APP_KEY ".conf");
     const fs::path token = fs::path(data_dir()) / secret_constants::USER_SECRET_FILENAME;
+    const fs::path install_state = fs::path(data_dir()) / "plugins" / "example" / ".install_state.json";
 
     SECTION("a non-denied file inside the allowed root is writable (root really grants writes)")
     {
@@ -150,6 +178,17 @@ TEST_CASE("Plugin audit deny beats allowed roots", "[audit]")
         CHECK_FALSE(decision.allowed);
     }
 
+    SECTION("plugin install state is blocked for reads and writes despite the allowed root")
+    {
+        AuditDecision read_decision = mgr.check_open(install_state.string(), "r");
+        CHECK_FALSE(read_decision.allowed);
+        CHECK(read_decision.reason == "denied filename");
+
+        AuditDecision write_decision = mgr.check_open(install_state.string(), "w");
+        CHECK_FALSE(write_decision.allowed);
+        CHECK(write_decision.reason == "denied filename");
+    }
+
     SECTION("a traversal path resolving to the config is blocked")
     {
         const fs::path traversal = fs::path(data_dir()) / "plugins" / ".." / (SLIC3R_APP_KEY ".conf");
@@ -349,3 +388,747 @@ TEST_CASE("Plugin audit a scoped root can also be registered read-only", "[audit
         CHECK_FALSE(mgr.check_open((readonly_dir / "vendor.json").string(), "w").allowed);
     }
 }
+
+// ---------------------------------------------------------------------------
+// The audit hook, run in the embedded interpreter
+// ---------------------------------------------------------------------------
+//
+// Each TEST_CASE runs in its own process (catch_discover_tests), so each brings the plugin system
+// up with the audit hook installed, once, and shuts it down at the end. The tests loop over their
+// cases instead of using SECTIONs, which would restart the interpreter for every section.
+
+namespace {
+
+// Discovered, never loaded: the hook only needs the plugin's root and its sidecar.
+const char* const AUDIT_PLUGIN_SOURCE = R"PY(# /// script
+# requires-python = ">=3.12"
+#
+# [tool.orcaslicer.plugin]
+# name = "Audit Plugin"
+# description = "Plugin audit hook fixture"
+# author = "OrcaSlicer"
+# version = "1.0"
+# type = "script"
+# ///
+)PY";
+
+// A third-party library, installed outside the stdlib and outside the plugin.
+const char* const LIBRARY_SOURCE = R"PY(
+import socket
+import urllib.request
+
+def read_all(paths):
+    for path in paths:
+        with open(path) as f:
+            f.read()
+
+def connect_from_host(port):
+    socket.gethostname()
+    socket.create_connection(("127.0.0.1", port)).close()
+
+def fetch(url):
+    with urllib.request.urlopen(url) as response:
+        return response.read()
+
+def fetch_each(urls):
+    for url in urls:
+        yield fetch(url)
+
+class ReadingHandler(urllib.request.BaseHandler):
+    """Reads a file while each response is processed."""
+    def __init__(self, path):
+        self.path = path
+        self.outcome = None
+
+    def http_response(self, request, response):
+        try:
+            open(self.path).close()
+            self.outcome = "ok"
+        except PermissionError:
+            self.outcome = "denied"
+        return response
+)PY";
+
+// Test-side Python, run outside any plugin context: files outside every allowed root, a local
+// HTTP server, the library, and every module the tests use imported up front, so that no import
+// happens inside a plugin context. Code from exec() runs as "<string>", which is not stdlib, so
+// attempt() and fetch() stand in for plugin code.
+const char* const AUDIT_SETUP = R"PY(
+import http.client, http.server, os, pathlib, shutil, socket, subprocess, sys, tempfile, threading
+import urllib.request, zipfile
+if os.name != "nt":
+    import pty
+
+APPROVED = os.path.join(OUTSIDE, "approved.txt")
+PRIVATE = os.path.join(OUTSIDE, "private.txt")
+MISSING = os.path.join(OUTSIDE, "missing")
+TREE = os.path.join(OUTSIDE, "tree")
+TRUE_COMMAND = ["cmd", "/c", "exit 0"] if os.name == "nt" else ["true"]
+for path in (APPROVED, PRIVATE):
+    with open(path, "w") as f:
+        f.write("x")
+for sub in ("one", "two"):
+    os.makedirs(os.path.join(TREE, sub))
+    with open(os.path.join(TREE, sub, "f.txt"), "w") as f:
+        f.write("x")
+
+LIBRARY = os.path.join(OUTSIDE, "library")
+os.makedirs(LIBRARY)
+with open(os.path.join(LIBRARY, "netlib.py"), "w") as f:
+    f.write(LIBRARY_SOURCE)
+sys.path.insert(0, LIBRARY)
+import netlib
+
+class Handler(http.server.BaseHTTPRequestHandler):
+    def do_GET(self):
+        if self.path == "/redirect":
+            self.send_response(302)
+            self.send_header("Location", URL_B)
+            body = b""
+        else:
+            self.send_response(200)
+            body = b"ok"
+        self.send_header("Content-Length", str(len(body)))
+        self.end_headers()
+        self.wfile.write(body)
+
+    def log_message(self, *args):
+        pass
+
+server = http.server.ThreadingHTTPServer(("127.0.0.1", 0), Handler)
+threading.Thread(target=server.serve_forever, daemon=True).start()
+PORT = server.server_address[1]
+BASE = "http://127.0.0.1:%d" % PORT
+URL_A, URL_B, URL_REDIRECT = BASE + "/a", BASE + "/b", BASE + "/redirect"
+urllib.request.install_opener(urllib.request.build_opener(urllib.request.ProxyHandler({})))
+
+def fetch(url):
+    with urllib.request.urlopen(url) as response:
+        return response.read()
+
+fetch(URL_A)  # urllib imports some modules on its first request
+
+def attempt(action):
+    try:
+        action()
+        return "ok"
+    except PermissionError:
+        return "denied"
+
+def spawn_checked(argv):
+    parent = os.getpid()
+    try:
+        return pty.spawn(argv)
+    finally:
+        if os.getpid() != parent:
+            os._exit(1)  # a child whose exec was refused must not go on running the tests
+
+finalizer_outcomes = []
+
+class TrackedRequest(urllib.request.Request):
+    def __del__(self):
+        finalizer_outcomes.append(attempt(lambda: open(PRIVATE).close()))
+)PY";
+
+struct Prompt
+{
+    std::string              plugin;
+    std::string              event;
+    std::vector<std::string> targets;
+};
+
+// One line per prompt, "event: target ...", so a failed check shows every prompt.
+std::string describe(const std::vector<Prompt>& prompts)
+{
+    std::string text;
+    for (const Prompt& prompt : prompts) {
+        text += prompt.event + ":";
+        for (const std::string& target : prompt.targets)
+            text += " " + target;
+        text += "\n";
+    }
+    return text;
+}
+
+// The plugin system with the audit hook installed, and the permission dialog replaced by a
+// recorder that answers with `approve`. Declare it first in a test, so it is destroyed last.
+struct AuditHarness
+{
+    // Before initialize(): the interpreter creates {data_dir}/python/packages and {data_dir}/log.
+    // data_dir() is a global allowed root from then on, so the test files live in `outside`.
+    ScopedDataDir                      data{"plugin-audit-hook"};
+    bool                               initialized = PluginManager::instance().initialize();
+    ScopedTemporaryDir                 outside{"orca-plugin-audit-outside"};
+    std::vector<Prompt>                prompts;
+    std::function<bool(const Prompt&)> approve = [](const Prompt&) { return false; };
+
+    AuditHarness()
+    {
+        PluginAuditManager::set_permission_prompt_for_testing(
+            [this](const std::string& event, const std::vector<std::string>& targets) {
+                prompts.push_back({PluginAuditManager::instance().current_plugin(), event, targets});
+                return approve(prompts.back());
+            });
+    }
+
+    ~AuditHarness()
+    {
+        PluginAuditManager::set_permission_prompt_for_testing(nullptr);
+        PluginManager::instance().shutdown();
+        PythonInterpreter::instance().shutdown();
+    }
+
+    // Call before taking the GIL: discovery is not Python work.
+    void add_plugin(const std::string& key)
+    {
+        const fs::path root = data.plugins_dir() / key;
+        fs::create_directories(root);
+        std::ofstream((root / (key + ".py")).string(), std::ios::binary) << AUDIT_PLUGIN_SOURCE;
+        save_permissions(key, {});
+        PluginManager::instance().discover_plugins(/*async=*/false, /*clear=*/true);
+    }
+
+    // Grants as if saved in an earlier session.
+    void save_permissions(const std::string& key, const PluginPermissions& permissions)
+    {
+        PluginInstallState state;
+        state.installed_from    = "local";
+        state.installed_version = "1.0";
+        state.plugin_name       = key;
+        state.permissions       = permissions;
+        REQUIRE(write_install_state(data.plugins_dir() / key, state));
+    }
+
+    PluginPermissions saved_permissions(const std::string& key) const
+    {
+        PluginInstallState state;
+        read_install_state(data.plugins_dir() / key, state);
+        return state.permissions;
+    }
+};
+
+// The test-side Python globals. Construct and destroy it with the GIL held; it stops the HTTP
+// server before the interpreter shuts down.
+struct PythonSide
+{
+    py::dict globals;
+
+    explicit PythonSide(const AuditHarness& harness)
+    {
+        globals["OUTSIDE"]        = harness.outside.path().string();
+        globals["LIBRARY_SOURCE"] = LIBRARY_SOURCE;
+        exec(AUDIT_SETUP);
+    }
+
+    // A Python error fails the test here, as text: an error_already_set left to propagate would
+    // outlive the interpreter the harness shuts down.
+    void exec(const char* code)
+    {
+        std::string error;
+        try {
+            py::exec(code, globals);
+        } catch (py::error_already_set& raised) {
+            error = raised.what();
+        }
+        if (!error.empty())
+            FAIL(error);
+    }
+
+    ~PythonSide()
+    {
+        try {
+            globals["server"].attr("shutdown")();
+            globals["server"].attr("server_close")();
+        } catch (...) {
+        }
+    }
+
+    std::string              str(const char* name) const { return py::str(globals[name]).cast<std::string>(); }
+    std::string              eval(const char* expression) const { return py::str(py::eval(expression, globals)).cast<std::string>(); }
+    std::vector<std::string> strings(const char* name) const { return globals[name].cast<std::vector<std::string>>(); }
+
+    // Runs `code` as `plugin_key`, as a trampoline call does: inside the caller's GIL, in an
+    // audit scope of its own.
+    void run_as(const std::string& plugin_key, const char* code)
+    {
+        ScopedPluginAuditContext audit(plugin_key);
+        exec(code);
+    }
+};
+
+PluginPermissions http_grants(std::vector<std::string> urls)
+{
+    PluginPermissions permissions;
+    permissions.network_http = std::move(urls);
+    return permissions;
+}
+
+const char* const PLUGIN = "AuditPlugin";
+
+} // namespace
+
+TEST_CASE("A saved request grant covers the request's own connection in a later session", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    harness.save_permissions(PLUGIN, http_grants({python.str("URL_A")}));
+
+    python.run_as(PLUGIN, "outcome = attempt(lambda: fetch(URL_A))");
+
+    CHECK(python.str("outcome") == "ok");
+    CHECK(describe(harness.prompts).empty());
+}
+
+TEST_CASE("A saved request grant does not cover another URL or a redirect", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    harness.save_permissions(PLUGIN, http_grants({python.str("URL_A"), python.str("URL_REDIRECT")}));
+
+    python.run_as(PLUGIN, R"PY(
+outcomes = [attempt(lambda: fetch(url)) for url in (URL_A, URL_B, URL_REDIRECT)]
+outcomes += [attempt(lambda: netlib.fetch(url)) for url in (URL_A, URL_B)]
+outcomes.append(attempt(lambda: list(netlib.fetch_each([URL_A, URL_B]))))
+)PY");
+
+    // The redirect target is asked for inside the approved redirecting request, and a library's
+    // wrapper or generator asks for the second URL as plain code does.
+    CHECK(python.strings("outcomes") == std::vector<std::string>{"ok", "denied", "denied", "ok", "denied", "denied"});
+    const std::string url_b = "urllib.Request: " + python.str("URL_B") + "\n";
+    CHECK(describe(harness.prompts) == url_b + url_b + url_b + url_b);
+}
+
+TEST_CASE("Code an approved operation calls back into is judged on its own", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    python.exec(R"PY(
+CALLBACK_COPY = os.path.join(OUTSIDE, "callback-copy")
+handler = netlib.ReadingHandler(PRIVATE)
+handler_opener = urllib.request.build_opener(urllib.request.ProxyHandler({}), handler)
+walk_outcomes = []
+copy_outcomes = []
+
+def on_walk_error(error):
+    walk_outcomes.append(attempt(lambda: open(PRIVATE).close()))
+
+def copy_file(source, destination):
+    copy_outcomes.append(attempt(lambda: open(PRIVATE).close()))
+)PY");
+    PluginPermissions permissions = http_grants({python.str("URL_A")});
+    permissions.fs_read           = {python.str("APPROVED"), python.str("MISSING")};
+    permissions.fs_readwrite      = {python.str("TREE"), python.str("CALLBACK_COPY")};
+    harness.save_permissions(PLUGIN, permissions);
+
+    // A library handler that urllib calls while the approved request runs, the plugin's own
+    // os.walk error callback and copytree copy function (called once per file), and a library
+    // loop over a saved file and an unsaved one.
+    python.run_as(PLUGIN, R"PY(
+request_outcome = attempt(lambda: handler_opener.open(URL_A).read())
+for _ in os.walk(MISSING, onerror=on_walk_error):
+    pass
+shutil.copytree(TREE, CALLBACK_COPY, copy_function=copy_file)
+loop_outcome = attempt(lambda: netlib.read_all([APPROVED, PRIVATE]))
+)PY");
+
+    CHECK(python.str("request_outcome") == "ok");
+    CHECK(python.eval("handler.outcome") == "denied");
+    CHECK(python.strings("walk_outcomes") == std::vector<std::string>{"denied"});
+    CHECK(python.strings("copy_outcomes") == std::vector<std::string>{"denied", "denied"});
+    CHECK(python.str("loop_outcome") == "denied");
+    const std::string private_file = "open: " + python.str("PRIVATE") + "\n";
+    CHECK(describe(harness.prompts) == private_file + private_file + private_file + private_file + private_file);
+}
+
+TEST_CASE("A saved directory walk covers each directory it lists", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    PluginPermissions permissions;
+    permissions.fs_read = {python.str("TREE"), python.str("APPROVED")};
+    harness.save_permissions(PLUGIN, permissions);
+
+    // The walk lists the tree's two subdirectories on later resumes, after the plugin's own
+    // audited reads in between. Abandoned walks leave frames whose generator is gone, which the
+    // next audited event lets go.
+    python.run_as(PLUGIN, R"PY(
+walked = []
+for root, dirs, files in os.walk(TREE):
+    walked.append(root)
+    open(APPROVED).close()
+globbed = list(pathlib.Path(TREE).glob("**/*"))
+
+abandoned = os.walk(TREE)
+next(abandoned)
+del abandoned
+open(APPROVED).close()
+for _ in pathlib.Path(TREE).glob("*"):
+    break
+open(APPROVED).close()
+)PY");
+
+    CHECK(py::len(python.globals["walked"]) == 3);
+    CHECK(py::len(python.globals["globbed"]) == 4);
+    CHECK(describe(harness.prompts).empty());
+}
+
+TEST_CASE("A freshly approved operation covers its nested events", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+
+    struct Case
+    {
+        const char* prompts;
+        const char* code;
+    };
+    // Each operation names targets no earlier one saved, so each is asked once. FsCreate and
+    // FsDelete grants are never saved, so those operations are asked every time. Only the
+    // expected prompts are approved, so a nested event left uncovered fails the operation.
+    std::vector<Case> cases = {
+        {"shutil.copytree", "shutil.copytree(TREE, os.path.join(OUTSIDE, 'copy'))"},
+        {"shutil.copyfile", "shutil.copyfile(APPROVED, os.path.join(OUTSIDE, 'copied.txt'))"},
+        {"shutil.move", "shutil.move(os.path.join(OUTSIDE, 'copied.txt'), os.path.join(OUTSIDE, 'moved.txt'))"},
+        {"shutil.copystat", "shutil.copystat(os.path.join(TREE, 'one', 'f.txt'), PRIVATE)"},
+        {"shutil.make_archive", "shutil.make_archive(os.path.join(OUTSIDE, 'archive'), 'zip', root_dir=TREE)"},
+        {"shutil.unpack_archive", "shutil.unpack_archive(os.path.join(OUTSIDE, 'archive.zip'), os.path.join(OUTSIDE, 'unpacked'))"},
+        {"pathlib.Path.glob", "list(pathlib.Path(TREE).glob('**/*'))"},
+        {"subprocess.Popen", "subprocess.run(TRUE_COMMAND, check=True)"},
+        {"tempfile.mkdtemp", "tempfile.mkdtemp(dir=OUTSIDE)"},
+        {"tempfile.mkstemp", "os.close(tempfile.mkstemp(dir=OUTSIDE)[0])"},
+        {"shutil.rmtree", "shutil.rmtree(os.path.join(OUTSIDE, 'copy'))"},
+        // send() runs after connect() has returned, so its own grant is asked once.
+        {"http.client.connect\nhttp.client.send",
+         "connection = http.client.HTTPConnection('127.0.0.1', PORT)\n"
+         "connection.request('GET', '/a')\n"
+         "connection.getresponse().read()\n"
+         "connection.close()"},
+    };
+#ifndef _WIN32
+    cases.push_back({"os.fwalk", "list(os.fwalk(os.path.join(OUTSIDE, 'unpacked')))"});
+    // The forked child's exec is covered by the spawn too: had it prompted, the child's own
+    // denial would end it with status 1.
+    cases.push_back({"pty.spawn", "spawn_status = spawn_checked(TRUE_COMMAND + ['spawned'])"});
+#endif
+
+    for (const Case& operation : cases) {
+        INFO(operation.code);
+        const std::string expected = std::string(operation.prompts) + "\n";
+        harness.approve = [&expected](const Prompt& prompt) {
+            return expected.find(prompt.event + "\n") != std::string::npos;
+        };
+        harness.prompts.clear();
+        python.run_as(PLUGIN, operation.code);
+
+        std::string asked;
+        for (const Prompt& prompt : harness.prompts)
+            asked += (asked.empty() ? "" : "\n") + prompt.event;
+        CHECK(asked == operation.prompts);
+    }
+#ifndef _WIN32
+    CHECK(python.eval("spawn_status") == "0");
+#endif
+}
+
+TEST_CASE("An event with no target is granted by name and remembered", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    harness.approve = [](const Prompt& prompt) { return prompt.event != "socket.sendto"; };
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+
+    python.run_as(PLUGIN, R"PY(
+socket.socket().close()
+udp = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
+sendto_outcome = attempt(lambda: udp.sendto(b"x", ("127.0.0.1", 9)))
+udp.close()
+)PY");
+
+    // The socket is asked for once, without a target to show; the datagram's address is a target.
+    CHECK(python.str("sendto_outcome") == "denied");
+    CHECK(describe(harness.prompts) == "socket.__new__:\nsocket.sendto: ('127.0.0.1', 9)\n");
+    CHECK(harness.saved_permissions(PLUGIN).events == std::vector<std::string>{"Socket:socket.__new__"});
+    CHECK(harness.saved_permissions(PLUGIN).network_socket.empty());
+
+    harness.prompts.clear();
+    python.run_as(PLUGIN, "socket.socket().close()");
+    CHECK(describe(harness.prompts).empty());
+
+    // A grant for an event with no target covers nothing else: a library's approved
+    // gethostname() does not carry the connection it makes next.
+    harness.approve = [](const Prompt& prompt) { return prompt.event == "socket.gethostname"; };
+    python.run_as(PLUGIN, "connect_outcome = attempt(lambda: netlib.connect_from_host(PORT))");
+    CHECK(python.str("connect_outcome") == "denied");
+    CHECK(describe(harness.prompts) == "socket.gethostname:\nsocket.getaddrinfo: 127.0.0.1\n");
+    harness.prompts.clear();
+    harness.approve = [](const Prompt&) { return true; };
+
+#ifndef _WIN32
+    // sendmsg() without an address names no target either.
+    python.run_as(PLUGIN, R"PY(
+left, right = socket.socketpair()
+left.sendmsg([b"x"])
+left.close()
+right.close()
+)PY");
+    CHECK(describe(harness.prompts) == "socket.sendmsg:\n");
+    CHECK(harness.saved_permissions(PLUGIN).events ==
+          std::vector<std::string>{"Socket:socket.__new__", "Socket:socket.gethostname", "Socket:socket.sendmsg"});
+#endif
+}
+
+TEST_CASE("An event grant does not stand in for another access or a target of the same name", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    harness.approve = [asked = 0](const Prompt&) mutable { return asked++ == 0; };
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    python.exec(R"PY(
+READ_FD = os.open(APPROVED, os.O_RDONLY)
+WRITE_FD = os.open(os.path.join(OUTSIDE, "scratch.txt"), os.O_WRONLY | os.O_CREAT)
+)PY");
+
+    // A file descriptor has no path to show or save: a granted read of one is not a write.
+    python.run_as(PLUGIN, R"PY(
+fd_outcomes = [attempt(lambda: open(READ_FD, "r", closefd=False).close()),
+               attempt(lambda: open(WRITE_FD, "w", closefd=False).close())]
+)PY");
+    CHECK(python.strings("fd_outcomes") == std::vector<std::string>{"ok", "denied"});
+    CHECK(describe(harness.prompts) == "open:\nopen:\n");
+    CHECK(harness.saved_permissions(PLUGIN).events == std::vector<std::string>{"FsRead:open"});
+
+    // A saved os.fork event grant is not an os.system command named "os.fork".
+    PluginPermissions permissions;
+    permissions.events = {"FsRead:open", "ProcessCreate:os.fork"};
+    harness.save_permissions(PLUGIN, permissions);
+    harness.prompts.clear();
+    python.run_as(PLUGIN, R"PY(
+reread_outcome = attempt(lambda: open(READ_FD, "r", closefd=False).close())
+system_outcome = attempt(lambda: os.system("os.fork"))
+os.close(READ_FD)
+os.close(WRITE_FD)
+)PY");
+    CHECK(python.str("reread_outcome") == "ok");
+    CHECK(python.str("system_outcome") == "denied");
+    REQUIRE(harness.prompts.size() == 1);
+    CHECK(harness.prompts.front().event == "os.system");
+    CHECK(harness.saved_permissions(PLUGIN).process.empty());
+}
+
+TEST_CASE("A finalizer run when a root frame is let go is judged as the plugin without a prompt", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin(PLUGIN);
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    PluginPermissions permissions = http_grants({python.str("URL_A")});
+    permissions.fs_read           = {python.str("APPROVED")};
+    harness.save_permissions(PLUGIN, permissions);
+    PluginAuditManager& mgr = PluginAuditManager::instance();
+
+    // Once the request returns, only its held frame keeps the request object alive, and the
+    // request's finalizer reads a file the plugin was never granted.
+    python.run_as(PLUGIN, "fetch(TrackedRequest(URL_A))");
+    CHECK(python.strings("finalizer_outcomes") == std::vector<std::string>{"denied"}); // at scope end
+    CHECK(describe(harness.prompts).empty());
+    CHECK_FALSE(mgr.audit_denial_pending());
+
+    python.exec("finalizer_outcomes.clear()");
+    python.run_as(PLUGIN, R"PY(
+fetch(TrackedRequest(URL_A))
+open(APPROVED).close()  # the next event lets the returned request's frame go
+outcomes_before_scope_end = list(finalizer_outcomes)
+)PY");
+    CHECK(python.strings("outcomes_before_scope_end") == std::vector<std::string>{"denied"});
+    CHECK(describe(harness.prompts).empty());
+
+    // The finalizer's denial during another event's decision leaves that event's own denial intact.
+    python.exec("finalizer_outcomes.clear()");
+    python.run_as(PLUGIN, R"PY(
+fetch(TrackedRequest(URL_A))
+try:
+    os.listdir(OUTSIDE)
+    outer_error = ""
+except PermissionError as error:
+    outer_error = str(error)
+)PY");
+    CHECK(python.strings("finalizer_outcomes") == std::vector<std::string>{"denied"});
+    CHECK_THAT(python.str("outer_error"), Catch::Matchers::ContainsSubstring("os.listdir"));
+    CHECK(describe(harness.prompts) == "os.listdir: " + python.str("OUTSIDE") + "\n");
+    AuditViolation violation;
+    REQUIRE(mgr.last_violation(violation));
+    CHECK(violation.event_name == "os.listdir");
+    CHECK(mgr.audit_denial_pending());
+}
+
+TEST_CASE("A nested audit scope does not see the outer scope's running operations", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.add_plugin("PluginA");
+    harness.add_plugin("PluginB");
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    PluginPermissions permissions;
+    permissions.fs_read = {python.str("TREE")};
+    harness.save_permissions("PluginA", permissions);
+
+    {
+        // Two walks plugin A started and suspended after listing the tree itself.
+        ScopedPluginAuditContext plugin_a("PluginA");
+        python.exec("first = os.walk(TREE)\nnext(first)\nsecond = os.walk(TREE)\nnext(second)");
+        {
+            // Plugin B resuming one of them is asked for each subdirectory, as plugin B.
+            ScopedPluginAuditContext plugin_b("PluginB");
+            python.exec("listed_by_b = len(list(first))");
+        }
+        // Back in plugin A's scope, its walks are covered again.
+        python.exec("listed_by_a = len(list(second))");
+    }
+
+    CHECK(python.globals["listed_by_b"].cast<int>() == 0);
+    CHECK(python.globals["listed_by_a"].cast<int>() == 2);
+    REQUIRE(harness.prompts.size() == 2);
+    for (const Prompt& prompt : harness.prompts) {
+        CHECK(prompt.plugin == "PluginB");
+        CHECK(prompt.event == "os.scandir");
+    }
+}
+
+TEST_CASE("Root frames held when a capability call ends are let go with the GIL, as the plugin", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    harness.approve = [](const Prompt& prompt) { return prompt.event == "os.walk"; };
+    py::gil_scoped_acquire gil;
+    PythonSide python(harness);
+    (void) PythonPluginBridge::instance(); // force the embedded module registration into the binary
+    python.globals["orca"] = py::module_::import("orca");
+
+    // walk_and_drop() leaves a returned walk's frame held by the audit scope alone, with a marker
+    // in its locals; the frame is let go when the capability call ends, which runs the marker's
+    // finalizer.
+    python.exec(R"PY(
+class Marker:
+    def __init__(self, action=None):
+        self.action = action
+    def __del__(self):
+        finalized.append(self.action() if self.action else "ran")
+
+finalized = []
+
+def walk_and_drop(marker):
+    walker = os.walk(TREE, onerror=marker)
+    next(walker)
+    del walker
+
+class ConfigCapability(orca.PythonPluginBase):
+    def get_name(self):
+        return "config_cap"
+    def get_default_config(self):
+        walk_and_drop(Marker())
+        return {"finalized_during_call": len(finalized)}
+    def has_config_ui(self):
+        walker = os.walk(TREE, onerror=Marker(lambda: attempt(lambda: open(PRIVATE).close())))
+        next(walker)
+        attempt(lambda: os.listdir(OUTSIDE))  # denied: the trampoline clears the plugin key
+        del walker  # the walk's frame is now held by the audit scope alone
+        raise RuntimeError("the capability fails after a denial")
+
+class TicketAgent(orca.printer_agent.PrinterAgentBase):
+    def get_name(self):
+        return "ticket_agent"
+    def request_bind_ticket(self):
+        walk_and_drop(Marker())
+        return (0, "ticket")
+)PY");
+
+    py::object config_instance = python.globals["ConfigCapability"]();
+    auto       config_cap      = config_instance.cast<std::shared_ptr<PluginCapabilityInterface>>();
+    config_cap->set_audit_plugin_key("GilPlugin");
+    config_cap->set_resolved_identity("config_cap", PluginCapabilityType::Script);
+
+    py::object agent_instance = python.globals["TicketAgent"]();
+    auto       agent_cap      = agent_instance.cast<std::shared_ptr<PluginCapabilityInterface>>();
+    agent_cap->set_audit_plugin_key("GilPlugin");
+    agent_cap->set_resolved_identity("ticket_agent", PluginCapabilityType::PrinterConnection);
+    auto agent = std::dynamic_pointer_cast<IPrinterAgent>(agent_cap);
+    REQUIRE(agent);
+
+    // A host call arrives without the GIL; both calls take it before their audit scope.
+    nlohmann::json config;
+    int            ticket_result = -1;
+    std::string    ticket;
+    {
+        py::gil_scoped_release released;
+        config        = config_cap->get_default_config();
+        ticket_result = agent->request_bind_ticket(&ticket);
+    }
+    CHECK(config == nlohmann::json{{"finalized_during_call", 0}});
+    CHECK(ticket_result == 0);
+    CHECK(ticket == "ticket");
+    CHECK(python.strings("finalized") == std::vector<std::string>{"ran", "ran"});
+
+    // On the trampoline's denial path the frame is let go as the plugin, though the ambient key
+    // was cleared: the finalizer's read is audited and denied without a prompt.
+    python.exec("finalized.clear()");
+    harness.prompts.clear();
+    CHECK_THROWS_AS(config_cap->has_config_ui(), py::error_already_set);
+    CHECK(python.strings("finalized") == std::vector<std::string>{"denied"});
+    CHECK(describe(harness.prompts) == "os.walk: " + python.str("TREE") + "\nos.listdir: " + python.str("OUTSIDE") + "\n");
+}
+
+TEST_CASE("Stdlib code is recognized through a symlinked Python home", "[audit][Python]")
+{
+    AuditHarness harness;
+    if (!harness.initialized)
+        SKIP("Bundled Python interpreter unavailable: " + PythonInterpreter::instance().last_error());
+    py::gil_scoped_acquire gil;
+
+    const py::dict paths   = py::module_::import("sysconfig").attr("get_paths")();
+    const fs::path stdlib  = py::str(paths["stdlib"]).cast<std::string>();
+    const fs::path purelib = py::str(paths["purelib"]).cast<std::string>();
+    const fs::path link    = harness.outside.path() / "linked-stdlib";
+    boost::system::error_code ec;
+    fs::create_directory_symlink(stdlib, link, ec);
+    if (ec)
+        SKIP("Cannot create a directory symlink here: " + ec.message());
+
+    CHECK(PluginAuditManager::is_stdlib_file((stdlib / "os.py").string()));
+    CHECK(PluginAuditManager::is_stdlib_file((link / "urllib" / "request.py").string()));
+    CHECK(PluginAuditManager::is_stdlib_file("<frozen os>"));
+    CHECK_FALSE(PluginAuditManager::is_stdlib_file((purelib / "requests" / "api.py").string()));
+    CHECK_FALSE(PluginAuditManager::is_stdlib_file((link / "site-packages" / "requests" / "api.py").string()));
+    CHECK_FALSE(PluginAuditManager::is_stdlib_file((harness.outside.path() / "plugin.py").string()));
+    CHECK_FALSE(PluginAuditManager::is_stdlib_file("<string>"));
+}