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
//! From the NLL RFC:
//! "Shallow prefixes are found by stripping away fields, but stop at
//! any dereference. So: writing a path like `a` is illegal if `a.b`
//! is borrowed. But: writing `a` is legal if `*a` is borrowed,
//! whether or not `a` is a shared or mutable reference. [...] "

use super::MirBorrowckCtxt;

use rustc_middle::mir::{PlaceRef, ProjectionElem};

pub trait IsPrefixOf<'tcx> {
    fn is_prefix_of(&self, other: PlaceRef<'tcx>) -> bool;
}

impl<'tcx> IsPrefixOf<'tcx> for PlaceRef<'tcx> {
    fn is_prefix_of(&self, other: PlaceRef<'tcx>) -> bool {
        self.local == other.local
            && self.projection.len() <= other.projection.len()
            && self.projection == &other.projection[..self.projection.len()]
    }
}

pub(super) struct Prefixes<'tcx> {
    kind: PrefixSet,
    next: Option<PlaceRef<'tcx>>,
}

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub(super) enum PrefixSet {
    /// Doesn't stop until it returns the base case (a Local or
    /// Static prefix).
    All,
    /// Stops at any dereference.
    Shallow,
}

impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
    /// Returns an iterator over the prefixes of `place`
    /// (inclusive) from longest to smallest, potentially
    /// terminating the iteration early based on `kind`.
    pub(super) fn prefixes(&self, place_ref: PlaceRef<'tcx>, kind: PrefixSet) -> Prefixes<'tcx> {
        Prefixes { next: Some(place_ref), kind }
    }
}

impl<'tcx> Iterator for Prefixes<'tcx> {
    type Item = PlaceRef<'tcx>;
    fn next(&mut self) -> Option<Self::Item> {
        let mut cursor = self.next?;

        // Post-processing `place`: Enqueue any remaining
        // work. Also, `place` may not be a prefix itself, but
        // may hold one further down (e.g., we never return
        // downcasts here, but may return a base of a downcast).

        'cursor: loop {
            match cursor.last_projection() {
                None => {
                    self.next = None;
                    return Some(cursor);
                }
                Some((cursor_base, elem)) => {
                    match elem {
                        ProjectionElem::Field(_ /*field*/, _ /*ty*/) => {
                            // FIXME: add union handling
                            self.next = Some(cursor_base);
                            return Some(cursor);
                        }
                        ProjectionElem::Downcast(..)
                        | ProjectionElem::Subslice { .. }
                        | ProjectionElem::OpaqueCast { .. }
                        | ProjectionElem::ConstantIndex { .. }
                        | ProjectionElem::Index(_) => {
                            cursor = cursor_base;
                            continue 'cursor;
                        }
                        ProjectionElem::Subtype(..) => {
                            panic!("Subtype projection is not allowed before borrow check")
                        }
                        ProjectionElem::Deref => {
                            match self.kind {
                                PrefixSet::Shallow => {
                                    // Shallow prefixes are found by stripping away
                                    // fields, but stop at *any* dereference.
                                    // So we can just stop the traversal now.
                                    self.next = None;
                                    return Some(cursor);
                                }
                                PrefixSet::All => {
                                    // All prefixes: just blindly enqueue the base
                                    // of the projection.
                                    self.next = Some(cursor_base);
                                    return Some(cursor);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}