// Copyright (c) 2022, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

package com.android.tools.r8.naming;

import static com.android.tools.r8.naming.MappedRangeUtils.isInlineMappedRange;
import static com.android.tools.r8.utils.FunctionUtils.ignoreArgument;

import com.android.tools.r8.naming.ClassNamingForNameMapper.MappedRange;
import com.android.tools.r8.naming.ClassNamingForNameMapper.MappedRangesOfName;
import com.android.tools.r8.naming.MemberNaming.FieldSignature;
import com.android.tools.r8.naming.MemberNaming.MethodSignature;
import com.android.tools.r8.naming.MemberNaming.Signature;
import com.android.tools.r8.naming.mappinginformation.MapVersionMappingInformation;
import com.android.tools.r8.naming.mappinginformation.MappingInformation;
import com.android.tools.r8.naming.mappinginformation.OutlineCallsiteMappingInformation;
import com.android.tools.r8.naming.mappinginformation.OutlineMappingInformation;
import com.android.tools.r8.naming.mappinginformation.ResidualSignatureMappingInformation;
import com.android.tools.r8.naming.mappinginformation.RewriteFrameMappingInformation;
import com.android.tools.r8.naming.mappinginformation.RewriteFrameMappingInformation.ThrowsCondition;
import com.android.tools.r8.references.ArrayReference;
import com.android.tools.r8.references.ClassReference;
import com.android.tools.r8.references.MethodReference;
import com.android.tools.r8.references.Reference;
import com.android.tools.r8.references.TypeReference;
import com.android.tools.r8.utils.Box;
import com.android.tools.r8.utils.ChainableStringConsumer;
import com.android.tools.r8.utils.ConsumerUtils;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.SegmentTree;
import com.android.tools.r8.utils.ThrowingBiFunction;
import com.google.common.collect.Sets;
import it.unimi.dsi.fastutil.ints.Int2IntLinkedOpenHashMap;
import it.unimi.dsi.fastutil.ints.Int2IntSortedMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.Set;
import java.util.TreeMap;
import java.util.function.BiConsumer;
import java.util.function.Consumer;

public class ComposingBuilder {

  private MapVersionMappingInformation currentMapVersion = null;

  /**
   * When composing we store a view of the previously known mappings in committed and retain a
   * current working set. When composing of a new map is finished we commit everything in current
   * into the committed set.
   *
   * <p>The reason for not having just a single set is that we can have a circular mapping as
   * follows:
   *
   * <pre>
   *   a -> b:
   *   ...
   *   b -> a:
   * </pre>
   *
   * After composing our current view of a with the above, we could end up transforming 'a' into 'b'
   * and then later transforming 'b' back into 'a' again. To ensure we do not mess up namings while
   * composing classes and methods we resort to a working set and committed set.
   */
  private final ComposingData committed = new ComposingData();

  private ComposingData current;
  private final InternalOptions options;

  public ComposingBuilder(InternalOptions options) {
    this.options = options;
  }

  public void compose(ClassNameMapper classNameMapper) throws MappingComposeException {
    current = new ComposingData();
    MapVersionMappingInformation newMapVersionInfo =
        classNameMapper.getFirstMapVersionInformation();
    if (newMapVersionInfo == null) {
      throw new MappingComposeException(
          "Composition of mapping files supported from map version 2.2.");
    }
    MapVersion newMapVersion = newMapVersionInfo.getMapVersion();
    if (!ResidualSignatureMappingInformation.isSupported(newMapVersion)
        || newMapVersion.isUnknown()) {
      throw new MappingComposeException(
          "Composition of mapping files supported from map version "
              + ResidualSignatureMappingInformation.SUPPORTED_VERSION.getName()
              + ".");
    }
    if (currentMapVersion == null) {
      currentMapVersion = newMapVersionInfo;
    } else {
      currentMapVersion =
          newMapVersionInfo.compose(currentMapVersion).asMapVersionMappingInformation();
    }
    for (ClassNamingForNameMapper classMapping : classNameMapper.getClassNameMappings().values()) {
      compose(classNameMapper, classMapping);
    }
    committed.commit(current, classNameMapper);
  }

  private void compose(ClassNameMapper classNameMapper, ClassNamingForNameMapper classMapping)
      throws MappingComposeException {
    String originalName = classMapping.originalName;
    String renamedName = classMapping.renamedName;
    ComposingClassBuilder composingClassBuilder =
        new ComposingClassBuilder(originalName, renamedName, committed, current, options);
    ComposingClassBuilder duplicateMapping =
        current.classBuilders.put(renamedName, composingClassBuilder);
    if (duplicateMapping != null) {
      throw new MappingComposeException(
          "Duplicate class mapping. Both '"
              + duplicateMapping.getOriginalName()
              + "' and '"
              + originalName
              + "' maps to '"
              + renamedName
              + "'.");
    }
    composingClassBuilder.compose(classNameMapper, classMapping);
  }

  public String finish() {
    List<ComposingClassBuilder> classBuilders = new ArrayList<>(committed.classBuilders.values());
    classBuilders.sort(Comparator.comparing(ComposingClassBuilder::getOriginalName));
    StringBuilder sb = new StringBuilder();
    committed.preamble.forEach(preambleLine -> sb.append(preambleLine).append("\n"));
    if (currentMapVersion != null) {
      sb.append("# ").append(currentMapVersion.serialize()).append("\n");
    }
    ChainableStringConsumer wrap = ChainableStringConsumer.wrap(sb::append);
    for (ComposingClassBuilder classBuilder : classBuilders) {
      classBuilder.write(wrap);
    }
    return sb.toString();
  }

  public static class ComposingData {

    /**
     * A map of minified names to their class builders. When committing to a new minified name we
     * destructively remove the previous minified mapping and replace it with the up-to-date one.
     */
    private Map<String, ComposingClassBuilder> classBuilders = new HashMap<>();
    /**
     * RewriteFrameInformation contains condition clauses that are bound to the residual program. As
     * a result of that, we have to patch up the conditions when we compose new class mappings.
     */
    private final List<RewriteFrameMappingInformation> rewriteFrameInformation = new ArrayList<>();
    /** Map of newly added outline call site informations which do not require any rewriting. */
    private Map<ClassTypeNameAndMethodName, OutlineCallsiteMappingInformation>
        outlineCallsiteInformation = new HashMap<>();
    /**
     * Map of updated outline definitions which has to be committed. The positions in the caller are
     * fixed at this point since these are local to the method when rewriting.
     */
    private final Map<ClassTypeNameAndMethodName, UpdateOutlineCallsiteInformation>
        outlineSourcePositionsUpdated = new HashMap<>();

    /**
     * Map of signatures that should be removed when finalizing the composed map. The key is the
     * original name of a class.
     */
    private final Map<String, Set<Signature>> signaturesToRemove = new HashMap<>();

    private final List<String> preamble = new ArrayList<>();

    public void commit(ComposingData current, ClassNameMapper classNameMapper)
        throws MappingComposeException {
      preamble.addAll(classNameMapper.getPreamble());
      commitClassBuilders(current, classNameMapper);
      commitRewriteFrameInformation(current, classNameMapper);
      commitOutlineCallsiteInformation(current, classNameMapper);
    }

    private void commitClassBuilders(ComposingData current, ClassNameMapper classNameMapper)
        throws MappingComposeException {
      Set<String> updatedClassBuilders = new HashSet<>();
      Map<String, ComposingClassBuilder> newClassBuilders = new HashMap<>();
      for (Entry<String, ComposingClassBuilder> newEntry : current.classBuilders.entrySet()) {
        String renamedName = newEntry.getKey();
        ComposingClassBuilder classBuilder = newEntry.getValue();
        updatedClassBuilders.add(classBuilder.originalName);
        ComposingClassBuilder existingBuilder = classBuilders.get(classBuilder.originalName);
        if (existingBuilder != null) {
          removeSignaturesFromBuilder(current, existingBuilder);
          classBuilder = existingBuilder.commit(classBuilder);
        }
        newClassBuilders.put(renamedName, classBuilder);
      }
      for (Entry<String, ComposingClassBuilder> existingEntry : classBuilders.entrySet()) {
        if (!updatedClassBuilders.contains(existingEntry.getKey())) {
          ComposingClassBuilder classBuilder = existingEntry.getValue();
          removeSignaturesFromBuilder(current, classBuilder);
          ComposingClassBuilder duplicateMapping =
              newClassBuilders.put(existingEntry.getKey(), classBuilder);
          if (duplicateMapping != null) {
            throw new MappingComposeException(
                "Duplicate class mapping. Both '"
                    + classBuilder.getOriginalName()
                    + "' and '"
                    + classNameMapper.getClassNaming(existingEntry.getKey()).originalName
                    + "' maps to '"
                    + classBuilder.renamedName
                    + "'.");
          }
        }
      }
      classBuilders = newClassBuilders;
    }

    private void removeSignaturesFromBuilder(
        ComposingData current, ComposingClassBuilder classBuilder) {
      Set<Signature> signaturesToRemove =
          current.signaturesToRemove.get(classBuilder.getOriginalName());
      if (signaturesToRemove == null) {
        return;
      }
      signaturesToRemove.forEach(
          signatureToRemove -> {
            if (signatureToRemove.isFieldSignature()) {
              classBuilder.fieldMembers.remove(signatureToRemove.asFieldSignature());
            } else {
              classBuilder.methodsWithoutPosition.remove(signatureToRemove.asMethodSignature());
              classBuilder.methodsWithPosition.remove(signatureToRemove.asMethodSignature());
            }
          });
    }

    public void addSignatureToRemove(
        ComposingClassBuilder composingClassBuilder, Signature signature) {
      signaturesToRemove
          .computeIfAbsent(
              composingClassBuilder.getOriginalName(), ignoreArgument(Sets::newHashSet))
          .add(signature);
    }

    private void commitRewriteFrameInformation(
        ComposingData current, ClassNameMapper classNameMapper) {
      // First update the existing frame information to have new class name mappings.
      Map<String, String> inverse = classNameMapper.getObfuscatedToOriginalMapping().inverse;
      for (RewriteFrameMappingInformation rewriteMappingInfo : rewriteFrameInformation) {
        rewriteMappingInfo
            .getConditions()
            .forEach(
                rewriteCondition -> {
                  ThrowsCondition throwsCondition = rewriteCondition.asThrowsCondition();
                  if (throwsCondition != null) {
                    throwsCondition.setClassReferenceInternal(
                        mapTypeReference(inverse, throwsCondition.getClassReference()).asClass());
                  }
                });
      }
      rewriteFrameInformation.addAll(current.rewriteFrameInformation);
    }

    private void commitOutlineCallsiteInformation(
        ComposingData current, ClassNameMapper classNameMapper) {
      // To commit outline call site information, we take the previously committed and bring forward
      // to a new mapping, and potentially rewrite source positions if available.
      Map<ClassTypeNameAndMethodName, OutlineCallsiteMappingInformation> newOutlineCallsiteInfo =
          new HashMap<>();
      Map<String, String> inverse = classNameMapper.getObfuscatedToOriginalMapping().inverse;
      outlineCallsiteInformation.forEach(
          (holderAndMethodNameOfOutline, outlineInfo) -> {
            UpdateOutlineCallsiteInformation updateOutlineCallsiteInformation =
                current.outlineSourcePositionsUpdated.get(holderAndMethodNameOfOutline);
            String newMethodName = outlineInfo.getOutline().getMethodName();
            if (updateOutlineCallsiteInformation != null) {
              // We have a callsite mapping that we need to update.
              MappedRangeOriginalToMinifiedMap originalToMinifiedMap =
                  MappedRangeOriginalToMinifiedMap.build(
                      updateOutlineCallsiteInformation.newMappedRanges);
              Int2IntSortedMap newPositionMap = new Int2IntLinkedOpenHashMap();
              outlineInfo
                  .getPositions()
                  .forEach(
                      (originalPosition, destination) ->
                          originalToMinifiedMap.visitMinified(
                              originalPosition,
                              newMinified -> newPositionMap.put(newMinified, destination)));
              outlineInfo.setPositionsInternal(newPositionMap);
              newMethodName = updateOutlineCallsiteInformation.newMethodName;
            }
            // Holder, return type or formals could have changed the outline descriptor.
            MethodReference outline = outlineInfo.getOutline();
            ClassReference newHolder =
                mapTypeReference(inverse, outline.getHolderClass()).asClass();
            outlineInfo.setOutlineInternal(
                Reference.method(
                    newHolder,
                    newMethodName,
                    mapTypeReferences(inverse, outline.getFormalTypes()),
                    mapTypeReference(inverse, outline.getReturnType())));
            newOutlineCallsiteInfo.put(
                new ClassTypeNameAndMethodName(
                    newHolder.getTypeName(), holderAndMethodNameOfOutline.getMethodName()),
                outlineInfo);
          });
      newOutlineCallsiteInfo.putAll(current.outlineCallsiteInformation);
      outlineCallsiteInformation = newOutlineCallsiteInfo;
    }

    public void addNewOutlineCallsiteInformation(
        MethodReference outline, OutlineCallsiteMappingInformation outlineCallsiteInfo) {
      outlineCallsiteInformation.put(
          new ClassTypeNameAndMethodName(
              outline.getHolderClass().getTypeName(), outline.getMethodName()),
          outlineCallsiteInfo);
    }

    public UpdateOutlineCallsiteInformation getUpdateOutlineCallsiteInformation(
        String originalHolder, String originalMethodName, String newMethodName) {
      return outlineSourcePositionsUpdated.computeIfAbsent(
          new ClassTypeNameAndMethodName(originalHolder, originalMethodName),
          ignore -> new UpdateOutlineCallsiteInformation(newMethodName));
    }

    private List<TypeReference> mapTypeReferences(
        Map<String, String> typeNameMap, List<TypeReference> typeReferences) {
      return ListUtils.map(typeReferences, typeRef -> mapTypeReference(typeNameMap, typeRef));
    }

    private TypeReference mapTypeReference(
        Map<String, String> typeNameMap, TypeReference typeReference) {
      if (typeReference == null || typeReference.isPrimitive()) {
        return typeReference;
      }
      if (typeReference.isArray()) {
        ArrayReference arrayReference = typeReference.asArray();
        return Reference.array(
            mapTypeReference(typeNameMap, arrayReference.getBaseType()),
            arrayReference.getDimensions());
      } else {
        assert typeReference.isClass();
        String newTypeName = typeNameMap.get(typeReference.getTypeName());
        return newTypeName == null ? typeReference : Reference.classFromTypeName(newTypeName);
      }
    }
  }

  private static class ClassTypeNameAndMethodName {

    private final String holderTypeName;
    private final String methodName;

    public ClassTypeNameAndMethodName(String holderTypeName, String methodName) {
      this.holderTypeName = holderTypeName;
      this.methodName = methodName;
    }

    public String getHolderTypeName() {
      return holderTypeName;
    }

    public String getMethodName() {
      return methodName;
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (!(o instanceof ClassTypeNameAndMethodName)) {
        return false;
      }
      ClassTypeNameAndMethodName that = (ClassTypeNameAndMethodName) o;
      return holderTypeName.equals(that.holderTypeName) && methodName.equals(that.methodName);
    }

    @Override
    public int hashCode() {
      return Objects.hash(holderTypeName, methodName);
    }
  }

  private static class UpdateOutlineCallsiteInformation {

    private List<MappedRange> newMappedRanges;
    private final String newMethodName;

    private UpdateOutlineCallsiteInformation(String newMethodName) {
      this.newMethodName = newMethodName;
    }

    private void setNewMappedRanges(List<MappedRange> mappedRanges) {
      newMappedRanges = mappedRanges;
    }
  }

  private static class MappedRangeOriginalToMinifiedMap {

    private final Int2ReferenceMap<List<Integer>> originalToMinified;

    private MappedRangeOriginalToMinifiedMap(Int2ReferenceMap<List<Integer>> originalToMinified) {
      this.originalToMinified = originalToMinified;
    }

    private static MappedRangeOriginalToMinifiedMap build(List<MappedRange> mappedRanges) {
      Int2ReferenceMap<List<Integer>> positionMap = new Int2ReferenceOpenHashMap<>();
      for (MappedRange mappedRange : mappedRanges) {
        Range originalRange = mappedRange.originalRange;
        for (int position = originalRange.from; position <= originalRange.to; position++) {
          // It is perfectly fine to have multiple minified ranges mapping to the same source, we
          // just need to keep the additional information.
          positionMap
              .computeIfAbsent(position, ignoreArgument(ArrayList::new))
              .add(mappedRange.minifiedRange.from + (position - originalRange.from));
        }
      }
      return new MappedRangeOriginalToMinifiedMap(positionMap);
    }

    public int lookupFirst(int originalPosition) {
      List<Integer> minifiedPositions = originalToMinified.get(originalPosition);
      return minifiedPositions == null ? 0 : minifiedPositions.get(0);
    }

    public void visitMinified(int originalPosition, Consumer<Integer> consumer) {
      List<Integer> minifiedPositions = originalToMinified.get(originalPosition);
      if (minifiedPositions != null) {
        minifiedPositions.forEach(consumer);
      }
    }
  }

  public static class ComposingClassBuilder {

    private static final String INDENTATION = "    ";
    private static final int NO_RANGE_FROM = -1;

    private final String originalName;
    private final String renamedName;
    private final Map<FieldSignature, MemberNaming> fieldMembers = new HashMap<>();
    private final Map<MethodSignature, SegmentTree<List<MappedRange>>> methodsWithPosition =
        new HashMap<>();
    private final Map<MethodSignature, MappedRange> methodsWithoutPosition = new HashMap<>();
    private final List<MappingInformation> additionalMappingInfo = new ArrayList<>();

    private final ComposingData committed;
    private final ComposingData current;

    private final Map<String, ComposingClassBuilder> committedPreviousClassBuilders;
    private final ComposingClassBuilder committedPreviousClassBuilder;
    private final InternalOptions options;

    private ComposingClassBuilder(
        String originalName,
        String renamedName,
        ComposingData committed,
        ComposingData current,
        InternalOptions options) {
      this.originalName = originalName;
      this.renamedName = renamedName;
      this.current = current;
      this.committed = committed;
      this.options = options;
      committedPreviousClassBuilders = committed.classBuilders;
      committedPreviousClassBuilder = committedPreviousClassBuilders.get(originalName);
    }

    public String getOriginalName() {
      return originalName;
    }

    public String getRenamedName() {
      return renamedName;
    }

    public void compose(ClassNameMapper classNameMapper, ClassNamingForNameMapper mapper)
        throws MappingComposeException {
      List<MappingInformation> newMappingInfo = mapper.getAdditionalMappingInfo();
      if (newMappingInfo != null) {
        additionalMappingInfo.addAll(newMappingInfo);
      }
      composeFieldNamings(mapper, classNameMapper);
      composeMethodNamings(mapper, classNameMapper);
    }

    private void composeFieldNamings(
        ClassNamingForNameMapper mapper, ClassNameMapper classNameMapper) {
      Map<String, String> inverseClassMapping =
          classNameMapper.getObfuscatedToOriginalMapping().inverse;
      mapper.forAllFieldNaming(
          fieldNaming -> {
            MemberNaming fieldNamingToAdd = fieldNaming;
            FieldSignature originalSignature =
                fieldNaming.getOriginalSignature().asFieldSignature();
            FieldSignature residualSignature =
                fieldNaming
                    .computeResidualSignature(type -> inverseClassMapping.getOrDefault(type, type))
                    .asFieldSignature();
            MemberNaming existingMemberNaming = getExistingMemberNaming(originalSignature);
            if (existingMemberNaming != null) {
              Signature existingOriginalSignature = existingMemberNaming.getOriginalSignature();
              if (!existingOriginalSignature.isQualified() && originalSignature.isQualified()) {
                String previousCommittedClassName =
                    getPreviousCommittedClassName(originalSignature.toHolderFromQualified());
                if (previousCommittedClassName != null) {
                  existingOriginalSignature =
                      existingOriginalSignature.toQualifiedSignature(previousCommittedClassName);
                }
              }
              fieldNamingToAdd = new MemberNaming(existingOriginalSignature, residualSignature);
            }
            MemberNaming existing = fieldMembers.put(residualSignature, fieldNamingToAdd);
            assert existing == null;
          });
    }

    private String getPreviousCommittedClassName(String holder) {
      ComposingClassBuilder composingClassBuilder = committedPreviousClassBuilders.get(holder);
      return composingClassBuilder == null ? null : composingClassBuilder.getOriginalName();
    }

    private MemberNaming getExistingMemberNaming(FieldSignature originalSignature) {
      ComposingClassBuilder composingClassBuilder =
          originalSignature.isQualified()
              ? committedPreviousClassBuilders.get(originalSignature.toHolderFromQualified())
              : committedPreviousClassBuilder;
      if (composingClassBuilder == null) {
        return null;
      }
      FieldSignature signature =
          (originalSignature.isQualified()
                  ? originalSignature.toUnqualifiedSignature()
                  : originalSignature)
              .asFieldSignature();
      current.addSignatureToRemove(composingClassBuilder, signature);
      return composingClassBuilder.fieldMembers.get(signature);
    }

    private void composeMethodNamings(
        ClassNamingForNameMapper mapper, ClassNameMapper classNameMapper)
        throws MappingComposeException {
      Map<String, String> inverseClassMapping =
          classNameMapper.getObfuscatedToOriginalMapping().inverse;
      for (Entry<String, MappedRangesOfName> entry : mapper.mappedRangesByRenamedName.entrySet()) {
        MappedRangesOfName mappedRangesOfName = entry.getValue();
        for (MappedRangesOfName rangesOfName : mappedRangesOfName.partitionOnMethodSignature()) {
          MemberNaming memberNaming = rangesOfName.getMemberNaming(mapper);
          List<MappedRange> newMappedRanges = rangesOfName.getMappedRanges();
          RangeBuilder minified = new RangeBuilder();
          RangeBuilder original = new RangeBuilder();
          // The new minified ranges may have ranges that range over positions that has additional
          // information, such as inlinees:
          // Existing:
          //  1:2:void caller():14:15 -> x
          //  3:3:void inlinee():42:42 -> x
          //  3:3:void caller():16:16 -> x
          //  4:10:void caller():17:23 -> x
          //  ...
          // New mapping:
          //  1:5:void x():1:5 -> y
          //  6:10:void x():6:6 -> y
          //  ...
          // It is important that we therefore split up the new ranges to map everything back to the
          // existing original mappings:
          // Resulting mapping:
          //  1:2:void caller():14:15 -> y
          //  3:3:void inlinee():42:42 -> y
          //  3:3:void caller():16:16 -> y
          //  4:5:void caller():17:18 -> y
          //  6:10:void caller():19:19 -> y
          //  ...
          List<MappedRange> composedRanges = new ArrayList<>();
          ComputedOutlineInformation computedOutlineInformation = new ComputedOutlineInformation();
          for (MappedRange mappedRange : newMappedRanges) {
            minified.addRange(mappedRange.minifiedRange);
            original.addRange(mappedRange.originalRange);
            // Register mapping information that is dependent on the residual naming to allow
            // updating later on.
            registerMappingInformationFromMappedRanges(mappedRange);

            MethodSignature originalSignature =
                mappedRange.getOriginalSignature().asMethodSignature();

            // Remove the existing entry if it exists.
            List<MappedRange> existingMappedRanges = null;
            ComposingClassBuilder existingClassBuilder = getExistingClassBuilder(originalSignature);
            if (existingClassBuilder != null) {
              MethodSignature signature =
                  (originalSignature.isQualified()
                          ? originalSignature.toUnqualifiedSignature()
                          : originalSignature)
                      .asMethodSignature();
              current.addSignatureToRemove(existingClassBuilder, signature);
              SegmentTree<List<MappedRange>> listSegmentTree =
                  existingClassBuilder.methodsWithPosition.get(signature);
              if (listSegmentTree != null) {
                // Any new transformation can be lossy - for example, D8 only promises to keep line
                // positions if the method is not throwing (and is not debug). Additionally, R8/PG
                // emits `1:1:void foo() -> a` instead of `1:1:void foo():1:1 -> a`, so R8 must
                // capture the preamble position by explicitly inserting 0 as original range.
                Entry<Integer, List<MappedRange>> existingEntry =
                    listSegmentTree.findEntry(original.getStartOrNoRangeFrom());
                // We assume that all new minified ranges for a method are rewritten in the new map
                // such that no previous existing positions exists.
                if (existingEntry != null) {
                  // listSegmentTree.removeSegment(existingEntry.getKey());
                  existingMappedRanges = existingEntry.getValue();
                } else {
                  // The original can be discarded if it no longer exists or if the method is
                  // non-throwing.
                  if (original.hasValue()
                      && !original.isPreamble()
                      && !options.mappingComposeOptions().allowNonExistingOriginalRanges) {
                    throw new MappingComposeException(
                        "Could not find original starting position of '"
                            + minified.start
                            + "' which should be "
                            + original.start);
                  }
                }
                assert minified.hasValue();
              } else {
                MappedRange existingMappedRange =
                    existingClassBuilder.methodsWithoutPosition.get(signature);
                existingMappedRanges =
                    existingMappedRange == null
                        ? null
                        : Collections.singletonList(existingMappedRange);
              }
            }
            composedRanges.addAll(
                composeMappedRangesForMethod(
                    existingMappedRanges, mappedRange, computedOutlineInformation));
          }
          MappedRange lastComposedRange = ListUtils.last(composedRanges);
          if (computedOutlineInformation.seenOutlineMappingInformation != null) {
            current
                .getUpdateOutlineCallsiteInformation(
                    committedPreviousClassBuilder.getRenamedName(),
                    ListUtils.last(newMappedRanges).signature.getName(),
                    lastComposedRange.getRenamedName())
                .setNewMappedRanges(newMappedRanges);
            lastComposedRange.addMappingInformation(
                computedOutlineInformation.seenOutlineMappingInformation,
                ConsumerUtils.emptyConsumer());
          }
          if (!computedOutlineInformation.outlineCallsiteMappingInformationToPatchUp.isEmpty()) {
            MappedRangeOriginalToMinifiedMap originalToMinifiedMap =
                MappedRangeOriginalToMinifiedMap.build(newMappedRanges);
            List<OutlineCallsiteMappingInformation> outlineCallSites =
                new ArrayList<>(
                    computedOutlineInformation.outlineCallsiteMappingInformationToPatchUp);
            outlineCallSites.sort(Comparator.comparing(mapping -> mapping.getOutline().toString()));
            for (OutlineCallsiteMappingInformation outlineCallSite : outlineCallSites) {
              Int2IntSortedMap positionMap = outlineCallSite.getPositions();
              for (Integer keyPosition : positionMap.keySet()) {
                int keyPositionInt = keyPosition;
                int originalDestination = positionMap.get(keyPositionInt);
                int newDestination = originalToMinifiedMap.lookupFirst(originalDestination);
                positionMap.put(keyPositionInt, newDestination);
              }
              lastComposedRange.addMappingInformation(
                  outlineCallSite, ConsumerUtils.emptyConsumer());
            }
          }
          MethodSignature residualSignature =
              memberNaming
                  .computeResidualSignature(type -> inverseClassMapping.getOrDefault(type, type))
                  .asMethodSignature();
          if (lastComposedRange.minifiedRange != null) {
            methodsWithPosition
                .computeIfAbsent(residualSignature, ignored -> new SegmentTree<>(false))
                .add(
                    minified.getStartOrNoRangeFrom(),
                    minified.getEndOrNoRangeFrom(),
                    composedRanges);
          } else {
            assert composedRanges.size() == 1;
            methodsWithoutPosition.put(residualSignature, lastComposedRange);
          }
        }
      }
    }

    private ComposingClassBuilder getExistingClassBuilder(MethodSignature originalSignature) {
      return originalSignature.isQualified()
          ? committedPreviousClassBuilders.get(originalSignature.toHolderFromQualified())
          : committedPreviousClassBuilder;
    }

    private void registerMappingInformationFromMappedRanges(MappedRange mappedRange)
        throws MappingComposeException {
      for (MappingInformation mappingInformation : mappedRange.getAdditionalMappingInformation()) {
        if (mappingInformation.isRewriteFrameMappingInformation()) {
          RewriteFrameMappingInformation rewriteFrameMappingInformation =
              mappingInformation.asRewriteFrameMappingInformation();
          rewriteFrameMappingInformation
              .getConditions()
              .forEach(
                  condition -> {
                    if (condition.isThrowsCondition()) {
                      current.rewriteFrameInformation.add(rewriteFrameMappingInformation);
                    }
                  });
        } else if (mappingInformation.isOutlineCallsiteInformation()) {
          OutlineCallsiteMappingInformation outlineCallsiteInfo =
              mappingInformation.asOutlineCallsiteInformation();
          MethodReference outline = outlineCallsiteInfo.getOutline();
          if (outline == null) {
            throw new MappingComposeException(
                "Unable to compose outline call site information without outline key: "
                    + outlineCallsiteInfo.serialize());
          }
          current.addNewOutlineCallsiteInformation(outline, outlineCallsiteInfo);
        }
      }
    }

    private List<MappedRange> composeMappedRangesForMethod(
        List<MappedRange> existingRanges,
        MappedRange newRange,
        ComputedOutlineInformation computedOutlineInformation)
        throws MappingComposeException {
      assert newRange != null;
      if (existingRanges == null || existingRanges.isEmpty()) {
        return Collections.singletonList(newRange);
      }
      Box<Range> originalRange = new Box<>();
      ExistingMapping mappedRangesForPosition =
          computeExistingMapping(
              existingRanges, (start, end) -> originalRange.set(new Range(start, end)));
      List<MappedRange> newComposedRanges = new ArrayList<>();
      MappedRange lastExistingRange = ListUtils.last(existingRanges);
      if (newRange.originalRange == null && newRange.minifiedRange == null) {
        MappedRange newComposedRange =
            new MappedRange(
                null, lastExistingRange.signature, originalRange.get(), newRange.renamedName);
        composeMappingInformation(
            newComposedRange.getAdditionalMappingInformation(),
            lastExistingRange.getAdditionalMappingInformation(),
            info -> newComposedRange.addMappingInformation(info, ConsumerUtils.emptyConsumer()));
        newComposedRanges.add(newComposedRange);
      } else {
        assert newRange.minifiedRange != null;
        // First check if the original range matches the existing minified range.
        List<MappedRange> existingMappedRanges =
            mappedRangesForPosition.getMappedRangesForPosition(
                newRange.getFirstPositionOfOriginalRange(NO_RANGE_FROM));
        if (existingMappedRanges == null) {
          // If we cannot lookup the original position because it has been removed we compose with
          // the existing method signature.
          if (newRange.originalRange != null && newRange.originalRange.isPreamble()) {
            return Collections.singletonList(
                new MappedRange(
                    null, lastExistingRange.signature, originalRange.get(), newRange.renamedName));
          } else {
            throw new MappingComposeException(
                "Unexpected missing original position for '" + newRange + "'.");
          }
        }
        // We have found an existing range for the original position.
        MappedRange lastExistingMappedRange = ListUtils.last(existingMappedRanges);
        // If the existing mapped minified range is equal to the original range of the new range
        // then we have a perfect mapping that we can translate directly.
        if (lastExistingMappedRange.minifiedRange.equals(newRange.originalRange)) {
          computeComposedMappedRange(
              newComposedRanges,
              newRange,
              existingMappedRanges,
              computedOutlineInformation,
              newRange.minifiedRange.from,
              newRange.minifiedRange.to);
        } else {
          // Otherwise, we have a situation where the minified range references over multiple
          // existing ranges. We simply chop op when the range changes on the right hand side. To
          // ensure we do not mess up the spans from the original range, we have to check if the
          // current starting position is inside an original range, and then chop it off.
          // Similarly, when writing the last block, we have to cut it off to match.
          int lastStartingMinifiedFrom = newRange.minifiedRange.from;
          for (int position = newRange.minifiedRange.from;
              position <= newRange.minifiedRange.to;
              position++) {
            List<MappedRange> existingMappedRangesForPosition =
                mappedRangesForPosition.getMappedRangesForPosition(
                    newRange.getOriginalLineNumber(position));
            MappedRange lastExistingMappedRangeForPosition = null;
            if (existingMappedRangesForPosition != null) {
              lastExistingMappedRangeForPosition = ListUtils.last(existingMappedRangesForPosition);
            }
            if (lastExistingMappedRangeForPosition == null
                || !lastExistingMappedRange.minifiedRange.equals(
                    lastExistingMappedRangeForPosition.minifiedRange)) {
              // We have seen an existing range we have to compute a splitting for.
              computeComposedMappedRange(
                  newComposedRanges,
                  newRange,
                  existingMappedRanges,
                  computedOutlineInformation,
                  lastStartingMinifiedFrom,
                  position - 1);
              // Advance the last starting position to this point and advance the existing mapped
              // ranges for this position.
              lastStartingMinifiedFrom = position;
              if (existingMappedRangesForPosition == null) {
                if (!options.mappingComposeOptions().allowNonExistingOriginalRanges) {
                  throw new MappingComposeException(
                      "Unexpected missing original position for '" + newRange + "'.");
                }
                // We are at the first position of a hole. If we have existing ranges:
                // 1:1:void foo():41:41 -> a
                // 9:9:void foo():49:49 -> a
                // We may have a new range that is:
                // 21:29:void foo():1:9
                // We end up here at position 2 and we have already committed
                // 21:21:void foo():41:41.
                // We then introduce a "fake" normal range to simulate the result of retracing one
                // after the other to end up with:
                // 21:21:void foo():41:41
                // 22:28:void foo():2:8
                // 29:29:void foo():49:49.
                int startOriginalPosition = newRange.getOriginalLineNumber(position);
                Integer endOriginalPosition =
                    mappedRangesForPosition.getCeilingForPosition(position);
                if (endOriginalPosition == null) {
                  endOriginalPosition = newRange.getLastPositionOfOriginalRange() + 1;
                }
                Range newOriginalRange = new Range(startOriginalPosition, endOriginalPosition - 1);
                MappedRange nonExistingMappedRange =
                    new MappedRange(
                        newOriginalRange,
                        lastExistingMappedRange.getOriginalSignature().asMethodSignature(),
                        newOriginalRange,
                        lastExistingMappedRange.renamedName);
                nonExistingMappedRange.setResidualSignatureInternal(
                    lastExistingRange.getResidualSignature());
                lastExistingMappedRange = nonExistingMappedRange;
                existingMappedRanges = Collections.singletonList(nonExistingMappedRange);
                position += (endOriginalPosition - startOriginalPosition) - 1;
              } else {
                lastExistingMappedRange = lastExistingMappedRangeForPosition;
                existingMappedRanges = existingMappedRangesForPosition;
              }
            }
          }
          computeComposedMappedRange(
              newComposedRanges,
              newRange,
              existingMappedRanges,
              computedOutlineInformation,
              lastStartingMinifiedFrom,
              newRange.minifiedRange.to);
        }
      }
      return newComposedRanges;
    }

    public interface ExistingMapping {

      Integer getCeilingForPosition(int i);

      List<MappedRange> getMappedRangesForPosition(int i);
    }

    /***
     * Builds a position to mapped ranges for mappings by looking up all mapped ranges for a given
     * position.
     */
    private ExistingMapping computeExistingMapping(
        List<MappedRange> existingRanges, BiConsumer<Integer, Integer> positions) {
      TreeMap<Integer, List<MappedRange>> mappedRangesForPosition = new TreeMap<>();
      List<MappedRange> currentRangesForPosition = new ArrayList<>();
      int startExisting = NO_RANGE_FROM;
      int endExisting = NO_RANGE_FROM;
      boolean isCatchAll = false;
      for (int i = 0; i < existingRanges.size(); i++) {
        MappedRange mappedRange = existingRanges.get(i);
        currentRangesForPosition.add(mappedRange);
        if (!isInlineMappedRange(existingRanges, i)) {
          if (startExisting == NO_RANGE_FROM) {
            startExisting = mappedRange.getFirstPositionOfOriginalRange(NO_RANGE_FROM);
          }
          endExisting = Math.max(mappedRange.getLastPositionOfOriginalRange(), endExisting);
          if (mappedRange.minifiedRange == null) {
            mappedRangesForPosition.put(NO_RANGE_FROM, currentRangesForPosition);
          } else if (mappedRange.minifiedRange.isCatchAll()) {
            isCatchAll = true;
          } else {
            for (int position = mappedRange.minifiedRange.from;
                position <= mappedRange.minifiedRange.to;
                position++) {
              mappedRangesForPosition.put(position, currentRangesForPosition);
            }
          }
          currentRangesForPosition = new ArrayList<>();
        }
      }
      if (startExisting > NO_RANGE_FROM) {
        positions.accept(startExisting, endExisting);
      }
      boolean finalIsCatchAll = isCatchAll;
      List<MappedRange> finalCurrentRangesForPosition = currentRangesForPosition;
      return new ExistingMapping() {
        @Override
        public Integer getCeilingForPosition(int i) {
          return finalIsCatchAll ? i : mappedRangesForPosition.ceilingKey(i);
        }

        @Override
        public List<MappedRange> getMappedRangesForPosition(int i) {
          return finalIsCatchAll ? finalCurrentRangesForPosition : mappedRangesForPosition.get(i);
        }
      };
    }

    private void computeComposedMappedRange(
        List<MappedRange> newComposedRanges,
        MappedRange newMappedRange,
        List<MappedRange> existingMappedRanges,
        ComputedOutlineInformation computedOutlineInformation,
        int lastStartingMinifiedFrom,
        int position)
        throws MappingComposeException {
      Range existingRange = existingMappedRanges.get(0).minifiedRange;
      assert existingMappedRanges.stream().allMatch(x -> x.minifiedRange.equals(existingRange));
      Range newMinifiedRange = new Range(lastStartingMinifiedFrom, position);
      boolean copyOriginalRange = existingRange.equals(newMappedRange.originalRange);
      for (MappedRange existingMappedRange : existingMappedRanges) {
        Range existingOriginalRange = existingMappedRange.originalRange;
        Range newOriginalRange;
        if (copyOriginalRange
            || existingOriginalRange == null
            || existingOriginalRange.span() == 1) {
          newOriginalRange = existingOriginalRange;
        } else {
          // Find the window that the new range points to into the original range.
          int existingMinifiedPos = newMappedRange.getOriginalLineNumber(lastStartingMinifiedFrom);
          int newOriginalStart = existingMappedRange.getOriginalLineNumber(existingMinifiedPos);
          if (newMappedRange.originalRange.span() == 1) {
            newOriginalRange = new Range(newOriginalStart, newOriginalStart);
          } else {
            assert newMinifiedRange.span() <= existingOriginalRange.span();
            newOriginalRange =
                new Range(newOriginalStart, newOriginalStart + newMinifiedRange.span() - 1);
          }
        }
        MappedRange computedRange =
            new MappedRange(
                newMinifiedRange,
                existingMappedRange.signature,
                newOriginalRange,
                newMappedRange.renamedName);
        List<MappingInformation> mappingInformationToCompose = new ArrayList<>();
        existingMappedRange
            .getAdditionalMappingInformation()
            .forEach(
                info -> {
                  if (info.isOutlineMappingInformation()) {
                    computedOutlineInformation.seenOutlineMappingInformation =
                        info.asOutlineMappingInformation();
                  } else if (info.isOutlineCallsiteInformation()) {
                    computedOutlineInformation.outlineCallsiteMappingInformationToPatchUp.add(
                        info.asOutlineCallsiteInformation());
                  } else {
                    mappingInformationToCompose.add(info);
                  }
                });
        composeMappingInformation(
            computedRange.getAdditionalMappingInformation(),
            mappingInformationToCompose,
            info -> computedRange.addMappingInformation(info, ConsumerUtils.emptyConsumer()));
        newComposedRanges.add(computedRange);
      }
    }

    /***
     * Populates newMappingInformation with existingMappingInformation.
     */
    private void composeMappingInformation(
        List<MappingInformation> newMappingInformation,
        List<MappingInformation> existingMappingInformation,
        Consumer<MappingInformation> consumer)
        throws MappingComposeException {
      Set<MappingInformation> nonCompasableNewInfos = Sets.newIdentityHashSet();
      for (MappingInformation existingInfo : existingMappingInformation) {
        boolean hasBeenComposed = false;
        for (MappingInformation newInfo : newMappingInformation) {
          if (newInfo.shouldCompose(existingInfo)) {
            nonCompasableNewInfos.add(newInfo);
            consumer.accept(newInfo.compose(existingInfo));
            hasBeenComposed = true;
          }
        }
        if (!hasBeenComposed) {
          consumer.accept(existingInfo);
        }
      }
      newMappingInformation.forEach(
          info -> {
            if (!nonCompasableNewInfos.contains(info)) {
              consumer.accept(info);
            }
          });
    }

    public void write(ChainableStringConsumer consumer) {
      consumer.accept(originalName).accept(" -> ").accept(renamedName).accept(":\n");
      additionalMappingInfo.forEach(info -> consumer.accept("# " + info.serialize()).accept("\n"));
      writeFields(consumer);
      writeMethods(consumer);
    }

    private void writeFields(ChainableStringConsumer consumer) {
      ArrayList<MemberNaming> fieldNamings = new ArrayList<>(fieldMembers.values());
      fieldNamings.sort(Comparator.comparing(MemberNaming::getOriginalName));
      fieldNamings.forEach(
          naming -> consumer.accept(INDENTATION).accept(naming.toString()).accept("\n"));
    }

    private void writeMethods(ChainableStringConsumer consumer) {
      methodsWithoutPosition.forEach(
          (ignored, mapped) -> {
            consumer.accept(INDENTATION).accept(mapped.toString()).accept("\n");
            for (MappingInformation info : mapped.getAdditionalMappingInformation()) {
              consumer.accept(INDENTATION).accept("# ").accept(info.serialize()).accept("\n");
            }
          });
      ArrayList<MethodSignature> sortedSignatures = new ArrayList<>(methodsWithPosition.keySet());
      sortedSignatures.sort(Comparator.comparing(Signature::getName));
      for (MethodSignature key : sortedSignatures) {
        methodsWithPosition
            .get(key)
            .visitSegments(
                mappedRanges ->
                    mappedRanges.forEach(
                        mappedRange -> {
                          consumer.accept(INDENTATION).accept(mappedRange.toString()).accept("\n");
                          for (MappingInformation info :
                              mappedRange.getAdditionalMappingInformation()) {
                            consumer
                                .accept(INDENTATION)
                                .accept("# ")
                                .accept(info.serialize())
                                .accept("\n");
                          }
                        }));
      }
    }

    public ComposingClassBuilder commit(ComposingClassBuilder classBuilder)
        throws MappingComposeException {
      ComposingClassBuilder newClassBuilder =
          new ComposingClassBuilder(
              originalName, classBuilder.renamedName, committed, null, options);
      composeMappingInformation(
          classBuilder.additionalMappingInfo,
          additionalMappingInfo,
          newClassBuilder.additionalMappingInfo::add);
      // Composed field namings and method namings should be freely composable by addition since
      // any renaming/position change should have removed the existing committed mapping.
      putAll(
          newClassBuilder.fieldMembers,
          fieldMembers,
          classBuilder.fieldMembers,
          (committed, add) -> {
            assert committed == null;
            return add;
          });
      putAll(
          newClassBuilder.methodsWithoutPosition,
          methodsWithoutPosition,
          classBuilder.methodsWithoutPosition,
          (committed, add) -> {
            if (committed != null && add != null) {
              throw new MappingComposeException(
                  "Cannot compose duplicate methods without position in class '"
                      + renamedName
                      + "': '"
                      + committed
                      + "' and '"
                      + add);
            }
            return committed != null ? committed : add;
          });
      putAll(
          newClassBuilder.methodsWithPosition,
          methodsWithPosition,
          classBuilder.methodsWithPosition,
          (committed, add) -> add);
      return newClassBuilder;
    }

    private <S extends Signature, V> void putAll(
        Map<S, V> output,
        Map<S, V> committed,
        Map<S, V> toAdd,
        ThrowingBiFunction<V, V, V, MappingComposeException> compose)
        throws MappingComposeException {
      assert output.isEmpty();
      output.putAll(committed);
      for (Entry<S, V> kvEntry : toAdd.entrySet()) {
        output.put(
            kvEntry.getKey(), compose.apply(output.get(kvEntry.getKey()), kvEntry.getValue()));
      }
    }

    private static class RangeBuilder {

      private int start = Integer.MAX_VALUE;
      private int end = Integer.MIN_VALUE;

      private void addRange(Range range) {
        if (range != null) {
          start = Math.min(start, range.from);
          end = Math.max(end, range.to);
        }
      }

      private boolean hasValue() {
        return start < Integer.MAX_VALUE;
      }

      private int getStartOrNoRangeFrom() {
        return hasValue() ? start : NO_RANGE_FROM;
      }

      private int getEndOrNoRangeFrom() {
        return hasValue() ? end : NO_RANGE_FROM;
      }

      private boolean isPreamble() {
        return hasValue() && start == end && start == 0;
      }
    }

    private static class ComputedOutlineInformation {
      private final Set<OutlineCallsiteMappingInformation>
          outlineCallsiteMappingInformationToPatchUp = Sets.newIdentityHashSet();
      private OutlineMappingInformation seenOutlineMappingInformation = null;
    }
  }
}