Quelle  lifetimes.rs

use proc_macro2::Span;
use quote::{quote, ToTokens};
use serde::{Deserialize, Serialize};
use std::fmt;

use super::{Docs, Ident, Param, SelfParam, TypeName};

/// A named lifetime, e.g. `'a`.
///
/// # Invariants
///
/// Cannot be `'static` or `'_`, use [`Lifetime`] to represent those instead.
#[derive(Clone, Debug, Hash, Eq, PartialEq, Serialize, PartialOrd, Ord)]
#[serde(transparent)]
pub struct NamedLifetime(Ident);

impl NamedLifetime {
    pub fn name(&self) -> &Ident {
        &self.0
    }
}

impl<'de> Deserialize<'de> for NamedLifetime {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        // Special `Deserialize` impl to ensure invariants.
        let named = Ident::deserialize(deserializer)?;
        if named.as_str() == "static" {
            panic!("cannot be static");
        }
        Ok(NamedLifetime(named))
    }
}

impl From<&syn::Lifetime> for NamedLifetime {
    fn from(lt: &syn::Lifetime) -> Self {
        Lifetime::from(lt).to_named().expect("cannot be static")
    }
}

impl From<&NamedLifetime> for NamedLifetime {
    fn from(this: &NamedLifetime) -> Self {
        this.clone()
    }
}

impl PartialEq<syn::Lifetime> for NamedLifetime {
    fn eq(&self, other: &syn::Lifetime) -> bool {
        other.ident == self.0.as_str()
    }
}

impl fmt::Display for NamedLifetime {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "'{}", self.0)
    }
}

impl ToTokens for NamedLifetime {
    fn to_tokens(&self, tokens: &mut proc_macro2::TokenStream) {
        use proc_macro2::{Punct, Spacing};
        Punct::new('\'', Spacing::Joint).to_tokens(tokens);
        self.0.to_tokens(tokens);
    }
}

/// A lifetime dependency graph used for tracking which lifetimes outlive,
/// and are outlived by, other lifetimes.
///
/// It is similar to [`syn::LifetimeDef`], except it can also track lifetime
/// bounds defined in the `where` clause.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub struct LifetimeEnv {
    pub(crate) nodes: Vec<LifetimeNode>,
}

impl LifetimeEnv {
    /// Construct an empty [`LifetimeEnv`].
    ///
    /// To create one outside of this module, use `LifetimeEnv::from_method_item`
    /// or `LifetimeEnv::from` on `&syn::Generics`.
    fn new() -> Self {
        Self { nodes: vec![] }
    }

    /// Iterate through the names of the lifetimes in scope.
    pub fn names(&self) -> impl Iterator<Item = &NamedLifetime> + Clone {
        self.nodes.iter().map(|node| &node.lifetime)
    }

    /// Returns a [`LifetimeEnv`] for a method, accounting for lifetimes and bounds
    /// defined in both the impl block and the method, as well as implicit lifetime
    /// bounds in the optional `self` param, other param, and optional return type.
    /// For example, the type `&'a Foo<'b>` implies `'b: 'a`.
    pub fn from_method_item(
        method: &syn::ImplItemFn,
        impl_generics: Option<&syn::Generics>,
        self_param: Option<&SelfParam>,
        params: &[Param],
        return_type: Option<&TypeName>,
    ) -> Self {
        let mut this = LifetimeEnv::new();
        // The impl generics _must_ be loaded into the env first, since the method
        // generics might use lifetimes defined in the impl, and `extend_generics`
        // panics if `'a: 'b` where `'b` isn't declared by the time it finishes.
        if let Some(generics) = impl_generics {
            this.extend_generics(generics);
        }
        this.extend_generics(&method.sig.generics);

        if let Some(self_param) = self_param {
            this.extend_implicit_lifetime_bounds(&self_param.to_typename(), None);
        }
        for param in params {
            this.extend_implicit_lifetime_bounds(¶m.ty, None);
        }
        if let Some(return_type) = return_type {
            this.extend_implicit_lifetime_bounds(return_type, None);
        }

        this
    }

    /// Returns a [`LifetimeEnv`] for a struct, accounding for lifetimes and bounds
    /// defined in the struct generics, as well as implicit lifetime bounds in
    /// the struct's fields. For example, the field `&'a Foo<'b>` implies `'b: 'a`.
    pub fn from_struct_item(strct: &syn::ItemStruct, fields: &[(Ident, TypeName, Docs)]) -> Self {
        let mut this = LifetimeEnv::new();
        this.extend_generics(&strct.generics);
        for (_, typ, _) in fields {
            this.extend_implicit_lifetime_bounds(typ, None);
        }
        this
    }

    /// Traverse a type, adding any implicit lifetime bounds that arise from
    /// having a reference to an opaque containing a lifetime.
    /// For example, the type `&'a Foo<'b>` implies `'b: 'a`.
    fn extend_implicit_lifetime_bounds(
        &mut self,
        typ: &TypeName,
        behind_ref: Option<&NamedLifetime>,
    ) {
        match typ {
            TypeName::Named(path_type) => {
                if let Some(borrow_lifetime) = behind_ref {
                    let explicit_longer_than_borrow =
                        LifetimeTransitivity::longer_than(self, borrow_lifetime);
                    let mut implicit_longer_than_borrow = vec![];

                    for path_lifetime in path_type.lifetimes.iter() {
                        if let Lifetime::Named(path_lifetime) = path_lifetime {
                            if !explicit_longer_than_borrow.contains(&path_lifetime) {
                                implicit_longer_than_borrow.push(path_lifetime);
                            }
                        }
                    }

                    self.extend_bounds(
                        implicit_longer_than_borrow
                            .into_iter()
                            .map(|path_lifetime| (path_lifetime, Some(borrow_lifetime))),
                    );
                }
            }
            TypeName::Reference(lifetime, _, typ) => {
                let behind_ref = if let Lifetime::Named(named) = lifetime {
                    Some(named)
                } else {
                    None
                };
                self.extend_implicit_lifetime_bounds(typ, behind_ref);
            }
            TypeName::Option(typ) => self.extend_implicit_lifetime_bounds(typ, None),
            TypeName::Result(ok, err, _) => {
                self.extend_implicit_lifetime_bounds(ok, None);
                self.extend_implicit_lifetime_bounds(err, None);
            }
            _ => {}
        }
    }

    /// Add the lifetimes from generic parameters and where bounds.
    fn extend_generics(&mut self, generics: &syn::Generics) {
        let generic_bounds = generics.params.iter().map(|generic| match generic {
            syn::GenericParam::Type(_) => panic!("generic types are unsupported"),
            syn::GenericParam::Lifetime(def) => (&def.lifetime, &def.bounds),
            syn::GenericParam::Const(_) => panic!("const generics are unsupported"),
        });

        let generic_defs = generic_bounds.clone().map(|(lifetime, _)| lifetime);

        self.extend_lifetimes(generic_defs);
        self.extend_bounds(generic_bounds);

        if let Some(ref where_clause) = generics.where_clause {
            self.extend_bounds(where_clause.predicates.iter().map(|pred| match pred {
                syn::WherePredicate::Type(_) => panic!("trait bounds are unsupported"),
                syn::WherePredicate::Lifetime(pred) => (&pred.lifetime, &pred.bounds),
                _ => panic!("Found unknown kind of where predicate"),
            }));
        }
    }

    /// Returns the number of lifetimes in the graph.
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Returns `true` if the graph contains no lifetimes.
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// `<'a, 'b, 'c>`
    ///
    /// Write the existing lifetimes, excluding bounds, as generic parameters.
    ///
    /// To include lifetime bounds, use [`LifetimeEnv::lifetime_defs_to_tokens`].
    pub fn lifetimes_to_tokens(&self) -> proc_macro2::TokenStream {
        if self.is_empty() {
            return quote! {};
        }

        let lifetimes = self.nodes.iter().map(|node| &node.lifetime);
        quote! { <#(#lifetimes),*> }
    }

    /// Returns the index of a lifetime in the graph, or `None` if the lifetime
    /// isn't in the graph.
    pub(crate) fn id<L>(&self, lifetime: &L) -> Option<usize>
    where
        NamedLifetime: PartialEq<L>,
    {
        self.nodes
            .iter()
            .position(|node| &node.lifetime == lifetime)
    }

    /// Add isolated lifetimes to the graph.
    fn extend_lifetimes<'a, L, I>(&mut self, iter: I)
    where
        NamedLifetime: PartialEq<L> + From<&'a L>,
        L: 'a,
        I: IntoIterator<Item = &'a L>,
    {
        for lifetime in iter {
            if self.id(lifetime).is_some() {
                panic!(
                    "lifetime name `{}` declared twice in the same scope",
                    NamedLifetime::from(lifetime)
                );
            }

            self.nodes.push(LifetimeNode {
                lifetime: lifetime.into(),
                shorter: vec![],
                longer: vec![],
            });
        }
    }

    /// Add edges to the lifetime graph.
    ///
    /// This method is decoupled from [`LifetimeEnv::extend_lifetimes`] because
    /// generics can define new lifetimes, while `where` clauses cannot.
    ///
    /// # Panics
    ///
    /// This method panics if any of the lifetime bounds aren't already defined
    /// in the graph. This isn't allowed by rustc in the first place, so it should
    /// only ever occur when deserializing an invalid [`LifetimeEnv`].
    fn extend_bounds<'a, L, B, I>(&mut self, iter: I)
    where
        NamedLifetime: PartialEq<L> + From<&'a L>,
        L: 'a,
        B: IntoIterator<Item = &'a L>,
        I: IntoIterator<Item = (&'a L, B)>,
    {
        for (lifetime, bounds) in iter {
            let long = self.id(lifetime).expect("use of undeclared lifetime, this is a bug: try calling `LifetimeEnv::extend_lifetimes` first");
            for bound in bounds {
                let short = self
                    .id(bound)
                    .expect("cannot use undeclared lifetime as a bound");
                self.nodes[short].longer.push(long);
                self.nodes[long].shorter.push(short);
            }
        }
    }
}

impl fmt::Display for LifetimeEnv {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        self.to_token_stream().fmt(f)
    }
}

impl ToTokens for LifetimeEnv {
    fn to_tokens(&self, tokens: &mut proc_macro2::TokenStream) {
        for node in self.nodes.iter() {
            let lifetime = &node.lifetime;
            if node.shorter.is_empty() {
                tokens.extend(quote! { #lifetime, });
            } else {
                let bounds = node.shorter.iter().map(|&id| &self.nodes[id].lifetime);
                tokens.extend(quote! { #lifetime: #(#bounds)+*, });
            }
        }
    }
}

/// Serialize a [`LifetimeEnv`] as a map from lifetimes to their bounds.
impl Serialize for LifetimeEnv {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        use serde::ser::SerializeMap;
        let mut seq = serializer.serialize_map(Some(self.len()))?;

        for node in self.nodes.iter() {
            /// Helper type for serializing bounds.
            struct Bounds<'a> {
                ids: &'a [usize],
                nodes: &'a [LifetimeNode],
            }

            impl<'a> Serialize for Bounds<'a> {
                fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
                where
                    S: serde::Serializer,
                {
                    use serde::ser::SerializeSeq;
                    let mut seq = serializer.serialize_seq(Some(self.ids.len()))?;
                    for &id in self.ids {
                        seq.serialize_element(&self.nodes[id].lifetime)?;
                    }
                    seq.end()
                }
            }

            seq.serialize_entry(
                &node.lifetime,
                &Bounds {
                    ids: &node.shorter[..],
                    nodes: &self.nodes,
                },
            )?;
        }
        seq.end()
    }
}

impl<'de> Deserialize<'de> for LifetimeEnv {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        use std::collections::BTreeMap;

        let m: BTreeMap<NamedLifetime, Vec<NamedLifetime>> =
            Deserialize::deserialize(deserializer)?;

        let mut this = LifetimeEnv::new();
        this.extend_lifetimes(m.keys());
        this.extend_bounds(m.iter());
        Ok(this)
    }
}

/// A lifetime, along with ptrs to all lifetimes that are explicitly
/// shorter/longer than it.
///
/// This type is internal to [`LifetimeGraph`]- the ptrs are stored as `usize`s,
/// meaning that they may be invalid if a `LifetimeEdges` is created in one
/// `LifetimeGraph` and then used in another.
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub(crate) struct LifetimeNode {
    /// The name of the lifetime.
    pub(crate) lifetime: NamedLifetime,

    /// Pointers to all lifetimes that this lives _at least_ as long as.
    ///
    /// Note: This doesn't account for transitivity.
    pub(crate) shorter: Vec<usize>,

    /// Pointers to all lifetimes that live _at least_ as long as this.
    ///
    /// Note: This doesn't account for transitivity.
    pub(crate) longer: Vec<usize>,
}

/// A lifetime, analogous to [`syn::Lifetime`].
#[derive(Clone, Debug, Hash, Eq, PartialEq, Serialize, Deserialize)]
#[non_exhaustive]
pub enum Lifetime {
    /// The `'static` lifetime.
    Static,

    /// A named lifetime, like `'a`.
    Named(NamedLifetime),

    /// An elided lifetime.
    Anonymous,
}

impl Lifetime {
    /// Returns the inner `NamedLifetime` if the lifetime is the `Named` variant,
    /// otherwise `None`.
    pub fn to_named(self) -> Option<NamedLifetime> {
        if let Lifetime::Named(named) = self {
            return Some(named);
        }
        None
    }

    /// Returns a reference to the inner `NamedLifetime` if the lifetime is the
    /// `Named` variant, otherwise `None`.
    pub fn as_named(&self) -> Option<&NamedLifetime> {
        if let Lifetime::Named(named) = self {
            return Some(named);
        }
        None
    }
}

impl fmt::Display for Lifetime {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Lifetime::Static => "'static".fmt(f),
            Lifetime::Named(ref named) => named.fmt(f),
            Lifetime::Anonymous => "'_".fmt(f),
        }
    }
}

impl ToTokens for Lifetime {
    fn to_tokens(&self, tokens: &mut proc_macro2::TokenStream) {
        match self {
            Lifetime::Static => syn::Lifetime::new("'static", Span::call_site()).to_tokens(tokens),
            Lifetime::Named(ref s) => s.to_tokens(tokens),
            Lifetime::Anonymous => syn::Lifetime::new("'_", Span::call_site()).to_tokens(tokens),
        };
    }
}

impl From<&syn::Lifetime> for Lifetime {
    fn from(lt: &syn::Lifetime) -> Self {
        if lt.ident == "static" {
            Self::Static
        } else {
            Self::Named(NamedLifetime((<.ident).into()))
        }
    }
}

impl From<&Option<syn::Lifetime>> for Lifetime {
    fn from(lt: &Option<syn::Lifetime>) -> Self {
        lt.as_ref().map(Into::into).unwrap_or(Self::Anonymous)
    }
}

impl Lifetime {
    /// Converts the [`Lifetime`] back into an AST node that can be spliced into a program.
    pub fn to_syn(&self) -> Option<syn::Lifetime> {
        match *self {
            Self::Static => Some(syn::Lifetime::new("'static", Span::call_site())),
            Self::Anonymous => None,
            Self::Named(ref s) => Some(syn::Lifetime::new(&s.to_string(), Span::call_site())),
        }
    }
}

/// Collect all lifetimes that are either longer_or_shorter
pub struct LifetimeTransitivity<'env> {
    env: &'env LifetimeEnv,
    visited: Vec<bool>,
    out: Vec<&'env NamedLifetime>,
    longer_or_shorter: LongerOrShorter,
}

impl<'env> LifetimeTransitivity<'env> {
    /// Returns a new [`LifetimeTransitivity`] that finds all longer lifetimes.
    pub fn longer(env: &'env LifetimeEnv) -> Self {
        Self::new(env, LongerOrShorter::Longer)
    }

    /// Returns a new [`LifetimeTransitivity`] that finds all shorter lifetimes.
    pub fn shorter(env: &'env LifetimeEnv) -> Self {
        Self::new(env, LongerOrShorter::Shorter)
    }

    /// Returns all the lifetimes longer than a provided `NamedLifetime`.
    pub fn longer_than(env: &'env LifetimeEnv, named: &NamedLifetime) -> Vec<&'n>env NamedLifetime> {
        let mut this = Self::new(env, LongerOrShorter::Longer);
        this.visit(named);
        this.finish()
    }

    /// Returns all the lifetimes shorter than the provided `NamedLifetime`.
    pub fn shorter_than(env: &'env LifetimeEnv, named: &NamedLifetime) -> Vec<&'an>env NamedLifetime> {
        let mut this = Self::new(env, LongerOrShorter::Shorter);
        this.visit(named);
        this.finish()
    }

    /// Returns a new [`LifetimeTransitivity`].
    fn new(env: &'env LifetimeEnv, longer_or_shorter: LongerOrShorter) -> Self {
        LifetimeTransitivity {
            env,
            visited: vec![false; env.len()],
            out: vec![],
            longer_or_shorter,
        }
    }

    /// Visits a lifetime, as well as all the nodes it's transitively longer or
    /// shorter than, depending on how the `LifetimeTransitivity` was constructed.
    pub fn visit(&mut self, named: &NamedLifetime) {
        if let Some(id) = self
            .env
            .nodes
            .iter()
            .position(|node| node.lifetime == *named)
        {
            self.dfs(id);
        }
    }

    /// Performs depth-first search through the `LifetimeEnv` created at construction
    /// for all nodes longer or shorter than the node at the provided index,
    /// depending on how the `LifetimeTransitivity` was constructed.
    fn dfs(&mut self, index: usize) {
        // Note: all of these indexings SHOULD be valid because
        // `visited.len() == nodes.len()`, and the ids come from
        // calling `Iterator::position` on `nodes`, which never shrinks.
        // So we should be able to change these to `get_unchecked`...
        if !self.visited[index] {
            self.visited[index] = true;

            let node = &self.env.nodes[index];
            self.out.push(&node.lifetime);
            for &edge_index in self.longer_or_shorter.edges(node).iter() {
                self.dfs(edge_index);
            }
        }
    }

    /// Returns the transitively reachable lifetimes.
    pub fn finish(self) -> Vec<&'env NamedLifetime> {
        self.out
    }
}

/// A helper type for [`LifetimeTransitivity`] determining whether to find the
/// transitively longer or transitively shorter lifetimes.
enum LongerOrShorter {
    Longer,
    Shorter,
}

impl LongerOrShorter {
    /// Returns either the indices of the longer or shorter lifetimes, depending
    /// on `self`.
    fn edges<'node>(&self, node: &'node LifetimeNode) -> &'node [usize] {
        match self {
            LongerOrShorter::Longer => &node.longer[..],
            LongerOrShorter::Shorter => &node.shorter[..],
        }
    }
}