Join Operation

The join algorithm on PCGs takes as input PCGs $\mathcal{G}$ and ${\mathcal{G}}^{\prime }$ and mutates $\mathcal{G}$ to join in ${\mathcal{G}}^{\prime }$.

The algorithm proceeds in the follow steps:

1. The Owned PCG of ${\mathcal{G}}^{\prime }$ is joined into the Owned PCG of $\mathcal{G}$ (this may also change the capabilities of $\mathcal{G}$)
2. The capabilities of ${\mathcal{G}}^{\prime }$ are joined into the capabilities of $\mathcal{G}$.
3. The Borrow State of ${\mathcal{G}}^{\prime }$ is joined into the Borrow State of $\mathcal{G}$

We now describe each step in detail:

Owned PCG Join

Let $\mathcal{O}$ be the owned PCG of $\mathcal{G}$ and ${\mathcal{O}}^{\prime }$ the PCG of ${\mathcal{G}}^{\prime }$.

1. For each local $v$ in the MIR body:
   1. If $v$ is allocated in both $\mathcal{O}$ and ${\mathcal{O}}^{\prime }$:
      1. Join the place expansions rooted at ${\mathcal{O}}^{\prime }[v]$ into $\mathcal{O}[v]$
   2. Otherwise, if $v$ is allocated in $\mathcal{O}$, it should be deallocated in $\mathcal{O}$

Joining Local Expansions (Algorithm Overview)

The algorithm for joining local expansions also involves modifying capabilities (including to borrowed places), and also may cause some places to be labelled. We "emulate" a modification of the block to be joined in, so that we can use the resulting modified capabilities and borrows graph in the remainder of the join. We implement the join by defining a "one-way" join operation ${\bigsqcup }^{\leftarrow }$, and then performing a join $(\mathcal{G},{\mathcal{G}}^{\prime })\leftarrow \mathcal{G}{\bigsqcup }^{\leftarrow }{\mathcal{G}}^{\prime }$ and subsequently $({\mathcal{G}}^{\prime },\mathcal{G})\to {\mathcal{G}}^{\prime }{\bigsqcup }^{\leftarrow }\mathcal{G}$. The owned PCGs of $\mathcal{G}$ and ${\mathcal{G}}^{\prime }$ (including the associated capabilities) should be the same after the join. Formally, we could imagine a partial order ${<}_{\mathcal{O}}$ where ${\mathcal{G}}_1{<}_{\mathcal{G}}{\mathcal{G}}_2$ iff the owned PCG of ${\mathcal{G}}_1$ can be transformed to the owned PCG of ${\mathcal{G}}_2$ by a sequence of repack operations on its owned PCG. The join identifies the maximum graph ${\mathcal{G}}^{\prime }$ (w.r.t ${<}_{\mathcal{O}}$) where ${\mathcal{G}}^{\prime }{<}_{\mathcal{O}}{\mathcal{G}}_1$ and ${\mathcal{G}}^{\prime }{<}_{\mathcal{O}}{\mathcal{G}}_2$.

Before we present the full algorithm (that takes into account borrows), we first describe a version that would work in the absence of borrows and therefore only considers capabilities W and E. The key point of the join is that all places/capabilities in the resulting joined PCGs should be obtainable from the originals (i.e. via a sequence of PCG repacks). The join starts from the root of both trees, and navigate downwards. For expansions that are the same in both, nothing needs to happen. If the other tree is expanded more than us, we continue expanding ours: the only reason it would be expanded is that part of it is moved out, so we can expand and weaken the LHS to match the RHS. For example, if the LHS is {x: E}, and the RHS is {x.f: E, x.g: W}, we'd want to expand x in the LHS (note that the subsequent capability join will properly account for capabilities).

If we're at a place where the expansions differ in both trees (e.g. x -> {x@Some} vs x -> {x@None}), we collapse both to the place (e.g x) and set capability to the place to W. Neither of the expansion places are accessible by both, so the "most" capability we could obtain is the W permission to the base.

More formally, we define the one-way join $joi{n}_{\leftarrow }(\mathcal{G},{\mathcal{G}}^{\prime })$ as the traversal where:

1. If we're at a leaf $p$ in $\mathcal{G}$ that is not a leaf in ${\mathcal{G}}^{\prime }$ (having children $\overline{p}$), then:
   1. Expand $p$ to $\overline{p}$ in $\mathcal{G}$
2. If were at a node $p$ in $\mathcal{G}$ where the expansion $e$ is not the same as the expansion $e^{\prime }$ in ${\mathcal{G}}^{\prime }$:
   1. Collapse both $\mathcal{G}$ and ${\mathcal{G}}^{\prime }$ to $p$ for capability $W$

Now, we extend the join to work with borrows and the read capability $R$. Borrows complicate the story because it enables mutually exclusive (at runtime) places to appear in the PCG. For example:

#![allow(unused)]
fn main() {
fn f(x: Either<String, String>) -> &String; {
    let result = match x {
        Left(l) => &l,
        Right(r) => &r
    };
    result
}
}

After the assignment, we should have $R$ capability to both x@Left and x@Right because they are borrowed into result. In the case of exclusive borrows, such places would not have capability but still present in the owned PCG (again, to reflect the target of result). Therefore, the collapse and expand rule previously shown are no longer sufficient.

1. If we're at a place $p$ that's a leaf in both $\mathcal{G}$ and ${\mathcal{G}}^{\prime }$:
   1. If $p$ has capability of at least $R$ in $\mathcal{G}$ and has capability exactly $R$ in ${\mathcal{G}}^{\prime }$:
      1. Then, after the join, the place $p$ can have at most capability $R$. Its also possible that we can now have incompatible different owned expansions of $p$ in the joined PCG, that have been borrowed under mutually exclusive paths.

Local Expansions Join: $joi{n}_{\mathcal{E}}$

The algorithm $joi{n}_{\mathcal{E}}(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$ joins a set of place expansions ${\mathcal{E}}^{\prime }$ into a set of place expansions $\mathcal{E}$, and makes corresponding changes to borrows $\mathcal{B}$ and capabilities $\mathcal{C}$.

1. If either $\mathcal{E}$ or ${\mathcal{E}}^{\prime }$ have any expansions:
   1. Perform $joi{n}_{\mathcal{E}}^{\leftarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$
   2. Perform $joi{n}_{\mathcal{E}}^{\leftarrow }(⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩,⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩)$
2. Otherwise:
   1. Let $v$ be the local
   2. Perform $joi{n}_v^{\leftarrow }(⟨\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$
   3. Perform $joi{n}_v^{\leftarrow }(⟨{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩,⟨\mathcal{B},\mathcal{C}⟩)$

We define $joi{n}_{\mathcal{E}}^{\leftarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$ as:

1. Let $\overline{p_{collapsed}}=\varnothing$
2. For each expansion $e^{\prime }\in {\mathcal{E}}^{\prime }$ (shortest first):
   1. Let $p^{\prime }$ be the base of $e^{\prime }$
   2. If there exists a $p\in \overline{p_{collapsed}}$ where $p$ is a prefix of $p^{\prime }$, then ignore this expansion
   3. Otherwise, let $\overline{e}$ by the set of (direct) expansions from $e^{\prime }$ in $\mathcal{E}$
   4. If $e^{\prime }\in \overline{e}$:
      1. Perform $joi{n}_{e^{\prime }}^{\leftarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$
   5. Otherwise, if $\overline{e}$ is empty and $\mathcal{C}[p^{\prime }]=c$:
      1. If ${\mathcal{C}}^{\prime }[p^{\prime }]=c^{\prime }$:
         1. Perform $expan{d}^{\leftarrow }(e^{\prime },⟨c,\mathcal{B},\mathcal{C}⟩,⟨c^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$
      2. Otherwise, perform a normal expansion operation of $e^{\prime }$ in $\mathcal{E}$
   6. Otherwise, perform $joi{n}_{e^{\prime }}^{\leftrightarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$
      1. If the result of the join is to collapse to $p^{\prime }$, then add $p^{\prime }$ to $\overline{p_{collapsed}}$

We define $expan{d}^{\leftarrow }(e,⟨c,\mathcal{B},\mathcal{C}⟩,⟨c^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$ as:

1. If $c\bigsqcup c^{\prime }=c^{\prime \prime }$
   1. Add expansion $e$ to $\mathcal{E}$
   2. Perform $joi{n}_{e^{\prime }}^{\leftarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$
2. Otherwise, if $c=R$:
   1. Let $p$ be the base of $e$
   2. Perform $joi{n}_{p_{RW}}^{\leftarrow }(p,\mathcal{B},\mathcal{C})$
3. Otherwise do nothing

Expansion Edge One-Way Join $joi{n}_e^{\leftarrow }$

We define $joi{n}_e^{\leftarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$ as:

1. For each place $p$ in the expansion of $e$:
   1. Perform $joi{n}_p^{\leftarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$

Expansion Edge Two-Way Join $joi{n}_e^{\leftrightarrow }$

We define $joi{n}_e^{\leftrightarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$ as:

1. Let $p$ be the base of $e$
2. If $\mathcal{C}[p]=R$ and ${\mathcal{C}}^{\prime }[p]=R$:
   1. Perform a regular expand of $e$
3. Otherwise, if there exists a descendant of $p$ in ${\mathcal{E}}^{\prime }$ that does not have a capability:
   1. Insert $e$ into $\mathcal{E}$ (do not change capabilities)
4. Otherwise:
   1. Collapse $\mathcal{E},\mathcal{C}$ and ${\mathcal{E}}^{\prime },{\mathcal{C}}^{\prime }$ to $p$

Place Join $joi{n}_p^{\leftarrow }$

We define $joi{n}_p^{\leftarrow }(⟨\mathcal{E},\mathcal{B},\mathcal{C}⟩,⟨{\mathcal{E}}^{\prime },{\mathcal{B}}^{\prime },{\mathcal{C}}^{\prime }⟩)$ as:

1. If $p$ is not a leaf in $\mathcal{E}$ or $p$ is not a leaf in ${\mathcal{E}}^{\prime }$ or $p\notin \mathcal{C}$ or $p\notin {\mathcal{C}}^{\prime }$:
   1. Abort
2. Otherwise, let $c=\mathcal{C}[p]$, $c^{\prime }={\mathcal{C}}^{\prime }[p]$
3. If $c⩾R$ and $c^{\prime }=R$:
   1. Perform $cop{y}_R^{\leftarrow }(p,C,C^{\prime })$
4. If $c=R$ and $c^{\prime }=W$:
   1. Perform $joi{n}_{p_{RW}}^{\leftarrow }(p,\mathcal{B},\mathcal{C})$
5. If $c=E$ and $c^{\prime }=W$:
   1. Perform $cop{y}^{\leftarrow }(p.+,C,C^{\prime })$

Leaf RW Join $joi{n}_{p_{RW}}^{\leftarrow }$

We define $joi{n}_{p_{RW}}^{\leftarrow }(p,\mathcal{B},\mathcal{C})$ as:

1. Label all postfixes places of $p$ in $\mathcal{B}$
2. $\mathcal{C}[p]=W$

Place Capabilitiies Join

The algorithm join($\mathcal{C},{\mathcal{C}}^{\prime }$) is defined as:

1. For each p: c in $\mathcal{C}$:
   1. If $p\notin {\mathcal{C}}^{\prime }$:
      1. Remove capability to $p$ in $\mathcal{C}$
   2. Otherwise:
      1. If $min(c,{\mathcal{C}}^{\prime }[p])$ is defined:
         1. Assign capability $min(c,{\mathcal{C}}^{\prime }[p])$ to $p$ in $\mathcal{C}$
      2. Otherwise, remove capability to $p$ in $\mathcal{C}$

Borrow State Join

1. The borrow graphs are joined
2. The validity conditions are joined

Borrow PCG Join

Joining ${\mathcal{B}}^{\prime }$ into $\mathcal{B}$, where $b$ is the block for $\mathcal{B}$ and $b^{\prime }$ is the block for ${\mathcal{B}}^{\prime }$.

Update the validity conditions for each edge $e$ in ${\mathcal{B}}^{\prime }$ to require the branch condition $b^{\prime }\to b$.

Update the validity

1. If $b$ is a loop head perform the loop join algorithm as described here.
2. Otherwise:
   1. For each edge $e^{\prime }$ in ${\mathcal{B}}^{\prime }$:
      1. If there exists an edge $e$ of the same kind in $\mathcal{B}$
         1. Join the validity conditions associated with $e$ in ${\mathcal{B}}^{\prime }$ to the validity conditions associated with $e$ in $\mathcal{B}$
      2. Otherwise, add $e$ to $\mathcal{B}$
   2. For all placeholder lifetime projections $\hat{p}\downarrow r\text{at}\text{FUTURE}$ in $\mathcal{B}$:
      1. Label all lifetime projection nodes of the form $\hat{p}\downarrow r$ in $\mathcal{B}$ with $\text{FUTURE}$