diff --git a/src/gn/starlark/Cargo.lock b/src/gn/starlark/Cargo.lock
index de40a89..0ecb308 100644
--- a/src/gn/starlark/Cargo.lock
+++ b/src/gn/starlark/Cargo.lock
@@ -462,6 +462,18 @@
 ]
 
 [[package]]
+name = "depset"
+version = "0.1.0"
+dependencies = [
+ "allocative",
+ "starlark",
+ "starlark_derive",
+ "testutils",
+ "thiserror",
+ "types",
+]
+
+[[package]]
 name = "derivative"
 version = "2.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/src/gn/starlark/Cargo.toml b/src/gn/starlark/Cargo.toml
index 4645b08..18aa81e 100644
--- a/src/gn/starlark/Cargo.toml
+++ b/src/gn/starlark/Cargo.toml
@@ -14,6 +14,7 @@
 members = [
     ".",
     "crates/attr",
+    "crates/depset",
     "crates/ffi",
     "crates/loader",
     "crates/testutils",
diff --git a/src/gn/starlark/crates/depset/Cargo.toml b/src/gn/starlark/crates/depset/Cargo.toml
new file mode 100644
index 0000000..63e6c0d
--- /dev/null
+++ b/src/gn/starlark/crates/depset/Cargo.toml
@@ -0,0 +1,19 @@
+[package]
+name = "depset"
+version = "0.1.0"
+edition = "2021"
+
+[lints]
+workspace = true
+
+[lib]
+
+[dependencies]
+types = { path = "../types" }
+starlark = { workspace = true }
+starlark_derive = { workspace = true }
+thiserror = { workspace = true }
+allocative = { workspace = true }
+
+[dev-dependencies]
+testutils = { path = "../testutils" }
diff --git a/src/gn/starlark/crates/depset/src/depset.rs b/src/gn/starlark/crates/depset/src/depset.rs
new file mode 100644
index 0000000..c1a5fe2
--- /dev/null
+++ b/src/gn/starlark/crates/depset/src/depset.rs
@@ -0,0 +1,425 @@
+// 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, Formatter},
+};
+
+use allocative::Allocative;
+use starlark::{
+    environment::{Methods, MethodsBuilder, MethodsStatic},
+    starlark_complex_value,
+    typing::Ty,
+    values::{
+        type_repr::StarlarkTypeRepr, Freeze, FreezeResult, Freezer, Heap, ProvidesStaticType,
+        StarlarkValue, Trace, UnpackValue, Value, ValueLike,
+    },
+};
+use starlark_derive::{starlark_module, starlark_value, Coerce, NoSerialize};
+use types::File;
+
+#[derive(Debug, Clone, Copy, Eq, PartialEq, Hash, Allocative)]
+/// All orderings are guaranteed to be deterministic.
+pub enum Order {
+    /// Our unspecified order is postorder. However, this should not be relied
+    /// upon.
+    /// This is named "default" in bazel, but we call it Unspecified to clarify
+    /// exactly how it should work from the depset implementation side of
+    /// things.
+    Unspecified,
+    /// Guaranteed to traverse through direct dependencies in left-to-right
+    /// order, then transitive in left-to-right order.
+    Preorder,
+    /// Guaranteed to traverse through transitive dependencies in left-to-right
+    /// order, then direct in left-to-right order.
+    Postorder,
+    /// Our topological order is reverse postorder. However, this should not be
+    /// relied upon. Note: Topological order is much slower and less memory
+    /// efficient as it requires an intermediate Vec to be created and then
+    /// reversed.
+    Topological,
+}
+
+impl StarlarkTypeRepr for Order {
+    type Canonical = String;
+
+    fn starlark_type_repr() -> Ty {
+        String::starlark_type_repr()
+    }
+}
+
+impl<'v> UnpackValue<'v> for Order {
+    type Error = starlark::Error;
+
+    fn unpack_value_impl(value: Value<'v>) -> Result<Option<Self>, Self::Error> {
+        match <&'v str>::unpack_value_err(value)? {
+            "default" => Ok(Some(Self::Unspecified)),
+            "preorder" => Ok(Some(Self::Preorder)),
+            "postorder" => Ok(Some(Self::Postorder)),
+            "topological" => Ok(Some(Self::Topological)),
+            s => Err(crate::Error::InvalidOrder(s.to_owned()).into()),
+        }
+    }
+}
+
+impl Display for Order {
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        match self {
+            // For consistency with bazel, the user sees unspecified as "default".
+            Self::Unspecified => write!(f, "default"),
+            Self::Preorder => write!(f, "preorder"),
+            Self::Postorder => write!(f, "postorder"),
+            Self::Topological => write!(f, "topological"),
+        }
+    }
+}
+
+/// The type of elements contained in a depset.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, allocative::Allocative)]
+pub enum Kind {
+    Empty,
+    Unknown,
+    File,
+}
+
+impl Display for Kind {
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        match self {
+            Self::Empty => write!(f, "empty"),
+            Self::Unknown => write!(f, "unknown"),
+            Self::File => write!(f, "File"),
+        }
+    }
+}
+
+/// A generic implementation of a Starlark Depset.
+#[derive(Debug, Trace, Coerce, ProvidesStaticType, NoSerialize, Allocative)]
+// By implementing coerce, freezing depsets is zero-cost.
+// Coerce requires repr(C).
+// Starlark knows that it can just do a reinterpret cast of the memory.
+#[repr(C)]
+pub struct DepsetGen<V> {
+    /// The traversal order of this depset.
+    pub(crate) order: Order,
+    /// The direct elements of this depset. De-duped on creation.
+    pub(crate) direct: Vec<V>,
+    /// Transitive depsets. Each entry is guaranteed to be a non-empty depset.
+    pub(crate) transitive: Vec<V>,
+    /// The element type kind of this depset.
+    pub(crate) kind: Kind,
+    /// The single phony file for this depset. Set for `depset[File]` only.
+    /// If the depset only has a single element, it will just be that element.
+    pub(crate) phony: Option<File>,
+}
+
+impl<'v> Depset<'v> {
+    /// Creates a new `Depset` containing `File` elements.
+    pub fn new_file_depset<C: types::EvalContext>(
+        direct: Vec<File>,
+        heap: &Heap<'v>,
+        ctx: &mut C,
+    ) -> starlark::Result<Self> {
+        let phony = if direct.len() == 1 {
+            Some(direct[0].clone())
+        } else if !direct.is_empty() {
+            Some(ctx.require_rule_impl_mut()?.new_phony(direct.clone()))
+        } else {
+            None
+        };
+        Ok(Self {
+            order: Order::Unspecified,
+            transitive: Vec::new(),
+            kind: if direct.is_empty() {
+                Kind::Empty
+            } else {
+                Kind::File
+            },
+            direct: direct.into_iter().map(|f| heap.alloc(f)).collect(),
+            phony,
+        })
+    }
+}
+
+impl<V> Default for DepsetGen<V> {
+    fn default() -> Self {
+        Self {
+            order: Order::Unspecified,
+            direct: Vec::new(),
+            transitive: Vec::new(),
+            kind: Kind::Empty,
+            phony: None,
+        }
+    }
+}
+
+impl<V> DepsetGen<V> {
+    pub(crate) fn order(&self) -> Order {
+        self.order
+    }
+
+    pub(crate) fn direct(&self) -> &[V] {
+        &self.direct
+    }
+
+    pub(crate) fn transitive(&self) -> &[V] {
+        &self.transitive
+    }
+
+    /// Returns the element kind of this depset.
+    pub fn kind(&self) -> &Kind {
+        &self.kind
+    }
+
+    /// Returns the single phony File if this is a file depset containing
+    /// exactly one element.
+    pub fn phony(&self) -> &Option<File> {
+        &self.phony
+    }
+
+    /// Returns true if this depset has no elements (its kind is Empty).
+    pub fn is_empty(&self) -> bool {
+        self.kind == Kind::Empty
+    }
+}
+
+starlark_complex_value!(pub Depset);
+
+impl<'v, V: ValueLike<'v>> Display for DepsetGen<V>
+where
+    Self: ProvidesStaticType<'v>,
+{
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        // Explicitly DO NOT flatten a depset implicitly, they can get massive.
+        // We may consider printing some fields in the future, but for now
+        // we'll leave this empty to be safe.
+        if self.is_empty() {
+            write!(f, "depset([])")
+        } else {
+            write!(f, "depset(...)")
+        }
+    }
+}
+
+#[starlark_value(type = "depset")]
+impl<'v, V: ValueLike<'v>> StarlarkValue<'v> for DepsetGen<V>
+where
+    Self: ProvidesStaticType<'v>,
+{
+    fn get_methods() -> Option<&'static Methods> {
+        static RES: MethodsStatic = MethodsStatic::new("depset", depset_methods);
+        Some(RES.methods())
+    }
+
+    fn to_bool(&self) -> bool {
+        !self.is_empty()
+    }
+}
+
+impl Freeze for Depset<'_> {
+    type Frozen = FrozenDepset;
+
+    fn freeze(self, freezer: &Freezer) -> FreezeResult<Self::Frozen> {
+        Ok(DepsetGen {
+            order: self.order,
+            direct: self.direct.freeze(freezer)?,
+            transitive: self.transitive.freeze(freezer)?,
+            kind: self.kind,
+            phony: self.phony,
+        })
+    }
+}
+
+/// Declares the Starlark methods for the `depset` type.
+#[starlark_module]
+pub fn depset_methods(builder: &mut MethodsBuilder) {
+    fn to_list<'v>(this: &Depset<'v>) -> starlark::Result<Vec<Value<'v>>> {
+        Ok(this.iter().collect())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use testutils::Assert;
+
+    use super::*;
+    use crate::{
+        globals::tests::{new_assert, test_globals},
+        UnpackFileDepset,
+    };
+
+    #[test]
+    fn test_depset_deduplication() {
+        let mut a = new_assert();
+        let depset_val = a.pass("depset(['a', 'a'])");
+        let depset = depset_val.value().downcast_ref::<FrozenDepset>().unwrap();
+        assert_eq!(depset.direct().len(), 1);
+    }
+
+    #[test]
+    fn test_depset_invalid_transitive() {
+        let mut a = new_assert();
+        a.fail(
+            "depset(['c'], transitive=['not a depset'])",
+            "Expected value of type `depset` but got `string (repr: \"not a depset\")`",
+        );
+    }
+
+    #[test]
+    fn test_depset_conflicting_orders() {
+        let mut a = new_assert();
+        a.fail(
+            "depset(transitive=[depset(['a'], order='preorder'), depset(['b'], order='postorder')])",
+            "conflicting orders: depset has order preorder, but transitive child has order postorder",
+        );
+
+        // When outer depset specifies non-default order, we can't reuse the inner
+        // depset.
+        a.equivalent(
+            "depset(transitive=[depset(['c'], transitive=[depset(['a'])])], order='preorder').to_list()",
+            "['c', 'a']",
+        );
+    }
+
+    #[test]
+    fn test_depset_type_validation() {
+        let mut a = new_assert();
+        let frozen_str_depset = a.pass("depset(['a', 'b'])");
+        let frozen_file_depset = a.pass("depset([make_file('a.txt'), make_file('b.txt')])");
+
+        a.globals_add(move |builder: &mut starlark::environment::GlobalsBuilder| {
+            test_globals(builder);
+            builder.set("frozen_str_depset", frozen_str_depset.clone());
+            builder.set("frozen_file_depset", frozen_file_depset.clone());
+        });
+
+        // Homogeneous File depset.
+        a.equivalent(
+            "[f.path for f in depset([make_file('a.txt'), make_file('b.txt')]).to_list()]",
+            "['a.txt', 'b.txt']",
+        );
+
+        // Homogeneous string depset.
+        a.equivalent("depset(['a', 'b']).to_list()", "['a', 'b']");
+
+        // Mixing File and String in direct elements.
+        a.fail(
+            "depset([make_file('a.txt'), 'b'])",
+            "depset elements must be of the same type, expected File, got unknown",
+        );
+
+        // Mixing String and File in direct elements.
+        a.fail(
+            "depset(['a', make_file('b.txt')])",
+            "depset elements must be of the same type, expected unknown, got File",
+        );
+
+        // Mixing File depset and String depset in transitive elements.
+        a.fail(
+            "depset(transitive=[depset([make_file('a.txt')]), depset(['b'])])",
+            "depset elements must be of the same type, expected File, got unknown",
+        );
+
+        // Direct File elements mixed with transitive String depset.
+        a.fail(
+            "depset([make_file('a.txt')], transitive=[depset(['b'])])",
+            "depset elements must be of the same type, expected File, got unknown",
+        );
+
+        // Transitive depset containing a frozen depset.
+        a.equivalent(
+            "depset(['c'], transitive=[frozen_str_depset], order='postorder').to_list()",
+            "['a', 'b', 'c']",
+        );
+
+        // Transitive depset containing a frozen File depset.
+        a.equivalent(
+            "[f.path for f in depset([make_file('c.txt')], transitive=[frozen_file_depset], order='postorder').to_list()]",
+            "['a.txt', 'b.txt', 'c.txt']",
+        );
+    }
+
+    #[test]
+    fn test_depset_starlark_conversions() {
+        let mut a = new_assert();
+        // Truthiness checks.
+        a.equivalent("bool(depset(['a']))", "True");
+        a.equivalent("bool(depset())", "False");
+        a.equivalent("bool(depset(transitive=[depset()]))", "False");
+
+        a.equivalent("repr(depset())", "\"depset([])\"");
+    }
+
+    #[test]
+    fn test_depset_phony() {
+        let mut a = new_assert();
+
+        // This is to ensure we don't accidentally use File::new.
+        // We cannot mix File::new and File::from_rust to get the same file object.
+        let f = |s: &str| File::intern(s);
+
+        let mut upto_phony = 0;
+        // Collect the phonies we've seen since last time we called new_phonies.
+        let mut new_phonies = |a: &Assert| {
+            let phonies = &a.context().rule_state.phonies;
+            let result = &phonies[upto_phony..];
+            upto_phony = phonies.len();
+            result.to_vec()
+        };
+
+        assert!(UnpackFileDepset::unpack_value_err(a.pass("depset([1])").value()).is_err());
+
+        a.eq("depset()", UnpackFileDepset(None));
+        assert_eq!(new_phonies(&a), &[]);
+
+        // Because the outer depset only phonies to one item, we shouldn't make a phony.
+        a.eq(
+            "depset([make_file('a.txt')])",
+            UnpackFileDepset(Some(f("a.txt"))),
+        );
+        assert_eq!(new_phonies(&a), &[]);
+
+        // We should make a phony here for the inner depset.
+        // Because the outer depset only phonies to one phony, it shouldn't make a
+        // phony.
+        a.eq(
+            "depset(transitive = [depset([make_file('a.txt'), make_file('b.txt')])])",
+            UnpackFileDepset(Some(f("phony/$TOOLCHAIN/$LABEL_0"))),
+        );
+        assert_eq!(
+            new_phonies(&a),
+            &[(f("phony/$TOOLCHAIN/$LABEL_0"), vec![f("a.txt"), f("b.txt")])]
+        );
+        a.eq(
+            "depset([make_file('c.txt')], transitive=[depset([make_file('a.txt'), make_file('b.txt')])])",
+            UnpackFileDepset(Some(f("phony/$TOOLCHAIN/$LABEL_2"))),
+        );
+        assert_eq!(
+            new_phonies(&a),
+            &[
+                (f("phony/$TOOLCHAIN/$LABEL_1"), vec![f("a.txt"), f("b.txt")]),
+                (
+                    f("phony/$TOOLCHAIN/$LABEL_2"),
+                    vec![f("c.txt"), f("phony/$TOOLCHAIN/$LABEL_1")]
+                ),
+            ]
+        );
+        assert_eq!(new_phonies(&a), &[]);
+
+        a.eq(
+            "new_file_depset([make_file('a.txt')])",
+            UnpackFileDepset(Some(f("a.txt"))),
+        );
+        assert_eq!(new_phonies(&a), &[]);
+
+        a.eq(
+            "new_file_depset([make_file('a.txt'), make_file('b.txt')])",
+            UnpackFileDepset(Some(f("phony/$TOOLCHAIN/$LABEL_3"))),
+        );
+        assert_eq!(
+            new_phonies(&a),
+            &[(f("phony/$TOOLCHAIN/$LABEL_3"), vec![f("a.txt"), f("b.txt")])]
+        );
+    }
+}
diff --git a/src/gn/starlark/crates/depset/src/errors.rs b/src/gn/starlark/crates/depset/src/errors.rs
new file mode 100644
index 0000000..dfb3ada
--- /dev/null
+++ b/src/gn/starlark/crates/depset/src/errors.rs
@@ -0,0 +1,30 @@
+// 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 crate::{Kind, Order};
+
+/// Errors returned by depset validation and iteration operations.
+#[derive(thiserror::Error, Debug)]
+pub enum Error {
+    #[error("Invalid order: {0}")]
+    InvalidOrder(String),
+    #[error("conflicting orders: depset has order {order}, but transitive child has order {child_order}")]
+    ConflictingOrders { order: Order, child_order: Order },
+    #[error("depset elements must be of the same type, expected {expected}, got {got}")]
+    DepsetTypeMismatch { expected: Kind, got: Kind },
+    #[error("expected a file depset")]
+    ExpectedFileDepset,
+}
+
+impl From<Error> for starlark::Error {
+    fn from(err: Error) -> Self {
+        Self::new_other(err)
+    }
+}
+
+impl starlark::values::UnpackValueError for Error {
+    fn into_error(this: Self) -> starlark::Error {
+        starlark::Error::new_other(this)
+    }
+}
diff --git a/src/gn/starlark/crates/depset/src/globals.rs b/src/gn/starlark/crates/depset/src/globals.rs
new file mode 100644
index 0000000..9a032c8
--- /dev/null
+++ b/src/gn/starlark/crates/depset/src/globals.rs
@@ -0,0 +1,187 @@
+// 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 starlark::{
+    collections::SmallSet,
+    values::{list::UnpackList, Heap, UnpackValue as _, Value, ValueLike as _},
+};
+use types::File;
+
+use crate::{Depset, Kind, Order, UnpackDepset};
+
+/// Inner implementation of the Starlark `depset(...)` constructor.
+/// This checks type matching, detects order conflicts, and creates the depset
+/// value.
+pub fn depset_constructor<'v, C: types::EvalContext>(
+    direct: Option<UnpackList<Value<'v>>>,
+    transitive: Option<UnpackList<UnpackDepset<'v>>>,
+    mut order: Order,
+    heap: &Heap<'v>,
+    ctx: &mut C,
+) -> starlark::Result<Value<'v>> {
+    let mut kind = Kind::Empty;
+    let mut set_kind = |k: Kind| -> Result<(), crate::Error> {
+        if k == Kind::Empty {
+            return Ok(());
+        }
+        if kind == Kind::Empty {
+            kind = k;
+            Ok(())
+        } else if kind != k {
+            Err(crate::Error::DepsetTypeMismatch {
+                expected: kind,
+                got: k,
+            })
+        } else {
+            Ok(())
+        }
+    };
+
+    let mut direct_vec = Vec::new();
+    if let Some(direct_list) = direct {
+        let mut direct_set = SmallSet::with_capacity(direct_list.items.len());
+        direct_vec = Vec::with_capacity(direct_list.items.len());
+        for elem in direct_list.items {
+            if elem.downcast_ref::<File>().is_some() {
+                set_kind(Kind::File)?;
+            } else {
+                set_kind(Kind::Unknown)?;
+            }
+            if direct_set.insert_hashed(elem.get_hashed()?) {
+                direct_vec.push(elem);
+            }
+        }
+    }
+
+    let transitive_vec = match transitive {
+        Some(transitive_list) => transitive_list
+            .items
+            .into_iter()
+            .filter(|child_depset| !child_depset.is_empty())
+            .map(|child_depset| {
+                let child_order = child_depset.order();
+                if child_order != Order::Unspecified {
+                    if order == Order::Unspecified {
+                        order = child_order;
+                    } else if order != child_order {
+                        return Err(crate::Error::ConflictingOrders { order, child_order });
+                    }
+                }
+                set_kind(*child_depset.kind())?;
+                Ok(child_depset.value())
+            })
+            .collect::<Result<Vec<_>, crate::Error>>()?,
+        None => Vec::new(),
+    };
+
+    if direct_vec.is_empty() && transitive_vec.len() == 1 {
+        // Safe to unwrap because we validated it's a depset when pushing to
+        // transitive_vec.
+        let child_depset = Depset::from_value(transitive_vec[0]).unwrap();
+        if order == child_depset.order() || order == Order::Unspecified {
+            // Just reuse the child depset object.
+            Ok(transitive_vec[0])
+        } else {
+            // We cannot reuse the child because the wrapper specifies a different order,
+            // so we create a new equivalent depset wrapping it.
+            Ok(heap.alloc(Depset {
+                order,
+                direct: child_depset.direct.clone(),
+                transitive: child_depset.transitive.clone(),
+                kind: child_depset.kind.clone(),
+                phony: child_depset.phony.clone(),
+            }))
+        }
+    } else {
+        let phony = if kind == Kind::File {
+            if direct_vec.len() == 1 && transitive_vec.is_empty() {
+                // If the depset contains only a single element, its phony is actually just the
+                // real object. We don't need to do this for transitive, because
+                // we optimize a depset with 1 transitive and no direct to not even create a
+                // depset object.
+                direct_vec[0].downcast_ref::<File>().cloned()
+            } else if !direct_vec.is_empty() || !transitive_vec.is_empty() {
+                let mut deps = vec![];
+                for v in &direct_vec {
+                    // Safety: `v` is guaranteed to be a `File` because we validated all direct
+                    // elements when setting the depset kind to `Kind::File`.
+                    deps.push(v.downcast_ref::<File>().unwrap().clone());
+                }
+                for v in &transitive_vec {
+                    // Safety:
+                    // 1. `v` is guaranteed to be a `Depset` because we successfully unpacked it and
+                    //    validated its kind during transition loop validation.
+                    // 2. The child depset is guaranteed to have a `phony` File because it is a
+                    //    non-empty `Kind::File` depset, which always has a phony file.
+                    let child_dep = UnpackDepset::unpack_value(*v).unwrap().unwrap();
+                    deps.push(child_dep.phony().as_ref().unwrap().clone());
+                }
+                let state = ctx.require_rule_impl_mut()?;
+                Some(state.new_phony(deps))
+            } else {
+                None
+            }
+        } else {
+            None
+        };
+
+        Ok(heap.alloc(Depset {
+            order,
+            direct: direct_vec,
+            transitive: transitive_vec,
+            kind,
+            phony,
+        }))
+    }
+}
+
+#[cfg(test)]
+pub(crate) mod tests {
+    use starlark::{environment::GlobalsBuilder, eval::Evaluator};
+    use starlark_derive::starlark_module;
+    use types::EvaluatorContextExt as _;
+
+    use super::*;
+
+    #[starlark_module]
+    pub(crate) fn test_globals(builder: &mut GlobalsBuilder) {
+        fn make_file<'v>(
+            eval: &mut Evaluator<'v, '_, '_>,
+            path: String,
+        ) -> starlark::Result<Value<'v>> {
+            Ok(eval.heap().alloc(types::File::intern(&path)))
+        }
+
+        fn new_file_depset<'v>(
+            files: UnpackList<&File>,
+            eval: &mut Evaluator<'v, '_, '_>,
+        ) -> starlark::Result<Depset<'v>> {
+            let heap = eval.heap();
+            let ctx = eval.context_mut::<testutils::eval_context::FakeEvalContext>();
+            let direct = files.items.into_iter().cloned().collect();
+            Depset::new_file_depset(direct, &heap, ctx)
+        }
+
+        fn depset<'v>(
+            direct: Option<UnpackList<Value<'v>>>,
+            transitive: Option<UnpackList<crate::UnpackDepset<'v>>>,
+            #[starlark(default = crate::Order::Unspecified)] order: crate::Order,
+            eval: &mut Evaluator<'v, '_, '_>,
+        ) -> starlark::Result<Value<'v>> {
+            crate::depset_constructor::<testutils::FakeEvalContext>(
+                direct,
+                transitive,
+                order,
+                &eval.heap(),
+                eval.context_mut(),
+            )
+        }
+    }
+
+    pub(crate) fn new_assert() -> testutils::Assert {
+        let mut a = testutils::Assert::default();
+        a.globals_add(test_globals);
+        a
+    }
+}
diff --git a/src/gn/starlark/crates/depset/src/iter.rs b/src/gn/starlark/crates/depset/src/iter.rs
new file mode 100644
index 0000000..d127dcf
--- /dev/null
+++ b/src/gn/starlark/crates/depset/src/iter.rs
@@ -0,0 +1,199 @@
+// 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 starlark::{
+    collections::SmallSet,
+    values::{ProvidesStaticType, UnpackValue as _, Value, ValueLike},
+};
+
+use crate::{
+    depset::{Depset, DepsetGen, Order},
+    unpack::UnpackDepset,
+};
+
+/// An iterator over the elements of a depset, respecting its traversal order.
+pub struct DepsetIterator<'a, 'v> {
+    stack: Vec<IterState<'a, 'v>>,
+    visited_nodes: std::collections::HashSet<usize>,
+    visited_elements: SmallSet<Value<'v>>,
+    order: Order,
+    topo_buffer: Option<Vec<Value<'v>>>,
+}
+
+enum IterState<'a, 'v> {
+    Direct {
+        iter: std::slice::Iter<'a, Value<'v>>,
+    },
+    Transitive {
+        iter: std::slice::Iter<'a, Value<'v>>,
+    },
+}
+
+impl<'a, 'v> DepsetIterator<'a, 'v> {
+    fn push_depset(&mut self, depset: &'a Depset<'v>, order: Order) {
+        if !depset.is_empty() {
+            match order {
+                Order::Preorder => {
+                    self.stack.push(IterState::Transitive {
+                        iter: depset.transitive().iter(),
+                    });
+                    self.stack.push(IterState::Direct {
+                        iter: depset.direct().iter(),
+                    });
+                },
+                Order::Postorder | Order::Unspecified => {
+                    self.stack.push(IterState::Direct {
+                        iter: depset.direct().iter(),
+                    });
+                    self.stack.push(IterState::Transitive {
+                        iter: depset.transitive().iter(),
+                    });
+                },
+                Order::Topological => unreachable!(),
+            }
+        }
+    }
+}
+
+impl<'a, 'v> Iterator for DepsetIterator<'a, 'v>
+where
+    'v: 'a,
+{
+    type Item = Value<'v>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        while let Some(state) = self.stack.last_mut() {
+            match state {
+                IterState::Direct { iter } => {
+                    if let Some(&val) = iter.next() {
+                        let hash = val.get_hashed().expect("Already verified hashable");
+                        if self.visited_elements.insert_hashed(hash) {
+                            return Some(val);
+                        }
+                    } else {
+                        self.stack.pop();
+                    }
+                },
+                IterState::Transitive { iter } => {
+                    if let Some(&child_val) = iter.next() {
+                        if let Some(child_depset) =
+                            UnpackDepset::unpack_value(child_val).ok().flatten()
+                        {
+                            let child_depset: &'v Depset<'v> = child_depset.depset();
+                            let node_id = std::ptr::from_ref::<Depset<'v>>(child_depset) as usize;
+                            if self.visited_nodes.insert(node_id) {
+                                self.push_depset(child_depset, self.order);
+                            }
+                        }
+                    } else {
+                        self.stack.pop();
+                    }
+                },
+            }
+        }
+
+        if self.order == Order::Topological {
+            // Safety: Topo order should always have topo buffer set
+            return unsafe { self.topo_buffer.as_mut().unwrap_unchecked() }.pop();
+        }
+
+        None
+    }
+}
+
+impl<'v, V: ValueLike<'v>> DepsetGen<V>
+where
+    V: starlark::coerce::Coerce<Value<'v>>,
+    Self: ProvidesStaticType<'v>,
+{
+    fn iter_ordered<'a>(&'a self, order: Order) -> DepsetIterator<'a, 'v>
+    where
+        'v: 'a,
+    {
+        let mut iter = DepsetIterator {
+            stack: Vec::new(),
+            visited_nodes: std::collections::HashSet::new(),
+            visited_elements: Default::default(),
+            order,
+            // Topological order requires complete collection before yielding any elements.
+            // We just do reverse postorder by collecting postorder to a vec and having iter
+            // call vec.pop().
+            topo_buffer: if order == Order::Topological {
+                Some(self.iter_ordered(Order::Postorder).collect())
+            } else {
+                None
+            },
+        };
+        if order != Order::Topological {
+            let depset: &Depset<'v> = starlark::coerce::coerce(self);
+            iter.visited_nodes
+                .insert(std::ptr::from_ref::<Depset<'v>>(depset) as usize);
+            iter.push_depset(depset, order);
+        }
+        iter
+    }
+
+    /// Returns an iterator over the elements in the depset using its configured
+    /// order.
+    pub fn iter<'a>(&'a self) -> DepsetIterator<'a, 'v>
+    where
+        'v: 'a,
+    {
+        self.iter_ordered(self.order())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::globals::tests::new_assert;
+
+    #[test]
+    fn test_depset() {
+        let mut a = new_assert();
+        a.equivalent(
+            "depset(['c'], transitive=[depset(['a', 'b'])], order='preorder').to_list()",
+            "['c', 'a', 'b']",
+        );
+        a.equivalent(
+            "depset(['c'], transitive=[depset(['a', 'b'])], order='postorder').to_list()",
+            "['a', 'b', 'c']",
+        );
+        a.equivalent(
+            "depset(['c'], transitive=[depset(['a', 'b'])], order='topological').to_list()",
+            "['c', 'b', 'a']",
+        );
+    }
+
+    #[test]
+    fn test_depset_complex_graph() {
+        let mut a = new_assert();
+        a.equivalent(
+            r#"
+d1 = depset(['a'])
+d2 = depset(['b', 'c'], transitive=[d1])
+d3 = depset(['d'], transitive=[d1])
+depset(['e'], transitive=[d2, d3], order='preorder').to_list()
+"#,
+            "['e', 'b', 'c', 'a', 'd']",
+        );
+        a.equivalent(
+            r#"
+d1 = depset(['a'])
+d2 = depset(['b', 'c'], transitive=[d1])
+d3 = depset(['d'], transitive=[d1])
+depset(['e'], transitive=[d2, d3], order='postorder').to_list()
+"#,
+            "['a', 'b', 'c', 'd', 'e']",
+        );
+        a.equivalent(
+            r#"
+d1 = depset(['a'])
+d2 = depset(['b', 'c'], transitive=[d1])
+d3 = depset(['d'], transitive=[d1])
+depset(['e'], transitive=[d2, d3], order='topological').to_list()
+"#,
+            "['e', 'd', 'c', 'b', 'a']",
+        );
+    }
+}
diff --git a/src/gn/starlark/crates/depset/src/lib.rs b/src/gn/starlark/crates/depset/src/lib.rs
new file mode 100644
index 0000000..7d62b63
--- /dev/null
+++ b/src/gn/starlark/crates/depset/src/lib.rs
@@ -0,0 +1,14 @@
+// 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.
+
+mod depset;
+pub mod errors;
+mod globals;
+mod iter;
+mod unpack;
+
+pub use depset::{Depset, DepsetGen, FrozenDepset, Kind, Order};
+pub use errors::Error;
+pub use globals::depset_constructor;
+pub use unpack::{UnpackDepset, UnpackFileDepset};
diff --git a/src/gn/starlark/crates/depset/src/unpack.rs b/src/gn/starlark/crates/depset/src/unpack.rs
new file mode 100644
index 0000000..1606e32
--- /dev/null
+++ b/src/gn/starlark/crates/depset/src/unpack.rs
@@ -0,0 +1,91 @@
+// 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 starlark::{
+    typing::Ty,
+    values::{type_repr::StarlarkTypeRepr, FrozenValueTyped, UnpackValue, Value, ValueTyped},
+};
+use types::File;
+
+use crate::depset::{Depset, FrozenDepset};
+
+/// Helper type to unpack a Starlark `Value` as either a mutable or frozen
+/// `Depset`.
+pub struct UnpackDepset<'v> {
+    depset: &'v Depset<'v>,
+    value: Value<'v>,
+}
+
+impl<'v> StarlarkTypeRepr for UnpackDepset<'v> {
+    type Canonical = <&'v Depset<'v> as StarlarkTypeRepr>::Canonical;
+
+    fn starlark_type_repr() -> Ty {
+        <&'v Depset<'v> as StarlarkTypeRepr>::starlark_type_repr()
+    }
+}
+
+impl<'v> UnpackValue<'v> for UnpackDepset<'v> {
+    type Error = starlark::Error;
+
+    fn unpack_value_impl(value: Value<'v>) -> Result<Option<Self>, Self::Error> {
+        if let Some(frozen) = value
+            .unpack_frozen()
+            .and_then(FrozenValueTyped::<FrozenDepset>::new)
+        {
+            let depset: &'v Depset<'v> = starlark::coerce::coerce(frozen.as_ref());
+            Ok(Some(UnpackDepset { depset, value }))
+        } else {
+            let mutable = ValueTyped::<Depset<'v>>::new_err(value)?;
+            let depset: &'v Depset<'v> = mutable.as_ref();
+            Ok(Some(UnpackDepset { depset, value }))
+        }
+    }
+}
+
+use std::ops::Deref;
+
+impl<'v> Deref for UnpackDepset<'v> {
+    type Target = Depset<'v>;
+
+    fn deref(&self) -> &Self::Target {
+        self.depset
+    }
+}
+impl<'v> UnpackDepset<'v> {
+    /// Returns a reference to the unpacked `Depset`.
+    pub fn depset(&self) -> &'v Depset<'v> {
+        self.depset
+    }
+
+    /// Returns the raw `Value` that was unpacked.
+    pub fn value(&self) -> Value<'v> {
+        self.value
+    }
+}
+
+/// Helper to unpack a depset and retrieve its single `File` if it represents a
+/// phony file depset.
+#[derive(Debug, PartialEq, Eq)]
+pub struct UnpackFileDepset(pub Option<File>);
+
+impl StarlarkTypeRepr for UnpackFileDepset {
+    type Canonical = Self;
+
+    fn starlark_type_repr() -> Ty {
+        Ty::any()
+    }
+}
+
+impl<'v> UnpackValue<'v> for UnpackFileDepset {
+    type Error = starlark::Error;
+
+    fn unpack_value_impl(value: Value<'v>) -> Result<Option<Self>, Self::Error> {
+        let depset = UnpackDepset::unpack_value_err(value)?;
+        if depset.phony().is_some() || depset.is_empty() {
+            Ok(Some(Self(depset.depset.phony().clone())))
+        } else {
+            Err(crate::errors::Error::ExpectedFileDepset.into())
+        }
+    }
+}