# julia-0001: isrelocatable() scans Vector for membership per include → O(n²)

**Target:** JuliaLang/julia
**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
**File:** `base/loading.jl` — `isrelocatable()` (~line 2096)
**Status:** PATCHED

## Description

`isrelocatable()` reads the cache header to retrieve `includes` (all included
files) and `includes_srcfiles` (the subset that are source files). It then
loops over `includes` and tests `inc ∉ includes_srcfiles` to identify
include-dependencies. `includes_srcfiles` is a `Vector{CacheHeaderIncludes}`,
so `∉` compiles to a linear scan using `==` on each element. With `n` entries
in `includes` and up to `n` entries in `includes_srcfiles`, this is O(n²).

During package precompile validation, `isrelocatable()` is called for every
package in the depot. Large projects (hundreds of includes) pay quadratic cost
on every validation pass.

## Root cause

```julia
# base/loading.jl ~2102
_, (includes, includes_srcfiles, _), _... = _parse_cache_header(io, path)
for inc in includes                          # outer O(n)
    if inc ∉ includes_srcfiles               # inner O(n) Vector linear scan
        track_content = inc.mtime == -1.0
        track_content || return false
    end
end
```

`includes_srcfiles` is a `Vector{CacheHeaderIncludes}` built in
`parse_cache_header`. The `∉` operator on a Vector is O(length).

## Fix

Build a `Set{CacheHeaderIncludes}` from `includes_srcfiles` before the loop so
membership tests are O(1).

```julia
srcfiles_set = Set{CacheHeaderIncludes}(includes_srcfiles)
for inc in includes
    if inc ∉ srcfiles_set                    # O(1) hash lookup
        track_content = inc.mtime == -1.0
        track_content || return false
    end
end
```

`CacheHeaderIncludes` is a mutable struct; equality (`==`) is already defined
structurally via `isequal` fallback, and `hash` can be derived from the
`filename` field (unique per include).

## Ops numbers (Java benchmark)

See `defects/julia/unit/JuliaTest.java` (bench label "isrelocatable-includes").
At N=1000 includes: slow ~500,500 comparisons, fast ~1000 → ~500× speedup.