Mengimplementasikan Deep Clone di JavaScript

Masalah dan Konteks yang Berlaku

Implementasikan deepClone(value). Inputnya adalah graf objek berhingga dari satu realm JavaScript. Input dapat berisi tipe primitif, array, plain object yang prototipe-nya adalah Object.prototype atau null, Date, RegExp, Map, dan Set. Setiap objek sumber yang didukung harus memiliki objek berbeda dalam salinannya. Jika dua edge sumber menunjuk ke objek yang sama, edge salinan yang bersangkutan harus menunjuk ke objek salinan yang sama. Siklus tidak boleh menyebabkan rekursi tanpa batas.

Fungsi ini juga harus menyalin setiap properti data milik sendiri (own data property), termasuk properti non-enumerable dan properti ber-key symbol, sambil tetap mempertahankan deskriptornya. Pertahankan array hole, nilai waktu dari Date, source, flag, dan lastIndex dari RegExp, baik key maupun value dari Map, serta value dari Set.

Fungsi, accessor property, WeakMap, WeakSet, proxy, typed array, array buffer, instans custom class, dan built-in yang tidak terdaftar berada di luar kontrak dan harus memicu TypeError. Implementasi ini bersifat rekursif, sehingga diasumsikan pula bahwa tingkat nesting tidak akan menghabiskan call stack. Untuk data produksi yang sesuai dengan tipe structured-cloneable milik platform, evaluasi structuredClone sebelum mengubah implementasi wawancara ini menjadi library tujuan umum.

Hal yang Dievaluasi oleh Pewawancara

Sinyal pertama adalah apakah kandidat mendefinisikan arti dari “deep clone”. JavaScript tidak memiliki aturan universal di userland yang dapat mereproduksi closure fungsi, DOM node, private field, proxy, dan setiap internal slot built-in. Jawaban yang kuat mencantumkan tipe yang didukung, semantik properti, perilaku siklus, dan perilaku kegagalan sebelum menulis rekursi.

Sinyal kedua adalah mengenali graf objek alih-alih pohon objek. Mengalokasikan objek secara rekursif dapat menyalin pohon, tetapi tidak dapat menangani source.self = source, dan secara keliru mengubah source.a === source.b menjadi dua salinan terpisah. State yang dibutuhkan bukan sekadar “sudah dikunjungi”; melainkan “salinan mana yang dimiliki oleh objek sumber ini”.

Sinyal ketiga adalah urutan alokasi. Alokasikan target kosong dan catat pemetaan source-to-copy sebelum menelusuri outgoing edge. Jika child disalin sebelum pendaftaran, back edge pertama tetap tidak menemukan target dan rekursi berlanjut mengitari siklus.

Sinyal keempat adalah penjelasan jujur mengenai batasan properti dan built-in. Object.entries melewatkan key symbol dan properti non-enumerable. Membaca source[key] dapat mengeksekusi getter. Memberi Date, Map, atau Set objek dengan prototipe yang sama tidak mereproduksi internal slot-nya.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Tipe apa saja yang harus didukung? Array dan plain object sudah cukup untuk data berbentuk JSON. Menambahkan Date, RegExp, Map, dan Set memerlukan konstruksi dan penelusuran spesifik per tipe. Menambahkan typed array atau array buffer memunculkan pilihan penyalinan buffer dan kepemilikan.
• Apakah siklus dan referensi duplikat harus gagal, diputus, atau dipertahankan topologinya? Masalah ini mempertahankan topologinya, sehingga memerlukan pemetaan source-to-copy. WeakSet dapat mendeteksi pengulangan tetapi tidak dapat mengembalikan salinan yang benar.
• Apakah properti hanya mencakup key string enumerable, atau juga symbol, non-enumerable, dan deskriptor? Kontrak ini memilih opsi kedua dan menolak accessor, menghindari eksekusi getter maupun fungsi getter atau setter bersama.
• Apakah custom class dan rantai prototipe harus disalin? Masalah ini hanya menerima plain object dan built-in yang terdaftar. Object.create(instancePrototype) tidak dapat mereproduksi private field atau state yang dibuat oleh konstruktor, sehingga menampilkan hasilnya sebagai instans lengkap akan menyesatkan.
• Apakah ini algoritma wawancara atau API produksi? Implementasi wawancara mendemonstrasikan kontrak dan invarian graf. Kode produksi harus membandingkan cakupan tipe structuredClone, semantik transfer, dan hilangnya metadata sebelum memilih serializer kustom yang terkontrol.
• Berapa kedalaman nesting maksimum? Rekursi menggunakan stack pembantu O(d). Rantai yang mungkin berisi seratus ribu objek memerlukan work stack eksplisit dan mengubah implementasi serta pengujian.

Kerangka Jawaban 30 Detik

“Saya akan menentukan tipe yang didukung dan memperlakukan input sebagai sebuah graf. Tipe primitif langsung dikembalikan. Untuk setiap objek, saya memeriksa WeakMap; pada kunjungan pertamanya, saya mengalokasikan dan mendaftarkan salinan kosong sebelum menyalin properti atau entri. Siklus dan referensi duplikat kemudian diarahkan ke satu salinan. Date dan RegExp dibangun ulang, sementara fungsi, accessor, dan objek yang tidak didukung akan melempar error. Waktu yang diharapkan dan ruang salinan adalah O(V + E), dengan recursion stack O(d).”

Pembahasan Mendalam Langkah Demi Langkah

JSON.parse(JSON.stringify(value)) hanya valid untuk kontrak JSON yang lebih sempit. Cara ini gagal pada siklus serta mengubah atau menghilangkan undefined, BigInt, symbol, Date, RegExp, Map, Set, dan nilai numerik khusus. Rekursi biasa memberikan kontrol lebih besar, tetapi tanpa pemetaan source-to-copy, rekursi biasa tetap hanya dapat menangani pohon.

Invarian utamanya adalah: sebelum menelusuri properti atau entri dari objek apa pun yang didukung, seen.get(sourceObject) sudah bernilai sama dengan salinan unik yang dialokasikan 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 harus menyimpan relasi source-to-copy, bukan sekadar bit visited. Andaikan source.first dan source.second sama-sama menunjuk ke shared. Kunjungan pertama mengalokasikan dan mendaftarkan sharedCopy; kunjungan kedua mengembalikan objek yang sama persis tersebut, sehingga mempertahankan aliasing. Jika source.self menunjuk kembali ke source, root sudah didaftarkan sebelum propertinya disalin, sehingga back edge akan menunjuk ke salinan root.

WeakMap cocok digunakan karena setiap key adalah objek dan algoritma ini tidak pernah memerlukan enumerasi. Map biasa juga akan benar dalam satu kali pemanggilan dan tidak akan otomatis bocor selamanya setelah fungsi selesai dieksekusi. Weak key sesuai dengan masa hidup asosiasi tersebut, tetapi “mencegah memory leak” bukanlah bukti bahwa siklus ditangani dengan benar.

Reflect.ownKeys mengembalikan key string dan symbol, termasuk properti non-enumerable. Kode membaca deskriptor alih-alih nilainya secara langsung, sehingga tidak secara proaktif memanggil getter; accessor gagal sesuai dengan kontrak. Kode mengganti nilai deskriptor data secara rekursif dan mendefinisikan properti beserta flag writable, enumerable, dan configurable-nya. length pada Array adalah properti non-configurable khusus, sehingga key lainnya disalin terlebih dahulu dan deskriptornya dipulihkan paling akhir. Sparse hole tidak akan secara tidak sengaja diubah menjadi elemen yang bernilai undefined.

Date, RegExp, Map, dan Set berisi internal state yang tidak dapat dijangkau oleh penyalinan properti biasa. Implementasi ini membangun kembali nilai waktu, regular expression source, flag, dan lastIndex, key dan value map, serta value set. Setiap kontainer didaftarkan sebelum iterasi, sehingga map atau set dapat berpartisipasi dalam sebuah siklus. Kode ini mengasumsikan objek berasal dari realm yang sama; pemeriksaan instanceof lintas realm tidak dapat diandalkan dan memerlukan platform cloning atau brand check yang lebih ketat.

Batasannya tetap eksplisit. Kode ini tidak mempertahankan state frozen, sealed, atau non-extensible, tidak mengkloning rantai prototipe, dan tidak mendukung accessor, private field, proxy, buffer, atau built-in yang tidak terdaftar. structuredClone mendukung lebih banyak tipe platform, siklus, dan identitas duplikat, tetapi juga mengecualikan fungsi dan tidak mempertahankan deskriptor properti, getter, setter, rantai prototipe, atau RegExp.lastIndex. Kontrak-kontrak ini tidak dapat dipertukarkan begitu saja hanya karena keduanya disebut deep clone.

Misalkan V adalah jumlah objek berbeda dan E adalah jumlah referensi yang disumbangkan oleh own property, entri map, dan elemen set. Di bawah asumsi performa rata-rata yang lazim untuk pemetaan bawaan (built-in mappings), proses penelusuran dan ruang salinan adalah O(V + E) karena setiap objek sumber diekspansi satu kali. Recursive call stack-nya adalah O(d), dengan d adalah jalur bersarang terpanjang. ECMAScript hanya mensyaratkan akses sublinear rata-rata untuk Map, Set, dan WeakMap; spesifikasi tidak menjanjikan operasi O(1) yang ketat di setiap implementasi.

Pengujian harus memeriksa struktur graf daripada sekadar membandingkan teks yang diserialisasi: self-cycle; dua properti yang berbagi satu child; map key yang juga direferensikan oleh properti lain; set yang berisi objek bersama; sparse array; objek null-prototype; data property non-enumerable dan ber-key symbol; Date; RegExp dengan lastIndex bukan nol; kegagalan untuk fungsi, accessor, dan custom class; serta isolasi setelah memutasi salinan. Rantai asiklik yang sangat dalam juga harus menguji batas rekursi.

Contoh Jawaban Berkualitas Tinggi

“Saya akan membatasi cakupan ini pada graf objek berhingga dari realm yang sama yang berisi tipe primitif, Array, plain Object, Date, RegExp, Map, dan Set. Fungsi, accessor, weak collection, buffer, dan custom class akan melempar error karena masalah ini tidak mendefinisikan semantik penyalinan yang dapat diuji untuk tipe-tipe tersebut.

Kuncinya adalah mempertahankan hubungan identitas objek, bukan rekursinya itu sendiri. Saya menyimpan sebuah WeakMap<source, copy>. Setiap kali melihat sebuah objek, saya memeriksa map terlebih dahulu. Pada kunjungan pertamanya, saya mengalokasikan salinan kosong dan mendaftarkannya sebelum menyalin properti atau entri. Self-cycle kemudian diarahkan ke salinan saat ini, dan dua edge ke satu objek sumber diarahkan ke satu objek target. Key dan value Map serta elemen Set menggunakan jalur clone yang sama, sehingga aliasing antar-kontainer tetap terjaga.

Untuk properti biasa, saya menggunakan Reflect.ownKeys dan deskriptor. Cara tersebut mempertahankan symbol, non-enumerable, dan flag deskriptor data tanpa mengeksekusi getter secara diam-diam. Date, RegExp, Map, dan Set mendapatkan rekonstruksi spesifik per tipe. Dengan menghitung objek berbeda dan reference edge, perkiraan waktu dan ruang salinan adalah O(V + E), dan call stack-nya adalah O(d). Di lingkungan produksi, saya akan menggunakan structuredClone ketika matriks dukungannya sesuai, sambil mendokumentasikan bahwa metode tersebut tidak mempertahankan deskriptor, prototipe, atau lastIndex milik RegExp.”

Kesalahan Umum

• Melakukan serialisasi dan parsing JSON → siklus akan melempar error, beberapa nilai JavaScript yang valid hilang atau berubah, dan referensi bersama terpisah → gunakan kontrak khusus JSON, algoritma graf, atau structuredClone sesuai kebutuhan.
• Menyalin hanya array dan objek secara rekursif → self-cycle akan berekursi selamanya dan referensi berulang menjadi objek yang terpisah → petakan setiap objek sumber ke satu salinan.
• Menyalin child sebelum memasukkannya ke dalam seen → back edge pertama masih belum memiliki pemetaan → alokasikan dan daftarkan salinan kosong sebelum mengekspansi edge.
• Melacak kunjungan dengan WeakSet → cara ini mendeteksi pengulangan tetapi tidak dapat memberi tahu algoritma salinan mana yang harus dikembalikan → gunakan WeakMap<source, copy>.
• Menggunakan for...in atau Object.entries untuk setiap properti → yang pertama menyertakan properti enumerable turunan, sedangkan yang kedua melewatkan symbol dan non-enumerable → gunakan own descriptor dan Reflect.ownKeys saat kontrak memerlukannya.
• Membaca source[key] secara langsung → getter dapat menimbulkan efek samping atau melempar error, mengubah perilaku kloning yang dapat diamati → periksa deskriptor dan tentukan kebijakan accessor yang eksplisit.
• Membuat setiap target dengan Object.create(proto) → internal slot untuk Date, Map, dan Set tetap tidak ada, dan private field custom class hilang → bangun ulang built-in yang didukung dan tolak tipe lainnya.
• Mengklaim O(V + E) ketat → ECMAScript tidak menjamin operasi Map, Set, atau WeakMap konstan secara waktu, dan rekursi dapat meluap (overflow) → nyatakan asumsi performa rata-rata dan batasan stack O(d).

Pertanyaan Lanjutan dan Tanggapan

Pertanyaan Lanjutan 1: Mengapa mempertahankan referensi duplikat alih-alih hanya mencegah siklus?

Identitas dapat membawa makna aplikasi. Jika order.customer === cache.currentCustomer, mengkloningnya secara independen membuat kesetaraan tersebut menjadi bernilai false pada salinannya, dan mutasi melalui satu jalur salinan tidak lagi dapat diamati melalui jalur lainnya. Pemetaan satu-ke-satu dari sumber ke salinan mempertahankan siklus sekaligus aliasing. Pengujian harus menegaskan bahwa copy.first === copy.second; sekadar menegaskan bahwa proses kloning tidak mengalami overflow belum cukup membuktikannya.

Pertanyaan Lanjutan 2: Bagaimana Anda menangani rantai dengan kedalaman seratus ribu objek?

Pertahankan invarian seen yang sama tetapi ganti pemanggilan rekursif dengan work stack eksplisit. Alokasikan dan daftarkan salinan saat pertama kali ditemukan, lalu lakukan push frame yang berisi kontainer sumber, kontainer target, serta key atau entri yang tertunda. Loop iteratif akan memproses frame tersebut. Waktu dan penggunaan heap masih bertumbuh sebesar V + E, tetapi state pembantu berpindah dari call stack bahasa ke struktur heap yang terkontrol. Date dan RegExp selesai seketika; Object, Array, Map, dan Set memerlukan frame tindak lanjut.

Pertanyaan Lanjutan 3: Apa yang berubah jika ArrayBuffer dapat disalin atau ditransfer?

API memerlukan opsi eksplisit. Penyalinan akan mengalokasikan buffer dengan panjang yang sama dan menyalin byte-nya. Mentransfer akan membatalkan (invalidate) buffer sumber, sehingga tindakan tersebut merupakan pemindahan kepemilikan dengan efek samping dan tidak dapat disembunyikan di dalam deepClone. Platform telah mendefinisikan hal ini melalui structuredClone(value, { transfer: [...] }). Implementasi kustom yang tidak dapat melepaskan storage (detach storage) harus menolak transfer daripada mengembalikan dua view di atas satu buffer dan melabeli hasilnya sebagai deep copy.

Pertanyaan Lanjutan 4: Bagaimana Anda mendukung custom class, getter, dan private field?

Refleksi umum tidak dapat membaca private field atau mereproduksi closure. Mempertahankan getter dan setter akan berbagi fungsi dan closure; mengevaluasi getter dapat menimbulkan efek samping. Ekstensi yang masuk akal adalah serializer registry: setiap class menyediakan fungsi serialize dan deserialize yang membangun kembali invarian miliknya, dan adapternya menentukan apakah accessor dipertahankan, dievaluasi, atau ditolak. Tanpa adaptor, melempar error lebih aman daripada membuat objek dengan instanceof bernilai true padahal internal state-nya rusak.