sealmap_model/
sym.rs

1//! The `sym:` symbol-id grammar.
2//!
3//! A [`SymbolId`] names a definition by **where it sits in the program**, never
4//! by where it sits on disk: no file path, no line number. Moving an item
5//! between files keeps its id; renaming it, or moving it to another module,
6//! changes it. Whether the definition's *content* changed is a separate
7//! question, answered by content fingerprints kept beside the id: identity
8//! and freshness are kept apart, as rustc keeps `DefPath` apart from its
9//! query fingerprints.
10//!
11//! The grammar follows SCIP's symbol strings (descriptor suffixes make the
12//! kind explicit), so a global id maps to a SCIP symbol by replacing the
13//! `sym:` prefix with a scheme name.
14//!
15//! # Grammar
16//!
17//! ```text
18//! id          ::= 'sym:' ( global | path | unresolved )
19//! global      ::= manager ' ' package ' ' version ( ' ' descriptor+ )?
20//! path        ::= 'extern ' name ( '::' name )*
21//! unresolved  ::= '? ' name
22//!
23//! manager     ::= [a-z] [a-z0-9-]*          -- not `extern`
24//! package     ::= field                     -- not `.`
25//! version     ::= '.' | field               -- `.` = the current tree
26//! field       ::= any characters except control characters, non-empty,
27//!                 no leading or trailing space; a space is written twice
28//!
29//! descriptor  ::= name '/'                  -- namespace (module)
30//!               | name '#'                  -- type (struct, enum, union, trait, alias)
31//!               | name '.'                  -- term (const, static)
32//!               | name '(' disambiguator? ').'   -- method or function
33//!               | name ':'                  -- meta
34//!               | name '!'                  -- macro
35//!               | '[' name ']'              -- type parameter (also: trait-impl block)
36//!               | '(' name ')'              -- parameter
37//! disambiguator ::= simple+
38//!
39//! name        ::= simple+ | '`' ( any character, '`' written '``' )* '`'
40//! simple      ::= [A-Za-z0-9_+$-]
41//! ```
42//!
43//! A name made only of `simple` characters is written bare; anything else
44//! (including the empty name) is quoted in backticks, with backticks doubled.
45//! A global id without descriptors names the package root (a crate's root
46//! module).
47//!
48//! The three forms are:
49//!
50//! * **global**: a definition with known kinds all the way down. Everything a
51//!   language adapter *defines* has a global id. The version is `.` for "the tree
52//!   being analysed", so releasing a new version does not churn every id.
53//! * **path**: a path as written that could not be resolved to kinds, such
54//!   as a call into a dependency (`sym:extern serde_json::to_string`). These
55//!   are references, never definitions.
56//! * **unresolved**: a method called on a receiver of unknown type
57//!   (`sym:? insert`).
58//!
59//! # Examples
60//!
61//! ```
62//! use sealmap_model::{Descriptor, Package, SymbolId};
63//!
64//! let pkg = Package::current("cargo", "shop").unwrap();
65//! let db = SymbolId::global(pkg, vec![Descriptor::namespace("db"), Descriptor::r#type("Db")]);
66//! let put = db.child(Descriptor::type_parameter("Store")).unwrap().child(Descriptor::method("put")).unwrap();
67//!
68//! assert_eq!(db.to_string(), "sym:cargo shop . db/Db#");
69//! assert_eq!(put.to_string(), "sym:cargo shop . db/Db#[Store]put().");
70//! // Methods in a trait-impl block belong to the type.
71//! assert_eq!(put.parent(), Some(db.clone()));
72//!
73//! // Parsing is the exact inverse of printing.
74//! assert_eq!("sym:cargo shop . db/Db#[Store]put().".parse::<SymbolId>().unwrap(), put);
75//!
76//! // Names outside the simple set are quoted.
77//! let from = db.child(Descriptor::type_parameter("From<String>")).unwrap().child(Descriptor::method("from")).unwrap();
78//! assert_eq!(from.to_string(), "sym:cargo shop . db/Db#[`From<String>`]from().");
79//!
80//! // References that never resolved to kinds.
81//! assert_eq!(SymbolId::path(["tokio", "spawn"]).unwrap().to_string(), "sym:extern tokio::spawn");
82//! assert_eq!(SymbolId::unresolved("insert").to_string(), "sym:? insert");
83//! ```
84
85use std::borrow::Cow;
86use std::fmt;
87use std::str::FromStr;
88use std::sync::Arc;
89
90use serde::{Deserialize, Deserializer, Serialize, Serializer};
91
92/// The prefix every printed id starts with.
93pub const SYM_PREFIX: &str = "sym:";
94
95/// The reserved word that introduces a [path id](SymbolId::path).
96const EXTERN: &str = "extern";
97
98/// The canonical identity of a symbol. See the [module docs](self) for the
99/// grammar.
100///
101/// An id holds its canonical text (shared, so cloning is cheap). Because
102/// printing is injective and only canonical text parses, two ids are equal
103/// exactly when their texts are, and ids order by their text. A parent's text
104/// is a prefix of its children's, so a parent always sorts before them.
105/// Structural accessors ([`descriptors`](Self::descriptors),
106/// [`package`](Self::package), ...) read the text on demand.
107#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
108pub struct SymbolId(Arc<str>);
109
110/// The structured form, used to build and validate ids.
111#[derive(Debug, Clone, PartialEq, Eq)]
112enum Repr {
113    Global { package: Package, descriptors: Vec<Descriptor> },
114    Path(Vec<String>),
115    Unresolved(String),
116}
117
118/// The package part of a global id: manager, name and version.
119///
120/// ```
121/// use sealmap_model::{Package, Version};
122///
123/// let p = Package::current("npm", "@acme/web app").unwrap();
124/// assert_eq!(p.name(), "@acme/web app");
125/// assert_eq!(p.version(), &Version::Current);
126/// assert!(Package::current("Cargo", "x").is_err()); // managers are lower-case
127/// assert!(Package::current("cargo", " x").is_err()); // no edge spaces
128/// ```
129#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
130pub struct Package {
131    manager: String,
132    name: String,
133    version: Version,
134}
135
136/// The version component of a [`Package`].
137#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
138pub enum Version {
139    /// The tree being analysed, printed `.`.
140    Current,
141    /// A named release, e.g. `1.2.0`.
142    Release(String),
143}
144
145/// One step of a global id: a name plus the kind-explicit suffix.
146///
147/// ```
148/// use sealmap_model::{Descriptor, Suffix};
149///
150/// let d = Descriptor::method("run");
151/// assert_eq!(d.name(), "run");
152/// assert_eq!(d.suffix(), &Suffix::Method { disambiguator: None });
153/// assert!(Descriptor::new("f", Suffix::Method { disambiguator: Some("a b".into()) }).is_err());
154/// ```
155#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
156pub struct Descriptor {
157    name: String,
158    suffix: Suffix,
159}
160
161/// The kind of a [`Descriptor`], after SCIP's descriptor suffixes.
162#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
163pub enum Suffix {
164    /// `name/`: a module or namespace.
165    Namespace,
166    /// `name#`: a type (struct, enum, union, trait, type alias, interface).
167    Type,
168    /// `name.`: a term (constant, static, variable).
169    Term,
170    /// `name(disambiguator).`: a function or method. The optional
171    /// disambiguator tells overloads apart.
172    Method {
173        /// Overload disambiguator, made of simple characters only.
174        disambiguator: Option<String>,
175    },
176    /// `[name]`: a type parameter. Within a type, it also marks a
177    /// trait-implementation block: `Db#[Store]put().` is `put` from
178    /// `impl Store for Db`.
179    TypeParameter,
180    /// `(name)`: a parameter.
181    Parameter,
182    /// `name:`: metadata.
183    Meta,
184    /// `name!`: a macro.
185    Macro,
186}
187
188/// Why an id or one of its parts could not be built or parsed.
189#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
190pub enum IdError {
191    /// The text does not start with `sym:`.
192    #[error("symbol id must start with `sym:`")]
193    MissingPrefix,
194    /// A manager name outside `[a-z][a-z0-9-]*`, or the reserved `extern`.
195    #[error("invalid package manager `{0}`")]
196    Manager(String),
197    /// An empty package name or version, `.` as a package name, a leading or
198    /// trailing space, or a control character.
199    #[error("invalid package field `{0}`")]
200    Field(String),
201    /// A method disambiguator with characters outside the simple set.
202    #[error("invalid method disambiguator `{0}`")]
203    Disambiguator(String),
204    /// A path id needs at least one segment.
205    #[error("a path id needs at least one segment")]
206    EmptyPath,
207    /// The text does not follow the grammar at byte offset `at`.
208    #[error("malformed symbol id at byte {at}: {why}")]
209    Syntax {
210        /// Byte offset into the input.
211        at: usize,
212        /// What was expected.
213        why: &'static str,
214    },
215}
216
217// ------------------------------------------------------------------ Package
218
219impl Package {
220    /// A package with an explicit version.
221    pub fn new(manager: impl Into<String>, name: impl Into<String>, version: Version) -> Result<Self, IdError> {
222        let manager = manager.into();
223        let name = name.into();
224        check_manager(&manager)?;
225        check_field(&name)?;
226        if name == "." {
227            return Err(IdError::Field(name));
228        }
229        if let Version::Release(v) = &version {
230            check_field(v)?;
231            if v == "." {
232                return Err(IdError::Field(v.clone()));
233            }
234        }
235        Ok(Self { manager, name, version })
236    }
237
238    /// A package at [`Version::Current`].
239    pub fn current(manager: impl Into<String>, name: impl Into<String>) -> Result<Self, IdError> {
240        Self::new(manager, name, Version::Current)
241    }
242
243    /// The package manager (`cargo`, `npm`, ...).
244    pub fn manager(&self) -> &str {
245        &self.manager
246    }
247
248    /// The package name (for Rust, the crate name as used in paths).
249    pub fn name(&self) -> &str {
250        &self.name
251    }
252
253    /// The version.
254    pub fn version(&self) -> &Version {
255        &self.version
256    }
257}
258
259fn check_manager(m: &str) -> Result<(), IdError> {
260    let mut cs = m.chars();
261    let ok = matches!(cs.next(), Some('a'..='z'))
262        && cs.all(|c| c.is_ascii_lowercase() || c.is_ascii_digit() || c == '-')
263        && m != EXTERN;
264    if ok { Ok(()) } else { Err(IdError::Manager(m.to_owned())) }
265}
266
267fn check_field(f: &str) -> Result<(), IdError> {
268    let ok = !f.is_empty() && !f.starts_with(' ') && !f.ends_with(' ') && !f.chars().any(char::is_control);
269    if ok { Ok(()) } else { Err(IdError::Field(f.to_owned())) }
270}
271
272// --------------------------------------------------------------- Descriptor
273
274impl Descriptor {
275    /// A descriptor, checking the method disambiguator if there is one.
276    pub fn new(name: impl Into<String>, suffix: Suffix) -> Result<Self, IdError> {
277        if let Suffix::Method { disambiguator: Some(d) } = &suffix {
278            if d.is_empty() || !d.chars().all(is_simple) {
279                return Err(IdError::Disambiguator(d.clone()));
280            }
281        }
282        Ok(Self { name: name.into(), suffix })
283    }
284
285    /// `name/`.
286    pub fn namespace(name: impl Into<String>) -> Self {
287        Self { name: name.into(), suffix: Suffix::Namespace }
288    }
289
290    /// `name#`.
291    pub fn r#type(name: impl Into<String>) -> Self {
292        Self { name: name.into(), suffix: Suffix::Type }
293    }
294
295    /// `name.`.
296    pub fn term(name: impl Into<String>) -> Self {
297        Self { name: name.into(), suffix: Suffix::Term }
298    }
299
300    /// `name().`.
301    pub fn method(name: impl Into<String>) -> Self {
302        Self { name: name.into(), suffix: Suffix::Method { disambiguator: None } }
303    }
304
305    /// `[name]`.
306    pub fn type_parameter(name: impl Into<String>) -> Self {
307        Self { name: name.into(), suffix: Suffix::TypeParameter }
308    }
309
310    /// `(name)`.
311    pub fn parameter(name: impl Into<String>) -> Self {
312        Self { name: name.into(), suffix: Suffix::Parameter }
313    }
314
315    /// `name:`.
316    pub fn meta(name: impl Into<String>) -> Self {
317        Self { name: name.into(), suffix: Suffix::Meta }
318    }
319
320    /// `name!`.
321    pub fn r#macro(name: impl Into<String>) -> Self {
322        Self { name: name.into(), suffix: Suffix::Macro }
323    }
324
325    /// The name, unescaped.
326    pub fn name(&self) -> &str {
327        &self.name
328    }
329
330    /// The kind suffix.
331    pub fn suffix(&self) -> &Suffix {
332        &self.suffix
333    }
334
335    fn write(&self, out: &mut String) {
336        match &self.suffix {
337            Suffix::TypeParameter => {
338                out.push('[');
339                write_name(&self.name, out);
340                out.push(']');
341            }
342            Suffix::Parameter => {
343                out.push('(');
344                write_name(&self.name, out);
345                out.push(')');
346            }
347            other => {
348                write_name(&self.name, out);
349                match other {
350                    Suffix::Namespace => out.push('/'),
351                    Suffix::Type => out.push('#'),
352                    Suffix::Term => out.push('.'),
353                    Suffix::Meta => out.push(':'),
354                    Suffix::Macro => out.push('!'),
355                    Suffix::Method { disambiguator } => {
356                        out.push('(');
357                        out.push_str(disambiguator.as_deref().unwrap_or(""));
358                        out.push_str(").");
359                    }
360                    Suffix::TypeParameter | Suffix::Parameter => unreachable!("handled above"),
361                }
362            }
363        }
364    }
365}
366
367/// SCIP's simple-identifier characters.
368fn is_simple(c: char) -> bool {
369    c.is_ascii_alphanumeric() || matches!(c, '_' | '+' | '-' | '$')
370}
371
372fn write_name(name: &str, out: &mut String) {
373    if !name.is_empty() && name.chars().all(is_simple) {
374        out.push_str(name);
375        return;
376    }
377    out.push('`');
378    for c in name.chars() {
379        if c == '`' {
380            out.push('`');
381        }
382        out.push(c);
383    }
384    out.push('`');
385}
386
387fn write_field(field: &str, out: &mut String) {
388    for c in field.chars() {
389        if c == ' ' {
390            out.push(' ');
391        }
392        out.push(c);
393    }
394}
395
396// ----------------------------------------------------------------- SymbolId
397
398impl SymbolId {
399    fn from_repr(repr: &Repr) -> Self {
400        Self(print(repr).into())
401    }
402
403    /// A global id: `package` followed by `descriptors` (empty for the
404    /// package root).
405    pub fn global(package: Package, descriptors: Vec<Descriptor>) -> Self {
406        Self::from_repr(&Repr::Global { package, descriptors })
407    }
408
409    /// The package root (a crate's root module).
410    pub fn package_root(package: Package) -> Self {
411        Self::global(package, Vec::new())
412    }
413
414    /// A path as written, for references whose kinds are unknown.
415    pub fn path<I, S>(segments: I) -> Result<Self, IdError>
416    where
417        I: IntoIterator<Item = S>,
418        S: Into<String>,
419    {
420        let segs: Vec<String> = segments.into_iter().map(Into::into).collect();
421        if segs.is_empty() {
422            return Err(IdError::EmptyPath);
423        }
424        Ok(Self::from_repr(&Repr::Path(segs)))
425    }
426
427    /// A method called on a receiver of unknown type.
428    pub fn unresolved(name: impl Into<String>) -> Self {
429        Self::from_repr(&Repr::Unresolved(name.into()))
430    }
431
432    /// Parse the canonical form. The exact inverse of [`Display`](fmt::Display):
433    /// only canonical text is accepted (a simple name in backticks, for
434    /// instance, is rejected), so `parse(s)` succeeding implies
435    /// `parse(s)?.to_string() == s`.
436    pub fn parse(text: &str) -> Result<Self, IdError> {
437        let repr = Parser { s: text, pos: 0 }.id()?;
438        // The parser only accepts canonical text; printing back is the
439        // guard that keeps that true, since ids compare by text.
440        if print(&repr) != text {
441            return Err(IdError::Syntax { at: 0, why: "not in canonical form" });
442        }
443        Ok(Self(text.into()))
444    }
445
446    /// The smallest possible id, used as a range bound.
447    pub(crate) fn min_value() -> Self {
448        Self("".into())
449    }
450
451    /// The canonical text, `sym:` prefix included.
452    pub fn as_str(&self) -> &str {
453        &self.0
454    }
455
456    fn repr(&self) -> Repr {
457        Parser { s: &self.0, pos: 0 }.id().expect("a SymbolId always holds canonical text")
458    }
459
460    fn shape(&self) -> Shape<'_> {
461        Shape::of(&self.0)
462    }
463
464    /// `true` for global (kind-explicit) ids.
465    pub fn is_global(&self) -> bool {
466        matches!(self.shape(), Shape::Global { .. })
467    }
468
469    /// `true` for [`SymbolId::unresolved`] ids.
470    pub fn is_unresolved(&self) -> bool {
471        matches!(self.shape(), Shape::Unresolved(_))
472    }
473
474    /// The package of a global id.
475    pub fn package(&self) -> Option<Package> {
476        match self.repr() {
477            Repr::Global { package, .. } => Some(package),
478            _ => None,
479        }
480    }
481
482    /// The descriptors of a global id (empty for the other forms).
483    pub fn descriptors(&self) -> Vec<Descriptor> {
484        match self.repr() {
485            Repr::Global { descriptors, .. } => descriptors,
486            _ => Vec::new(),
487        }
488    }
489
490    /// The segments of a path id.
491    pub fn segments(&self) -> Option<Vec<String>> {
492        match self.repr() {
493            Repr::Path(s) => Some(s),
494            _ => None,
495        }
496    }
497
498    /// The last descriptor of a global id.
499    pub fn last(&self) -> Option<Descriptor> {
500        self.descriptors().pop()
501    }
502
503    /// The short name: the last descriptor's name, the package name of a
504    /// package root, the last path segment, or the unresolved method name.
505    ///
506    /// ```
507    /// # use sealmap_model::SymbolId;
508    /// assert_eq!(SymbolId::parse("sym:cargo a . b/C#go().").unwrap().name(), "go");
509    /// assert_eq!(SymbolId::parse("sym:cargo a .").unwrap().name(), "a");
510    /// ```
511    pub fn name(&self) -> Cow<'_, str> {
512        match self.shape() {
513            Shape::Global { name, descriptors, .. } => {
514                scan_descriptors(descriptors).last().map_or_else(|| unfield(name), |d| unquote(d.name))
515            }
516            Shape::Path(body) => scan_path(body).last().map_or(Cow::Borrowed(""), |s| unquote(s)),
517            Shape::Unresolved(raw) => unquote(raw),
518        }
519    }
520
521    /// The first name: the package name, or the first path segment.
522    /// `None` for unresolved ids.
523    pub fn root(&self) -> Option<Cow<'_, str>> {
524        match self.shape() {
525            Shape::Global { name, .. } => Some(unfield(name)),
526            Shape::Path(body) => scan_path(body).first().map(|s| unquote(s)),
527            Shape::Unresolved(_) => None,
528        }
529    }
530
531    /// The enclosing definition. For a global id, the last descriptor is
532    /// dropped, then any trailing type-parameter descriptors, so a method in
533    /// a trait-impl block has its type as parent. For a path id, the last
534    /// segment is dropped. A package root, a one-segment path and an
535    /// unresolved id have no parent.
536    ///
537    /// ```
538    /// # use sealmap_model::SymbolId;
539    /// let m = SymbolId::parse("sym:cargo a . T#[Tr]f().").unwrap();
540    /// assert_eq!(m.parent().unwrap().to_string(), "sym:cargo a . T#");
541    /// assert_eq!(SymbolId::parse("sym:cargo a . T#").unwrap().parent().unwrap().to_string(), "sym:cargo a .");
542    /// assert!(SymbolId::parse("sym:cargo a .").unwrap().parent().is_none());
543    /// ```
544    pub fn parent(&self) -> Option<SymbolId> {
545        let text: &str = &self.0;
546        match self.shape() {
547            Shape::Global { descriptors, .. } => {
548                let mut spans = scan_descriptors(descriptors);
549                spans.pop()?;
550                while spans.last().is_some_and(|d| d.kind == b'[') {
551                    spans.pop();
552                }
553                let base = text.len() - descriptors.len();
554                let end = match spans.last() {
555                    Some(d) => base + d.end,
556                    // No descriptors left: drop the separating space too.
557                    None => base - 1,
558                };
559                Some(Self(text[..end].into()))
560            }
561            Shape::Path(body) => {
562                let segs = scan_path(body);
563                if segs.len() < 2 {
564                    return None;
565                }
566                let last = segs[segs.len() - 1];
567                let end = text.len() - last.len() - "::".len();
568                Some(Self(text[..end].into()))
569            }
570            Shape::Unresolved(_) => None,
571        }
572    }
573
574    /// Append a descriptor to a global id. `None` for the other forms,
575    /// which have no kinds to extend.
576    pub fn child(&self, descriptor: Descriptor) -> Option<SymbolId> {
577        let Shape::Global { descriptors, .. } = self.shape() else { return None };
578        let mut out = String::with_capacity(self.0.len() + descriptor.name.len() + 4);
579        out.push_str(&self.0);
580        if descriptors.is_empty() {
581            out.push(' ');
582        }
583        descriptor.write(&mut out);
584        Some(Self(out.into()))
585    }
586
587    /// Every name in order: package and descriptor names for a global id,
588    /// the segments of a path id, the name of an unresolved id.
589    pub fn names(&self) -> Vec<Cow<'_, str>> {
590        match self.shape() {
591            Shape::Global { name, descriptors, .. } => std::iter::once(unfield(name))
592                .chain(scan_descriptors(descriptors).into_iter().map(|d| unquote(d.name)))
593                .collect(),
594            Shape::Path(body) => scan_path(body).into_iter().map(unquote).collect(),
595            Shape::Unresolved(raw) => vec![unquote(raw)],
596        }
597    }
598
599    /// Continue an id with a segment of unknown kind: the result is a path
600    /// id made of [`names`](Self::names) plus `segment`. This is how a
601    /// reference that leaves known territory (`krate::known::unknown`) is
602    /// recorded.
603    ///
604    /// ```
605    /// # use sealmap_model::SymbolId;
606    /// let m = SymbolId::parse("sym:cargo a . net/").unwrap();
607    /// assert_eq!(m.extend_path("dial").to_string(), "sym:extern a::net::dial");
608    /// ```
609    pub fn extend_path(&self, segment: &str) -> SymbolId {
610        let mut s: Vec<String> = self.names().into_iter().map(Cow::into_owned).collect();
611        s.push(segment.to_owned());
612        Self::from_repr(&Repr::Path(s))
613    }
614
615    /// A borrowed view of the id's parts. Unlike [`package`](Self::package)
616    /// and [`descriptors`](Self::descriptors) it allocates nothing but the
617    /// descriptor list (and a name only when it needs unescaping), so it
618    /// suits hot paths such as deriving a diagram id per call site.
619    ///
620    /// ```
621    /// use sealmap_model::{DescriptorKind, IdView, SymbolId};
622    ///
623    /// let id = SymbolId::parse("sym:cargo shop . db/Db#[Store]put().").unwrap();
624    /// let IdView::Global(g) = id.view() else { unreachable!() };
625    /// assert_eq!((g.manager, &*g.package, g.version.is_none()), ("cargo", "shop", true));
626    /// let kinds: Vec<_> = g.descriptors.iter().map(|d| (d.kind, &*d.name)).collect();
627    /// assert_eq!(kinds, [
628    ///     (DescriptorKind::Namespace, "db"),
629    ///     (DescriptorKind::Type, "Db"),
630    ///     (DescriptorKind::TypeParameter, "Store"),
631    ///     (DescriptorKind::Method, "put"),
632    /// ]);
633    /// ```
634    pub fn view(&self) -> IdView<'_> {
635        match self.shape() {
636            Shape::Global { manager, name, version, descriptors } => IdView::Global(GlobalView {
637                manager,
638                package: unfield(name),
639                version: (version != ".").then(|| unfield(version)),
640                descriptors: scan_descriptors(descriptors)
641                    .into_iter()
642                    .map(|d| DescriptorView {
643                        name: unquote(d.name),
644                        kind: match d.kind {
645                            b'/' => DescriptorKind::Namespace,
646                            b'#' => DescriptorKind::Type,
647                            b'(' => DescriptorKind::Method,
648                            b'[' => DescriptorKind::TypeParameter,
649                            b')' => DescriptorKind::Parameter,
650                            b':' => DescriptorKind::Meta,
651                            b'!' => DescriptorKind::Macro,
652                            _ => DescriptorKind::Term,
653                        },
654                        disambiguator: (!d.disambiguator.is_empty()).then_some(d.disambiguator),
655                    })
656                    .collect(),
657            }),
658            Shape::Path(body) => IdView::Path(scan_path(body).into_iter().map(unquote).collect()),
659            Shape::Unresolved(raw) => IdView::Unresolved(unquote(raw)),
660        }
661    }
662
663    /// The names joined by `::`, for human-facing labels. Not injective:
664    /// never use it as a key.
665    pub fn display_path(&self) -> String {
666        self.names().join("::")
667    }
668}
669
670impl fmt::Debug for SymbolId {
671    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
672        write!(f, "SymbolId({:?})", &*self.0)
673    }
674}
675
676impl fmt::Display for SymbolId {
677    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
678        f.write_str(&self.0)
679    }
680}
681
682impl FromStr for SymbolId {
683    type Err = IdError;
684    fn from_str(s: &str) -> Result<Self, Self::Err> {
685        Self::parse(s)
686    }
687}
688
689impl Serialize for SymbolId {
690    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
691        serializer.serialize_str(&self.0)
692    }
693}
694
695impl<'de> Deserialize<'de> for SymbolId {
696    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
697        let s = String::deserialize(deserializer)?;
698        Self::parse(&s).map_err(serde::de::Error::custom)
699    }
700}
701
702/// The canonical text of `repr`.
703fn print(repr: &Repr) -> String {
704    let mut out = String::from(SYM_PREFIX);
705    match repr {
706        Repr::Global { package, descriptors } => {
707            out.push_str(&package.manager);
708            out.push(' ');
709            write_field(&package.name, &mut out);
710            out.push(' ');
711            match &package.version {
712                Version::Current => out.push('.'),
713                Version::Release(v) => write_field(v, &mut out),
714            }
715            if !descriptors.is_empty() {
716                out.push(' ');
717                for d in descriptors {
718                    d.write(&mut out);
719                }
720            }
721        }
722        Repr::Path(segs) => {
723            out.push_str(EXTERN);
724            out.push(' ');
725            for (i, s) in segs.iter().enumerate() {
726                if i > 0 {
727                    out.push_str("::");
728                }
729                write_name(s, &mut out);
730            }
731        }
732        Repr::Unresolved(n) => {
733            out.push_str("? ");
734            write_name(n, &mut out);
735        }
736    }
737    out
738}
739
740/// A borrowed view of a [`SymbolId`], from [`SymbolId::view`].
741#[derive(Debug, Clone, PartialEq, Eq)]
742pub enum IdView<'a> {
743    /// A global id.
744    Global(GlobalView<'a>),
745    /// A path id's segments.
746    Path(Vec<Cow<'a, str>>),
747    /// An unresolved method's name.
748    Unresolved(Cow<'a, str>),
749}
750
751/// The parts of a global id.
752#[derive(Debug, Clone, PartialEq, Eq)]
753pub struct GlobalView<'a> {
754    /// The package manager.
755    pub manager: &'a str,
756    /// The package name.
757    pub package: Cow<'a, str>,
758    /// The release version, `None` for [`Version::Current`].
759    pub version: Option<Cow<'a, str>>,
760    /// The descriptors in order.
761    pub descriptors: Vec<DescriptorView<'a>>,
762}
763
764/// One descriptor of a [`GlobalView`].
765#[derive(Debug, Clone, PartialEq, Eq)]
766pub struct DescriptorView<'a> {
767    /// The name, unescaped.
768    pub name: Cow<'a, str>,
769    /// The kind.
770    pub kind: DescriptorKind,
771    /// A method's disambiguator.
772    pub disambiguator: Option<&'a str>,
773}
774
775/// The kind of a descriptor, as in [`Suffix`] without the payload.
776#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
777pub enum DescriptorKind {
778    /// `name/`.
779    Namespace,
780    /// `name#`.
781    Type,
782    /// `name.`.
783    Term,
784    /// `name(…).`.
785    Method,
786    /// `[name]`.
787    TypeParameter,
788    /// `(name)`.
789    Parameter,
790    /// `name:`.
791    Meta,
792    /// `name!`.
793    Macro,
794}
795
796// ------------------------------------------------------------------ scanner
797//
798// Borrowed views of text already known to be canonical. They never allocate
799// unless a name needs unescaping, and never fail: on canonical text every
800// branch below is the one the printer took.
801
802enum Shape<'a> {
803    /// Raw manager, package-name and version fields; `descriptors` is the
804    /// raw text after the version's separating space (empty for a package
805    /// root).
806    Global { manager: &'a str, name: &'a str, version: &'a str, descriptors: &'a str },
807    /// The raw text after `extern `.
808    Path(&'a str),
809    /// The raw name after `? `.
810    Unresolved(&'a str),
811}
812
813impl<'a> Shape<'a> {
814    fn of(text: &'a str) -> Self {
815        let body = text.strip_prefix(SYM_PREFIX).unwrap_or(text);
816        if let Some(raw) = body.strip_prefix("? ") {
817            return Shape::Unresolved(raw);
818        }
819        if let Some(raw) = body.strip_prefix("extern ") {
820            return Shape::Path(raw);
821        }
822        // Field separators are single spaces; literal spaces inside fields
823        // come in pairs.
824        let bytes = body.as_bytes();
825        let mut seps = Vec::with_capacity(3);
826        let mut i = 0;
827        while i < bytes.len() && seps.len() < 3 {
828            if bytes[i] == b' ' {
829                let run = bytes[i..].iter().take_while(|&&b| b == b' ').count();
830                if run % 2 == 1 {
831                    seps.push(i + run - 1);
832                }
833                i += run;
834            } else {
835                i += 1;
836            }
837        }
838        let (a, b) = match (seps.first(), seps.get(1)) {
839            (Some(&a), Some(&b)) => (a, b),
840            _ => (0, 0),
841        };
842        let manager = &body[..a];
843        let name = body.get(a + 1..b).unwrap_or("");
844        let version = seps.get(2).map_or(body.get(b + 1..).unwrap_or(""), |&c| &body[b + 1..c]);
845        let descriptors = seps.get(2).map_or("", |&c| &body[c + 1..]);
846        Shape::Global { manager, name, version, descriptors }
847    }
848}
849
850/// One descriptor in raw text: byte range, raw name and kind byte (the
851/// suffix character, or `[` / `(` for type parameters and parameters).
852struct DescSpan<'a> {
853    end: usize,
854    name: &'a str,
855    /// The suffix byte (`/ # . ( : !`), `[` for a type parameter, `)` for a
856    /// parameter.
857    kind: u8,
858    /// A method's raw disambiguator (empty when there is none).
859    disambiguator: &'a str,
860}
861
862/// The length of the raw name at the start of `s` (quoted or simple).
863fn raw_name_len(s: &str) -> usize {
864    let b = s.as_bytes();
865    if b.first() == Some(&b'`') {
866        let mut i = 1;
867        while i < b.len() {
868            if b[i] == b'`' {
869                if b.get(i + 1) == Some(&b'`') {
870                    i += 2;
871                    continue;
872                }
873                return i + 1;
874            }
875            i += 1;
876        }
877        return b.len();
878    }
879    s.char_indices().find(|&(_, c)| !is_simple(c)).map_or(s.len(), |(i, _)| i)
880}
881
882fn scan_descriptors(s: &str) -> Vec<DescSpan<'_>> {
883    let mut out = Vec::new();
884    let mut pos = 0;
885    while pos < s.len() {
886        let rest = &s[pos..];
887        let (kind, name, len, disambiguator) = match rest.as_bytes()[0] {
888            open @ (b'[' | b'(') => {
889                let n = raw_name_len(&rest[1..]);
890                (if open == b'(' { b')' } else { b'[' }, &rest[1..1 + n], n + 2, "")
891            }
892            _ => {
893                let n = raw_name_len(rest);
894                let kind = rest.as_bytes().get(n).copied().unwrap_or(b'.');
895                if kind == b'(' {
896                    // `name(disambiguator).`
897                    let close = rest[n..].find(").").unwrap_or(rest.len() - n);
898                    (kind, &rest[..n], n + close + 2, rest.get(n + 1..n + close).unwrap_or(""))
899                } else {
900                    (kind, &rest[..n], n + 1, "")
901                }
902            }
903        };
904        pos += len.max(1);
905        out.push(DescSpan { end: pos.min(s.len()), name, kind, disambiguator });
906    }
907    out
908}
909
910fn scan_path(s: &str) -> Vec<&str> {
911    let mut out = Vec::new();
912    let mut pos = 0;
913    loop {
914        let n = raw_name_len(&s[pos..]);
915        out.push(&s[pos..pos + n]);
916        pos += n;
917        if s[pos..].starts_with("::") {
918            pos += 2;
919        } else {
920            return out;
921        }
922    }
923}
924
925/// A raw name without its quotes and doubled backticks.
926fn unquote(raw: &str) -> Cow<'_, str> {
927    match raw.strip_prefix('`').and_then(|r| r.strip_suffix('`')) {
928        Some(inner) if inner.contains("``") => Cow::Owned(inner.replace("``", "`")),
929        Some(inner) => Cow::Borrowed(inner),
930        None => Cow::Borrowed(raw),
931    }
932}
933
934/// A raw package field without its doubled spaces.
935fn unfield(raw: &str) -> Cow<'_, str> {
936    if raw.contains("  ") { Cow::Owned(raw.replace("  ", " ")) } else { Cow::Borrowed(raw) }
937}
938
939// ------------------------------------------------------------------- parser
940
941struct Parser<'a> {
942    s: &'a str,
943    pos: usize,
944}
945
946impl Parser<'_> {
947    fn err(&self, why: &'static str) -> IdError {
948        IdError::Syntax { at: self.pos, why }
949    }
950
951    fn rest(&self) -> &str {
952        &self.s[self.pos..]
953    }
954
955    fn peek(&self) -> Option<char> {
956        self.rest().chars().next()
957    }
958
959    fn eat(&mut self, lit: &str) -> bool {
960        if self.rest().starts_with(lit) {
961            self.pos += lit.len();
962            true
963        } else {
964            false
965        }
966    }
967
968    fn expect(&mut self, lit: &str, why: &'static str) -> Result<(), IdError> {
969        if self.eat(lit) { Ok(()) } else { Err(self.err(why)) }
970    }
971
972    fn done(&self) -> Result<(), IdError> {
973        if self.pos == self.s.len() { Ok(()) } else { Err(self.err("unexpected trailing text")) }
974    }
975
976    fn id(mut self) -> Result<Repr, IdError> {
977        if !self.eat(SYM_PREFIX) {
978            return Err(IdError::MissingPrefix);
979        }
980        if self.eat("? ") {
981            let name = self.name()?;
982            self.done()?;
983            return Ok(Repr::Unresolved(name));
984        }
985        if self.eat("extern ") {
986            let mut segs = vec![self.name()?];
987            while self.eat("::") {
988                segs.push(self.name()?);
989            }
990            self.done()?;
991            return Ok(Repr::Path(segs));
992        }
993        let manager = self.field()?;
994        self.expect(" ", "expected a space after the manager")?;
995        let name = self.field()?;
996        self.expect(" ", "expected a space after the package name")?;
997        let version = self.field()?;
998        let version = if version == "." { Version::Current } else { Version::Release(version) };
999        let package = Package::new(manager, name, version)?;
1000        let mut descriptors = Vec::new();
1001        if self.pos < self.s.len() {
1002            self.expect(" ", "expected a space before the descriptors")?;
1003            if self.pos == self.s.len() {
1004                return Err(self.err("expected a descriptor"));
1005            }
1006            while self.pos < self.s.len() {
1007                descriptors.push(self.descriptor()?);
1008            }
1009        }
1010        Ok(Repr::Global { package, descriptors })
1011    }
1012
1013    /// A package field, up to (not including) the next single space or the
1014    /// end. A doubled space is a literal space.
1015    fn field(&mut self) -> Result<String, IdError> {
1016        let mut out = String::new();
1017        loop {
1018            let rest = self.rest();
1019            if rest.starts_with("  ") {
1020                out.push(' ');
1021                self.pos += 2;
1022                continue;
1023            }
1024            match rest.chars().next() {
1025                None | Some(' ') => break,
1026                Some(c) => {
1027                    out.push(c);
1028                    self.pos += c.len_utf8();
1029                }
1030            }
1031        }
1032        if out.is_empty() {
1033            return Err(self.err("empty package field"));
1034        }
1035        Ok(out)
1036    }
1037
1038    fn name(&mut self) -> Result<String, IdError> {
1039        if self.eat("`") {
1040            let mut out = String::new();
1041            loop {
1042                match self.peek() {
1043                    None => return Err(self.err("unterminated quoted name")),
1044                    Some('`') => {
1045                        if self.rest().starts_with("``") {
1046                            out.push('`');
1047                            self.pos += 2;
1048                        } else {
1049                            if !out.is_empty() && out.chars().all(is_simple) {
1050                                return Err(self.err("a simple name must not be quoted"));
1051                            }
1052                            self.pos += 1;
1053                            return Ok(out);
1054                        }
1055                    }
1056                    Some(c) => {
1057                        out.push(c);
1058                        self.pos += c.len_utf8();
1059                    }
1060                }
1061            }
1062        }
1063        let start = self.pos;
1064        while self.peek().is_some_and(is_simple) {
1065            self.pos += 1;
1066        }
1067        if self.pos == start {
1068            return Err(self.err("expected a name"));
1069        }
1070        Ok(self.s[start..self.pos].to_owned())
1071    }
1072
1073    fn descriptor(&mut self) -> Result<Descriptor, IdError> {
1074        if self.eat("[") {
1075            let name = self.name()?;
1076            self.expect("]", "expected `]`")?;
1077            return Ok(Descriptor::type_parameter(name));
1078        }
1079        if self.eat("(") {
1080            let name = self.name()?;
1081            self.expect(")", "expected `)`")?;
1082            return Ok(Descriptor::parameter(name));
1083        }
1084        let name = self.name()?;
1085        let suffix = match self.peek() {
1086            Some('/') => Suffix::Namespace,
1087            Some('#') => Suffix::Type,
1088            Some('.') => Suffix::Term,
1089            Some(':') => Suffix::Meta,
1090            Some('!') => Suffix::Macro,
1091            Some('(') => {
1092                self.pos += 1;
1093                let start = self.pos;
1094                while self.peek().is_some_and(is_simple) {
1095                    self.pos += 1;
1096                }
1097                let d = &self.s[start..self.pos];
1098                let disambiguator = (!d.is_empty()).then(|| d.to_owned());
1099                self.expect(").", "expected `).`")?;
1100                return Descriptor::new(name, Suffix::Method { disambiguator });
1101            }
1102            _ => return Err(self.err("expected a descriptor suffix")),
1103        };
1104        self.pos += 1;
1105        Ok(Descriptor { name, suffix })
1106    }
1107}
1108
1109#[cfg(test)]
1110mod tests {
1111    use super::*;
1112
1113    fn rt(s: &str) {
1114        let id = SymbolId::parse(s).unwrap_or_else(|e| panic!("{s}: {e}"));
1115        assert_eq!(id.to_string(), s);
1116    }
1117
1118    #[test]
1119    fn round_trips_every_form() {
1120        rt("sym:cargo a .");
1121        rt("sym:cargo a . b/");
1122        rt("sym:cargo a . b/C#d().");
1123        rt("sym:cargo a 1.2.0 b/C#d(+1).");
1124        rt("sym:cargo a . T#[`From<a::B>`]from().");
1125        rt("sym:npm @x/y . index/`POST /api`().");
1126        rt("sym:npm a  b . c/");
1127        rt("sym:cargo a . f().(x)[T]m:k!v.");
1128        rt("sym:cargo a . ``#```a``b```.");
1129        rt("sym:extern tokio::spawn");
1130        rt("sym:extern `?`::`a b`");
1131        rt("sym:? insert");
1132        rt("sym:? ``");
1133    }
1134
1135    #[test]
1136    fn rejects_malformed() {
1137        for bad in [
1138            "",
1139            "cargo a .",
1140            "sym:",
1141            "sym:cargo",
1142            "sym:cargo a",
1143            "sym:cargo a . ",
1144            "sym:Cargo a .",
1145            "sym:extern",
1146            "sym:extern a::",
1147            "sym:cargo a . b",
1148            "sym:cargo a . `b",
1149            "sym:cargo a . b(x y).",
1150            "sym:cargo a . b().c",
1151            "sym:cargo . .",
1152            "sym:cargo a   .",
1153            "sym:? a b",
1154            "sym:? `a`",
1155        ] {
1156            assert!(SymbolId::parse(bad).is_err(), "accepted {bad:?}");
1157        }
1158    }
1159
1160    #[test]
1161    fn json_is_the_canonical_string() {
1162        let id = SymbolId::parse("sym:cargo a . b/C#").unwrap();
1163        let json = serde_json::to_string(&id).unwrap();
1164        assert_eq!(json, "\"sym:cargo a . b/C#\"");
1165        assert_eq!(serde_json::from_str::<SymbolId>(&json).unwrap(), id);
1166        assert!(serde_json::from_str::<SymbolId>("\"a::b\"").is_err());
1167    }
1168}
sealmap_model/sym.rs

sealmap_model/
sym.rs
