26 lines
1.8 KiB
Markdown
26 lines
1.8 KiB
Markdown
# 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(R*P*W) 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.
|