bliksemlabs
Overnight: Reversal on first day of timetable.dat goes wrong
When reversing a request departing at the first possible second in the timetable.dat, the reversal ends up in 1970
CONTEXT
n_stops: 2
n_routes: 1
STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0
stop 1 at lat 0.000000 lon 0.000000
served by routes 0
ROUTES
route 0
serves stops 0 1
STOPIDS
stop 000 has id Stop 2a1
stop 001 has id Stop 2a2
ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 2014-01-01
time: 00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time: --
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 2014-01-01
time: 00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time: --
origin_time 00:00:00
CONTEXT
n_stops: 2
n_routes: 1
STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0
stop 1 at lat 0.000000 lon 0.000000
served by routes 0
ROUTES
route 0
serves stops 0 1
STOPIDS
stop 000 has id Stop 2a1
stop 001 has id Stop 2a2
ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R
Initializing router state
stop 0 was marked as updated
applying transfer at 0 (Stop 2a1)
flagging route 0 at stop 0
route running
Router states:
Stop name [sindex] round 0 round 1 round 2 round 3 round 4 round 5
Stop 2a1 [ 0] 00:00:00 -- -- -- -- --
round 0
route 0: bus long
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
stop 0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
board option 0 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 1 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 2 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 3 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 0 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 1 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 2 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 3 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 0 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
board option 1 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
board option 2 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
board option 3 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
boarding trip 0 at 00:01:00
stop 1 [1] -- Stop 2a2
on board trip 0 considering time 00:03:00
setting stop to 00:03:00
stop 1 was marked as updated
applying transfer at 1 (Stop 2a2)
flagging route 0 at stop 1
route running
round 1
route 0: bus long
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
stop 0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
board option 0 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 1 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 2 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 3 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000000
board option 0 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 1 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 2 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 3 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000001
board option 0 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
board option 1 at 00:01:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
board option 2 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
board option 3 at 00:05:00 -1D
00000000000000000000000000000001
00000000000000000000000000000010
boarding trip 0 at 00:01:00
stop 1 [1] 00:03:00 Stop 2a2
on board trip 0 considering time 00:03:00
(no improvement)
round 2
round 3
round 4
round 5
State present at round 0
-- Router State --
time: 00:03:00
board time: 00:01:00
back trip id: bus long
back route: 0
back stop 0
Repeating search with reversed request:
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
origin_time 00:03:00
CONTEXT
n_stops: 2
n_routes: 1
STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0
stop 1 at lat 0.000000 lon 0.000000
served by routes 0
ROUTES
route 0
serves stops 0 1
STOPIDS
stop 000 has id Stop 2a1
stop 001 has id Stop 2a2
ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R
Initializing router state
stop 1 was marked as updated
applying transfer at 1 (Stop 2a2)
flagging route 0 at stop 1
Router states:
Stop name [sindex] round 0 round 1 round 2 round 3 round 4 round 5
Stop 2a2 [ 1] 00:03:00 -- -- -- -- --
round 0
round 1
round 2
round 3
round 4
round 5
Repeating search with reversed request:
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
origin_time 00:03:00
CONTEXT
n_stops: 2
n_routes: 1
STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0
stop 1 at lat 0.000000 lon 0.000000
served by routes 0
ROUTES
route 0
serves stops 0 1
STOPIDS
stop 000 has id Stop 2a1
stop 001 has id Stop 2a2
ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1pL�R
Initializing router state
stop 1 was marked as updated
applying transfer at 1 (Stop 2a2)
flagging route 0 at stop 1
Router states:
Stop name [sindex] round 0 round 1 round 2 round 3 round 4 round 5
Stop 2a2 [ 1] 00:03:00 -- -- -- -- --
round 0
round 1
round 2
round 3
round 4
round 5
Same one but without t_data_dump at each route_route. This might not just be the first second of the timetable.dat related but more with departing at midnight...
./testerrrr 0 1 2014-01-01T00:00:00 timetable.dat
CONTEXT
n_stops: 2
n_routes: 1
STOPS
stop 0 at lat 0.000000 lon 0.000000
served by routes 0
stop 1 at lat 0.000000 lon 0.000000
served by routes 0
ROUTES
route 0
serves stops 0 1
STOPIDS
stop 000 has id Stop 2a1
stop 001 has id Stop 2a2
ROUTEIDS, TRIPIDS
route 000 has id bus long and first trip id LEV1���R
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 2014-01-01
time: 00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time: --
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 2014-01-01
time: 00:00:00 [1388530800]
speed: 1.500000 m/sec
arrive-by: false
max xfers: 5
max time: --
origin_time 00:00:00
Initializing router state
stop 0 was marked as updated
applying transfer at 0 (Stop 2a1)
flagging route 0 at stop 0
route running
Router states:
Stop name [sindex] round 0 round 1 round 2 round 3 round 4 round 5
Stop 2a1 [ 0] 00:00:00 -- -- -- -- --
round 0
route 0: bus long
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
stop 0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
board option 0 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 1 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 2 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 3 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 0 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 1 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 2 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 3 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 0 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
board option 1 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
board option 2 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
board option 3 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
boarding trip 0 at 00:01:00
stop 1 [1] -- Stop 2a2
on board trip 0 considering time 00:03:00
setting stop to 00:03:00
stop 1 was marked as updated
applying transfer at 1 (Stop 2a2)
flagging route 0 at stop 1
route running
round 1
route 0: bus long
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
stop 0 [0] 00:00:00 Stop 2a1
hit previously-reached stop 0
Route details for 'bus long' [0] (n_stops 2, n_trips 4)
stop sequence, stop name (index), departures
0 Stop 2a1 [000000] : 00:01:00 -1D 00:01:00 -1D 00:05:00 -1D 00:05:00 -1D
1 Stop 2a2 [000001] : 00:03:00 -1D 00:02:00 -1D 00:06:00 -1D 00:07:00 -1D
board option 0 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 1 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 2 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 3 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000001
board option 0 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 1 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 2 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 3 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000010
board option 0 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
board option 1 at 00:01:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
board option 2 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
board option 3 at 00:05:00 -1D
00000000000000000000000000000010
00000000000000000000000000000100
boarding trip 0 at 00:01:00
stop 1 [1] 00:03:00 Stop 2a2
on board trip 0 considering time 00:03:00
(no improvement)
round 2
round 3
round 4
round 5
State present at round 0
-- Router State --
time: 00:03:00
board time: 00:01:00
back trip id: bus long
back route: 0
back stop 0
Repeating search with reversed request:
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
origin_time 00:03:00
Initializing router state
stop 1 was marked as updated
applying transfer at 1 (Stop 2a2)
flagging route 0 at stop 1
Router states:
Stop name [sindex] round 0 round 1 round 2 round 3 round 4 round 5
Stop 2a2 [ 1] 00:03:00 -- -- -- -- --
round 0
round 1
round 2
round 3
round 4
round 5
Repeating search with reversed request:
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
-- Router Request --
from: Stop 2a1 [0]
to: Stop 2a2 [1]
date: 1970-01-01
time: 00:03:00 [180]
speed: 1.500000 m/sec
arrive-by: true
max xfers: 0
max time: 12:02:56 +1D
origin_time 00:03:00
Initializing router state
stop 1 was marked as updated
applying transfer at 1 (Stop 2a2)
flagging route 0 at stop 1
Router states:
Stop name [sindex] round 0 round 1 round 2 round 3 round 4 round 5
Stop 2a2 [ 1] 00:03:00 -- -- -- -- --
round 0
round 1
round 2
round 3
round 4
round 5
This fixes the calendar date, but doesn't fix the actual routing problem.
diff --git a/router.c b/router.c
index 6a0ebbd..69b8bae 100644
--- a/router.c
+++ b/router.c
@@ -530,7 +530,11 @@ bool router_request_reverse(router_t *router, router_request_t *req) {
D router_state_dump (&(states[round][stop]));
req->max_transfers = round;
req->time_cutoff = SEC_TO_RTIME(req->time); // fix units situation -- use durations in seconds o
- req->time = RTIME_TO_SEC(states[round][stop].time - RTIME_ONE_DAY);
+ struct tm origin_tm;
+ rtime_t origin_rtime = epoch_to_rtime (req->time, &origin_tm);
+ origin_tm.tm_min = 0;
+ origin_tm.tm_hour = 0;
+ origin_tm.tm_sec = 0;
+ req->time = RTIME_TO_SEC(states[round][stop].time - RTIME_ONE_DAY) + mktime(&origin_tm);
req->arrive_by = !(req->arrive_by);
// router_request_dump(router, req);
return true;
Final patch.
This is indeed part of the problem, but a deeper problem here is the mixing of internal r(outer)times and epoch times. The epoch time thing seemed like a good idea (especially since I just wanted to test out the date masks) but it's time zone sensitive, and prone to weirdness like this. We should instead store the date and time as separate fields in requests, and only perform math on dates to determine on which day of the internal calendar a request is made. There, in most cases it doesn't matter in which time zone the problem is evaluated because only the relative number of days is important. Daylight saving time problems could be eliminated by evaluating at noon instead of midnight.
I think you should start thinking on a private structure for the request and the public structure. The private structure could contain the rtime and cal_day, while the public part only does have epoch (or struct tm).
But epoch time is not "in a timezone". We might as well avoid that trap and do everything timezone-agnostic. C does easily allow a public and private structure: by including the smaller public structure as the first element of the larger private structure, you should be able to use them somewhat interchangeably.
This is probably partially fixed since we use rtimes now. There is a remaining edge case though: an arrive-by search early on the first day of the schedule may go past midnight into a day where no services are running (its mask is 0). In this case, the search should just fail with no result if the destination cannot be reached. Still, this case should be tested.
TODO check that no-trip-found does not crash but fails gracefully.
Depart-after searches should not encounter this problem during reversal, since the reversed search should be bounded by the original search's departure time.
This does imply a "business rule" though: we should always publish timetables including at least yesterday, today, and tomorrow relative to the date of issue.
If this is a problem, i have no issues at all to just set up as design that "yesterday" should always be exported. Thus that if you export for 2013-09-26, 2013-09-25 is included.
On Thu, Sep 26, 2013 at 6:12 PM, Andrew Byrd [email protected]:
This is probably partially fixed since we use rtimes now. There is a remaining edge case though: an arrive-by search early on the first day of the schedule may go past midnight into a day where no services are running (its mask is 0). In this case, the search should just fail with no result if the destination cannot be reached. Still, this case should be tested.
Depart-after searches should not have this problem at reversal, since the reversed search should be bounded by the original search's departure time.
— Reply to this email directly or view it on GitHubhttps://github.com/abyrd/rrrr/issues/29#issuecomment-25180962 .