Fix a TODO and slightly optimize backfill strategy. (#4621)

Closes https://github.com/flutter/flutter/issues/165683.

A few changes:

- Release candidates are now kDefault, so that reruns still take priority
- Reruns check for tree-redness cause, not just last kBatchSize tasks
- Tip-of-tree runs at kDefaultPriority
diff --git a/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart b/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart
index 4961b4e..47cd8e3 100644
--- a/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart
+++ b/app_dart/lib/src/request_handlers/scheduler/backfill_strategy.dart
@@ -72,8 +72,12 @@
       return false;
     });
 
-    // Now, create two lists: high priority (recent failure or RC) and regular.
+    // Now, create three lists
+    // 1. Rerun existing failure
     final higherPriorityReruns = <TaskRef>[];
+    // 2. Tip of tree
+    final mediumPriorityReruns = <TaskRef>[];
+    // 3. Everything else
     final lowerPriorityReruns = <TaskRef>[];
 
     for (final (_, column) in grid.eligibleTasks) {
@@ -83,13 +87,27 @@
           continue;
         }
 
-        // Determine whether it is high priority or regular priority.
-        if (isReleaseCandidateBranch(branchName: grid.getCommit(row).branch) ||
-            column
-                .getRange(i, min(i + BatchPolicy.kBatchSize + 1, column.length))
-                .any((t) => fs.Task.taskFailStatusSet.contains(t.status))) {
+        // Determine relative priority.
+        if (_indexOfTreeRedCause(column) case final index? when index > i) {
+          // ⬜ i
+          // 🟥 index
+          // ^^ Use high priority, this is turning the tree red.
+          //
+          // ⬜ i
+          // 🟩
+          // 🟥 index will return as `null`
+          // ^^ Uses default (or backfill) priority, next commit passed.
           higherPriorityReruns.add(row);
+        } else if (isReleaseCandidateBranch(
+          branchName: grid.getCommit(row).branch,
+        )) {
+          // Release candidates should take priority over normal backfill.
+          mediumPriorityReruns.add(row);
+        } else if (row.commitSha == grid.getCommit(column[0]).sha) {
+          // Tip of tree should take priority over normal backfill.
+          mediumPriorityReruns.add(row);
         } else {
+          // Everything else.
           lowerPriorityReruns.add(row);
         }
 
@@ -98,12 +116,16 @@
       }
     }
 
-    // Shuffle both sublists.
-    higherPriorityReruns.shuffle(_random);
-    lowerPriorityReruns.shuffle(_random);
+    // Shuffle each sublist.
+    for (final list in [
+      higherPriorityReruns,
+      mediumPriorityReruns,
+      lowerPriorityReruns,
+    ]) {
+      list.shuffle(_random);
+    }
 
-    // Return both of these lists, concatted.
-    // TODO(matanlurey): ToT tasks should be run with kDefaultPriority.
+    // Return each list concatted in order.
     return [
       ...higherPriorityReruns.map(
         (t) => grid.createBackfillTask(
@@ -111,6 +133,12 @@
           priority: LuciBuildService.kRerunPriority,
         ),
       ),
+      ...mediumPriorityReruns.map(
+        (t) => grid.createBackfillTask(
+          t,
+          priority: LuciBuildService.kDefaultPriority,
+        ),
+      ),
       ...lowerPriorityReruns.map(
         (t) => grid.createBackfillTask(
           t,
@@ -119,4 +147,21 @@
       ),
     ];
   }
+
+  static int? _indexOfTreeRedCause(Iterable<TaskRef> tasks) {
+    for (final (i, task) in tasks.indexed) {
+      // Only evaluate completed tasks.
+      if (!fs.Task.finishedStatusValues.contains(task.status)) {
+        continue;
+      }
+
+      // Returns true for failed tasks, and false for successful.
+      if (fs.Task.taskFailStatusSet.contains(task.status)) {
+        return i;
+      } else {
+        return null;
+      }
+    }
+    return null;
+  }
 }
diff --git a/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart b/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart
index 1f56346..c387105 100644
--- a/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart
+++ b/app_dart/test/request_handlers/scheduler/backfill_strategy_test.dart
@@ -10,6 +10,7 @@
 import 'package:cocoon_service/src/request_handlers/scheduler/backfill_strategy.dart';
 import 'package:cocoon_service/src/service/luci_build_service.dart';
 import 'package:cocoon_service/src/service/luci_build_service/commit_task_ref.dart';
+import 'package:test/fake.dart';
 import 'package:test/test.dart';
 
 import '../../src/utilities/entity_generators.dart';
@@ -20,8 +21,7 @@
 
   group('DefaultBackfillStrategy', () {
     // Pick a deterministic seed, because shuffling is involved.
-    final random = Random(0);
-    final strategy = DefaultBackfillStrategy(random);
+    final strategy = DefaultBackfillStrategy(_FakeRandom());
 
     final commits = [
       for (var i = 0; i < 10; i++)
@@ -127,14 +127,54 @@
       ]);
       // dart format on
 
+      expect(
+        strategy.determineBackfill(grid),
+        unorderedEquals([
+          isBackfillTask
+              .hasCommit(commits[0])
+              .hasTarget(targets[0])
+              .hasPriority(LuciBuildService.kDefaultPriority),
+          isBackfillTask
+              .hasCommit(commits[0])
+              .hasTarget(targets[1])
+              .hasPriority(LuciBuildService.kDefaultPriority),
+        ]),
+      );
+    });
+
+    // INPUT:
+    // 🧑‍💼 ⬜ 🟩
+    // 🧑‍💼 ⬜ ⬜
+    //
+    // OUTPUT:
+    // 🧑‍💼 🟨 🟩
+    // 🧑‍💼 ⬜ 🟨
+    test('gives lowest priority to non-ToT commits', () {
+      // dart format off
+      grid = BackfillGrid.from([
+        //           Linux TASK_0            Linux TASK_1
+        (commits[0], [taskNew       (0, 0),  taskSucceeded (0, 1)]),
+        (commits[1], [taskNew       (1, 0),  taskNew       (1, 1)]),
+      ], tipOfTreeTargets: [
+        targets[0],
+        targets[1],
+      ]);
+      // dart format on
+
       expect(strategy.determineBackfill(grid), [
-        isBackfillTask.hasCommit(commits[0]).hasTarget(targets[0]),
-        isBackfillTask.hasCommit(commits[0]).hasTarget(targets[1]),
+        isBackfillTask
+            .hasCommit(commits[0])
+            .hasTarget(targets[0])
+            .hasPriority(LuciBuildService.kDefaultPriority),
+        isBackfillTask
+            .hasCommit(commits[1])
+            .hasTarget(targets[1])
+            .hasPriority(LuciBuildService.kBackfillPriority),
       ]);
     });
 
     // INPUT:
-    // 🧑‍💼 ⬜ ⬜ ⬜ kBatchSize = 6
+    // 🧑‍💼 ⬜ ⬜ ⬜ < 0
     // 🧑‍💼 ⬜ ⬜ ⬜ < 1
     // 🧑‍💼 ⬜ ⬜ ⬜ < 2
     // 🧑‍💼 ⬜ ⬜ ⬜ < 3
@@ -144,7 +184,7 @@
     // 🧑‍💼 🟥 ⬜ ⬜ < 7
     //
     // OUTPUT:
-    // 🧑‍💼 3️⃣ 1️⃣ 2️⃣ kBatchSize = 6
+    // 🧑‍💼 3️⃣ 2️⃣ 1️⃣ < 0
     // 🧑‍💼 ⬜ ⬜ ⬜ < 1
     // 🧑‍💼 ⬜ ⬜ ⬜ < 2
     // 🧑‍💼 ⬜ ⬜ ⬜ < 3
@@ -152,7 +192,7 @@
     // 🧑‍💼 ⬜ ⬜ 🟥 < 5
     // 🧑‍💼 ⬜ 🟥 ⬜ < 6
     // 🧑‍💼 🟥 ⬜ ⬜ < 7
-    test('places previously failing within kBatchSize as high priority', () {
+    test('places previously failing as high priority ignoring kBatchSize', () {
       // dart format off
       grid = BackfillGrid.from([
         //           Linux TASK_0            Linux TASK_1          Linux TASK_2
@@ -171,20 +211,28 @@
       ]);
       // dart format on
 
-      expect(strategy.determineBackfill(grid), [
-        isBackfillTask.hasCommit(commits[0]).hasTarget(targets[1]), // 1️⃣
-        isBackfillTask.hasCommit(commits[0]).hasTarget(targets[2]), // 2️⃣
-        isBackfillTask.hasCommit(commits[0]).hasTarget(targets[0]), // 3️⃣
-      ]);
+      expect(
+        strategy.determineBackfill(grid),
+        unorderedEquals([
+          isBackfillTask // 1️⃣
+              .hasCommit(commits[0])
+              .hasTarget(targets[2])
+              .hasPriority(LuciBuildService.kRerunPriority),
+          isBackfillTask // 2️⃣
+              .hasCommit(commits[0])
+              .hasTarget(targets[1])
+              .hasPriority(LuciBuildService.kRerunPriority),
+          isBackfillTask // 3️⃣
+              .hasCommit(commits[0])
+              .hasTarget(targets[0])
+              .hasPriority(LuciBuildService.kRerunPriority),
+        ]),
+      );
     });
 
-    test('any commit to a release candidate branch has high priority', () {
+    test('any commit to tip-of-tree has medium priority', () {
       final commit = CommitRef.fromFirestore(
-        generateFirestoreCommit(
-          1,
-          branch: 'flutter-3.32-candidate.0',
-          sha: '123',
-        ),
+        generateFirestoreCommit(1, sha: '123'),
       );
       // dart format off
       grid = BackfillGrid.from([
@@ -200,8 +248,15 @@
         isBackfillTask
             .hasCommit(commit)
             .hasTarget(targets[0])
-            .hasPriority(LuciBuildService.kRerunPriority),
+            .hasPriority(LuciBuildService.kDefaultPriority),
       ]);
     });
   });
 }
+
+final class _FakeRandom extends Fake implements Random {
+  @override
+  int nextInt(_) {
+    return 0;
+  }
+}