Melaksanakan Deep Clone dalam JavaScript

Masalah dan Konteks Berkenaan

Laksanakan deepClone(value). Input ialah graf objek terhingga daripada satu realm JavaScript. Ia mungkin mengandungi primitif, tatasusunan, objek biasa yang prototaipnya ialah Object.prototype atau null, Date, RegExp, Map, dan Set. Setiap objek sumber yang disokong mesti mempunyai objek yang berbeza dalam salinan. Jika dua edge sumber menunjuk kepada objek yang sama, edge salinan yang sepadan mesti menunjuk kepada objek salinan yang sama. Kitaran tidak boleh menyebabkan rekursi tanpa batas.

Fungsi ini juga mesti menyalin setiap data property milik sendiri (own data property), termasuk property bukan enumerable dan property ber-key symbol, sambil mengekalkan deskriptornya. Kekalkan kekosongan tatasusunan (array hole), nilai masa bagi Date, sumber, bendera, dan lastIndex bagi RegExp, kedua-dua key dan value bagi Map, serta value bagi Set.

Fungsi, accessor property, WeakMap, WeakSet, proksi, typed array, array buffer, tika kelas tersuai (custom class instances), dan built-in yang tidak disenaraikan berada di luar kontrak dan mesti menghasilkan TypeError. Pelaksanaan ini bersifat rekursif, jadi ia juga mengandaikan bahawa peneluran (nesting) tidak akan menghabiskan call stack. Untuk data pengeluaran yang mematuhi jenis structured-cloneable platform, nilaikan structuredClone sebelum menukar pelaksanaan temu duga ini menjadi pustaka kegunaan umum.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon mentakrifkan maksud “deep clone”. JavaScript tidak mempunyai peraturan peringkat pengguna yang universal yang boleh menghasilkan semula closure fungsi, nod DOM, medan peribadi, proksi, dan setiap internal slot built-in. Jawapan yang kukuh menyenaraikan jenis yang disokong, semantik property, kelakuan kitaran, dan kelakuan kegagalan sebelum menulis rekursi.

Isyarat kedua ialah mengenal pasti graf objek dan bukannya pepohon objek. Memperuntukkan objek secara rekursif boleh menyalin pepohon, tetapi ia tidak dapat mengendalikan source.self = source, dan secara salah menukar source.a === source.b kepada dua salinan yang berasingan. Keadaan yang diperlukan bukan sekadar “telah dilawati”; ia adalah “salinan mana yang dimiliki oleh objek sumber ini”.

Isyarat ketiga ialah susunan peruntukan. Peruntukkan sasaran kosong dan rekodkan pemetaan source-to-copy sebelum merentasi outgoing edge. Jika nod anak disalin sebelum pendaftaran, back edge yang pertama masih tidak menemui sasaran dan rekursi diteruskan di sekitar kitaran.

Isyarat keempat ialah penerangan jujur tentang batasan property dan built-in. Object.entries terlepas symbol key dan property bukan enumerable. Membaca source[key] boleh melaksanakan getter. Memberikan Date, Map, atau Set objek dengan prototaip yang sama tidak menghasilkan semula internal slot miliknya.

Soalan untuk Dijelaskan Sebelum Menjawab

• Jenis manakah yang mesti disokong? Tatasusunan dan objek biasa adalah mencukupi untuk data berbentuk JSON. Menambah Date, RegExp, Map, dan Set memerlukan pembinaan dan perentasan khusus mengikut jenis. Menambah typed array atau array buffer memperkenalkan pilihan penyalinan buffer dan pemilikan.
• Patutkah kitaran dan rujukan pendua gagal, diputuskan, atau mengekalkan topologi? Masalah ini mengekalkannya, jadi ia memerlukan pemetaan source-to-copy. WeakSet boleh mengesan pengulangan tetapi tidak boleh mengembalikan salinan yang betul.
• Adakah property bermaksud string key enumerable sahaja, atau juga symbol, bukan enumerable, dan deskriptor? Kontrak ini memilih yang kedua dan menolak accessor, mengelakkan kedua-dua pelaksanaan getter dan fungsi getter atau setter yang dikongsi.
• Adakah custom class dan rantai prototaip mesti disalin? Masalah ini hanya menerima objek biasa dan built-in yang disenaraikan. Object.create(instancePrototype) tidak dapat menghasilkan semula medan peribadi atau keadaan yang ditetapkan oleh pembina (constructor), jadi mempersembahkan hasilnya sebagai tika yang lengkap adalah mengelirukan.
• Adakah ini algoritma temu duga atau API pengeluaran? Pelaksanaan temu duga menunjukkan kontrak dan invarian graf. Kod pengeluaran harus membandingkan liputan jenis structuredClone, semantik pemindahan, dan kehilangan metadata sebelum memilih serializer tersuai yang terkawal.
• Apakah kedalaman peneluran (nesting) maksimum? Rekursi menggunakan stack bantuan O(d). Rantaian yang mungkin mengandungi seratus ribu objek memerlukan work stack eksplisit dan mengubah pelaksanaan serta ujian.

Rangka Jawapan 30 Saat

“Saya akan menentukan jenis yang disokong dan menganggap input sebagai satu graf. Nilai primitif dikembalikan secara langsung. Bagi setiap objek, saya menyemak WeakMap; pada lawatan pertamanya, saya memperuntukkan dan mendaftarkan salinan kosong sebelum menyalin property atau entri. Kitaran dan rujukan pendua kemudian diselesaikan kepada satu salinan. Date dan RegExp dibina semula, manakala fungsi, accessor, dan objek yang tidak disokong akan melontarkan ralat. Masa yang dijangkakan dan ruang salinan ialah O(V + E), dengan rekursi stack O(d).”

Penerokaan Mendalam Langkah Demi Langkah

JSON.parse(JSON.stringify(value)) hanya sah untuk kontrak JSON yang lebih sempit. Ia gagal pada kitaran dan mengubah atau kehilangan undefined, BigInt, symbol, Date, RegExp, Map, Set, dan nilai berangka khas. Rekursi biasa memberikan lebih kawalan, tetapi tanpa pemetaan source-to-copy ia masih hanya mengendalikan pepohon.

Invarian utamanya ialah: sebelum merentasi sebarang property atau entri objek yang disokong, seen.get(sourceObject) sudah sama dengan salinan unik yang diperuntukkan untuknya.

function deepClone(input) {
  const seen = new WeakMap();

  function clone(value) {
    if (typeof value === 'function') {
      throw new TypeError('Functions are not supported');
    }

    if (value === null || typeof value !== 'object') {
      return value;
    }

    if (seen.has(value)) {
      return seen.get(value);
    }

    let result;

    if (value instanceof Date) {
      result = new Date(value.getTime());
      seen.set(value, result);
      copyOwnDataProperties(value, result);
      return result;
    }

    if (value instanceof RegExp) {
      result = new RegExp(value.source, value.flags);
      result.lastIndex = value.lastIndex;
      seen.set(value, result);
      copyOwnDataProperties(value, result, new Set(['lastIndex']));
      return result;
    }

    if (value instanceof Map) {
      result = new Map();
      seen.set(value, result);
      for (const [key, item] of value) {
        result.set(clone(key), clone(item));
      }
      copyOwnDataProperties(value, result);
      return result;
    }

    if (value instanceof Set) {
      result = new Set();
      seen.set(value, result);
      for (const item of value) {
        result.add(clone(item));
      }
      copyOwnDataProperties(value, result);
      return result;
    }

    if (Array.isArray(value)) {
      result = new Array(value.length);
      seen.set(value, result);
      copyOwnDataProperties(value, result, new Set(['length']));
      Object.defineProperty(
        result,
        'length',
        Object.getOwnPropertyDescriptor(value, 'length'),
      );
      return result;
    }

    const prototype = Object.getPrototypeOf(value);
    if (prototype !== Object.prototype && prototype !== null) {
      throw new TypeError('Unsupported object type');
    }

    result = Object.create(prototype);
    seen.set(value, result);
    copyOwnDataProperties(value, result);
    return result;
  }

  function copyOwnDataProperties(source, target, skipped = new Set()) {
    for (const key of Reflect.ownKeys(source)) {
      if (skipped.has(key)) {
        continue;
      }

      const descriptor = Object.getOwnPropertyDescriptor(source, key);
      if (!('value' in descriptor)) {
        throw new TypeError('Accessor properties are not supported');
      }

      descriptor.value = clone(descriptor.value);
      Object.defineProperty(target, key, descriptor);
    }
  }

  return clone(input);
}

seen mesti menyimpan hubungan source-to-copy, bukan sekadar bit yang telah dilawati. Andaikan source.first dan source.second kedua-duanya menunjuk kepada shared. Lawatan pertama memperuntukkan dan mendaftarkan sharedCopy; lawatan kedua mengembalikan objek yang sama, mengekalkan aliasing. Jika source.self menunjuk kembali kepada source, nod punca telah didaftarkan sebelum property miliknya disalin, jadi back edge menunjuk kepada salinan punca tersebut.

WeakMap sesuai kerana setiap key ialah objek dan algoritma ini tidak memerlukan penyenaraian (enumeration). Map biasa juga betul dalam satu seruan dan tidak akan bocor selama-lamanya secara automatik selepas fungsi kembali. Weak key sepadan dengan jangka hayat perkaitan tersebut, tetapi “mencegah kebocoran memori” bukanlah bukti bahawa kitaran dikendalikan dengan betul.

Reflect.ownKeys mengembalikan string dan symbol key, termasuk property bukan enumerable. Kod membaca deskriptor dan bukannya nilai, jadi ia tidak melaksanakan getter secara proaktif; accessor gagal mengikut kontrak. Ia menggantikan nilai data descriptor secara rekursif dan mentakrifkan property dengan bendera writable, enumerable, dan configurable miliknya. length tatasusunan ialah property khas yang non-configurable, jadi key lain disalin terlebih dahulu dan deskriptornya dipulihkan paling akhir. Sparse hole tidak ditukar secara tidak sengaja kepada elemen yang nilainya adalah undefined.

Date, RegExp, Map, dan Set mengandungi internal state yang tidak boleh dicapai oleh penyalinan property biasa. Pelaksanaan ini membina semula nilai masa, sumber regular expression, bendera, dan lastIndex, key dan value map, serta value set. Setiap bekas didaftarkan sebelum lelaran, jadi map atau set boleh mengambil bahagian dalam kitaran. Kod ini mengandaikan objek realm yang sama; semakan instanceof merentas realm tidak boleh dipercayai dan memerlukan pengklonan platform atau semakan jenama yang lebih ketat.

Sempadan kekal eksplisit. Kod ini tidak mengekalkan keadaan beku (frozen), termeterai (sealed), atau tidak boleh dilanjutkan (non-extensible), tidak mengklon rantai prototaip, dan tidak menyokong accessor, medan peribadi, proksi, buffer, atau built-in yang tidak disenaraikan. structuredClone menyokong lebih banyak jenis platform, kitaran, dan identiti pendua, tetapi ia juga tidak menyertakan fungsi dan tidak mengekalkan deskriptor property, getter, setter, rantai prototaip, atau RegExp.lastIndex. Kontrak ini tidak boleh ditukar ganti hanya kerana kedua-duanya dipanggil klon mendalam (deep clone).

Katakan V ialah bilangan objek yang berbeza dan E ialah bilangan rujukan yang disumbangkan oleh own property, entri map, dan elemen set. Di bawah andaian prestasi purata yang biasa untuk pemetaan terbina dalam, kerja perentasan dan ruang salinan ialah O(V + E) kerana setiap objek sumber dikembangkan sekali. Recursive call stack ialah O(d), dengan d ialah laluan bersarang terpanjang. ECMAScript hanya memerlukan akses sublinear purata untuk Map, Set, dan WeakMap; ia tidak menjanjikan operasi O(1) yang ketat dalam setiap pelaksanaan.

Ujian mesti menguji struktur graf dan bukannya membandingkan teks bersiri: kitaran diri (self-cycle); dua property berkongsi satu anak; map key yang turut dirujuk oleh property lain; set yang mengandungi objek kongsi; tatasusunan jarang (sparse array); objek null-prototype; data property bukan enumerable dan ber-key symbol; Date; RegExp dengan lastIndex bukan sifar; kegagalan untuk fungsi, accessor, dan kelas tersuai; serta pengasingan selepas mengubah salinan. Rantaian asiklik yang sangat dalam juga harus menguji sempadan rekursi.

Contoh Jawapan Berkualiti Tinggi

“Saya akan menghadkan skop ini kepada graf objek terhingga dari realm yang sama yang mengandungi primitif, Array, Objek biasa, Date, RegExp, Map, dan Set. Fungsi, accessor, weak collection, buffer, dan kelas tersuai melontarkan ralat kerana masalah ini tidak mentakrifkan semantik salinan yang boleh diuji untuknya.

Kuncinya ialah mengekalkan hubungan identiti objek, bukan rekursi itu sendiri. Saya menyimpan WeakMap<source, copy>. Setiap kali saya melihat objek, saya menyemak map terlebih dahulu. Pada lawatan pertamanya, saya memperuntukkan salinan kosong dan mendaftarkannya sebelum menyalin property atau entri. Kitaran diri kemudiannya diselesaikan kepada salinan semasa, dan dua edge kepada satu objek sumber diselesaikan kepada satu objek sasaran. Key dan value Map serta elemen Set menggunakan laluan klon yang sama, jadi aliasing merentasi bekas dikekalkan.

Untuk property biasa saya menggunakan Reflect.ownKeys dan deskriptor. Ini mengekalkan symbol, bukan enumerable, dan bendera data descriptor tanpa melaksanakan getter secara senyap. Date, RegExp, Map, dan Set mendapat pembinaan semula khusus mengikut jenis. Mengira objek berbeza dan reference edge, kerja dan ruang salinan yang dijangkakan ialah O(V + E), dan call stack ialah O(d). Dalam pengeluaran, saya akan menggunakan structuredClone apabila matriks sokongannya bersesuaian, sambil mendokumentasikan bahawa ia tidak mengekalkan deskriptor, prototaip, atau lastIndex RegExp.”

Kesilapan Biasa

• Mensirikan dan menghurai JSON → kitaran melontarkan ralat, beberapa nilai JavaScript yang sah hilang atau berubah, dan rujukan kongsi terpisah → gunakan kontrak JSON sahaja, algoritma graf, atau structuredClone seperti yang sesuai.
• Menyalin tatasusunan dan objek sahaja secara rekursif → kitaran diri berulang tanpa henti dan rujukan berulang menjadi objek berasingan → petakan setiap objek sumber kepada satu salinan.
• Menyalin anak sebelum memasukkan ke dalam seen → back edge pertama masih tidak mempunyai pemetaan → peruntukkan dan daftarkan salinan kosong sebelum mengembangkan edge.
• Menjejaki lawatan dengan WeakSet → ia mengesan pengulangan tetapi tidak boleh memberitahu algoritma salinan mana yang hendak dikembalikan → gunakan WeakMap<source, copy>.
• Menggunakan for...in atau Object.entries untuk setiap property → yang pertama merangkumi property enumerable yang diwarisi, manakala yang kedua terlepas symbol dan bukan enumerable → gunakan own descriptor dan Reflect.ownKeys apabila kontrak memerlukannya.
• Membaca source[key] secara langsung → getter mungkin melakukan kesan sampingan atau melontarkan ralat, mengubah kelakuan pengklonan yang boleh diperhatikan → periksa deskriptor dan tentukan dasar accessor yang jelas.
• Mencipta setiap sasaran dengan Object.create(proto) → internal slot untuk Date, Map, dan Set kekal tiada, dan medan peribadi kelas tersuai hilang → bina semula built-in yang disokong dan tolak jenis lain.
• Mendakwa O(V + E) yang ketat → ECMAScript tidak menjamin operasi Map, Set, atau WeakMap masa malar, dan rekursi mungkin melimpah (overflow) → nyatakan andaian prestasi purata dan sempadan stack O(d).

Soalan Susulan dan Maklum Balas

Soalan Susulan 1: Mengapakah rujukan pendua dikekalkan dan bukannya hanya menghalang kitaran?

Identiti boleh membawa makna aplikasi. Jika order.customer === cache.currentCustomer, mengklonnya secara bebas menjadikan kesamarataan itu palsu dalam salinan, dan mutasi melalui satu laluan yang disalin tidak lagi dapat diperhatikan melalui laluan yang satu lagi. Pemetaan satu-ke-satu source-to-copy mengekalkan kedua-dua kitaran dan aliasing. Ujian harus menegaskan copy.first === copy.second; sekadar menegaskan bahawa pengklonan tidak melimpah membuktikan terlalu sedikit.

Soalan Susulan 2: Bagaimanakah anda mengendalikan rantaian sedalam seratus ribu objek?

Kekalkan invarian seen yang sama tetapi gantikan panggilan rekursif dengan work stack yang eksplisit. Peruntukkan dan daftarkan salinan pada pertemuan pertama, kemudian tolak bingkai (frame) yang mengandungi bekas sumber, bekas sasaran, dan key atau entri yang belum selesai. Gelung lelaran memproses bingkai tersebut. Penggunaan masa dan heap masih meningkat dengan V + E, tetapi keadaan bantuan beralih daripada call stack bahasa ke struktur heap terkawal. Date dan RegExp selesai dengan serta-merta; Object, Array, Map, dan Set memerlukan bingkai susulan.

Soalan Susulan 3: Apakah yang berubah jika ArrayBuffer boleh disalin atau dipindahkan?

API memerlukan pilihan yang jelas. Menyalin memperuntukkan buffer dengan panjang yang sama dan menyalin bait. Pemindahan membatalkan buffer sumber, jadi ia merupakan peralihan pemilikan dengan kesan sampingan dan tidak boleh disembunyikan di dalam deepClone. Platform telah mentakrifkan perkara ini melalui structuredClone(value, { transfer: [...] }). Pelaksanaan tersuai yang tidak dapat memisahkan storan harus menolak pemindahan dan bukannya mengembalikan dua paparan pada satu buffer dan melabelkan hasilnya sebagai deep copy.

Soalan Susulan 4: Bagaimanakah anda menyokong kelas tersuai, getter, dan medan peribadi?

Refleksi umum tidak dapat membaca medan peribadi atau menghasilkan semula closure. Mengekalkan getter dan setter berkongsi fungsi dan closure; menilai getter boleh menyebabkan kesan sampingan. Pelanjutan yang munasabah ialah pendaftaran serializer: setiap kelas membekalkan fungsi serialize dan deserialize yang membina semula invarian miliknya, dan adapternya memutuskan sama ada accessor dikekalkan, dinilai, atau ditolak. Tanpa adapter, melontarkan ralat adalah lebih selamat daripada mencipta objek yang mana instanceof adalah benar sedangkan internal state miliknya rosak.