ojak/
template.rs

1//! URI templates: the one description of a route that both matches requests
2//! and builds URIs.
3//!
4//! A template is a path in RFC 6570's level 1: literal segments, and `{name}`
5//! expressions, each the whole of a segment or the end of one
6//! (`/users/{user_id}`, `/@{handle}`). Expanding percent-encodes each value,
7//! everything but RFC 3986's unreserved characters, and matching decodes it,
8//! so an identifier can be a UUID, a login name or a DID and come back as it
9//! went in.
10
11use percent_encoding::{AsciiSet, NON_ALPHANUMERIC, percent_decode_str, utf8_percent_encode};
12use std::collections::BTreeMap;
13use std::fmt;
14
15/// What expansion encodes: everything but ALPHA, DIGIT, `-`, `.`, `_`, `~`.
16const COMPONENT: &AsciiSet = &NON_ALPHANUMERIC
17    .remove(b'-')
18    .remove(b'.')
19    .remove(b'_')
20    .remove(b'~');
21
22/// The values of a template's expressions, by name.
23#[derive(Clone, Debug, Default, Eq, PartialEq)]
24pub struct Values(BTreeMap<String, String>);
25
26impl Values {
27    #[must_use]
28    pub fn new() -> Self {
29        Self::default()
30    }
31
32    /// The value of `name`, if the template has it.
33    #[must_use]
34    pub fn get(&self, name: &str) -> Option<&str> {
35        self.0.get(name).map(String::as_str)
36    }
37
38    pub fn insert(&mut self, name: impl Into<String>, value: impl Into<String>) {
39        self.0.insert(name.into(), value.into());
40    }
41
42    pub fn iter(&self) -> impl Iterator<Item = (&str, &str)> {
43        self.0.iter().map(|(k, v)| (k.as_str(), v.as_str()))
44    }
45
46    /// The only value, for a template with one expression.
47    #[must_use]
48    pub fn single(&self) -> Option<&str> {
49        let mut values = self.0.values();
50        match (values.next(), values.next()) {
51            (Some(value), None) => Some(value),
52            _ => None,
53        }
54    }
55}
56
57impl std::ops::Index<&str> for Values {
58    type Output = str;
59
60    /// # Panics
61    ///
62    /// When the template has no expression `name`.
63    fn index(&self, name: &str) -> &str {
64        self.get(name)
65            .unwrap_or_else(|| panic!("no template value {name:?}"))
66    }
67}
68
69impl<K: Into<String>, V: Into<String>> FromIterator<(K, V)> for Values {
70    fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
71        Self(
72            iter.into_iter()
73                .map(|(k, v)| (k.into(), v.into()))
74                .collect(),
75        )
76    }
77}
78
79/// Why a template is not one.
80#[derive(Clone, Debug, Eq, PartialEq)]
81pub struct TemplateError(pub String);
82
83impl fmt::Display for TemplateError {
84    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
85        f.write_str(&self.0)
86    }
87}
88
89impl std::error::Error for TemplateError {}
90
91#[derive(Clone, Debug, Eq, PartialEq)]
92enum Segment {
93    Literal(String),
94    /// A literal prefix, possibly empty, and then an expression.
95    Expression {
96        prefix: String,
97        name: String,
98    },
99}
100
101/// A parsed template.
102#[derive(Clone, Debug, Eq, PartialEq)]
103pub struct Template {
104    source: String,
105    segments: Vec<Segment>,
106}
107
108impl Template {
109    /// Parse `source`.
110    ///
111    /// # Errors
112    ///
113    /// When it does not start with `/`, has an empty segment, a query or
114    /// fragment, an expression that is not the end of its segment, one that
115    /// is not a plain name, or two expressions of one name.
116    pub fn parse(source: &str) -> Result<Self, TemplateError> {
117        let error = |why: &str| Err(TemplateError(format!("{source:?}: {why}")));
118        let Some(path) = source.strip_prefix('/') else {
119            return error("a template is a path starting with /");
120        };
121        if source.contains(['?', '#']) {
122            return error("a template has no query or fragment");
123        }
124        let mut segments = Vec::new();
125        let mut names = Vec::new();
126        if !path.is_empty() {
127            for segment in path.split('/') {
128                if segment.is_empty() {
129                    return error("empty segment");
130                }
131                match segment.find('{') {
132                    None if segment.contains('}') => return error("unmatched }"),
133                    None => segments.push(Segment::Literal(segment.to_owned())),
134                    Some(open) => {
135                        let (prefix, expression) = segment.split_at(open);
136                        let Some(name) = expression
137                            .strip_prefix('{')
138                            .and_then(|rest| rest.strip_suffix('}'))
139                        else {
140                            return error("an expression is the end of its segment");
141                        };
142                        if name.is_empty()
143                            || !name.chars().all(|c| c.is_ascii_alphanumeric() || c == '_')
144                        {
145                            return error("an expression is {name}, with a plain name");
146                        }
147                        if names.contains(&name) {
148                            return error("an expression name appears twice");
149                        }
150                        names.push(name);
151                        segments.push(Segment::Expression {
152                            prefix: prefix.to_owned(),
153                            name: name.to_owned(),
154                        });
155                    }
156                }
157            }
158        }
159        Ok(Self {
160            source: source.to_owned(),
161            segments,
162        })
163    }
164
165    /// The template as written.
166    #[must_use]
167    pub fn as_str(&self) -> &str {
168        &self.source
169    }
170
171    /// The names of its expressions, in order.
172    pub fn names(&self) -> impl Iterator<Item = &str> {
173        self.segments.iter().filter_map(|segment| match segment {
174            Segment::Expression { name, .. } => Some(name.as_str()),
175            Segment::Literal(_) => None,
176        })
177    }
178
179    /// The path with each expression replaced by its value, encoded.
180    ///
181    /// # Errors
182    ///
183    /// When a value is missing or empty.
184    pub fn expand(&self, values: &Values) -> Result<String, TemplateError> {
185        let mut path = String::new();
186        for segment in &self.segments {
187            path.push('/');
188            match segment {
189                Segment::Literal(literal) => path.push_str(literal),
190                Segment::Expression { prefix, name } => {
191                    let value = values.get(name).filter(|value| !value.is_empty());
192                    let Some(value) = value else {
193                        return Err(TemplateError(format!(
194                            "{:?}: no value for {{{name}}}",
195                            self.source
196                        )));
197                    };
198                    path.push_str(prefix);
199                    path.extend(utf8_percent_encode(value, COMPONENT));
200                }
201            }
202        }
203        if path.is_empty() {
204            path.push('/');
205        }
206        Ok(path)
207    }
208
209    /// The values of `path`, if it matches. `path` has no query.
210    #[must_use]
211    pub fn matches(&self, path: &str) -> Option<Values> {
212        let path = path.strip_prefix('/')?;
213        let parts: Vec<&str> = if path.is_empty() {
214            Vec::new()
215        } else {
216            path.split('/').collect()
217        };
218        if parts.len() != self.segments.len() {
219            return None;
220        }
221        let mut values = Values::new();
222        for (segment, part) in self.segments.iter().zip(parts) {
223            match segment {
224                Segment::Literal(literal) => {
225                    if literal != part {
226                        return None;
227                    }
228                }
229                Segment::Expression { prefix, name } => {
230                    let encoded = part.strip_prefix(prefix.as_str())?;
231                    if encoded.is_empty() {
232                        return None;
233                    }
234                    let value = percent_decode_str(encoded).decode_utf8().ok()?;
235                    values.insert(name.clone(), value.into_owned());
236                }
237            }
238        }
239        Some(values)
240    }
241
242    /// How specific `self` is next to `other`, for a path that matches
243    /// both: at the first segment where they differ, a literal is more
244    /// specific than an expression, and an expression with a longer prefix
245    /// than one with a shorter. `Equal` when no segment tells them apart, so
246    /// that neither can be preferred.
247    #[must_use]
248    pub fn specificity(&self, other: &Self) -> std::cmp::Ordering {
249        fn rank(segment: &Segment) -> (u8, usize) {
250            match segment {
251                Segment::Literal(literal) => (1, literal.len()),
252                Segment::Expression { prefix, .. } => (0, prefix.len()),
253            }
254        }
255        self.segments
256            .iter()
257            .zip(&other.segments)
258            .map(|(a, b)| rank(a).cmp(&rank(b)))
259            .find(|order| order.is_ne())
260            .unwrap_or(std::cmp::Ordering::Equal)
261    }
262
263    /// Whether some path matches both `self` and `other`.
264    #[must_use]
265    pub fn overlaps(&self, other: &Self) -> bool {
266        self.segments.len() == other.segments.len()
267            && self
268                .segments
269                .iter()
270                .zip(&other.segments)
271                .all(|pair| match pair {
272                    (Segment::Literal(a), Segment::Literal(b)) => a == b,
273                    (Segment::Literal(literal), Segment::Expression { prefix, .. })
274                    | (Segment::Expression { prefix, .. }, Segment::Literal(literal)) => {
275                        literal.len() > prefix.len() && literal.starts_with(prefix.as_str())
276                    }
277                    (
278                        Segment::Expression { prefix: a, .. },
279                        Segment::Expression { prefix: b, .. },
280                    ) => a.starts_with(b.as_str()) || b.starts_with(a.as_str()),
281                })
282    }
283}
284
285#[cfg(test)]
286mod tests {
287    use super::*;
288
289    fn template(source: &str) -> Template {
290        Template::parse(source).unwrap()
291    }
292
293    fn values(pairs: &[(&str, &str)]) -> Values {
294        pairs.iter().copied().collect()
295    }
296
297    #[test]
298    fn a_value_survives_the_round_trip() {
299        let t = template("/ap/users/{user_id}");
300        for id in [
301            "0190c2f0-6f3b-7c3e-9d61-3c1b0f6e1a2b",
302            "alice",
303            "did:key:z6MkrJVnaZkeFzdQyMZu1cgjg7k1pZZ6pvBQ7XJPt4swbTQ2",
304            "그림 쟁이",
305            "a/b?c#d%e",
306        ] {
307            let path = t.expand(&values(&[("user_id", id)])).unwrap();
308            assert!(!path[10..].contains(['/', '?', '#', ':', ' ']), "{path}");
309            assert_eq!(t.matches(&path).unwrap().get("user_id"), Some(id), "{path}");
310        }
311    }
312
313    #[test]
314    fn a_prefix_is_part_of_its_segment() {
315        let t = template("/@{handle}");
316        assert_eq!(t.expand(&values(&[("handle", "bob")])).unwrap(), "/@bob");
317        assert_eq!(t.matches("/@bob").unwrap().get("handle"), Some("bob"));
318        assert_eq!(t.matches("/bob"), None);
319        assert_eq!(t.matches("/@"), None, "an expression is never empty");
320    }
321
322    #[test]
323    fn several_expressions_are_read_by_name() {
324        let t = template("/users/{username}/statuses/{id}/activity");
325        let v = t.matches("/users/alice/statuses/42/activity").unwrap();
326        assert_eq!((&v["username"], &v["id"]), ("alice", "42"));
327        assert_eq!(t.names().collect::<Vec<_>>(), ["username", "id"]);
328        assert_eq!(t.matches("/users/alice/statuses/42"), None);
329        assert!(t.expand(&values(&[("username", "alice")])).is_err());
330    }
331
332    #[test]
333    fn a_literal_is_more_specific_than_an_expression() {
334        use std::cmp::Ordering;
335        let followers = template("/@{username}/followers");
336        let status = template("/@{username}/{status_id}");
337        assert!(followers.overlaps(&status));
338        assert_eq!(followers.specificity(&status), Ordering::Greater);
339        assert_eq!(status.specificity(&followers), Ordering::Less);
340        assert_eq!(
341            template("/@{name}").specificity(&template("/{name}")),
342            Ordering::Greater,
343            "a longer prefix is more specific"
344        );
345        assert_eq!(
346            template("/users/{a}").specificity(&template("/users/{b}")),
347            Ordering::Equal
348        );
349    }
350
351    #[test]
352    fn a_template_without_expressions_is_a_fixed_path() {
353        let t = template("/actor");
354        assert_eq!(t.expand(&Values::new()).unwrap(), "/actor");
355        assert_eq!(t.matches("/actor"), Some(Values::new()));
356        assert_eq!(template("/").expand(&Values::new()).unwrap(), "/");
357        assert_eq!(template("/").matches("/"), Some(Values::new()));
358    }
359
360    #[test]
361    fn malformed_templates_are_refused() {
362        for source in [
363            "users/{id}",
364            "/users//{id}",
365            "/users/{id}/",
366            "/users/{id}x",
367            "/users/{}",
368            "/users/{a-b}",
369            "/users/{id}/{id}",
370            "/users/id}",
371            "/users/{id}?page",
372        ] {
373            assert!(Template::parse(source).is_err(), "{source}");
374        }
375    }
376
377    #[test]
378    fn templates_that_could_match_one_path_overlap() {
379        let overlapping = [
380            ("/users/{a}", "/users/{b}"),
381            ("/users/{a}", "/users/alice"),
382            ("/@{a}", "/{b}"),
383            ("/@{a}", "/@alice"),
384        ];
385        for (a, b) in overlapping {
386            assert!(template(a).overlaps(&template(b)), "{a} {b}");
387            assert!(template(b).overlaps(&template(a)), "{b} {a}");
388        }
389        let apart = [
390            ("/users/{a}", "/users/{a}/followers"),
391            ("/users/{a}", "/groups/{a}"),
392            ("/@{a}", "/!{a}"),
393            ("/@{a}", "/@"),
394            ("/actor", "/inbox"),
395        ];
396        for (a, b) in apart {
397            assert!(!template(a).overlaps(&template(b)), "{a} {b}");
398        }
399    }
400}
ojak/template.rs

ojak/
template.rs
