1//! Determining which types for which we cannot emit `#[derive(Trait)]`.
2
3use std::fmt;
4
5use super::{generate_dependencies, ConstrainResult, MonotoneFramework};
6use crate::ir::analysis::has_vtable::HasVtable;
7use crate::ir::comp::CompKind;
8use crate::ir::context::{BindgenContext, ItemId};
9use crate::ir::derive::CanDerive;
10use crate::ir::function::FunctionSig;
11use crate::ir::item::{IsOpaque, Item};
12use crate::ir::layout::Layout;
13use crate::ir::template::TemplateParameters;
14use crate::ir::traversal::{EdgeKind, Trace};
15use crate::ir::ty::RUST_DERIVE_IN_ARRAY_LIMIT;
16use crate::ir::ty::{Type, TypeKind};
17use crate::{Entry, HashMap, HashSet};
18
19/// Which trait to consider when doing the `CannotDerive` analysis.
20#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
21pub enum DeriveTrait {
22 /// The `Copy` trait.
23 Copy,
24 /// The `Debug` trait.
25 Debug,
26 /// The `Default` trait.
27 Default,
28 /// The `Hash` trait.
29 Hash,
30 /// The `PartialEq` and `PartialOrd` traits.
31 PartialEqOrPartialOrd,
32}
33
34/// An analysis that finds for each IR item whether a trait cannot be derived.
35///
36/// We use the monotone constraint function `cannot_derive`, defined as follows
37/// for type T:
38///
39/// * If T is Opaque and the layout of the type is known, get this layout as an
40/// opaquetype and check whether it can derive using trivial checks.
41///
42/// * If T is Array, a trait cannot be derived if the array is incomplete,
43/// if the length of the array is larger than the limit (unless the trait
44/// allows it), or the trait cannot be derived for the type of data the array
45/// contains.
46///
47/// * If T is Vector, a trait cannot be derived if the trait cannot be derived
48/// for the type of data the vector contains.
49///
50/// * If T is a type alias, a templated alias or an indirection to another type,
51/// the trait cannot be derived if the trait cannot be derived for type T
52/// refers to.
53///
54/// * If T is a compound type, the trait cannot be derived if the trait cannot
55/// be derived for any of its base members or fields.
56///
57/// * If T is an instantiation of an abstract template definition, the trait
58/// cannot be derived if any of the template arguments or template definition
59/// cannot derive the trait.
60///
61/// * For all other (simple) types, compiler and standard library limitations
62/// dictate whether the trait is implemented.
63#[derive(Debug, Clone)]
64pub(crate) struct CannotDerive<'ctx> {
65 ctx: &'ctx BindgenContext,
66
67 derive_trait: DeriveTrait,
68
69 // The incremental result of this analysis's computation.
70 // Contains information whether particular item can derive `derive_trait`
71 can_derive: HashMap<ItemId, CanDerive>,
72
73 // Dependencies saying that if a key ItemId has been inserted into the
74 // `cannot_derive_partialeq_or_partialord` set, then each of the ids
75 // in Vec<ItemId> need to be considered again.
76 //
77 // This is a subset of the natural IR graph with reversed edges, where we
78 // only include the edges from the IR graph that can affect whether a type
79 // can derive `derive_trait`.
80 dependencies: HashMap<ItemId, Vec<ItemId>>,
81}
82
83type EdgePredicate = fn(EdgeKind) -> bool;
84
85fn consider_edge_default(kind: EdgeKind) -> bool {
86 match kind {
87 // These are the only edges that can affect whether a type can derive
88 EdgeKind::BaseMember |
89 EdgeKind::Field |
90 EdgeKind::TypeReference |
91 EdgeKind::VarType |
92 EdgeKind::TemplateArgument |
93 EdgeKind::TemplateDeclaration |
94 EdgeKind::TemplateParameterDefinition => true,
95
96 EdgeKind::Constructor |
97 EdgeKind::Destructor |
98 EdgeKind::FunctionReturn |
99 EdgeKind::FunctionParameter |
100 EdgeKind::InnerType |
101 EdgeKind::InnerVar |
102 EdgeKind::Method |
103 EdgeKind::Generic => false,
104 }
105}
106
107impl CannotDerive<'_> {
108 fn insert<Id: Into<ItemId>>(
109 &mut self,
110 id: Id,
111 can_derive: CanDerive,
112 ) -> ConstrainResult {
113 let id = id.into();
114 trace!(
115 "inserting {id:?} can_derive<{}>={can_derive:?}",
116 self.derive_trait,
117 );
118
119 if let CanDerive::Yes = can_derive {
120 return ConstrainResult::Same;
121 }
122
123 match self.can_derive.entry(id) {
124 Entry::Occupied(mut entry) => {
125 if *entry.get() < can_derive {
126 entry.insert(can_derive);
127 ConstrainResult::Changed
128 } else {
129 ConstrainResult::Same
130 }
131 }
132 Entry::Vacant(entry) => {
133 entry.insert(can_derive);
134 ConstrainResult::Changed
135 }
136 }
137 }
138
139 fn constrain_type(&mut self, item: &Item, ty: &Type) -> CanDerive {
140 if !self.ctx.allowlisted_items().contains(&item.id()) {
141 let can_derive = self
142 .ctx
143 .blocklisted_type_implements_trait(item, self.derive_trait);
144 match can_derive {
145 CanDerive::Yes => trace!(
146 " blocklisted type explicitly implements {}",
147 self.derive_trait
148 ),
149 CanDerive::Manually => trace!(
150 " blocklisted type requires manual implementation of {}",
151 self.derive_trait
152 ),
153 CanDerive::No => trace!(
154 " cannot derive {} for blocklisted type",
155 self.derive_trait
156 ),
157 }
158 return can_derive;
159 }
160
161 if self.derive_trait.not_by_name(self.ctx, item) {
162 trace!(
163 " cannot derive {} for explicitly excluded type",
164 self.derive_trait
165 );
166 return CanDerive::No;
167 }
168
169 trace!("ty: {ty:?}");
170 if item.is_opaque(self.ctx, &()) {
171 if !self.derive_trait.can_derive_union() &&
172 ty.is_union() &&
173 self.ctx.options().untagged_union
174 {
175 trace!(
176 " cannot derive {} for Rust unions",
177 self.derive_trait
178 );
179 return CanDerive::No;
180 }
181
182 let layout_can_derive =
183 ty.layout(self.ctx).map_or(CanDerive::Yes, |l| {
184 l.opaque().array_size_within_derive_limit()
185 });
186
187 match layout_can_derive {
188 CanDerive::Yes => {
189 trace!(
190 " we can trivially derive {} for the layout",
191 self.derive_trait
192 );
193 }
194 _ => {
195 trace!(
196 " we cannot derive {} for the layout",
197 self.derive_trait
198 );
199 }
200 };
201 return layout_can_derive;
202 }
203
204 match *ty.kind() {
205 // Handle the simple cases. These can derive traits without further
206 // information.
207 TypeKind::Void |
208 TypeKind::NullPtr |
209 TypeKind::Int(..) |
210 TypeKind::Complex(..) |
211 TypeKind::Float(..) |
212 TypeKind::Enum(..) |
213 TypeKind::TypeParam |
214 TypeKind::UnresolvedTypeRef(..) |
215 TypeKind::Reference(..) |
216 TypeKind::ObjCInterface(..) |
217 TypeKind::ObjCId |
218 TypeKind::ObjCSel => self.derive_trait.can_derive_simple(ty.kind()),
219 TypeKind::Pointer(inner) => {
220 let inner_type =
221 self.ctx.resolve_type(inner).canonical_type(self.ctx);
222 if let TypeKind::Function(ref sig) = *inner_type.kind() {
223 self.derive_trait.can_derive_fnptr(sig)
224 } else {
225 self.derive_trait.can_derive_pointer()
226 }
227 }
228 TypeKind::Function(ref sig) => {
229 self.derive_trait.can_derive_fnptr(sig)
230 }
231
232 // Complex cases need more information
233 TypeKind::Array(t, len) => {
234 let inner_type =
235 self.can_derive.get(&t.into()).copied().unwrap_or_default();
236 if inner_type != CanDerive::Yes {
237 trace!(
238 " arrays of T for which we cannot derive {} \
239 also cannot derive {}",
240 self.derive_trait,
241 self.derive_trait
242 );
243 return CanDerive::No;
244 }
245
246 if len == 0 && !self.derive_trait.can_derive_incomplete_array()
247 {
248 trace!(
249 " cannot derive {} for incomplete arrays",
250 self.derive_trait
251 );
252 return CanDerive::No;
253 }
254
255 if self.derive_trait.can_derive_large_array(self.ctx) {
256 trace!(" array can derive {}", self.derive_trait);
257 return CanDerive::Yes;
258 }
259
260 if len > RUST_DERIVE_IN_ARRAY_LIMIT {
261 trace!(
262 " array is too large to derive {}, but it may be implemented", self.derive_trait
263 );
264 return CanDerive::Manually;
265 }
266 trace!(
267 " array is small enough to derive {}",
268 self.derive_trait
269 );
270 CanDerive::Yes
271 }
272 TypeKind::Vector(t, len) => {
273 let inner_type =
274 self.can_derive.get(&t.into()).copied().unwrap_or_default();
275 if inner_type != CanDerive::Yes {
276 trace!(
277 " vectors of T for which we cannot derive {} \
278 also cannot derive {}",
279 self.derive_trait,
280 self.derive_trait
281 );
282 return CanDerive::No;
283 }
284 assert_ne!(len, 0, "vectors cannot have zero length");
285 self.derive_trait.can_derive_vector()
286 }
287
288 TypeKind::Comp(ref info) => {
289 assert!(
290 !info.has_non_type_template_params(),
291 "The early ty.is_opaque check should have handled this case"
292 );
293
294 if !self.derive_trait.can_derive_compound_forward_decl() &&
295 info.is_forward_declaration()
296 {
297 trace!(
298 " cannot derive {} for forward decls",
299 self.derive_trait
300 );
301 return CanDerive::No;
302 }
303
304 // NOTE: Take into account that while unions in C and C++ are copied by
305 // default, the may have an explicit destructor in C++, so we can't
306 // defer this check just for the union case.
307 if !self.derive_trait.can_derive_compound_with_destructor() &&
308 self.ctx.lookup_has_destructor(
309 item.id().expect_type_id(self.ctx),
310 )
311 {
312 trace!(
313 " comp has destructor which cannot derive {}",
314 self.derive_trait
315 );
316 return CanDerive::No;
317 }
318
319 if info.kind() == CompKind::Union {
320 if self.derive_trait.can_derive_union() {
321 if self.ctx.options().untagged_union &&
322 // https://github.com/rust-lang/rust/issues/36640
323 (!info.self_template_params(self.ctx).is_empty() ||
324 !item.all_template_params(self.ctx).is_empty())
325 {
326 trace!(
327 " cannot derive {} for Rust union because issue 36640", self.derive_trait
328 );
329 return CanDerive::No;
330 }
331 // fall through to be same as non-union handling
332 } else {
333 if self.ctx.options().untagged_union {
334 trace!(
335 " cannot derive {} for Rust unions",
336 self.derive_trait
337 );
338 return CanDerive::No;
339 }
340
341 let layout_can_derive =
342 ty.layout(self.ctx).map_or(CanDerive::Yes, |l| {
343 l.opaque().array_size_within_derive_limit()
344 });
345 match layout_can_derive {
346 CanDerive::Yes => {
347 trace!(
348 " union layout can trivially derive {}",
349 self.derive_trait
350 );
351 }
352 _ => {
353 trace!(
354 " union layout cannot derive {}",
355 self.derive_trait
356 );
357 }
358 };
359 return layout_can_derive;
360 }
361 }
362
363 if !self.derive_trait.can_derive_compound_with_vtable() &&
364 item.has_vtable(self.ctx)
365 {
366 trace!(
367 " cannot derive {} for comp with vtable",
368 self.derive_trait
369 );
370 return CanDerive::No;
371 }
372
373 // Bitfield units are always represented as arrays of u8, but
374 // they're not traced as arrays, so we need to check here
375 // instead.
376 if !self.derive_trait.can_derive_large_array(self.ctx) &&
377 info.has_too_large_bitfield_unit() &&
378 !item.is_opaque(self.ctx, &())
379 {
380 trace!(
381 " cannot derive {} for comp with too large bitfield unit",
382 self.derive_trait
383 );
384 return CanDerive::No;
385 }
386
387 let pred = self.derive_trait.consider_edge_comp();
388 self.constrain_join(item, pred)
389 }
390
391 TypeKind::ResolvedTypeRef(..) |
392 TypeKind::TemplateAlias(..) |
393 TypeKind::Alias(..) |
394 TypeKind::BlockPointer(..) => {
395 let pred = self.derive_trait.consider_edge_typeref();
396 self.constrain_join(item, pred)
397 }
398
399 TypeKind::TemplateInstantiation(..) => {
400 let pred = self.derive_trait.consider_edge_tmpl_inst();
401 self.constrain_join(item, pred)
402 }
403
404 TypeKind::Opaque => unreachable!(
405 "The early ty.is_opaque check should have handled this case"
406 ),
407 }
408 }
409
410 fn constrain_join(
411 &mut self,
412 item: &Item,
413 consider_edge: EdgePredicate,
414 ) -> CanDerive {
415 let mut candidate = None;
416
417 item.trace(
418 self.ctx,
419 &mut |sub_id, edge_kind| {
420 // Ignore ourselves, since union with ourself is a
421 // no-op. Ignore edges that aren't relevant to the
422 // analysis.
423 if sub_id == item.id() || !consider_edge(edge_kind) {
424 return;
425 }
426
427 let can_derive = self.can_derive
428 .get(&sub_id)
429 .copied()
430 .unwrap_or_default();
431
432 match can_derive {
433 CanDerive::Yes => trace!(" member {sub_id:?} can derive {}", self.derive_trait),
434 CanDerive::Manually => trace!(" member {sub_id:?} cannot derive {}, but it may be implemented", self.derive_trait),
435 CanDerive::No => trace!(" member {sub_id:?} cannot derive {}", self.derive_trait),
436 }
437
438 *candidate.get_or_insert(CanDerive::Yes) |= can_derive;
439 },
440 &(),
441 );
442
443 if candidate.is_none() {
444 trace!(
445 " can derive {} because there are no members",
446 self.derive_trait
447 );
448 }
449 candidate.unwrap_or_default()
450 }
451}
452
453impl DeriveTrait {
454 fn not_by_name(&self, ctx: &BindgenContext, item: &Item) -> bool {
455 match self {
456 DeriveTrait::Copy => ctx.no_copy_by_name(item),
457 DeriveTrait::Debug => ctx.no_debug_by_name(item),
458 DeriveTrait::Default => ctx.no_default_by_name(item),
459 DeriveTrait::Hash => ctx.no_hash_by_name(item),
460 DeriveTrait::PartialEqOrPartialOrd => {
461 ctx.no_partialeq_by_name(item)
462 }
463 }
464 }
465
466 fn consider_edge_comp(&self) -> EdgePredicate {
467 match self {
468 DeriveTrait::PartialEqOrPartialOrd => consider_edge_default,
469 _ => |kind| matches!(kind, EdgeKind::BaseMember | EdgeKind::Field),
470 }
471 }
472
473 fn consider_edge_typeref(&self) -> EdgePredicate {
474 match self {
475 DeriveTrait::PartialEqOrPartialOrd => consider_edge_default,
476 _ => |kind| kind == EdgeKind::TypeReference,
477 }
478 }
479
480 fn consider_edge_tmpl_inst(&self) -> EdgePredicate {
481 match self {
482 DeriveTrait::PartialEqOrPartialOrd => consider_edge_default,
483 _ => |kind| {
484 matches!(
485 kind,
486 EdgeKind::TemplateArgument | EdgeKind::TemplateDeclaration
487 )
488 },
489 }
490 }
491
492 fn can_derive_large_array(&self, ctx: &BindgenContext) -> bool {
493 if ctx.options().rust_features().larger_arrays {
494 !matches!(self, DeriveTrait::Default)
495 } else {
496 matches!(self, DeriveTrait::Copy)
497 }
498 }
499
500 fn can_derive_union(&self) -> bool {
501 matches!(self, DeriveTrait::Copy)
502 }
503
504 fn can_derive_compound_with_destructor(&self) -> bool {
505 !matches!(self, DeriveTrait::Copy)
506 }
507
508 fn can_derive_compound_with_vtable(&self) -> bool {
509 !matches!(self, DeriveTrait::Default)
510 }
511
512 fn can_derive_compound_forward_decl(&self) -> bool {
513 matches!(self, DeriveTrait::Copy | DeriveTrait::Debug)
514 }
515
516 fn can_derive_incomplete_array(&self) -> bool {
517 !matches!(
518 self,
519 DeriveTrait::Copy |
520 DeriveTrait::Hash |
521 DeriveTrait::PartialEqOrPartialOrd
522 )
523 }
524
525 fn can_derive_fnptr(&self, f: &FunctionSig) -> CanDerive {
526 match (self, f.function_pointers_can_derive()) {
527 (DeriveTrait::Copy, _) | (DeriveTrait::Default, _) | (_, true) => {
528 trace!(" function pointer can derive {self}");
529 CanDerive::Yes
530 }
531 (DeriveTrait::Debug, false) => {
532 trace!(" function pointer cannot derive {self}, but it may be implemented");
533 CanDerive::Manually
534 }
535 (_, false) => {
536 trace!(" function pointer cannot derive {self}");
537 CanDerive::No
538 }
539 }
540 }
541
542 fn can_derive_vector(&self) -> CanDerive {
543 if *self == DeriveTrait::PartialEqOrPartialOrd {
544 // FIXME: vectors always can derive PartialEq, but they should
545 // not derive PartialOrd:
546 // https://github.com/rust-lang-nursery/packed_simd/issues/48
547 trace!(" vectors cannot derive PartialOrd");
548 CanDerive::No
549 } else {
550 trace!(" vector can derive {self}");
551 CanDerive::Yes
552 }
553 }
554
555 fn can_derive_pointer(&self) -> CanDerive {
556 if *self == DeriveTrait::Default {
557 trace!(" pointer cannot derive Default");
558 CanDerive::No
559 } else {
560 trace!(" pointer can derive {self}");
561 CanDerive::Yes
562 }
563 }
564
565 fn can_derive_simple(&self, kind: &TypeKind) -> CanDerive {
566 match (self, kind) {
567 // === Default ===
568 (DeriveTrait::Default, TypeKind::Void) |
569 (DeriveTrait::Default, TypeKind::NullPtr) |
570 (DeriveTrait::Default, TypeKind::Enum(..)) |
571 (DeriveTrait::Default, TypeKind::Reference(..)) |
572 (DeriveTrait::Default, TypeKind::TypeParam) |
573 (DeriveTrait::Default, TypeKind::ObjCInterface(..)) |
574 (DeriveTrait::Default, TypeKind::ObjCId) |
575 (DeriveTrait::Default, TypeKind::ObjCSel) => {
576 trace!(" types that always cannot derive Default");
577 CanDerive::No
578 }
579 (DeriveTrait::Default, TypeKind::UnresolvedTypeRef(..)) => {
580 unreachable!(
581 "Type with unresolved type ref can't reach derive default"
582 )
583 }
584 // === Hash ===
585 (DeriveTrait::Hash, TypeKind::Float(..)) |
586 (DeriveTrait::Hash, TypeKind::Complex(..)) => {
587 trace!(" float cannot derive Hash");
588 CanDerive::No
589 }
590 // === others ===
591 _ => {
592 trace!(" simple type that can always derive {self}");
593 CanDerive::Yes
594 }
595 }
596 }
597}
598
599impl fmt::Display for DeriveTrait {
600 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
601 let s: &'static str = match self {
602 DeriveTrait::Copy => "Copy",
603 DeriveTrait::Debug => "Debug",
604 DeriveTrait::Default => "Default",
605 DeriveTrait::Hash => "Hash",
606 DeriveTrait::PartialEqOrPartialOrd => "PartialEq/PartialOrd",
607 };
608 s.fmt(f)
609 }
610}
611
612impl<'ctx> MonotoneFramework for CannotDerive<'ctx> {
613 type Node = ItemId;
614 type Extra = (&'ctx BindgenContext, DeriveTrait);
615 type Output = HashMap<ItemId, CanDerive>;
616
617 fn new(
618 (ctx, derive_trait): (&'ctx BindgenContext, DeriveTrait),
619 ) -> CannotDerive<'ctx> {
620 let can_derive = HashMap::default();
621 let dependencies = generate_dependencies(ctx, consider_edge_default);
622
623 CannotDerive {
624 ctx,
625 derive_trait,
626 can_derive,
627 dependencies,
628 }
629 }
630
631 fn initial_worklist(&self) -> Vec<ItemId> {
632 // The transitive closure of all allowlisted items, including explicitly
633 // blocklisted items.
634 self.ctx
635 .allowlisted_items()
636 .iter()
637 .copied()
638 .flat_map(|i| {
639 let mut reachable = vec![i];
640 i.trace(
641 self.ctx,
642 &mut |s, _| {
643 reachable.push(s);
644 },
645 &(),
646 );
647 reachable
648 })
649 .collect()
650 }
651
652 fn constrain(&mut self, id: ItemId) -> ConstrainResult {
653 trace!("constrain: {id:?}");
654
655 if let Some(CanDerive::No) = self.can_derive.get(&id) {
656 trace!(" already know it cannot derive {}", self.derive_trait);
657 return ConstrainResult::Same;
658 }
659
660 let item = self.ctx.resolve_item(id);
661 let can_derive = match item.as_type() {
662 Some(ty) => {
663 let mut can_derive = self.constrain_type(item, ty);
664 if let CanDerive::Yes = can_derive {
665 let is_reached_limit =
666 |l: Layout| l.align > RUST_DERIVE_IN_ARRAY_LIMIT;
667 if !self.derive_trait.can_derive_large_array(self.ctx) &&
668 ty.layout(self.ctx).is_some_and(is_reached_limit)
669 {
670 // We have to be conservative: the struct *could* have enough
671 // padding that we emit an array that is longer than
672 // `RUST_DERIVE_IN_ARRAY_LIMIT`. If we moved padding calculations
673 // into the IR and computed them before this analysis, then we could
674 // be precise rather than conservative here.
675 can_derive = CanDerive::Manually;
676 }
677 }
678 can_derive
679 }
680 None => self.constrain_join(item, consider_edge_default),
681 };
682
683 self.insert(id, can_derive)
684 }
685
686 fn each_depending_on<F>(&self, id: ItemId, mut f: F)
687 where
688 F: FnMut(ItemId),
689 {
690 if let Some(edges) = self.dependencies.get(&id) {
691 for item in edges {
692 trace!("enqueue {item:?} into worklist");
693 f(*item);
694 }
695 }
696 }
697}
698
699impl<'ctx> From<CannotDerive<'ctx>> for HashMap<ItemId, CanDerive> {
700 fn from(analysis: CannotDerive<'ctx>) -> Self {
701 extra_assert!(analysis
702 .can_derive
703 .values()
704 .all(|v| *v != CanDerive::Yes));
705
706 analysis.can_derive
707 }
708}
709
710/// Convert a `HashMap<ItemId, CanDerive>` into a `HashSet<ItemId>`.
711///
712/// Elements that are not `CanDerive::Yes` are kept in the set, so that it
713/// represents all items that cannot derive.
714pub(crate) fn as_cannot_derive_set(
715 can_derive: HashMap<ItemId, CanDerive>,
716) -> HashSet<ItemId> {
717 can_deriveimpl Iterator
718 .into_iter()
719 .filter_map(|(k: ItemId, v: CanDerive)| if v == CanDerive::Yes { None } else { Some(k) })
720 .collect()
721}
722