rust-lang / chalk

An implementation and definition of the Rust trait system using a PROLOG-like logic solver
https://rust-lang.github.io/chalk/book/
Other
1.85k stars 182 forks source link

Generalize program clause for `AliasEq` goal with nested alias #792

Closed lowr closed 1 year ago

lowr commented 1 year ago

Consider a goal: AliasEq(<<?0 as X>::A as Y>::B = <<?1 as X>::A as Y>::B). This is expected to (eventually) flounder when the traits are non-enumerable and the variables are yet to be known, but it's currently disproven:

  1. the goal is canonicalized as follows:
    • forall<T, U> AliasEq(<<T as X>::A as Y>::B = <<U as X>::A as Y>::B)
  2. we produce the following ProgramClause that could match:
    • forall<T, U, ..> AliasEq(<<T as X>::A as Y>::B = <<U as X>::A as Y>::B) :- AliasEq(..), AliasEq(..)
  3. the consequence of the (instantiated) clause is unified with the goal, which produces a subgoal:
    • AliasEq(<<?0 as X>::A as Y>::B = <<?1 as X>::A as Y>::B)
    • this is because when we unify rhs of AliasEq, we see two AliasTys that we cannot unify structurally, forcing us to produce the subgoal
  4. boom, cycle emerged, goal disproven!

The problem is that because we're reusing the original goal as the consequence of the program clause we expect them to unify structurally, however we cannot unify aliases structurally in general (e.g. <?0 as X>::A = <?1 as X>::A does not imply ?0 = ?1).

This PR solves it by placing a fresh variable in rhs of the consequence AliasEq instead of reusing the original term. This ensures that rhs of the original AliasEq goal is preserved via unification without producing subgoals even if it's an alias.

See rust-lang/rust-analyzer#14369 for a real world case where this issue arises.

jackh726 commented 1 year ago

@bors r+

bors commented 1 year ago

:pushpin: Commit db746e092a30eec47eb31f939cbf221fed95e377 has been approved by jackh726

It is now in the queue for this repository.

bors commented 1 year ago

:lock: Merge conflict

This pull request and the master branch diverged in a way that cannot be automatically merged. Please rebase on top of the latest master branch, and let the reviewer approve again.

How do I rebase? Assuming `self` is your fork and `upstream` is this repository, you can resolve the conflict following these steps: 1. `git checkout fix/generalize-alias-alias-eq-clause` *(switch to your branch)* 2. `git fetch upstream master` *(retrieve the latest master)* 3. `git rebase upstream/master -p` *(rebase on top of it)* 4. Follow the on-screen instruction to resolve conflicts (check `git status` if you got lost). 5. `git push self fix/generalize-alias-alias-eq-clause --force-with-lease` *(update this PR)* You may also read [*Git Rebasing to Resolve Conflicts* by Drew Blessing](http://blessing.io/git/git-rebase/open-source/2015/08/23/git-rebasing-to-resolve-conflicts.html) for a short tutorial. Please avoid the ["**Resolve conflicts**" button](https://help.github.com/articles/resolving-a-merge-conflict-on-github/) on GitHub. It uses `git merge` instead of `git rebase` which makes the PR commit history more difficult to read. Sometimes step 4 will complete without asking for resolution. This is usually due to difference between how `Cargo.lock` conflict is handled during merge and rebase. This is normal, and you should still perform step 5 to update this PR.
Error message ```text Auto-merging tests/test/projection.rs CONFLICT (content): Merge conflict in tests/test/projection.rs Auto-merging chalk-solve/src/clauses.rs Automatic merge failed; fix conflicts and then commit the result. ```
bors commented 1 year ago

:umbrella: The latest upstream changes (presumably #780) made this pull request unmergeable. Please resolve the merge conflicts.

jackh726 commented 1 year ago

@bors r+

bors commented 1 year ago

:pushpin: Commit 91c24e391eab2c717398dccb97162206c90b450a has been approved by jackh726

It is now in the queue for this repository.

bors commented 1 year ago

:hourglass: Testing commit 91c24e391eab2c717398dccb97162206c90b450a with merge 88fd1c21e39fd17933d1965c2b986446c3e1822d...

bors commented 1 year ago

:sunny: Test successful - checks-actions Approved by: jackh726 Pushing 88fd1c21e39fd17933d1965c2b986446c3e1822d to master...