Mini Swift - Lexer (Faz 1) - Uğur Toprakdeviren

2009 senesinden bu yana Apple platformları için uygulama geliştirmekteyim, ARC ve StoryBoard olmadan da kod yazdığım zamanları hatırlıyorum. Apple bu süreç zarfında baya yol katetti.

Fakat Apple her ne kadar dışarıya karşı çok yüksek kullanıcı deneyimi sağlasa da, geliştiricilere aynı deneyimi sunmakta aynı kaliteyi gösteremiyor.

Swift 2014 senesinde ilk çıktıktan sonra çok hızlı bir şekilde (bu makalenin yazıldığı günde) 6.1.2 ye kadar geldi. Bu süre zarfında özellikle 1’den 2 ye geçerken String manüplasyonunda ciddi sıkıntılar yaşadılar ki, bununda bir hikayesi var her neyse konumuz Swift tarihi değil.

Swift (Apple) kontrolünde olduğu için komunite baskısına ciddi mukavemet gösterdi. Hatta komünite python, ruby tarzı syntax istedikleri zaman, bununla ilgili uzun bir yazı yayınladıklarını hatırlıyorum. Hayır syntax isteklerinizi yapmayacağız, artık daha fazla bu konuda ısrar etmeyin diye.

Her neyse, swift dilinde en çok problemli kısımlardan bir tanesi sugar (bazıları sexy diyor) syntax konusu. XCode’da geliştirme yapıyorsanız, ambigous hatası sıkça almanızın sebebi işte bu. Çünkü sugar syntax ı sağlayabilmek için arka planda bir çok performansdan ödün vermesi gerekti.

Bu süreçte acaba bu Swift lexer, parser (ast), semantic ve derleme işlemlerini, ne kadar GPU tarafında yapabilirim diye, Metal’de mini-swift projesi geliştirmeye başladım. Ve sonuçlar oldukça ilginç çıktı.

İlk başta GPU’ya geçmeden sadece SIMD tekniklerini kullanarak (saniyede 2M Token’a) kadar görebildim. Daha sonra bunu GPU’ya geçirince ilk zıplamayı gerçekleştirdim. Saniyede 9M Token a kadar çıktım ama bu M3 Metal in performansının ve yapabileceklerinin hala çok altındayı. Bunu gördüğümden biraz daha ilerledim ve yaptığım optimizasyonlar ile en nihai olarak sadece bir defa saniyede 1 Milyar token’ı gördüm ama 800M token stabil sonuç alabildim.

Bunu test etmek için maalesef yanlış yerden başladım. Telegram ve Firefox iOS’un kaynak kodunu derlemeye çalıştım. Ama maalesef, burada bir çok kod codegen ile türetildiği için backtrick problemleri ile uğraşmak zorunda kaldım. Ama bu hata bana çok büyük bir avantaj sağladı. Çünkü zor olan kısmı atlatınca, artık geriye kolay kısımlar kaldı.

Backtrick meselesi nedir? Her dilde olduğu gibi Swift dilinde de “Reserved Keyword” ler var. Ama burada çok garip bir durum var, her keyword, sıkı bir şekilde kontrole tabi değil. Yani class keywordu reserved olmasına rağmen, bunu değişken olarak kullanabiliyorsunuz. Bu konu kafamı çok karıştırdı. Ayrıca objC ile uyumlulukdan dolayı, objC de reserved keyword ler ile de çakışmaması gerekiyor.

Mesela, kodunuzda Category isminde bir değişken tanımladınız, bingo, objC deki Category reserved keywordu ile çakıştı :D. İşte bu tarz problemlerden dolayı, adı üstünde backtrick, trick i uygulanıyor.

Teknik Detaylar

Bu kısım MiniSwift Lexer Faz 1’in teknik detaylarını içermektedir.

Amaç

Lexing’i yönetilebilir ve genişletilebilir kılmak için UTF‑8 çözme/temizlemeyi (decoder) lexing den ayırıp, decoder.wgsl de yönetmek.

Bu aşamada temel tokenizasyon;

NL,
WS,
// yorum,
parantez/noktalama,
ASCII identifier

tamamladım ve pozisyonlar bayt ofsetiyle doğru bir şekilde korudum.

İki aşama: decoder.wgsl （UTF‑8 decode/sanitize） → lexer.wgsl （token üretimi）
Veri sözleşmesi: codepoints[] ve vflags[] （bayt‑indeksli） + Token[32B] + Counters
Pozisyonlar: Token.start/length bayt cinsinden, CRLF NL olarak 2 bayt
Token kapsamı (v0.1): NL, WS, COMMENT(//), PUNCT (){}[],;:, IDENT (ASCII)
Hata yönetimi: Geçersiz UTF‑8 için ERROR_INVALID_UTF8 ve invalid_utf8_count
UI/Host: İki compute pass, sıfır kopya; lexer tek thread (faz 1 için şimdilik tek thread)

Tasarım İlkeleri

Ayır ve basitleştir: UTF‑8’in tüm varyantlarını tek yerde işlemeyi (decoder) hedefledim. Böylece lexer dallanmaları azaldı, okunabilirlik arttı.
Sözleşme odaklı: Aşamalar arası sabit bir veri invariyantı tanımlandı; host/şader tarafı bu invariyantla hareket eder.
Doğru konumlandırma: Token sınırları ve konumları (satır/sütun & bayt ofset) IDE/araç entegrasyonu için birebir korunur.
GPU dostu: İki pass aynı GPU buffer’ları üzerinde çalışır; readback sadece sonda yapılır.

Veri Sözleşmeleri (ABI)

Token (32 bayt hizalı)

struct Token {
    uint32_t kind;       // TOKEN_NL, TOKEN_WS, etc.
    uint32_t start;      // Byte offset in source
    uint32_t length;     // Byte length
    uint32_t line;       // Line number (1-based)
    uint32_t column;     // Column number (1-based) 
    uint32_t reserved[3]; // Padding for 32-byte alignment
};

Counters

struct Counters {
    uint32_t input_length;
    uint32_t token_count;
    uint32_t error_count;
    uint32_t invalid_utf8_count;
    uint32_t current_line;
    uint32_t current_column;
    uint32_t reserved[2];
};

Not: Paralelleşmeye geçtiğim zaman token_count/error_count atomicolacak, ayrıca chunk state alanları (örn. pending_cr) ekleyeceğim.

Decoder → Lexer Invariyantı

codepoints[i] = cp yalnızca kod noktasının ilk baytında; devam baytlarında 0.
vflags[i] = 1 geçerli UTF‑8 dizgisi başlangıcı; 0 ise geçersiz dizi (o cp’nin ilk baytında).

indeksleme bayt bazlıdır; lexer bu yüzden start/length’i bayt olarak üretir.

Storage / Binding

decoder.wgsl: 0=src(u8|u32), 1=codepoints(u32), 4=vflags(u32), 5=stats, 6=params
lexer.wgsl: 0=codepoints, 1=vflags, 2=tokens, 3=counters

Binding indexleri projeye göre değişebilir; önemli olan bu sözleşmenin aynen korunmasıdır.

decoder.wgsl (UTF‑8 Decode & Sanitize)

Sorumluluklar

1–4 bayt UTF‑8 dizilerini çözer; geçersiz ise tek hamlede işaretler (baş baytta vflags=0).
codepoints[]'e yalnızca ilk bayta cp yazar; takip baytları 0 kalır.

Pozisyonlar bozulmasın diye, CR/LF normalizasyonu yapmaz.

Çıktılar

codepoints: array— bayt indeksli cp akışı (devam baytları 0 olur)
vflags: array— geçerli/geçersiz başlangıç bayrağı (devam baytları 0 olur)
Opsiyonel: boundaries, seq_ids, stats vs.

lexer.wgsl

Girişler: codepoints, vflags, counters.input_length
Çıkışlar: counters güncellenmiş olarak tokens[]

Temel yardımcı fonksiyonu ise şu şekilde tanımladım;

fn get_next_codepoint(pos: ptr<function, u32>) -> u32 {
    let cp = codepoints[*pos];
    if (vflags[*pos] != 0u) {
        // Valid UTF-8 sequence start
        let char_len = utf8_char_length(cp);
        *pos += char_len;
        return cp;
    } else {
        // Invalid UTF-8, skip one byte
        *pos += 1u;
        return 0xFFFD; // Replacement character
    }
}

Faz 1 için geçerli Token Kuralları

NL: \n veya \r\n → TOKEN_NL (CRLF uzunluk=2)
WS: space (0x20), tab (0x09) → TOKEN_WS
Line Comment: // … (CR/LF’e kadar) → TOKEN_COMMENT
Punctuation: (){}[],;: → TOKEN_PUNCT
IDENT (ASCII): [A‑Za‑z_][A‑Za‑z0‑9_] → TOKEN_IDENT
Hatalı UTF‑8: vflags[pos]==0 ise TOKEN_ERROR*(ERROR_INVALID_UTF8) ve invalid_utf8_count += (np-pos)*

Satır/Sütun güncellemesi

Her ilerlemede col += bayt_uzunluğu (codepoint’in toplam bayt sayısı) verdim,
NL’de line += 1; col = 1 (CRLF özel durumu: 2 bayt uzunluk) verdim,
Debug edebilmek için fonksiyon sonunda counters.current_line/col güncelledim.

Host/Pipeline Akışı

Faz 1 sürümü için basit bir akış kurdum.

Önce bufferları oluşturdum (src, codepoints, vflags, tokens, counters)
Sonra girdi uzunluğunu set ettim Counters.input_length = src.length
Decoder (yani utf8 normalizasyon işlemine) e gönderdim dispatchWorkgroups(ceil(N/256))
Buradan gelen sonucu lexer’e verdim. dispatchWorkgroups(1)
Sonra tokens + counters readback ile ui da gösterdim

Lexer için, determenistik sonuçları teyit edebilmek, racing problemleri ile başa çıkabilmek ve kolay debug edebilmek için, bilerek tek thread verdim, onu en son atomic ile 256 thread e çıkaracağım.

Faz 2 de görüşmek üzere!

Bu yazıda Mini Swift Lexer’ın ilk fazını tamamladık. GPU tabanlı Swift lexer geliştirme sürecinde Metal’in gücünden yararlanarak saniyede 800M token işleme kapasitesine ulaştık. Gelecek yazılarda parser ve semantic analiz fazlarını da paylaşacağım.

Performans Sonuçları:

SIMD (CPU): 2M token/saniye
GPU (ilk deneme): 9M token/saniye
GPU (optimized): 800M token/saniye (stabil)
GPU (peak): 1B token/saniye (tek seferlik)

Faz 2’de görüşmek üzere!