React taskQueue 排序过程

React调度过程中是根据优先级来确定任务的过期时间，不同任务的过期时间是不同的，从而导致任务执行的时机不一样，下面是React创建任务的源码，其中newTask.sortIndex设置为过期时间用于排序。

function unstable_scheduleCallback(
  priorityLevel: PriorityLevel,
  callback: Callback,
  options?: {delay: number},
): Task {
  var currentTime = getCurrentTime();
  var startTime;
  // ....

  var timeout;
  switch (priorityLevel) {
    case ImmediatePriority:
      // Times out immediately
      timeout = -1;
      break;
    case UserBlockingPriority:
      // Eventually times out
      timeout = userBlockingPriorityTimeout;
      break;
    case IdlePriority:
      // Never times out
      timeout = maxSigned31BitInt;
      break;
    case LowPriority:
      // Eventually times out
      timeout = lowPriorityTimeout;
      break;
    case NormalPriority:
    default:
      // Eventually times out
      timeout = normalPriorityTimeout;
      break;
  }
	// 过期时间
  var expirationTime = startTime + timeout;

  var newTask: Task = {
    id: taskIdCounter++,
    callback,
    priorityLevel,
    startTime,
    expirationTime,
    sortIndex: -1,
  };
  // ....
  if (startTime > currentTime) {
  // ....
  } else {
    // sortIndex 使用过期时间用于小根堆排序
    newTask.sortIndex = expirationTime;
    push(taskQueue, newTask);
    // ....
    if (!isHostCallbackScheduled && !isPerformingWork) {
      isHostCallbackScheduled = true;
      // 开始调度
      requestHostCallback();
    }
  }

  return newTask;
}

但是每次执行workLoop时都是取taskQueue中的第一个元素的过期时间作为依据，下面是执行任务的源码，每次会比较currentTask.expirationTime > currentTime && shouldYieldToHost()是否成立

function workLoop(initialTime: number) {
  let currentTime = initialTime;
  advanceTimers(currentTime);
  currentTask = peek(taskQueue);
  while (
    currentTask !== null &&
    !(enableSchedulerDebugging && isSchedulerPaused)
  ) {
    // 如果任务没有过期并且应该中断时，跳出循环（由上层函数再次调用任务）
    if (currentTask.expirationTime > currentTime && shouldYieldToHost()) {
      // This currentTask hasn't expired, and we've reached the deadline.
      break;
    }
    // ...
    currentTask = peek(taskQueue);
  }
  // Return whether there's additional work
  if (currentTask !== null) {
    // 返回true表示还有任务没有执行完成，由上层函数再次调用workLoop来执行任务
    return true;
  } else {
    // taskQueue 执行完后，将排队任务里的第一个任务拿出来进行倒计时，用于触发下一次调度
    const firstTimer = peek(timerQueue);
    if (firstTimer !== null) {
      requestHostTimeout(handleTimeout, firstTimer.startTime - currentTime);
    }
    return false;
  }
}

如果任务的先后顺序不正确，可能导致错误，比如下面的例子，有任务taskA、taskB，currentTime = 15，如果直接执行由于taskB > currentTime，同时shouldYieldToHost()也为 true的话，就会直接中断，所以React对taskQueue使用小根堆，保证第一个元素始终为expirationTime最小。

const taskA = {
    expirationTime: 10,
  }
const taskB = {
    expirationTime: 20,
  }
const currentTime = 15;
const taskQueue = [
  taskB,
  taskA,
]

任务的push、peek、pop操作

这些函数在React的SchedulerMinHeap.js文件中

type Heap<T: Node> = Array<T>;
type Node = {
  id: number,
  sortIndex: number,
  ...
};

export function push<T: Node>(heap: Heap<T>, node: T): void {
  const index = heap.length;
  heap.push(node);
  siftUp(heap, node, index);
}

export function peek<T: Node>(heap: Heap<T>): T | null {
  return heap.length === 0 ? null : heap[0];
}

export function pop<T: Node>(heap: Heap<T>): T | null {
  if (heap.length === 0) {
    return null;
  }
  const first = heap[0];
  const last = heap.pop();
  if (last !== first) {
    heap[0] = last;
    siftDown(heap, last, 0);
  }
  return first;
}

function siftUp<T: Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  while (index > 0) {
    const parentIndex = (index - 1) >>> 1;
    const parent = heap[parentIndex];
    if (compare(parent, node) > 0) {
      // The parent is larger. Swap positions.
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      // The parent is smaller. Exit.
      return;
    }
  }
}

function siftDown<T: Node>(heap: Heap<T>, node: T, i: number): void {
  let index = i;
  const length = heap.length;
  const halfLength = length >>> 1;
  while (index < halfLength) {
    const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];

    // If the left or right node is smaller, swap with the smaller of those.
    if (compare(left, node) < 0) {
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      // Neither child is smaller. Exit.
      return;
    }
  }
}

function compare(a: Node, b: Node) {
  // Compare sort index first, then task id.
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}

taskQueue是一个小根堆，所以每次新增和删除元素都会对堆进行排序。

1. 每次 push都会通过siftUp进行排序，就是将新的节点添加到末尾，然后与父节点进行比较，如果比父节点小就交换位置，一直到根节点为止，否则维持不变。
2. 每次pop都通过siftDown将最后一个节点移到开头，然后从根节点开始向下比较；
   1. 如果父节点比左右节点都大，则 父节点与右子节点交换位置；
   2. 如果父节点比左节点大，则 父节点与左子节点交换位置；
   3. 如果父节点比右节点大，则 父节点与右子节点交换位置；
   4. 如果父节点比左右节点都小，停止比较。