Quais são as regras exatas de desreferenciação automática da Rust?

Estou aprendendo / experimentando o Rust e, com toda a elegância que encontro neste idioma, há uma peculiaridade que me confunde e parece totalmente fora de lugar.

O Rust desreferencia automaticamente os ponteiros ao fazer chamadas de método. Fiz alguns testes para determinar o comportamento exato:

struct X { val: i32 }
impl std::ops::Deref for X {
    type Target = i32;
    fn deref(&self) -> &i32 { &self.val }
}

trait M { fn m(self); }
impl M for i32   { fn m(self) { println!("i32::m()");  } }
impl M for X     { fn m(self) { println!("X::m()");    } }
impl M for &X    { fn m(self) { println!("&X::m()");   } }
impl M for &&X   { fn m(self) { println!("&&X::m()");  } }
impl M for &&&X  { fn m(self) { println!("&&&X::m()"); } }

trait RefM { fn refm(&self); }
impl RefM for i32  { fn refm(&self) { println!("i32::refm()");  } }
impl RefM for X    { fn refm(&self) { println!("X::refm()");    } }
impl RefM for &X   { fn refm(&self) { println!("&X::refm()");   } }
impl RefM for &&X  { fn refm(&self) { println!("&&X::refm()");  } }
impl RefM for &&&X { fn refm(&self) { println!("&&&X::refm()"); } }


struct Y { val: i32 }
impl std::ops::Deref for Y {
    type Target = i32;
    fn deref(&self) -> &i32 { &self.val }
}

struct Z { val: Y }
impl std::ops::Deref for Z {
    type Target = Y;
    fn deref(&self) -> &Y { &self.val }
}


#[derive(Clone, Copy)]
struct A;

impl M for    A { fn m(self) { println!("A::m()");    } }
impl M for &&&A { fn m(self) { println!("&&&A::m()"); } }

impl RefM for    A { fn refm(&self) { println!("A::refm()");    } }
impl RefM for &&&A { fn refm(&self) { println!("&&&A::refm()"); } }


fn main() {
    // I'll use @ to denote left side of the dot operator
    (*X{val:42}).m();        // i32::m()    , Self == @
    X{val:42}.m();           // X::m()      , Self == @
    (&X{val:42}).m();        // &X::m()     , Self == @
    (&&X{val:42}).m();       // &&X::m()    , Self == @
    (&&&X{val:42}).m();      // &&&X:m()    , Self == @
    (&&&&X{val:42}).m();     // &&&X::m()   , Self == *@
    (&&&&&X{val:42}).m();    // &&&X::m()   , Self == **@
    println!("-------------------------");

    (*X{val:42}).refm();     // i32::refm() , Self == @
    X{val:42}.refm();        // X::refm()   , Self == @
    (&X{val:42}).refm();     // X::refm()   , Self == *@
    (&&X{val:42}).refm();    // &X::refm()  , Self == *@
    (&&&X{val:42}).refm();   // &&X::refm() , Self == *@
    (&&&&X{val:42}).refm();  // &&&X::refm(), Self == *@
    (&&&&&X{val:42}).refm(); // &&&X::refm(), Self == **@
    println!("-------------------------");

    Y{val:42}.refm();        // i32::refm() , Self == *@
    Z{val:Y{val:42}}.refm(); // i32::refm() , Self == **@
    println!("-------------------------");

    A.m();                   // A::m()      , Self == @
    // without the Copy trait, (&A).m() would be a compilation error:
    // cannot move out of borrowed content
    (&A).m();                // A::m()      , Self == *@
    (&&A).m();               // &&&A::m()   , Self == &@
    (&&&A).m();              // &&&A::m()   , Self == @
    A.refm();                // A::refm()   , Self == @
    (&A).refm();             // A::refm()   , Self == *@
    (&&A).refm();            // A::refm()   , Self == **@
    (&&&A).refm();           // &&&A::refm(), Self == @
}

( Parque infantil )

Então, parece que, mais ou menos:

• O compilador inserirá o número de operadores de desreferência necessários para chamar um método.
• O compilador, ao resolver métodos declarados usando &self(chamada por referência):
  • Primeiramente tenta solicitar uma única desreferência de self
  • Em seguida, tenta chamar o tipo exato de self
  • Em seguida, tenta inserir quantos operadores de desreferência forem necessários para uma correspondência
• Os métodos declarados usando self(chamada por valor) para o tipo Tse comportam como se fossem declarados usando &self(chamada por referência) para o tipo &Te chamavam a referência para o que estiver no lado esquerdo do operador de ponto.
• As regras acima são tentadas primeiro com a desreferenciação interna bruta e, se não houver correspondência, a sobrecarga com a Derefcaracterística é usada.

Quais são as regras exatas de desreferenciação automática? Alguém pode dar uma justificativa formal para essa decisão de design?

Seu pseudo-código está praticamente correto. Para este exemplo, suponha que tivemos uma chamada de método foo.bar()where foo: T. Vou usar a sintaxe totalmente qualificada (FQS) para não ter ambiguidade sobre com que tipo o método está sendo chamado, por exemplo, A::bar(foo)ou A::bar(&***foo). Vou apenas escrever uma pilha de letras maiúsculas aleatórias, cada uma com apenas um tipo / característica arbitrária, exceto que Tsempre é o tipo da variável original na fooqual o método é chamado.

O núcleo do algoritmo é:

• Para cada "etapa de desreferência" U (ou seja, defina U = Te depois U = *T...)
  1. se houver um método em barque o tipo de receptor (o tipo de selfno método) corresponda Uexatamente, use-o ( um "método por valor" )
  2. caso contrário, adicione uma auto-ref (take &ou &mutdo receptor) e, se o receptor de algum método corresponder &U, use-o ( um "método autorefd" )

Notavelmente, tudo considera o "tipo de receptor" do método, não o Selftipo da característica, ou seja, impl ... for Foo { fn method(&self) {} }pensa &Fooem combinar o método e fn method2(&mut self)pensaria &mut Fooem combinar.

É um erro se houver vários métodos de característica válidos nas etapas internas (ou seja, só pode haver zero ou um método de característica válido em cada um de 1. ou 2., mas pode haver um válido para cada um: o único de 1 serão tomados primeiro), e os métodos inerentes têm precedência sobre os de característica. Também é um erro se chegarmos ao final do loop sem encontrar nada que corresponda. Também é um erro ter Derefimplementações recursivas , que tornam o loop infinito (elas atingem o "limite de recursão").

Essas regras parecem fazer o que eu quero dizer na maioria das circunstâncias, embora ter a capacidade de escrever o formulário FQS inequívoco seja muito útil em alguns casos extremos e para mensagens de erro sensíveis para código gerado por macro.

Apenas uma referência automática é adicionada porque

• se não havia um limite, as coisas ficam ruins / lentas, pois todo tipo pode ter um número arbitrário de referências
• tomar uma referência &foomantém uma forte conexão com foo(é o endereço de foosi mesmo), mas tomar mais começa a perdê-la: &&fooé o endereço de alguma variável temporária na pilha que armazena &foo.

Exemplos

Suponha que tenhamos uma chamada foo.refm(), se footiver o tipo:

• X, então começamos com U = X, refmtem o tipo de receptor &..., portanto, a etapa 1 não corresponde, a realização de uma auto-ref nos fornece &X, e isso corresponde (com Self = X), para que a chamada sejaRefM::refm(&foo)
• &X, começa com U = &X, que corresponde &selfna primeira etapa (com Self = X) e, portanto, a chamada éRefM::refm(foo)
• &&&&&X, isso não corresponde a nenhuma das etapas (a característica não está implementada para &&&&Xou &&&&&X), portanto, desreferenciamos uma vez para obter U = &&&&X, que corresponde a 1 (com Self = &&&X) e a chamada éRefM::refm(*foo)
• Z, não corresponde a nenhuma das etapas, por isso é desreferenciada uma vez, para obter Y, o que também não corresponde, por isso é desreferenciada novamente, para obter X, que não corresponde a 1, mas corresponde após a reorientação automática, então a chamada é RefM::refm(&**foo).
• &&A, o 1. não corresponde e nem o 2., pois a característica não é implementada para &A(para 1) ou &&A(para 2), portanto, é desreferenciada para &A, que corresponde a 1., comSelf = A

Suponha que tenhamos foo.m(), e que Anão seja Copy, se footiver o tipo:

• A, em seguida, U = Acorresponde selfdiretamente para que a chamada seja M::m(foo)comSelf = A
• &A, então 1. não corresponde e nem 2. ( &Anem &&Aimplementa a característica), portanto, é desreferenciado para A, o que corresponde, mas M::m(*foo)requer a tomada Ade valor e, portanto, a saída foo, daí o erro.
• &&A, 1. não corresponde, mas o autorefing fornece &&&A, o que corresponde, então a chamada é M::m(&foo)com Self = &&&A.

(Esta resposta é baseada no código e está razoavelmente próxima do README (um pouco desatualizado) . Niko Matsakis, o principal autor desta parte do compilador / idioma, também deu uma olhada nessa resposta.)

A referência Rust possui um capítulo sobre a expressão de chamada do método . Copiei a parte mais importante abaixo. Lembrete: estamos falando de uma expressão recv.m(), onde recvé chamada "expressão receptora" abaixo.

O primeiro passo é criar uma lista de tipos de receptores candidatos. Obtenha-os desreferenciando repetidamente o tipo de expressão do receptor, adicionando cada tipo encontrado à lista e, finalmente, tentando uma coerção não dimensionada no final e adicionando o tipo de resultado, se for bem-sucedido. Em seguida, para cada candidato T, adicione &Te &mut Tà lista imediatamente após T.

Por exemplo, se o receptor tem o tipo Box<[i32;2]>, em seguida, os tipos de candidatos será Box<[i32;2]>, &Box<[i32;2]>, &mut Box<[i32;2]>, [i32; 2](por dereferencing), &[i32; 2], &mut [i32; 2], [i32](por coerção unsized), &[i32]e, finalmente, &mut [i32].

Em seguida, para cada tipo de candidato T, procure um método visível com um receptor desse tipo nos seguintes locais:

1. Tmétodos inerentes (métodos implementados diretamente em T[¹]).
2. Qualquer um dos métodos fornecidos por uma característica visível implementada por T. [...]

( Nota sobre [¹] : Na verdade, acho que essa frase está errada. Abri um problema . Vamos ignorar essa frase entre parênteses.)

Vamos ver alguns exemplos do seu código em detalhes! Para seus exemplos, podemos ignorar a parte sobre "coerção não dimensionada" e "métodos inerentes".

(*X{val:42}).m(): o tipo da expressão do receptor é i32. Nós executamos estas etapas:

• Criando lista de tipos de receptores candidatos:
  • i32 não pode ser desreferenciada, portanto já terminamos a etapa 1. Lista: [i32]
  • Em seguida, adicionamos &i32e &mut i32. Lista:[i32, &i32, &mut i32]
• Procurando métodos para cada tipo de receptor candidato:
  • Nós descobrimos <i32 as M>::mqual tem o tipo de receptor i32. Então, nós já terminamos.

Até aqui tudo é fácil. Agora vamos pegar um exemplo mais difícil (&&A).m(). O tipo da expressão do receptor é &&A. Nós executamos estas etapas:

• Criando lista de tipos de receptores candidatos:
  • &&Apode ser desreferenciado para &A, então adicionamos isso à lista. &Apode ser desreferenciada novamente, então também adicionamos Aà lista. Anão pode ser desreferenciada, então paramos. Lista:[&&A, &A, A]
  • Em seguida, para cada tipo Tna lista, adicionamos &Te &mut Timediatamente depois T. Lista:[&&A, &&&A, &mut &&A, &A, &&A, &mut &A, A, &A, &mut A]
• Procurando métodos para cada tipo de receptor candidato:
  • Não há método com o tipo de receptor &&A, então vamos para o próximo tipo na lista.
  • Encontramos o método <&&&A as M>::mque realmente tem o tipo de receptor &&&A. Então terminamos.

Aqui estão as listas de destinatários candidatos para todos os seus exemplos. O tipo que está incluído ⟪x⟫é o que "ganhou", ou seja, o primeiro tipo para o qual um método de ajuste pode ser encontrado. Lembre-se também de que o primeiro tipo da lista é sempre o tipo de expressão do receptor. Por fim, formatei a lista em linhas de três, mas isso é apenas formatação: esta lista é uma lista simples.

• (*X{val:42}).m() → <i32 as M>::m

  [⟪i32⟫, &i32, &mut i32]

• X{val:42}.m() → <X as M>::m

  [⟪X⟫, &X, &mut X, 
   i32, &i32, &mut i32]

• (&X{val:42}).m() → <&X as M>::m

  [⟪&X⟫, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&X{val:42}).m() → <&&X as M>::m

  [⟪&&X⟫, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&&X{val:42}).m() → <&&&X as M>::m

  [⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&&&X{val:42}).m() → <&&&X as M>::m

  [&&&&X, &&&&&X, &mut &&&&X, 
   ⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&&&&X{val:42}).m() → <&&&X as M>::m

  [&&&&&X, &&&&&&X, &mut &&&&&X, 
   &&&&X, &&&&&X, &mut &&&&X, 
   ⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (*X{val:42}).refm() → <i32 as RefM>::refm

  [i32, ⟪&i32⟫, &mut i32]

• X{val:42}.refm() → <X as RefM>::refm

  [X, ⟪&X⟫, &mut X, 
   i32, &i32, &mut i32]

• (&X{val:42}).refm() → <X as RefM>::refm

  [⟪&X⟫, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&X{val:42}).refm() → <&X as RefM>::refm

  [⟪&&X⟫, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&&X{val:42}).refm() → <&&X as RefM>::refm

  [⟪&&&X⟫, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&&&X{val:42}).refm() → <&&&X as RefM>::refm

  [⟪&&&&X⟫, &&&&&X, &mut &&&&X, 
   &&&X, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• (&&&&&X{val:42}).refm() → <&&&X as RefM>::refm

  [&&&&&X, &&&&&&X, &mut &&&&&X, 
   ⟪&&&&X⟫, &&&&&X, &mut &&&&X, 
   &&&X, &&&&X, &mut &&&X, 
   &&X, &&&X, &mut &&X, 
   &X, &&X, &mut &X, 
   X, &X, &mut X, 
   i32, &i32, &mut i32]

• Y{val:42}.refm() → <i32 as RefM>::refm

  [Y, &Y, &mut Y,
   i32, ⟪&i32⟫, &mut i32]

• Z{val:Y{val:42}}.refm() → <i32 as RefM>::refm

  [Z, &Z, &mut Z,
   Y, &Y, &mut Y,
   i32, ⟪&i32⟫, &mut i32]

• A.m() → <A as M>::m

  [⟪A⟫, &A, &mut A]

• (&A).m() → <A as M>::m

  [&A, &&A, &mut &A,
   ⟪A⟫, &A, &mut A]

• (&&A).m() → <&&&A as M>::m

  [&&A, ⟪&&&A⟫, &mut &&A,
   &A, &&A, &mut &A,
   A, &A, &mut A]

• (&&&A).m() → <&&&A as M>::m

  [⟪&&&A⟫, &&&&A, &mut &&&A,
   &&A, &&&A, &mut &&A,
   &A, &&A, &mut &A,
   A, &A, &mut A]

• A.refm() → <A as RefM>::refm

  [A, ⟪&A⟫, &mut A]

• (&A).refm() → <A as RefM>::refm

  [⟪&A⟫, &&A, &mut &A,
   A, &A, &mut A]

• (&&A).refm() → <A as RefM>::refm

  [&&A, &&&A, &mut &&A,
   ⟪&A⟫, &&A, &mut &A,
   A, &A, &mut A]

• (&&&A).refm() → <&&&A as RefM>::refm

  [&&&A, ⟪&&&&A⟫, &mut &&&A,
   &&A, &&&A, &mut &&A,
   &A, &&A, &mut &A,
   A, &A, &mut A]