Access violation crash in difference -> enrich_sort

[Volker Schöch <vschoech@…>]

We investigated a crash that surfaced in update_discarded(...) but is actually a consequence of a memory corruption that occurred earlier, see discussion here: ​http://lists.boost.org/geometry/2014/10/3139.php

We found the problems are caused by undefined behavior within the comparison function object sort_on_segment_and_ratio, which is used for sorting vectors of indexed_turn_operation.

Running the following code...

{      // RT#8837
       _intPolygon polygonA;
       boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 2093,488 2093)))", polygonA); // does not throw

       _intRect rectB;
       boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB); // does not throw

       _intPolygon polygonC;
       boost::geometry::difference(polygonA, rectB, polygonC); // ACCESS VIOLATION
}

...we get into the following callstack:

copy_segment_point(... SegmentIdentifier const& seg_id, .... )
copy_segment_points(...)
sort_on_segment_and_ratio::get_situation_map(...)
sort_on_segment_and_ratio::consider_relative_order(...)
sort_on_segment_and_ratio::operator()(...)
std::sort(...)
enrich_sort(...)
enrich_intersection_points(...)
...
difference(polygonA, rectB, polygonC);
...

Note that the seg_id argument for copy_segment_point is taken from the indexed turn operations being compared (i.e., either subject.seg_id or subject.other_id).

If seg_id.source_index == -1, copy_segment_points does not copy any data, thus the computation continues with random junk values from the stack. This is exactly what happens in the above example, as some of the turning points have other_id.source_index == -1.

As a consequence, sort_on_segment_and_ratio::operator()(...) gives non-deterministic comparison results. Depending on the actual data that happens to be in memory during a specific instance of execution, the sort algorithm may crash. For example, Visual Studio's std::sort implementation may write to memory locations outside the input range. Please note that this is not a bug in std::sort.

Note for think-cell: RT8837

[Barend Gehrels]

I will check, but note your box is invalid, it's a spike

BOX(417 2064,597 2064)

So you should easily be able to work around this (assuming the problem does not occur for valid boxes)

[Barend Gehrels]

Cannot yet be reproduced with Boost 1.57, which does not have the sort_on_segment_and_ratio::get_situation_map(...)

anymore

[Volker Schöch <vschoech@…>]

May be related to #8366.

[Barend Gehrels]

Fixed by changing copy_segment_point for open polygons. Also fixed errors in sorting errors (operator<) by enrich and handle-tangencies functionality