Create starlark depset crate Bug: 528225104 Change-Id: Iee012057ff2a7fe5cc3a014a9abd52966a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/23802 Reviewed-by: Matt Stark <msta@google.com> Commit-Queue: Matt Stark <msta@google.com> Reviewed-by: Philipp Wollermann <philwo@google.com> Reviewed-by: Cole Faust <colefaust@google.com>
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()) + } + } +}