New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

type inference bug for multi-cycle functions #9770

Closed
null-a opened this Issue Jan 14, 2015 · 6 comments

Comments

Projects
None yet
4 participants
@null-a

null-a commented Jan 14, 2015

I think I might have stumbled across a bug, possibly in type inference though I'm not sure.

I'd expect that running the following would print "ok" 3 times, instead it prints "ok" once then two blank lines.

function printit(x, _)
    if _true()
        z = id(x)
        print("")
        println(z)
        :sym
    elseif _false()
        printit("ok", :foo)
    end
end

function id(x)
    if _false()
        printit(unknowntype, :foo)
    else
        x
    end
end

_false() = false
_true() = true

printit("ok", "foo")
printit("ok", :foo)
printit("ok", :foo)

Making any one of the following changes results in the expected output. Perhaps this will help point someone who understands Julia's internals at the cause of the unexpected behavior.

  1. Remove the printit("ok", "foo") line. (Results in "ok" been printed twice as expected.)
  2. Remove the :sym line.
  3. Remove the print("") line.
  4. Remove either of the if expressions leaving only the non-redundant branch.
  5. Replace unknowntype with unknowntype::ASCIIString.
  6. Remove either of the calls to printit within printit or id.

I've also just noticed that replacing println(z) with println(z==nothing ? "nothing" : z) causes a seg fault.

All of this is happening with the latest nightly build, details below. I get very similar results using v0.3.4, but not the seg fault.

Julia Version 0.4.0-dev+2689
Commit a418672 (2015-01-14 10:05 UTC)
Platform Info:
  System: Darwin (x86_64-apple-darwin13.4.0)
  CPU: Intel(R) Core(TM)2 Duo CPU     T7700  @ 2.40GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Core2)
  LAPACK: libopenblas
  LIBM: libopenlibm
  LLVM: libLLVM-3.3
@vtjnash

This comment has been minimized.

Member

vtjnash commented Jan 15, 2015

it appears that somehow inference has tricked itself into thinking that id(::ASCIIString) does not return:

julia> @code_typed printit("ok",:foo)
1-element Array{Any,1}:
 :($(Expr(:lambda, Any[:x,:_], Any[Any[:z,:_var0],Any[Any[:x,ASCIIString,0],Any[:_,Symbol,0],Any[:z,Union(),18],Any[:_var0,(ASCIIString,),0]],Any[]], :(begin  # none, line 2:
        unless true goto 0 # line 3:
        z = id(x::ASCIIString)::Union() # line 4:
        print(GetfieldNode(Base,:STDOUT,Any),"")::Any # line 5:
        println(z::Union())::Union() # line 6:
        return :sym
        goto 2
        0:  # line 7:
        unless false goto 1 # line 8:
        return printit("ok",:foo)::Union(Void,Symbol)
        goto 2
        1: 
        return
        2: 
    end::Union(Void,Symbol)))))

@vtjnash vtjnash added the bug label Jan 15, 2015

@vtjnash

This comment has been minimized.

Member

vtjnash commented Jan 25, 2015

@JeffBezanson debug dump:

julia> begin # define the problematic code
       function printit(x, _)
           _true()
           if _true()
               z = id(x)
               print("")
               println(z)
               "a"
           elseif _false()
               printit("ok", :foo)
           end
       end

       function id(x)
           if _false()
               printit(unknowntype, :foo)
           else
               x
           end
       end

       _false() = false
       _true() = true
       end
_true (generic function with 1 method)

julia> printit(":ok", ":foo") # cause it to be type inferred
:ok
"a"

julia> x=Base._methods(printit, typeof((":ok", :foo)), -1)[1] # inspect what happened
((ASCIIString,Symbol),(),printit(x,_) at none:3)

julia> linfo.tfunc # we needed to compile several functions, lets see them
9-element Array{Any,1}:
      (ASCIIString,Symbol)                                                                                          
      UInt8[0x04,0xd0,0x06,0x02,0x0c,0x04,0x00,0xca,0x08,0x03  …  0xbd,0x85,0x08,0x01,0x21,0x19,0x18,0x04,0xbd,0x86]
 false                                                                                                              
      (Any,Symbol)                                                                                                  
      UInt8[0x04,0xd0,0x06,0x02,0x0c,0x04,0x00,0xca,0x08,0x03  …  0xbd,0x85,0x08,0x01,0x21,0x19,0x18,0x04,0xbd,0x86]
 false                                                                                                              
      (ASCIIString,ASCIIString)                                                                                     
      UInt8[0x04,0xd0,0x06,0x02,0x0c,0x04,0x00,0xca,0x08,0x03  …  0xbd,0x85,0x08,0x01,0x21,0x19,0x18,0x04,0xbd,0x86]
 false   

julia> # huh, that's interesting. while inferring printit(ASCIIString, ASCIIString), we incidentally inferred (ASCIIString,Symbol) (because we needed to) but when we did so, we also failed to notice that our type information was incomplete. in particular, we first reach this method while recurring inside printit->id->printit, but at that time, we don't know the return type of id (so it's assumed to be Union(), because it's recurred), but then we proceeded to store the resulting AST (because when we recurred on id the second time, we didn't mark printit as recurred)

julia> # my resulting hypothesis? all frames between this frame and the top recurred frame need to be marked as recurred, not just those where ast0===ast

does that make sense?

@vtjnash

This comment has been minimized.

Member

vtjnash commented Jan 25, 2015

oh, wait. that is what the code doing already.

new hypothesis: there are two cycles (overlapping) going on here (at different points in the function). that causes toprec to get set in typeinf (because the printit cycle is reached second), even though that is incorrect (because it is also part of the id cycle)

@vtjnash vtjnash changed the title from Possible type inference bug to type inference bug for multi-cycle functions Jan 25, 2015

vtjnash added a commit that referenced this issue Jan 25, 2015

vtjnash added a commit that referenced this issue Jan 26, 2015

@ihnorton

This comment has been minimized.

Member

ihnorton commented Apr 6, 2015

xref #9926

vtjnash added a commit that referenced this issue Aug 21, 2015

vtjnash added a commit that referenced this issue Jan 13, 2016

vtjnash added a commit that referenced this issue Jan 24, 2016

@Keno

This comment has been minimized.

Member

Keno commented Feb 11, 2016

@JeffBezanson Could you look at this? Segfaulting on perfectly valid julia code is somewhat unfortunate and it looks like there's at least three issues now where this was reported.

@vtjnash

This comment has been minimized.

Member

vtjnash commented Feb 11, 2016

@carnaval and I were discussing ways to fix this. it's possible to do, but requires redesigning inference to be non-recursive. as a side-benefit, that design should be faster at inferring code too.

vtjnash added a commit that referenced this issue Feb 27, 2016

vtjnash added a commit that referenced this issue Mar 1, 2016

vtjnash added a commit that referenced this issue Mar 1, 2016

@vtjnash vtjnash referenced this issue Mar 1, 2016

Merged

type-inference workq #15300

2 of 2 tasks complete

vtjnash added a commit that referenced this issue Mar 1, 2016

do type-inference using a work queue
note: directly inferring linfo in pure_eval_call is unnecessary since abstract_call_gf_by_type would add this edge anyways
and it can be harmful since there was no logic here to prevent unbounded recursion in the type signature

fixes #9770

vtjnash added a commit that referenced this issue Mar 1, 2016

do type-inference using a work queue
note: directly inferring linfo in pure_eval_call is unnecessary since abstract_call_gf_by_type would add this edge anyways
and it can be harmful since there was no logic here to prevent unbounded recursion in the type signature

fixes #9770

vtjnash added a commit that referenced this issue Mar 2, 2016

do type-inference using a work queue
note: directly inferring linfo in pure_eval_call is unnecessary since abstract_call_gf_by_type would add this edge anyways
and it can be harmful since there was no logic here to prevent unbounded recursion in the type signature

fixes #9770
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment