diff --git a/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart b/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart
index 706a85d..6769e5c 100644
--- a/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart
+++ b/pkg/front_end/lib/src/fasta/fasta_codes_generated.dart
@@ -4935,30 +4935,6 @@
 }
 
 // DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
-const Template<Message Function(String name)>
-    templateInternalProblemSuperclassNotFound =
-    const Template<Message Function(String name)>(
-        messageTemplate: r"""Superclass not found '#name'.""",
-        withArguments: _withArgumentsInternalProblemSuperclassNotFound);
-
-// DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
-const Code<Message Function(String name)>
-    codeInternalProblemSuperclassNotFound =
-    const Code<Message Function(String name)>(
-        "InternalProblemSuperclassNotFound",
-        templateInternalProblemSuperclassNotFound,
-        severity: Severity.internalProblem);
-
-// DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
-Message _withArgumentsInternalProblemSuperclassNotFound(String name) {
-  if (name.isEmpty) throw 'No name provided';
-  name = demangleMixinApplicationName(name);
-  return new Message(codeInternalProblemSuperclassNotFound,
-      message: """Superclass not found '${name}'.""",
-      arguments: {'name': name});
-}
-
-// DO NOT EDIT. THIS FILE IS GENERATED. SEE TOP OF FILE.
 const Template<Message Function(String string, String string2)>
     templateInternalProblemUnexpected =
     const Template<Message Function(String string, String string2)>(
diff --git a/pkg/front_end/lib/src/fasta/kernel/kernel_class_builder.dart b/pkg/front_end/lib/src/fasta/kernel/kernel_class_builder.dart
index b913847..56bc3b2 100644
--- a/pkg/front_end/lib/src/fasta/kernel/kernel_class_builder.dart
+++ b/pkg/front_end/lib/src/fasta/kernel/kernel_class_builder.dart
@@ -41,7 +41,7 @@
 
 import 'package:kernel/core_types.dart' show CoreTypes;
 
-import 'package:kernel/type_algebra.dart' show Substitution;
+import 'package:kernel/type_algebra.dart' show Substitution, substitute;
 
 import 'package:kernel/type_algebra.dart' as type_algebra
     show getSubstitutionMap;
@@ -73,7 +73,6 @@
         templateIncorrectTypeArgumentInSupertype,
         templateIncorrectTypeArgumentInSupertypeInferred,
         templateInterfaceCheckContext,
-        templateInternalProblemSuperclassNotFound,
         templateMissingImplementationCause,
         templateMissingImplementationNotAbstract,
         templateMixinApplicationIncompatibleSupertype,
@@ -96,8 +95,7 @@
 
 import '../names.dart' show noSuchMethodName;
 
-import '../problems.dart'
-    show internalProblem, unexpected, unhandled, unimplemented;
+import '../problems.dart' show unexpected, unhandled, unimplemented;
 
 import '../type_inference/type_schema.dart' show UnknownType;
 
@@ -116,11 +114,8 @@
         LibraryBuilder,
         MemberBuilder,
         MetadataBuilder,
-        MixinApplicationBuilder,
-        NamedTypeBuilder,
         ProcedureBuilder,
         Scope,
-        TypeBuilder,
         TypeVariableBuilder;
 
 import 'redirecting_factory_body.dart'
@@ -1741,66 +1736,30 @@
   ///
   ///     [[BeatBox]].getSubstitutionMap([[Box]]) -> {[[Box::T]]: Beat]]}.
   ///
-  /// This method returns null if the map is empty, and it's an error if
-  /// [superclass] isn't a superclass.
-  Map<TypeParameter, DartType> getSubstitutionMap(ClassBuilder superclass,
-      Uri fileUri, int charOffset, TypeBuilder dynamicType) {
-    TypeBuilder supertype = this.supertype;
-    Map<TypeVariableBuilder, TypeBuilder> substitutionMap;
-    List arguments;
-    List variables;
-    Declaration declaration;
+  /// It's an error if [superclass] isn't a superclass.
+  Map<TypeParameter, DartType> getSubstitutionMap(Class superclass) {
+    Supertype supertype = target.supertype;
+    Map<TypeParameter, DartType> substitutionMap = <TypeParameter, DartType>{};
+    List<DartType> arguments;
+    List<TypeParameter> variables;
+    Class classNode;
 
-    /// If [application] is mixing in [superclass] directly or via other named
-    /// mixin applications, return it.
-    NamedTypeBuilder findSuperclass(MixinApplicationBuilder application) {
-      for (TypeBuilder t in application.mixins) {
-        if (t is NamedTypeBuilder) {
-          if (t.declaration == superclass) return t;
-        } else if (t is MixinApplicationBuilder) {
-          NamedTypeBuilder s = findSuperclass(t);
-          if (s != null) return s;
-        }
-      }
-      return null;
-    }
-
-    void handleNamedTypeBuilder(NamedTypeBuilder t) {
-      declaration = t.declaration;
-      arguments = t.arguments ?? const [];
-      if (declaration is ClassBuilder) {
-        ClassBuilder cls = declaration;
-        variables = cls.typeVariables;
-        supertype = cls.supertype;
-      }
-    }
-
-    while (declaration != superclass) {
-      variables = null;
-      if (supertype is NamedTypeBuilder) {
-        handleNamedTypeBuilder(supertype);
-      } else if (supertype is MixinApplicationBuilder) {
-        MixinApplicationBuilder t = supertype;
-        NamedTypeBuilder s = findSuperclass(t);
-        if (s != null) {
-          handleNamedTypeBuilder(s);
-        }
-        supertype = t.supertype;
-      } else {
-        internalProblem(
-            templateInternalProblemSuperclassNotFound
-                .withArguments(superclass.fullNameForErrors),
-            charOffset,
-            fileUri);
-      }
-      if (variables != null) {
-        Map<TypeVariableBuilder, TypeBuilder> directSubstitutionMap =
-            <TypeVariableBuilder, TypeBuilder>{};
+    while (classNode != superclass) {
+      classNode = supertype.classNode;
+      arguments = supertype.typeArguments;
+      variables = classNode.typeParameters;
+      supertype = classNode.supertype;
+      if (variables.isNotEmpty) {
+        Map<TypeParameter, DartType> directSubstitutionMap =
+            <TypeParameter, DartType>{};
         for (int i = 0; i < variables.length; i++) {
-          TypeBuilder argument =
-              i < arguments.length ? arguments[i] : dynamicType;
+          DartType argument =
+              i < arguments.length ? arguments[i] : const DynamicType();
           if (substitutionMap != null) {
-            argument = argument.subst(substitutionMap);
+            // TODO(ahe): Investigate if requiring the caller to use
+            // `substituteDeep` from `package:kernel/type_algebra.dart` instead
+            // of `substitute` is faster. If so, we can simply this code.
+            argument = substitute(argument, substitutionMap);
           }
           directSubstitutionMap[variables[i]] = argument;
         }
@@ -1808,13 +1767,6 @@
       }
     }
 
-    if (substitutionMap == null) return const <TypeParameter, DartType>{};
-
-    Map<TypeParameter, DartType> result = <TypeParameter, DartType>{};
-    substitutionMap
-        .forEach((TypeVariableBuilder variable, TypeBuilder argument) {
-      result[variable.target] = argument.build(library);
-    });
-    return result;
+    return substitutionMap;
   }
 }
diff --git a/pkg/front_end/lib/src/fasta/kernel/kernel_target.dart b/pkg/front_end/lib/src/fasta/kernel/kernel_target.dart
index fd807fc..8354ddb 100644
--- a/pkg/front_end/lib/src/fasta/kernel/kernel_target.dart
+++ b/pkg/front_end/lib/src/fasta/kernel/kernel_target.dart
@@ -481,8 +481,7 @@
         builder.addSyntheticConstructor(makeDefaultConstructor(builder.target));
       } else {
         Map<TypeParameter, DartType> substitutionMap =
-            builder.getSubstitutionMap(
-                supertype, builder.fileUri, builder.charOffset, dynamicType);
+            builder.getSubstitutionMap(supertype.target);
         for (Constructor constructor in supertype.cls.constructors) {
           builder.addSyntheticConstructor(makeMixinApplicationConstructor(
               builder.target, builder.cls.mixin, constructor, substitutionMap));
diff --git a/pkg/front_end/messages.yaml b/pkg/front_end/messages.yaml
index 5d3e0cf..60bb455 100644
--- a/pkg/front_end/messages.yaml
+++ b/pkg/front_end/messages.yaml
@@ -1576,10 +1576,6 @@
   template: "Unsupported operation: '#name'."
   severity: INTERNAL_PROBLEM
 
-InternalProblemSuperclassNotFound:
-  template: "Superclass not found '#name'."
-  severity: INTERNAL_PROBLEM
-
 InternalProblemNotFound:
   template: "Couldn't find '#name'."
   severity: INTERNAL_PROBLEM
diff --git a/pkg/front_end/test/issue_34856_test.dart b/pkg/front_end/test/issue_34856_test.dart
new file mode 100644
index 0000000..c3f6693
--- /dev/null
+++ b/pkg/front_end/test/issue_34856_test.dart
@@ -0,0 +1,108 @@
+// Copyright (c) 2018, the Dart 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.
+
+import 'dart:io' show File;
+
+import 'package:async_helper/async_helper.dart' show asyncTest;
+
+import 'package:front_end/src/api_prototype/compiler_options.dart'
+    show CompilerOptions;
+
+import 'package:front_end/src/api_prototype/kernel_generator.dart'
+    show kernelForComponent;
+
+import 'package:front_end/src/api_prototype/memory_file_system.dart'
+    show MemoryFileSystem;
+
+import 'package:front_end/src/base/processed_options.dart'
+    show ProcessedOptions;
+
+import 'package:front_end/src/compute_platform_binaries_location.dart'
+    show computePlatformBinariesLocation;
+
+import 'package:front_end/src/fasta/compiler_context.dart' show CompilerContext;
+
+import 'package:front_end/src/fasta/kernel/utils.dart' show serializeComponent;
+
+import 'package:front_end/src/fasta/kernel/verifier.dart' show verifyComponent;
+
+import 'package:kernel/ast.dart' show Component;
+
+const Map<String, String> files = const <String, String>{
+  "repro.dart": """
+
+import 'lib.dart';
+
+abstract class M<M_K, M_V> implements Map<M_K, Set<M_V>> {}
+
+abstract class C<C_K, C_V> extends UnmodifiableMapView<C_K, Set<C_V>>
+    with M<C_K, C_V> {
+  C._() : super(null);
+}
+""",
+  "lib.dart": """abstract class MapView<K, V> {
+  const MapView(Map<K, V> map);
+}
+
+abstract class _UnmodifiableMapMixin<K, V> {}
+
+abstract class UnmodifiableMapView<K, V> extends MapView<K, V>
+    with _UnmodifiableMapMixin<K, V> {
+  UnmodifiableMapView(Map<K, V> map) : super(map);
+}""",
+};
+
+Future<void> test() async {
+  final String platformBaseName = "vm_platform_strong.dill";
+  final Uri base = Uri.parse("org-dartlang-test:///");
+  final Uri platformDill = base.resolve(platformBaseName);
+  final List<int> platformDillBytes = await new File.fromUri(
+          computePlatformBinariesLocation(forceBuildDir: true)
+              .resolve(platformBaseName))
+      .readAsBytes();
+  MemoryFileSystem fs = new MemoryFileSystem(base);
+  fs.entityForUri(platformDill).writeAsBytesSync(platformDillBytes);
+  fs
+      .entityForUri(base.resolve("lib.dart"))
+      .writeAsStringSync(files["lib.dart"]);
+  CompilerOptions options = new CompilerOptions()
+    ..fileSystem = fs
+    ..sdkSummary = platformDill;
+
+  Component component =
+      await kernelForComponent(<Uri>[base.resolve("lib.dart")], options);
+
+  fs = new MemoryFileSystem(base);
+  fs.entityForUri(platformDill).writeAsBytesSync(platformDillBytes);
+  fs
+      .entityForUri(base.resolve("lib.dart.dill"))
+      .writeAsBytesSync(serializeComponent(component));
+  fs
+      .entityForUri(base.resolve("repro.dart"))
+      .writeAsStringSync(files["repro.dart"]);
+
+  options = new CompilerOptions()
+    ..fileSystem = fs
+    ..linkedDependencies = <Uri>[base.resolve("lib.dart.dill")]
+    ..sdkSummary = platformDill;
+
+  List<Uri> inputs = <Uri>[base.resolve("repro.dart")];
+
+  component = await kernelForComponent(inputs, options);
+
+  List<Object> errors = await CompilerContext.runWithOptions(
+      new ProcessedOptions(options: options, inputs: inputs),
+      (_) => new Future<List<Object>>.value(
+          verifyComponent(component, skipPlatform: true)));
+
+  serializeComponent(component);
+
+  if (errors.isNotEmpty) {
+    throw "Verification failed";
+  }
+}
+
+main() {
+  asyncTest(test);
+}