[Boost-bugs] [Boost C++ Libraries] #10719: Access violation crash in difference -> enrich_sort

Subject: [Boost-bugs] [Boost C++ Libraries] #10719: Access violation crash in difference -> enrich_sort
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-10-30 10:33:21

#10719: Access violation crash in difference -> enrich_sort
-------------------------------------------------+-------------------------
 Reporter:  Volker Schöch <vschoech@…>           |      Owner:
     Type:  Bugs                                 |  barendgehrels
Milestone:  To Be Determined                     |     Status:  new
  Version:  Boost 1.56.0                         |  Component:  geometry
 Keywords:  access violation, uninitialized      |   Severity:  Showstopper
  memory, undefined behavior, crash              |
-------------------------------------------------+-------------------------
 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'''

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10719>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.