pub struct Tree {
pub(super) tag_mapping: UniKeyMap<BorTag>,
pub(super) nodes: UniValMap<Node>,
pub(super) rperms: RangeMap<UniValMap<LocationState>>,
pub(super) root: UniIndex,
}
Expand description
Tree structure with both parents and children since we want to be able to traverse the tree efficiently in both directions.
Fields§
§tag_mapping: UniKeyMap<BorTag>
Mapping from tags to keys. The key obtained can then be used in
any of the UniValMap
relative to this allocation, i.e. both the
nodes
and rperms
of the same Tree
.
The parent-child relationship in Node
is encoded in terms of these same
keys, so traversing the entire tree needs exactly one access to
tag_mapping
.
nodes: UniValMap<Node>
All nodes of this tree.
rperms: RangeMap<UniValMap<LocationState>>
Maps a tag and a location to a perm, with possible lazy initialization.
NOTE: not all tags registered in nodes
are necessarily in all
ranges of rperms
, because rperms
is in part lazily initialized.
Just because nodes.get(key)
is Some(_)
does not mean you can safely
unwrap
any perm.get(key)
.
We do uphold the fact that keys(perms)
is a subset of keys(nodes)
root: UniIndex
The index of the root node.
Implementations§
source§impl<'tcx> Tree
impl<'tcx> Tree
sourcefn nth_parent(&self, tag: BorTag, nth_parent: u8) -> Option<BorTag>
fn nth_parent(&self, tag: BorTag, nth_parent: u8) -> Option<BorTag>
Climb the tree to get the tag of a distant ancestor.
Allows operations on tags that are unreachable by the program
but still exist in the tree. Not guaranteed to perform consistently
if tag-gc=1
.
sourcepub fn give_pointer_debug_name(
&mut self,
tag: BorTag,
nth_parent: u8,
name: &str
) -> InterpResult<'tcx>
pub fn give_pointer_debug_name( &mut self, tag: BorTag, nth_parent: u8, name: &str ) -> InterpResult<'tcx>
Debug helper: assign name to tag.
sourcepub fn is_allocation_of(&self, tag: BorTag) -> bool
pub fn is_allocation_of(&self, tag: BorTag) -> bool
Debug helper: determines if the tree contains a tag.
source§impl<'tcx> Tree
impl<'tcx> Tree
sourcepub fn print_tree(
&self,
protected_tags: &FxHashMap<BorTag, ProtectorKind>,
show_unnamed: bool
) -> InterpResult<'tcx>
pub fn print_tree( &self, protected_tags: &FxHashMap<BorTag, ProtectorKind>, show_unnamed: bool ) -> InterpResult<'tcx>
Display the contents of the tree.
source§impl<'tcx> Tree
impl<'tcx> Tree
sourcepub fn new_child(
&mut self,
parent_tag: BorTag,
new_tag: BorTag,
default_initial_perm: Permission,
reborrow_range: AllocRange,
span: Span
) -> InterpResult<'tcx>
pub fn new_child( &mut self, parent_tag: BorTag, new_tag: BorTag, default_initial_perm: Permission, reborrow_range: AllocRange, span: Span ) -> InterpResult<'tcx>
Insert a new tag in the tree
sourcepub fn dealloc(
&mut self,
tag: BorTag,
access_range: AllocRange,
global: &RefCell<GlobalStateInner>,
span: Span
) -> InterpResult<'tcx>
pub fn dealloc( &mut self, tag: BorTag, access_range: AllocRange, global: &RefCell<GlobalStateInner>, span: Span ) -> InterpResult<'tcx>
Deallocation requires
- a pointer that permits write accesses
- the absence of Strong Protectors anywhere in the allocation
sourcepub fn perform_access(
&mut self,
access_kind: AccessKind,
tag: BorTag,
access_range: AllocRange,
global: &RefCell<GlobalStateInner>,
span: Span,
access_cause: AccessCause
) -> InterpResult<'tcx>
pub fn perform_access( &mut self, access_kind: AccessKind, tag: BorTag, access_range: AllocRange, global: &RefCell<GlobalStateInner>, span: Span, access_cause: AccessCause ) -> InterpResult<'tcx>
Map the per-node and per-location LocationState::perform_access
to each location of access_range
, on every tag of the allocation.
LocationState::perform_access
will take care of raising transition
errors and updating the initialized
status of each location,
this traversal adds to that:
- inserting into the map locations that do not exist yet,
- trimming the traversal,
- recording the history.
source§impl Tree
impl Tree
Integration with the BorTag garbage collector
sourcefn keep_only_needed(&mut self, idx: UniIndex, live: &FxHashSet<BorTag>) -> bool
fn keep_only_needed(&mut self, idx: UniIndex, live: &FxHashSet<BorTag>) -> bool
Traverses the entire tree looking for useless tags. Returns true iff the tag it was called on is still live or has live children, and removes from the tree all tags that have no live children.
NOTE: This leaves in the middle of the tree tags that are unreachable but have reachable children. There is a potential for compacting the tree by reassigning children of dead tags to the nearest live parent, but it must be done with care not to remove UB.
Example: Consider the tree root - parent - child
, with parent: Frozen
and
child: Reserved
. This tree can exist. If we blindly delete parent
and reassign
child
to be a direct child of root
then Writes to child
are now permitted
whereas they were not when parent
was still there.
source§impl<'tcx> Tree
impl<'tcx> Tree
sourcepub fn new_allocation(
id: AllocId,
size: Size,
state: &mut GlobalStateInner,
_kind: MemoryKind<MiriMemoryKind>,
machine: &MiriMachine<'_, 'tcx>
) -> Self
pub fn new_allocation( id: AllocId, size: Size, state: &mut GlobalStateInner, _kind: MemoryKind<MiriMemoryKind>, machine: &MiriMachine<'_, 'tcx> ) -> Self
Create a new allocation, i.e. a new tree
sourcepub fn before_memory_access(
&mut self,
access_kind: AccessKind,
alloc_id: AllocId,
prov: ProvenanceExtra,
range: AllocRange,
machine: &MiriMachine<'_, 'tcx>
) -> InterpResult<'tcx>
pub fn before_memory_access( &mut self, access_kind: AccessKind, alloc_id: AllocId, prov: ProvenanceExtra, range: AllocRange, machine: &MiriMachine<'_, 'tcx> ) -> InterpResult<'tcx>
Check that an access on the entire range is permitted, and update the tree.
sourcepub fn before_memory_deallocation(
&mut self,
_alloc_id: AllocId,
prov: ProvenanceExtra,
range: AllocRange,
machine: &MiriMachine<'_, 'tcx>
) -> InterpResult<'tcx>
pub fn before_memory_deallocation( &mut self, _alloc_id: AllocId, prov: ProvenanceExtra, range: AllocRange, machine: &MiriMachine<'_, 'tcx> ) -> InterpResult<'tcx>
Check that this pointer has permission to deallocate this range.
pub fn expose_tag(&mut self, _tag: BorTag)
Trait Implementations§
Auto Trait Implementations§
impl RefUnwindSafe for Tree
impl !Send for Tree
impl !Sync for Tree
impl Unpin for Tree
impl UnwindSafe for Tree
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Layout§
Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...)
attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.
Size: 112 bytes