Create starlark providers crate

Bug: 528225104
Change-Id: I6691d035e7f5b43b48a32debb3f4e8c76a6a6964
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/24020
Reviewed-by: Matt Stark <msta@google.com>
Reviewed-by: Cole Faust <colefaust@google.com>
diff --git a/src/gn/starlark/Cargo.lock b/src/gn/starlark/Cargo.lock
index da068a6..fe40557 100644
--- a/src/gn/starlark/Cargo.lock
+++ b/src/gn/starlark/Cargo.lock
@@ -24,7 +24,7 @@
 [[package]]
 name = "allocative"
 version = "0.3.6"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "allocative_derive",
  "bumpalo",
@@ -36,7 +36,7 @@
 [[package]]
 name = "allocative_derive"
 version = "0.3.6"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -290,7 +290,7 @@
 [[package]]
 name = "cmp_any"
 version = "0.8.1"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#1dc81928e2b9766919416ef5fb21857452153ec0"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 
 [[package]]
 name = "cobs"
@@ -534,7 +534,7 @@
 [[package]]
 name = "display_container"
 version = "0.9.0"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#1dc81928e2b9766919416ef5fb21857452153ec0"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "either",
  "indenter",
@@ -543,7 +543,7 @@
 [[package]]
 name = "dupe"
 version = "0.9.1"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#1dc81928e2b9766919416ef5fb21857452153ec0"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "dupe_derive",
 ]
@@ -551,7 +551,7 @@
 [[package]]
 name = "dupe_derive"
 version = "0.9.1"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#1dc81928e2b9766919416ef5fb21857452153ec0"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -635,7 +635,7 @@
 checksum = "39cab71617ae0d63f51a36d69f866391735b51691dbda63cf6f96d042b63efeb"
 dependencies = [
  "libc",
- "windows-sys 0.52.0",
+ "windows-sys 0.61.2",
 ]
 
 [[package]]
@@ -1040,7 +1040,7 @@
 [[package]]
 name = "pagable"
 version = "0.4.1"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "allocative",
  "anyhow",
@@ -1075,7 +1075,7 @@
 [[package]]
 name = "pagable_derive"
 version = "0.4.1"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -1135,6 +1135,19 @@
 ]
 
 [[package]]
+name = "providers"
+version = "0.1.0"
+dependencies = [
+ "allocative",
+ "either",
+ "starlark",
+ "starlark_derive",
+ "testutils",
+ "thiserror",
+ "types",
+]
+
+[[package]]
 name = "quickcheck"
 version = "1.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1273,7 +1286,7 @@
  "errno",
  "libc",
  "linux-raw-sys",
- "windows-sys 0.52.0",
+ "windows-sys 0.61.2",
 ]
 
 [[package]]
@@ -1464,7 +1477,7 @@
 [[package]]
 name = "starlark"
 version = "0.14.2"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "allocative",
  "anyhow",
@@ -1508,7 +1521,7 @@
 [[package]]
 name = "starlark_derive"
 version = "0.14.2"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "dupe",
  "proc-macro2",
@@ -1519,7 +1532,7 @@
 [[package]]
 name = "starlark_map"
 version = "0.14.2"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "allocative",
  "dupe",
@@ -1534,7 +1547,7 @@
 [[package]]
 name = "starlark_syntax"
 version = "0.14.2"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#c599dd000d7f754cfa68af4bca4a4e2a622c2e1b"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "allocative",
  "annotate-snippets",
@@ -1572,7 +1585,7 @@
 [[package]]
 name = "strong_hash"
 version = "0.1.0"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#1dc81928e2b9766919416ef5fb21857452153ec0"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "ref-cast",
  "strong_hash_derive",
@@ -1581,7 +1594,7 @@
 [[package]]
 name = "strong_hash_derive"
 version = "0.1.0"
-source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#1dc81928e2b9766919416ef5fb21857452153ec0"
+source = "git+https://github.com/matts1/starlark-rust.git?branch=gn_starlark#4fdfa21b978a8fb1fd910b07f1d2b2be0ea89d7e"
 dependencies = [
  "quote",
  "syn 2.0.118",
@@ -1751,7 +1764,7 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "c2a7b1c03c876122aa43f3020e6c3c3ee5c05081c9a00739faf7503aeba10d22"
 dependencies = [
- "windows-sys 0.52.0",
+ "windows-sys 0.61.2",
 ]
 
 [[package]]
diff --git a/src/gn/starlark/Cargo.toml b/src/gn/starlark/Cargo.toml
index ac485ff..5d03132 100644
--- a/src/gn/starlark/Cargo.toml
+++ b/src/gn/starlark/Cargo.toml
@@ -18,6 +18,7 @@
     "crates/depset",
     "crates/ffi",
     "crates/loader",
+    "crates/providers",
     "crates/testutils",
     "crates/types",
 ]
diff --git a/src/gn/starlark/crates/providers/Cargo.toml b/src/gn/starlark/crates/providers/Cargo.toml
new file mode 100644
index 0000000..ff8eaf4
--- /dev/null
+++ b/src/gn/starlark/crates/providers/Cargo.toml
@@ -0,0 +1,21 @@
+[package]
+name = "providers"
+version = "0.1.0"
+edition = "2021"
+
+[lints]
+workspace = true
+
+[lib]
+doctest = false
+
+[dependencies]
+allocative = { workspace = true }
+either = { workspace = true }
+starlark = { workspace = true }
+starlark_derive = { workspace = true }
+thiserror = { workspace = true }
+types = { path = "../types" }
+
+[dev-dependencies]
+testutils = { path = "../testutils" }
diff --git a/src/gn/starlark/crates/providers/src/errors.rs b/src/gn/starlark/crates/providers/src/errors.rs
new file mode 100644
index 0000000..4f5cf04
--- /dev/null
+++ b/src/gn/starlark/crates/providers/src/errors.rs
@@ -0,0 +1,26 @@
+// Copyright 2026 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+/// Errors returned by provider validation, unpacking, and extraction.
+#[derive(thiserror::Error, Debug)]
+pub(crate) enum Error {
+    #[error("The elements of provider fields must be strings")]
+    FieldsMustBeStrings,
+    #[error("Provider fields must be an iterable")]
+    FieldsMustBeIterable,
+    #[error("Provider name must end with 'Info' (got '{0}')")]
+    InvalidProviderName(String),
+    #[error("Duplicate field name: {0}")]
+    DuplicateFieldName(String),
+    #[error("The result of provider() must be assigned to a variable")]
+    ProviderNotExported,
+    #[error("Cannot construct values of non-frozen provider type")]
+    ProviderNotFrozen,
+}
+
+impl From<Error> for starlark::Error {
+    fn from(err: Error) -> Self {
+        Self::new_other(err)
+    }
+}
diff --git a/src/gn/starlark/crates/providers/src/globals.rs b/src/gn/starlark/crates/providers/src/globals.rs
new file mode 100644
index 0000000..d503789
--- /dev/null
+++ b/src/gn/starlark/crates/providers/src/globals.rs
@@ -0,0 +1,32 @@
+use starlark::{environment::GlobalsBuilder, eval::Evaluator, values::Value};
+use starlark_derive::starlark_module;
+
+use crate::Error;
+
+/// Registers the global `provider()` function.
+#[starlark_module]
+pub(crate) fn register_providers_globals(builder: &mut GlobalsBuilder) {
+    fn provider<'v>(
+        #[starlark(require = named)] fields: Value<'v>,
+        eval: &mut Evaluator<'v, '_, '_>,
+    ) -> starlark::Result<Value<'v>> {
+        let mut field_names = Vec::new();
+        for field in fields
+            .iterate(eval.heap())
+            .map_err(|_| Error::FieldsMustBeIterable)?
+        {
+            let s = field
+                .unpack_str()
+                .ok_or(Error::FieldsMustBeStrings)?
+                .to_owned();
+            field_names.push(s);
+        }
+
+        let provider_type = crate::provider_type::ProviderType::new(field_names)?;
+        Ok(eval.heap().alloc_complex(provider_type))
+    }
+}
+
+pub fn register_providers(builder: &mut GlobalsBuilder) {
+    register_providers_globals(builder);
+}
diff --git a/src/gn/starlark/crates/providers/src/lib.rs b/src/gn/starlark/crates/providers/src/lib.rs
new file mode 100644
index 0000000..ab02770
--- /dev/null
+++ b/src/gn/starlark/crates/providers/src/lib.rs
@@ -0,0 +1,13 @@
+// Copyright 2026 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+pub(crate) mod errors;
+pub mod globals;
+pub mod provider_instance;
+pub mod provider_type;
+
+pub(crate) use errors::Error;
+pub use globals::register_providers;
+pub use provider_instance::{FrozenProviderInstance, ProviderInstance};
+pub use provider_type::ProviderType;
diff --git a/src/gn/starlark/crates/providers/src/provider_instance.rs b/src/gn/starlark/crates/providers/src/provider_instance.rs
new file mode 100644
index 0000000..54e8284
--- /dev/null
+++ b/src/gn/starlark/crates/providers/src/provider_instance.rs
@@ -0,0 +1,291 @@
+// Copyright 2026 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+use std::{fmt, fmt::Display, hash::Hasher as _};
+
+use allocative::Allocative;
+use starlark::{
+    any::ProvidesStaticType,
+    coerce::Coerce,
+    collections::{Hashed, StarlarkHasher},
+    starlark_complex_value,
+    values::{
+        Freeze, FrozenValueTyped, Heap, StarlarkValue, Trace, Value, ValueLifetimeless, ValueLike,
+    },
+};
+use starlark_derive::{starlark_value, NoSerialize};
+
+use crate::provider_type::FrozenProviderType;
+
+/// Represents an instance of a provider.
+#[derive(Clone, Trace, Coerce, Freeze, ProvidesStaticType, Allocative, NoSerialize)]
+#[repr(C)]
+pub struct ProviderInstanceGen<V: ValueLifetimeless> {
+    pub(crate) provider_type: FrozenValueTyped<'static, FrozenProviderType>,
+    pub(crate) values: Box<[Option<V>]>,
+}
+
+starlark_complex_value!(pub ProviderInstance);
+
+impl<'v, V: ValueLike<'v>> ProviderInstanceGen<V>
+where
+    Self: ProvidesStaticType<'v>,
+{
+    pub(crate) fn ty(&self) -> &'v FrozenProviderType {
+        self.provider_type.as_ref()
+    }
+
+    pub(crate) fn ty_name(&self) -> &'static str {
+        self.get_type_value_dyn().as_str()
+    }
+
+    pub fn iter<'a>(&'a self) -> impl Iterator<Item = (&'v str, V)> + 'a
+    where
+        'v: 'a,
+    {
+        let fields = &self.ty().fields;
+        fields
+            .iter()
+            .filter_map(move |(name, &idx)| self.values[idx].map(|val| (name.as_str(), val)))
+    }
+
+    // A common API for both the Debug trait and starlark's repr.
+    fn collect_repr_impl(&self, collector: &mut String) {
+        use std::fmt::Write as _;
+        write!(collector, "{}(", self.ty_name()).unwrap();
+        for (i, (name, val)) in self.iter().enumerate() {
+            if i > 0 {
+                write!(collector, ", ").unwrap();
+            }
+            write!(collector, "{name} = ").unwrap();
+            val.to_value().collect_repr(collector);
+        }
+        write!(collector, ")").unwrap();
+    }
+}
+
+impl<'v, V: ValueLike<'v>> fmt::Debug for ProviderInstanceGen<V>
+where
+    Self: ProvidesStaticType<'v>,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut s = String::new();
+        self.collect_repr_impl(&mut s);
+        write!(f, "{s}")
+    }
+}
+
+impl<'v, V: ValueLike<'v>> Display for ProviderInstanceGen<V>
+where
+    Self: ProvidesStaticType<'v>,
+{
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{self:?}")
+    }
+}
+
+#[starlark_value(type = "provider")]
+impl<'v, V: ValueLike<'v>> StarlarkValue<'v> for ProviderInstanceGen<V>
+where
+    Self: ProvidesStaticType<'v>,
+{
+    type Canonical = FrozenProviderInstance;
+
+    fn get_type_value_dyn(&self) -> starlark::values::FrozenStringValue {
+        // Safety: ProviderInstance is only constructed when the provider is exported.
+        unsafe { self.ty().data.as_ref().unwrap_unchecked().name }
+    }
+
+    fn equals(&self, other: Value<'v>) -> starlark::Result<bool> {
+        let Some(other) = ProviderInstance::from_value(other) else {
+            return Ok(false);
+        };
+        if self.ty().id != other.ty().id {
+            return Ok(false);
+        }
+        for (v1, v2) in self.values.iter().zip(other.values.iter()) {
+            match (v1, v2) {
+                (Some(val1), Some(val2)) => {
+                    if !val1.to_value().equals(val2.to_value())? {
+                        return Ok(false);
+                    }
+                },
+                (None, None) => {},
+                _ => return Ok(false),
+            }
+        }
+        Ok(true)
+    }
+
+    fn collect_repr(&self, collector: &mut String) {
+        self.collect_repr_impl(collector);
+    }
+
+    fn collect_repr_cycle(&self, collector: &mut String) {
+        use std::fmt::Write as _;
+        write!(collector, "{}(...)", self.ty_name()).unwrap();
+    }
+
+    fn get_attr(&self, attribute: &str, heap: Heap<'v>) -> Option<Value<'v>> {
+        self.get_attr_hashed(Hashed::new(attribute), heap)
+    }
+
+    fn get_attr_hashed(&self, attribute: Hashed<&str>, _heap: Heap<'v>) -> Option<Value<'v>> {
+        let &i = self.ty().fields.get_hashed(attribute)?;
+        self.values[i].map(|v| v.to_value())
+    }
+
+    fn write_hash(&self, hasher: &mut StarlarkHasher) -> starlark::Result<()> {
+        self.provider_type.write_hash(hasher)?;
+        for v in &self.values {
+            if let Some(val) = *v {
+                val.write_hash(hasher)?;
+            } else {
+                hasher.write_u8(0);
+            }
+        }
+        Ok(())
+    }
+
+    fn dir_attr(&self) -> Vec<String> {
+        let fields = &self.ty().fields;
+        fields
+            .iter()
+            .filter_map(|(name, &idx)| {
+                if self.values[idx].is_some() {
+                    Some(name.clone())
+                } else {
+                    None
+                }
+            })
+            .collect()
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use starlark::values::UnpackValue as _;
+
+    use crate::{register_providers, ProviderInstance};
+
+    fn new_assert() -> testutils::Assert {
+        let mut a = testutils::Assert::default();
+        a.modify_globals(|builder| {
+            register_providers(builder);
+        });
+        a
+    }
+
+    #[test]
+    fn test_unpack_fails() {
+        let mut a = new_assert();
+        let val = a.pass("1");
+        let err = <&ProviderInstance>::unpack_value_err(val.value()).unwrap_err();
+        assert_eq!(
+            err.to_string(),
+            "Expected `provider`, but got `int (repr: 1)`"
+        );
+    }
+
+    #[test]
+    fn test_provider_instance() {
+        let mut a = new_assert();
+
+        let ty = a.pass("MyInfo = provider(fields = ['first', 'second', 'third']); MyInfo");
+        a.modify_globals(move |builder| {
+            builder.set("MyInfo", ty.clone());
+        });
+
+        let instance = a.pass("MyInfo(first = 'hello', third = 3)");
+        let unpacked = <&ProviderInstance>::unpack_value_err(instance.value()).unwrap();
+        assert_eq!(unpacked.ty_name(), "MyInfo");
+
+        a.modify_globals(move |builder| {
+            builder.set("info", instance.clone());
+        });
+
+        a.eq("type(info)", "MyInfo".to_string());
+
+        a.eq(
+            "str(info)",
+            "MyInfo(first = \"hello\", third = 3)".to_string(),
+        );
+        a.eq(
+            "repr(info)",
+            "MyInfo(first = \"hello\", third = 3)".to_string(),
+        );
+
+        a.eq(
+            "dir(info)",
+            starlark::values::list::UnpackList {
+                items: vec!["first".to_string(), "third".to_string()],
+            },
+        );
+
+        // 'first' field: declared and set
+        a.eq(r#"hasattr(info, "first")"#, true);
+        a.eq(r#"info.first"#, "hello".to_string());
+
+        // 'second' field: declared but unset
+        a.eq(r#"hasattr(info, "second")"#, false);
+        a.fail(
+            "info.second",
+            "Object of type `MyInfo` has no attribute `second`",
+        );
+
+        // 'nonexistent' field: undeclared and unset
+        a.eq(r#"hasattr(info, "nonexistent")"#, false);
+        a.fail(
+            "info.nonexistent",
+            "Object of type `MyInfo` has no attribute `nonexistent`",
+        );
+
+        a.eq(
+            r#"
+info2 = MyInfo(first = [])
+info2.first.append(info2)
+str(info2)
+"#,
+            "MyInfo(first = [MyInfo(...)])".to_string(),
+        );
+    }
+
+    #[test]
+    fn test_provider_instance_equality() {
+        let mut a = new_assert();
+
+        let ty = a.pass("MyInfo = provider(fields = ['first', 'second']); MyInfo");
+        let other_ty = a.pass("OtherInfo = provider(fields = ['first', 'second']); OtherInfo");
+        a.modify_globals(move |builder| {
+            builder.set("MyInfo", ty.clone());
+            builder.set("OtherInfo", other_ty.clone());
+        });
+
+        a.eq(
+            "MyInfo(first = 'hello', second = 2) == MyInfo(first = 'hello', second = 2)",
+            true,
+        );
+        a.eq(
+            "MyInfo(first = 'hello', second = 2) == MyInfo(first = 'hello', second = 3)",
+            false,
+        );
+        a.eq(
+            "MyInfo(first = 'hello', second = 2) == MyInfo(first = 'hello')",
+            false,
+        );
+
+        a.eq(
+            "MyInfo(first = 'hello', second = 2) == OtherInfo(first = 'hello', second = 2)",
+            false,
+        );
+
+        // Test equality between a frozen instance and an unfrozen instance
+        let frozen_info = a.pass("MyInfo(first = 'hello', second = 2)");
+        a.modify_globals(move |builder| {
+            builder.set("frozen_info", frozen_info.clone());
+        });
+        a.eq("frozen_info == MyInfo(first = 'hello', second = 2)", true);
+        a.eq("MyInfo(first = 'hello', second = 2) == frozen_info", true);
+    }
+}
diff --git a/src/gn/starlark/crates/providers/src/provider_type.rs b/src/gn/starlark/crates/providers/src/provider_type.rs
new file mode 100644
index 0000000..24c7569
--- /dev/null
+++ b/src/gn/starlark/crates/providers/src/provider_type.rs
@@ -0,0 +1,248 @@
+// Copyright 2026 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+use std::{
+    cell::OnceCell,
+    fmt,
+    fmt::{Debug, Display},
+};
+
+use allocative::Allocative;
+use starlark::{
+    any::ProvidesStaticType,
+    collections::SmallMap,
+    eval::{Arguments, Evaluator, ParametersSpec, ParametersSpecParam},
+    starlark_simple_value,
+    values::{
+        typing::TypeInstanceId, Freeze, FreezeResult, Freezer, FrozenValue, FrozenValueTyped,
+        StarlarkValue, Trace, Value,
+    },
+};
+use starlark_derive::{starlark_value, NoSerialize};
+
+use crate::{Error, ProviderInstance};
+
+#[derive(Debug, Clone, Trace, Allocative)]
+// Contains all the information we cannot know about a provider type until we
+// actually know the name of it.
+pub(crate) struct ProviderTypeData {
+    pub(crate) name: starlark::values::FrozenStringValue,
+    pub(crate) parameter_spec: ParametersSpec<FrozenValue>,
+}
+
+/// Represents the provider type constructor.
+#[derive(Debug, ProvidesStaticType, NoSerialize, Allocative, Trace)]
+pub struct ProviderType {
+    /// The unique type identifier.
+    pub(crate) id: TypeInstanceId,
+    /// The configured provider fields. This is set when starlark calls
+    /// `export_as` when you assign the provider to a variable.
+    /// If this is not set, you cannot construct the provider.
+    pub(crate) data: OnceCell<ProviderTypeData>,
+    /// A mapping from field name to index.
+    /// This is akin to python's `__slots__`.
+    pub(crate) fields: SmallMap<String, usize>,
+}
+
+/// Represents the frozen provider type constructor.
+#[derive(Debug, ProvidesStaticType, NoSerialize, Allocative, Trace)]
+pub struct FrozenProviderType {
+    /// The unique type identifier.
+    pub(crate) id: TypeInstanceId,
+    /// The configured provider fields.
+    pub(crate) data: Option<ProviderTypeData>,
+    /// A mapping from field name to index.
+    /// This is akin to python's `__slots__`.
+    pub(crate) fields: SmallMap<String, usize>,
+}
+
+starlark_simple_value!(FrozenProviderType);
+
+impl Display for ProviderType {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "<provider>")
+    }
+}
+
+impl Display for FrozenProviderType {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "<provider>")
+    }
+}
+
+#[starlark_value(type = "provider")]
+impl<'v> StarlarkValue<'v> for ProviderType {
+    type Canonical = FrozenProviderType;
+
+    // Being unable to invoke non-frozen provider types makes ProviderInstance code
+    // much simpler. It isn't really a problems since you should be making
+    // providers inside rule implementations. We can choose to add this feature
+    // later if we'd like.
+    fn invoke(
+        &self,
+        _me: Value<'v>,
+        _args: &Arguments<'v, '_>,
+        _eval: &mut Evaluator<'v, '_, '_>,
+    ) -> starlark::Result<Value<'v>> {
+        Err(Error::ProviderNotFrozen.into())
+    }
+
+    fn export_as(&self, name: &str, eval: &mut Evaluator<'v, '_, '_>) -> starlark::Result<()> {
+        if self.data.get().is_some() {
+            return Ok(());
+        }
+
+        if !name.ends_with("Info") {
+            return Err(Error::InvalidProviderName(name.to_owned()).into());
+        }
+
+        self.data.get_or_init(|| ProviderTypeData {
+            name: eval.frozen_heap().alloc_str(name),
+            parameter_spec: ParametersSpec::new_named_only(
+                name,
+                self.fields
+                    .keys()
+                    .map(|f| (f.as_str(), ParametersSpecParam::Optional)),
+            ),
+        });
+        Ok(())
+    }
+}
+
+#[starlark_value(type = "provider")]
+impl<'v> StarlarkValue<'v> for FrozenProviderType {
+    type Canonical = Self;
+
+    fn invoke(
+        &self,
+        me: Value<'v>,
+        args: &Arguments<'v, '_>,
+        eval: &mut Evaluator<'v, '_, '_>,
+    ) -> starlark::Result<Value<'v>> {
+        // Safety: `me` is the receiver of type `FrozenProviderType`, which is
+        // guaranteed to be frozen.
+        let provider_type =
+            unsafe { FrozenValueTyped::new_unchecked(me.unpack_frozen().unwrap_unchecked()) };
+
+        let data = self.data.as_ref().ok_or(Error::ProviderNotExported)?;
+        data.parameter_spec
+            .parser(args, eval, |param_parser, eval| {
+                let values: Box<[Option<Value<'v>>]> = (0..self.fields.len())
+                    .map(|_| param_parser.next_opt::<Value<'v>>())
+                    .collect::<starlark::Result<_>>()?;
+                Ok(eval.heap().alloc_complex(ProviderInstance {
+                    provider_type,
+                    values,
+                }))
+            })
+    }
+}
+
+impl ProviderType {
+    /// Creates a new provider type with the provided fields.
+    /// This provider is not yet configured, and is unusable until `export_as`
+    /// is called.
+    pub fn new(fields: Vec<String>) -> starlark::Result<Self> {
+        let mut field_map = SmallMap::with_capacity(fields.len());
+        for (idx, field) in fields.into_iter().enumerate() {
+            if field_map.insert(field.clone(), idx).is_some() {
+                return Err(Error::DuplicateFieldName(field).into());
+            }
+        }
+        Ok(Self {
+            id: TypeInstanceId::r#gen(),
+            data: OnceCell::new(),
+            fields: field_map,
+        })
+    }
+}
+impl Freeze for ProviderType {
+    type Frozen = FrozenProviderType;
+
+    fn freeze(self, _freezer: &Freezer) -> FreezeResult<Self::Frozen> {
+        Ok(FrozenProviderType {
+            id: self.id,
+            data: self.data.into_inner(),
+            fields: self.fields,
+        })
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::globals::register_providers;
+
+    fn new_assert() -> testutils::Assert {
+        let mut a = testutils::Assert::default();
+        a.modify_globals(|builder| {
+            register_providers(builder);
+        });
+        a
+    }
+
+    #[test]
+    fn test_provider_type() {
+        let mut a = new_assert();
+        a.fail(
+            "provider()",
+            "Missing named-only parameter `fields` for call to `provider`",
+        );
+
+        a.fail(
+            "provider(fields=['a'])(a=1)",
+            "Cannot construct values of non-frozen provider type",
+        );
+
+        a.fail(
+            r#"
+MyInfo = provider(fields=['a'])
+MyInfo(a=1, b=2)
+"#,
+            "Cannot construct values of non-frozen provider type",
+        );
+        a.fail(
+            "provider(fields = 1)",
+            "Provider fields must be an iterable",
+        );
+        a.fail("provider(fields = ['a', 'a'])", "Duplicate field name: a");
+        a.fail(
+            r#"
+p = provider(fields=['a'])
+"#,
+            "Provider name must end with 'Info' (got 'p')",
+        );
+    }
+
+    #[test]
+    fn test_provider_aliasing() {
+        let mut a = new_assert();
+
+        let p_info = a.pass("MyInfo = provider(fields = ['a']); foo = MyInfo; foo");
+        a.modify_globals(move |builder| {
+            builder.set("foo", p_info.clone());
+        });
+
+        let alias = a.pass("alias = foo; alias");
+        a.modify_globals(move |builder| {
+            builder.set("alias", alias.clone());
+        });
+
+        // The constructor should retain its canonical name "MyInfo"
+        a.eq("str(alias(a = 1))", "MyInfo(a = 1)".to_string());
+    }
+
+    #[test]
+    fn test_unexported_provider_fails_to_call() {
+        let mut a = new_assert();
+        let unexported = a.pass("x = [provider(fields=['a'])]; x");
+        a.modify_globals(move |builder| {
+            builder.set("x", unexported.clone());
+        });
+
+        a.fail(
+            "MyInfo = x[0]; MyInfo()",
+            "The result of provider() must be assigned to a variable",
+        );
+    }
+}