Fix T89435: Reordering FCurves can cause crash or corruption

Correctly reset `prev` and `next` pointers of action group FCurves when
separating them into distinct `ListBase`s per `bActionGroup`.

These `NULL` pointers are necessary to temporarily demarcate the start &
end of the `bActionGroup::channels` list. Having them still point to
other FCurves caused ordering issues when moving curves towards the
start/end of a group.

This commit corrects the above issue and adds versioning code to rectify
any ordering issues that may have been caused. For this purpose the
`BKE_action_groups_reconstruct()` function is rewritten to avoid relying
on the `bAction::curves` list order or `prev` link integrity.

Differential Revision: https://developer.blender.org/D11811

6 files changed, 192 insertions, 40 deletions

diff --git a/source/blender/blenkernel/BKE_blender_version.h b/source/blender/blenkernel/BKE_blender_version.h
index 9d286b94b04..30f6ad7475d 100644
--- a/source/blender/blenkernel/BKE_blender_version.h
+++ b/source/blender/blenkernel/BKE_blender_version.h
@@ -39,7 +39,7 @@ extern "C" {
 
 /* Blender file format version. */
 #define BLENDER_FILE_VERSION BLENDER_VERSION
-#define BLENDER_FILE_SUBVERSION 8
+#define BLENDER_FILE_SUBVERSION 9
 
 /* Minimum Blender version that supports reading file written with the current
  * version. Older Blender versions will test this and show a warning if the file
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index a0aee552759..2c25b940578 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -765,6 +765,7 @@ add_dependencies(bf_blenkernel bf_dna)
 
 if(WITH_GTESTS)
   set(TEST_SRC
+    intern/action_test.cc
     intern/armature_test.cc
     intern/cryptomatte_test.cc
     intern/fcurve_test.cc
diff --git a/source/blender/blenkernel/intern/action.c b/source/blender/blenkernel/intern/action.c
index 13ca5ecf23c..d55f023d209 100644
--- a/source/blender/blenkernel/intern/action.c
+++ b/source/blender/blenkernel/intern/action.c
@@ -497,9 +497,8 @@ void action_groups_add_channel(bAction *act, bActionGroup *agrp, FCurve *fcurve)
 }
 
 /* Reconstruct group channel pointers.
- * Assumes that the channels are still in the proper order, i.e. that channels of the same group
- * are adjacent in the act->channels list. It also assumes that the groups
- * referred to by the FCurves are already in act->groups.
+ * Assumes that the groups referred to by the FCurves are already in act->groups.
+ * Reorders the main channel list to match group order.
  */
 void BKE_action_groups_reconstruct(bAction *act)
 {
@@ -514,23 +513,30 @@ void BKE_action_groups_reconstruct(bAction *act)
     BLI_listbase_clear(&group->channels);
   }
 
-  bActionGroup *grp;
-  bActionGroup *last_grp = NULL;
-  LISTBASE_FOREACH (FCurve *, fcurve, &act->curves) {
-    if (fcurve->grp == NULL) {
-      continue;
-    }
+  /* Sort the channels into the group lists, destroying the act->curves list. */
+  ListBase ungrouped = {NULL, NULL};
 
-    grp = fcurve->grp;
-    if (last_grp != grp) {
-      /* If this is the first time we see this group, this must be the first channel. */
-      grp->channels.first = fcurve;
+  LISTBASE_FOREACH_MUTABLE (FCurve *, fcurve, &act->curves) {
+    if (fcurve->grp) {
+      BLI_assert(BLI_findindex(&act->groups, fcurve->grp) >= 0);
+
+      BLI_addtail(&fcurve->grp->channels, fcurve);
+    }
+    else {
+      BLI_addtail(&ungrouped, fcurve);
     }
+  }
+
+  /* Recombine into the main list. */
+  BLI_listbase_clear(&act->curves);
 
-    /* This is the last channel, until it's overwritten by a later iteration. */
-    grp->channels.last = fcurve;
-    last_grp = grp;
+  LISTBASE_FOREACH (bActionGroup *, group, &act->groups) {
+    /* Copy the list header to preserve the pointers in the group. */
+    ListBase tmp = group->channels;
+    BLI_movelisttolist(&act->curves, &tmp);
   }
+
+  BLI_movelisttolist(&act->curves, &ungrouped);
 }
 
 /* Remove the given channel from all groups */
diff --git a/source/blender/blenkernel/intern/action_test.cc b/source/blender/blenkernel/intern/action_test.cc
new file mode 100644
index 00000000000..cd8751ec358
--- /dev/null
+++ b/source/blender/blenkernel/intern/action_test.cc
@@ -0,0 +1,144 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2021 Blender Foundation
+ * All rights reserved.
+ */
+
+#include "BKE_action.h"
+
+#include "DNA_action_types.h"
+#include "DNA_anim_types.h"
+
+#include "BLI_listbase.h"
+
+#include "testing/testing.h"
+
+namespace blender::bke::tests {
+
+TEST(action_groups, ReconstructGroupsWithReordering)
+{
+  // Construct an Action with three groups.
+  bAction action = {0};
+  FCurve groupAcurve1 = {0};
+  FCurve groupAcurve2 = {0};
+  FCurve groupBcurve1 = {0};
+  FCurve groupBcurve2 = {0};
+  FCurve groupBcurve3 = {0};
+  // Group C has no curves intentionally.
+  FCurve groupDcurve1 = {0};
+  FCurve groupDcurve2 = {0};
+
+  groupAcurve1.rna_path = (char *)"groupAcurve1";
+  groupAcurve2.rna_path = (char *)"groupAcurve2";
+  groupBcurve1.rna_path = (char *)"groupBcurve1";
+  groupBcurve2.rna_path = (char *)"groupBcurve2";
+  groupDcurve1.rna_path = (char *)"groupDcurve1";
+  groupBcurve3.rna_path = (char *)"groupBcurve3";
+  groupDcurve2.rna_path = (char *)"groupDcurve2";
+
+  BLI_addtail(&action.curves, &groupAcurve1);
+  BLI_addtail(&action.curves, &groupAcurve2);
+  BLI_addtail(&action.curves, &groupBcurve1);
+  BLI_addtail(&action.curves, &groupBcurve2);
+  BLI_addtail(&action.curves, &groupDcurve1);
+  BLI_addtail(&action.curves, &groupBcurve3);  // <-- The error that should be corrected.
+  BLI_addtail(&action.curves, &groupDcurve2);
+
+  // Introduce another error type, by changing some `prev` pointers.
+  groupBcurve1.prev = NULL;
+  groupBcurve3.prev = &groupBcurve2;
+  groupDcurve1.prev = &groupBcurve3;
+
+  bActionGroup groupA = {0};
+  bActionGroup groupB = {0};
+  bActionGroup groupC = {0};
+  bActionGroup groupD = {0};
+  strcpy(groupA.name, "groupA");
+  strcpy(groupB.name, "groupB");
+  strcpy(groupC.name, "groupC");
+  strcpy(groupD.name, "groupD");
+
+  BLI_addtail(&action.groups, &groupA);
+  BLI_addtail(&action.groups, &groupB);
+  BLI_addtail(&action.groups, &groupC);
+  BLI_addtail(&action.groups, &groupD);
+
+  groupAcurve1.grp = &groupA;
+  groupAcurve2.grp = &groupA;
+  groupBcurve1.grp = &groupB;
+  groupBcurve2.grp = &groupB;
+  groupBcurve3.grp = &groupB;
+  groupDcurve1.grp = &groupD;
+  groupDcurve2.grp = &groupD;
+
+  groupA.channels.first = &groupAcurve1;
+  groupA.channels.last = &groupAcurve2;
+  groupB.channels.first = &groupBcurve1;
+  groupB.channels.last = &groupBcurve3;  // The last channel in group B, after group C curve 1.
+  groupD.channels.first = &groupDcurve1;
+  groupD.channels.last = &groupDcurve2;
+
+  EXPECT_EQ(groupA.channels.first, &groupAcurve1);
+  EXPECT_EQ(groupA.channels.last, &groupAcurve2);
+  EXPECT_EQ(groupB.channels.first, &groupBcurve1);
+  EXPECT_EQ(groupB.channels.last, &groupBcurve3);
+  EXPECT_EQ(groupC.channels.first, nullptr);
+  EXPECT_EQ(groupC.channels.last, nullptr);
+  EXPECT_EQ(groupD.channels.first, &groupDcurve1);
+  EXPECT_EQ(groupD.channels.last, &groupDcurve2);
+
+  BKE_action_groups_reconstruct(&action);
+
+  EXPECT_EQ(action.curves.first, &groupAcurve1);
+  EXPECT_EQ(action.curves.last, &groupDcurve2);
+
+  EXPECT_EQ(groupA.prev, nullptr);
+  EXPECT_EQ(groupB.prev, &groupA);
+  EXPECT_EQ(groupC.prev, &groupB);
+  EXPECT_EQ(groupD.prev, &groupC);
+
+  EXPECT_EQ(groupA.next, &groupB);
+  EXPECT_EQ(groupB.next, &groupC);
+  EXPECT_EQ(groupC.next, &groupD);
+  EXPECT_EQ(groupD.next, nullptr);
+
+  EXPECT_EQ(groupA.channels.first, &groupAcurve1);
+  EXPECT_EQ(groupA.channels.last, &groupAcurve2);
+  EXPECT_EQ(groupB.channels.first, &groupBcurve1);
+  EXPECT_EQ(groupB.channels.last, &groupBcurve3);
+  EXPECT_EQ(groupC.channels.first, nullptr);
+  EXPECT_EQ(groupC.channels.last, nullptr);
+  EXPECT_EQ(groupD.channels.first, &groupDcurve1);
+  EXPECT_EQ(groupD.channels.last, &groupDcurve2);
+
+  EXPECT_EQ(groupAcurve1.prev, nullptr);
+  EXPECT_EQ(groupAcurve2.prev, &groupAcurve1);
+  EXPECT_EQ(groupBcurve1.prev, &groupAcurve2);
+  EXPECT_EQ(groupBcurve2.prev, &groupBcurve1);
+  EXPECT_EQ(groupBcurve3.prev, &groupBcurve2);
+  EXPECT_EQ(groupDcurve1.prev, &groupBcurve3);
+  EXPECT_EQ(groupDcurve2.prev, &groupDcurve1);
+
+  EXPECT_EQ(groupAcurve1.next, &groupAcurve2);
+  EXPECT_EQ(groupAcurve2.next, &groupBcurve1);
+  EXPECT_EQ(groupBcurve1.next, &groupBcurve2);
+  EXPECT_EQ(groupBcurve2.next, &groupBcurve3);
+  EXPECT_EQ(groupBcurve3.next, &groupDcurve1);
+  EXPECT_EQ(groupDcurve1.next, &groupDcurve2);
+  EXPECT_EQ(groupDcurve2.next, nullptr);
+}
+
+}  // namespace blender::bke::tests
diff --git a/source/blender/blenloader/intern/versioning_300.c b/source/blender/blenloader/intern/versioning_300.c
index f16b73f3c7b..5d3bde428c0 100644
--- a/source/blender/blenloader/intern/versioning_300.c
+++ b/source/blender/blenloader/intern/versioning_300.c
@@ -34,6 +34,7 @@
 #include "DNA_modifier_types.h"
 #include "DNA_text_types.h"
 
+#include "BKE_action.h"
 #include "BKE_animsys.h"
 #include "BKE_collection.h"
 #include "BKE_fcurve_driver.h"
@@ -480,17 +481,13 @@ void blo_do_versions_300(FileData *fd, Library *UNUSED(lib), Main *bmain)
     }
   }
 
-  /**
-   * Versioning code until next subversion bump goes here.
-   *
-   * \note Be sure to check when bumping the version:
-   * - "versioning_userdef.c", #blo_do_versions_userdef
-   * - "versioning_userdef.c", #do_versions_theme
-   *
-   * \note Keep this message at the bottom of the function.
-   */
-  {
-    /* Keep this block, even when empty. */
+  if (!MAIN_VERSION_ATLEAST(bmain, 300, 9)) {
+    /* Fix a bug where reordering FCurves and bActionGroups could cause some corruption. Just
+     * reconstruct all the action groups & ensure that the FCurves of a group are continuously
+     * stored (i.e. not mixed with other groups) to be sure. See T89435. */
+    LISTBASE_FOREACH (bAction *, act, &bmain->actions) {
+      BKE_action_groups_reconstruct(act);
+    }
 
     FOREACH_NODETREE_BEGIN (bmain, ntree, id) {
       if (ntree->type == NTREE_GEOMETRY) {
@@ -503,4 +500,17 @@ void blo_do_versions_300(FileData *fd, Library *UNUSED(lib), Main *bmain)
     }
     FOREACH_NODETREE_END;
   }
+
+  /**
+   * Versioning code until next subversion bump goes here.
+   *
+   * \note Be sure to check when bumping the version:
+   * - "versioning_userdef.c", #blo_do_versions_userdef
+   * - "versioning_userdef.c", #do_versions_theme
+   *
+   * \note Keep this message at the bottom of the function.
+   */
+  {
+    /* Keep this block, even when empty. */
+  }
 }
diff --git a/source/blender/editors/animation/anim_channels_edit.c b/source/blender/editors/animation/anim_channels_edit.c
index 76b6ce54d29..8f8c1c067d4 100644
--- a/source/blender/editors/animation/anim_channels_edit.c
+++ b/source/blender/editors/animation/anim_channels_edit.c
@@ -1283,6 +1283,9 @@ static void split_groups_action_temp(bAction *act, bActionGroup *tgrp)
     else {
       group_fcurves_last->next->prev = group_fcurves_first->prev;
     }
+
+    /* Clear links pointing outside the per-group list. */
+    group_fcurves_first->prev = group_fcurves_last->next = NULL;
   }
 
   /* Initialize memory for temp-group */
@@ -1337,24 +1340,12 @@ static void join_groups_action_temp(bAction *act)
     if (agrp->flag & AGRP_TEMP) {
       LISTBASE_FOREACH (FCurve *, fcu, &agrp->channels) {
         fcu->grp = NULL;
-        if (fcu == agrp->channels.last) {
-          break;
-        }
       }
 
       BLI_remlink(&act->groups, agrp);
       break;
     }
   }
-
-  /* BLI_movelisttolist() doesn't touch first->prev and last->next pointers in its "dst" list.
-   * Ensure that after the reshuffling the list is properly terminated. */
-  if (!BLI_listbase_is_empty(&act->curves)) {
-    FCurve *act_fcurves_first = act->curves.first;
-    act_fcurves_first->prev = NULL;
-    FCurve *act_fcurves_last = act->curves.last;
-    act_fcurves_last->next = NULL;
-  }
 }
 
 /* Change the order of anim-channels within action