Repository files navigation

The slow descent into madness

Cthulhu can help you debug type inference issues by recursively showing thetype-inferred code until you find the exact point where inference gave up,messed up, or did something unexpected. Using the Cthulhu interface, you candebug type inference problems faster.

Cthulhu's main tool,descend, can be invoked like this:

descend(f, tt)# function `f` and Tuple `tt` of argument types@descendf(args)# normal call

descend allows you to interactively explore the type-annotated sourcecode by descending into the callees off.Press enter to select a call to descend into, select ↩ to ascend,and press q or control-c to quit.You can also toggle various aspect of the view, for example to suppress"type-stable" (concretely inferred) annotations or view non-concretetypes in red.Currently-active options are highlighted with color; press the correspondingkey to toggle these options. Below we walk through a simple example ofthese interactive features; you can also see Cthulhu v2.8 in action inthis video.

functionfoo()    T=rand()>0.5? Int64: Float64sum(rand(T,100))enddescend(foo, Tuple{})# option 1: specify by function name and argument types@descendfoo()# option 2: apply `@descend` to a working execution of the function

If you do this, you'll see quite a bit of text output. Let's break it down andsee it section-by-section. At the top, you may see something like this:

This shows your original source code (together with line numbers, which here were in the REPL).The cyan annotations are the types of the variables:Union{Float64, Int64} means "either aFloat64or anInt64".Smallconcrete unions (where all the possibilities are known exactly) are generally are not a problemfor type inference, unless there are so many that Julia stops trying to workout all the different combinations (seethis blog postfor more information).

Note: if the function has default positional or keyword arguments, you may see only the signatureof the function. Internally, Julia creates additional methods to fill in default arguments, which in turn call the "body" method that appears in the source text. If you're descending into one of these "default-filling" functions,you won't be able to see types on variables that appear in the body method, so to reduce confusing the entire body is eliminated. You'll have an opportunity to descend further into the "body" method in the "call menu" described below.

In the next section you may see something like

This section shows you some interactive options you have for controlling the display.Normal text inside[] generally indicates "off", and color is used for "on" or specific options.For example, if you hitw to turn on warnings, now you should see something like this:

Note that thew in the[w]arn toggle is now shown in cyan, indicating that it is "on."Now you can see small concrete unions in yellow, and concretely inferred code in cyan.Serious forms of poor inferrability are colored in red (of which there are none in this example);these generally hurt runtime performance and may make compiled code more vulnerable to being invalidated.

In the final section, you see:

This is a menu of calls that you can further descend into. Move the dot• with the up and downarrow keys, and hit Enter to descend into a particular call. Note that the naming of calls can sometimesvary from what you see in the source-text; for example, if you're descending into kwarg-functionfoo,then the "body" function might be called something like#foo#123.

Any calls that are made at runtime (dynamic dispatch) cannot be descended into;if you select one, you'll see

[ Info: This is a runtime call. You cannot descend into it.

and the call menu will be printed again.

Calls that start with%nn = ... are in Julia's internalAbstract Syntax Tree (AST) form;for these calls, Cthulhu and/orTypedSyntax (a sub-package living inside the Cthulhu repository) failed to "map" the call back to the original source code.

As a word of warning,mapping type inference results back to the source is hard, and there may be errors or omissions in this mapping. See theTypedSyntax README for further details about the challenges. When you think there are reasons to doubt what you're seeing, a reliable but harder-to-interpret strategy is to directly view the[T]yped code rather than the[S]ource code.

For problems you encounter, please consider filing issues for (and/or making pull requests to fix) any failures you observe. SeeCONTRIBUTING.md for tips on filing effective bug reports.

• @descend_code_typed
• descend_code_typed
• @descend_code_warntype
• descend_code_warntype
• @descend: Shortcut for@descend_code_typed
• descend: Shortcut fordescend_code_typed

Cthulhu also provides the "upwards-looking"ascend. Whiledescend allowsyou to explore a call tree starting from the outermost caller,ascendallows you to explore a call chain or tree starting from the innermostcallee. Its primary purpose is to support analysis of invalidation and inferencetriggers in conjunction withSnoopCompile,but you can use it as a standalone tool.There is avideo using ascend to fix invalidations,where the part onascend starts at minute 4:55.

For example, you can use it to examine all the inferred callers of a method instance:

julia> m=which(length, (Set{Symbol},))length(s::Set)in Base at set.jl:55julia> mi= m.specializations[1]# or `mi = first(Base.specializations(m))` on Julia 1.10+MethodInstanceforlength(::Set{Symbol})julia>ascend(mi)Choose a callfor analysis (q to quit):>length(::Set{Symbol})union!(::Set{Symbol},::Vector{Symbol})Set{Symbol}(::Vector{Symbol})intersect!(::Set{Union{Int64, Symbol}},::Vector{Symbol})_shrink(::typeof(intersect!),::Vector{Union{Int64, Symbol}},::Tuple{Vector{Symbol}})intersect(::Vector{Union{Int64, Symbol}},::Vector{Symbol})union!(::Set{Symbol},::Set{Symbol})union!(::Set{Symbol},::Set{Symbol},::Set{Symbol})union(::Set{Symbol},::Set{Symbol})

You use the up/down arrows to navigate this menu, enter to select a call todescend into,and your space bar to toggle branch-folding.

It also works on stacktraces. If your version of Julia stores the most recent error in the globalerr variable, you can use

julia>using Cthulhujulia>sqrt(-1)ERROR: DomainError with-1.0:sqrt will onlyreturn a complex resultif called with a complex argument. Trysqrt(Complex(x)).Stacktrace: [1]throw_complex_domainerror(f::Symbol, x::Float64)   @ Base.Math./math.jl:33 [2] sqrt   @./math.jl:677 [inlined] [3]sqrt(x::Int64)   @ Base.Math./math.jl:1491 [4] top-level scope   @ REPL[1]:1julia>ascend(err)Choose a callfor analysis (q to quit):>throw_complex_domainerror(::Symbol,::Float64) at./math.jl:33sqrt(::Int64) at./math.jl:1491

If this isn't available to you, a more "manual" approach is:

julia> bt=try           [sqrt(x)for xin [1,-1]]catchcatch_backtrace()end;julia>ascend(bt)Choose a callfor analysis (q to quit):>throw_complex_domainerror(::Symbol,::Float64) at./math.jl:33       sqrt at./math.jl:582=> sqrt at./math.jl:608=> iterate at./generator.jl:47=> collect_to! at./array.jl:710=>collect_to_with_first!(::Vector{Float64},::Float64,::Base.Generator{Vector{Int64}, typeof(sqrt)},::Int64) at./array.jl:688collect(::Base.Generator{Vector{Int64}, typeof(sqrt)}) at./array.jl:669eval(::Module,::Any) at./boot.jl:360eval_user_input(::Any,::REPL.REPLBackend) at/home/tim/src/julia-master/usr/share/julia/stdlib/v1.6/REPL/src/REPL.jl:139...

The calls that appear on the same line separated by=> represent inlined methods; when you select such a line,you enter at the final (topmost) call on that line.

Using Cthulhu may be particularly useful forMethodErrors, since those exist purely in the type-domain.

By default,

• descend views non-optimized code without "warn" coloration of types
• ascend views non-optimized code with "warn" coloration

You can toggle between these witho andw.

Cthulhu has access only to "static" type information, the same information available to the Julia compiler and type inference.In some situations, this will lead to incomplete or misleading information about type instabilities.

Take for example:

using Infiltrator:@infiltrateusing Cthulhu:@descendusing Base:@noinline# already exported, but be explcitfunctionfoo(n)    x= n<2?2* n:2.5* n    y= n<4?3* n:3.5* n    z= n<5?4* n:4.5* n# on Julia v1.6, there is no union splitting for this number of cases.bar(x, y, z)end@noinlinefunctionbar(x, y, z)string(x+ y+ z)end

Then invoke:

Cthulhu.@descendfoo(5)

Now, descend intobar: move the cursor down (or wrap around by hitting the up arrow) untilthe dot is next to thebar call:

 ⋮   4  (4.5 * n::Int64)::Float64 • 6 bar(x, y, z)   ↩

and then hit Enter. Then you will see the code forbar with its type annotations.

Notice that many variables are annotated asUnion.To give Cthulhu more complete type information, we have to actually run some Julia code. There are many ways to do this. In this example, we useInfiltrator.jl.

Add an@infiltrate:

functionfoo(n)    x= n<2?2* n:2.5* n    y= n<4?3* n:3.5* n    z= n<5?4* n:4.5* n# on Julia v1.6, there is no union splitting for this number of cases.@infiltratebar(x, y, z)end@noinlinefunctionbar(x, y, z)string(x+ y+ z)end

Now invokefoo to get REPL in the scope just beforebar gets called:

julia>foo(4)Infiltratingfoo(n::Int64) at ex.jl:10:infil>

Enter@descend bar(x, y, z) you can see that, forfoo(4), the types withinbar are fully inferred.

While Cthulhu tries to place type-annotations on the source code, this obscuresdetail and can occassionally go awry (see detailshere).For anyone who needs more direct insight, it can be better to look directly at Julia'sinternal representations of type-inferred code.Looking at type-inferred code can be a bit daunting initially, but you grow morecomfortable with practice. Consider starting with atutorial on "lowered" representation,which introduces most of the new concepts. Type-inferrred code differs fromlowered representation by having additional type annotation.Moreover,call statements that can be inferred are converted toinvokes(these correspond to static dispatch), whereas dynamic dispatch is indicated by theremainingcall statements.Depending on whether you're looking at optimized or non-optimized code,it may also incorporate inlining and other fairly significant transformationsof the original code as written by the programmer.

This video demonstrates Cthulhu for viewing "raw" type-inferred code:Watch on YouTube

The version of Cthulhu in the demo is a little outdated, without the newest features,but may still be relevant for users who want to view code at this level of detail.

The default configuration of toggles in the@descend menu can be customizedwithCthulhu.CONFIG and persistently saved (via Preferences.jl) usingCthulhu.save_config!():

julia> Cthulhu.CONFIG.enable_highlighter=true# Change defaulttruejulia> Cthulhu.save_config!(Cthulhu.CONFIG)# Will be automatically read next time you `using Cthulhu`