# Simplify View Insertion

Currently doing view insertion is complicated as can be seen in [`walkTNodeTree()`](https://github.com/angular/angular/blob/master/packages/core/src/render3/node_manipulation.ts#L73-L196). The reason for the complexity is that finding the node in front of which the insertion should happen is complicated by `<ng-container>`, `<ng-content>` and the fact that `LView` could have no nodes. Let's look at some cases.

Assume that you have these template defined: `simple`, `empty`, `projection`, and `containar`.

<ng-template #last>last</ng-template>
<ng-template #simple>simple</ng-template>
<ng-template #empty></ng-template>
<ng-template #projection><ng-content></ng-content></ng-template>
<ng-template #container><div *ngIf="exp">true</div></ng-template>

<!--#insertAnchor-->

These templates can be inserted in the `insertAnchor`. If we insert `last` than the output would look like this:

<!--#insertAnchor-->
last

The insertion here is easy because originally the container was empty `[]` and therefore the `insertBeforeNode` (DOM) was just `<!--#insertAnchor-->.nextSibling`.

Now let's insert `empty` at position `0`. The resulting HTML should be the same because the `empty` view does not have any DOM nodes. (View is: `[empty, last]`)

<!--#insertAnchor-->
last

New let's insert `projection` at position 0. The resulting HTML is now: (View is: `[projection, empty, view]`)

<!--#insertAnchor-->
SomeProjectedText
last

This operation is hard because we know that we want to insert in front of `empty` , but `empty` has no nodes so we cant do `domNodeAt(empty).nextSibling` to get `insertBeforeNode`. So any insertion will have to look into the first node of `empty` realize that there is nothing there and fall through to looking at the first node of `last`.

Now let's insert `container` at `3` (View is: `[projection, empty, last, container]`)

<!--#insertAnchor-->
SomeProjectedText
last
<!--#container_insertAnchor-->

The above is tricky because we need to find the `insertBeforeNode` at the end of the view. One way to do this is to look at the last `LView`, find it's last node and than call `.nextSbling` on it. However this is complicated by the fact that the `LView` `LContainer`, `Projection`, or an empty `<ng-container>` can have its own flattened structure, which makes the traversal complex.

We can summarize the above as:
1. Inserting at the end of the `LView` requires looking for the end, which is complicated by the fact that the search is recursive.

## Proposal

Let's simplify both of the above assumptions so that we don't have to have a recursive solution and our lookups can be fast.

### Simplify Finding Last `insertBeforeNode`

Looking for the last `insertBeforeNode` is hard. The whole problem could be simplified if we only had an `insertBeforeAnchor` just like we have `insertAfterAnchor`. This would require more DOM nodes which would have a runtime implication. However there is a simple trick we can do to work around it.

The `LContainer` currently stores `insertAfterAnchor`. We could also store `insertBeforeAnchor` which would be initialized on first `LView` insert into the `LContainer`. The initialization would simply be `insertBeforeAnchor = insertAfterAnchor.nextSibling`. Because we would lazy initialize we are saying that whatever the next `RNode` is we will treat as our `insertBeforeNode`
- If `null` than `insertBefore` will become just `appendChild`.
- If defined, than the next node is the `insertBeforeNode`.

### Simplify Locating `insertBeforeNode` in the Middle

It would be ideal if we could have a quick way of locating `insertBeforeNode` if we do inserts in front of existing view. We could look it up using `lView[lView[TView].firstChild.index]` in the case of the `LView`, (This is more complex when projection is taken into account). A simpler way to do this is just to store the first `RNode` along the `LView` in the `LContainer`. Currently `LContainer` has an array of `LView`s. We could have it store `RNode` in even locations and `LView` in odd. By caching the nodes in this way the lookup would be very efficient. (This would pay off even more in case of projections).

Storing of the first element in the array is safe because it is stable. For example if it is `LContaine` than the first element would be the anchor node.

This also works for Projected nodes and nested `LView`s.

NOTE: If we have empty `LView` or projection we simply store null.

## Pseudo Code

With the above changes the lookup of the insertion point becomes trivial. We simply go to the next view and look at its cached `RNode` if `null` than we keep looking until we fall of at the end and just return `lContanier.endAnchor`;

/**
 * @param lContainer
 * @param index location where the inserted node should be.
 */
function getInsertInFrontOfRNodeOfViewInLContainer(
    lContainer: LContainer, 
    index: number
): RNode | null {
  const rLength = lContainer.length;
  for(let rIndex = (index<1) + 2; rLength < rIndex; rIndex += 2) {
    const node = lContainer[rIndexNext];
    if (node !== null) {
      // if we have found an RNode than return it.
      return node;
    }
    // if RNode is null than it is empty LView or Projection
    // just keep looking at the next one.
  }
  // If no more views just return the endAnchor.
  return lContainer.endAnchor;
}

### Projection

If the `LView` being inserted has a projection than we need to return the first element of the projection at that location

## Removal of View

When removing a view it is also necessary to collect all of the DOM nodes in the View. We already have the first element of the view stored in `LContainer`. So when removing the `LView` we should start with the first `RNode` and just keep removing the elements using `.nextSibling` until we hit the `insertBeforeNode` of the next `LView` or `endAnchor` if last view.

## Work Breakdown

### Flattening the `LView`

### Getting first `RNode` of projection

### Internationalization

-------------------------
S T O P - R E A D I N G
-------------------------

## Miško's Notes IGNORE
- we can save the first element of the view, because that one is guaranteed to be stable.
- in case of View it will be the anchor.
- in case of projection it will be the first element of projection
- if view in projection that it is the anchor
- if element that it is the element
- if (empty) than we have null??
- The last element is not stable
- in case of view it is whatever the last element of last view is.
- in case of projection it is the last element
- if view than it is unstable since it would be whatever the element was
- Problem with insert after strategy is that we need an efficient way of finding the tail of the view, which we don't have.
- What about disallowing empty Views? An empty view can just be `<!---->` instead.
- Can we grad the next element of anchor on first insert? I think we can!
- If next element is `LContainer` than next element will be its anchor so OK
- If projection

function getInsertInFrontOfRNodeOfViewInLContainer(
    lContainer: LContainer, 
    index: number
): RNode | null {
  // Each storage takes two locatios hence *2;
  let rIndex = index < 1;
  let rIndexNext = rIndex + 2;
  if (lContainer.length < rIndexNext) {
    // This is the easy case where we just take the next view.
    return lContainer[rIndexNext];
  } else {
    // We don't have the next view
    return lContainer.endAnchor;
  }
}


function getLastRNodeOfView(
    lContainer: LContainer, 
    index: number
): RNode | null {
  const firstRNode = getFirstRNodeOfView(lContainer, index + 1);
  if (firstRNode === null) {
    return search
  }
}

function getFirstRNodeOfView(
    lContainer: LContainer, 
    index: number
): RNode | null {
  // if there is no view at that location return null
  if (lContainer.length <= index) return null;
  // Otherwise retun the first element in the view from cache.
  const firstNode = lContainer[index << 1];
}

### Disallow Empty `LView`

Currently this is supported:

<ng-container *ngIf="true"></ng-container>

This creates an empty view, which complicates our life. We can workaround this simply by saying that each `LView` must have at least one `RNode`. This restriction would not be an issues in most cases. For the pathological case above we can simply force the compiler to generate a view with a single `<!---->` node which would have the same render behavior but would mean that at runtime we would not have to deal with this case.

1. Supporting `LView`'s with no children complicates our mental model.

# Ben's Notes :P

Cases where an `LContainer`'s `insertBeforeNode` information will need to be updated:

- If any view that is a child of a container adds a DOM node in the simple case
- If any projection, that is at the tail end of a view, that is in a container, updates a DOM node
- If a container appends a view (during creation)
- If a container inserts or moves a view (ngForOf)

Keeping records updated may be tricky: If we're storing the last DOM node that exists in a child view in it's parent LContainer, that means that we're going to need to update LContainer all the way down the tree to the root whenever we update the DOM. Areas where we dynamically update the DOM: i18n, projection, and dynamic view insertion/removal (to my knowledge).

We will probably want a set of functions dedicated to updating DOM for an `LView` that would do the work of crawling back up the tree looking for containers to update, and those methods would have to be used in any case where we are updating DOM in a view.

I *think* this would be an idiomatic case of containers within containers within containers:

<div>
  some text
  <div *ngIf="foo">
      more text
      <div *ngIf="bar">
          even more text
          <div *ngIf="baz">
              done
          </div>
      </div>
  </div>
</div>

Which should result in a structure like...

digraph hierarchy {

                nodesep=1.0 // increases the separation between nodes

                node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
                edge [color=Blue, style=dashed] //All the lines look like this

                "root view"->{"text('some text')" "view(ngIf=foo)"}
                "view(ngIf=foo)"->container1
                container1->{"view(ngIf=bar)"}
                "view(ngIf=bar)"->{"text('more text')" container2}
                container2->"view(ngIf=baz)"
                "view(ngIf=baz)"->{"text('even more text')" container3}
                container3->view4
                view4->"text('done')"
}

So as any give `ngIf` binding is updated, we'll be adding and removing whole trees of `LViews`/`LContainers` and `DOM` along with it. Meaning ancestor containers will need to have their "insert before node" records updated.

**Possible functions needed**

- `appendNodeToLView` - (may just modify `appendChild`)responsible for not only appending a DOM node, but potentially crawling over ancestor `LContainer`s an updating DOM insertBefore information. (We'll need to use this everywhere, including places like `elementStart`, `text`, `projection` and `i18n` (et al).)
- `removeNodeFromLView` - responsible for not only removing a DOM node from an `LView`, but potentially crawling over ancestor `LContainer`s and updating their insertBefore information
- `viewContainerRemoveView` (already exists in PR) - will need to remove the view *and* the insert before information
- `viewContainerInsertBefore` (already exists in PR) - will need up insert the view *and* identify the insert before information and add update the position *before* where it was inserted (after the previous). Basically it's going to insert a `position, LView` inbetween the previous `LView` and the position right after it.