Add devdocs on UB

[Keno]

This adds some basic devdocs for undefined behavior, since there keep being complaints that it's not written down anywhere. The list of UB is just what I remembered off the top of my head, it's probably incomplete, since we haven't historically been particularly careful about this. This way, at least when people add new sources of UB, they'll have a centralized place to write that down.

[mbauman]

I really don't like this, but thank you.

My previous — obviously wrong — understanding was that the Julia compiler was trying to guard us from LLVM's undefined behaviors via freezes and such. In particular, because the observable behavior of Julia is the spec, it's impossible to know whether, e.g., accessing undef bitstypes are simply arbitrary values or UB — users only see the arbitrary values. Apparently this particular thing isn't UB anymore (yay!), but users are regularly leaning on other sorts of UB here, too.

I think part of my issue here is just how aggressively and adversarially other compiler teams have historically used a very legalistic reading of UB to do absurd things. For example, my mental model was that changing a const was just putting me at risk of using the old value in some places — and those places simply aren't specified. That's just fine. Now, sure, you might not decide to make entire function bodies no-ops when they contain a changed-const var, but another compiler dev could look at this list and see a juicy spot for a great optimization.

[oscardssmith]

@mbauman there are already cases where changing a const can lead to a method being optimized out. Consider, for example

const a = true
r() = a
r()
a=false
function f()
    if r() == a
        println("always happens")
    else
        println("never happens")
    end
end
using Debugger
@run f()
always happens
f()
never happens

Despite the fact that r is defined to return a, this code currently prints out "never happens". In general, most inconsistencies end up as full scale UB because if the compiler can derive false, anything can happen.

Since we have had the ability to define typed globals, I wonder if we should make redefining a const into an error...

[mbauman]

That matches my expectations, though. It's just fine that r() uses an old value of a and f() uses a new one and that the two may not be consistent. That feels markedly different than UB — which grants the compiler leeway to compile f() to nothing (executing neither branch and outputting nothing) because you've broken some devdocs law.

Edit to add: I fully understand your point about how inconsistencies like these can "bubble up" to larger unexpected behaviors, but to my understanding the distinction between an undefined behavior and an unspecified behavior is exactly how the language behaves in doing that "bubbling up." If the value of a is unspecified, then all language semantics must still be followed; you just aren't sure what value you'll see at any given point. If using a is undefined behavior, however, then the language is free to use alternative semantics — it can decide to skip calls to f(a) entirely, throw away whole code blocks, etc.

[Seelengrab]

My previous — obviously wrong — understanding was that the Julia compiler was trying to guard us from LLVM's undefined behaviors via freezes and such.

That is not so - admittedly, without a specified memory model it's a bit hard to do for everything in this PR (things involving pointers in particular, though those operations generally inherit the semantics of C by necessity), but in principle everything here can be justified as being in this document through Julia semantics alone. Undefined behavior is not something that bubbles up from a lower level of abstraction, but is inherent to every level of abstraction, to some extent (and with sometimes more disliked behavior than other times). Getting an error when calling lowercase on a String containing malformed UTF-8 is just as much "undefined behavior" (in the sense that it's not defined what exactly happens when you try to do that) as misusing @inbounds is - the latter usually just has much more disastrous effects. Actually getting an error you can handle is a gazillion times better than silent memory corruption.

This difficulty is part of the reason why I want to get away from the term "undefined behavior", because people generally think "ah, this is this nasty C business with pointers and boundschecking and stuff" instead of "I'm relying on behavior that is not specified/guaranteed to continue to exist".

[vtjnash]

Getting an error when calling lowercase on a String containing malformed UTF-8 is just as much "undefined behavior" (in the sense that it's not defined what exactly happens when you try to do that) as misusing @inbounds is

In C standards and related common usage, the former is called "unspecified behavior", not undefined behavior and makes a precise distinction between them. However it is also true that many UTF-8 decoders are unsound if they encounter any malformed data and therefore they will cause undefined behavior (but this is not true of the Julia decoder).

[mbauman]

I don't disagree with any of the things in this PR being marked as unspecified or implementation-defined or flat-out invalid.

What I dislike is the term UB and the privilege that it traditionally grants the compiler — it's not generic "nasty C pointer stuff," it's the way in which UB wrecks mayhem around it. It's how UB propagates not just forwards in the execution context but also backwards in how it affects the entire function's compilation. It's how C compilers will notoriously delete error checks that were naively (and, yes, improperly) trying to "catch" some UB.

It's how, if invalid string codeunits were included in this list as UB, it'd grant Julia the license to skip the error entirely. And how that might only happen in some contexts. And how trying to test for invalid codeunits would itself be invalid and eligible for deletion. Even if the UB is scoped to s = lowercase(invalid_string), it still would allow Julia to skip the error entirely. And then do arbitrary deletions with downstream uses of s. That's why I dislike UB.

This document cuts two ways: it sets guardrails for users, and it grants license to the compiler devs. The guardrails for user APIs need to be in user docs, not devdocs.

[Keno]

That matches my expectations, though. It's just fine that r() uses an old value of a and f() uses a new one and that the two may not be consistent. That feels markedly different than UB — which grants the compiler leeway to compile f() to nothing (executing neither branch and outputting nothing) because you've broken some devdocs law.

const replacement is definitely full on UB. The runtime tries to recover as best it can to limit fallout (by disallowing some of the more egregious cases), but it's not at all modeled. Because of the checks, it took me a few minutes to come up with an example, but it's not particularly hard:

julia> struct Foo
       x::Any
       end

julia> const r = Foo(Ref{Any}());

julia> @noinline function f()
       x = getfield(@__MODULE__, :r).x
       Base.donotdelete(x)
       Base.compilerbarrier(:const, x)
       end
f (generic function with 1 method)

julia> g() = f()[]
g (generic function with 1 method)

julia> h() = g()
h (generic function with 1 method)

julia> @code_typed h()
CodeInfo(
1 ─ %1 = invoke Main.f()::Base.RefValue{Any}
│   %2 = Base.getfield(%1, :x)::Any
└──      return %2
) => Any

julia> const r = Foo(1.0)
WARNING: redefinition of constant Main.r. This may fail, cause incorrect answers, or produce other errors.
Foo(1.0)

julia> g()

[64236] signal (11.2): Segmentation fault: 11
in expression starting at none:0
typekeyvalue_hash at /Users/keno/julia/src/jltypes.c:1637 [inlined]
lookup_typevalue at /Users/keno/julia/src/jltypes.c:1067
jl_inst_arg_tuple_type at /Users/keno/julia/src/jltypes.c:2199
jl_f_tuple at /Users/keno/julia/src/builtins.c:915
indexed_iterate at ./pair.jl:42 [inlined]
indexed_iterate at ./pair.jl:42

Doing an example to turn this into launching space invaders is left as an exercise to the reader.

[Keno]

invalid string codeunits were included in this list as UB

Clearly they're not

[mbauman]

Clearly, I know.

That const replacement crash is a good example, thanks. But it still feels different to me than how UB has traditionally been exploited by other compilers. Maybe it’s just my feels, but even in that crash the compiler seems doing something reasonable — albeit problematic. I know that reasonable is in the eye of the beholder, but that’s at the crux of it — users and compiler devs have historically had very different views on what reasonable behaviors might be.

I just don’t want to have to argue with a legalistic and maliciously compliant compiler.

I dunno, obviously this ship has already sailed. It’s definitely better to have it written down.

[gbaraldi]

I guess to be clear, we exploit similar things in julia i.e assuming consts don't change. It's just that our UB surface area is a lot smaller than C's which is the issue with C in itself. Any code with UB is a code with bugs, most of those become runtime errors for us, but C doesn't have that so it just assumes they never happen.

We could create a new term for it, but it would mean exactly the same as UB

[Seelengrab]

In C standards and related common usage, the former is called "unspecified behavior", not undefined behavior and makes a precise distinction between them.

You're right, it's unspecified behavior, not undefined behavior. The exact definition of what that is though is also not consistent across languages, so it seems to me we'd be in need of a definition for that as well...

It's how, if invalid string codeunits were included in this list as UB, it'd grant Julia the license to skip the error entirely.

Note that I haven't claimed either "invalid string codeunits" nor "malformed string codeunits" (very different things!) themselves to be UB - String itself only guarantees to be a "bag of bytes", which is perfectly fine. In practice, I think we generally assume String to be well-formed UTF-8 though, which is why I'm saying that "UB is behavior that we assume never happens" is a bad definition of UB (and is where IMO the angle "let's leverage this for optimization" comes from). I'd much rather define UB in terms of hard language semantics/invariants that must not be violated, but for that we'll need a memory model...

This document cuts two ways: it sets guardrails for users, and it grants license to the compiler devs. The guardrails for user APIs need to be in user docs, not devdocs.

Yes, I agree with that! One caveat though: since Julia doesn't have a spec, writing this down doesn't grant more license to compiler devs than they already had, since the current compiler is the exact "guaranteed" semantics. What I'd love to see is a longer list of "these things are guaranteed NOT to be UB (i.e., they are always allowed/guaranteed by the language semantics)", because that is what ultimately restricts the sorts of optimizations that are possible/valid.

[adienes]

const replacement is definitely full on UB

IMO anything that is

• easily detectable
• "full on UB"

should error, rather than warn?

maybe also applies to the a value other than true or false for bool one

[jonas-schulze]

Should the associativity within reduce and mapreduce be added to the list of implementation-defined behavior? See discussion in #53871.

[mbauman]

reduce and mapreduce be added to the list of implementation-defined behavior

No, I think that's a different sort of thing; every single function needs to specify the behaviors its callers can expect and its methods need to satisfy. Or similarly grant leeway. This is more about the semantics of the language itself.

---

I think I can finally express why I so strongly dislike the language of "undefined behavior."

I've known forever that you shouldn't rely on Core.Compiler.return_type. That it's not stable across versions, that it's not always going to work as expected depending upon the compilation mode, etc. And yet I wouldn't have thought to call that UB. It's just something that you shouldn't do.

And that's at the core of why I don't like the terminology of Undefined Behavior — in particular in a language without a standard to define behaviors. Undefined Behavior turns around the "above don't do that" into a threat. UB is "you can do that, but I'll trash your program and it'll be your fault, because it was invalid."

It is jargon, because of how it typically differs from an unspecified behavior, or even a plain reading of "the behavior is undefined." The value from undef bitstype array is unspecified, and you can use it. But were accessing it an undefined behavior, then you couldn't touch it or your program is trashed and it's be your fault. This is beyond the plain interpretation of the two words — and twisting them into a backwards threat. Only people who know compilers can see the distinction between unspecified and undefined. It's fine to use UB in devdocs, but these guidelines need to be user visible. And at that point, I'd much rather simply call these things invalid.

So back to const redefinitions. Redefining const, even in that segfaulting example, is currently ok if I also redefine all the functions that use that binding, too. It makes no sense to say it's full-on UB and at the same time "minimize impact" to preserve some behaviors. There are some behaviors that are defined — the warning is even documented! So what does it mean to me that it appears on this list?

All this to say, this is a great list. We need to do more of this. Other candidates include return types and Tuple{Union{}} and maybe even Tuple{:wat}.

[Keno]

And yet I wouldn't have thought to call that UB.

It's not UB

The value from undef bitstype array is unspecified, and you can use it. But were accessing it an undefined behavior, then you couldn't touch it or your program is trashed and it's be your fault.

It now is, because it's no longer UB. That was a language specification change as a result of #26764.

So back to const redefinitions. Redefining const, even in that segfaulting example, is currently ok if I also redefine all the functions that use that binding, too.

No, it's not guaranteed - there could have been world age capture.

It makes no sense to say it's full-on UB and at the same time "minimize impact" to preserve some behaviors.

UB is about guarantees. After UB occurs the system can no longer make any guarantees about the future behavior the system, basically because a proof of false now exists in the system. We would like to make it work (#40399) and of course we could make it an error right now, but general experience is that users would prefer the system to keep running, even if it becomes crashy, rather than having to restart the system (because the likely outcome of a crash is that you're restarting anyway).

Also finally, I don't know why people keep interpreting what I'm saying as trying to add UB everywhere. If you look at both the issues where we've removed significant sources of UB (#26764, #40009) and the one I mentioned above that may remove more (#40399), both of them were filed by me, as was the work that actually made #40009 not a disaster performance-wise (the termination tracking in the effect system). I think any reasonable observer would conclude that I'm in favor of removing as much UB as possible without compromising the overall performance of the system ;).

[mbauman]

I don't know why people keep interpreting what I'm saying as trying to add UB everywhere

That's not at all what I'm doing here. This whole thing started because I didn't understand what UB meant for Julia and because I thought others wouldn't understand the term. I've seen and so much appreciate how you've been removing it. Turns out, I still don't understand it — to the point that I can't communicate cogently with you (let alone the compiler). I mean, I get LLVM's poison values and things that are assumed to not happen. I really get and love and appreciate the idea of writing down "third rails" that we can't touch. I want more documented third rails!

But I don't understand UB in higher-level Julia terms. I've used the words "the behavior is undefined" in docstrings before, probably inappropriately. Am I using my words correctly if I describe const redefinition in these terms: There's a clear meaning to what redefining a const should do: it throws a warning in some cases, an error in others, and Julia tries to behave as though that's the value of the binding going forward. But doing so is a source for undefined behavior. It breaks the runtime in a fundamental manner that is not recoverable. Is that accurate? See, that's very different to me than saying that Julia doesn't have any meaningful behaviors when you redefine const, which is what I (and I think others) think when we read that const redefinition is UB.

The feedback I hope you hear is that this is a very specific term of art that I don't understand.

[Keno]

Am I using my words correctly if I describe const redefinition in these terms

Kind of? I think part of the problem is the focusing on the behavior of julia the program, but a lot of this is really about Julia the language, for which julia the program is an implementation. Julia the language has semantics that are independent of julia the program, although julia the program is required to be a correct implementation of Julia the language.

There's additional confusion, because some choices of the semantics of Julia the language are made explicitly due to implementation constraints of julia the program.

So what do we do in those cases? In some cases we, we change the semantics of the language to something that is suboptimal but reasonable (integer overflow overflows silently, does not error). In other cases, we change the semantics to produce an error, but in a small set of cases, an error is not feasible or desirable so the semantics are "julia the program may assume this does not happen".

So the question then is, what happens if the third case does happen? Basically, the answer is 🤷. From the moment any undefined behavior is executed, julia the program ceases to guarantee that it correctly implements the semantics of Julia the language. This state is in principle non-recoverable as you say. Of course it's possible that nothing happens and everything keeps working, but there's no guarantee. It's not really about corruption in the runtime, although that is of course a possible mechanism here (although there are other).

Maybe think of Julia the language as a set of tracks where julia the program is a train that runs on top of them. Generally, it may switch between tracks, and go up and down, through tunnels, over bridges, what have you, but it always stays on the track. Except that in some places, some asshole went and removed a big piece of track and put up a sign "warning: undefined rails ahead". So what happens if the train goes there anyway? Again 🤷. It depends on way too many circumstances - the weight of the train, the wind conditions, wear of the wheels, etc. Best we can say is 🤷 - it might crash, it might accidentally end up back on the tracks and keep going, or maybe something even weirder happened like it ended up at running through the backyard of a nuclear power plant while you're thinking, "weird, I didn't think there were rails there".

[LilithHafner]

The view that "if there is UB then anything goes" is incompatible with the real world where UB is prevalent. For example, according to that semantic, 1+1 == 3 would be valid because, as a nontrivial codebase, of course Base has UB in it and therefore anything goes.

For folks who are skeptical that Base has UB, I decided to find an example in the latest stable release (1.10.2). This function is marked as :total, which includes :nothrow, which applies to all possible arguments, not just semantic executions:

https://github.com/JuliaLang/julia/blob/bd47eca2c8aacd145b6c5c02e47e2b9ec27ab456/base/reinterpretarray.jl#L729-L731

And on some arguments it does throw:

julia> Base.array_subpadding(1, 2)
ERROR: MethodError: no method matching Base.CyclePadding(::Int64)

Closest candidates are:
  Base.CyclePadding(::P, ::Int64) where P
   @ Base reinterpretarray.jl:681
  Base.CyclePadding(::DataType)
   @ Base reinterpretarray.jl:719

Stacktrace:
 [1] array_subpadding(S::Int64, T::Int64)
   @ Base ./reinterpretarray.jl:731
 [2] top-level scope
   @ REPL[23]:1

---

To continue the train example, if I'm sitting around in the back yard of a nuclear power plant and suddenly a train runs over my clover garden, that's bad. It's reasonable for me to say "hey, there aren't tracks over here, please keep your trains on the tracks". The presence of a bit of "undefined tracks" in the train manufacturing plant (Base) does not not give the train driver license to careen their train into my clover garden unannounced.

Now, I understand that it's hard for train drivers to keep trains well behaved when they drive over "undefined tracks". But in a world where undefined tracks are everywhere, it is a part of the train driver's professional responsibilities.

---

"Julia is fast" is not in the spec, and is not promised by any legalistic agreements, but we still do a pretty good job, provided users write reasonable code. I think we should treat "Julia doesn't have crazy UB behaviors" similarly. If users are not going out of their way to construct pathological UB exploits, they shouldn't see crazy UB behaviors. And I think we should document that aspiration.

---

This is not blocking and I'd be happy to add this note (with compiler folks' approval) in a separate PR after this one merges.

[vtjnash]

UB triggers only if the user executes it. The compiler is not allowed to speculatively insert UB. (Well, except possibly nothrow as we haven't decided yet if that annotation allows the compiler to invent UB if it does actually throw or if it does not permit hoisting call and only allows eliminating calls)

[mbauman]

Julia the language has semantics that are independent of julia the program, although julia the program is required to be a correct implementation of Julia the language.

Ahhh, thank you @Keno. OK, now I can much better understand what's written in this PR. I had this backwards — that julia the program itself is what defines Julia the language, and it does so through its observable behaviors, with caveats on what is allowed to be observable. And that's why I was finding UB to be backwards — and why I just wanted to define what's allowed to be observable or not allowed to be performed (like how I said I wanted to just document the "third rails"!).

This is a subtle shift in my own understanding of Julia, and I still don't quite fully appreciate why this distinction is valuable, but now I get what UB means in the context of Julia the language and how it affects julia the program. I think. Mostly.

[Seelengrab]

This is a subtle shift in my own understanding of Julia, and I still don't quite fully appreciate why this distinction is valuable, but now I get what UB means in the context of Julia the language. I think. Mostly.

It's a very subtle thing, yeah - in Python, quite a lot of behavior from cpython has been "adopted" into Python-the-language, which makes it very hard to do meaningful changes. There's this very good talk by Armin Ronacher (How Python was shaped by leaky internals) that gets into some details about a similar distinction there.

Hopefully the distinction between "Julia-The-Language" and "julia-the-program" becomes more clear/obvious with "juliac-the-static-compiler" :eyes:

[Keno]

And on some arguments it does throw:

That definitely needs to be fixed. @assume_effects is too hard to use correctly, but that's yet another track of effort (#49273 and related).

[vtjnash]

That definitely needs to be fixed

Should we split this into 2 cases? A case where any throw is UB (so hoisting is permitted without introducing UB), and a case where throwing is fine, but relying on that throw to exist is UB (so call elimination is fine without introducing UB, but hoisting is not fine)?

[mbauman]

One thing that's a little fuzzy to me is the various concepts and the wordings that are used for them:

• Julia-the-language can be any of:
  • Julia
  • the language
• julia-the-program:
  • julia
  • language implementation(s)
  • implementation(s)
  • compiler
  • julia's compiler
• .jl-files-I-write and things I type into a REPL:
  • "a julia program"
  • programs

Let me try to use what I've learned:

Julia-the-language has semantics that define (or don't define!) and constrain (or don't constrain) behaviors that julia-the-program must have when executing my Julia programs. The "don't define" there is UB, the "don't constrain" is implementation-defined.

But then the programs I write can define (or not define) and constrain (or not) what behaviors subtypes should have or what functions mean or what method implementations must do. This is not the Language's UB or implementation-defined, it's just a program.

One question I still have: are the "non-unique allowable behaviors" things from the beginning (@fastmath, rng, async, etc) "implementation-defined" things? Or are they a not-a-language-spec thing? Or something else entirely?

[oscardssmith]

One question I still have: are the "non-unique allowable behaviors" things from the beginning (@fastmath, rng, async, etc) "implementation-defined" things? Or are they a not-a-language-spec thing? Or something else entirely?

They are something else entirely (except for rng stream which is implementation defined). They define equivalence classes on what is allowable by the as-if rule. @fastmath in particular is a very fancy one which gives the compiler pretty wide latitude to change all your floating point results as long as the produced program has the right vibes.

[giordano]

Minor nitpick to try and reduce further confusion: based on #53873, people can be confused by what Julia is, and our own CONTRIBUTING.md suggests the language should be referred to as "Julia", while the monospace julia should be limited to the executable.

[nsajko]

The metaprogramming docs on generated functions say:

Note that the set of operations that should not be attempted in a generated function is unbounded, and the runtime system can currently only detect a subset of the invalid operations. There are many other operations that will simply corrupt the runtime system without notification, usually in subtle ways not obviously connected to the bad definition. Because the function generator is run during inference, it must respect all of the limitations of that code.

Sounds like UB, right? So maybe @generated should be mentioned here, too.

Also xref: #55332