Wrong assertion in suitesparse.cc

[sandwichmaker]

Original issue 45 created by sandwichmaker on 2012-06-13T15:19:38.000Z:

What steps will reproduce the problem?

1. Build latest revision (fa01519)
2. Run bundle_adjuster -solver_type cholesky --input=../../data/problem-16-22106-pre.txt

What is the expected output? What do you see instead?

The program aborts after running into the following assertion:
F0613 17:03:53.814010 17742 suitesparse.cc:227] Check failed: it != row_block_starts.end()
*** Check failure stack trace: ***
@ 0x7fd732545ffd google::LogMessage::Fail()
@ 0x7fd732548757 google::LogMessage::SendToLog()
@ 0x7fd732545bfb google::LogMessage::Flush()
@ 0x7fd73254900d google::LogMessageFatal::~LogMessageFatal()
@ 0xa1ab8b ceres::internal::SuiteSparse::ScalarMatrixToBlockMatrix()
@ 0xa1a70d ceres::internal::SuiteSparse::BlockAMDOrdering()
[...]

If my understanding of the code is correct, this happens in code that tries to find the corresponding row block for an entry in a suitesparse matrix. The relevant assertion is triggered if the entry belongs to the last row block but is not the first row in this block. In this case the lower_bound call returns end(). (As a side note, I am not sure what happens if the entry in the first row of the block is precisely zero. Can this happen at all? Will there still be a corresponding entry in the suitesparse matrix?)

In my opinion the fix for the above problem is to simply continue if end() is returned, see the attached patch.

[sandwichmaker]

Comment #1 originally posted by sandwichmaker on 2012-06-13T16:02:35.000Z:

You are right this is an off by one error. I will look at this later today.
Thank you for reporting, and I am surprised that this escaped my testing. I will add a test to the effect too.

[sandwichmaker]

Comment #2 originally posted by sandwichmaker on 2012-06-14T19:54:06.000Z:

I saw that commit 469bf39 tries to fix this. However, the DCHECK was only part of the problem. The code now happily dereferences row_block_starts.end() in the following if-statement, which results in undefined behavior. I failed to mention that this has always been the case in Release mode. It is necessary to explicitly check for end().

[sandwichmaker]

Comment #3 originally posted by sandwichmaker on 2012-06-14T20:11:13.000Z:

ugh, my bad, this is what happens when I do things late night.
I will fix this in a follow up. Thanks for your careful look at his.
Sameer

[sandwichmaker]

Comment #4 originally posted by sandwichmaker on 2012-06-15T22:04:20.000Z:

Hopefully fixed and pushed to master for real this time :).