https://svn.boost.org/trac10/ticket/10719 <p> We investigated a crash that surfaced in <em>update_discarded(...)</em> but is actually a consequence of a memory corruption that occurred earlier, see discussion here: <a class="ext-link" href="http://lists.boost.org/geometry/2014/10/3139.php"><span class="icon">​</span>http://lists.boost.org/geometry/2014/10/3139.php</a> </p> <p> We found the problems are caused by undefined behavior within the comparison function object <em>sort_on_segment_and_ratio</em>, which is used for sorting vectors of <em>indexed_turn_operation</em>. </p> <p> Running the following code... </p> <pre class="wiki">{ // 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 } </pre><p> ...we get into the following callstack: </p> <pre class="wiki">copy_segment_point(... SegmentIdentifier const&amp; 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); ... </pre><p> Note that the <em>seg_id</em> argument for <em>copy_segment_point</em> is taken from the indexed turn operations being compared (i.e., either <em>subject.seg_id</em> or <em>subject.other_id</em>). </p> <p> If <em>seg_id.source_index</em> == -1, <em>copy_segment_points</em> does not copy any data, <strong>thus the computation continues with random junk values from the stack</strong>. This is exactly what happens in the above example, as some of the turning points have <em>other_id.source_index</em> == -1. </p> <p> As a consequence, <em>sort_on_segment_and_ratio::operator()(...)</em> gives <strong>non-deterministic comparison</strong> 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 <strong>not</strong> a bug in std::sort. </p> <p> Note for think-cell: <strong>RT8837</strong> </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/10719 Trac 1.4.3 Barend Gehrels Thu, 06 Nov 2014 09:35:00 GMT https://svn.boost.org/trac10/ticket/10719#comment:1 https://svn.boost.org/trac10/ticket/10719#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">assigned</span> </li> </ul> Ticket Barend Gehrels Thu, 06 Nov 2014 14:04:41 GMT https://svn.boost.org/trac10/ticket/10719#comment:3 https://svn.boost.org/trac10/ticket/10719#comment:3 <ul> <li><strong>severity</strong> <span class="trac-field-old">Showstopper</span> → <span class="trac-field-new">Problem</span> </li> </ul> <p> Cannot yet be reproduced with Boost 1.57, which does not have the sort_on_segment_and_ratio::get_situation_map(...) </p> <p> anymore </p> Ticket Volker Schöch <vschoech@…> Wed, 19 Nov 2014 15:14:14 GMT https://svn.boost.org/trac10/ticket/10719#comment:5 https://svn.boost.org/trac10/ticket/10719#comment:5 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> <li><strong>milestone</strong> <span class="trac-field-old">To Be Determined</span> → <span class="trac-field-new">Boost 1.58.0</span> </li> </ul> <p> Fixed by changing copy_segment_point for open polygons. Also fixed errors in sorting errors (operator&lt;) by enrich and handle-tangencies functionality </p> Ticket