# `Deref` is not a projection

### Motivation
The MIR uses `Place` to refer to memory locations. A `Place` consists of a base, either a static or a local, and a series of projections starting from that base. With one exception, these projections are merely refinements of the base: they specify a field, an array element, or the portion of memory corresponding to a given enum variant. However, the `Deref` projection is unique in that the target of the `Place` refers to a completely different region of memory than the base. As a result, several analyses must iterate over each place to see whether that place contains a `Deref`.

## The problem

let mut a = (17,13);
let mut b = (99, &mut a);
let x = &mut (*b.1).0;

// Given code above, emitted MIR would be this.

let mut _0: ();
let mut _1: (i32, i32);
let mut _3: &mut (i32, i32);

// ...
_4 = &mut ((*(_2.1: &mut (i32, i32))).0: i32); 
_5 = &mut ((*(_2.1: &mut (i32, i32))).1: i32);

This is the result for a basic case, more complex this gets longer the `Deref` chain becomes, which results more complexity to be solved by MIR analyses.

### Solution
Convert

let x = (*a.b).c

into

let tmp = a.b;
let x = (*tmp).c

### Plan
- Create new mir-opt(derefer) that does the above mentioned convertion
- Pull `derefer`, earlier in the optimization phases
- Create new `Rvalue` for `derefer`
- *everything above has already been done*
- Pull `derefer` before borrowck
- Make it so MIR `Body` is built in a way that the transformation becomes unnecessary
- Remove `ProjectionElem::Deref` entirely.
- add a `deref: bool` field to `Place`, which indicates that the place must be dereferenced before its projections are applied.

### Changes so far
Highlevel overview of work done so far from oldest PR to the newest
- 95649 : Added new mir-opt `deref_separator` that converts `let x = (*a.b).c` into => `tmp = a.b let x= (*tmp).c`
- 95857 : Make `deref_separator` work for nested derefs
- 96116 : By using `visit_place` started working directly on `Places` instead of statements, made major changes to make it work with `Terminator`s.
- 96549 : Pulled `deref_separator` before `add_retag`, to make this work added new field to `LocalInfo`, `DerefTemp`
- 97025 : Added new `MirPhase` `Derefered` Added validation layer for `Derefered`, that validates to see if there is a `ProjectionElem::Deref` after `deref_separator` runs.
- 98145 : Pulled `deref_separator` before `elaborate_drops`, to make it work created new `Rvalue::CopyForDeref` that acts as a differentiator to detect `temp` values created by `deref_separator`.

# Appendix
This is the explanation for main body of `deref_separator`

fn visit_place(&mut self, place: &mut Place<'tcx>,
    cntxt: PlaceContext, loc: Location){
    if !place.projection.is_empty()
        && cntxt != PlaceContext::NonUse(VarDebugInfo)
        && place.projection[1..].contains(&ProjectionElem::Deref)

3. Projections shouldn't be empty...
4. Currently, `Derefer` doesn't work for `VarDebugInfo` so we skip them
5. Since the problem only starts when `Derefer` is not at the start of the projection list, we skip non problematic ones.
---------------

let mut place_local = place.local;
let mut last_len = 0;
let mut last_deref_idx = 0;
let mut prev_temp: Option<Local> = None;
    for (idx, elem) in place.projection[0..].iter().enumerate() {
        if *elem == ProjectionElem::Deref {
            last_deref_idx = idx;
        }
    }

1. We need to have a starting local.
2. We start copying from the beginning so this will start at 0 (this is going to make more sense later)
3. Position of the last `Deref` in the slice of projections.
4. We have to destroy the last temp we created, this is `None` for now
------------

    for (idx, (p_ref, p_elem)) in place.iter_projections().enumerate() {
        if !p_ref.projection.is_empty() && p_elem == ProjectionElem::Deref {
            let ty = p_ref.ty(&self.local_decls, self.tcx).ty;
            let temp = self.patcher.new_local_with_info(
                ty,
                self.local_decls[p_ref.local].source_info.span,
                Some(Box::new(LocalInfo::DerefTemp)),

1. `idx` will be used to compare with `last_deref_idx`
2. We only care for `Deref`
4. `temp` is created with `MirPatch`, it will be used for derefing
7. We mark this as `DerefTemp`, so we can retrieve this information when needed (it will be needed in other mir-opts)
-----

self.patcher.add_statement(loc, StatementKind::StrorageLive(temp));
let deref_place = Place::from(place_local)
.project_deeper(&p_ref.projection[last_len..], self.tcx);               

1. We mark the temp we just created as living
2. These last 2 lines are quite important, I will be explaining it with example code below.

fn main () {
     let mut a = (42, 43);
     let mut b = (99, &mut a);
     let mut c = (11, &mut b);
     let mut d = (13, &mut c);
     let x = &mut (*d.1).1.1.1;
}

Given this code `deref_place` and `last_len` will have these values.

projections[Field(field[1], &mut (i32, &mut (i32, &mut (i32, i32)))]
last_len = 0
// in the next loop
projections[Deref,Field(field[1], &mut (i32, &mut (i32, i32)))]
last_len = 1
// in the last loop
projections[Deref, Field(field[1], &mut (i32, i32))]
last_len = 3

As you can see, we cut away `&` with each loop creating new temp that holds next referenced value.

---

self.patcher.add_assign(loc, Place::From(temp),
    Rvalue::CopyForDeref(deref_place),);
place_local = temp;
last_len = p_ref.projection.len();

2. We assign newly created `deref_place` to our `temp` using, `Rvalue::CopyForDeref` which is basically `Copy` but let's us differentiate it from normal `Copy`, which is used to un-do this whole proccess to bypass `elaborate_drops`.
3. In the next loop `deref_place` will be created from this temps local value.
4. We update last_len as explained above.
----

if idx == last_deref_idx {
    let temp_place = Place::from(temp)
        .project_deeper(&place.projection[idx..], self.tcx);
    *place = temp_place;
}

1. Remember `last_deref_idx` ? this is where we use it.
2. For the example given above temp place's projections are ` Deref,
Field(
field[1],
i32,
),` as you can see final projection is clean, meaning we successfully transformed it from this

`_8 = &mut ((*((*((*(_6.1: &mut (i32, &mut (i32, &mut (i32, i32))))).1: &mut (i32, &mut (i32, i32)))).1: &mut (i32, i32))).1: i32);`
to this `_8 = &mut ((*_12).1: i32); `

3. We swap the original place, with our final value.

---

if let Some(prev_temp) = prev_temp {
    self.patcher.add_statement(loc, StatementKind::StorageDead(prev_temp));
}
prev_temp = Some(temp)

1. Since we have to eliminate previously created temps we do it here
4. Since we are at the end of our loop we assign, temp as `prev_temp` to be destroyed in the next loop.