Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

8 files changed, 652 insertions, 0 deletions

diff --git a/third_party/rust/yoke-derive/.cargo-checksum.json b/third_party/rust/yoke-derive/.cargo-checksum.json
new file mode 100644
index 0000000000..dd9125cbc0
--- /dev/null
+++ b/third_party/rust/yoke-derive/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.lock":"b049fb914acbe1e0e077dab5d74935eabbe7e9f8b739014c5506397be105bf36","Cargo.toml":"8f9583212657f43f3d9446acf6c96947c4667520ddd1575ec40b7b6cdd1c42ff","LICENSE":"853f87c96f3d249f200fec6db1114427bc8bdf4afddc93c576956d78152ce978","README.md":"5004c9b0aa6e1f4d0e5c8919e14e0bad0cc6753cc589d82aa9521e1bc1fd39bf","examples/yoke_derive.rs":"787ad9872040733c243ec81e67e0b9651937d4e01670b6f050c13e82f1c24a4e","src/lib.rs":"407ff55652d02edea743031c0cadccfe2ca3183e9e0cca8943a6b1bdc7ad630b","src/visitor.rs":"24545c1e81fd35c1d2bd38a1c8d1e684dd08faed4d10d75b103c371df4446c21"},"package":"9e6936f0cce458098a201c245a11bef556c6a0181129c7034d10d76d1ec3a2b8"}
\ No newline at end of file
diff --git a/third_party/rust/yoke-derive/Cargo.lock b/third_party/rust/yoke-derive/Cargo.lock
new file mode 100644
index 0000000000..08850720e8
--- /dev/null
+++ b/third_party/rust/yoke-derive/Cargo.lock
@@ -0,0 +1,66 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.67"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3d433d9f1a3e8c1263d9456598b16fec66f4acc9a74dacffd35c7bb09b3a1328"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.33"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5267fca4496028628a95160fc423a33e8b2e6af8a5302579e322e4b520293cae"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "syn"
+version = "2.0.37"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7303ef2c05cd654186cb250d29049a24840ca25d2747c25c0381c8d9e2f582e8"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
+[[package]]
+name = "synstructure"
+version = "0.13.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "285ba80e733fac80aa4270fbcdf83772a79b80aa35c97075320abfee4a915b06"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+ "unicode-xid",
+]
+
+[[package]]
+name = "unicode-ident"
+version = "1.0.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b"
+
+[[package]]
+name = "unicode-xid"
+version = "0.2.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f962df74c8c05a667b5ee8bcf162993134c104e96440b663c8daa176dc772d8c"
+
+[[package]]
+name = "yoke-derive"
+version = "0.7.3"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+ "synstructure",
+]
diff --git a/third_party/rust/yoke-derive/Cargo.toml b/third_party/rust/yoke-derive/Cargo.toml
new file mode 100644
index 0000000000..8bd87a5f35
--- /dev/null
+++ b/third_party/rust/yoke-derive/Cargo.toml
@@ -0,0 +1,58 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies.
+#
+# If you are reading this file be aware that the original Cargo.toml
+# will likely look very different (and much more reasonable).
+# See Cargo.toml.orig for the original contents.
+
+[package]
+edition = "2021"
+name = "yoke-derive"
+version = "0.7.3"
+authors = ["Manish Goregaokar <manishsmail@gmail.com>"]
+description = "Custom derive for the yoke crate"
+readme = "README.md"
+keywords = [
+    "zerocopy",
+    "serialization",
+    "lifetime",
+    "borrow",
+    "self-referential",
+]
+categories = [
+    "data-structures",
+    "memory-management",
+    "caching",
+    "no-std",
+]
+license-file = "LICENSE"
+repository = "https://github.com/unicode-org/icu4x"
+
+[package.metadata.workspaces]
+independent = true
+
+[lib]
+path = "src/lib.rs"
+proc_macro = true
+
+[dependencies.proc-macro2]
+version = "1.0.27"
+
+[dependencies.quote]
+version = "1.0.9"
+
+[dependencies.syn]
+version = "2"
+features = [
+    "derive",
+    "fold",
+]
+
+[dependencies.synstructure]
+version = "0.13"
+
+[dev-dependencies]
diff --git a/third_party/rust/yoke-derive/LICENSE b/third_party/rust/yoke-derive/LICENSE
new file mode 100644
index 0000000000..9845aa5f48
--- /dev/null
+++ b/third_party/rust/yoke-derive/LICENSE
@@ -0,0 +1,44 @@
+UNICODE LICENSE V3
+
+COPYRIGHT AND PERMISSION NOTICE
+
+Copyright © 2020-2023 Unicode, Inc.
+
+NOTICE TO USER: Carefully read the following legal agreement. BY
+DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING DATA FILES, AND/OR
+SOFTWARE, YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE
+TERMS AND CONDITIONS OF THIS AGREEMENT. IF YOU DO NOT AGREE, DO NOT
+DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE THE DATA FILES OR SOFTWARE.
+
+Permission is hereby granted, free of charge, to any person obtaining a
+copy of data files and any associated documentation (the "Data Files") or
+software and any associated documentation (the "Software") to deal in the
+Data Files or Software without restriction, including without limitation
+the rights to use, copy, modify, merge, publish, distribute, and/or sell
+copies of the Data Files or Software, and to permit persons to whom the
+Data Files or Software are furnished to do so, provided that either (a)
+this copyright and permission notice appear with all copies of the Data
+Files or Software, or (b) this copyright and permission notice appear in
+associated Documentation.
+
+THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
+KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT OF
+THIRD PARTY RIGHTS.
+
+IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE
+BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL DAMAGES,
+OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
+WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
+ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THE DATA
+FILES OR SOFTWARE.
+
+Except as contained in this notice, the name of a copyright holder shall
+not be used in advertising or otherwise to promote the sale, use or other
+dealings in these Data Files or Software without prior written
+authorization of the copyright holder.
+
+—
+
+Portions of ICU4X may have been adapted from ICU4C and/or ICU4J.
+ICU 1.8.1 to ICU 57.1 © 1995-2016 International Business Machines Corporation and others.
diff --git a/third_party/rust/yoke-derive/README.md b/third_party/rust/yoke-derive/README.md
new file mode 100644
index 0000000000..04ef27e066
--- /dev/null
+++ b/third_party/rust/yoke-derive/README.md
@@ -0,0 +1,11 @@
+# yoke-derive [![crates.io](https://img.shields.io/crates/v/yoke-derive)](https://crates.io/crates/yoke-derive)
+
+<!-- cargo-rdme start -->
+
+Custom derives for `Yokeable` from the `yoke` crate.
+
+<!-- cargo-rdme end -->
+
+## More Information
+
+For more information on development, authorship, contributing etc. please visit [`ICU4X home page`](https://github.com/unicode-org/icu4x).
diff --git a/third_party/rust/yoke-derive/examples/yoke_derive.rs b/third_party/rust/yoke-derive/examples/yoke_derive.rs
new file mode 100644
index 0000000000..a011d5c241
--- /dev/null
+++ b/third_party/rust/yoke-derive/examples/yoke_derive.rs
@@ -0,0 +1,86 @@
+// This file is part of ICU4X. For terms of use, please see the file
+// called LICENSE at the top level of the ICU4X source tree
+// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
+#![allow(unused)]
+
+use std::borrow::Cow;
+use yoke::{Yoke, Yokeable};
+use zerovec::{maps::ZeroMapKV, ule::AsULE, VarZeroVec, ZeroMap, ZeroVec};
+
+#[derive(Yokeable)]
+pub struct StringExample {
+    x: String,
+}
+
+#[derive(Yokeable, Copy, Clone)]
+pub struct IntExample {
+    x: u32,
+}
+
+#[derive(Yokeable, Copy, Clone)]
+pub struct GenericsExample<T> {
+    x: u32,
+    y: T,
+}
+
+#[derive(Yokeable, Copy, Clone)]
+pub struct GenericsExampleWithDefault<T, U = usize> {
+    x: T,
+    y: U,
+}
+
+#[derive(Yokeable)]
+pub struct CowExample<'a> {
+    x: u8,
+    y: &'a str,
+    z: Cow<'a, str>,
+    w: Cow<'a, [u8]>,
+}
+
+#[derive(Yokeable)]
+pub struct ZeroVecExample<'a> {
+    var: VarZeroVec<'a, str>,
+    vec: ZeroVec<'a, u16>,
+}
+
+#[derive(Yokeable)]
+pub struct ZeroVecExampleWithGenerics<'a, T: AsULE> {
+    gen: ZeroVec<'a, T>,
+    vec: ZeroVec<'a, u16>,
+    bare: T,
+}
+
+// Since ZeroMap has generic parameters, the Rust compiler cannot
+// prove the covariance of the lifetimes. To use derive(Yokeable)
+// with a type such as ZeroMap, you just add the attribute
+// yoke(prove_covariance_manually)
+#[derive(Yokeable)]
+#[yoke(prove_covariance_manually)]
+pub struct ZeroMapExample<'a> {
+    map: ZeroMap<'a, str, u16>,
+}
+
+#[derive(Yokeable)]
+#[yoke(prove_covariance_manually)]
+pub struct ZeroMapGenericExample<'a, T: for<'b> ZeroMapKV<'b> + ?Sized> {
+    map: ZeroMap<'a, str, T>,
+}
+
+pub struct AssertYokeable {
+    string: Yoke<StringExample, Box<[u8]>>,
+    int: Yoke<IntExample, Box<[u8]>>,
+    gen1: Yoke<GenericsExample<u32>, Box<[u8]>>,
+    gen2: Yoke<GenericsExample<String>, Box<[u8]>>,
+    gen_default1: Yoke<GenericsExampleWithDefault<String>, Box<[u8]>>,
+    gen_default2: Yoke<GenericsExampleWithDefault<String, u8>, Box<[u8]>>,
+    cow: Yoke<CowExample<'static>, Box<[u8]>>,
+    zv: Yoke<ZeroVecExample<'static>, Box<[u8]>>,
+    zv_gen1: Yoke<ZeroVecExampleWithGenerics<'static, u8>, Box<[u8]>>,
+    zv_gen2: Yoke<ZeroVecExampleWithGenerics<'static, char>, Box<[u8]>>,
+    map: Yoke<ZeroMapExample<'static>, Box<[u8]>>,
+    map_gen1: Yoke<ZeroMapGenericExample<'static, u32>, Box<[u8]>>,
+    map_gen2: Yoke<ZeroMapGenericExample<'static, str>, Box<[u8]>>,
+}
+
+fn main() {}
diff --git a/third_party/rust/yoke-derive/src/lib.rs b/third_party/rust/yoke-derive/src/lib.rs
new file mode 100644
index 0000000000..dd1ea90b8d
--- /dev/null
+++ b/third_party/rust/yoke-derive/src/lib.rs
@@ -0,0 +1,273 @@
+// This file is part of ICU4X. For terms of use, please see the file
+// called LICENSE at the top level of the ICU4X source tree
+// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
+//! Custom derives for `Yokeable` from the `yoke` crate.
+
+use proc_macro::TokenStream;
+use proc_macro2::{Span, TokenStream as TokenStream2};
+use quote::quote;
+use syn::spanned::Spanned;
+use syn::{parse_macro_input, parse_quote, DeriveInput, Ident, Lifetime, Type, WherePredicate};
+use synstructure::Structure;
+
+mod visitor;
+
+/// Custom derive for `yoke::Yokeable`,
+///
+/// If your struct contains `zerovec::ZeroMap`, then the compiler will not
+/// be able to guarantee the lifetime covariance due to the generic types on
+/// the `ZeroMap` itself. You must add the following attribute in order for
+/// the custom derive to work with `ZeroMap`.
+///
+/// ```rust,ignore
+/// #[derive(Yokeable)]
+/// #[yoke(prove_covariance_manually)]
+/// ```
+///
+/// Beyond this case, if the derive fails to compile due to lifetime issues, it
+/// means that the lifetime is not covariant and `Yokeable` is not safe to implement.
+#[proc_macro_derive(Yokeable, attributes(yoke))]
+pub fn yokeable_derive(input: TokenStream) -> TokenStream {
+    let input = parse_macro_input!(input as DeriveInput);
+    TokenStream::from(yokeable_derive_impl(&input))
+}
+
+fn yokeable_derive_impl(input: &DeriveInput) -> TokenStream2 {
+    let tybounds = input
+        .generics
+        .type_params()
+        .map(|ty| {
+            // Strip out param defaults, we don't need them in the impl
+            let mut ty = ty.clone();
+            ty.eq_token = None;
+            ty.default = None;
+            ty
+        })
+        .collect::<Vec<_>>();
+    let typarams = tybounds
+        .iter()
+        .map(|ty| ty.ident.clone())
+        .collect::<Vec<_>>();
+    // We require all type parameters be 'static, otherwise
+    // the Yokeable impl becomes really unweildy to generate safely
+    let static_bounds: Vec<WherePredicate> = typarams
+        .iter()
+        .map(|ty| parse_quote!(#ty: 'static))
+        .collect();
+    let lts = input.generics.lifetimes().count();
+    if lts == 0 {
+        let name = &input.ident;
+        quote! {
+            // This is safe because there are no lifetime parameters.
+            unsafe impl<'a, #(#tybounds),*> yoke::Yokeable<'a> for #name<#(#typarams),*> where #(#static_bounds),* {
+                type Output = Self;
+                #[inline]
+                fn transform(&self) -> &Self::Output {
+                    self
+                }
+                #[inline]
+                fn transform_owned(self) -> Self::Output {
+                    self
+                }
+                #[inline]
+                unsafe fn make(this: Self::Output) -> Self {
+                    this
+                }
+                #[inline]
+                fn transform_mut<F>(&'a mut self, f: F)
+                where
+                    F: 'static + for<'b> FnOnce(&'b mut Self::Output) {
+                    f(self)
+                }
+            }
+        }
+    } else {
+        if lts != 1 {
+            return syn::Error::new(
+                input.generics.span(),
+                "derive(Yokeable) cannot have multiple lifetime parameters",
+            )
+            .to_compile_error();
+        }
+        let name = &input.ident;
+        let manual_covariance = input.attrs.iter().any(|a| {
+            if let Ok(i) = a.parse_args::<Ident>() {
+                if i == "prove_covariance_manually" {
+                    return true;
+                }
+            }
+            false
+        });
+        if manual_covariance {
+            let mut structure = Structure::new(input);
+            let generics_env = typarams.iter().cloned().collect();
+            let static_bounds: Vec<WherePredicate> = typarams
+                .iter()
+                .map(|ty| parse_quote!(#ty: 'static))
+                .collect();
+            let mut yoke_bounds: Vec<WherePredicate> = vec![];
+            structure.bind_with(|_| synstructure::BindStyle::Move);
+            let owned_body = structure.each_variant(|vi| {
+                vi.construct(|f, i| {
+                    let binding = format!("__binding_{i}");
+                    let field = Ident::new(&binding, Span::call_site());
+                    let fty_static = replace_lifetime(&f.ty, static_lt());
+
+                    let (has_ty, has_lt) = visitor::check_type_for_parameters(&f.ty, &generics_env);
+                    if has_ty {
+                        // For types without type parameters, the compiler can figure out that the field implements
+                        // Yokeable on its own. However, if there are type parameters, there may be complex preconditions
+                        // to `FieldTy: Yokeable` that need to be satisfied. We get them to be satisfied by requiring
+                        // `FieldTy<'static>: Yokeable<FieldTy<'a>>`
+                        if has_lt {
+                            let fty_a = replace_lifetime(&f.ty, custom_lt("'a"));
+                            yoke_bounds.push(
+                                parse_quote!(#fty_static: yoke::Yokeable<'a, Output = #fty_a>),
+                            );
+                        } else {
+                            yoke_bounds.push(
+                                parse_quote!(#fty_static: yoke::Yokeable<'a, Output = #fty_static>),
+                            );
+                        }
+                    }
+                    if has_ty || has_lt {
+                        // By calling transform_owned on all fields, we manually prove
+                        // that the lifetimes are covariant, since this requirement
+                        // must already be true for the type that implements transform_owned().
+                        quote! {
+                            <#fty_static as yoke::Yokeable<'a>>::transform_owned(#field)
+                        }
+                    } else {
+                        // No nested lifetimes, so nothing to be done
+                        quote! { #field }
+                    }
+                })
+            });
+            let borrowed_body = structure.each(|binding| {
+                let f = binding.ast();
+                let field = &binding.binding;
+
+                let (has_ty, has_lt) = visitor::check_type_for_parameters(&f.ty, &generics_env);
+
+                if has_ty || has_lt {
+                    let fty_static = replace_lifetime(&f.ty, static_lt());
+                    let fty_a = replace_lifetime(&f.ty, custom_lt("'a"));
+                    // We also must assert that each individual field can `transform()` correctly
+                    //
+                    // Even though transform_owned() does such an assertion already, CoerceUnsized
+                    // can cause type transformations that allow it to succeed where this would fail.
+                    // We need to check both.
+                    //
+                    // https://github.com/unicode-org/icu4x/issues/2928
+                    quote! {
+                        let _: &#fty_a = &<#fty_static as yoke::Yokeable<'a>>::transform(#field);
+                    }
+                } else {
+                    // No nested lifetimes, so nothing to be done
+                    quote! {}
+                }
+            });
+            return quote! {
+                unsafe impl<'a, #(#tybounds),*> yoke::Yokeable<'a> for #name<'static, #(#typarams),*>
+                    where #(#static_bounds,)*
+                    #(#yoke_bounds,)* {
+                    type Output = #name<'a, #(#typarams),*>;
+                    #[inline]
+                    fn transform(&'a self) -> &'a Self::Output {
+                        // These are just type asserts, we don't need them for anything
+                        if false {
+                            match self {
+                                #borrowed_body
+                            }
+                        }
+                        unsafe {
+                            // safety: we have asserted covariance in
+                            // transform_owned
+                            ::core::mem::transmute(self)
+                        }
+                    }
+                    #[inline]
+                    fn transform_owned(self) -> Self::Output {
+                        match self { #owned_body }
+                    }
+                    #[inline]
+                    unsafe fn make(this: Self::Output) -> Self {
+                        use core::{mem, ptr};
+                        // unfortunately Rust doesn't think `mem::transmute` is possible since it's not sure the sizes
+                        // are the same
+                        debug_assert!(mem::size_of::<Self::Output>() == mem::size_of::<Self>());
+                        let ptr: *const Self = (&this as *const Self::Output).cast();
+                        #[allow(forgetting_copy_types, clippy::forget_copy, clippy::forget_non_drop)] // This is a noop if the struct is copy, which Clippy doesn't like
+                        mem::forget(this);
+                        ptr::read(ptr)
+                    }
+                    #[inline]
+                    fn transform_mut<F>(&'a mut self, f: F)
+                    where
+                        F: 'static + for<'b> FnOnce(&'b mut Self::Output) {
+                        unsafe { f(core::mem::transmute::<&'a mut Self, &'a mut Self::Output>(self)) }
+                    }
+                }
+            };
+        }
+        quote! {
+            // This is safe because as long as `transform()` compiles,
+            // we can be sure that `'a` is a covariant lifetime on `Self`
+            //
+            // This will not work for structs involving ZeroMap since
+            // the compiler does not know that ZeroMap is covariant.
+            //
+            // This custom derive can be improved to handle this case when
+            // necessary
+            unsafe impl<'a, #(#tybounds),*> yoke::Yokeable<'a> for #name<'static, #(#typarams),*> where #(#static_bounds),* {
+                type Output = #name<'a, #(#typarams),*>;
+                #[inline]
+                fn transform(&'a self) -> &'a Self::Output {
+                    self
+                }
+                #[inline]
+                fn transform_owned(self) -> Self::Output {
+                    self
+                }
+                #[inline]
+                unsafe fn make(this: Self::Output) -> Self {
+                    use core::{mem, ptr};
+                    // unfortunately Rust doesn't think `mem::transmute` is possible since it's not sure the sizes
+                    // are the same
+                    debug_assert!(mem::size_of::<Self::Output>() == mem::size_of::<Self>());
+                    let ptr: *const Self = (&this as *const Self::Output).cast();
+                    #[allow(forgetting_copy_types, clippy::forget_copy, clippy::forget_non_drop)] // This is a noop if the struct is copy, which Clippy doesn't like
+                    mem::forget(this);
+                    ptr::read(ptr)
+                }
+                #[inline]
+                fn transform_mut<F>(&'a mut self, f: F)
+                where
+                    F: 'static + for<'b> FnOnce(&'b mut Self::Output) {
+                    unsafe { f(core::mem::transmute::<&'a mut Self, &'a mut Self::Output>(self)) }
+                }
+            }
+        }
+    }
+}
+
+fn static_lt() -> Lifetime {
+    Lifetime::new("'static", Span::call_site())
+}
+
+fn custom_lt(s: &str) -> Lifetime {
+    Lifetime::new(s, Span::call_site())
+}
+
+fn replace_lifetime(x: &Type, lt: Lifetime) -> Type {
+    use syn::fold::Fold;
+    struct ReplaceLifetime(Lifetime);
+
+    impl Fold for ReplaceLifetime {
+        fn fold_lifetime(&mut self, _: Lifetime) -> Lifetime {
+            self.0.clone()
+        }
+    }
+    ReplaceLifetime(lt).fold_type(x.clone())
+}
diff --git a/third_party/rust/yoke-derive/src/visitor.rs b/third_party/rust/yoke-derive/src/visitor.rs
new file mode 100644
index 0000000000..daca1da13f
--- /dev/null
+++ b/third_party/rust/yoke-derive/src/visitor.rs
@@ -0,0 +1,113 @@
+// This file is part of ICU4X. For terms of use, please see the file
+// called LICENSE at the top level of the ICU4X source tree
+// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
+
+//! Visitor for determining whether a type has type and non-static lifetime parameters
+
+use std::collections::HashSet;
+use syn::visit::{visit_lifetime, visit_type, visit_type_path, Visit};
+use syn::{Ident, Lifetime, Type, TypePath};
+
+struct TypeVisitor<'a> {
+    /// The type parameters in scope
+    typarams: &'a HashSet<Ident>,
+    /// Whether we found a type parameter
+    found_typarams: bool,
+    /// Whether we found a non-'static lifetime parameter
+    found_lifetimes: bool,
+}
+
+impl<'a, 'ast> Visit<'ast> for TypeVisitor<'a> {
+    fn visit_lifetime(&mut self, lt: &'ast Lifetime) {
+        if lt.ident != "static" {
+            self.found_lifetimes = true;
+        }
+        visit_lifetime(self, lt)
+    }
+    fn visit_type_path(&mut self, ty: &'ast TypePath) {
+        // We only need to check ty.path.get_ident() and not ty.qself or any
+        // generics in ty.path because the visitor will eventually visit those
+        // types on its own
+        if let Some(ident) = ty.path.get_ident() {
+            if self.typarams.contains(ident) {
+                self.found_typarams = true;
+            }
+        }
+
+        visit_type_path(self, ty)
+    }
+}
+
+/// Checks if a type has type or lifetime parameters, given the local context of
+/// named type parameters. Returns (has_type_params, has_lifetime_params)
+pub fn check_type_for_parameters(ty: &Type, typarams: &HashSet<Ident>) -> (bool, bool) {
+    let mut visit = TypeVisitor {
+        typarams,
+        found_typarams: false,
+        found_lifetimes: false,
+    };
+    visit_type(&mut visit, ty);
+
+    (visit.found_typarams, visit.found_lifetimes)
+}
+
+#[cfg(test)]
+mod tests {
+    use proc_macro2::Span;
+    use std::collections::HashSet;
+    use syn::{parse_quote, Ident};
+
+    use super::check_type_for_parameters;
+    fn make_typarams(params: &[&str]) -> HashSet<Ident> {
+        params
+            .iter()
+            .map(|x| Ident::new(x, Span::call_site()))
+            .collect()
+    }
+
+    #[test]
+    fn test_simple_type() {
+        let environment = make_typarams(&["T", "U", "V"]);
+
+        let ty = parse_quote!(Foo<'a, T>);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (true, true));
+
+        let ty = parse_quote!(Foo<T>);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (true, false));
+
+        let ty = parse_quote!(Foo<'static, T>);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (true, false));
+
+        let ty = parse_quote!(Foo<'a>);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (false, true));
+
+        let ty = parse_quote!(Foo<'a, Bar<U>, Baz<(V, u8)>>);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (true, true));
+
+        let ty = parse_quote!(Foo<'a, W>);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (false, true));
+    }
+
+    #[test]
+    fn test_assoc_types() {
+        let environment = make_typarams(&["T"]);
+
+        let ty = parse_quote!(<Foo as SomeTrait<'a, T>>::Output);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (true, true));
+
+        let ty = parse_quote!(<Foo as SomeTrait<'static, T>>::Output);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (true, false));
+
+        let ty = parse_quote!(<T as SomeTrait<'static, Foo>>::Output);
+        let check = check_type_for_parameters(&ty, &environment);
+        assert_eq!(check, (true, false));
+    }
+}