Memory leaks when intersecting geometries with invalid data

[DalePAtSafe]

Our internal sanitize testing discovered two instances of memory leaks that occur when attempting to intersect geometries with some invalid data.

Leak 1:

These are the geometries that trigger the leak

LINESTRING (nan 0.0000000000000000, 0.0000000000000000 1.0000000000000000, 1.0000000000000000 1.0000000000000000, 1.0000000000000000 0.0000000000000000, nan 0.0000000000000000)
POLYGON ((-86060443046427184.0000000000000000 20820223.5124294497072697, -86060443046427184.0000000000000000 -20820223.5124294497072697, -86060443004786720.0000000000000000 -20820223.5124294497072697, -86060443004786720.0000000000000000 20820223.5124294497072697, -86060443046427184.0000000000000000 20820223.5124294497072697))

This is the stack to the exception that causes the leak

1:  libgeos.so.3.9.1!geos::algorithm::CGAlgorithmsDD::orientationIndex(double p1x, double p1y, double p2x, double p2y, double qx, double qy) (geos-3.9.1/src/algorithm/CGAlgorithmsDD.cpp:65)
2:  libgeos.so.3.9.1!geos::algorithm::CGAlgorithmsDD::orientationIndex(const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & q) (geos-3.9.1/src/algorithm/CGAlgorithmsDD.cpp:95)
3:  libgeos.so.3.9.1!geos::algorithm::Orientation::index(const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & q) (geos-3.9.1/src/algorithm/Orientation.cpp:40)
4:  libgeos.so.3.9.1!geos::algorithm::LineIntersector::computeIntersect(geos::algorithm::LineIntersector * const this, const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & q1, const geos::geom::Coordinate & q2) (geos-3.9.1/src/algorithm/LineIntersector.cpp:343)
5:  libgeos.so.3.9.1!geos::algorithm::LineIntersector::computeIntersection(geos::algorithm::LineIntersector * const this, const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & p3, const geos::geom::Coordinate & p4) (geos-3.9.1/src/algorithm/LineIntersector.cpp:97)
6:  libgeos.so.3.9.1!geos::noding::snap::SnappingIntersectionAdder::processIntersections(geos::noding::snap::SnappingIntersectionAdder * const this, geos::noding::SegmentString * seg0, size_t segIndex0, geos::noding::SegmentString * seg1, size_t segIndex1) (geos-3.9.1/src/noding/snap/SnappingIntersectionAdder.cpp:61)
7:  libgeos.so.3.9.1!geos::noding::MCIndexNoder::SegmentOverlapAction::overlap(geos::noding::MCIndexNoder::SegmentOverlapAction * const this, geos::index::chain::MonotoneChain & mc1, size_t start1, geos::index::chain::MonotoneChain & mc2, size_t start2) (geos-3.9.1/src/noding/MCIndexNoder.cpp:143)
8:  libgeos.so.3.9.1!geos::index::chain::MonotoneChain::computeOverlaps(geos::index::chain::MonotoneChain * const this, size_t start0, size_t end0, geos::index::chain::MonotoneChain & mc, size_t start1, size_t end1, double overlapTolerance, geos::index::chain::MonotoneChainOverlapAction & mco) (geos-3.9.1/src/index/chain/MonotoneChain.cpp:142)
9:  libgeos.so.3.9.1!geos::index::chain::MonotoneChain::computeOverlaps(geos::index::chain::MonotoneChain * const this, geos::index::chain::MonotoneChain * mc, double overlapTolerance, geos::index::chain::MonotoneChainOverlapAction * mco) (geos-3.9.1/src/index/chain/MonotoneChain.cpp:129)
10: libgeos.so.3.9.1!geos::noding::MCIndexNoder::intersectChains(geos::noding::MCIndexNoder * const this) (geos-3.9.1/src/noding/MCIndexNoder.cpp:86)
11: libgeos.so.3.9.1!geos::noding::MCIndexNoder::computeNodes(geos::noding::MCIndexNoder * const this, geos::noding::SegmentString::NonConstVect * inputSegStrings) (geos-3.9.1/src/noding/MCIndexNoder.cpp:56)
12: libgeos.so.3.9.1!geos::noding::snap::SnappingNoder::snapIntersections(geos::noding::snap::SnappingNoder * const this, std::vector<geos::noding::SegmentString*, std::allocator<geos::noding::SegmentString*> > & inputSS) (geos-3.9.1/src/noding/snap/SnappingNoder.cpp:112)
13: libgeos.so.3.9.1!geos::noding::snap::SnappingNoder::computeNodes(geos::noding::snap::SnappingNoder * const this, std::vector<geos::noding::SegmentString*, std::allocator<geos::noding::SegmentString*> > * inputSegStrings) (geos-3.9.1/src/noding/snap/SnappingNoder.cpp:44)
14: libgeos.so.3.9.1!geos::operation::overlayng::EdgeNodingBuilder::node(geos::operation::overlayng::EdgeNodingBuilder * const this, std::vector<geos::noding::SegmentString*, std::allocator<geos::noding::SegmentString*> > * segStrings) (geos-3.9.1/src/operation/overlayng/EdgeNodingBuilder.cpp:100)
15: libgeos.so.3.9.1!geos::operation::overlayng::EdgeNodingBuilder::build(geos::operation::overlayng::EdgeNodingBuilder * const this, const geos::geom::Geometry * geom0, const geos::geom::Geometry * geom1) (geos-3.9.1/src/operation/overlayng/EdgeNodingBuilder.cpp:84)
16: libgeos.so.3.9.1!geos::operation::overlayng::OverlayNG::computeEdgeOverlay(geos::operation::overlayng::OverlayNG * const this) (geos-3.9.1/src/operation/overlayng/OverlayNG.cpp:226)
17: libgeos.so.3.9.1!geos::operation::overlayng::OverlayNG::getResult(geos::operation::overlayng::OverlayNG * const this) (geos-3.9.1/src/operation/overlayng/OverlayNG.cpp:179)
18: libgeos.so.3.9.1!geos::operation::overlayng::OverlayNG::overlay(const geos::geom::Geometry * geom0, const geos::geom::Geometry * geom1, int opCode, geos::noding::Noder * noder) (geos-3.9.1/src/operation/overlayng/OverlayNG.cpp:118)
19: libgeos.so.3.9.1!geos::operation::overlayng::OverlayNGRobust::overlaySnapTol(const geos::geom::Geometry * geom0, const geos::geom::Geometry * geom1, int opCode, double snapTol) (geos-3.9.1/src/operation/overlayng/OverlayNGRobust.cpp:242)
20: libgeos.so.3.9.1!geos::operation::overlayng::OverlayNGRobust::overlaySnapping(const geos::geom::Geometry * geom0, const geos::geom::Geometry * geom1, int opCode, double snapTol) (geos-3.9.1/src/operation/overlayng/OverlayNGRobust.cpp:188)
21: libgeos.so.3.9.1!geos::operation::overlayng::OverlayNGRobust::overlaySnapTries(const geos::geom::Geometry * geom0, const geos::geom::Geometry * geom1, int opCode) (geos-3.9.1/src/operation/overlayng/OverlayNGRobust.cpp:166)
22: libgeos.so.3.9.1!geos::operation::overlayng::OverlayNGRobust::Overlay(const geos::geom::Geometry * geom0, const geos::geom::Geometry * geom1, int opCode) (geos-3.9.1/src/operation/overlayng/OverlayNGRobust.cpp:135)
23: libgeos.so.3.9.1!geos::geom::HeuristicOverlay(const geos::geom::Geometry * g0, const geos::geom::Geometry * g1, int opCode) (geos-3.9.1/src/geom/HeuristicOverlay.cpp:415)
24: libgeos.so.3.9.1!geos::geom::Geometry::intersection(const geos::geom::Geometry * const this, const geos::geom::Geometry * other) (geos-3.9.1/src/geom/Geometry.cpp:554)
25: libgeos_c.so.1!operator()(const struct {...} * const __closure) (geos-3.9.1/capi/geos_ts_c.cpp:1046)
26: libgeos_c.so.1!execute<GEOSIntersection_r(GEOSContextHandle_t, const geos::geom::Geometry*, const geos::geom::Geometry*)::<lambda()> >(GEOSContextHandle_t, struct {...} &&)(GEOSContextHandle_t extHandle, struct {...} && f) (geos-3.9.1/capi/geos_ts_c.cpp:388)
27: libgeos_c.so.1!GEOSIntersection_r(GEOSContextHandle_t extHandle, const geos::geom::Geometry * g1, const geos::geom::Geometry * g2) (geos-3.9.1/capi/geos_ts_c.cpp:1045)

This leak occurs due to an IllegalArgumentException thrown in geos::algorithm::CGAlgorithmsDD::orientationIndex (line 65). That exception causes the de-allocation of some SegmentStrings allocated in geos::noding::snap::SnappingNoder::computeNodes (frame 13 of the stack) to be skipped.

Leak 2:

These are the geometries that trigger the leak

LINESTRING (nan 0.0000000000000000, 0.0000000000000000 nan)
POLYGON ((-86060443046427184.0000000000000000 20820223.5124294497072697, -86060443046427184.0000000000000000 -20820223.5124294497072697, -86060443004786720.0000000000000000 -20820223.5124294497072697, -86060443004786720.0000000000000000 20820223.5124294497072697, -86060443046427184.0000000000000000 20820223.5124294497072697))

This is the stack to the exception that causes the leak

1:  libgeos.so.3.9.1!geos::algorithm::CGAlgorithmsDD::orientationIndex(double p1x, double p1y, double p2x, double p2y, double qx, double qy) (geos-3.9.1/src/algorithm/CGAlgorithmsDD.cpp:65)
2:  libgeos.so.3.9.1!geos::algorithm::CGAlgorithmsDD::orientationIndex(const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & q) (geos-3.9.1/src/algorithm/CGAlgorithmsDD.cpp:95)
3:  libgeos.so.3.9.1!geos::algorithm::Orientation::index(const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & q) (geos-3.9.1/src/algorithm/Orientation.cpp:40)
4:  libgeos.so.3.9.1!geos::algorithm::LineIntersector::computeIntersect(geos::algorithm::LineIntersector * const this, const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & q1, const geos::geom::Coordinate & q2) (geos-3.9.1/src/algorithm/LineIntersector.cpp:342)
5:  libgeos.so.3.9.1!geos::algorithm::LineIntersector::computeIntersection(geos::algorithm::LineIntersector * const this, const geos::geom::Coordinate & p1, const geos::geom::Coordinate & p2, const geos::geom::Coordinate & p3, const geos::geom::Coordinate & p4) (geos-3.9.1/src/algorithm/LineIntersector.cpp:97)
6:  libgeos.so.3.9.1!geos::noding::NodingIntersectionFinder::processIntersections(geos::noding::NodingIntersectionFinder * const this, geos::noding::SegmentString * e0, size_t segIndex0, geos::noding::SegmentString * e1, size_t segIndex1) (geos-3.9.1/src/noding/NodingIntersectionFinder.cpp:127)
7:  libgeos.so.3.9.1!geos::noding::MCIndexNoder::SegmentOverlapAction::overlap(geos::noding::MCIndexNoder::SegmentOverlapAction * const this, geos::index::chain::MonotoneChain & mc1, size_t start1, geos::index::chain::MonotoneChain & mc2, size_t start2) (geos-3.9.1/src/noding/MCIndexNoder.cpp:143)
8:  libgeos.so.3.9.1!geos::index::chain::MonotoneChain::computeOverlaps(geos::index::chain::MonotoneChain * const this, size_t start0, size_t end0, geos::index::chain::MonotoneChain & mc, size_t start1, size_t end1, double overlapTolerance, geos::index::chain::MonotoneChainOverlapAction & mco) (geos-3.9.1/src/index/chain/MonotoneChain.cpp:142)
9:  libgeos.so.3.9.1!geos::index::chain::MonotoneChain::computeOverlaps(geos::index::chain::MonotoneChain * const this, geos::index::chain::MonotoneChain * mc, double overlapTolerance, geos::index::chain::MonotoneChainOverlapAction * mco) (geos-3.9.1/src/index/chain/MonotoneChain.cpp:129)
10: libgeos.so.3.9.1!geos::noding::MCIndexNoder::intersectChains(geos::noding::MCIndexNoder * const this) (geos-3.9.1/src/noding/MCIndexNoder.cpp:86)
11: libgeos.so.3.9.1!geos::noding::MCIndexNoder::computeNodes(geos::noding::MCIndexNoder * const this, geos::noding::SegmentString::NonConstVect * inputSegStrings) (geos-3.9.1/src/noding/MCIndexNoder.cpp:56)
12: libgeos.so.3.9.1!geos::noding::FastNodingValidator::checkInteriorIntersections(geos::noding::FastNodingValidator * const this) (geos-3.9.1/src/noding/FastNodingValidator.cpp:40)
13: libgeos.so.3.9.1!geos::noding::FastNodingValidator::execute(geos::noding::FastNodingValidator * const this) (geos-3.9.1/include/geos/noding/FastNodingValidator.h:118)
14: libgeos.so.3.9.1!geos::noding::FastNodingValidator::checkValid(geos::noding::FastNodingValidator * const this) (geos-3.9.1/src/noding/FastNodingValidator.cpp:71)
15: libgeos.so.3.9.1!geos::geomgraph::EdgeNodingValidator::checkValid(geos::geomgraph::EdgeNodingValidator * const this) (geos-3.9.1/include/geos/geomgraph/EdgeNodingValidator.h:106)
16: libgeos.so.3.9.1!geos::geomgraph::EdgeNodingValidator::checkValid(std::vector<geos::geomgraph::Edge*, std::allocator<geos::geomgraph::Edge*> > & edges) (geos-3.9.1/include/geos/geomgraph/EdgeNodingValidator.h:91)
17: libgeos.so.3.9.1!geos::operation::overlay::OverlayOp::computeOverlay(geos::operation::overlay::OverlayOp * const this, geos::operation::overlay::OverlayOp::OpCode opCode) (geos-3.9.1/src/operation/overlay/OverlayOp.cpp:813)
18: libgeos.so.3.9.1!geos::operation::overlay::OverlayOp::getResultGeometry(geos::operation::overlay::OverlayOp * const this, geos::operation::overlay::OverlayOp::OpCode funcCode) (geos-3.9.1/src/operation/overlay/OverlayOp.cpp:192)
19: libgeos.so.3.9.1!geos::operation::overlay::OverlayOp::overlayOp(const geos::geom::Geometry * geom0, const geos::geom::Geometry * geom1, geos::operation::overlay::OverlayOp::OpCode opCode) (geos-3.9.1/src/operation/overlay/OverlayOp.cpp:94)
20: libgeos.so.3.9.1!geos::geom::HeuristicOverlay(const geos::geom::Geometry * g0, const geos::geom::Geometry * g1, int opCode) (geos-3.9.1/src/geom/HeuristicOverlay.cpp:446)
21: libgeos.so.3.9.1!geos::geom::Geometry::intersection(const geos::geom::Geometry * const this, const geos::geom::Geometry * other) (geos-3.9.1/src/geom/Geometry.cpp:554)
22: libgeos_c.so.1!operator()(const struct {...} * const __closure) (geos-3.9.1/capi/geos_ts_c.cpp:1046)
23: libgeos_c.so.1!execute<GEOSIntersection_r(GEOSContextHandle_t, const geos::geom::Geometry*, const geos::geom::Geometry*)::<lambda()> >(GEOSContextHandle_t, struct {...} &&)(GEOSContextHandle_t extHandle, struct {...} && f) (geos-3.9.1/capi/geos_ts_c.cpp:388)
24: libgeos_c.so.1!GEOSIntersection_r(GEOSContextHandle_t extHandle, const geos::geom::Geometry * g1, const geos::geom::Geometry * g2) (geos-3.9.1/capi/geos_ts_c.cpp:1045)

This leak also occurs due to an IllegalArgumentException thrown in geos::algorithm::CGAlgorithmsDD::orientationIndex (line 65), however this time the memory is leaked in geos::operation::overlay::OverlayOp::computeOverlay (frame 17 of the stack) where the exception causes edgeList.clearList() (line 828) to be skipped and so leaks any edges contained within it.

[dbaston]

No leaks appear to be present in the current main branch. I've added tests for these cases at 0f18895aa3ad762caeaa4259c320832252922fac/git

Also added passing tests to 3.11 and 3.10 branches. The leaks are still present in the 3.9 branch.