# Piracy hunting

**URL:** <https://discourse.julialang.org/t/piracy-hunting/90119>\
**Category:** Tooling\
**Created:** [November 11, 2022, 1:37pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119 "2022-11-11T13:37:43Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [November 11, 2022, 1:37pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/1 "2022-11-11T13:37:43Z")

</div>

I made a script to detect piracy, and I’d like feedback. Eventually I hope to put the functionality in Aqua.jl. There is already an old thread with a similar script here: [Pirate Hunter](https://discourse.julialang.org/t/pirate-hunter/20402). However, the script to longer works for me, as it both have quite many false positives, and it also fails to detect some pretty blatant cases of piracy, so I rewrote it. Thanks to @oxinabox for the original implementation

## How it works

Load a package `MyPkg`, then do `hunt(MyPkg)`

- First, it traverses all objects reachable from the given module which are of type `Union{Function, Type}`, and calls `methods` on it, filtering away all methods originating in `Core` or `Base`, as these are assumed to not be piracy
- It filters to keep methods that 1) originate from `MyPkg`, and 2) are pirates
- Pirate methods is defined as a method defined in package `X` where neither the function, nor any of its arguments are from package `X`. The definition can get a little tricky with parametric types, varargs and unions, but I think my definition makes sense.

## Current problems

- ~~Its suuuper slow, since it needs to traverse and examinate _every reachable object_. It takes about 2 minutes. Not sure how to improve it, but feedback is very welcome~~ Edit: Thanks to comment from @kristoffer.carlsson, it’s now reasonably fast!
- I’m not 100% sure my definition of piracy is correct for edge cases. I tried on a few of my own packages, but I’d like feedback

```julia
const Callable = Union{Function, Type}
const DEFAULT_PKGS = (Base.PkgId(Base), Base.PkgId(Core))

function all_methods(
    mod::Module,
    done_modules::Base.IdSet{Module}, # cached to prevent inf loops
    done_callables::Base.IdSet{Callable}, # cached to prevent inf loops
    result::Vector{Method},
    filter_default::Bool
)::Vector{Method}
    push!(done_modules, mod)
    for name in names(mod; all=true, imported=true)
        # names can list undefined symbols which cannot be eval'd
        isdefined(mod, name) || continue
        
        # Skip closures
        first(String(name)) == '#' && continue
        val = Core.eval(mod, name)
        
        if val isa Module
            if !in(val, done_modules)
                all_methods(val, done_modules, done_callables, result, filter_default)
            end
        elseif val isa Callable
            if !in(val, done_callables)
                for method in methods(val)
                    # Default filtering removes all methods defined in DEFAULT_PKGs,
                    # since these may pirate each other.
                    if !(filter_default && in(Base.PkgId(method.module), DEFAULT_PKGS))
                        push!(result, method)
                    end
                end
            end
            push!(done_callables, val)
        end
    end
    result
end

function all_methods(mod::Module; filter_default::Bool=true)
    all_methods(mod, Base.IdSet{Module}(), Base.IdSet{Callable}(), Method[], filter_default)
end

##################################
# Generic fallback
is_foreign(@nospecialize(x), pkg::Base.PkgId) = is_foreign(typeof(x), pkg)
is_foreign(mod::Module, pkg::Base.PkgId) = Base.PkgId(mod) != pkg

function is_foreign(@nospecialize(T::DataType), pkg::Base.PkgId)
    params = T.parameters
    # For Type{Foo}, we consider it to originate from the same as Foo
    if Base.typename(T).wrapper === Type
        return is_foreign(only(params), pkg)
    else
        # Both the type itself and all of its parameters must be foreign
        return is_foreign(T.name.module, pkg) && all(params) do param
            is_foreign(param, pkg)
        end
    end
end

function is_foreign(@nospecialize(U::UnionAll), pkg::Base.PkgId)
    # We do not consider extending Set{T} to be piracy, if T is not foreign.
    # Extending it goes against Julia style, but it's not piracy IIUC.
    is_foreign(U.body, pkg) && is_foreign(U.var, pkg)
end

is_foreign(@nospecialize(T::TypeVar), pkg::Base.PkgId) = is_foreign(T.ub, pkg)
is_foreign(@nospecialize(T::Core.TypeofVararg), pkg::Base.PkgId) = is_foreign(T.T, pkg)

function is_foreign(@nospecialize(U::Union), pkg::Base.PkgId)
    # Even if Foo is local, overloading f(::Union{Foo, Int}) with foreign f 
    # is piracy.
    any(Base.uniontypes(U)) do T
        is_foreign(T, pkg)
    end
end

function is_pirate(meth::Method)
    method_pkg = Base.PkgId(meth.module)

    signature = meth.sig
    while signature isa UnionAll
        signature = signature.body
    end

    all(signature.parameters) do parameter
        is_foreign(parameter, method_pkg)
    end
end

#######################################
hunt(;from::Module=Main) = filter(is_pirate, all_methods(from))
hunt(mod::Module; from::Module=Main) = hunt(Base.PkgId(mod); from=from)
hunt(pkg::Base.PkgId; from::Module=Main) = filter(all_methods(from)) do method
    is_pirate(method) &&
    Base.PkgId(method.module) === pkg
end

```

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 11, 2022, 2:02pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/2 "2022-11-11T14:02:20Z")

</div>

Use a `Base.IdSet` over a `Set` and perf should be better.

```julia
julia> @time hunt() # default
 89.321905 seconds (326.64 M allocations: 15.402 GiB, 4.56% gc time, 98.73% compilation time)

julia> @time hunt(); # `IdSet
  0.546979 seconds (1.10 M allocations: 60.358 MiB, 0.80% gc time)

```

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [November 11, 2022, 2:25pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/3 "2022-11-11T14:25:47Z")

</div>

That’s fantastic, thanks! Real easy ~150x speedup 😃

---

<div class="post-metadata">

**Author:** ![sjkelly](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sjkelly/32/9280_2.png) [@sjkelly](https://discourse.julialang.org/u/sjkelly)\
**Post date:** [November 11, 2022, 2:26pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/4 "2022-11-11T14:26:53Z")

</div>

Wow nice!

> Eventually I hope to put the functionality in Aqua.jl

This would be amazing. I am a big fan of Aqua!

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [November 11, 2022, 4:29pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/5 "2022-11-11T16:29:43Z")

</div>

Doesn’t it say 98.73% compilation time for the first call?  
So the speedup might be slower?

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [November 11, 2022, 4:48pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/6 "2022-11-11T16:48:03Z")

</div>

1.27% of 89 seconds is more than one second as far as I can tell, so the sped up function looks faster also at runtime?

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [November 11, 2022, 4:48pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/7 "2022-11-11T16:48:59Z")

</div>

Yeah agree, I wanted to point out that it’s not 150x 😃

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [November 11, 2022, 5:29pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/8 "2022-11-11T17:29:36Z")

</div>

Way to do something about global warming. Us Pastafarians salute you.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 11, 2022, 6:09pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/9 "2022-11-11T18:09:14Z")

</div>

> [@roflmaostc](#):
>
> Doesn’t it say 98.73% compilation time for the first call?

You will likely run this once. So what matters is end to end time.

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [November 11, 2022, 7:40pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/10 "2022-11-11T19:40:14Z")

</div>

Just to clarify: the second call didn’t include any compilation time, does it?  
But it should have, if it’s called the first time?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 12, 2022, 9:28am UTC](https://discourse.julialang.org/t/piracy-hunting/90119/11 "2022-11-12T09:28:47Z")

</div>

I don’t remember. You can run them again to get a more accurate response if you want.

---

<div class="post-metadata">

**Author:** ![gustaphe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gustaphe/32/18174_2.png) [@gustaphe](https://discourse.julialang.org/u/gustaphe)\
**Post date:** [November 12, 2022, 10:42pm UTC](https://discourse.julialang.org/t/piracy-hunting/90119/12 "2022-11-12T22:42:50Z")

</div>

This may be a stupid suggestion, but couldn’t you do this analysis on the code rather than on the loaded module? So you parse the code, collect all imported functions and check that they are never given methods without locally defined types in the signature. Seems like that would be faster.

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [November 14, 2022, 10:47am UTC](https://discourse.julialang.org/t/piracy-hunting/90119/13 "2022-11-14T10:47:03Z")

</div>

You were right!

But why is the compilation time of `Set` vs `Base.IdSet` so bad?

```julia
julia> include("/tmp/piracy_IdSet.jl")
hunt (generic function with 3 methods)

julia> @time hunt()
  0.485699 seconds (1.43 M allocations: 77.007 MiB, 1.98% gc time, 15.50% compilation time)
[1] adjoint(B::Union{BitMatrix, BitVector}) in LinearAlgebra at /home/fxw/.julia/juliaup/julia-1.8.2+0.x64
[...]

julia> @time hunt()
 0.394691 seconds (1.32 M allocations: 71.240 MiB, 1.70% gc time)
[1] adjoint(B::Union{BitMatrix, BitVector}) in LinearAlgebra at /home/fxw/.julia/juliaup/julia-1.8.2+0.x64
[...]
...

# new shell
julia> include("/tmp/piracy_set.jl")
hunt (generic function with 3 methods)

julia> @time hunt()
 73.374539 seconds (455.11 M allocations: 21.454 GiB, 5.86% gc time, 98.89% compilation time)
[1] adjoint(B::Union{BitMatrix, BitVector}) in LinearAlgebra at /home/fxw/.julia/juliaup/julia-1.8.2+0.x64
[...]

julia> @time hunt()
  0.424547 seconds (1.34 M allocations: 71.242 MiB, 3.20% gc time)
[1] adjoint(B::Union{BitMatrix, BitVector}) in LinearAlgebra at /home/fxw/.julia/juliaup/julia-1.8.2+0.x64/share/julia/stdlib/v1.8/LinearAlgebra/src/bitarray.jl:237
[...]

```

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 14, 2022, 11:12am UTC](https://discourse.julialang.org/t/piracy-hunting/90119/14 "2022-11-14T11:12:49Z")

</div>

> [@roflmaostc](#):
>
> But why is the compilation time of `Set` vs `Base.IdSet` so bad?

It might be specializing the `push!` method on every `function` (which are all different types) or something along those lines.

---

<div class="post-metadata">

**Author:** ![jakobnissen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jakobnissen/32/13477_2.png) [@jakobnissen](https://discourse.julialang.org/u/jakobnissen)\
**Post date:** [November 14, 2022, 11:30am UTC](https://discourse.julialang.org/t/piracy-hunting/90119/15 "2022-11-14T11:30:17Z")

</div>

> It might be specializing the `push!` method on every `function` (which are all different types) or something along those lines.

That’s it. The normal script compiles 380 specializations (according to SnoopCompile) - without `Base.IdSet`, it compiles nearly 191,000.  
The script is also inherently type unstable, since the value of `val` cannot possibly be known at compile time. So even after all these methods are compiled, it’s slow to find the correct matching specialization out of the thousands compiled.

That’s a general pattern in Julia: If your code is very type unstable (with lots of possible types), it’s more efficient to not specialize your code than it is to specialize.