String C: Kesalahan yang Berlanjut Selama 50 Tahun

• String berakhiran NUL di C tidak menyimpan informasi panjang, sehingga memicu pemindaian berulang dan kesalahan batas; di era modern, string berbasis panjang yang menyimpan pointer dan ukuran bersama-sama lebih cocok sebagai desain dasar
• Tanpa panjang yang eksplisit, pemanggilan strlen dan penelusuran byte harus diulang, dan pada snprintf, sizeof, serta strlen, apakah byte terminator ikut dihitung berbeda-beda, sehingga penulisan dan peninjauan kode menjadi sulit
• String berbasis panjang menangani string kosong secara konsisten dengan size == 0, dan operasi pencarian, pemisahan, serta slicing dapat diterapkan apa adanya pada data biner arbitrer yang mengandung byte NUL
• Karena dapat mengembalikan substring yang menunjuk ke sebagian memori asli, pemotongan, pencarian, tokenisasi, serta parsing CSV, Markdown, JSON, dan C dapat menghindari alokasi dan penyalinan perantara
• Sentinel tetap berguna untuk menjaga invariant dan beberapa pencarian token, dan konversi dengan API C/OS yang ada tetap diperlukan, tetapi untuk sebagian besar kode, menggabungkan string berbasis panjang dengan immutabilitas di batas API lebih sederhana dan fleksibel

---

Menyimpan pointer dan panjang alih-alih terminasi NUL

• String C direpresentasikan sebagai pointer ke aliran karakter dan batasnya ditandai oleh byte NUL terakhir
  • Dalam keterbatasan memori dan performa pada tahun 1970-an, ini mungkin masuk akal, tetapi saat ini hampir tidak ada alasan untuk mempertahankan pendekatan ini
• Alternatif yang diadopsi bahasa modern dan framework utama adalah struct yang menyimpan pointer data dan ukuran bersama-sama

struct String
{
    u8* data;
    u64 size;
};

• Literal string dapat diubah menjadi String dengan menghitung panjangnya melalui sizeof(s) - 1, dan operasi seperti perbandingan atau output dapat langsung memakai ukuran yang tersimpan
• Array juga kehilangan informasi seperti panjang saat terkonversi menjadi pointer, sehingga mengalami masalah keamanan dan kegunaan yang mirip dengan string

Biaya saat membuang informasi panjang

• Jika panjang tidak disimpan, setiap kode yang menggunakannya harus berulang kali memanggil strlen atau menelusuri byte satu per satu, sehingga menambah pekerjaan yang tidak perlu dan kompleksitas
• Memeriksa dan menegakkan panjang pada runtime juga lebih lambat dan merepotkan, dan debugger maupun alat analisis sulit memperlakukan char*, char[N], dan char*[N] secara konsisten
• Ada pandangan bahwa banyak masalah memori dan bug overflow di C berasal dari desain ini, meski ada pula argumen tandingan bahwa sentinel saja sudah cukup
• String yang panjangnya tidak diketahui menjadi lebih mirip pola akses sekuensial seperti linked list daripada akses acak pada array
• Pihak yang membela pendekatan berakhiran NUL menganggap pemrosesan sekuensial mendorong algoritme satu lintasan yang lebih efisien daripada multi-lintasan
  • Banyak programmer, termasuk pemula, menulis kode dengan asumsi bahwa panjang string bisa diperoleh dengan murah
  • Rutinitas string umum pun lebih alami ditulis dalam bentuk yang menerima panjang, dan pemanggilan strlen yang berulang membuat kode nyata menelusuri string yang sama berkali-kali
  • Anggapan bahwa jumlah lintasan yang lebih sedikit selalu lebih cepat berasal dari salah paham tentang cara kerja CPU modern

Arti panjang yang berbeda pada snprintf, sizeof, dan strlen

• Dua bilangan bulat pada snprintf tampak seperti sama-sama berarti “panjang”, tetapi aturan apakah NUL dihitung justru berlawanan

int snprintf(char *str, size_t size, const char *format, ...);

• size pada input harus mencakup ruang untuk terminasi NUL pada buffer output, tetapi nilai baliknya menunjukkan panjang string yang akan dihasilkan tanpa menghitung byte NUL
• Setiap kali memakai fungsi atau API terkait string, hal-hal berikut harus diperiksa secara terpisah
  • apakah fungsi menulis byte NUL secara langsung
  • apakah ukuran alokasi harus ditambah ruang untuk byte NUL
  • apakah argumen ukuran dan nilai balik menghitung byte NUL
• sizeof("some string") menghitung byte NUL, tetapi strlen("some string") tidak
• Saat mengubah kode berbasis literal menjadi kode berbasis pointer runtime sambil mempertahankan - 1 yang sama, bisa muncul bug panjang kurang satu

#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

const char *str = "some string";
size_t size = strlen(str) - 1;

Menimpa byte NUL di tengah berulang kali

• Jika beberapa nilai balik snprintf dijumlahkan ke offset untuk menyambung string, maka byte terminasi NUL yang ditulis tiap pemanggilan akan ditimpa oleh pemanggilan berikutnya

int offset = 0;
offset += snprintf(ptr + offset, size - offset, "%d", my_int);
offset += snprintf(ptr + offset, size - offset, "%s", my_str);
offset += snprintf(ptr + offset, size - offset, "%f", my_flt);

• Penulisan byte terminasi di tengah ini tidak perlu, tetapi dampaknya pada performa mungkin memang tidak besar
• Masalah yang lebih besar adalah perilaku ini tidak intuitif, sehingga menimbulkan kesalahpahaman bahwa snprintf tidak melakukan terminasi NUL
• Akibatnya muncul kode yang menambahkan ptr[offset] = 0; di akhir, padahal itu juga tidak perlu dan justru makin memperkuat salah paham yang sama

Dua status untuk string kosong dan string null

• Dalam model berakhiran NUL, string kosong dan pointer null diperlakukan sebagai dua status tidak valid yang berbeda, sehingga kode pemrosesan string harus memeriksa keduanya
• String dan array di C# juga merupakan tipe referensi, sehingga membaca Length atau mengiterasi saat bernilai null akan melempar exception dan memerlukan penanganan terpisah
• Respons yang umum adalah selalu meneruskan dan mengembalikan string kosong atau array kosong alih-alih null
  • Aturan seperti String.IsNullOrEmpty, “Don’t Return Null”, dan “Don’t Pass Null” juga merupakan cara untuk menangani pembedaan ini
• Pada struct yang memiliki pointer dan panjang, string kosong dapat ditentukan hanya dengan size == 0
  • Pointernya bisa null atau bisa alamat yang valid
  • Saat sudah bergerak ke akhir string, atau saat menunjuk substring kosong di dalam string besar, pointer valid masih bisa ada meski panjangnya 0
  • Jika dereferensi hanya dilakukan setelah memeriksa panjang, pointer yang menunjuk ke memori yang sudah dibebaskan pun tidak akan diakses ketika panjangnya 0

Memakai representasi yang sama untuk data biner

• String berbasis panjang tidak bergantung pada sentinel, sehingga data biner arbitrer yang mengandung byte NUL pun dapat disimpan dengan aman
• Seperti fungsi string ASCII yang juga bekerja pada UTF-8, operasi berbasis panjang seperti pemindaian, pemisahan, trimming, dan slicing juga bisa diterapkan pada array byte
• Format biner berakhiran NUL harus memutuskan secara terpisah apakah byte terminasi akan disimpan
  • Jika disimpan, kode baca-tulis menjadi lebih mirip dengan pemrosesan string umum
  • Jika tidak disimpan, overhead ruang dan pemrosesan bisa dikurangi, dan itulah salah satu alasan utama memakai format biner
• Format yang menyimpan panjang dan isi sekaligus tetap menambahkan byte NUL akan menghidupkan lagi ambiguitas yang sama, karena kita harus kembali memeriksa apakah panjang yang tersimpan mencakup byte terminasi

Substring tanpa alokasi dan penyalinan

• Jika terminasi NUL diwajibkan, maka trimming, slicing, splitting, tokenisasi, dan hasil pencarian juga harus menempatkan byte terminasi di ujungnya, sehingga perlu alokasi dan penyalinan string baru serta buffer perantara
• String berbasis panjang cukup mengembalikan pointer dan panjang yang menunjuk ke sebagian data asli

String StrPrefix(String str, u64 size);
String StrPostfix(String str, u64 size);
String StrChop(String str, u64 size);
String StrSkip(String str, u64 size);
String Substr(String a, u64 min, u64 max);

String StrFindNeedle(String str, String needle);
String StrTrim(String str);

• Lexer dan parser untuk CSV, Markdown, JSON, dan C dapat menyimpan slice dari buffer input sebagai nama dan nilai dalam parse tree tanpa menyalin setiap token
• Kode lanjutan yang memakai parse tree tersebut juga bisa menerima slice yang sama dan memprosesnya tanpa manajemen memori tambahan

Saat sentinel masih berguna

• Sentinel masih berguna untuk menjaga invariant struktur data dan dalam beberapa situasi dapat memberi keuntungan performa
• Pada perangkat keras dan compiler modern, keuntungan performa itu sebagian besar melemah kecuali pada kasus khusus, tetapi efeknya dalam mengurangi jumlah invariant yang harus dijaga program tetap ada
• Dalam pemeriksaan token yang ditulis manual, sentinel NUL membuat loop bisa membaca byte saat ini dengan aman
  • Lookahead seperti s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r' dapat gagal lebih awal dengan memanfaatkan urutan byte dan short-circuit evaluation
  • String berbasis panjang perlu membedakan antara token yang berakhir karena spasi dan token yang berakhir karena input memang habis, dan lookahead juga memerlukan pemeriksaan batas yang lebih sistematis
• Sebagian besar pustaka C dan API OS yang ada menuntut string berakhiran NUL, sehingga biaya konversi tetap muncul
  • Di Windows, UTF-8 memang sudah harus dikonversi ke UTF-16, sehingga biaya menambahkan byte NUL relatif kecil
  • Batasan yang dipaksakan oleh OS dan vendor bisa saja dibesar-besarkan, sementara manfaat string berbasis panjang justru diremehkan

Cara menerapkan immutabilitas pada API string

• Desain API lengkap dan abstraksi untuk lapisan string yang matang berada di luar cakupan, tetapi sebagai prinsip struktur inti, immutabilitas direkomendasikan
• Setelah dibuat, string diperlakukan seperti konstanta tanpa mengubah isinya, dan fungsi yang menerima string lalu mengembalikan string juga harus mempertahankan sifat ini
• Cukup menjamin immutabilitas pada signature fungsi dan batas API
  • Di dalam fungsi, modifikasi in-place atau pemrosesan prosedural lain tetap bisa dipakai sesuai kebutuhan
  • Pada aliran informasi tingkat atas, kita memperoleh manfaat immutabilitas ala functional programming, sementara pada implementasi tingkat bawah, fleksibilitas procedural programming tetap terjaga
• Aturan ini dapat dijalankan sebagai konvensi coding dan API meski tidak dipaksakan oleh bahasa atau runtime
• Dengan membedakan jenis string dan operasinya secara jelas, beban untuk mempertahankan aturan ini tidak besar, dan codebase dapat menentukan sendiri ruang lingkup penerapan serta kapan pelonggaran dilakukan
• Bahasa juga merupakan sebuah API, jadi kita tidak harus hanya bergantung pada batasan yang ditetapkan komite bahasa; aturan bisa dirancang dengan tingkat perincian yang diperlukan

Contoh implementasi string berbasis panjang

• RAD Debugger memakai string berbasis panjang yang didukung arena sebagai dasar di seluruh proyek, dan Metadesk adalah contoh penerapannya pada pustaka parsing mandiri
• Seri membangun lapisan berbasis codebase oleh Allen Webster memiliki episode khusus string
• Video proses belajar C dari VoxelRifts juga membahas string berbasis panjang
• Chris Wellons terus menggunakan pendekatan ini di C dan bereksperimen juga di C++
• Tulisan NRK menyertakan lampiran yang menganjurkan agar informasi panjang tidak dibuang
• Implementasi terkait juga dapat dilihat di repositori Base yang bersifat eksperimental

Keterbatasan representasi string lain

• Flexible array member

  • Seperti SDS di Redis, bagian depan struct menyimpan panjang saat ini dan kapasitas maksimum, lalu field terakhir dideklarasikan sebagai flexible array member untuk menempatkan data karakter
  • Pendekatan ini bisa menghindari pemindaian O(n) strlen dan masalah string C seperti penyambungan manual serta pengelolaan batas
  • Namun pendekatan ini sulit langsung kompatibel dengan literal string, dan tidak mendukung substring efisien yang merupakan salah satu keunggulan utama string berbasis panjang

• Stretchy buffer

  • Stretchy buffer mirip array dinamis, tetapi menyimpan header panjang dan kapasitas di area terpisah sebelum pointer, bukan dalam struct eksplisit
  • Selain kekurangan flexible array member, pendekatan ini juga memberi setiap char* aturan metadata yang nyaris tak terlihat, dan pada setiap operasi string yang bermakna, header itu harus menjadi bagian dari model API
  • Representasi pointer memang memberi type safety dan menghindari akses .str atau ->str, tetapi keuntungan ini saja sulit membenarkan aturan tersembunyi tersebut
  • Field capacity yang terpisah terasa alami untuk array dinamis, tetapi pada string ia mencampur konsep yang berbeda ke dalam satu tipe dan mengaburkan pembedaan antarjenis
  • Flexible array member juga bisa memiliki masalah serupa, tetapi ada perbedaan bahwa ukuran tetap awal dapat dipakai sebagai kapasitas dan ekspansi dinamis bisa dihindari

• Gaya Pascal

  • String pendek bergaya Pascal biasanya memakai array karakter berukuran tetap 256 byte, dengan 1 byte dicadangkan untuk panjang atau memakai terminasi NUL
  • Ini valid dalam batasan memori dan perangkat keras masa lalu, tetapi saat ini strategi alokasi memori arena yang baik tersedia, sehingga pendekatan ini kurang cocok kecuali dalam situasi khusus

Mengapa string berbasis panjang seharusnya menjadi default

• Keunggulan string berbasis panjang sudah dikenal di sebagian komunitas dan di kalangan programmer berpengalaman, tetapi banyak developer masih belum pernah mempertimbangkan implementasi seperti ini
• Materi terkait tersebar di banyak tempat, sehingga sulit membandingkan sekaligus kehilangan panjang, ambiguitas byte terminasi, pemrosesan biner, substring, kelebihan dan kekurangan sentinel, serta implementasi alternatif
• Jika tipe string default dibuat sebagai slice berbentuk pointer dan panjang, maka pelestarian informasi batas, penyederhanaan status, kompatibilitas biner, dan substring tanpa alokasi dapat diselesaikan dalam satu desain

[GN⁺]

Opini di Lobste.rs

• Menurut saya, untuk menghindari padding byte, lebih baik urutan anggota struct diubah seperti berikut

  struct String  
  {  
      u8* data;  
      u64 size;  
  };  
  

  alih-alih:

  struct String  
  {  
      u64 size;  
      u8* data;  
  };  
  

  • Di lingkungan pointer 64-bit, ukuran kedua field sama sehingga tidak ada padding dalam urutan mana pun, dan di lingkungan 32-bit, u64 untuk merepresentasikan rentang yang lebih besar daripada yang bisa ditunjuk pointer itu sendiri sudah merupakan pemborosan
    Jika memakai pointer 128-bit seperti CHERI, susunan pertama menimbulkan padding alignment di antara data dan size, sedangkan susunan kedua menimbulkan padding di akhir struct, jadi pada akhirnya tetap ada sedikit pemborosan ruang

  • Definisi yang benar adalah bentuk yang memakai anggota array panjang variabel

    typedef struct {  
      u64 len;  
      u8 buf[];  
    } String;  
    

• Standar C tidak mendefinisikan tipe u8 dan u64; ini adalah notasi bergaya Rust
  Di lingkungan 32-bit, menggunakan u64 untuk panjang juga kurang cocok, dan karena tipe idiomatis di C untuk merepresentasikan ukuran array adalah size_t, akan lebih alami bila ditulis seperti ini

  struct String  
  {  
      char* data;  
      size_t size;  
  };  
  

  Orang yang menulis artikel itu, atau LLM yang membuatnya, tampaknya tidak benar-benar paham C

  • Banyak proyek C mendefinisikan u8 dan u64 dengan typedef, dan ini praktik yang sangat umum
    Banyak juga yang merasa penamaan standar uintN_t merepotkan, ada proyek besar yang lebih tua daripada standar tersebut, dan kernel Linux juga memakai alias semacam ini
    Justru kritik itu menunjukkan kurang familier dengan proyek-proyek C

• Jika sudah menulis C atau C++ lebih dari beberapa bulan, rasanya pendekatan mengoper pointer dan panjang bersama-sama sudah merupakan hal yang sangat dikenal
  Hampir semua codebase C modern pada akhirnya mengoper pointer data dan panjang bersama-sama atau memiliki library string sendiri

  • Menyimpan panjang hanyalah salah satu masalah string C; manajemen lifetime juga sangat merepotkan
    std::string_view di C++ modern secara eksplisit menyatakan “string ini boleh dilihat, tetapi tidak boleh diubah atau disimpan”, sehingga sangat mengurangi bug
    Pada API yang menerima string C, batasan seperti ini hanya berupa janji dalam dokumentasi

• Kesalahan yang sebenarnya bukanlah penyimpanan panjang atau null-termination, melainkan konsep String itu sendiri yang terlalu luas untuk punya makna dalam konteks sembarang
  String dipakai untuk bermacam-macam tujuan, lebih dari sekadar array karakter, dan bahkan kata “karakter” di sini sendiri terlalu disederhanakan seperti lelucon fisika tentang sapi bulat di ruang hampa
  Bahkan “panjang” pun tidak jelas: apakah jumlah cluster grafem, jumlah code point, atau total byte
  Perlu juga dibedakan apa encoding-nya, apakah ditampilkan ke pengguna sehingga perlu lokalisasi, apakah sudah disanitasi, dan apakah itu nilai atomik yang tidak punya alasan untuk diubah seperti key pada map
  Dari sudut pandang ini, tipe string dalam implementasi umum menjadi sesuatu yang tidak lagi diinginkan

  • Orang kadang mengeluh karena Rust punya terlalu banyak tipe string, tetapi sebagian dari itu justru untuk menyimpan informasi semacam ini di dalam sistem tipe
    Setahu saya tidak ada library yang begitu saja menyebut jumlah cluster grafem sebagai “panjang”
    Sebagian masalah bisa diatasi dengan menjadikan UTF-8 sebagai encoding default dan memakai tipe terpisah untuk encoding lain atau array byte, dan sebagian besar sisanya bisa diekspresikan lewat sistem tipe

• Setahu saya, C tidak memiliki konsep string pada level bahasa seperti yang disediakan kebanyakan bahasa modern
  Manipulasi string disediakan oleh pustaka standar, bukan oleh bahasa itu sendiri
  K&R edisi ke-2 menjelaskan bahwa C adalah bahasa yang relatif low-level, dekat dengan hal-hal yang langsung ditangani komputer seperti karakter, angka, dan alamat, serta tidak menyediakan operasi untuk langsung memanipulasi keseluruhan objek komposit seperti string, himpunan, daftar, dan array
  Ketiadaan fitur seperti ini bisa tampak sebagai cacat besar, tetapi menjaga bahasa tetap kecil memberi keuntungan: bahasanya bisa dijelaskan dengan ringkas, dipelajari cepat, dan programmer bisa memahami keseluruhan bahasa lalu memakainya sehari-hari
  Untuk memahami mengapa C dirancang seperti ini dan mengapa fitur-fitur modern yang kini dianggap wajar tidak ada, saya sangat menyarankan membaca kata pengantar dan bagian pendahuluan K&R edisi ke-2

  • Namun, dalam arti terbatas bahwa tipe dan tata letak memori string literal menentukan bentuk library, string juga merupakan bagian dari bahasa C
    Ini tidak terlalu berbeda dari pembedaan antara bahasa dan library pada bahasa low-level seperti Rust

• Ada usulan format serialisasi seperti https://cr.yp.to/proto/netstrings.txt, dan ada juga pendekatan yang menangani struktur kompleks seperti https://web.archive.org/web/20230305073119/…
  Namun tampaknya bentuknya terlalu sederhana untuk diparse dengan aman, sehingga para pendukung fanatik XML, JSON, YAML, Protocol Buffers, dan lainnya tetap bisa terus sibuk bekerja