private void init(final ASTNode child) {
    if (child == null) {
        return;
    }
    ASTNode treePrev = child.getTreePrev();
    while (treePrev != null && SpacingUtil.isWhiteSpace(treePrev)) {
        treePrev = treePrev.getTreePrev();
    }

    if (treePrev == null) {
        init(child.getTreeParent());
    } else {
        myChild2 = child;
        myChild1 = treePrev;
        final CompositeElement parent = (CompositeElement) treePrev.getTreeParent();
        myParent = SourceTreeToPsiMap.treeElementToPsi(parent);
    }
}
 

void fireEvent(int parentStart, PsiFile file, CompositeElement parent) {
  PsiTreeChangeEventImpl e = createEvent(file, myOffset + parentStart);

  if (myOldChild == myNewChild && myNewChild != null) {
    childrenChanged(e, myNewChild, myOldLength);
  }
  else if (myOldChild != null && myNewChild != null) {
    childReplaced(e, myOldChild, myNewChild, parent);
  }
  else if (myOldChild != null) {
    childRemoved(e, myOldChild, parent);
  }
  else if (myNewChild != null) {
    childAdded(e, myNewChild, parent);
  }
}
 

@Nonnull
private String dumpCreationTraces(@Nonnull FileElement fileElement) {
  final StringBuilder traces = new StringBuilder("\nNow " + Thread.currentThread() + "\n");
  traces.append("My creation trace:\n").append(getUserData(CREATION_TRACE));
  traces.append("AST creation traces:\n");
  fileElement.acceptTree(new RecursiveTreeElementWalkingVisitor(false) {
    @Override
    public void visitComposite(CompositeElement composite) {
      PsiElement psi = composite.getPsi();
      if (psi != null) {
        traces.append(psi).append("@").append(System.identityHashCode(psi)).append("\n");
        String trace = psi.getUserData(CREATION_TRACE);
        if (trace != null) {
          traces.append(trace).append("\n");
        }
      }
      super.visitComposite(composite);
    }
  });
  return traces.toString();
}
 

private static void bindStubsWithAst(@Nonnull List<PsiElement> srcSpine, List<StubElement<?>> stubList, List<CompositeElement> nodeList, boolean takePsiFromStubs) {
  for (int i = firstNonFilePsiIndex; i < stubList.size(); i++) {
    StubElement<?> stub = stubList.get(i);
    CompositeElement node = nodeList.get(i);
    assert stub.getStubType() == node.getElementType() : "Stub type mismatch: " + stub.getStubType() + "!=" + node.getElementType() + " in #" + node.getElementType().getLanguage();

    PsiElement psi = Objects.requireNonNull(srcSpine.get(i));
    if (takePsiFromStubs) {
      node.setPsi(psi);
    }
    else {
      //noinspection unchecked
      ((StubBase)stub).setPsi(psi);
    }
  }
}
 

public static void visitRecursively(PsiElement element, BashVisitor visitor) {
    element.accept(visitor);

    // calling element.getChildren() is expensive,
    // better iterate over the chilren
    PsiElement child = element.getFirstChild();
    while (child != null) {
        if (child.getNode() instanceof CompositeElement) {
            visitRecursively(child, visitor);
        }

        child = child.getNextSibling();
    }
}
 

/** Create a FileElement for root or a parse tree CompositeElement (not
*  PSI) for the token. This impl is more or less the default.
*/
  @Override
  public CompositeElement createComposite(IElementType type) {
      if (type instanceof IFileElementType) {
          return new FileElement(type, null);
}
      return new CompositeElement(type);
  }
 

@Nonnull
@Override
public CompositeElement createComposite(@Nonnull IElementType type) {
  if (type instanceof IFileElementType) {
    return new FileElement(type, null);
  }
  if (type instanceof ICompositeElementType) {
    return (CompositeElement)((ICompositeElementType)type).createCompositeNode();
  }
  return new CompositeElement(type);
}
 

public TreeChangeImpl(@Nonnull CompositeElement parent) {
  myParent = parent;
  assert myParent.getPsi() != null : myParent.getElementType() + " of " + myParent.getClass();
  mySuperParents = JBIterable.generate(parent.getTreeParent(), TreeElement::getTreeParent).toList();
  for (TreeElement child : getCurrentChildren()) {
    myInitialLengths.put(child, child.getTextLength());
  }
}
 

@Override
public int compareTo(@Nonnull TreeChangeImpl o) {
  List<CompositeElement> thisParents = ContainerUtil.reverse(getSuperParents());
  List<CompositeElement> thatParents = ContainerUtil.reverse(o.getSuperParents());
  for (int i = 1; i <= thisParents.size() && i <= thatParents.size(); i++) {
    CompositeElement thisParent = i < thisParents.size() ? thisParents.get(i) : myParent;
    CompositeElement thatParent = i < thatParents.size() ? thatParents.get(i) : o.myParent;
    int result = compareNodePositions(thisParent, thatParent);
    if (result != 0) return result;
  }
  return 0;
}
 

private static int compareNodePositions(CompositeElement node1, CompositeElement node2) {
  if (node1 == node2) return 0;

  int o1 = node1.getStartOffsetInParent();
  int o2 = node2.getStartOffsetInParent();
  return o1 != o2 ? Integer.compare(o1, o2) : Integer.compare(getChildIndex(node1), getChildIndex(node2));
}
 

public void addElementaryChange(@Nonnull CompositeElement parent) {
  TreeChangeImpl existing = myChangedElements.get(parent);
  if (existing != null) {
    existing.clearCache();
  }
  else if (!integrateIntoExistingChanges(parent)) {
    mergeChange(new TreeChangeImpl(parent));
  }
}
 

private boolean integrateIntoExistingChanges(CompositeElement nextParent) {
  for (CompositeElement eachParent : JBIterable.generate(nextParent, TreeElement::getTreeParent)) {
    CompositeElement superParent = eachParent.getTreeParent();
    TreeChangeImpl superChange = myChangedElements.get(superParent);
    if (superChange != null) {
      superChange.markChildChanged(eachParent, 0);
      return true;
    }
  }
  return false;
}
 

private void mergeChange(TreeChangeImpl nextChange) {
  CompositeElement newParent = nextChange.getChangedParent();

  for (TreeChangeImpl descendant : new ArrayList<>(myChangesByAllParents.get(newParent))) {
    TreeElement ancestorChild = findAncestorChild(newParent, descendant);
    if (ancestorChild != null) {
      nextChange.markChildChanged(ancestorChild, descendant.getLengthDelta());
    }

    unregisterChange(descendant);
  }

  registerChange(nextChange);
}
 

/**
 * @return a direct child of {@code ancestor} which contains {@code change}
 */
@Nullable
private static TreeElement findAncestorChild(@Nonnull CompositeElement ancestor, @Nonnull TreeChangeImpl change) {
  List<CompositeElement> superParents = change.getSuperParents();
  int index = superParents.indexOf(ancestor);
  return index < 0 ? null : index == 0 ? change.getChangedParent() : superParents.get(index - 1);
}
 

private void childReplaced(PsiTreeChangeEventImpl e, TreeElement oldChild, TreeElement newChild, CompositeElement parent) {
  e.setParent(parent.getPsi());
  e.setOldChild(oldChild.getPsi());
  e.setChild(newChild.getPsi());
  e.setNewChild(newChild.getPsi());
  e.setOldLength(myOldLength);
  getPsiManagerImpl(e).childReplaced(e);
}
 

private ReplaceElementWithEvents(@Nonnull CompositeElement oldRoot, @Nonnull CompositeElement newRoot) {
  myOldRoot = oldRoot;
  myNewRoot = newRoot;
  // parse in background to reduce time spent in EDT and to ensure the newRoot light containing file is still valid
  TreeUtil.ensureParsed(myOldRoot.getFirstChildNode());
  TreeUtil.ensureParsed(myNewRoot.getFirstChildNode());
}
 

private static void treeToBufferWithUserData(Appendable buffer, PsiElement root, int indent, boolean skipWhiteSpaces) {
  if (skipWhiteSpaces && root instanceof PsiWhiteSpace) return;

  StringUtil.repeatSymbol(buffer, ' ', indent);
  try {
    if (root instanceof CompositeElement) {
      buffer.append(root.toString());
    }
    else {
      final String text = fixWhiteSpaces(root.getText());
      buffer.append(root.toString()).append("('").append(text).append("')");
    }
    buffer.append(((UserDataHolderBase)root).getUserDataString());
    buffer.append("\n");

    PsiElement[] children = root.getChildren();

    for (PsiElement child : children) {
      treeToBufferWithUserData(buffer, child, indent + 2, skipWhiteSpaces);
    }

    if (children.length == 0) {
      StringUtil.repeatSymbol(buffer, ' ', indent + 2);
      buffer.append("<empty list>\n");
    }
  }
  catch (IOException e) {
    LOG.error(e);
  }
}
 

public static void doCheckTreeStructure(@Nullable ASTNode anyElement) {
  if (anyElement == null) return;
  ASTNode root = anyElement;
  while (root.getTreeParent() != null) {
    root = root.getTreeParent();
  }
  if (root instanceof CompositeElement) {
    checkSubtree((CompositeElement)root);
  }
}
 

private static void checkSubtree(CompositeElement root) {
  if (root.rawFirstChild() == null) {
    if (root.rawLastChild() != null) {
      throw new IncorrectTreeStructureException(root, "firstChild == null, but lastChild != null");
    }
  }
  else {
    for (ASTNode child = root.getFirstChildNode(); child != null; child = child.getTreeNext()) {
      if (child instanceof CompositeElement) {
        checkSubtree((CompositeElement)child);
      }
      if (child.getTreeParent() != root) {
        throw new IncorrectTreeStructureException(child, "child has wrong parent value");
      }
      if (child == root.getFirstChildNode()) {
        if (child.getTreePrev() != null) {
          throw new IncorrectTreeStructureException(root, "firstChild.prev != null");
        }
      }
      else {
        if (child.getTreePrev() == null) {
          throw new IncorrectTreeStructureException(child, "not first child has prev == null");
        }
        if (child.getTreePrev().getTreeNext() != child) {
          throw new IncorrectTreeStructureException(child, "element.prev.next != element");
        }
      }
      if (child.getTreeNext() == null) {
        if (root.getLastChildNode() != child) {
          throw new IncorrectTreeStructureException(child, "not last child has next == null");
        }
      }
    }
  }
}
 

private void bindSubstratesToCachedPsi(List<StubElement<?>> stubList, List<CompositeElement> nodeList) {
  assert myRefToPsi != null;
  for (int i = firstNonFilePsiIndex; i < myRefToPsi.length; i++) {
    StubBasedPsiElementBase cachedPsi = SoftReference.dereference(myRefToPsi[i]);
    if (cachedPsi != null) {
      if (stubList != null) {
        //noinspection unchecked
        ((StubBase)stubList.get(i)).setPsi(cachedPsi);
      }
      if (nodeList != null) {
        nodeList.get(i).setPsi(cachedPsi);
      }
    }
  }
}
 

@Override
public void insert(CompositeElement parent, TreeElement anchorBefore, OuterLanguageElement toInsert) {
  if(anchorBefore != null) {
    anchorBefore.rawInsertBeforeMe((TreeElement)toInsert);
  }
  else parent.rawAddChildren((TreeElement)toInsert);
}
 

/** Create an internal parse tree node. FileElement for root or a parse tree CompositeElement (not
 *  PSI) for the token.
 *  The FileElement is a parse tree node, which is converted to a PsiFile
 *  by {@link ParserDefinition#createFile}.
 */
@NotNull
   @Override
   public CompositeElement createComposite(IElementType type) {
    return super.createComposite(type);
   }
 

@Nullable
@Override
public CompositeElement createComposite(IElementType type) {
  return super.createComposite(type);
}
 

@Nonnull
CompositeElement createComposite(@Nonnull IElementType type);
 

List<CompositeElement> getSuperParents() {
  return mySuperParents;
}
 

private static int getChildIndex(CompositeElement e) {
  return ArrayUtil.indexOf(e.getTreeParent().getChildren(null), e);
}
 

@Nonnull
public CompositeElement getChangedParent() {
  return myParent;
}
 

@Override
public TreeChange getChangesByElement(@Nonnull ASTNode element) {
  return myChangedElements.get((CompositeElement)element);
}
 

private void registerChange(TreeChangeImpl nextChange) {
  myChangedElements.put(nextChange.getChangedParent(), nextChange);
  for (CompositeElement eachParent : nextChange.getSuperParents()) {
    myChangesByAllParents.putValue(eachParent, nextChange);
  }
}
 

private void unregisterChange(TreeChangeImpl change) {
  myChangedElements.remove(change.getChangedParent());
  for (CompositeElement superParent : change.getSuperParents()) {
    myChangesByAllParents.remove(superParent, change);
  }
}