id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
10719	Access violation crash in difference -> enrich_sort	Volker Schöch <vschoech@…>	Barend Gehrels	"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'''"	Bugs	closed	Boost 1.58.0	geometry	Boost 1.56.0	Problem	fixed	access violation, uninitialized memory, undefined behavior, crash