Karmaşıklık için Kod Okuma

Grep adaylar bulur. Okuma doğrular onları. Bir aday dosyasını açtığınızda, sorunun maliyetinin girişe bağlı olarak büyüüp büyümediğini sormalısınız?

MOAD-0001 doğrulama protokolü:

1. Dış döngüyü bulun. Döngü sınırlayıcı sayısı neyi belirler?
2. İç işlem (.contains, .indexOf, 'in'). Bu işlem neye karşı çalışır?
3. Bu veri yapısı, dış döngüyü sürükleyen girişle aynı şekilde büyüyor mu?
4. Evet: maliyet O(N²) (N=input size) ve doğrulanmış bir kusurdur.
5. Hayır: iç yapı sınırlıdır (konfigürasyon, enum, küçük sabit). Yanlış pozitif.

N düğümünü ziyaret eden bir graf dolaşı, her adımda 'visited' listesini kontrol eder: hem döngü hem de iç veri yapısı N ile büyür. Doğrulanmış.

5 admin IP'si olan bir izin listesi kontrol eden bir talep işleyicisi: izin listesi talep hacmiyle asla büyümez. Yanlış pozitif.

Her MOAD için aynı protokol uygulanır: dış sürücüyi tanımla, iç yapıyı tanımla ve her ikisinin de birlikte büyüüp büyümediğini sor.

Surge Score: Buluşlarınızı Önceliklendirin

Onaylanmış tüm kusurlar hemen onarılmasını gerektirmeyebilir. 10.000 indirekt bağımlı olan bir kütüphanede bulunan MOAD, aynı MOAD'nin özel bir iç araçta olanından daha yüksek bir sürü skoruna sahip.

Sürü skoru = hızlanma × bağımlılık derecesi. Hızlanma: Klasik üretim ölçekinde onarım ne kadar hızlı çalışır? Bağımlılık derecesi: Ondalıkta ne kadar çok alt paket veya hizmet otomatik olarak değişikliği miras alırken üstteki onu birleştirdiğinde?

Apache Maven bağımlılık çözücüsünde onaylanmış MOAD-0001, 50.000 düğüm üzerinde çalışıyor ve 1.000'den fazla otomatik olarak değişikliği miras alan Maven eklentileri var: sürü skoru çok yüksek. Bu onarımlarınızın sıralamasının önünde olmalıdır.

Bir kullanıcı için CLI aracı içinde onaylanmış MOAD-0001, hiçbir bağımlı olmadan çalışıyor: sürü skoru sıfır yakın. Onarılmalı ama acil değil.

Çalışkan vs. aç gözlü düğüm nodes. Yüksek betweenness ve yüksek hızlanma olan bir düğüm, kritik akışı ele alır ve serbest bırakıldığında alt dizinleri boşaltır. Alt dizinlerin kapasitesini doğruladıktan sonra onarılmalıdır. Yüksek out-degree ve düşük hızlanma olan düğüm, aç gözlüdür: ona beslenen her şeyi tüketir ve hiçbir acı duymaz. Çalışkan bir düğümü alt dizinlerin kapasitesini hazırlamadan önce onarmak, altyapı ölçeğinde MOAD-0005 (fırtınalı kalabalık) yaratır.

Birleştirmeye Yönlendirme: MOAD Akışını

Bir yüksek firtina puanına sahip bir kusuma onay verilir ve bu kusuprop ile bir akış boyunca geçer. Her aşama bir nesne üretir. Hiçbir aşama zorunlu değildir.

tarama → aday listesi (grep çıktısı, statik analiz sonuçları)
bilet → kusunun açıklaması (MOAD numarası, konum, karmaşıklık analizi)
patch → kod değişikliği (veri yapısı değiştirme, temel benimseme)
test → birim testi (O(1) kanıtı: N=100 ve N=10.000'de düzeltmenin süresini zamanla)
UNDF → kamuya açık açıklama gönderisi (undefect.com, kamusal alan)
açıklama → güvenlik açısından önemli ise CVE veya CWE referansı
PR → upstream pull request ile patch + test + UNDF bağlantısı
birleştirme → bakıcı kabulü; düzeltme sürüklemeye yönelik sürüm artışı aracılığıyla yayılır

Her nesne bir sonraki aşama için beslenir. Bir patche test olmadan doğrulanamaz. Bir test olmadan açıklama başka örneklerin aynı desene göre yayılmasını engeller. Bir açıklama olmadan upstream PR'ye bağlı kalmak, düzeltmenin bir fork'ta kalmasına neden olur.

Bir MOAD post (UNDF) aşaması en çok mühendisler tarafından atlanmaktadır. Kusuyu düzelttikten sonra, bir PR gönderirler ve kendilerini tamamladıklarını düşünürler. Ama bir düzeltme olmadan adlandırılmış bir postsa, gelecekte aynı deseni karşılayan her mühendis aynı sorunu ve düzeltmeyi yeniden keşfetmek zorunda kalır. Bir MOAD post, deseni adlandırır, tespit yöntemini gösterir ve patche bağlantılıdır. Gelecekteki araştırmacılar, düzeltmeyi desen adı üzerinde arama yaparak bulur.

Küresel ölçekte planet düzeltme. Geniş kullanılan bir kütüphanede yaygın olarak bulunan MOAD-0001 düzeltmesi, onu ithal eden her proje için yayılır. Bir MOAD postu, kütüphaneyi asla güncellemeyen projelerdeki mühendislere de düzeltmeyi öğrenmelerini sağlar. Her iki yol paralel olarak çalışır.

Kusü Ticketi Yazma

İyi bir kusü ticketi, beş soruyu yanıtlar:

1. Nerede: tam dosya, sınıf, yöntem ve satır aralığı
2. Ne: veri yapısı türü ve üzerindeki işlem
3. Niçin: karmaşıklık analizi (N ile O(N²) veya daha kötü, N'in tanımlanması)
4. Etki: en kötü durumda davranışa ne tür girişler neden olur ve ne kadar büyük bir ölçekte?
5. Düzeltme: değiştirilmesi gereken veri yapısı veya temel

Herhangi bir analizini okuma olmadan önce kusuyu tekrarlayabilen ve düzeltmeyi doğrulayabilen bir ticket oluşturmak için tüm beş soruyu yanıtlamanız gerekir. (3) veya (4) sorularını atlayan bir ticket, bakıcının karmaşıklık analizi yapmadan önce düzeltmeyi doğrulaması gerektiği anlamına gelir. Bu ekleme, birleştirme olasılığını azaltır.

Güvenilirlik katlanır. İlk PR'de açık bir bilet, iyi hedeflenmiş bir patch ve performans testi bulunursa kabul edilir. Aynı yazarın ikinci bir PR'si daha az direnişle gözden geçirilir. Üçüncü bir PR ilk iki tanenin kabul edilmesinden sonra sürüdürücü tarafından gözden geçirilir. Açık kaynakta itibar, eserlerin defteridir: her kabul edilen patch, bir sonraki için güvence sağlar.

Gerçek Bir Adayı Okuma

Burada Python'da gerçek bir MOAD-0001 adayı bulunmaktadır. Okuyup triage protokolünü tamamlayın.

class DependencyResolver:
    def resolve(self, package, resolved=None, seen=None):
        if resolved is None:
            resolved = []
        if seen is None:
            seen = []
        if package in seen:
            return
        seen.append(package)
        for dep in self.registry.get_dependencies(package):
            self.resolve(dep, resolved, seen)
        resolved.append(package)
        return resolved

Triage soruları:

1. `seen` ne tür bir veri yapısı?
2. 6. satırda hangi işlem gerçekleştiriliyor?
3. `seen` büyüklük ile büyür mü?
4. Recursive çağrılara yol gösteren döngi de büyüklük ile büyür mü?
5. Bu, doğrulanmış bir MOAD-0001 mi, yoksa yanlış pozitif mi?

Patchınız

Bir doğrulanmış hasar yüksek bir dalga skoru gerektirir: kodu düzelt, iyileşmeyi kanıtlayacak bir test ve MOAD post özetini.

Test, düzeltmeden önce ve sonra geçeceğinden doğruluk testi olmalıdır. Doğruluk testi, çıktı değişmediğinden - bu da noktasıdır - geçerlidir. İki girdi boyutunda performans testi, iyileşmeyi kanıtlar:

import time

def build_graph(n):
    # n paketler, her biri önceki pakete bağlı
    return {f'pkg{i}': [f'pkg{i-1}'] if i > 0 else [] for i in range(n)}

for n in [100, 1000, 5000]:
    registry = build_graph(n)
    resolver = DependencyResolver(registry)
    start = time.perf_counter()
    resolver.resolve(f'pkg{n-1}')
    elapsed = time.perf_counter() - start
    print(f'n={n}: {elapsed:.4f}s')

Düzeltmeden önce, zaman n'in karesiyle doğrusal olarak artar. Düzelttikten sonra, doğrusal olarak artar. Her ikisi de PR açıklamasına yazılır.

A MOAD post outline covers: the pattern name, the substrate (Python dependency resolver), the detection method (grep for in seen where seen starts as []), the fix, & a link to your PR. The post goes to undefect.com as public domain. Future engineers searching for 'Python list membership in loop slow' will find it.