Under certain, very specific conditions get_shortest_route( ) may go into an infinite loop without producing a result.
(The following is a muchly boiled-down version of a Real World Case.)
The situation comes up with a line A like this:
A1 <-> A2 <- A4
| /
V /
A3
A3 is a terminus station only (end station, arrivals only, no boarding); A4 is also a terminus station (start station, no arrivals, boarding only). There is a pedestrian connection between A3 and A4 (indicated by the slashes in the diagram above).
The relevant section from the map specification in XML format looks like this:
<station id="A1" name="A1" line="A:1" link="A2" />
<station id="A2" name="A2" line="A:2" link="A1,A3"/>
<station id="A3" name="A3" line="A:3" link="" other_link="walk:A4"/>
<station id="A4" name="A4" line="A:4" link="A2"/>
Note that the link attribute for A3 is empty, because this station indeed has no forward link (but does have an other_link).
In this situation _get_shortest_route( ) will go into an infinite loop. (This will not happen if the other_link were non-existent.)
From what I understand up to now, when node A3 is examined, $f_node->{link} should be a string containing a comma-separated list of the stations reachable from A3. But in the case of A3, this list starts with a comma. The subsequent split /,/ then yields an array whose first element is empty. Within the following while loop, when an empty list is passed to _get_next_link( ), this function will return success, but with an undefined link value. In this case, the next iteration of the while loop is started, but with unchanged list of links -- hence, infinite loop.
I do not understand the code well enough to supply a patch (sorry!), but from afar I see three possible places where this might be fixed:
- Arguably, the
$f__next->{link} (i.e., the $self->{nodes}->{link} values, should not contain "empty" links. Then the whole problem would not arise. (This seems to be contingent on an other_link being present.)
_get_next_link( ) could signal non-success if it received an empty link list.- In the case of receiving an undefined
$link from _get_next_link( ), the loop in _get_shortest_route( ) should remove the offending first element from the list in $links.
I do not know about the possible side effects of each of these three possibilities and thus cannot say which (if any) of these three ways might be the best.
(As an aside: in _get_shortest_route( ), the test for undefinedness of $link should probably go before using this very same variable within the regular expression, which is currently one line before.)
I am enclosing three files providing a unit test case.
forked-map.zip
Under certain, very specific conditions
get_shortest_route( )may go into an infinite loop without producing a result.(The following is a muchly boiled-down version of a Real World Case.)
The situation comes up with a line A like this:
A3 is a terminus station only (end station, arrivals only, no boarding); A4 is also a terminus station (start station, no arrivals, boarding only). There is a pedestrian connection between A3 and A4 (indicated by the slashes in the diagram above).
The relevant section from the map specification in XML format looks like this:
Note that the link attribute for A3 is empty, because this station indeed has no forward link (but does have an other_link).
In this situation
_get_shortest_route( )will go into an infinite loop. (This will not happen if theother_linkwere non-existent.)From what I understand up to now, when node A3 is examined,
$f_node->{link}should be a string containing a comma-separated list of the stations reachable from A3. But in the case of A3, this list starts with a comma. The subsequentsplit /,/then yields an array whose first element is empty. Within the following while loop, when an empty list is passed to_get_next_link( ), this function will return success, but with an undefined link value. In this case, the next iteration of the while loop is started, but with unchanged list of links -- hence, infinite loop.I do not understand the code well enough to supply a patch (sorry!), but from afar I see three possible places where this might be fixed:
$f__next->{link}(i.e., the$self->{nodes}->{link}values, should not contain "empty" links. Then the whole problem would not arise. (This seems to be contingent on another_linkbeing present.)_get_next_link( )could signal non-success if it received an empty link list.$linkfrom_get_next_link( ), the loop in_get_shortest_route( )should remove the offending first element from the list in$links.I do not know about the possible side effects of each of these three possibilities and thus cannot say which (if any) of these three ways might be the best.
(As an aside: in
_get_shortest_route( ), the test for undefinedness of$linkshould probably go before using this very same variable within the regular expression, which is currently one line before.)I am enclosing three files providing a unit test case.
forked-map.zip