n_http_router.c

Go to the documentation of this file.

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * permissions and limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 */

 
#include "nilorea/n_http_router.h"
 
#include "nilorea/n_common.h"
#include "nilorea/n_log.h"
#include "nilorea/n_str.h"
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* most segments in a pattern or a path the router looks at */
#define N_ROUTER_SEGS_MAX 32
 
/* Segment kinds. The value is also the specificity rank: lower wins. */
typedef enum {
    _SEG_LITERAL = 0,
    _SEG_DIGITS = 1, /* dN */
    _SEG_HEX = 1,    /* hexN, same rank as dN */
    _SEG_INT = 2,
    _SEG_SLUG = 3,
    _SEG_ANY = 4, /* seg */
    _SEG_REST = 5
} _seg_rank;
 
typedef enum {
    _T_LITERAL,
    _T_DIGITS,
    _T_HEX,
    _T_INT,
    _T_SLUG,
    _T_ANY,
    _T_REST
} _seg_type;
 
typedef struct {
    _seg_type type;
    const char* lit; /* literal text, inside the pattern */
    size_t lit_len;
    size_t n;  /* N of dN / hexN / intN */
    int param; /* placeholder index, -1 for a literal */
} _seg;
 
typedef struct {
    const N_ROUTE* route;
    _seg segs[N_ROUTER_SEGS_MAX];
    size_t nb_segs;
    int trailing_slash;
    size_t nb_params;
    char names[N_ROUTE_PARAMS_MAX][N_ROUTE_NAME_MAX + 1];
} _compiled;
 
struct N_ROUTER {
    _compiled* routes;
    size_t nb;
};
 
static int _rank(_seg_type t) {
    switch (t) {
        case _T_LITERAL:
            return _SEG_LITERAL;
        case _T_DIGITS:
            return _SEG_DIGITS;
        case _T_HEX:
            return _SEG_HEX;
        case _T_INT:
            return _SEG_INT;
        case _T_SLUG:
            return _SEG_SLUG;
        case _T_ANY:
            return _SEG_ANY;
        default:
            return _SEG_REST;
    }
}

N_ROUTER* n_router_new(void) {
    N_ROUTER* r = NULL;
    Malloc(r, N_ROUTER, 1);
    return r;
}

void n_router_free(N_ROUTER** r) {
    if (!r || !*r)
        return;
    FreeNoLog((*r)->routes);
    FreeNoLog(*r);
}
 
/* Parse "N" of dN / hexN / intN within [lo, hi]. */
static int _parse_n(const char* s, size_t len, size_t lo, size_t hi, size_t* n) {
    size_t i;
    *n = 0;
    if (len == 0 || len > 2)
        return 0;
    for (i = 0; i < len; i++) {
        if (s[i] < '0' || s[i] > '9')
            return 0;
        *n = *n * 10 + (size_t)(s[i] - '0');
    }
    return *n >= lo && *n <= hi;
}
 
static int _literal_byte_ok(unsigned char c) {
    return c > 0x20 && c < 0x7f && c != '%' && c != '{' && c != '}' && c != '?' && c != '#';
}
 
/* Compile one pattern into c. Returns 1, or 0 with a reason in why. */
static int _compile(const N_ROUTE* route, _compiled* c, const char** why) {
    const char* p = route->pattern;
    size_t len, i = 1;
    memset(c, 0, sizeof(*c));
    c->route = route;
    *why = "";
    if (!route->methods || !route->handler) {
        *why = "no method or no handler";
        return 0;
    }
    if (route->methods & ~(unsigned)(N_ROUTE_GET | N_ROUTE_POST | N_ROUTE_HEAD)) {
        *why = "unknown method bit";
        return 0;
    }
    if (!p || p[0] != '/') {
        *why = "a pattern starts with '/'";
        return 0;
    }
    len = strlen(p);
    if (len > N_HTTP_REQ_PATH_MAX) {
        *why = "pattern too long";
        return 0;
    }
    if (len == 1) {
        c->trailing_slash = 1;
        return 1;
    }
    while (i < len) {
        size_t s = i, e;
        _seg* g;
        while (i < len && p[i] != '/')
            i++;
        e = i;
        if (e == s) {
            *why = "empty segment ('//')";
            return 0;
        }
        if (c->nb_segs >= N_ROUTER_SEGS_MAX) {
            *why = "too many segments";
            return 0;
        }
        if (c->nb_segs > 0 && c->segs[c->nb_segs - 1].type == _T_REST) {
            *why = "{...:rest} must be the last segment";
            return 0;
        }
        g = &c->segs[c->nb_segs];
        g->param = -1;
        if (p[s] == '{') {
            size_t colon = s + 1, nlen, k, tlen;
            const char* t;
            if (p[e - 1] != '}') {
                *why = "a placeholder fills its whole segment";
                return 0;
            }
            while (colon < e - 1 && p[colon] != ':')
                colon++;
            nlen = colon - s - 1;
            if (nlen == 0 || nlen > N_ROUTE_NAME_MAX) {
                *why = "placeholder name empty or too long";
                return 0;
            }
            for (k = s + 1; k < colon; k++)
                if (!((p[k] >= 'a' && p[k] <= 'z') || (p[k] >= '0' && p[k] <= '9') || p[k] == '_')) {
                    *why = "placeholder name is not [a-z0-9_]";
                    return 0;
                }
            if (c->nb_params >= N_ROUTE_PARAMS_MAX) {
                *why = "too many placeholders";
                return 0;
            }
            for (k = 0; k < c->nb_params; k++)
                if (strlen(c->names[k]) == nlen && memcmp(c->names[k], p + s + 1, nlen) == 0) {
                    *why = "duplicate placeholder name";
                    return 0;
                }
            memcpy(c->names[c->nb_params], p + s + 1, nlen);
            c->names[c->nb_params][nlen] = '\0';
            t = colon < e - 1 ? p + colon + 1 : "seg}";
            tlen = colon < e - 1 ? (size_t)(e - 1 - colon - 1) : 3;
            if (tlen == 4 && memcmp(t, "slug", 4) == 0)
                g->type = _T_SLUG;
            else if (tlen == 3 && memcmp(t, "seg", 3) == 0)
                g->type = _T_ANY;
            else if (tlen == 4 && memcmp(t, "rest", 4) == 0)
                g->type = _T_REST;
            else if (tlen > 1 && t[0] == 'd' && _parse_n(t + 1, tlen - 1, 1, 18, &g->n))
                g->type = _T_DIGITS;
            else if (tlen > 3 && memcmp(t, "hex", 3) == 0 && _parse_n(t + 3, tlen - 3, 1, 64, &g->n))
                g->type = _T_HEX;
            else if (tlen > 3 && memcmp(t, "int", 3) == 0 && _parse_n(t + 3, tlen - 3, 1, 18, &g->n))
                g->type = _T_INT;
            else {
                *why = "unknown placeholder type";
                return 0;
            }
            g->param = (int)c->nb_params;
            c->nb_params++;
        } else {
            size_t k;
            for (k = s; k < e; k++)
                if (!_literal_byte_ok((unsigned char)p[k])) {
                    *why = "literal holds a byte outside visible ASCII, or % { } ? #";
                    return 0;
                }
            g->type = _T_LITERAL;
            g->lit = p + s;
            g->lit_len = e - s;
        }
        c->nb_segs++;
        if (i < len) {
            i++; /* skip '/' */
            if (i == len)
                c->trailing_slash = 1;
        }
    }
    if (c->nb_segs > 0 && c->segs[c->nb_segs - 1].type == _T_REST && c->trailing_slash) {
        *why = "{...:rest} takes the trailing '/' itself";
        return 0;
    }
    return 1;
}

int n_router_add(N_ROUTER* r, const N_ROUTE* routes, size_t count) {
    _compiled* grown = NULL;
    size_t i;
    __n_assert(r, return FALSE);
    if (count == 0)
        return TRUE;
    __n_assert(routes, return FALSE);
    Malloc(grown, _compiled, r->nb + count);
    __n_assert(grown, return FALSE);
    if (r->nb)
        memcpy(grown, r->routes, r->nb * sizeof(_compiled));
    for (i = 0; i < count; i++) {
        const char* why = "";
        if (!_compile(&routes[i], &grown[r->nb + i], &why)) {
            n_log(LOG_ERR, "router: route '%s' refused: %s", routes[i].pattern ? routes[i].pattern : "(null)", why);
            Free(grown);
            return FALSE;
        }
    }
    FreeNoLog(r->routes);
    r->routes = grown;
    r->nb += count;
    return TRUE;
}

size_t n_router_count(const N_ROUTER* r) {
    return r ? r->nb : 0;
}

const N_ROUTE* n_router_route(const N_ROUTER* r, size_t i) {
    if (!r || i >= r->nb)
        return NULL;
    return r->routes[i].route;
}
 
/* Effective methods: GET implies HEAD. */
static unsigned _methods(unsigned m) {
    if (m & N_ROUTE_GET)
        m |= N_ROUTE_HEAD;
    return m;
}
 
/* Can two typed segments of the same rank both match some segment? */
static int _types_overlap(const _seg* a, const _seg* b) {
    if (_rank(a->type) == _SEG_DIGITS)
        return a->n == b->n; /* dN / hexN: equal length, digits are hex */
    return 1;
}

int n_router_check(const N_ROUTER* r, char* err, size_t errsz) {
    size_t i, j, k;
    if (err && errsz)
        err[0] = '\0';
    __n_assert(r, return FALSE);
    for (i = 0; i < r->nb; i++) {
        for (j = i + 1; j < r->nb; j++) {
            const _compiled* a = &r->routes[i];
            const _compiled* b = &r->routes[j];
            int ambiguous = 1;
            if (!(_methods(a->route->methods) & _methods(b->route->methods)))
                continue;
            if (a->nb_segs != b->nb_segs || a->trailing_slash != b->trailing_slash)
                continue;
            for (k = 0; k < a->nb_segs && ambiguous; k++) {
                const _seg* x = &a->segs[k];
                const _seg* y = &b->segs[k];
                if (_rank(x->type) != _rank(y->type)) {
                    ambiguous = 0; /* the more specific one wins here */
                } else if (x->type == _T_LITERAL) {
                    ambiguous = x->lit_len == y->lit_len && memcmp(x->lit, y->lit, x->lit_len) == 0;
                } else {
                    ambiguous = _types_overlap(x, y);
                }
            }
            if (ambiguous) {
                if (err && errsz)
                    snprintf(err, errsz, "'%s' and '%s' match the same paths with the same specificity", a->route->pattern, b->route->pattern);
                return FALSE;
            }
        }
    }
    return TRUE;
}
 
/* Does the raw segment [s, s+n) satisfy g? */
static int _seg_fits(const _seg* g, const char* s, size_t n) {
    size_t k;
    switch (g->type) {
        case _T_LITERAL:
            return n == g->lit_len && memcmp(s, g->lit, n) == 0;
        case _T_DIGITS:
        case _T_INT:
            if (n == 0 || (g->type == _T_DIGITS ? n != g->n : n > g->n))
                return 0;
            for (k = 0; k < n; k++)
                if (s[k] < '0' || s[k] > '9')
                    return 0;
            return 1;
        case _T_HEX:
            if (n != g->n)
                return 0;
            for (k = 0; k < n; k++)
                if (!((s[k] >= '0' && s[k] <= '9') || (s[k] >= 'a' && s[k] <= 'f')))
                    return 0;
            return 1;
        case _T_SLUG:
            if (n == 0 || n > 120)
                return 0;
            for (k = 0; k < n; k++)
                if (!((s[k] >= 'a' && s[k] <= 'z') || (s[k] >= '0' && s[k] <= '9') || s[k] == '_' || s[k] == '-'))
                    return 0;
            return 1;
        case _T_ANY:
            return n >= 1 && n <= 255;
        default:
            return n >= 1;
    }
}
 
static int _hexval(char c) {
    if (c >= '0' && c <= '9')
        return c - '0';
    if (c >= 'a' && c <= 'f')
        return c - 'a' + 10;
    if (c >= 'A' && c <= 'F')
        return c - 'A' + 10;
    return -1;
}
 
/* Strictly percent-decode [s, s+n) into dst (n + 1 bytes). Returns the
 * decoded length, or (size_t)-1 on a malformed escape, a NUL or bad UTF-8. */
static size_t _decode(const char* s, size_t n, char* dst) {
    size_t i, o = 0;
    for (i = 0; i < n; i++) {
        char c = s[i];
        if (c == '%') {
            int hi, lo;
            if (n - i < 3 || (hi = _hexval(s[i + 1])) < 0 || (lo = _hexval(s[i + 2])) < 0)
                return (size_t)-1;
            c = (char)((hi << 4) | lo);
            i += 2;
        }
        if (c == '\0')
            return (size_t)-1;
        dst[o++] = c;
    }
    dst[o] = '\0';
    if (!n_str_utf8_valid(dst, o))
        return (size_t)-1;
    return o;
}
 
/* Compare the specificity of two matching routes: < 0 when a is more specific. */
static int _more_specific(const _compiled* a, const _compiled* b) {
    size_t k, n = a->nb_segs < b->nb_segs ? a->nb_segs : b->nb_segs;
    for (k = 0; k < n; k++) {
        int d = _rank(a->segs[k].type) - _rank(b->segs[k].type);
        if (d)
            return d;
    }
    return 0;
}
 
/* Split path into raw segments; returns the count or -1 when there are too many. */
static int _split(const char* path, size_t len, const char** seg, size_t* seglen, int* trailing) {
    size_t i = 1;
    int n = 0;
    *trailing = 0;
    if (len == 1)
        *trailing = 1;
    while (i < len) {
        size_t s = i;
        while (i < len && path[i] != '/')
            i++;
        if (n >= N_ROUTER_SEGS_MAX)
            return -1;
        seg[n] = path + s;
        seglen[n] = i - s;
        n++;
        if (i < len) {
            i++;
            if (i == len)
                *trailing = 1;
        }
    }
    return n;
}
 
/* Does route c match the split path? rest consumes the remainder. */
static int _route_fits(const _compiled* c, const char** seg, const size_t* seglen, int nseg, int trailing) {
    size_t k;
    if (c->nb_segs > 0 && c->segs[c->nb_segs - 1].type == _T_REST) {
        if ((size_t)nseg < c->nb_segs)
            return 0;
    } else if ((size_t)nseg != c->nb_segs || trailing != c->trailing_slash) {
        return 0;
    }
    for (k = 0; k < c->nb_segs; k++) {
        if (c->segs[k].type == _T_REST)
            return 1; /* everything from here on, any length >= 1 */
        if (!_seg_fits(&c->segs[k], seg[k], seglen[k]))
            return 0;
    }
    return 1;
}

N_ROUTER_RESULT n_router_match(const N_ROUTER* r, n_http_req_method method, const char* path, size_t len, N_ROUTE_MATCH* match, unsigned* allowed) {
    const char* seg[N_ROUTER_SEGS_MAX];
    size_t seglen[N_ROUTER_SEGS_MAX];
    char scratch[N_HTTP_REQ_PATH_MAX + 1];
    const _compiled* best = NULL;
    unsigned path_methods = 0, want = N_HTTP_REQ_METHOD_BIT(method);
    int nseg, trailing, k;
    size_t i, o;
 
    if (allowed)
        *allowed = 0;
    if (!r || !path || !match || len == 0 || len > N_HTTP_REQ_PATH_MAX || path[0] != '/')
        return N_ROUTER_BAD_REQUEST;
    nseg = _split(path, len, seg, seglen, &trailing);
    if (nseg < 0)
        return N_ROUTER_NOT_FOUND;
    /* the whole path must decode cleanly, whatever route it ends up on */
    for (k = 0; k < nseg; k++)
        if (_decode(seg[k], seglen[k], scratch) == (size_t)-1)
            return N_ROUTER_BAD_REQUEST;
    for (i = 0; i < r->nb; i++) {
        const _compiled* c = &r->routes[i];
        if (!_route_fits(c, seg, seglen, nseg, trailing))
            continue;
        path_methods |= _methods(c->route->methods);
        if (!(_methods(c->route->methods) & want))
            continue;
        if (!best || _more_specific(c, best) < 0)
            best = c;
    }
    if (!best) {
        if (path_methods) {
            if (allowed)
                *allowed = path_methods;
            return N_ROUTER_METHOD_NOT_ALLOWED;
        }
        return N_ROUTER_NOT_FOUND;
    }
    /* decode the captured values into the match */
    memset(match, 0, sizeof(*match));
    match->route = best->route;
    match->nb_params = best->nb_params;
    o = 0;
    for (i = 0; i < best->nb_segs; i++) {
        const _seg* g = &best->segs[i];
        const char* s = seg[i];
        size_t n = seglen[i], d;
        if (g->param < 0)
            continue;
        if (g->type == _T_REST)
            n = (size_t)(path + len - s); /* remainder, '/' included */
        d = _decode(s, n, match->buf + o);
        if (d == (size_t)-1)
            return N_ROUTER_BAD_REQUEST; /* a %2F-built remainder may still be bad */
        match->names[g->param] = best->names[g->param];
        match->values[g->param] = match->buf + o;
        match->lens[g->param] = d;
        o += d + 1;
    }
    return N_ROUTER_FOUND;
}

const char* n_route_param(const N_ROUTE_MATCH* m, const char* name, size_t* len) {
    size_t i;
    if (len)
        *len = 0;
    if (!m || !name)
        return NULL;
    for (i = 0; i < m->nb_params; i++)
        if (m->names[i] && strcmp(m->names[i], name) == 0) {
            if (len)
                *len = m->lens[i];
            return m->values[i];
        }
    return NULL;
}

int n_router_allow_header(unsigned allowed, char* out, size_t size) {
    char buf[32] = "";
    allowed = _methods(allowed);
    if (allowed & N_ROUTE_GET)
        strcat(buf, "GET");
    if (allowed & N_ROUTE_HEAD)
        strcat(buf, buf[0] ? ", HEAD" : "HEAD");
    if (allowed & N_ROUTE_POST)
        strcat(buf, buf[0] ? ", POST" : "POST");
    if (!out || size <= strlen(buf))
        return FALSE;
    memcpy(out, buf, strlen(buf) + 1);
    return TRUE;
}