ChangingAndChangedNotifications performs incorrect updates on Many-To-Many Relationships

[AlmightyLks]

File a bug

Include your code

Full reproduction code: https://github.com/AlmightyLks/WeirdBehaviour

Expected Behaviour: No-Op
Actual Behaviour: Alternating Delete / Insert Ops

TLDR:
Clearing and re-adding a navigation property's ICollection elements will alternatingly delete and insert them, every other run.

using var ctx = new ExampleContext();
var artists = ctx.Artists.First();
var songs = ctx.Songs.ToList();

artists.Songs.Clear();

foreach (var song in songs)
    artists.Songs.Add(song);

ctx.SaveChanges();

The logging output of running this code twice in a row is more or less this:

 First Time:

dbug: 05.09.2023 10:33:14.912 RelationalEventId.CommandExecuting[20100] (Microsoft.EntityFrameworkCore.Database.Command)
      Executing DbCommand [Parameters=[@p0='3', @p1='7', @p2='3', @p3='8', @p4='3', @p5='9'], CommandType='Text', CommandTimeout='30']
      SET NOCOUNT ON;
      DELETE FROM [ArtistSong]
      OUTPUT 1
      WHERE [ArtistId] = @p0 AND [SongId] = @p1;
      DELETE FROM [ArtistSong]
      OUTPUT 1
      WHERE [ArtistId] = @p2 AND [SongId] = @p3;
      DELETE FROM [ArtistSong]
      OUTPUT 1
      WHERE [ArtistId] = @p4 AND [SongId] = @p5;


 Second Time:

dbug: 05.09.2023 10:33:14.932 RelationalEventId.CommandExecuting[20100] (Microsoft.EntityFrameworkCore.Database.Command)
      Executing DbCommand [Parameters=[@p0='3', @p1='7', @p2='3', @p3='8', @p4='3', @p5='9'], CommandType='Text', CommandTimeout='30']
      SET IMPLICIT_TRANSACTIONS OFF;
      SET NOCOUNT ON;
      INSERT INTO [ArtistSong] ([ArtistId], [SongId])
      VALUES (@p0, @p1),
      (@p2, @p3),
      (@p4, @p5);
	  

This also happens using Microsoft.EntityFrameworkCore.Proxies's UseChangeTrackingProxies()

Include provider and version information

EF Core version: 7.0.10
Database provider: Microsoft.EntityFrameworkCore.SqlServer
Target framework: .NET 7.0
Operating system: Windows 10
IDE: Visual Studio 2022 17.7.0 Preview 5.0

Note: The issue still occurs with .NET 8 and EFC8 preview versions

[AlmightyLks]

If anything is still unclear about this, let me know

[ajcvickers]

Note for triage: we should consider doing something to Deleted join entities when the relationship is re-established in the same context instance. In this case, we start off with no relationships loaded:

Artist {Id: 1} Unchanged
  Id: 1 PK
  Songs: []
Song {Id: 1} Unchanged
  Id: 1 PK
  Artists: []
Song {Id: 2} Unchanged
  Id: 2 PK
  Artists: []
Song {Id: 3} Unchanged
  Id: 3 PK
  Artists: []

The code then lazy loads the relationships and immediately severs them with a call to Clear:

Artist {Id: 1} Unchanged
  Id: 1 PK
  Songs: []
ArtistSong {ArtistId: 1, SongId: 1} Deleted
  ArtistId: 1 PK FK
  SongId: 1 PK FK
  Artist: {Id: 1}
  Song: {Id: 1}
ArtistSong {ArtistId: 1, SongId: 2} Deleted
  ArtistId: 1 PK FK
  SongId: 2 PK FK
  Artist: {Id: 1}
  Song: {Id: 2}
ArtistSong {ArtistId: 1, SongId: 3} Deleted
  ArtistId: 1 PK FK
  SongId: 3 PK FK
  Artist: {Id: 1}
  Song: {Id: 3}
Song {Id: 1} Unchanged
  Id: 1 PK
  Artists: []
Song {Id: 2} Unchanged
  Id: 2 PK
  Artists: []
Song {Id: 3} Unchanged
  Id: 3 PK
  Artists: []

Adding the same instances back to the collection does not change this:

Artist {Id: 1} Unchanged
  Id: 1 PK
  Songs: [{Id: 1}, {Id: 2}, {Id: 3}]
ArtistSong {ArtistId: 1, SongId: 1} Deleted
  ArtistId: 1 PK FK
  SongId: 1 PK FK
  Artist: {Id: 1}
  Song: {Id: 1}
ArtistSong {ArtistId: 1, SongId: 2} Deleted
  ArtistId: 1 PK FK
  SongId: 2 PK FK
  Artist: {Id: 1}
  Song: {Id: 2}
ArtistSong {ArtistId: 1, SongId: 3} Deleted
  ArtistId: 1 PK FK
  SongId: 3 PK FK
  Artist: {Id: 1}
  Song: {Id: 3}
Song {Id: 1} Unchanged
  Id: 1 PK
  Artists: [{Id: 1}]
Song {Id: 2} Unchanged
  Id: 2 PK
  Artists: [{Id: 1}]
Song {Id: 3} Unchanged
  Id: 3 PK
  Artists: [{Id: 1}]

It should potentially mark the join entities as Unchanged.

[AndriySvyryd]

Related to #27677