diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 7c7249b..4b67000 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
 
   // This field is accessed from release scripts using simple pattern matching.
   // Therefore, changing this field could break our release scripts.
-  public static final String LABEL = "1.5.40";
+  public static final String LABEL = "1.5.41";
 
   private Version() {
   }
diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
index 8018a2d..db46954 100644
--- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java
@@ -33,6 +33,7 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
+import java.util.function.Predicate;
 
 class ClassNameMinifier {
 
@@ -367,11 +368,6 @@
           // L or La/b/ (or La/b/C$)
           + (packageName.isEmpty() ? "" : separator))
           .toCharArray();
-
-      // R.class in Android, which contains constant IDs to assets, can be bundled at any time.
-      // Insert `R` immediately so that the class name minifier can skip that name by default.
-      StringBuilder rBuilder = new StringBuilder().append(packagePrefix).append("R;");
-      usedTypeNames.add(appView.dexItemFactory().createString(rBuilder.toString()));
     }
 
     public String getPackageName() {
@@ -379,21 +375,18 @@
     }
 
     DexString nextTypeName(DexType type) {
-      DexString candidate;
-      do {
-        candidate = classNamingStrategy.next(type, packagePrefix, this);
-      } while (usedTypeNames.contains(candidate));
+      DexString candidate =
+          classNamingStrategy.next(type, packagePrefix, this, usedTypeNames::contains);
+      assert !usedTypeNames.contains(candidate);
       usedTypeNames.add(candidate);
       return candidate;
     }
 
     String nextPackagePrefix() {
-      String candidate;
-      do {
-        candidate = packageNamingStrategy.next(packagePrefix, this);
-      } while (usedPackagePrefixes.contains(candidate));
-      usedPackagePrefixes.add(candidate);
-      return candidate;
+      String next = packageNamingStrategy.next(packagePrefix, this, usedPackagePrefixes::contains);
+      assert !usedPackagePrefixes.contains(next);
+      usedPackagePrefixes.add(next);
+      return next;
     }
 
     @Override
@@ -414,13 +407,14 @@
   }
 
   protected interface ClassNamingStrategy {
-    DexString next(DexType type, char[] packagePrefix, InternalNamingState state);
+    DexString next(
+        DexType type, char[] packagePrefix, InternalNamingState state, Predicate<DexString> isUsed);
 
     boolean noObfuscation(DexType type);
   }
 
   protected interface PackageNamingStrategy {
-    String next(char[] packagePrefix, InternalNamingState state);
+    String next(char[] packagePrefix, InternalNamingState state, Predicate<String> isUsed);
   }
 
   /**
diff --git a/src/main/java/com/android/tools/r8/naming/FieldNamingState.java b/src/main/java/com/android/tools/r8/naming/FieldNamingState.java
index d8cb81d..6718c44 100644
--- a/src/main/java/com/android/tools/r8/naming/FieldNamingState.java
+++ b/src/main/java/com/android/tools/r8/naming/FieldNamingState.java
@@ -14,11 +14,13 @@
 import com.android.tools.r8.naming.FieldNamingState.InternalState;
 import java.util.IdentityHashMap;
 import java.util.Map;
+import java.util.function.BiPredicate;
 
 public class FieldNamingState extends FieldNamingStateBase<InternalState> implements Cloneable {
 
   private final ReservedFieldNamingState reservedNames;
   private final MemberNamingStrategy strategy;
+  private final BiPredicate<DexString, DexType> isUsed;
 
   public FieldNamingState(AppView<?> appView, MemberNamingStrategy strategy) {
     this(appView, strategy, new ReservedFieldNamingState(appView));
@@ -37,6 +39,7 @@
     super(appView, internalStates);
     this.reservedNames = reservedNames;
     this.strategy = strategy;
+    this.isUsed = (newName, fieldType) -> reservedNames.isReserved(newName, fieldType);
   }
 
   public FieldNamingState createChildState(ReservedFieldNamingState reservedNames) {
@@ -95,10 +98,8 @@
     }
 
     public DexString createNewName(DexField field) {
-      DexString name;
-      do {
-        name = strategy.next(field, this);
-      } while (reservedNames.isReserved(name, field.type));
+      DexString name = strategy.next(field, this, isUsed);
+      assert !reservedNames.isReserved(name, field.type);
       return name;
     }
 
diff --git a/src/main/java/com/android/tools/r8/naming/MemberNamingStrategy.java b/src/main/java/com/android/tools/r8/naming/MemberNamingStrategy.java
index f33027b..fefba5b 100644
--- a/src/main/java/com/android/tools/r8/naming/MemberNamingStrategy.java
+++ b/src/main/java/com/android/tools/r8/naming/MemberNamingStrategy.java
@@ -11,12 +11,16 @@
 import com.android.tools.r8.graph.DexMethod;
 import com.android.tools.r8.graph.DexReference;
 import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import java.util.function.BiPredicate;
+import java.util.function.Predicate;
 
 public interface MemberNamingStrategy {
 
-  DexString next(DexMethod method, InternalNamingState internalState);
+  DexString next(DexMethod method, InternalNamingState internalState, Predicate<DexString> isUsed);
 
-  DexString next(DexField field, InternalNamingState internalState);
+  DexString next(
+      DexField field, InternalNamingState internalState, BiPredicate<DexString, DexType> isUsed);
 
   DexString getReservedNameOrDefault(
       DexEncodedMethod method, DexClass holder, DexString defaultValue);
diff --git a/src/main/java/com/android/tools/r8/naming/MethodNamingState.java b/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
index adbc1c3..7cbdc45 100644
--- a/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
+++ b/src/main/java/com/android/tools/r8/naming/MethodNamingState.java
@@ -11,6 +11,7 @@
 import java.util.HashMap;
 import java.util.Map;
 import java.util.function.Function;
+import java.util.function.Predicate;
 
 class MethodNamingState<KeyType> {
 
@@ -253,6 +254,7 @@
 
     private final InternalNewNameState parentInternalState;
     private final InternalReservationState reservationState;
+    private final Predicate<DexString> isUsed;
 
     private static final int INITIAL_NAME_COUNT = 1;
     private static final int INITIAL_DICTIONARY_INDEX = 0;
@@ -272,6 +274,7 @@
       this.virtualNameCount =
           parentInternalState == null ? INITIAL_NAME_COUNT : parentInternalState.virtualNameCount;
       assert reservationState != null;
+      isUsed = newName -> !reservationState.isAvailable(newName);
     }
 
     @Override
@@ -307,11 +310,9 @@
     }
 
     private DexString getNewNameFor(DexMethod source) {
-      DexString name;
-      do {
-        name = strategy.next(source, this);
-      } while (!reservationState.isAvailable(name));
-      return name;
+      DexString next = strategy.next(source, this, isUsed);
+      assert reservationState.isAvailable(next);
+      return next;
     }
 
     void printInternalState(
diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java
index 6906a06..7623b79 100644
--- a/src/main/java/com/android/tools/r8/naming/Minifier.java
+++ b/src/main/java/com/android/tools/r8/naming/Minifier.java
@@ -5,6 +5,7 @@
 
 import static com.android.tools.r8.utils.StringUtils.EMPTY_CHAR_ARRAY;
 
+import com.android.tools.r8.errors.CompilationError;
 import com.android.tools.r8.graph.AppView;
 import com.android.tools.r8.graph.DexCallSite;
 import com.android.tools.r8.graph.DexClass;
@@ -29,6 +30,8 @@
 import java.util.List;
 import java.util.Set;
 import java.util.TreeSet;
+import java.util.function.BiPredicate;
+import java.util.function.Predicate;
 
 public class Minifier {
 
@@ -123,19 +126,43 @@
       implements ClassNamingStrategy {
 
     final AppView<?> appView;
-    private final DexItemFactory factory;
+    final DexItemFactory factory;
 
     MinificationClassNamingStrategy(AppView<?> appView) {
       super(
           appView.options().getProguardConfiguration().getClassObfuscationDictionary(),
           appView.options().getProguardConfiguration().hasDontUseMixedCaseClassnames());
       this.appView = appView;
-      factory = appView.dexItemFactory();
+      this.factory = appView.dexItemFactory();
     }
 
     @Override
-    public DexString next(DexType type, char[] packagePrefix, InternalNamingState state) {
-      return factory.createString(nextName(packagePrefix, state, false) + ";");
+    public DexString next(
+        DexType type,
+        char[] packagePrefix,
+        InternalNamingState state,
+        Predicate<DexString> isUsed) {
+      DexString candidate = null;
+      String lastName = null;
+      do {
+        String newName = nextName(packagePrefix, state, false) + ";";
+        if (newName.equals(lastName)) {
+          throw new CompilationError(
+              "Generating same name '"
+                  + newName
+                  + "' when given a new minified name to '"
+                  + type.toString()
+                  + "'.");
+        }
+        lastName = newName;
+        // R.class in Android, which contains constant IDs to assets, can be bundled at any time.
+        // Insert `R` immediately so that the class name minifier can skip that name by default.
+        if (newName.endsWith("LR;") || newName.endsWith("/R;")) {
+          continue;
+        }
+        candidate = factory.createString(newName);
+      } while (candidate == null || isUsed.test(candidate));
+      return candidate;
     }
 
     @Override
@@ -154,12 +181,16 @@
     }
 
     @Override
-    public String next(char[] packagePrefix, InternalNamingState state) {
+    public String next(char[] packagePrefix, InternalNamingState state, Predicate<String> isUsed) {
       // Note that the differences between this method and the other variant for class renaming are
       // 1) this one uses the different dictionary and counter,
       // 2) this one does not append ';' at the end, and
       // 3) this one removes 'L' at the beginning to make the return value a binary form.
-      return nextName(packagePrefix, state, false).substring(1);
+      String nextPackageName;
+      do {
+        nextPackageName = nextName(packagePrefix, state, false).substring(1);
+      } while (isUsed.test(nextPackageName));
+      return nextPackageName;
     }
   }
 
@@ -176,17 +207,27 @@
     }
 
     @Override
-    public DexString next(DexMethod method, InternalNamingState internalState) {
+    public DexString next(
+        DexMethod method, InternalNamingState internalState, Predicate<DexString> isUsed) {
       assert checkAllowMemberRenaming(method.holder);
       DexEncodedMethod encodedMethod = appView.definitionFor(method);
       boolean isDirectOrStatic = encodedMethod.isDirectMethod() || encodedMethod.isStatic();
-      return getNextName(internalState, isDirectOrStatic);
+      DexString candidate;
+      do {
+        candidate = getNextName(internalState, isDirectOrStatic);
+      } while (isUsed.test(candidate));
+      return candidate;
     }
 
     @Override
-    public DexString next(DexField field, InternalNamingState internalState) {
+    public DexString next(
+        DexField field, InternalNamingState internalState, BiPredicate<DexString, DexType> isUsed) {
       assert checkAllowMemberRenaming(field.holder);
-      return getNextName(internalState, false);
+      DexString candidate;
+      do {
+        candidate = getNextName(internalState, false);
+      } while (isUsed.test(candidate, field.type));
+      return candidate;
     }
 
     private DexString getNextName(InternalNamingState internalState, boolean isDirectOrStatic) {
diff --git a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
index 895b8c5..8f73dd0 100644
--- a/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
+++ b/src/main/java/com/android/tools/r8/naming/ProguardMapMinifier.java
@@ -39,6 +39,8 @@
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeSet;
+import java.util.function.BiPredicate;
+import java.util.function.Predicate;
 
 /**
  * The ProguardMapMinifier will assign names to classes and members following the initial naming
@@ -335,13 +337,17 @@
     }
 
     @Override
-    public DexString next(DexType type, char[] packagePrefix, InternalNamingState state) {
+    public DexString next(
+        DexType type,
+        char[] packagePrefix,
+        InternalNamingState state,
+        Predicate<DexString> isUsed) {
       DexString nextName = mappings.get(type);
       if (nextName != null) {
         return nextName;
       }
       assert !(isMinifying && noObfuscation(type));
-      return isMinifying ? super.next(type, packagePrefix, state) : type.descriptor;
+      return isMinifying ? super.next(type, packagePrefix, state, isUsed) : type.descriptor;
     }
 
     @Override
@@ -372,15 +378,19 @@
     }
 
     @Override
-    public DexString next(DexMethod method, InternalNamingState internalState) {
+    public DexString next(
+        DexMethod method, InternalNamingState internalState, Predicate<DexString> isUsed) {
       assert !mappedNames.containsKey(method);
-      return canMinify(method, method.holder) ? super.next(method, internalState) : method.name;
+      return canMinify(method, method.holder)
+          ? super.next(method, internalState, isUsed)
+          : method.name;
     }
 
     @Override
-    public DexString next(DexField field, InternalNamingState internalState) {
+    public DexString next(
+        DexField field, InternalNamingState internalState, BiPredicate<DexString, DexType> isUsed) {
       assert !mappedNames.containsKey(field);
-      return canMinify(field, field.holder) ? super.next(field, internalState) : field.name;
+      return canMinify(field, field.holder) ? super.next(field, internalState, isUsed) : field.name;
     }
 
     private boolean canMinify(DexReference reference, DexType type) {
diff --git a/src/test/java/com/android/tools/r8/naming/applymapping/ApplyMappingReservationTest.java b/src/test/java/com/android/tools/r8/naming/applymapping/ApplyMappingReservationTest.java
new file mode 100644
index 0000000..0a826d7
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/applymapping/ApplyMappingReservationTest.java
@@ -0,0 +1,63 @@
+// Copyright (c) 2019, 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.applymapping;
+
+import com.android.tools.r8.CompilationFailedException;
+import com.android.tools.r8.R8TestCompileResult;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.naming.applymapping.shared.R;
+import java.io.IOException;
+import java.util.concurrent.ExecutionException;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ApplyMappingReservationTest extends TestBase {
+
+  // This is the program which we will not rename and will cause a naming conflict per b/133646663.
+  public static class Runner {
+
+    public static void main(String[] args) {
+      System.out.print(new R().identifier);
+    }
+  }
+
+  private final TestParameters parameters;
+
+  @Parameters(name = "{0}")
+  public static TestParametersCollection data() {
+    return getTestParameters().withAllRuntimes().build();
+  }
+
+  public ApplyMappingReservationTest(TestParameters parameters) {
+    this.parameters = parameters;
+  }
+
+  @Test
+  public void testReservedNames()
+      throws IOException, CompilationFailedException, ExecutionException {
+    R8TestCompileResult libraryCompileResult =
+        testForR8(parameters.getBackend())
+            .addProgramClasses(R.class)
+            .addKeepClassAndMembersRules(R.class)
+            .setMinApi(parameters.getRuntime())
+            .compile();
+    testForR8(parameters.getBackend())
+        .addProgramClasses(Runner.class)
+        .addClasspathClasses(R.class)
+        .addKeepMainRule(Runner.class)
+        .addApplyMapping(R.class.getTypeName() + " -> " + R.class.getTypeName() + ":")
+        .setMinApi(parameters.getRuntime())
+        .noTreeShaking()
+        .compile()
+        .addRunClasspathFiles(libraryCompileResult.writeToZip())
+        .run(parameters.getRuntime(), Runner.class)
+        .assertSuccessWithOutput("0");
+  }
+}
diff --git a/src/test/java/com/android/tools/r8/naming/applymapping/shared/R.java b/src/test/java/com/android/tools/r8/naming/applymapping/shared/R.java
new file mode 100644
index 0000000..1c19e96
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/naming/applymapping/shared/R.java
@@ -0,0 +1,10 @@
+// Copyright (c) 2019, 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.applymapping.shared;
+
+public class R {
+
+  public final int identifier = 0;
+}