--- a/dom/bindings/Codegen.py
+++ b/dom/bindings/Codegen.py
@@ -4468,21 +4468,25 @@ def handleDefaultStringValue(defaultValu
             "%(method)s(data, ArrayLength(data) - 1)") % {
                 'char_t': "char" if defaultValue.type.isByteString() else "char16_t",
                 'method': method,
                 'data': ", ".join(["'" + char + "'" for char in
                                    defaultValue.value] + ["0"])
             }
 
 
-def recordKeyDeclType(recordType):
+def recordKeyType(recordType):
     assert recordType.keyType.isString()
     if recordType.keyType.isByteString():
-        return CGGeneric("nsCString")
-    return CGGeneric("nsString")
+        return "nsCString"
+    return "nsString"
+
+
+def recordKeyDeclType(recordType):
+    return CGGeneric(recordKeyType(recordType))
 
 
 # If this function is modified, modify CGNativeMember.getArg and
 # CGNativeMember.getRetvalInfo accordingly.  The latter cares about the decltype
 # and holdertype we end up using, because it needs to be able to return the code
 # that will convert those to the actual return value of the callback function.
 def getJSToNativeConversionInfo(type, descriptorProvider, failureCode=None,
                                 isDefinitelyObject=False,
@@ -4880,16 +4884,25 @@ def getJSToNativeConversionInfo(type, de
             "declName": "slot",
             # We only need holderName here to handle isExternal()
             # interfaces, which use an internal holder for the
             # conversion even when forceOwningType ends up true.
             "holderName": "tempHolder",
             "passedToJSImpl": "${passedToJSImpl}"
         })
 
+        keyType = recordKeyType(recordType)
+        if recordType.keyType.isDOMString():
+            keyConversionFunction = "ConvertJSValueToString"
+        elif recordType.keyType.isUSVString():
+            keyConversionFunction = "ConvertJSValueToUSVString"
+        else:
+            assert recordType.keyType.isByteString()
+            keyConversionFunction = "ConvertJSValueToByteString"
+
         templateBody = fill(
             """
             auto& recordEntries = ${recordRef}.Entries();
 
             JS::Rooted<JSObject*> recordObj(cx, &$${val}.toObject());
             JS::AutoIdVector ids(cx);
             // Keep skipping symbols until
             // https://github.com/heycam/webidl/issues/294 is sorted out.
@@ -4899,53 +4912,55 @@ def getJSToNativeConversionInfo(type, de
             }
             if (!recordEntries.SetCapacity(ids.length(), mozilla::fallible)) {
               JS_ReportOutOfMemory(cx);
               $*{exceptionCode}
             }
             JS::Rooted<JS::Value> propNameValue(cx);
             JS::Rooted<JS::Value> temp(cx);
             JS::Rooted<jsid> curId(cx);
+            JS::Rooted<JS::Value> idVal(cx);
             for (size_t i = 0; i < ids.length(); ++i) {
               curId = ids[i];
 
               MOZ_ASSERT(!JSID_IS_SYMBOL(curId), "No symbols, we said!");
 
               JS::Rooted<JS::PropertyDescriptor> desc(cx);
               if (!JS_GetOwnPropertyDescriptorById(cx, recordObj, curId,
                                                    &desc)) {
                 $*{exceptionCode}
               }
 
               if (!desc.object() /* == undefined in spec terms */ ||
                   !desc.enumerable()) {
                 continue;
               }
 
-              binding_detail::FakeString propName;
-              bool isSymbol;
-              if (!ConvertIdToString(cx, curId, propName, isSymbol)) {
+              idVal = js::IdToValue(curId);
+              ${keyType} propName;
+              if (!${keyConversionFunction}(cx, idVal, propName)) {
                 $*{exceptionCode}
               }
-              MOZ_ASSERT(!isSymbol, "We said, no symbols!");
 
               if (!JS_GetPropertyById(cx, recordObj, curId, &temp)) {
                 $*{exceptionCode}
               }
 
               // Safe to do an infallible append here, because we did a
               // SetCapacity above to the right capacity.
               ${typeName}::EntryType* entry = recordEntries.AppendElement();
               entry->mKey = propName;
               ${valueType}& slot = entry->mValue;
               $*{valueConversion}
             }
             """,
             exceptionCode=exceptionCode,
             recordRef=recordRef,
+            keyType=keyType,
+            keyConversionFunction=keyConversionFunction,
             typeName=typeName,
             valueType=valueInfo.declType.define(),
             valueConversion=valueConversion)
 
         templateBody = wrapObjectTemplate(templateBody, type,
                                           "${declName}.SetNull();\n",
                                           notRecord)
 
@@ -6553,16 +6568,28 @@ def getWrapTemplateForType(type, descrip
                 'jsvalRef': "tmp",
                 'jsvalHandle': "&tmp",
                 'returnsNewObject': returnsNewObject,
                 'exceptionCode': exceptionCode,
                 'obj': "returnObj",
                 'typedArraysAreStructs': typedArraysAreStructs
             })
         recordWrapLevel -= 1
+        if type.keyType.isByteString():
+            # There is no length-taking JS_DefineProperty.  So to keep
+            # things sane with embedded nulls, we want to byte-inflate
+            # to an nsAString.  The only byte-inflation function we
+            # have around is AppendASCIItoUTF16, which luckily doesn't
+            # assert anything about the input being ASCII.
+            expandedKeyDecl = "NS_ConvertASCIItoUTF16 expandedKey(entry.mKey);\n"
+            keyName = "expandedKey"
+        else:
+            expandedKeyDecl = ""
+            keyName = "entry.mKey"
+
         code = fill(
             """
 
             JS::Rooted<JSObject*> returnObj(cx, JS_NewPlainObject(cx));
             if (!returnObj) {
               $*{exceptionCode}
             }
             // Scope for 'tmp'
@@ -6570,30 +6597,33 @@ def getWrapTemplateForType(type, descrip
               JS::Rooted<JS::Value> tmp(cx);
               for (auto& entry : ${result}.Entries()) {
                 auto& ${valueName} = entry.mValue;
                 // Control block to let us common up the JS_DefineUCProperty calls when there
                 // are different ways to succeed at wrapping the value.
                 do {
                   $*{innerTemplate}
                 } while (0);
+                $*{expandedKeyDecl}
                 if (!JS_DefineUCProperty(cx, returnObj,
-                                         entry.mKey.BeginReading(),
-                                         entry.mKey.Length(), tmp,
+                                         ${keyName}.BeginReading(),
+                                         ${keyName}.Length(), tmp,
                                          JSPROP_ENUMERATE)) {
                   $*{exceptionCode}
                 }
               }
             }
             $*{set}
             """,
             result=result,
             exceptionCode=exceptionCode,
             valueName=valueName,
             innerTemplate=innerTemplate,
+            expandedKeyDecl=expandedKeyDecl,
+            keyName=keyName,
             set=setObject("*returnObj"))
 
         return (code, False)
 
     if type.isPromise():
         assert not type.nullable()
         # The use of ToJSValue here is a bit annoying because the Promise
         # version is not inlined.  But we can't put an inline version in either

--- a/dom/bindings/Record.h
+++ b/dom/bindings/Record.h
@@ -42,17 +42,17 @@ public:
 };
 
 } // namespace binding_detail
 
 template<typename KeyType, typename ValueType>
 class Record
 {
 public:
-  typedef typename binding_detail::RecordEntry<nsString, ValueType> EntryType;
+  typedef typename binding_detail::RecordEntry<KeyType, ValueType> EntryType;
   typedef Record<KeyType, ValueType> SelfType;
 
   Record()
   {
   }
 
   // Move constructor so we can do Record of Record.
   Record(SelfType&& aOther) :

--- a/dom/fetch/InternalHeaders.cpp
+++ b/dom/fetch/InternalHeaders.cpp
@@ -304,17 +304,17 @@ InternalHeaders::Fill(const Sequence<Seq
     Append(tuple[0], tuple[1], aRv);
   }
 }
 
 void
 InternalHeaders::Fill(const Record<nsCString, nsCString>& aInit, ErrorResult& aRv)
 {
   for (auto& entry : aInit.Entries()) {
-    Append(NS_ConvertUTF16toUTF8(entry.mKey), entry.mValue, aRv);
+    Append(entry.mKey, entry.mValue, aRv);
     if (aRv.Failed()) {
       return;
     }
   }
 }
 
 namespace {