proptest_derive/
void.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
// Copyright 2018 The proptest developers
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! Provides the `IsUninhabited` trait.
//!
//! By nature, determining if a type is uninhabited or not given Rust's
//! turing complete type system is undecidable. Furthermore, we don't even
//! have access to all the information because we can't inspect type
//! definitions, type macros, or projections via associated types.
//!
//! Any analysis we perform here is therefore incomplete but sound.
//! That is, if we state that a type is uninhabited, it is so for sure.
//! But we can't state that all uninhabited types are uninhabited.

use syn::{self, visit};

use crate::interp;
use crate::util;

//==============================================================================
// Trait
//==============================================================================

/// A trait for types for which it is possible to check if the modelled
/// object is uninhabited or not. A `false` answer means that we can not
/// tell for sure that the thing is uninhabited, not that we are 100%
/// certain that it is inhabited.
pub trait IsUninhabited {
    /// Returns true if the given type is known to be uninhabited.
    /// There may be more scenarios under which the type is uninhabited.
    /// Thus, this is not a complete and exhaustive check.
    fn is_uninhabited(&self) -> bool;
}

//==============================================================================
// Enum/Variants:
//==============================================================================

impl IsUninhabited for syn::DataEnum {
    fn is_uninhabited(&self) -> bool {
        self.variants.is_uninhabited()
    }
}

impl<P> IsUninhabited for syn::punctuated::Punctuated<syn::Variant, P> {
    fn is_uninhabited(&self) -> bool {
        self.iter().all(IsUninhabited::is_uninhabited)
    }
}

impl<'a> IsUninhabited for &'a [syn::Variant] {
    fn is_uninhabited(&self) -> bool {
        self.iter().all(IsUninhabited::is_uninhabited)
    }
}

impl IsUninhabited for syn::Variant {
    fn is_uninhabited(&self) -> bool {
        self.fields.is_uninhabited()
    }
}

//==============================================================================
// Struct/Fields:
//==============================================================================

impl IsUninhabited for syn::Fields {
    fn is_uninhabited(&self) -> bool {
        self.iter().any(syn::Field::is_uninhabited)
    }
}

impl<'a> IsUninhabited for &'a [syn::Field] {
    fn is_uninhabited(&self) -> bool {
        self.iter().any(syn::Field::is_uninhabited)
    }
}

impl IsUninhabited for syn::Field {
    fn is_uninhabited(&self) -> bool {
        self.ty.is_uninhabited()
    }
}

//==============================================================================
// Types:
//==============================================================================

impl IsUninhabited for syn::Type {
    fn is_uninhabited(&self) -> bool {
        let mut uninhabited = Uninhabited(false);
        visit::visit_type(&mut uninhabited, &self);
        uninhabited.0
    }
}

/// Tracks uninhabitedness.
struct Uninhabited(bool);

impl Uninhabited {
    /// Set to uninhabited.
    fn set(&mut self) {
        self.0 = true;
    }
}

// We are more strict than Rust is.
// Our notion of uninhabited is if the type is generatable or not.
// The second a type like *const ! is dereferenced you have UB.

impl<'ast> visit::Visit<'ast> for Uninhabited {
    //------------------------------------------------------------------
    // If we get to one of these we have a knowably uninhabited type:
    //------------------------------------------------------------------

    // The ! (never) type is obviously uninhabited:
    fn visit_type_never(&mut self, _: &'ast syn::TypeNever) {
        self.set();
    }

    // A path is uninhabited if we get one we know is uninhabited.
    // Even if `T` in `<T as Trait>::Item` is uninhabited, the associated item
    // may be inhabited, so we can't say for sure that it is uninhabited.
    fn visit_type_path(&mut self, type_path: &'ast syn::TypePath) {
        const KNOWN_UNINHABITED: &[&str] =
            &["std::string::ParseError", "::std::string::ParseError"];

        if type_path.qself.is_none()
            && util::match_pathsegs(&type_path.path, KNOWN_UNINHABITED)
        {
            self.set();
        }
    }

    // An array is uninhabited iff: `[T; N]` where uninhabited(T) && N != 0
    // We want to block decent if N == 0.
    fn visit_type_array(&mut self, arr: &'ast syn::TypeArray) {
        if let Some(len) = interp::eval_expr(&arr.len) {
            if len > 0 {
                self.visit_type(&arr.elem);
            }
        }
    }

    //------------------------------------------------------------------
    // These are here to block decent:
    //------------------------------------------------------------------

    // An fn(I) -> O is never uninhabited even if I or O are:
    fn visit_type_bare_fn(&mut self, _: &'ast syn::TypeBareFn) {}

    // A macro may transform the inner type in ways we can't predict:
    fn visit_macro(&mut self, _: &'ast syn::Macro) {}

    // Both of these could be, but type is anonymous:
    fn visit_type_impl_trait(&mut self, _: &'ast syn::TypeImplTrait) {}
    fn visit_type_trait_object(&mut self, _: &'ast syn::TypeTraitObject) {}
}