// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! The inverse of reference resolution: given a base and a target, find a //! relative reference that `click` resolves back to the target. //! //! RFC 3986 specifies resolution (§5.2) and says nothing about going the other //! way, so what counts as "the" answer is a choice rather than a rule. The one //! made here is the shortest reference that resolves to the target, preferring //! the reference forms §4.2 lists in the order it lists them: a same-document //! reference, then a relative path, then an absolute path, then a network path, //! and failing all of those the target itself. //! //! The guarantee is the round trip, and it is what the tests assert over every //! case: for any base and target sharing a scheme and authority, //! //! base.clickUri(base.relativize(target)) == target //! //! with both paths' `.` and `..` segments already removed, since resolution //! removes them and a reference therefore cannot reproduce them. const std = @import("std"); const components = @import("components.zig"); const format = @import("format.zig"); const normalize = @import("normalize.zig"); const Components = components.Components; const QueryParam = components.QueryParam; pub const Options = struct { /// When the scheme matches but the authority does not, emit a network-path /// reference — `//other.example/a/b`, the protocol-relative form. /// /// Off by default. It is a correct relative reference and `click` resolves /// it, but a caller asking to relativize against a different host usually /// wants to be told that it cannot be done rather than handed a reference /// whose meaning depends on the scheme it is later read under. network_path: bool = false, /// Use an absolute-path reference (`/a/b`) rather than walking up with /// `..`. Off by default, so that a result is relative to the base's /// directory and a whole tree can be moved without rewriting its links. /// Turn it on for links that must keep working when the document itself /// moves. absolute_path: bool = false, }; /// Whether two query strings hold the same parameters in the same order. fn queryEql(a: []const QueryParam, b: []const QueryParam) bool { if (a.len != b.len) return false; for (a, b) |x, y| { if (!x.eql(y)) return false; } return true; } fn pathEql(a: []const []const u8, b: []const []const u8) bool { if (a.len != b.len) return false; for (a, b) |x, y| { if (!std.mem.eql(u8, x, y)) return false; } return true; } fn schemeEql(a: ?[]const u8, b: ?[]const u8) bool { if (a == null or b == null) return a == null and b == null; return std.ascii.eqlIgnoreCase(a.?, b.?); } /// Whether two references name the same authority, credentials included. A /// reference cannot change the userinfo without restating the whole authority, /// so a differing password is as disqualifying as a differing host. fn authorityEql(a: Components, b: Components) bool { if ((a.host == null) != (b.host == null)) return false; if (a.host) |h| { if (!h.eql(b.host.?)) return false; } if (a.port != b.port) return false; if ((a.username == null) != (b.username == null)) return false; if (a.username) |u| { if (!std.mem.eql(u8, u, b.username.?)) return false; } if ((a.password == null) != (b.password == null)) return false; if (a.password) |p| { if (!std.mem.eql(u8, p, b.password.?)) return false; } return true; } /// The number of leading segments `a` and `b` share. fn commonPrefix(a: []const []const u8, b: []const []const u8) usize { const n = @min(a.len, b.len); var i: usize = 0; while (i < n) : (i += 1) { if (!std.mem.eql(u8, a[i], b[i])) break; } return i; } /// Build `(from.len - k)` parent segments followed by `to[k..]`. fn walkUp( alloc: std.mem.Allocator, from: []const []const u8, to: []const []const u8, k: usize, ) ![]const []const u8 { const ups = from.len - k; const rest = to[k..]; const out = try alloc.alloc([]const u8, ups + rest.len); for (out[0..ups]) |*seg| seg.* = ".."; @memcpy(out[ups..], rest); return out; } /// A relative-path reference whose first segment is empty would be written /// with a leading `/` and read back as a rooted path — or, with a second empty /// segment, as an authority. A leading `.` is the shortest fix, and resolution /// removes it again. /// /// The `:` in a first segment needs no such guard: the formatter escapes it /// with `segment_nc`, which decodes back to the same text. fn guardLeadingEmpty(alloc: std.mem.Allocator, path: []const []const u8) ![]const []const u8 { if (path.len == 0 or path[0].len != 0) return path; const out = try alloc.alloc([]const u8, path.len + 1); out[0] = "."; @memcpy(out[1..], path); return out; } /// Find a relative reference that resolves against `base` to `target`. /// /// Everything in the result is borrowed from `base`, `target` or `alloc`. /// Returns `target` itself when no relative reference would do: a differing /// scheme, a differing authority with `network_path` off, or the one shape a /// reference cannot express — dropping a query the base has and the target /// does not, with no path to carry the change. pub fn relativize( alloc: std.mem.Allocator, base: Components, target: Components, opts: Options, ) !Components { // A relative reference has no scheme, so it can only be read back under // the base's. Nothing else here can make up for that. if (!schemeEql(base.scheme, target.scheme)) return target; if (!authorityEql(base, target)) { if (!opts.network_path or target.host == null) return target; var out = target; out.scheme = null; return out; } // Resolution removes dot segments, so a reference can never resolve *to* // one. Compare against the paths as resolution would leave them. const base_path = try resolved(alloc, base); const target_path = try resolved(alloc, target); const same_document = base.rooted == target.rooted and pathEql(base_path, target_path); // A reference with no path keeps the base's query unless it brings its own // (RFC 3986 §5.2.2), so an empty path cannot clear a query. When the base // has one and the target does not, the reference has to restate the path. const must_restate_path = target.query.len == 0 and base.query.len > 0; if (same_document and !must_restate_path) { // A reference with no path of its own inherits the base's query, so // when the two agree the query need not be written at all: `#f` rather // than `?q=1#f`. When they differ, the target's is what changes it. var out = relative(target, &.{}, false); if (queryEql(base.query, target.query)) out.query = &.{}; return out; } // §5.2.3 merges a relative path against the base's directory, which is the // base path with its last segment dropped. const from = base_path[0..(base_path.len -| 1)]; const to = target_path; var k = commonPrefix(from, to); // A reference that ends in `..` cannot name the target. §5.2.4 leaves a // trailing empty segment behind such a segment, so it always resolves to a // directory -- `..` against `/a/b/c` gives `/a/`, never `/a`. That happens // exactly when the common prefix consumes the whole target, so give up one // segment of it and let the reference end by descending into that segment // again: `../../a` rather than `..`. if (k == to.len and k > 0) k -= 1; const rel = try walkUp(alloc, from, to, k); // Nothing left to say: the base and the target share everything, and the // difference is in a query a path-less reference cannot carry. if (rel.len == 0) return absoluteOrTarget(target, target_path, opts); if (opts.absolute_path) return absoluteOrTarget(target, target_path, opts); return relative(target, try guardLeadingEmpty(alloc, rel), false); } /// The target's path with `.` and `..` resolved, as resolution would leave it. fn resolved(alloc: std.mem.Allocator, c: Components) ![]const []const u8 { const segments = try normalize.resolveDotSegments(alloc, c.path); return normalize.canonicalPath(format.hasAuthority(c), c.rooted, segments).segments; } /// An absolute-path reference (`/a/b`), which needs no authority and survives /// the document moving. Falls back to the target itself when the target has no /// rooted path for one to be made from. fn absoluteOrTarget(target: Components, path: []const []const u8, opts: Options) Components { _ = opts; if (!target.rooted or path.len == 0) return target; return relative(target, path, true); } /// A relative reference carrying `target`'s query and fragment and nothing of /// its scheme or authority. fn relative(target: Components, path: []const []const u8, rooted: bool) Components { return .{ .scheme = null, .username = null, .password = null, .host = null, .port = null, .rooted = rooted, .path = path, .query = target.query, .fragment = target.fragment, }; }