From a2f57f7ee1390ffd4c5441015083b477e995de96 Mon Sep 17 00:00:00 2001
From: Steven Noonan <steven@uplinklabs.net>
Date: Thu, 15 Oct 2009 12:16:09 -0700
Subject: los.cc: fix _find_minimal_cellrays iteration

From an earlier email about this bug:

  It bombed on the min_it++, which was odd.

  Looking at the loop, I suspect what happens is this:
  - Erases the last item in the 'min' list, setting min_it to min.end(),
  - Attempts to increment min_it (which isn't valid on the end iterator)

  The patch at the bottom of this mail avoids the crash, but DOES NOT
  fix the root bug. The root bug is a bit more insidous (imagine that,
  MSVC helped us catch a real bug!). Consider the following test case:

  -- BEGIN --
  #include <iostream>
  #include <list>

  int main()
  {
     std::list<int> ilist;
     for (int i = 1; i < 10; i++)
     {
         ilist.push_back(i);
     }

     for (std::list<int>::iterator l_it = ilist.begin();
          l_it != ilist.end();
          l_it++)
     {
         std::cout << *l_it << " ";
         if (*l_it == 4)
             l_it = ilist.erase(l_it);
     }
     std::cout << std::endl;

     return 0;
  }
  -- EOF --

  Here's the output:

  $ ./test
  1 2 3 4 6 7 8 9

  Note that it skipped over '5'. The reason is because the iterator ends
  up being incremented _twice_ (the erase() moves the iterator one
  forward of the previous position). So the obvious solution might be to
  decrement the iterator immediately after erase(), right? Wrong. If you
  erased the last element in the list, your iterator will be ==
  list.end(), which is an iterator you should NEVER use ++ or -- on.

Signed-off-by: Steven Noonan <steven@uplinklabs.net>
---
 crawl-ref/source/los.cc | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

(limited to 'crawl-ref/source/los.cc')

diff --git a/crawl-ref/source/los.cc b/crawl-ref/source/los.cc
index 4fa567d091..b30bac7249 100644
--- a/crawl-ref/source/los.cc
+++ b/crawl-ref/source/los.cc
@@ -274,8 +274,9 @@ static std::vector<int> _find_minimal_cellrays()
             cellray c(ray, i);
             std::list<cellray>& min = minima(c.end());
 
+            bool erased = false;
             for (min_it = min.begin();
-                 min_it != min.end() && !dup; min_it++)
+                 min_it != min.end() && !dup; )
             {
                 switch(_compare_cellrays(*min_it, c))
                 {
@@ -284,6 +285,7 @@ static std::vector<int> _find_minimal_cellrays()
                     break;
                 case C_SUPERRAY:
                     min_it = min.erase(min_it);
+                    erased = true;
                     // clear this should be added, but might have
                     // to erase more
                     break;
@@ -291,6 +293,10 @@ static std::vector<int> _find_minimal_cellrays()
                 default:
                     break;
                 }
+                if (!erased)
+                    min_it++;
+                else
+                    erased = false;
             }
             if (!dup)
                 min.push_back(c);
-- 
cgit v1.2.3-54-g00ecf