PCG Hyperedges

A PCG Hyperedge is a directed edge of the form $\overline{n_{s}} \to \overline{n_{t}}$ , where elements of $\overline{n_{s}}$ and $\overline{n_{t}}$ are PCG nodes. The set $\overline{n_{s}}$ are referred to as the source nodes of the edge, and $\overline{n_{t}}$ are the target nodes. Hyperedges in the PCG are labelled with validity conditions¹.

We represent a PCG hyperedge as a tuple of an edge kind and validity conditions.

Edge Kinds

An edge kind is a description an edge, including its source and target nodes, as well as other associated metadata. The metadata is described by the type of the edge, the various types are presented below:

Unpack Edges

Unpack edges are used to represent the unpack of an owned place in order to access one of its fields. For example, writing to a field x.f requires expanding x.

An unpack edge connects an owned place $p$ to one of it's expansions $\overline{p}$ . Each place in $\overline{p}$ is guaranteed to be owned.

For example, if x is an owned place with fields x.f and x.g, the edge {x} -> {x.f, x.g} is a valid unpack edge.

Unpack edges are not generated for dereferences of reference-typed places. Borrow PCG Expansion Edges are used in such cases. Unpack edges are used in derefences of Box-typed places.

In the implementation, we don't have an explicit data type representing unpack edges. Rather, the unpack edges are conceptually represented as the interior edges in the Owned PCG.

Validity conditions are not currently associated with unpack edges in the implementation.

Borrow PCG Expansion Edge

Borrow PCG Expansion Edges conceptually take one of three forms:

Dereference Expansion: The dereference of a reference-typed place
Place Expansion: The expansion of a borrowed place to access one of its fields
Lifetime Projection Expansion: The expansion of the lifetime projections of an owned or borrowed place

Dereference Expansion

The source nodes of a dereference expansion consist of:

A maybe-labelled place $p_{s}$ , and:
A lifetime projection $rp_{s}$

Where $p_{s}$ and $rp_{s}$ have the same associated place $p_{s}$ .

The target node $p_{t}$ of a dereference expansion is a maybe-labelled place with associated place $* p_{s}$ .

Place Expansion

The source node of a place expansion is a maybe-labelled place $p_{s}$ with associated place $p_{s}$ , where $p_{s}$ is a borrowed place and $p_{s}$ is not a reference.

The target nodes of a place expansion is a set of maybe-labelled places $\overline{p_{t}}$ where the associated places of $\overline{p_{t}}$ are an expansion of $p_{s}$ .

Lifetime Projection Expansion

The source node of a lifetime projection expansion is a lifetime projection $rp_{s}$ where $base (rp_{s})$ is a maybe-labelled place $p_{s}$ with associated place of $p_{s}$ .

The target nodes of a lifetime projection expansion is a set of lifetime projections $\overline{rp_{t}}$ where the base of each place is a maybe-labelled place. The associated places of the bases of $\overline{rp_{t}}$ are an expansion of $p_{s}$ .

It might make sense to differentiate lifetime projection expansions of owned and borrowed places, since they differ in terms of how placeholder labels should be included. Namely, for owned places there is no need to connect the expansion nodes to the placeholder of the base node (the owned place may never be repacked, or could be repacked with entirely unrelated lifetime projections)

Borrow Edges

Borrow edges are used to represent direct borrows in the program. We define two types:

Local Borrow Edges: A borrow created in the MIR Body, e.g. from a statement let y = &mut x;
Remote Borrow Edges: A borrow created by the caller of this function where the assigned place of the borrow is an input to this function.

Remote Borrows are named as such because (unlike local borrows), the borrowed place does not have a name in the MIR body (since it was created by the caller).

Local Borrows

The source node of a local borrow is a maybe-labelled place $p$ . The target node of a local borrow is a lifetime projection $rp$ where $base (rp)$ is a maybe-labelled place.

Remote Borrows

The source node of a remote borrow is a remote place $remote (v)$ . The target node of a remote borrow is a lifetime projection $rp$ where $base (rp)$ is a maybe-labelled place.

Abstraction Edge

An abstraction edge represents the flow of borrows introduced due to a function call or loop.

Function Call Abstraction Edge

The source node of a function call abstraction edge is a lifetime projection $rp$ where $base (rp)$ is a maybe-labelled place.

The target node of a function call abstraction edge is a lifetime projection $rp$ where $base (rp)$ is a maybe-labelled place.

Loop Abstraction Edge

The source node of a loop abstraction edge is a PCG node.

The target node of a loop abstraction edge is a local PCG node.

Borrow-Flow Edge

A borrow-flow edge represents the flow of borrows between a lifetime projection $rp_{s}$ and a local lifetime projection $rp_{t}$ . This edge is used when the relationship between the blocked and target node is known concretely, but does not correspond to an expansion or a borrow.

Borrow-Flow Edges are labelled with a Borrow-Flow Edge Kind with associated metadata, enumerated as follows:

Aggregate

Metadata:

$i_{f}$ : Field Index
$i_{rp}$ : Lifetime Projection Index

An aggregate kind is used for borrows flowing into an aggregate type (i.e. struct, tuple). The metadata indicates that the blocked lifetime projection flows into the $i_{rp}^{t h}$ lifetime projection of the $i_{f}^{t h}$ field of the blocking lifetime projection.

Introduced in the following two cases:

Collapsing an owned place:
- edges flow from the lifetime projections of the labelled places of the base to the lifetime projections of the current base
Assigning an aggregate (e.g. x = Aggregate(a, b)):
- edges flow from the lifetime projections of the labelled places in the rvalue to the lifetime projections of x

$i_{rp}$ is probably not necessary. We probably don't even need $i_{f}$ for case 1 (field index can be inferred from the expansion place), so perhaps a different edge kind could be used in that case.

Reference to Constant

Connects a region projection from a constant to some PCG node. For example let x: &'x C = c; where c is a constant of type &'c C, then an edge {c↓'c} -> {x↓'x} of this kind is created. This is called ConstRef in the implementation.

This seems quite similar to "Borrow Outlives", perhaps we should merge them?

Borrow Outlives

For a borrow e.g. let x: &mut y;, the PCG analysis inserts edges of this kind to connect the (potentially snapshotted) lifetime projections of y to the lifetime projections of x.

Initial Borrows

To construct the initial PCG state, the PCG analysis adds an edge of this kind between every lifetime projection in each remote place to the corresponding lifetime projection of its corresponding argument.

For example, if $v$ is the local corresponding to a function argument and contains a lifetime projection $v ↓ r$ , an edge ${remote (v) ↓ r} \to {v ↓ r}$ will appear in the graph.

Connects the lifetime projections of remote places to the lifetime projections of

Currently not in the owned portion of the PCG, but this should happen eventually. ↩

PCG Documentation