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