diff --git a/pkg/analyzer/lib/src/dart/element/replacement_visitor.dart b/pkg/analyzer/lib/src/dart/element/replacement_visitor.dart
index e02c15f..d58ef88 100644
--- a/pkg/analyzer/lib/src/dart/element/replacement_visitor.dart
+++ b/pkg/analyzer/lib/src/dart/element/replacement_visitor.dart
@@ -139,6 +139,24 @@
     );
   }
 
+  RecordTypeImpl? createRecordType({
+    required RecordTypeImpl type,
+    required InstantiatedTypeAliasElement? newAlias,
+    required List<DartType>? newFieldTypes,
+    required NullabilitySuffix? newNullability,
+  }) {
+    if (newAlias == null && newFieldTypes == null && newNullability == null) {
+      return null;
+    }
+
+    return RecordTypeImpl(
+      element2: type.element2,
+      fieldTypes: newFieldTypes ?? type.fieldTypes,
+      nullabilitySuffix: newNullability ?? type.nullabilitySuffix,
+      alias: newAlias ?? type.alias,
+    );
+  }
+
   DartType? createTypeParameterType({
     required TypeParameterType type,
     required NullabilitySuffix? newNullability,
@@ -423,9 +441,32 @@
   }
 
   @override
-  DartType? visitRecordType(RecordType type) {
-    // TODO: implement visitRecordType
-    throw UnimplementedError();
+  DartType? visitRecordType(covariant RecordTypeImpl type) {
+    var newNullability = visitNullability(type);
+
+    InstantiatedTypeAliasElement? newAlias;
+    var alias = type.alias;
+    if (alias != null) {
+      var newArguments = _typeArguments(
+        alias.element.typeParameters,
+        alias.typeArguments,
+      );
+      if (newArguments != null) {
+        newAlias = InstantiatedTypeAliasElementImpl(
+          element: alias.element,
+          typeArguments: newArguments,
+        );
+      }
+    }
+
+    final newFieldTypes = _typeList(type.fieldTypes);
+
+    return createRecordType(
+      type: type,
+      newAlias: newAlias,
+      newFieldTypes: newFieldTypes,
+      newNullability: newNullability,
+    );
   }
 
   DartType? visitTypeArgument(
@@ -488,4 +529,17 @@
 
     return newArguments;
   }
+
+  List<DartType>? _typeList(List<DartType> arguments) {
+    List<DartType>? newArguments;
+    for (var i = 0; i < arguments.length; i++) {
+      var substitution = arguments[i].accept(this);
+      if (substitution != null) {
+        newArguments ??= arguments.toList(growable: false);
+        newArguments[i] = substitution;
+      }
+    }
+
+    return newArguments;
+  }
 }
diff --git a/pkg/analyzer/test/generated/elements_types_mixin.dart b/pkg/analyzer/test/generated/elements_types_mixin.dart
index 592a74d..9c1da07 100644
--- a/pkg/analyzer/test/generated/elements_types_mixin.dart
+++ b/pkg/analyzer/test/generated/elements_types_mixin.dart
@@ -560,12 +560,18 @@
   }
 
   RecordElementImpl recordElement({
-    List<RecordPositionalFieldElementImpl> positionalFields = const [],
-    List<RecordNamedFieldElementImpl> namedFields = const [],
+    List<DartType> positionalTypes = const [],
+    Map<String, DartType> namedTypes = const {},
   }) {
     return RecordElementImpl(
-      positionalFields: positionalFields,
-      namedFields: namedFields,
+      positionalFields: positionalTypes.map(
+        (fieldType) {
+          return recordPositionalField(type: fieldType);
+        },
+      ).toList(),
+      namedFields: namedTypes.entries.map((entry) {
+        return recordNamedField(name: entry.key, type: entry.value);
+      }).toList(),
     );
   }
 
@@ -590,14 +596,52 @@
     );
   }
 
-  RecordTypeImpl recordTypeNone({
-    required RecordElementImpl element,
+  RecordTypeImpl recordType({
+    List<DartType> positionalTypes = const [],
+    Map<String, DartType> namedTypes = const {},
+    required NullabilitySuffix nullabilitySuffix,
   }) {
-    return element.instantiate(
+    return recordElement(
+      positionalTypes: positionalTypes,
+      namedTypes: namedTypes,
+    ).instantiate(
+      nullabilitySuffix: nullabilitySuffix,
+    );
+  }
+
+  RecordTypeImpl recordTypeNone({
+    List<DartType> positionalTypes = const [],
+    Map<String, DartType> namedTypes = const {},
+  }) {
+    return recordType(
+      positionalTypes: positionalTypes,
+      namedTypes: namedTypes,
       nullabilitySuffix: NullabilitySuffix.none,
     );
   }
 
+  RecordTypeImpl recordTypeQuestion({
+    List<DartType> positionalTypes = const [],
+    Map<String, DartType> namedTypes = const {},
+  }) {
+    return recordType(
+      positionalTypes: positionalTypes,
+      namedTypes: namedTypes,
+      nullabilitySuffix: NullabilitySuffix.question,
+    );
+  }
+
+  RecordTypeImpl recordTypeStar({
+    List<DartType> positionalTypes = const [],
+    Map<String, DartType> namedTypes = const {},
+  }) {
+    return recordType(
+      positionalTypes: positionalTypes,
+      namedTypes: namedTypes,
+      nullabilitySuffix: NullabilitySuffix.star,
+    );
+  }
+
   ParameterElement requiredParameter({
     String? name,
     required DartType type,
diff --git a/pkg/analyzer/test/src/dart/element/normalize_type_test.dart b/pkg/analyzer/test/src/dart/element/normalize_type_test.dart
index aa6ea5d..da0f5a2 100644
--- a/pkg/analyzer/test/src/dart/element/normalize_type_test.dart
+++ b/pkg/analyzer/test/src/dart/element/normalize_type_test.dart
@@ -341,52 +341,40 @@
   test_recordType() {
     _check(
       recordTypeNone(
-        element: recordElement(
-          positionalFields: [
-            recordPositionalField(type: intNone),
-          ],
-        ),
+        positionalTypes: [
+          intNone,
+        ],
       ),
       recordTypeNone(
-        element: recordElement(
-          positionalFields: [
-            recordPositionalField(type: intNone),
-          ],
-        ),
+        positionalTypes: [
+          intNone,
+        ],
       ),
     );
 
     _check(
       recordTypeNone(
-        element: recordElement(
-          positionalFields: [
-            recordPositionalField(type: futureOrNone(objectNone)),
-          ],
-        ),
+        positionalTypes: [
+          futureOrNone(objectNone),
+        ],
       ),
       recordTypeNone(
-        element: recordElement(
-          positionalFields: [
-            recordPositionalField(type: objectNone),
-          ],
-        ),
+        positionalTypes: [
+          objectNone,
+        ],
       ),
     );
 
     _check(
       recordTypeNone(
-        element: recordElement(
-          namedFields: [
-            recordNamedField(name: 'foo', type: futureOrNone(objectNone)),
-          ],
-        ),
+        namedTypes: {
+          'foo': futureOrNone(objectNone),
+        },
       ),
       recordTypeNone(
-        element: recordElement(
-          namedFields: [
-            recordNamedField(name: 'foo', type: objectNone),
-          ],
-        ),
+        namedTypes: {
+          'foo': objectNone,
+        },
       ),
     );
   }
diff --git a/pkg/analyzer/test/src/dart/element/nullability_eliminator_test.dart b/pkg/analyzer/test/src/dart/element/nullability_eliminator_test.dart
index 05c1d38..aef063f 100644
--- a/pkg/analyzer/test/src/dart/element/nullability_eliminator_test.dart
+++ b/pkg/analyzer/test/src/dart/element/nullability_eliminator_test.dart
@@ -10,6 +10,7 @@
 import 'package:test_reflective_loader/test_reflective_loader.dart';
 
 import '../../../generated/type_system_base.dart';
+import 'string_types.dart';
 
 main() {
   defineReflectiveSuite(() {
@@ -18,7 +19,14 @@
 }
 
 @reflectiveTest
-class NullabilityEliminatorTest extends AbstractTypeSystemTest {
+class NullabilityEliminatorTest extends AbstractTypeSystemTest
+    with StringTypes {
+  @override
+  void setUp() {
+    super.setUp();
+    defineStringTypes();
+  }
+
   test_dynamicType() {
     _verifySame(typeProvider.dynamicType);
   }
@@ -312,6 +320,61 @@
     _verify(listStar(neverNone), listStar(nullStar));
   }
 
+  test_recordType_fromAlias() {
+    var T = typeParameter('T');
+    var A = typeAlias(
+      name: 'A',
+      typeParameters: [T],
+      aliasedType: recordTypeNone(
+        positionalTypes: [
+          typeParameterTypeNone(T),
+        ],
+      ),
+    );
+
+    var input = A.instantiate(
+      typeArguments: [intNone],
+      nullabilitySuffix: NullabilitySuffix.none,
+    );
+    expect(_typeToString(input), '(int)');
+
+    var result = NullabilityEliminator.perform(typeProvider, input);
+    expect(_typeToString(result), '(int*)*');
+    _assertInstantiatedAlias(result, A, 'int*');
+  }
+
+  test_recordType_named() {
+    final expected = '({int* f1})*';
+
+    _verify2('({int f1})', expected);
+    _verify2('({int? f1})', expected);
+    _verify2('({int* f1})', expected);
+
+    _verify2('({int f1})?', expected);
+    _verify2('({int? f1})?', expected);
+    _verify2('({int* f1})?', expected);
+
+    _verify2('({int f1})*', expected);
+    _verify2('({int? f1})*', expected);
+    _verifySame(typeOfString(expected));
+  }
+
+  test_recordType_positional() {
+    final expected = '(int*)*';
+
+    _verify2('(int)', expected);
+    _verify2('(int?)', expected);
+    _verify2('(int*)', expected);
+
+    _verify2('(int)?', expected);
+    _verify2('(int?)?', expected);
+    _verify2('(int*)?', expected);
+
+    _verify2('(int)*', expected);
+    _verify2('(int?)*', expected);
+    _verifySame(typeOfString(expected));
+  }
+
   test_typeParameterType() {
     var T = typeParameter('T');
     _verify(
@@ -348,6 +411,10 @@
     expect(result, expected);
   }
 
+  void _verify2(String input, String expected) {
+    _verify(typeOfString(input), typeOfString(expected));
+  }
+
   void _verifySame(DartType input) {
     var result = NullabilityEliminator.perform(typeProvider, input);
     expect(result, same(input));
diff --git a/pkg/analyzer/test/src/dart/element/string_types.dart b/pkg/analyzer/test/src/dart/element/string_types.dart
index 2081d30..883cfe5 100644
--- a/pkg/analyzer/test/src/dart/element/string_types.dart
+++ b/pkg/analyzer/test/src/dart/element/string_types.dart
@@ -409,18 +409,9 @@
       Map<String, DartType> namedTypes,
     ) {
       final type = recordTypeNone(
-        element: recordElement(
-          positionalFields: positionalTypes.map(
-            (fieldType) {
-              return recordPositionalField(type: fieldType);
-            },
-          ).toList(),
-          namedFields: namedTypes.entries.map((entry) {
-            return recordNamedField(name: entry.key, type: entry.value);
-          }).toList(),
-        ),
+        positionalTypes: positionalTypes,
+        namedTypes: namedTypes,
       );
-      expect(type.toString(), str);
       _defineType(str, type);
     }
 
@@ -428,12 +419,34 @@
       mixed(str, types, const {});
     }
 
+    void allPositionalQuestion(String str, List<DartType> types) {
+      final type = recordTypeQuestion(
+        positionalTypes: types,
+      );
+      _defineType(str, type);
+    }
+
+    void allPositionalStar(String str, List<DartType> types) {
+      final type = recordTypeStar(
+        positionalTypes: types,
+      );
+      _defineType(str, type);
+    }
+
     allPositional('(double)', [doubleNone]);
     allPositional('(int)', [intNone]);
     allPositional('(int?)', [intQuestion]);
     allPositional('(int*)', [intStar]);
     allPositional('(num)', [numNone]);
 
+    allPositionalQuestion('(int)?', [intNone]);
+    allPositionalQuestion('(int?)?', [intQuestion]);
+    allPositionalQuestion('(int*)?', [intStar]);
+
+    allPositionalStar('(int)*', [intNone]);
+    allPositionalStar('(int?)*', [intQuestion]);
+    allPositionalStar('(int*)*', [intStar]);
+
     allPositional('(double, int)', [doubleNone, intNone]);
     allPositional('(int, double)', [intNone, doubleNone]);
     allPositional('(int, int)', [intNone, intNone]);
@@ -447,6 +460,20 @@
       mixed(str, const [], types);
     }
 
+    void allNamedQuestion(String str, Map<String, DartType> types) {
+      final type = recordTypeQuestion(
+        namedTypes: types,
+      );
+      _defineType(str, type);
+    }
+
+    void allNamedStar(String str, Map<String, DartType> types) {
+      final type = recordTypeStar(
+        namedTypes: types,
+      );
+      _defineType(str, type);
+    }
+
     allNamed('({double f1})', {'f1': doubleNone});
     allNamed('({int f1})', {'f1': intNone});
     allNamed('({int? f1})', {'f1': intQuestion});
@@ -454,6 +481,14 @@
     allNamed('({num f1})', {'f1': numNone});
     allNamed('({int f2})', {'f2': intNone});
 
+    allNamedQuestion('({int f1})?', {'f1': intNone});
+    allNamedQuestion('({int? f1})?', {'f1': intQuestion});
+    allNamedQuestion('({int* f1})?', {'f1': intStar});
+
+    allNamedStar('({int f1})*', {'f1': intNone});
+    allNamedStar('({int? f1})*', {'f1': intQuestion});
+    allNamedStar('({int* f1})*', {'f1': intStar});
+
     allNamed('({double f1, int f2})', {'f1': doubleNone, 'f2': intNone});
     allNamed('({int f1, double f2})', {'f1': intNone, 'f2': doubleNone});
     allNamed('({int f1, int f2})', {'f1': intNone, 'f2': intNone});
diff --git a/pkg/analyzer/test/src/dart/element/subtype_test.dart b/pkg/analyzer/test/src/dart/element/subtype_test.dart
index ee31ff1e..46cdf59 100644
--- a/pkg/analyzer/test/src/dart/element/subtype_test.dart
+++ b/pkg/analyzer/test/src/dart/element/subtype_test.dart
@@ -4166,24 +4166,20 @@
 
     check(
       recordTypeNone(
-        element: recordElement(
-          namedFields: [
-            recordNamedField(name: 'f1', type: intNone),
-            recordNamedField(name: 'f2', type: intNone),
-            recordNamedField(name: 'f3', type: intNone),
-            recordNamedField(name: 'f4', type: intNone),
-          ],
-        ),
+        namedTypes: {
+          'f1': intNone,
+          'f2': intNone,
+          'f3': intNone,
+          'f4': intNone,
+        },
       ),
       recordTypeNone(
-        element: recordElement(
-          namedFields: [
-            recordNamedField(name: 'f4', type: intNone),
-            recordNamedField(name: 'f3', type: intNone),
-            recordNamedField(name: 'f2', type: intNone),
-            recordNamedField(name: 'f1', type: intNone),
-          ],
-        ),
+        namedTypes: {
+          'f4': intNone,
+          'f3': intNone,
+          'f2': intNone,
+          'f1': intNone,
+        },
       ),
     );
   }
diff --git a/pkg/analyzer/test/src/dart/element/type_algebra_test.dart b/pkg/analyzer/test/src/dart/element/type_algebra_test.dart
index e355e61..36e0c11 100644
--- a/pkg/analyzer/test/src/dart/element/type_algebra_test.dart
+++ b/pkg/analyzer/test/src/dart/element/type_algebra_test.dart
@@ -381,11 +381,7 @@
     final T = typeParameter('T');
 
     final type = recordTypeNone(
-      element: recordElement(
-        positionalFields: [
-          recordPositionalField(type: intNone),
-        ],
-      ),
+      positionalTypes: [intNone],
     );
 
     assertType(type, '(int)');
@@ -399,12 +395,7 @@
       name: 'Alias',
       typeParameters: [T],
       aliasedType: recordTypeNone(
-        element: recordElement(
-          positionalFields: [
-            recordPositionalField(type: intNone),
-            recordPositionalField(type: stringNone),
-          ],
-        ),
+        positionalTypes: [intNone, stringNone],
       ),
     );
 
@@ -424,12 +415,10 @@
       name: 'Alias',
       typeParameters: [T],
       aliasedType: recordTypeNone(
-        element: recordElement(
-          positionalFields: [
-            recordPositionalField(type: T_none),
-            recordPositionalField(type: listNone(T_none)),
-          ],
-        ),
+        positionalTypes: [
+          T_none,
+          listNone(T_none),
+        ],
       ),
     );
 
@@ -442,12 +431,10 @@
     final T_none = typeParameterTypeNone(T);
 
     final type = recordTypeNone(
-      element: recordElement(
-        namedFields: [
-          recordNamedField(name: 'f1', type: T_none),
-          recordNamedField(name: 'f2', type: listNone(T_none)),
-        ],
-      ),
+      namedTypes: {
+        'f1': T_none,
+        'f2': listNone(T_none),
+      },
     );
 
     assertType(type, '({T f1, List<T> f2})');
@@ -459,12 +446,10 @@
     final T_none = typeParameterTypeNone(T);
 
     final type = recordTypeNone(
-      element: recordElement(
-        positionalFields: [
-          recordPositionalField(type: T_none),
-          recordPositionalField(type: listNone(T_none)),
-        ],
-      ),
+      positionalTypes: [
+        T_none,
+        listNone(T_none),
+      ],
     );
 
     assertType(type, '(T, List<T>)');