►
From YouTube: Polonius
Description
Niko Matsakis
A
If
you
attended
high
school
english
in
the
united
states,
you
probably
remember
polonius
from
hamlet,
he
gets
he
gets
killed,
at
least
in
the
play,
and
he's
most
well
remembered
for
a
piece
of
advice
that
he
gave
to
his
son,
which
was
neither
a
borrower
nor
lender
b
for
a
loan.
Oft
loses
both
itself
and
friend.
But
what
you
might
not
know
is
that
polonius
was
actually
a
c
programmer
and
he
was
very
careful
about
borrowing
and
lending
memory
because
he
had
debugged
so
many
horrible
problems,
but
he
actually
wasn't
killed.
A
They
made
it
a
little
more
dramatic,
he
was
just
wounded
and
he
recovered
in
the
hospital
and
spent
the
time
reading
this
really
cool
book
about
rust
and
he
got
really
enthusiastic
and
now,
when
he
talks
to
his
son,
he
actually
says
stuff
like
this.
You
know
go
for
it.
Do
whatever
you
want
to
do
it's
going
to
be
fine.
The
type
checkers
got
your
back.
So
that's
why
I
named
this
project
after
him
because
of
his
inspirational
transformation,
and
what
polonius
is
is
it's
a
work
in
progress?
A
That's
step
one,
but
it's
it's
a
kind
of
reimagination
of
the
way
that
the
borrow
checker
works
and
it
has
two
goals.
One
is
to
accept
more
programs
than
the
rest
bar
attacker
currently
does,
and
the
other
is
to
give
a
formal
and
simpler
definition
of
the
borrow
trigger
and
also
a
more
efficient
one.
I
should
say
than
the
current
definition.
So
we
we
have.
A
The
current
definition
is
not
formalized.
It
has
there's
an
rfc
that
kind
of
lays
out
how
it
should
work.
The
rfc
is
a
little
out
of
date,
but
it's
still
rather
challenging
to
like
write
it
all
out.
I
guess
that
depends
on
how
you
consider
whether
you
consider
ralph's
work
to
be
a
formalization
thereof,
and
there
have
been
some
other
attempts,
but
you
know
none
from
the
rest
team
at
least
and
polonius
actually
is
a
little
different.
So
what
I'm
going
to
do
in
this
talk,
though,
is
walk
you
through
first.
A
What
I
consider
to
be
the
classic
borrow
checker
error,
like
the
kind
of
the
simplest
pattern
that
the
brow
tracker
is
aiming
to
prevent
and
show
how
the
current
biochecker
reasons
about
it.
But
then
show
how
polonius
reasons
about
it,
which
they
both
report,
the
era,
but
they
they
sort
of
think
about
it
slightly
differently
and
then
I'll
talk
about
why
the
polonius
way
can
actually
help
us
do
more
things
in
the
future,
both
accepting
some
cases
and
also
potentially
other
language
changes.
A
A
We
have
a
shared
borrow
of
x,
resulting
in
a
reference
which
is
getting
used
again
down
here
and
then
during
the
live
period
of
that
reference,
where
it's
between
its
creation
and
some
future
use,
there's
a
modification
to
the
data
that
was
borrowed
right
and
that's
not
supposed
to
happen.
If
you
borrow
an
integer,
it's
supposed
to
be
immutable
during
the
span
of
that
shared
borrow
and,
of
course
you.
A
So
these
are
the
three
spots
right
and
we're
going
to
come
back
to
these.
The
point
where
the
borrow
occurred,
the
point
of
some
access
that
that
kind
of
violates
the
borrow
and
then
some
future
use
of
the
borrow
okay.
Let's
see,
then,
if
we
can
using
that
intuition,
can
we
kind
of
make
this
statement
of
when
is
there
an
error
that
should
get
reported?
Can
we
make
that
more
precise?
We
could
say
that
there
is
an
error
at
some
program
statement
n.
If
the
statement
n
accesses
some
place
p.
A
A
So
I
think
in
this
sometimes
it's
called
a
path,
so
the
local
variable
x
is
a
place
x.
Dot
f
is
a
place.
That's
some
just
just
the
memory
that
corresponds
to
the
field.
F,
star,
x,
dot
f
is
a
place
where
you
pass
through
a
pointer
found
in
the
field
x,
dot,
f
and
then
you
could
also
do
places
that
are
indexing
into
arrays
and
so
forth,
and
then
you
can
kind
of
compose
these
right.
A
So
if
we
go
back
to
our
error
now,
we've
got
the
statement
n,
which
is
this
one
modifies
the
place
x.
So
that's
the
step,
that's
the
first
thing
we
need.
We
have
the
the
axis
and
then
we
have
to
have
an
additional
condition
that
accessing
this
place
p
would
violate
the
terms
of
some
lone
l.
So
what
do
I
mean
by
alone?
A
A
That's
what
a
loan
is,
and
so
every
loan
has
a
place
that
was
borrowed
in
this
case
x
and
a
mode
which
is
either
shared
or
mutable,
and
the
mode
determines
what
it
means
to
violate
the
terms
of
the
loan,
because
if
you
make
a
shared
reference,
do
you
have
a
shared
loan?
Then
any
modification
to
the
memory
at
place
p
at
the
place
b,
will
be
considered
violating
the
terms,
whereas
with
immutable
loan
we
need
exclusive
access.
A
So
any
kind
of
access
whatsoever,
read
or
write
violates
the
terms
and
if
you've,
written
rust,
you're
probably
pretty
familiar
with
these
rules.
By
now-
and
I
said
directly
or
indirectly
what
I
meant
by
that
was
sometimes
the
place
that
we
borrow
is
not
exactly
the
place
that
is
accessed,
but
it's
either
one
or
the
other
is
a
subset
of
one
another
and
that's
still
a
violation.
A
A
That's
here,
access
is
the
place.
P
that's
x
and
accessing
the
place
p
would
violate
the
terms
of
some
loan
l.
So
this
this
loan,
I
should
say,
like
this-
is
kind
of
a
property.
We
can
it's
like
a
syntactic
property
of
the
program
that
we
can
scrape
just
from
looking
at
it
that
there
is
some
loan
l
which
I'll
just
call
it
l
and
that
it
shares
x.
A
It's
a
shared
bar
of
x
and
therefore
any
mutation
to
x
would
violate
l,
that's
all
true,
but
that's
still
not
enough
to
know
that
we
have
an
error.
There's
one
last
ingredient
we
need.
We
need
to
know
that
that
loan
is
live,
and
so
what
I
mean
by
live.
Well,
we
can.
This
is
a
common
compiler
term.
It
just
means
something
is
live
if
it
might
get
used
later
and
it's
dead
if
it
won't
get
used
later.
A
Usually
we
talk
about
variables
being
live
right,
so
we
could
say
here
we
have
x
the
value
that's
in
x.
At
this
we
first
assign
one,
and
then
we
assign
two
so
right
here
in
between
those
two
statements
x
is
not
actually
live
because
the
value
that's
in
it
is
not
going
to
get
used
again.
It's
just
going
to
get
overwritten
right.
It's
going
to
be
reassigned,
but
here,
just
after
x
equals
2.
A
Now
the
current
value
might
get
used
right.
It
might
get
overwritten
if
we
take
the
if,
but
it
might
skip
the
if
and
be
read
from
here.
So
it's
considered
live
it's
interestingly,
you
know
if
we
enter
into
the.
If,
but
we
haven't
yet
executed
x
equals
four,
then
x
is
no
longer
live
again
and
finally,
after
the
last
use
of
x,
it's
not
live.
So
that's
kind
of
the
sense
of
life
that
we
mean
for
loans.
A
So,
if
we
have
this
example,
we
we
create
a
loan.
Let's
call
this
loan
l1
and
we
make
a
reference
y
and
here
we're
actually
borrowing
something
from
y.
So
that's
actually
a
second
loan
at
least
the
way
polonius
looks
at
the
world
that
borrows
star
wide
dot
bar
you
know
the
star
is
implicit
raw,
syntax
and
there's
some
parentheses,
but
in
any
case
it
borrows
y
dot
bar,
and
the
thing
is
this:
reference
z
is
derived
from
y,
so
what
did
they
just
do?
A
A
So
how
do
we
decide
if
a
loan
is
live?
Well?
How
does
the
borrow
checker
do
it
today?
We
have
this
idea
of
a
lifetime
for
every
reference
and
a
lifetime
is
kind
of
conceptually.
The
part
of
the
program
where
the
reference
might
be
used,
so
we
can
make
that
more
concrete.
If
we
think
about
here's
our
example
and
we
give
line
numbers
to
every
line
here,
you
might
say
that
a
lifetime
is
like
a
set
of
line
numbers.
A
So
let
me
make.
Let
me
give
you
some
examples.
I'm
going
to
call
this
tick0
and
I'm
going
to
call
this
tick1,
there's
like
two
lifetimes
that
the
user
didn't
have
to
write,
but
the
compiler
has
in
mind
a
lifetime
for
the
resulting
value
of
ampersand
x.
This
this
creates
a
reference
which
has
a
lifetime
and
then
the
lifetime,
that's
annotated
as
the
type
of
y
we'll
call.
Those
are
basically
inference
variables
right
and
the
compiler's
job
is
going
to
be
to
figure
out
for
each
of
them.
What
value
do
they
have?
A
What
set
of
lines
could
we
write
in
there?
That
would
make
the
whole
program
type
check
and
there
are
some
basic
rules
that
we
use
to
do
that
inference
so
to
figure
out
we'll
start
with
figuring
out
what
is
the
value
of
tick
zero
because
that's
kind
of
the
easier
one?
That's
the
lifetime
of
this
variable
y,
this
reference
right
and
so
there's
one
rule
that
says
any
for
some
variable
y,
like
basically
the
lifetimes
that
appear
in
it
anywhere
that
y
is
live.
The
variable
y
might
get
used
well.
A
That
line
had
better
appear
in
the
lifetime
because
that's
a
spot
where
the
data
might
be
used
later.
So
in
this
case,
the
variable
y
is
live
on
these
two
lines,
so
we
could
say:
okay,
tick,
0
should
be
the
set
2
and
3..
Let's
say
you
can
kind
of
debate
whether
one
should
be
included
or
not.
I
said
no
in
this
slide.
A
There's
different.
This
is
this
is
a
hand,
wavy
definition
and
then
there's
a
separate
thing.
We
have
to
do
when
we're
doing
inference
which
is
kind
of
a
subtyping
consideration.
So
we
know
that
we're
going
to
take
this
value
and
assign
it
to
this
variable.
That
means
that
this
type
must
be
a
subtype
of
that
type.
A
So
the
subtyping
rule
is
basically
if
data
with
one
lifetime
flows
into
a
location
with
another
lifetime,
so
tick
one
flows
into
tick:
zero,
then
that
source
lifetime
has
to
outlive
to
the
destination.
So
you
can
sort
of
re-label
and
retype
something
as
having
a
smaller
and
smaller
lifetime.
That's
a
subset
of
the
original
because
it
was
included
in
the
original
borrow.
So
in
short,
we
know
that
tick
one
has
to
be
a
superset
of
tick
zero,
and
so
we
get
two
and
three
great.
A
So
that's
our
final
result.
If
we
think
of
lifetimes
like
this,
we
borrowed
x
for
the
during
the
lines
two
and
three
and
that's
what
the
the
y
variable
is,
and
so
you
could
imagine
if
you
didn't
have
inference
and
you
used
y
outside
of
lines
two
and
three.
That
would
be
a
type
error.
For
example,
we
don't
actually
let
you
write
annotations
like
that,
so
it
doesn't
ever
happen
in
rest.
So
how
do
we
decide?
Oh
right?
Okay,
so
let's
go
back
to
our
to
our
how
the
borrow
checker
works.
A
So
now
we
have
as
a
first
step,
we've
computed
these
lifetimes
for
every
reference.
These
sets
of
lines,
and
now
we
know
that
every
loan
creates
a
reference.
That's
the
ampersand
x
expression
and
we
know
the
lifetime
of
that
reference
right.
That's
what
we
had
here.
So
it's
live
on
lines,
two
and
three.
So
now
we
can
just
kind
of
apply
this
search
for
things
that
might
match
this
pattern.
We
look
for
statements
that
access
a
place
p.
Let's
see
what
I
have
here
so
here
we
found
that
line
two
modifies
x.
A
We
look
at
what
loans
are
in
scope.
We
look
at
what
loans
affect
x.
Let's
say
we
say:
oh
okay,
here's
a
loan
that
affects
x
and
then
we
can
check
what
is
the
lines
in
the
lifetime
and
is
the
line
that
x
that
the
statement
appears
on
is
two
in
that
set.
It
is
okay.
We
have
an
error,
that's
not
actually
how
the
code
works.
Obviously,
but
it's
the
same
basic
idea.
So
that's
how
the
borrow
checker
works
today,
but
polonius
looks
at
it
rather
differently.
A
C
A
D
A
Yeah,
sorry,
thank
you.
Something
like
this
is
your
example
and
you're,
saying
yeah,
and
if
I
did
this,
it
would
work
so
sometimes
it
turns
out.
You
can't
do
that
and
sometimes
you
can't,
but
you
particularly
can't
if
they're
both
mute
self
methods.
Yes,
it
does
tie
in.
The
reason
is
when
you
de-sugar
this,
what
you
essentially
get
like
at
the
the
bar
checker
actually
operates
at
the
mirror
level,
and
what
you
get
is
something
like:
let
temp
zero
equals
and
mute
self.
A
A
C
A
Not
going
to
go
into
the
details
here
afterwards,
we
can
talk
about
two-phase
borrows,
which
is
how
we
sometimes
allow
this
in
some
cases
in
particular.
If
this
is
not
ann
mute,
you
actually
can
do
it
because
of
two
phase
borrowers,
but
ralph
will
attest
to
all
the
horror
stories
that
I
put
onto
him,
trying
to
figure
out
how
to
make
that
make
sense,
we'll
leave
it
out
for
now
all
right.
So
how
does
polonius
approach
this
problem?
A
Polonius
looks
a
little
differently
instead
of
computing
lifetimes
sets
of
lines
it
computes
origins,
which
is
basically,
where
might
the
reference
have
come
from?
Not
where
will
it
be
used
in
the
future?
So
it's
looking
backwards
and
it's
kind
of
so
an
origin
for
the
purpose
of
plenus
is
really
a
set
of
loans.
A
So
we
have
the
same
concept
of
this
being
alone,
we'll
call
it
l1,
but
instead
of
making
sets
of
lines
for
tick,
zero
and
tick,
one
we're
going
to
make
sets
of
loans.
So
now
it's
kind
of
obvious,
but
what
for
ampersand
and
oh
and
the
inference
is
flowing
the
other
way,
instead
of
starting
with
tick,
zero,
we're
gonna
start
with
tick
one,
because
we're
gonna
say
what
is
sort
of
this
is
like
the
base
case
now.
What
loan
could
this
reference
have
come
from?
Well,
we
know.
A
A
If,
if
some,
if,
if
something
comes,
if
the
value
flows
from
tick
one
into
tuck
zero,
then
tick,
zero
has
to
be
a
super
set,
took
one
because
obviously
it
comes
from
at
least
as
many
loans
as
tick
one,
and
so
we
get
this
super
set
relationship
so
take
zero,
has
to
be
at
least
l1
and
right
now,
there's
no
other
assignments
to
y.
So
it's
exactly
equal.
If
you
had
multiple
assignments
or
like,
if
expressions
you
could
get
more
approximation
there,
so
now
we
can
have.
A
A
When
do
we
consider
a
loan
to
be
live?
Well,
the
answer
is:
if
there's
some
live
variable
like
program
variable
like
x
or
y,
and
it
has
the
loan
l
in
its
type,
then
l
is
live
so
now
we
can
apply
our
our
little
rule.
We
can
say:
okay,
just
like
before
the
statement
two
that
is
modifying
the
place
x
just
like
before.
We
know
that
that
would
violate
the
terms
of
loan.
L
one
nothing
has
changed
here.
The
only
change
is
now
we
talk
about.
Well,
do
we
know
whether
l1
is
live?
A
A
That's
how
pony
has
reasons
about
it,
so
it's
actually
more
of
a
forward
analysis
in
the
sense
of
it
doesn't
well
backward
depends
on
your
point
of
view,
it's
tracking
where
data
came
from
and
that
gets
propagated
in
a
forward
way,
as
opposed
to
looking
more
of
a
liveness
analysis.
So
how
does
that
help
us?
Why
does
this
actually
matter?
It's
almost
always
equivalent,
except
for
there
are
some
examples
where
polonius
is
more
expressive,
so
here's
here's
one.
A
A
Infeasible
like
it
just
the
compilation
times,
were
pretty
bad,
so
we
cut
it
out
and
what
what's
happening
here,
and
why
is
this
such
a
problem?
Well,
let's
look.
What
we've
got
is
we've
got
a
map
and
we
this
function.
Signature
says
we're
going
to
take
a
mutable
reference
to
a
hash
map
and
we're
going
to
return
a
reference
to
some
string
in
that
map
and
the
way
it
works
is.
A
It
first
looks
up
for
the
key
22
if
it
finds
it,
it
returns
it
and
if
not,
it
tries
to
insert
the
value
into
the
map
and
then
return
the
reference.
So
that
should
work
like
that.
That's
not
a
there's!
No
reason
this
can't
this
is
unsafe.
Fundamentally,
however,
if
you
actually
try
it
you're
going
to
get
this
compilation
here
saying
well,
there
was
a
borrow
here
and
you
returned
the
value
that
came
from
that
borrow,
and
then
you
tried
to
mutate
the
map.
A
While
we
know
now
that
the
way
that
the
compiler
thinks
about
it,
somehow
it
must
think
that
map
is
live,
that
the
reference
we
created
here
is
still
live
at
this
point,
because
that's
what
we
need.
That's
the
key
ingredient
for
making
an
error,
but
we
know
from
looking
at
the
code
that
when
you
return
the
reference
that
came
when
you
called
map.get,
if
you
had
gone
down
this
arm,
it
would
be
live
but
down
this
arm,
it
shouldn't
be,
and
we
know
that
everything's
flow
sensitive,
so
why?
Why
is
this
a
problem?
A
Well,
let
me
start
by
lightly
de-sugaring.
We
actually
just
did
this
in
the
playground.
So,
instead
of
calling
map.get
like
before,
I'm
going
to
show
you
how
the
compiler
thinks
about
this,
this
is
really
a
call
to
hashmap
get
and
the
first
argument
is
ampersand
star
map.
So
this
is
the
loan
that
the
compiler
is
looking
at
and
now
we
have
this
problem,
which
is
well
what
line
numbers
should
I
use
for
that
lifetime?
A
I
can't
use
any
set
of
line
numbers
inside
of
this
function,
because
this
loan
is
going
to
get
returned,
so
actually
the
line
numbers
that
I
have
to
use
sort
of
include
the
caller
and
there
could
be
many
callers
that
doesn't
really
make
sense.
So
the
way
we
talk
about
that
is,
we
have
these
named
lifetimes,
like
tick.
A
A
and
so
really
I
oversimplified,
I
said
that
a
lifetime
could
either
be
a
set
of
line
numbers
or
I
said
that
a
lifetime
was
instead
of
line
numbers,
but
really
the
way
that
the
compiler
thinks
about
it.
It
could
either
be
a
set
of
line
numbers
or
a
named
lifetime
parameter
like
or
an
anonymous
one,
but
so,
and
that's
because
really
what
you
think
about
it.
We
want
this
to
be
live
for
as
long
as
the
borrowed
to
map
is
live,
which
is
really
some
portion
of
the
caller
right.
A
A
That's
not
part
of
the
function,
we're
looking
at
that's
no
good,
but
though,
if
we
do
think
about
that
those
lines
sort
of
include
the
entire
execution
of
this
function,
so
we
could
say
we'll
call
it
tick
a
and
we
know
that
take
a
is
some
superset
it
like
includes
every
line,
and
now
maybe
you
start
to
see
why
the
compiler
gets
confused,
because
we
said
they
can
either
be
the
set
of
lines
or
a
named
lifetime.
That
includes
all
lines
and
right
here
we
make
a
loan.
A
We
have
to
make
that
loan
for
the
lifetime
tick
a
because
it
gets
returned,
which
means
that
we've
got
a
loan
that
starts
here
and
extends
for
all
the
lifetime.
All
the
lines
in
this
function
from
the
point
of
view
of
the
compiler,
because
it's
too
simple
it
just
doesn't
understand
that
it
needs
to
that.
It
needs
to
live
for
tick
a,
but
only
down
some
pads
of
the
code.
A
A
And
that's
you
just
don't
get
an
error,
and
so
it's
exactly
the
fact
that
we
don't
need
polonius
doesn't
in
order
to
assign
a
type
to
map.
It
doesn't
have
to
look
forward
and
know
all
the
places
it's
going
to
get
used
in
the
future,
which
is
hard
to
describe.
It
only
needs
to
know
where
it
came
from,
which
is
relatively
easy.
A
So
that's
kind
of
nice,
so
if
we
can
switch
to
plenus
we'll
this
is
a
fairly
common
pattern
to
get
it
like,
not
nowhere
near
as
common
as
the
other
nll
bugs,
but
still
comes
up
pretty
regularly
that
people
ask.
Why
doesn't
my
code
compile?
This
seems
like
it
should
work.
So
if
we
switch
to
polonius,
we
would
get
that
right
off
the
bat,
but
there's
a
few
other
things.
It
would
do.
D
A
A
That
would
be
really
cool,
because
then
we
could
package
up
the
struct
and
its
references
and
like
send
it
to
other
threads
and
do
neat
stuff
with
it,
but
all
the
concepts
of
lifetimes,
and
so
on
that
we've
talked
about.
Don't
really
apply
here,
because
it's
not
you
can't
describe
the
lifetime
of
this
as
some
set
of
lines,
it's
more
tied
to
the
the
container
it's
in.
A
We
need.
There
are
lots
of
cool
academic
approaches
that
apply
completely
and
we
should
totally
steal
them,
but
haven't
done
it
yet,
however,
to
even
go
back
a
little
further,
if
you
imagine
just
what
is
it
going
to
take
to
create
a
message
like
this?
We're
gonna
need
to
put
together
two
the
values
for
its
fields.
A
We're
gonna
need
a
vector
and
we're
gonna
need
some
slice
that
we
know
came
from
that
vector
so
that
when
we
move
it,
we
know
that
they
move
together,
and
if
you
ask
yourself,
how
do
you
know
where
something?
How
would
I
know
if
that
slice
came
from
the
vector
you
can
kind
of
see
lifetimes
are
just
the
wrong
tool
for
this.
This
has
nothing
to
do
with
how
long
the
slice
is
going
to
get
used
for
there's
everything
to
do
with
where
it
came
from
so
origins.
A
So
that's
the
end
of
the
talk
and
the
current
status
this
slide
and
it's
sort
of
amusing,
because
this
slide
I
made
like
a
year
ago,
and
it's
still
completely
accurate
just
because
things
move
slowly
sometimes,
but
we're
exploring
polonius
in
this
working
group.
We'd
love
to
have
people
join
us.
The
working
group
is
kind
of
goes
and
fits
and
starts
depending
on
how
much
time
everybody
has.
Sometimes
we
do
sprints
for
a
week
or
two
where
we
go
hack
and
and
fix
a
bunch
of
stuff.
A
A
B
E
E
A
C
B
A
I
I
don't,
but
I'd
be
interested
to
see
it
is
the
answer
and
yeah.
It
was
inspired
by
me
sitting
on
an
airplane
thinking,
wait
a
minute.
Why
am
I?
Why
are
we
not
using
points
to
analyses,
they're
really
well
known,
and
they
do
a
lot
of
great
stuff?
What
would
it
be
like
if
we
just
used
that?
But
so
it
definitely
is
connected
to
points
too,
but
I'm
not
sure
I'm
not
aware
of
anyone
who's
written
a
good
comparison,
though,
like
I
said
I
would
love
to
hear
about
it.