proptest_derive/
void.rs

1// Copyright 2018 The proptest developers
2//
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9//! Provides the `IsUninhabited` trait.
10//!
11//! By nature, determining if a type is uninhabited or not given Rust's
12//! turing complete type system is undecidable. Furthermore, we don't even
13//! have access to all the information because we can't inspect type
14//! definitions, type macros, or projections via associated types.
15//!
16//! Any analysis we perform here is therefore incomplete but sound.
17//! That is, if we state that a type is uninhabited, it is so for sure.
18//! But we can't state that all uninhabited types are uninhabited.
19
20use syn::{self, visit};
21
22use crate::interp;
23use crate::util;
24
25//==============================================================================
26// Trait
27//==============================================================================
28
29/// A trait for types for which it is possible to check if the modelled
30/// object is uninhabited or not. A `false` answer means that we can not
31/// tell for sure that the thing is uninhabited, not that we are 100%
32/// certain that it is inhabited.
33pub trait IsUninhabited {
34    /// Returns true if the given type is known to be uninhabited.
35    /// There may be more scenarios under which the type is uninhabited.
36    /// Thus, this is not a complete and exhaustive check.
37    fn is_uninhabited(&self) -> bool;
38}
39
40//==============================================================================
41// Enum/Variants:
42//==============================================================================
43
44impl IsUninhabited for syn::DataEnum {
45    fn is_uninhabited(&self) -> bool {
46        self.variants.is_uninhabited()
47    }
48}
49
50impl<P> IsUninhabited for syn::punctuated::Punctuated<syn::Variant, P> {
51    fn is_uninhabited(&self) -> bool {
52        self.iter().all(IsUninhabited::is_uninhabited)
53    }
54}
55
56impl<'a> IsUninhabited for &'a [syn::Variant] {
57    fn is_uninhabited(&self) -> bool {
58        self.iter().all(IsUninhabited::is_uninhabited)
59    }
60}
61
62impl IsUninhabited for syn::Variant {
63    fn is_uninhabited(&self) -> bool {
64        self.fields.is_uninhabited()
65    }
66}
67
68//==============================================================================
69// Struct/Fields:
70//==============================================================================
71
72impl IsUninhabited for syn::Fields {
73    fn is_uninhabited(&self) -> bool {
74        self.iter().any(syn::Field::is_uninhabited)
75    }
76}
77
78impl<'a> IsUninhabited for &'a [syn::Field] {
79    fn is_uninhabited(&self) -> bool {
80        self.iter().any(syn::Field::is_uninhabited)
81    }
82}
83
84impl IsUninhabited for syn::Field {
85    fn is_uninhabited(&self) -> bool {
86        self.ty.is_uninhabited()
87    }
88}
89
90//==============================================================================
91// Types:
92//==============================================================================
93
94impl IsUninhabited for syn::Type {
95    fn is_uninhabited(&self) -> bool {
96        let mut uninhabited = Uninhabited(false);
97        visit::visit_type(&mut uninhabited, &self);
98        uninhabited.0
99    }
100}
101
102/// Tracks uninhabitedness.
103struct Uninhabited(bool);
104
105impl Uninhabited {
106    /// Set to uninhabited.
107    fn set(&mut self) {
108        self.0 = true;
109    }
110}
111
112// We are more strict than Rust is.
113// Our notion of uninhabited is if the type is generatable or not.
114// The second a type like *const ! is dereferenced you have UB.
115
116impl<'ast> visit::Visit<'ast> for Uninhabited {
117    //------------------------------------------------------------------
118    // If we get to one of these we have a knowably uninhabited type:
119    //------------------------------------------------------------------
120
121    // The ! (never) type is obviously uninhabited:
122    fn visit_type_never(&mut self, _: &'ast syn::TypeNever) {
123        self.set();
124    }
125
126    // A path is uninhabited if we get one we know is uninhabited.
127    // Even if `T` in `<T as Trait>::Item` is uninhabited, the associated item
128    // may be inhabited, so we can't say for sure that it is uninhabited.
129    fn visit_type_path(&mut self, type_path: &'ast syn::TypePath) {
130        const KNOWN_UNINHABITED: &[&str] =
131            &["std::string::ParseError", "::std::string::ParseError"];
132
133        if type_path.qself.is_none()
134            && util::match_pathsegs(&type_path.path, KNOWN_UNINHABITED)
135        {
136            self.set();
137        }
138    }
139
140    // An array is uninhabited iff: `[T; N]` where uninhabited(T) && N != 0
141    // We want to block decent if N == 0.
142    fn visit_type_array(&mut self, arr: &'ast syn::TypeArray) {
143        if let Some(len) = interp::eval_expr(&arr.len) {
144            if len > 0 {
145                self.visit_type(&arr.elem);
146            }
147        }
148    }
149
150    //------------------------------------------------------------------
151    // These are here to block decent:
152    //------------------------------------------------------------------
153
154    // An fn(I) -> O is never uninhabited even if I or O are:
155    fn visit_type_bare_fn(&mut self, _: &'ast syn::TypeBareFn) {}
156
157    // A macro may transform the inner type in ways we can't predict:
158    fn visit_macro(&mut self, _: &'ast syn::Macro) {}
159
160    // Both of these could be, but type is anonymous:
161    fn visit_type_impl_trait(&mut self, _: &'ast syn::TypeImplTrait) {}
162    fn visit_type_trait_object(&mut self, _: &'ast syn::TypeTraitObject) {}
163}
proptest_derive/void.rs

proptest_derive/
void.rs
