borrow_graph/
references.rs

1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4use crate::{
5    paths::{self, Path},
6    shared::*,
7};
8use std::{
9    cmp::Ordering,
10    collections::{BTreeMap, BTreeSet},
11    fmt,
12    fmt::Debug,
13};
14
15//**************************************************************************************************
16// Definitions
17//**************************************************************************************************
18
19/// Unique identifier for the reference
20#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
21pub struct RefID(pub(crate) usize);
22
23impl RefID {
24    /// Creates a new reference id from the given number
25    pub const fn new(x: usize) -> Self {
26        RefID(x)
27    }
28
29    /// Returns the number representing this reference id.
30    pub fn number(&self) -> usize {
31        self.0
32    }
33}
34
35/// An edge in the borrow graph
36#[derive(Clone)]
37pub(crate) struct BorrowEdge<Loc: Copy, Lbl: Clone + Ord> {
38    /// true if it is an exact (strong) edge,
39    /// false if it is a prefix (weak) edge
40    pub(crate) strong: bool,
41    /// The path (either exact/prefix strong/weak) for the borrow relationship of this edge
42    pub(crate) path: Path<Lbl>,
43    /// Location information for the edge
44    pub(crate) loc: Loc,
45}
46
47/// Represents outgoing edges in the borrow graph
48#[derive(Clone, Debug, PartialEq, Eq)]
49pub(crate) struct BorrowEdges<Loc: Copy, Lbl: Clone + Ord>(
50    pub(crate) BTreeMap<RefID, BTreeSet<BorrowEdge<Loc, Lbl>>>,
51);
52
53/// Represents the borrow relationships and information for a node in the borrow graph, i.e
54/// for a single reference
55#[derive(Clone, Debug, PartialEq, Eq)]
56pub(crate) struct Ref<Loc: Copy, Lbl: Clone + Ord> {
57    /// Parent to child
58    /// 'self' is borrowed by _
59    pub(crate) borrowed_by: BorrowEdges<Loc, Lbl>,
60    /// Child to parent
61    /// 'self' borrows from _
62    /// Needed for efficient querying, but should be in one-to-one corespondence with borrowed by
63    /// i.e. x is borrowed by y IFF y borrows from x
64    pub(crate) borrows_from: BTreeSet<RefID>,
65    /// true if mutable, false otherwise
66    pub(crate) mutable: bool,
67}
68
69//**************************************************************************************************
70// Impls
71//**************************************************************************************************
72
73impl<Loc: Copy, Lbl: Clone + Ord> BorrowEdge<Loc, Lbl> {
74    pub(crate) fn leq(&self, other: &Self) -> bool {
75        self == other || (!self.strong && paths::leq(&self.path, &other.path))
76    }
77}
78
79impl<Loc: Copy, Lbl: Clone + Ord> BorrowEdges<Loc, Lbl> {
80    pub(crate) fn new() -> Self {
81        Self(BTreeMap::new())
82    }
83}
84
85impl<Loc: Copy, Lbl: Clone + Ord> Ref<Loc, Lbl> {
86    pub(crate) fn new(mutable: bool) -> Self {
87        let borrowed_by = BorrowEdges::new();
88        let borrows_from = BTreeSet::new();
89        Self {
90            borrowed_by,
91            borrows_from,
92            mutable,
93        }
94    }
95}
96
97//**********************************************************************************************
98// Remap
99//**********************************************************************************************
100
101impl<Loc: Copy, Lbl: Clone + Ord> BorrowEdges<Loc, Lbl> {
102    /// Utility for remapping the reference ids according the `id_map` provided
103    /// If it is not in the map, the id remains the same
104    pub(crate) fn remap_refs(&mut self, id_map: &BTreeMap<RefID, RefID>) {
105        for (old, new) in id_map {
106            if let Some(edges) = self.0.remove(old) {
107                self.0.insert(*new, edges);
108            }
109        }
110    }
111}
112
113impl<Loc: Copy, Lbl: Clone + Ord> Ref<Loc, Lbl> {
114    /// Utility for remapping the reference ids according the `id_map` provided
115    /// If it is not in the map, the id remains the same
116    pub(crate) fn remap_refs(&mut self, id_map: &BTreeMap<RefID, RefID>) {
117        self.borrowed_by.remap_refs(id_map);
118        remap_set(&mut self.borrows_from, id_map)
119    }
120}
121
122//**********************************************************************************************
123// Traits
124//**********************************************************************************************
125
126/// Dummy struct used to implement traits for BorrowEdge that skips over the loc field
127#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
128struct BorrowEdgeNoLoc<'a, Lbl: Clone> {
129    strong: bool,
130    path: &'a Path<Lbl>,
131}
132
133impl<'a, Lbl: Clone + Ord> BorrowEdgeNoLoc<'a, Lbl> {
134    fn new<Loc: Copy>(e: &'a BorrowEdge<Loc, Lbl>) -> Self {
135        BorrowEdgeNoLoc {
136            strong: e.strong,
137            path: &e.path,
138        }
139    }
140}
141
142impl<Loc: Copy, Lbl: Clone + Ord> PartialEq for BorrowEdge<Loc, Lbl> {
143    fn eq(&self, other: &BorrowEdge<Loc, Lbl>) -> bool {
144        BorrowEdgeNoLoc::new(self) == BorrowEdgeNoLoc::new(other)
145    }
146}
147
148impl<Loc: Copy, Lbl: Clone + Ord> Eq for BorrowEdge<Loc, Lbl> {}
149
150impl<Loc: Copy, Lbl: Clone + Ord> PartialOrd for BorrowEdge<Loc, Lbl> {
151    fn partial_cmp(&self, other: &BorrowEdge<Loc, Lbl>) -> Option<Ordering> {
152        BorrowEdgeNoLoc::new(self).partial_cmp(&BorrowEdgeNoLoc::new(other))
153    }
154}
155
156impl<Loc: Copy, Lbl: Clone + Ord> Ord for BorrowEdge<Loc, Lbl> {
157    fn cmp(&self, other: &BorrowEdge<Loc, Lbl>) -> Ordering {
158        BorrowEdgeNoLoc::new(self).cmp(&BorrowEdgeNoLoc::new(other))
159    }
160}
161
162impl<Loc: Copy, Lbl: Clone + Ord + Debug> Debug for BorrowEdge<Loc, Lbl> {
163    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
164        BorrowEdgeNoLoc::new(self).fmt(f)
165    }
166}
borrow_graph/references.rs

borrow_graph/
references.rs
