Every light was green

This afternoon, for the first time, a real routing engine planned us a trip by bus: line 06-2, 2,071 seconds from door to door, against 2,585 on foot. Eight and a half minutes saved. Not a landslide, but it's a bus, and it came out of a timetable we wrote ourselves.

That timetable is a GTFS feed, and we've been trying to publish it every weekday morning since March. Until today, nothing in Cuando ever asked it for a bus. This post is about the five months in between, the one long day it took to close them, and how green everything looked the whole time.

Why a routing engine

Part four ended with route search running in the Worker's memory: a graph of stops and edges, and a loop that lists the paths with at most two changes. It works. But it finds routes first and asks the timetable afterwards. It lists candidate paths by counting stops and changes, then looks up when their buses leave and ranks them by total time, waits included. A path it never listed can't win, however soon its bus leaves.

A transit router does it the other way round. It searches the timetable itself, so a route with a twenty-minute wait loses to a longer ride that leaves now.

We already run one. Valhalla is an open-source routing engine, and since last November it has worked out the walking parts of our routes. It runs on a small VM we already had, the same box that draws the map tiles from part two. Valhalla can route public transport too. You just have to feed it GTFS.

A timetable nobody publishes

GTFS is the format transit agencies publish timetables in: a zip of CSV files. stops.txt says where the stops are and routes.txt lists the lines. trips.txt has one row per bus journey, stop_times.txt says when each journey reaches each stop, and calendar.txt says on which days. shapes.txt draws the road the bus takes. Every routing engine reads it. As far as we know, nobody publishes one for Torrevieja.

But we have everything a GTFS feed is made of. Part one's hand-drawn network gives the stops, the lines and the shapes. The timetable patterns ("from C/ Mayor at 07:30, every 30 minutes, till 20:01, weekdays") give the departures. And the trick from part one, a departure time plus the seconds from each stop to the next, gives every arrival. stop_times.txt is that arithmetic, written out for every departure and every stop. Simplified a little:

for (const dep of departures) {
  const vec = vectors.get(`${dep.line}:${dep.from}`) // seconds from each stop to the next
  let t = dep.departure_time * 60
  for (let i = 0; i < vec.length; i++) {
    t += vec[i] // vec[0] is 0 for the first stop
    stopTimes.push({
      trip_id: tripId,
      stop_id: lineStations[fromIdx + i],
      arrival_time: formatTime(t),
      departure_time: formatTime(t),
      stop_sequence: i + 1,
    })
  }
}

It's plain JavaScript in the Worker, plus a small zip library. As the file's header puts it, "nothing here needs a binary, a container, or a GitHub Actions runner."

I wrote the first version on March 6. Every weekday at 04:20 UTC the Worker builds the feed and uploads it to R2, but only when its hash has changed. Ten minutes later a cron job on the VM was meant to check the hash, download the zip if it was new, unpack it for Valhalla and restart it. The feed sits behind a token, because the stops, lines and shapes in it are data we collected by hand.

In the same commit the Worker got a function that asks Valhalla for a route by bus and on foot.

Nothing called it.

The app kept asking the graph search from part four, and the feed kept going out every weekday morning, or trying to. Today we pointed route search at Valhalla and started finding out what we'd been publishing.

Every light was green

Here's what stood between the feed and a bus in the app.

The first one at least looked broken. Building the feed means expanding every departure into a trip and every trip into a row per stop, then zipping the lot, and all of it had to fit in one run of the Worker. When it didn't, the run died halfway, nothing recorded how it ended, and our job list marked it "orphaned". R2 kept whatever the last good run had written. The job is now a durable Cloudflare Workflow in five steps, each with a fresh budget.

The rest are why this post has its title. Each one on its own is enough to lose every bus, or to hide that you have, and none of them turns anything red.

One blank number drops every bus. Valhalla's GTFS reader parses numbers eagerly, and one empty coordinate in shapes.txt makes std::stod throw:

[ERROR] Couldn't find a required file for feed cuando: stod while adding item from shapes.txt
[ERROR] Couldn't find any usable GTFS feeds.

That's not the end of the build. Valhalla carries on without transit and builds a perfectly good graph with no buses in it. And our shapes.txt didn't have one empty coordinate. Over half of its rows looked like this:

guardamar-hospital,,,1

Each edge stores the road it follows as a list of points, and our edges store them in two encodings: [lat, lng] pairs and {latitude, longitude} objects. Both are legitimate, both are common, and the map in the app reads both. The feed builder read only the objects and wrote the pairs as nothing. The best part is the builder's own type declaration, whose comment says the column holds [lat, lng] pairs. The comment was right about half the rows, and the code about the other half.

A zip is a feed too. The image looks for feeds in /gtfs_feeds, a path hard-coded in its scripts, and wants each one unpacked into a directory of its own. The script we committed in March unpacked the feed there correctly, then left the zip lying next to it. Anything else in that folder is treated as a feed of its own, and fails the ingest.

A restart ingests nothing. We run Valhalla from its valhalla-scripted Docker image, which is configured with environment variables, and they don't mean what they say. build_transit=True builds transit only if there are no transit tiles yet. build_tar=True builds the tile archive only if there's no archive yet. And the service serves that archive, not the fresh tiles next to it. From the image's own scripts:

# configure_valhalla.sh: transit builds only if the directory is missing or empty
if [[ "${build_transit}" == "Force" ]] || (! [[ -d ${TRANSIT_DIR} ]] && [[ "${build_transit}" == "True" ]]) || ...

# docker-entrypoint.sh: the archive is built only if it does not already exist
if ([[ "${build_tar_local}" == "True" && ! -f $TILE_TAR ]]) || [[ "${build_tar_local}" == "Force" ]]; then

Our sync script ended with a restart, under the comment "Restart Valhalla to rebuild with new transit data". Once there are transit tiles, a restart rebuilds nothing of the kind. The new feed sits on disk and the old graph keeps answering.

The obvious fix is a trap. The image also takes Force, which rebuilds every time. But a container's environment is fixed when it's created, and ours is set to come back up on its own. Create it once with Force, and every reboot of the VM wipes the tiles and rebuilds them for about twenty minutes, whether the feed changed or not. The compose file we committed in March had a cousin of that switch on, force_rebuild=True. It rebuilds the whole road graph on every start and still leaves existing transit tiles alone: twenty minutes of rebuilding everything except the one thing that changed.

What works is the other way round: leave the variables at True, and delete the transit tiles and the archive before recreating the container. True then builds exactly when there's something to build. A rebuild takes ten to twenty-five minutes on four threads, for an OpenStreetMap extract of about 46 MB.

A calendar runs out without a word. calendar.txt says which days each service runs, between a start date and an end date. Ours covers the departures we've generated, about six weeks ahead. A feed whose end date has passed builds cleanly and routes nobody, with no error at all. The feed we published today stops routing on September 13, unless a newer one replaces it first.

A walk is a 200. When Valhalla has no buses, or none that help, a request for a route by bus doesn't fail. It answers with a walking route and HTTP 200, exactly like a success. The function I wrote in March checked exactly one thing, res.ok. Had anything called it, it would have put a walk into the list of bus routes, and the walk would have looked fine.

Plugging it in

The feed fix went in at five. By a quarter past six, route search in the app came from Valhalla. What the Worker does with the answer:

• Ask more than once. Valhalla returns one itinerary per request, and the app shows a few to choose from. So the Worker asks up to three times, each time excluding the lines that earlier answers used. If an answer comes back the same anyway, it stops.
• Read our own ids back. Valhalla returns the ids from our feed wrapped in its own: cuando_06-2 for the line, cuando_c-argonauto_transit_station for a stop. Strip the wrapping and they're the ids the app already knows, so the app didn't need a single change.
• Never go by the name. Line 06-2's short name is "06", and so is the name of the line running the other way. Look lines up by name and you get the right number in the wrong direction.
• Send local time. Valhalla takes the departure time as a local wall-clock time, because the times in stop_times.txt are local. Send UTC and in August you get the buses from two hours ago.
• Treat a walk as no answer. A response with no bus in it counts as "nothing found". Every line and stop in an answer is checked against the database too, so tiles built from an older dataset show up as a warning in the logs rather than a nameless line in the app.

One setting on the Worker switches route search back to the graph from part four. No app release, no store review.

Then we looked at the map

With real trips coming back, we looked at their shapes. A bus line drawn on a trip stopped 843 metres short of the stop where you get off. Another took an 851-metre detour and skipped a stop. The same lines drew in full in our admin console, which was the clue: the console draws every edge it has, and anything that walks a line's edges in order could lose some.

Four separate bugs did. Each one was silent by construction, with a continue or a filter where a warning should have been:

• The two encodings again, this time in the code that draws a trip's shape. An edge stored as pairs contributed zero points.
• An id parser that ate the id. Old rows store a bare stop id, new ones a full resource name, and a query cut the name after /stations/ with substr(x, instr(x, '/stations/') + length('/stations/')). On a bare id instr returns 0, so the cut started at the id's tenth character: c-argonauto became to, and c-perseo, shorter than that, became nothing at all. Neither matches anything.
• Picking an edge by lowest id. Several lines can run between the same two stops by different roads. The query took the first one, whichever line it belonged to.
• Circular lines. The feed looked up a line's edges by the stop they leave from. A circular line calls at one stop twice, so two edges leave it. The feed kept one and used it both times: the shape ran out along one branch, came back, drew it again, and never drew the other branch, the one with a stop on it.

Earlier in the day, rebuilding the job, we'd found one more. Every trip in the feed had direction_id 0, because the line of code that was supposed to tell the two directions apart compared a line with its own opposite.

The fix came with two jobs that check the geometry, run by hand after someone edits the network. The one that matters here reads the published zip out of R2, so it checks the bytes Valhalla ingests rather than a fresh build that might differ. Its headline check flags any stop more than 120 metres from the shape drawn for its trip. The threshold comes from the bug report: in the good case, stops sat at most 41 metres from the line, and the broken ones missed by 313, 435 and 843.

Navigation day

Twelve pull requests went into navigation and the geometry under it today, from a quarter to three in the afternoon to twenty past ten at night. Three of them fixed the in-memory search from part four, which had troubles of its own. One added Norwegian to route directions, and Swedish to the labels we write ourselves: a town with this many Scandinavian residents should have had both long ago. (Valhalla has no Belarusian at all, so Belarusian readers get theirs in Russian.)

The lesson I'm taking away is about signals. Every check we had asked whether a thing ran: the job, the upload, the container, the HTTP request. Nothing asked whether a bus came out the other end. Whenever the container was answering, it was healthy. It just didn't have any buses.

What's next

• A probe. Every morning, ask Valhalla for a trip that has to include a bus, and fail loudly if it doesn't. Right now "the sync finished" means a rebuild started, and the rebuild runs for up to twenty-five minutes after that.
• Later departures. Valhalla answers "what's the best trip if I leave now?", and the app has no way yet to ask for the one after.
• The data itself. The new jobs have a list for us, and it isn't short.