java-topology/defects/git/CLEAN.md

git — CWE-407 scan result: CLEAN

Scan date: 2026-03-27

Files scanned

• list-objects.c — oidset (hashset) for seen objects, O(1)
• ref-filter.c — match_pattern/match_name_as_path: O(R*P) wildmatch, but P = #patterns (bounded input), not unbounded list membership; --points-at uses oid_array with binary search (O(log N))
• commit.c — commit_list_contains: linear scan, but called only on parent lists (bounded by merge fanout, typically < 10)
• diff.c — no list membership defects found
• merge.c — no list membership defects found
• refs/files-backend.c — string_list_has_string uses binary search on sorted list; refs_verify_refnames_available uses strset (hashset) for seen dirnames
• refs/packed-backend.c — sortedcache with hashmap lookup for exact match
• commit-reach.c — in_commit_list is O(W) but called with W = #--contains targets (bounded user input, not repository scale); result is memoized per commit
• fmt-merge-msg.c — unsorted_string_list_lookup on srcs list, but srcs = #remote repos (< 10 typically), not proportional to repository size
• pack-bitmap-write.c — commit_list_contains in reverse_edges propagation, but edge lists are bounded by commit fanout (< 100 typically)
• builtin/fetch.c — hashmap for existing-ref lookup, O(1)
• upload-pack.c — strmap and oidset for all ref/object lookups, O(1)

Conclusion

No unbounded O(n²) membership defects found in the scanned git files. All membership tests in hot paths use sorted binary-search lists or hash structures.

The match_pattern wildcard matching is O(RPW) but this is structurally unavoidable for arbitrary wildcard patterns. With purely literal patterns a hash set would be faster but the API does not distinguish literal vs wildcard. This is a potential future optimization but does not qualify as CWE-407.