Pernahkah Anda menjalankan perintah npm install atau composer update, lalu tiba-tiba terminal Anda menampilkan error merah bertuliskan "Circular Dependency Detected" (Error: Circular dependency detected: src/a.js -> src/b.js -> src/a.js)?. Bagi pengguna, error ini mungkin menyebalkan. Namun bagi seorang Software Engineer, pesan tersebut adalah bukti bahwa package manager sedang menyelamatkan sistem Anda dari infinite loop.
Bagaimana cara tool seperti npm (Node.js), Composer (PHP), atau Maven (Java) mengetahui bahwa sekumpulan kode saling memanggil satu sama lain dalam sebuah lingkaran?
Jawabannya ada pada teori graf klasik berumur puluhan tahun yaitu Algoritma Kosaraju. Kita mulai dengan misteri dependency hell yaitu kondisi dimana proyek Anda memiliki banyak dependensi library/package. Sehingga hubungan dependensi menjadi kompleks dan sulit untuk dikelola. Berikut adalah penjelasan mengenai misteri dependency hell dan cara mengatasinya.
1. Misteri Dependency Hell
Dalam pengembangan perangkat lunak modern, kita tidak pernah menulis kode dari nol. Kita merakit blok-blok bangunan yang disebut package atau library.
Bayangkan skenario ini:
- Anda menginstal Package A (misalnya sistem Payment).
- Package A ternyata membutuhkan fitur dari Package B (User Authentication).
- Package B membutuhkan utilitas dari Package C (Logger).
- Sayangnya, sang pembuat Package C memasukkan Package A sebagai dependensinya untuk mencatat log pembayaran.
Visualisasi Graf Berarah: Package A → B → C → A membentuk sebuah lingkaran yang tidak bisa diselesaikan.
Jika package manager sembarangan mulai mengunduh tanpa menganalisis, ia akan mengunduh A, lalu B, lalu C, lalu A lagi, lalu B lagi... hingga RAM komputer Anda habis atau server registry/prouduction down. Ini dikenal dengan sebutan Circular Dependency.
Ada beberapa jenis Dependency Hell yaitu:
- Version Conflict yaitu kondisi ketika dua package membutuhkan versi yang berbeda dari package yang sama. Contohnya Package A membutuhkan Package B versi 1.0 dan Package C membutuhkan Package B versi 2.0.
- Diamond Dependency yaitu kondisi ketika sebuah aplikasi bergantung pada dua pustaka (library atau package) berbeda, di mana kedua pustaka tersebut ternyata membutuhkan pustaka ketiga yang sama, tetapi dengan versi yang berbeda.
- Circular Dependency yaitu di mana dua atau lebih modul, kelas, atau paket saling membutuhkan satu sama lain, baik secara langsung maupun tidak langsung, sehingga membentuk sebuah lingkaran setan (loop). Komponen A tidak bisa berfungsi tanpa Komponen B, tetapi Komponen B juga tidak bisa hidup tanpa Komponen A. Ada 2 jenis yaitu Direct dan Indirect.
- Dependency Explosion yaitu kondisi ketika di mana jumlah pustaka (library/package) pihak ketiga yang masuk ke dalam proyek Anda membengkak secara eksponensial dan tak terkendali. Kondisi ini biasanya terjadi bukan karena Anda sengaja menginstal ratusan pustaka, melainkan karena efek domino dari pustaka-pustaka yang saling menggendong pustaka lainnya (Transitive Dependencies).
- Transitive Dependency yaitu dependensi dari dependensi Anda. Ini adalah situasi di mana proyek Anda tidak meminta suatu pustaka secara langsung, tetapi pustaka yang Anda pasang membutuhkannya.
- Dependency Lock yaitu kondisi ketika Anda tidak dapat memperbarui versi paket tanpa berpotensi memutus kompatibilitas dengan dependensi lain dalam proyek Anda. Situasi ini sering kali muncul akibat efek domino dari transitive dependencies dan diamond dependencies yang kompleks. Sederhananya, komponen A membutuhkan B (versi 1), C membutuhkan B (versi 2), dan A juga membutuhkan D, sementara D membutuhkan B (versi 3). Akibatnya, Anda terjebak: jika ingin meng-upgrade B ke versi 3 (karena D butuh itu), Anda berisiko merusak A yang masih bergantung pada versi 1.
Ada satu aturan wajib bagi developer dalam mengelola aplikasi: Jangan pernah memasukkan file lock ke dalam .gitignore. File lock (composer.lock, package-lock.json, pnpm-lock.yaml) wajib di-commit dan didorong ke dalam repository Git bersama kode aplikasi Anda.
Satu-satunya pengecualian adalah ketika Anda sedang membangun sebuah pustaka/package yang sengaja dibuat untuk dipakai orang lain (bukan aplikasi akhir), di mana flexibilitas versi lebih diutamakan.
Mari kita pikirkan solusinya dengan menggunakan Graf Berarah atau Directed Graph.
2. Berpikir Layaknya Graf
Untuk memecahkan masalah ini secara algoritmik, package manager tidak membaca kode sumber. Ia membaca file manifes (package.json atau composer.json) dan memodelkannya sebagai Directed Graph (Graf Berarah).
Dalam dunia graf:
- Node (Simpul): Adalah nama package (A, B, C).
- Edge (Sisi): Adalah arah ketergantungan (A membutuhkan B).
Tugas utama sistem berubah dari "Membaca file JSON" menjadi masalah matematis: "Apakah ada siklus di dalam graf berarah ini?"
Dari sinilah kita mencari Strongly Connected Components (SCC). SCC adalah sekumpulan node di mana Anda bisa mulai dari node manapun ke node lain di dalam kumpulan tersebut. Jika ada SCC yang berisi lebih dari 1 package, maka Anda menemukan Circular Dependency.
Mencari kumpulan-kumpulan terisolasi ini di dalam graf raksasa (seperti miliaran baris kode) secara manual tentulah mustahil. Para ilmuwan komputer telah merancang dua algoritma untuk menyelesaikannya dengan efisiensi tinggi (kompleksitas waktu $O(V+E)$): Algoritma Kosaraju dan Algoritma Tarjan. Kita akan fokus pada Algoritma Kosaraju pada kesempatan kali ini, mari kita berkenalan lebih lanjut dengan Algoritma Kosaraju.
3. Mengenal Algoritma Kosaraju
Ditemukan oleh Sambasiva Rao Kosaraju pada tahun 1978, algoritma ini sangat elegan karena memecahkan pencarian SCC hanya dalam waktu linear O(V + E) menggunakan manipulasi pembalikan arah graf.
Kosaraju bekerja dalam 3 langkah sangat berurutan:
- DFS (Depth-First Search) Maju: Lakukan penjelajahan graf secara mendalam. Setiap kali sebuah package selesai dieksplorasi (tidak punya anak lagi), masukkan ia ke dalam sebuah tumpukan (Stack).
- Transpose Graf (Pembalikan Arah): Balik semua arah panah ketergantungan. Jika A → B, ubah menjadi B → A.
- DFS Mundur (Pop Stack): Ambil package dari tumpukan teratas, lalu lakukan DFS pada graf yang sudah dibalik. Semua node yang berhasil terjangkau dalam satu kali jalan, membentuk satu siklus SCC!
Kunci dari algoritma Kosaraju adalah Transpose Graph: Membalik arah panah untuk menjebak siklus agar tidak bisa kabur ke graf lain saat DFS kedua dilakukan.
4. Implementasi Kosaraju di TypeScript
Mari kita tulis sistem deteksi sederhana ala npm menggunakan TypeScript. Kita akan membuat graf dari package.json, lalu mendeteksi siklusnya.
// Representasi Graf menggunakan Adjacency List
type Graph = Map<string, string[]>;
class PackageManager {
private graph: Graph = new Map();
// 1. Tambahkan dependensi (A butuh B)
public addDependency(pkg: string, deps: string[]) {
this.graph.set(pkg, deps);
// Pastikan dependensi yang tidak punya anak juga terdaftar
for (const dep of deps) {
if (!this.graph.has(dep)) this.graph.set(dep, []);
}
}
// 2. Pembalikan Arah Graf (Transpose)
private getTranspose(): Graph {
const transposed: Graph = new Map();
for (const node of this.graph.keys()) {
transposed.set(node, []);
}
for (const [node, neighbors] of this.graph.entries()) {
for (const neighbor of neighbors) {
transposed.get(neighbor)!.push(node); // Balik panah
}
}
return transposed;
}
// 3. Algoritma Inti Kosaraju
public detectCircularDependencies(): string[][] {
const stack: string[] = [];
const visited: Set<string> = new Set();
const sccList: string[][] = [];
// DFS Tahap 1: Isi Stack berdasarkan waktu penyelesaian
const dfs1 = (node: string) => {
visited.add(node);
for (const neighbor of this.graph.get(node) || []) {
if (!visited.has(neighbor)) dfs1(neighbor);
}
stack.push(node);
};
for (const node of this.graph.keys()) {
if (!visited.has(node)) dfs1(node);
}
// DFS Tahap 2: Jelajahi graf yang sudah dibalik
const transposedGraph = this.getTranspose();
visited.clear();
const dfs2 = (node: string, currentScc: string[]) => {
visited.add(node);
currentScc.push(node);
for (const neighbor of transposedGraph.get(node) || []) {
if (!visited.has(neighbor)) dfs2(neighbor, currentScc);
}
};
// Pop stack dari belakang
while (stack.length > 0) {
const node = stack.pop()!;
if (!visited.has(node)) {
const currentScc: string[] = [];
dfs2(node, currentScc);
// Jika SCC > 1, itu adalah Circular Dependency!
if (currentScc.length > 1) {
sccList.push(currentScc);
}
}
}
return sccList;
}
}
Menguji Sistem Kita
Mari kita berikan skenario jebakan seperti yang kita bahas di awal artikel:
const npmClient = new PackageManager();
// A -> B -> C -> A
npmClient.addDependency("PackageA", ["PackageB"]);
npmClient.addDependency("PackageB", ["PackageC"]);
npmClient.addDependency("PackageC", ["PackageA", "Utils"]);
npmClient.addDependency("Utils", []); // Aman
const errors = npmClient.detectCircularDependencies();
if (errors.length > 0) {
console.error("❌ ERRR! Circular Dependency Detected!");
errors.forEach(cycle => {
console.error(`Cycle: ${cycle.join(' ↔ ')} ↔ ${cycle[0]}`);
});
// Jangan lanjutkan instalasi!
} else {
console.log("✅ Graf aman. Melanjutkan instalasi...");
}
Output Terminal:
❌ ERRR! Circular Dependency Detected!
Cycle: PackageA ↔ PackageC ↔ PackageB ↔ PackageA
5. Arsitektur Package Manager
Dalam sistem production skala besar, deteksi ini dilakukan jauh sebelum koneksi internet dibuat untuk mengunduh file .tar.gz dari registry.
Pipeline Arsitektur Sistem: Evaluasi graf adalah first line of defense sebelum komputasi berat dilakukan.
Jika algoritma mendeteksi bahwa instalasi akan berujung pada stack overflow atau infinite download, ia akan langsung memicu mekanisme Fail-Fast. Sistem melempar Exception, menghentikan memori, dan memberikan pesan yang jelas kepada developer untuk memperbaiki skema aplikasinya.
Hal yang membuat Software Engineering sangat menarik dan keren adalah bagaimana penemuan teoritis matematika murni dari puluhan tahun silam (seperti teori Strongly Connected Component tahun 1978) masih menjadi tulang punggung yang menjaga server-server triliunan rupiah di abad ke-21 agar tidak crash atau down saat kita sekadar mengetik npm install.
Kode mungkin menua, framework akan mati silih berganti, namun fundamental algoritma akan berdiri kokoh sebagai kebenaran.