mg4/server/maps.go

package main

import (
	"bytes"
	"compress/gzip"
	"context"
	"encoding/json"
	"errors"
	"fmt"
	"io"
	"log/slog"
	"math"
	"net/http"
	"net/url"
	"os"
	"path/filepath"
	"strconv"
	"strings"
	"sync"
	"time"
)

// Maps serves the roads around the car for the Overview's map (the "Grid with map" style). It
// fetches only the tiles a car asks for, as OpenStreetMap vector tiles (OpenMapTiles schema,
// by default from OpenFreeMap), keeps their roads and stores them, so each tile is fetched
// once and the car only ever talks to this server.
//
//	POST /v1/map/roads   {"z":14,"x":…,"y":…}
//	                     → {"z","x","y","extent":4096,"ways":[{"c":class,"p":[x,y,x,y,…]}]}
//
// The car names a web-mercator tile at zoom 14 (about 1.5 km across in central Europe), not
// its position, and in the body so the tile stays out of access logs. Points are tile-local
// in 0..4096 (a little beyond at the edges), simplified to about 1.5 m. Classes: 0 motorway and
// trunk, 1 primary and secondary, 2 tertiary, 3 minor streets (residential, unclassified,
// living streets).
//
// A fetch runs to its end even when the car stops waiting (the car gives up after a few
// seconds), so its next try finds the tile. Tiles are kept in memory (the last mapMemoryTiles)
// and, with a cache directory, on disk for mapCacheAge. The tile's coordinates never appear
// in the log.
type Maps struct {
	// TileJSONURL names the vector tiles: a TileJSON document whose first "tiles" template is
	// used (OpenFreeMap moves its template with every weekly build).
	TileJSONURL string
	// CacheDir keeps fetched tiles across restarts; empty keeps them in memory only.
	CacheDir  string
	UserAgent string
	Client    *http.Client

	mu       sync.Mutex
	memory   map[mapTile]mapEntry
	inflight map[mapTile]*mapFlight
	template string
	tmplAt   time.Time
	// slots limits fetches running at once.
	slots chan struct{}
}

const (
	mapZoom        = 14
	mapExtent      = 4096
	mapMemoryTiles = 300
	mapCacheAge    = 30 * 24 * time.Hour
	maxTileBytes   = 8 << 20
	mapFetchTime   = 60 * time.Second
	templateAge    = 6 * time.Hour
	// The simplification tolerance in tile units (about 0.37 m each at 52° N).
	mapTolerance = 4.0
	// DefaultMapTilesURL is OpenFreeMap's TileJSON: free OpenStreetMap vector tiles, no key.
	DefaultMapTilesURL = "https://tiles.openfreemap.org/planet"
	// mapUserAgent names this service to the tile host.
	mapUserAgent = "nils-mg4-server/2.8 (private car dashboard; roads for an in-car map)"
)

// mapWait is how long a request waits for a fetch: less than the car's own 8 s.
var mapWait = 6 * time.Second

type mapTile struct{ Z, X, Y int }

type mapEntry struct {
	body []byte
	at   time.Time
}

type mapFlight struct {
	done chan struct{}
	body []byte
	err  error
}

// roadClasses maps the OpenMapTiles transportation classes to the four the car draws; the
// rest (service, track, path, rail, ferry…) are left out.
var roadClasses = map[string]int{
	"motorway": 0, "trunk": 0,
	"primary": 1, "secondary": 1,
	"tertiary": 2,
	"minor":    3,
}

type roadTile struct {
	Z      int    `json:"z"`
	X      int    `json:"x"`
	Y      int    `json:"y"`
	Extent int    `json:"extent"`
	Ways   []road `json:"ways"`
}

type road struct {
	C int   `json:"c"`
	P []int `json:"p"`
}

func NewMaps(tileJSONURL, cacheDir, userAgent string) *Maps {
	return &Maps{TileJSONURL: tileJSONURL, CacheDir: cacheDir, UserAgent: userAgent}
}

func (m *Maps) client() *http.Client {
	if m.Client != nil {
		return m.Client
	}
	return &http.Client{Timeout: mapFetchTime}
}

// Tile returns the tile's roads as JSON and whether it came from a cache. Waiting ends with
// ctx; the fetch itself goes on and is kept.
func (m *Maps) Tile(ctx context.Context, t mapTile) ([]byte, bool, error) {
	if body, ok := m.cached(t); ok {
		return body, true, nil
	}
	m.mu.Lock()
	if m.inflight == nil {
		m.inflight = map[mapTile]*mapFlight{}
		m.slots = make(chan struct{}, 2)
	}
	f, running := m.inflight[t]
	if !running {
		f = &mapFlight{done: make(chan struct{})}
		m.inflight[t] = f
		go m.run(t, f)
	}
	m.mu.Unlock()
	select {
	case <-f.done:
		return f.body, false, f.err
	case <-ctx.Done():
		return nil, false, errors.New("still fetching")
	}
}

func (m *Maps) run(t mapTile, f *mapFlight) {
	defer func() {
		m.mu.Lock()
		delete(m.inflight, t)
		m.mu.Unlock()
		close(f.done)
	}()
	m.slots <- struct{}{}
	defer func() { <-m.slots }()
	ctx, cancel := context.WithTimeout(context.Background(), mapFetchTime)
	defer cancel()
	raw, err := m.fetch(ctx, t)
	if err == nil {
		f.body, err = buildTile(t, raw)
	}
	if err != nil {
		f.err = err
		return
	}
	m.store(t, f.body)
	slog.Info("map tile fetched", "ways", strings.Count(string(f.body), `"c":`), "bytes", len(f.body))
}

func (m *Maps) cachePath(t mapTile) string {
	return filepath.Join(m.CacheDir, fmt.Sprintf("%d_%d_%d.json", t.Z, t.X, t.Y))
}

func (m *Maps) cached(t mapTile) ([]byte, bool) {
	m.mu.Lock()
	e, ok := m.memory[t]
	m.mu.Unlock()
	if ok && time.Since(e.at) <= mapCacheAge {
		return e.body, true
	}
	if m.CacheDir == "" {
		return nil, false
	}
	info, err := os.Stat(m.cachePath(t))
	if err != nil || time.Since(info.ModTime()) > mapCacheAge {
		return nil, false
	}
	body, err := os.ReadFile(m.cachePath(t))
	if err != nil || !json.Valid(body) {
		return nil, false
	}
	m.remember(t, body, info.ModTime())
	return body, true
}

func (m *Maps) store(t mapTile, body []byte) {
	m.remember(t, body, time.Now())
	if m.CacheDir == "" {
		return
	}
	tmp := m.cachePath(t) + ".tmp"
	if err := os.WriteFile(tmp, body, 0o600); err != nil {
		slog.Warn("map tile not stored", "error", err)
		return
	}
	if err := os.Rename(tmp, m.cachePath(t)); err != nil {
		slog.Warn("map tile not stored", "error", err)
	}
}

// remember keeps the tile in memory, dropping the oldest when full.
func (m *Maps) remember(t mapTile, body []byte, at time.Time) {
	m.mu.Lock()
	defer m.mu.Unlock()
	if m.memory == nil {
		m.memory = map[mapTile]mapEntry{}
	}
	if _, ok := m.memory[t]; !ok && len(m.memory) >= mapMemoryTiles {
		var oldest mapTile
		var first time.Time
		for k, e := range m.memory {
			if first.IsZero() || e.at.Before(first) {
				oldest, first = k, e.at
			}
		}
		delete(m.memory, oldest)
	}
	m.memory[t] = mapEntry{body: body, at: at}
}

func (m *Maps) get(ctx context.Context, u string, limit int64) ([]byte, error) {
	req, err := http.NewRequestWithContext(ctx, http.MethodGet, u, nil)
	if err != nil {
		return nil, err
	}
	req.Header.Set("User-Agent", m.UserAgent)
	resp, err := m.client().Do(req)
	if err != nil {
		// The URL holds the tile: name the failure, not the request.
		if errors.Is(err, context.DeadlineExceeded) || errors.Is(ctx.Err(), context.DeadlineExceeded) {
			return nil, errors.New("tile host timed out")
		}
		return nil, errors.New("tile host could not be reached")
	}
	defer resp.Body.Close()
	if resp.StatusCode != http.StatusOK {
		_, _ = io.Copy(io.Discard, io.LimitReader(resp.Body, 1<<16))
		return nil, fmt.Errorf("tile host answered %d", resp.StatusCode)
	}
	body, err := io.ReadAll(io.LimitReader(resp.Body, limit+1))
	if err != nil {
		return nil, errors.New("tile host answer could not be read")
	}
	if int64(len(body)) > limit {
		return nil, errors.New("tile host answer is too large")
	}
	return body, nil
}

// tileTemplate is the current {z}/{x}/{y} URL from the TileJSON, looked up every few hours.
func (m *Maps) tileTemplate(ctx context.Context) (string, error) {
	m.mu.Lock()
	tmpl, at := m.template, m.tmplAt
	m.mu.Unlock()
	if tmpl != "" && time.Since(at) < templateAge {
		return tmpl, nil
	}
	body, err := m.get(ctx, m.TileJSONURL, 1<<20)
	if err != nil {
		return "", err
	}
	var doc struct {
		Tiles []string `json:"tiles"`
	}
	if err := json.Unmarshal(body, &doc); err != nil || len(doc.Tiles) == 0 {
		return "", errors.New("tile index has no tiles")
	}
	tmpl = doc.Tiles[0]
	u, err := url.Parse(strings.NewReplacer("{z}", "0", "{x}", "0", "{y}", "0").Replace(tmpl))
	if err != nil || u.Scheme != "https" || u.Host == "" ||
		!strings.Contains(tmpl, "{z}") || !strings.Contains(tmpl, "{x}") || !strings.Contains(tmpl, "{y}") {
		return "", errors.New("tile index names no usable https template")
	}
	m.mu.Lock()
	m.template, m.tmplAt = tmpl, time.Now()
	m.mu.Unlock()
	return tmpl, nil
}

func (m *Maps) fetch(ctx context.Context, t mapTile) ([]byte, error) {
	tmpl, err := m.tileTemplate(ctx)
	if err != nil {
		return nil, err
	}
	u := strings.NewReplacer("{z}", strconv.Itoa(t.Z), "{x}", strconv.Itoa(t.X), "{y}", strconv.Itoa(t.Y)).Replace(tmpl)
	raw, err := m.get(ctx, u, maxTileBytes)
	if err != nil {
		return nil, err
	}
	// Some hosts send the tile gzipped whatever the request said.
	if len(raw) > 2 && raw[0] == 0x1f && raw[1] == 0x8b {
		zr, err := gzip.NewReader(bytes.NewReader(raw))
		if err != nil {
			return nil, errors.New("tile is not readable")
		}
		raw, err = io.ReadAll(io.LimitReader(zr, maxTileBytes+1))
		if err != nil || len(raw) > maxTileBytes {
			return nil, errors.New("tile is not readable")
		}
	}
	return raw, nil
}

// buildTile keeps the roads of the vector tile's transportation layer, in the car's format.
func buildTile(t mapTile, raw []byte) ([]byte, error) {
	lines, err := decodeRoads(raw)
	if err != nil {
		return nil, err
	}
	out := roadTile{Z: t.Z, X: t.X, Y: t.Y, Extent: mapExtent, Ways: []road{}}
	for _, l := range lines {
		pts := simplify(l.points, mapTolerance)
		if len(pts) < 2 {
			continue
		}
		flat := make([]int, 0, len(pts)*2)
		for _, p := range pts {
			flat = append(flat, p[0], p[1])
		}
		out.Ways = append(out.Ways, road{C: l.class, P: flat})
	}
	return json.Marshal(out)
}

// simplify is Douglas–Peucker: the points that keep the line within tol of the original.
func simplify(pts [][2]int, tol float64) [][2]int {
	if len(pts) < 3 {
		return pts
	}
	keep := make([]bool, len(pts))
	keep[0], keep[len(pts)-1] = true, true
	type span struct{ a, b int }
	stack := []span{{0, len(pts) - 1}}
	for len(stack) > 0 {
		s := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		best, at := 0.0, -1
		for i := s.a + 1; i < s.b; i++ {
			if d := segmentDistance(pts[i], pts[s.a], pts[s.b]); d > best {
				best, at = d, i
			}
		}
		if at >= 0 && best > tol {
			keep[at] = true
			stack = append(stack, span{s.a, at}, span{at, s.b})
		}
	}
	var out [][2]int
	for i, k := range keep {
		if k {
			out = append(out, pts[i])
		}
	}
	return out
}

func segmentDistance(p, a, b [2]int) float64 {
	px, py := float64(p[0]), float64(p[1])
	ax, ay, bx, by := float64(a[0]), float64(a[1]), float64(b[0]), float64(b[1])
	dx, dy := bx-ax, by-ay
	if dx == 0 && dy == 0 {
		return math.Hypot(px-ax, py-ay)
	}
	u := ((px-ax)*dx + (py-ay)*dy) / (dx*dx + dy*dy)
	u = max(0, min(1, u))
	return math.Hypot(px-ax-u*dx, py-ay-u*dy)
}

func (a *API) mapRoutes(mux *http.ServeMux) {
	mux.HandleFunc("POST /v1/map/roads", a.ingest(a.mapRoads))
}

func (a *API) mapRoads(w http.ResponseWriter, r *http.Request, c caller, body []byte) error {
	if a.Maps == nil {
		writeJSON(w, http.StatusNotFound, map[string]string{"error": "maps are not enabled"})
		return nil
	}
	var req struct {
		Z, X, Y *int
	}
	if err := json.Unmarshal(body, &req); err != nil || req.Z == nil || req.X == nil || req.Y == nil {
		return invalid("z, x and y are required")
	}
	if *req.Z != mapZoom {
		return invalid("z must be %d", mapZoom)
	}
	limit := 1 << mapZoom
	if *req.X < 0 || *req.X >= limit || *req.Y < 0 || *req.Y >= limit {
		return invalid("x and y must be within the zoom level")
	}
	// The car waits a few seconds at most; the fetch goes on without it.
	wait, cancel := context.WithTimeout(r.Context(), mapWait)
	defer cancel()
	data, _, err := a.Maps.Tile(wait, mapTile{Z: *req.Z, X: *req.X, Y: *req.Y})
	if err != nil {
		slog.Warn("map tile not available yet", "installation", who(c), "error", err)
		w.Header().Set("Retry-After", "10")
		writeJSON(w, http.StatusServiceUnavailable, map[string]string{"error": "map data not available yet, try again shortly"})
		return nil
	}
	w.Header().Set("Content-Type", "application/json")
	if strings.Contains(r.Header.Get("Accept-Encoding"), "gzip") {
		var buf bytes.Buffer
		zw := gzip.NewWriter(&buf)
		_, _ = zw.Write(data)
		_ = zw.Close()
		w.Header().Set("Content-Encoding", "gzip")
		data = buf.Bytes()
	}
	w.WriteHeader(http.StatusOK)
	_, _ = w.Write(data)
	return nil
}