Sage: Ticket #11942: segfault on Graph().connected_component_containing_vertex('')
https://trac.sagemath.org/ticket/11942
<p>
As title.
</p>
<pre class="wiki">fs@zhenghe /tmp $ sage -c "Graph().connected_component_containing_vertex('')"
/opt/sage/local/lib/libcsage.so(print_backtrace+0x31)[0x7f14e1a96df2]
/opt/sage/local/lib/libcsage.so(sigdie+0x14)[0x7f14e1a96e24]
/opt/sage/local/lib/libcsage.so(sage_signal_handler+0x20c)[0x7f14e1a96a72]
/lib/x86_64-linux-gnu/libpthread.so.0(+0xf020)[0x7f14e31fa020]
/opt/sage/local/lib/python2.6/site-packages/sage/graphs/base/c_graph.so(+0x11aa1)[0x7f14be4d8aa1]
/opt/sage/local/lib/libpython2.6.so.1.0(+0x75876)[0x7f14e347c876]
/opt/sage/local/lib/libpython2.6.so.1.0(+0x75b92)[0x7f14e347cb92]
/opt/sage/local/lib/libpython2.6.so.1.0(+0xa0f08)[0x7f14e34a7f08]
/opt/sage/local/lib/libpython2.6.so.1.0(PyObject_Call+0x53)[0x7f14e3451cd3]
/opt/sage/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x395d)[0x7f14e34e835d]
/opt/sage/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x602d)[0x7f14e34eaa2d]
/opt/sage/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f14e34eb549]
/opt/sage/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f14e34eb642]
/opt/sage/local/lib/libpython2.6.so.1.0(+0xdb07e)[0x7f14e34e207e]
/opt/sage/local/lib/libpython2.6.so.1.0(PyEval_EvalFrameEx+0x4f8d)[0x7f14e34e998d]
/opt/sage/local/lib/libpython2.6.so.1.0(PyEval_EvalCodeEx+0x879)[0x7f14e34eb549]
/opt/sage/local/lib/libpython2.6.so.1.0(PyEval_EvalCode+0x32)[0x7f14e34eb642]
/opt/sage/local/lib/libpython2.6.so.1.0(PyRun_FileExFlags+0xb0)[0x7f14e350d9b0]
/opt/sage/local/lib/libpython2.6.so.1.0(PyRun_SimpleFileExFlags+0xdf)[0x7f14e350e3ef]
/opt/sage/local/lib/libpython2.6.so.1.0(Py_Main+0xb23)[0x7f14e351b693]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xfd)[0x7f14e27fcead]
python[0x4006a1]
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.
------------------------------------------------------------------------
/opt/sage/local/bin/sage-sage: line 772: 19065 Segmentation fault sage-eval "$@"
fs@zhenghe /tmp $
</pre><p>
Apply:
</p>
<ol><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11942/trac_11942.patch" title="Attachment 'trac_11942.patch' in Ticket #11942">trac_11942.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11942/trac_11942.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11942/trac_11942-exceptions.2.patch" title="Attachment 'trac_11942-exceptions.2.patch' in Ticket #11942">trac_11942-exceptions.2.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11942/trac_11942-exceptions.2.patch" title="Download"></a>
</li></ol>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11942
Trac 1.1.6ncohenFri, 21 Oct 2011 15:29:05 GMTstatus, description changed; author set
https://trac.sagemath.org/ticket/11942#comment:1
https://trac.sagemath.org/ticket/11942#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11942?action=diff&version=1">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Right ! <code>:-p</code>
</p>
<p>
This comes from an unchecked operation at the beginning of BFS/DFS. Fixed in the following patch <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketkiniSat, 22 Oct 2011 07:31:19 GMTreviewer set
https://trac.sagemath.org/ticket/11942#comment:2
https://trac.sagemath.org/ticket/11942#comment:2
<ul>
<li><strong>reviewer</strong>
set to <em>Keshav Kini</em>
</li>
</ul>
<p>
Wow, that was fast! :D I have a couple of questions, though. <code>Graph().connected_component_containing_vertex(0)</code> already produces an exception, which includes the number 0 in the message. This is still true with your patch. Currently investigating why...
</p>
<p>
Also, your exception is a <code>ValueError</code> - shouldn't it be a <code>KeyError</code>? Shouldn't the current error for vertex <code>0</code> be a <code>KeyError</code> too instead of a (!?) <code>RuntimeError</code>? The <a class="ext-link" href="http://docs.python.org/library/exceptions.html#exceptions.Exception"><span class="icon"></span>Python docs</a> say:
</p>
<blockquote class="citation">
<p>
This exception is mostly a relic from a previous version of the interpreter; it is not used very much any more.
</p>
</blockquote>
TicketncohenThu, 27 Oct 2011 17:57:11 GMT
https://trac.sagemath.org/ticket/11942#comment:3
https://trac.sagemath.org/ticket/11942#comment:3
<p>
Hellooooooo !
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
This exception is mostly a relic from a previous version of the interpreter; it is not used very much any more.
</p>
</blockquote>
</blockquote>
<p>
Oh ? That's a pity, I really use it a lot <code>:-)</code>
</p>
<p>
I immediately update the patch to return a <a class="missing wiki">KeyError?</a> <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketkiniThu, 27 Oct 2011 17:59:14 GMT
https://trac.sagemath.org/ticket/11942#comment:4
https://trac.sagemath.org/ticket/11942#comment:4
<p>
Oh, <code>ValueError</code> is still used a lot but it is <code>RuntimeError</code> which is not used much anymore.
</p>
TicketncohenThu, 27 Oct 2011 18:01:37 GMT
https://trac.sagemath.org/ticket/11942#comment:5
https://trac.sagemath.org/ticket/11942#comment:5
<blockquote class="citation">
<p>
Oh, <code>ValueError</code> is still used a lot but it is <code>RuntimeError</code> which is not used much anymore.
</p>
</blockquote>
<p>
Argggggg !!!
</p>
<p>
Patch reverted to the former one <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 27 Oct 2011 18:02:01 GMTattachment set
https://trac.sagemath.org/ticket/11942
https://trac.sagemath.org/ticket/11942
<ul>
<li><strong>attachment</strong>
set to <em>trac_11942.patch</em>
</li>
</ul>
TicketkiniThu, 27 Oct 2011 18:08:01 GMT
https://trac.sagemath.org/ticket/11942#comment:6
https://trac.sagemath.org/ticket/11942#comment:6
<p>
... but... even though <code>ValueError</code> is used a lot, the correct one to use here is <code>KeyError</code>... <code>D:</code>
</p>
<p>
Anyway don't worry about it, I'll do that in another patch later :) Sorry, didn't get much time to look at this earlier this week.
</p>
TicketncohenThu, 27 Oct 2011 18:09:27 GMT
https://trac.sagemath.org/ticket/11942#comment:7
https://trac.sagemath.org/ticket/11942#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11942#comment:6" title="Comment 6">kini</a>:
</p>
<blockquote class="citation">
<p>
... but... even though <code>ValueError</code> is used a lot, the correct one to use here is <code>KeyError</code>... <code>D:</code>
</p>
</blockquote>
<p>
Arggggggggggg !!!
</p>
<blockquote class="citation">
<p>
Anyway don't worry about it, I'll do that in another patch later :) Sorry, didn't get much time to look at this earlier this week.
</p>
</blockquote>
<p>
Good !! THaaaaanks ! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerThu, 03 Nov 2011 16:14:43 GMTmilestone deleted
https://trac.sagemath.org/ticket/11942#comment:8
https://trac.sagemath.org/ticket/11942#comment:8
<ul>
<li><strong>milestone</strong>
<em>sage-4.7.3</em> deleted
</li>
</ul>
<p>
Milestone sage-4.7.3 deleted
</p>
TicketdcoudertSat, 10 Dec 2011 20:06:01 GMTstatus, reviewer changed; milestone set
https://trac.sagemath.org/ticket/11942#comment:9
https://trac.sagemath.org/ticket/11942#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Keshav Kini</em> to <em>Keshav Kini, David Coudert</em>
</li>
<li><strong>milestone</strong>
set to <em>sage-4.8</em>
</li>
</ul>
<p>
I don't understand why you have both stopped the discussion without concluding on the status of this patch.
</p>
<p>
I have no problem when installing the patch and building the documentation.
The function tests correctly that the parameter is or is not a vertex of the graph.
</p>
<p>
For me the patch is correct, so I give a positive review.
</p>
<p>
Best,
David.
</p>
TicketkiniSat, 10 Dec 2011 20:21:47 GMTstatus changed
https://trac.sagemath.org/ticket/11942#comment:10
https://trac.sagemath.org/ticket/11942#comment:10
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Please read the comments. The <a class="missing wiki">ValueError?</a> needs to be changed to <a class="missing wiki">KeyError?</a>, and also I wanted to understand the following before giving it a positive review, as possibly the fix could be improved (multiple code paths for a single purpose is bad design):
</p>
<blockquote class="citation">
<p>
<code>Graph().connected_component_containing_vertex(0)</code> already produces an exception, which includes the number 0 in the message. This is still true with your patch.
</p>
</blockquote>
<p>
Sorry for neglecting this ticket for so long.
</p>
TicketkiniWed, 04 Jan 2012 01:50:20 GMTstatus, description, author changed; keywords set
https://trac.sagemath.org/ticket/11942#comment:11
https://trac.sagemath.org/ticket/11942#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>keywords</strong>
<em>segfault</em> <em>cython</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11942?action=diff&version=11">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>Nathann Cohen</em> to <em>Nathann Cohen, Keshav Kini</em>
</li>
</ul>
<p>
Well, I'm still not sure about the multiple code paths. But here is a patch to use better exceptions throughout the file in question, though that's sort of tangential to the original purpose of the ticket. This ticket has been sitting around too long for me to delay it any further just because of my ignorance of the Cython graphs code, especially since it fixes a segfault, so I will give a positive review to Nathann's part. Maybe someone can review my exceptions patch? It passes <code>make ptestlong</code> on my machine fwiw.
</p>
TicketncohenWed, 04 Jan 2012 23:11:15 GMTstatus changed
https://trac.sagemath.org/ticket/11942#comment:12
https://trac.sagemath.org/ticket/11942#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Well, what about setting the message to what it was before, and just change the exception's name if yo feels it should be ? The former message was way clearer, especially when the exception is thrown by a submethod of the method run by the user.
</p>
<p>
Nathann
</p>
TicketkiniThu, 05 Jan 2012 04:53:48 GMT
https://trac.sagemath.org/ticket/11942#comment:13
https://trac.sagemath.org/ticket/11942#comment:13
<p>
<code>ValueError</code>'s constructor accepts a string representing a message, but <code>KeyError</code>'s constructor accepts an object representing the key which was not found in some collection. So this is the "correct" way to raise the exception here. The traceback call stack should theoretically give you all the info that was in the error message before. I noticed this because <code>raise ValueError('foo')</code> gives you a message "ValueError: foo" whereas <code>raise KeyError('foo')</code> gives you a message "KeyError: 'foo'" (note the quotation marks). I asked about it on the Python IRC channel and the above is the answer I got.
</p>
TicketncohenThu, 05 Jan 2012 09:52:14 GMT
https://trac.sagemath.org/ticket/11942#comment:14
https://trac.sagemath.org/ticket/11942#comment:14
<p>
Well, for me this modification just makes the error message harder to understand, and I do not see the point of losing that if the only gain is to respect some standard we did not know even existed two weeks ago.
</p>
TicketkiniThu, 05 Jan 2012 10:00:01 GMT
https://trac.sagemath.org/ticket/11942#comment:15
https://trac.sagemath.org/ticket/11942#comment:15
<p>
Hmm. OK, I'll just put back the messages and still use <a class="missing wiki">KeyError?</a>. The quotation marks are a bit weird, but not such a big deal, I guess - we are not actually trying to catch these exceptions and do anything with them anyway.
</p>
TicketdcoudertThu, 05 Jan 2012 10:10:19 GMT
https://trac.sagemath.org/ticket/11942#comment:16
https://trac.sagemath.org/ticket/11942#comment:16
<p>
Hello,
It would be nice if the <a class="missing wiki">KeyError?</a> method could take an extra argument to describe the error. For instance <a class="missing wiki">KeyError?</a>(key, 'You should add some tests to your algorithm!').
Unfortunately, I'm not able to find the documentation of the <a class="missing wiki">KeyError?</a> function.
</p>
<p>
However, according to the documentation of Python, the raise method can handle multiple arguments:
<code>raise_stmt ::= "raise" [expression ["," expression ["," expression]]]</code>
See: <a class="ext-link" href="http://docs.python.org/reference/simple_stmts.html#raise"><span class="icon"></span>http://docs.python.org/reference/simple_stmts.html#raise</a>
It may help satisfying both of you ;-)
</p>
<p>
Best,
David.
</p>
TicketkiniThu, 05 Jan 2012 10:33:03 GMT
https://trac.sagemath.org/ticket/11942#comment:17
https://trac.sagemath.org/ticket/11942#comment:17
<p>
Thank you, David! I agree with you, that would be great. Unfortunately it is not supported by Python. The documentation you linked about the <code>raise</code> statement is unfortunately not so helpful - there must be between 1 and 3 arguments, and they have special meanings. Actually, the multiple-argument syntax for <code>raise</code> is there in order to provide backwards compatibility with old versions of Python in which Exceptions were not objects with constructors. Now we would do something like
</p>
<p>
<code>raise HALError("I can't let you do that, Dave")</code>
</p>
<p>
but before you would write
</p>
<p>
<code>raise HALError, "I can't let you do that, Dave"</code>
</p>
<p>
because the <code>HALError(foo)</code> syntax didn't exist. So the multiple arguments basically allows you to still use the old syntax. Unfortunately this doesn't mean that we can just raise multiple exceptions...
</p>
TicketkiniThu, 05 Jan 2012 10:36:14 GMTattachment set
https://trac.sagemath.org/ticket/11942
https://trac.sagemath.org/ticket/11942
<ul>
<li><strong>attachment</strong>
set to <em>trac_11942-exceptions.patch</em>
</li>
</ul>
<p>
apply to $SAGE_ROOT/devel/sage
</p>
TicketkiniThu, 05 Jan 2012 10:36:55 GMTstatus changed
https://trac.sagemath.org/ticket/11942#comment:18
https://trac.sagemath.org/ticket/11942#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
New patch up. Sorry about all this noise, I should really have just made a different ticket for this exception stuff.
</p>
TicketncohenThu, 05 Jan 2012 13:36:47 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/11942#comment:19
https://trac.sagemath.org/ticket/11942#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Keshav Kini, David Coudert</em> to <em>Keshav Kini, David Coudert, Nathann Cohen</em>
</li>
</ul>
<p>
Hellooooo !!!
</p>
<p>
Well, thank you for this new version <code>:-)</code>
</p>
<p>
It passes all tests, so this ticket can go !
</p>
<p>
Nathann
</p>
TicketkiniThu, 05 Jan 2012 14:04:24 GMT
https://trac.sagemath.org/ticket/11942#comment:20
https://trac.sagemath.org/ticket/11942#comment:20
<p>
Hurrah! Thanks for the review (and the original patch)!
</p>
<p>
BTW, I botched that 2001 quote above... it should be "I'm sorry, Dave, I'm afraid I can't do that", of course <code>:P</code>
</p>
TicketncohenThu, 05 Jan 2012 14:07:01 GMT
https://trac.sagemath.org/ticket/11942#comment:21
https://trac.sagemath.org/ticket/11942#comment:21
<blockquote class="citation">
<p>
BTW, I botched that 2001 quote above... it should be "I'm sorry, Dave, I'm afraid I can't do that", of course <code>:P</code>
</p>
</blockquote>
<p>
No harm done, we both watched the french version of it <code>:-D</code>
</p>
TicketjdemeyerThu, 05 Jan 2012 14:13:55 GMTmilestone changed
https://trac.sagemath.org/ticket/11942#comment:22
https://trac.sagemath.org/ticket/11942#comment:22
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.8</em> to <em>sage-5.0</em>
</li>
</ul>
TicketjdemeyerThu, 05 Jan 2012 14:36:59 GMTattachment set
https://trac.sagemath.org/ticket/11942
https://trac.sagemath.org/ticket/11942
<ul>
<li><strong>attachment</strong>
set to <em>trac_11942-exceptions.2.patch</em>
</li>
</ul>
<p>
Use <a class="missing wiki">LookupError?</a> instead of <a class="missing wiki">ValueError?</a> or <a class="missing wiki">KeyError?</a>
</p>
TicketjdemeyerThu, 05 Jan 2012 14:38:11 GMTstatus, description, author changed
https://trac.sagemath.org/ticket/11942#comment:23
https://trac.sagemath.org/ticket/11942#comment:23
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/11942?action=diff&version=23">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>Nathann Cohen, Keshav Kini</em> to <em>Nathann Cohen, Keshav Kini, Jeroen Demeyer</em>
</li>
</ul>
<p>
Since <code>KeyError</code> is specifically about dicts, I think the more general <code>LookupError</code> is better. Needs review.
</p>
TicketjdemeyerThu, 05 Jan 2012 14:38:20 GMTstatus changed
https://trac.sagemath.org/ticket/11942#comment:24
https://trac.sagemath.org/ticket/11942#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketkiniThu, 05 Jan 2012 14:58:40 GMTmilestone changed
https://trac.sagemath.org/ticket/11942#comment:25
https://trac.sagemath.org/ticket/11942#comment:25
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.0</em> to <em>sage-4.8</em>
</li>
</ul>
<p>
Oh, I was under the impression that those base classes shouldn't be instantiated, but that seems to be unfounded after reading the docs. Looks good to me! Lines 855-856 of <code>$SAGE_ROOT/devel/sage/sage/graphs/base/graph_backends.py</code> contains another exception which seems like it should be a <code>LookupError</code> but I'm not sure I understand why the current exception is imported from !NetworkX. Maybe there is a good reason for it?
</p>
TicketkiniThu, 05 Jan 2012 14:58:57 GMTmilestone changed
https://trac.sagemath.org/ticket/11942#comment:26
https://trac.sagemath.org/ticket/11942#comment:26
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.8</em> to <em>sage-5.0</em>
</li>
</ul>
<p>
Whoops, didn't mean to change the milestone.
</p>
TicketncohenThu, 05 Jan 2012 15:04:06 GMT
https://trac.sagemath.org/ticket/11942#comment:27
https://trac.sagemath.org/ticket/11942#comment:27
<p>
Well, these lines are contained in the NetworkX backend, so it may mean that they define their own Exceptions in the NetworkX project. I do not think this class is still used in Sage anyway.
</p>
<p>
Nathann
</p>
TicketkiniThu, 05 Jan 2012 15:06:19 GMTstatus changed
https://trac.sagemath.org/ticket/11942#comment:28
https://trac.sagemath.org/ticket/11942#comment:28
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
But didn't Sage developers write that NetworkX backend wrapper? Well, never mind, if it's not used in Sage anymore.
</p>
TicketncohenThu, 05 Jan 2012 15:11:39 GMT
https://trac.sagemath.org/ticket/11942#comment:29
https://trac.sagemath.org/ticket/11942#comment:29
<p>
Well yes, and that's most probably this class. But if you run some code made for NetworkX on a Sage graph with our own exception it may break the NetworkX code. I guess this was the point of importing exceptions. Thank you for the patch Jeroen !
</p>
<p>
Nathann
</p>
TicketkiniThu, 05 Jan 2012 15:36:03 GMT
https://trac.sagemath.org/ticket/11942#comment:30
https://trac.sagemath.org/ticket/11942#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11942#comment:29" title="Comment 29">ncohen</a>:
</p>
<blockquote class="citation">
<p>
if you run some code made for NetworkX on a Sage graph
</p>
</blockquote>
<p>
Aha, now I get it. And yes, thanks Jeroen :)
</p>
TicketjdemeyerSun, 15 Jan 2012 21:56:17 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11942#comment:31
https://trac.sagemath.org/ticket/11942#comment:31
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.0.beta0</em>
</li>
</ul>
Ticket