title: 栈操作

React 算法之栈操作

概念

来自 wiki 上的解释: 堆栈(stack)又称为栈或堆叠, 是计算机科学中的一种抽象资料类型, 只允许在有序的线性资料集合的一端(称为堆栈顶端top)进行加入数据(push)和移除数据(pop)的运算. 因而按照后进先出(LIFO, Last In First Out)的原理运作.

注意:

  • 栈(stack)又叫做堆栈, 这里特指数据结构中的栈(另一种程序内存分配中的栈, 本系列不做介绍, 读者可自行了解).
  • 堆栈中虽带有一个堆字, 只是命名, 不要和堆混淆.
  • 常说的堆有 2 种指代, 一种是数据结构中的堆(在React 算法之堆排序中有介绍), 另一种是程序内存分配中的堆(本系列不做介绍, 读者可自行了解).

特性

  1. 先入后出, 后入先出.
  2. 除头尾节点之外, 每个元素有一个前驱, 一个后继.

基本使用

  1. 压栈: push()
  2. 弹栈: pop((
  3. 预览栈顶元素: peek()
  1. class Stack {
  2.   constructor() {
  3.     this.dataStore = [];
  4.     this.top = 0;
  5.   }
  7.   // 压栈
  8.   push(element) {
  9.     this.dataStore[this.top++] = element;
  10.   }
  12.   // 弹栈
  13.   pop() {
  14.     return this.dataStore[--this.top];
  15.   }
  17.   // 预览栈顶元素
  18.   peek() {
  19.     return this.dataStore[this.top - 1];
  20.   }
  22.   // 检测栈内存储了多少个元素
  23.   length() {
  24.     return this.top;
  25.   }
  27.   // 清空栈
  28.   clear() {
  29.     this.top = 0;
  30.   }
  31. }

测试代码:

  1. const test = () => {
  2.   const stack = new Stack();
  3.   console.log('压栈a: ');
  4.   stack.push('a');
  5.   console.log('压栈b: ');
  6.   stack.push('b');
  7.   console.log('压栈c: ');
  8.   stack.push('c');
  9.   console.log('栈高度: ', stack.length());
  10.   console.log('栈顶元素: ', stack.peek());
  11.   console.log('弹出: ', stack.pop());
  12.   console.log('栈顶元素: ', stack.peek());
  13.   console.log('压栈d: ');
  14.   stack.push('d');
  15.   console.log('栈顶元素: ', stack.peek());
  16.   console.log('清空栈: ');
  17.   stack.clear();
  18.   console.log('栈高度: ', stack.length());
  19.   console.log('压栈e: ');
  20.   stack.push('e');
  21.   console.log('栈顶元素: ', stack.peek());
  22. };

利用栈先进后出的特性, 在实际编码中应用非常广泛. 如回溯,递归,深度优先搜索等经典算法都可以利用栈的特性来实现. 由于本文的目的是讲解栈react中的使用场景, 所以与栈相关的经典案例本文不再列举, 请读者移步其他算法资料.

React 当中的使用场景

Context 状态管理 {#context}

在fiber树创建过程中, 如果使用了Context api(具体来说是使用Context.Provider, Class.contextType, Context.Consumer等api), react内部会维护一个栈来保存提供者(Context.Provider)的状态, 供给消费者(Context.Consumer)使用.

首先看stack的定义(ReactFiberStack.js中):

  1. export type StackCursor<T> = {| current: T |};
  3. // 维护一个全局stack
  4. const valueStack: Array<any> = [];
  5. let index = -1;
  7. // 一个工厂函数, 创建StackCursor对象
  8. function createCursor<T>(defaultValue: T): StackCursor<T> {
  9.   return {
  10.     current: defaultValue,
  11.   };
  12. }
  13. function isEmpty(): boolean {
  14.   return index === -1;
  15. }
  16. // 出栈
  17. function pop<T>(cursor: StackCursor<T>, fiber: Fiber): void {
  18.   if (index < 0) {
  19.     return;
  20.   }
  21.   cursor.current = valueStack[index];
  22.   valueStack[index] = null;
  23.   index--;
  24. }
  25. // 入栈
  26. function push<T>(cursor: StackCursor<T>, value: T, fiber: Fiber): void {
  27.   index++;
  28.   // 注意: 这里存储的是 cursor当前值, 随后更新了cursor.current为
  29.   valueStack[index] = cursor.current;
  30.   cursor.current = value;
  31. }

在ReactFiberStack.js源码中, 定义的valueStack作为全局变量, 用来存储所有的StackCursor.current(不仅仅存储context api相关的StackCursor, 在context 原理章节中详细解读, 本节只讨论与context api相关的栈操作).

注意StackCursor是一个泛型对象, 与context api相关的StackCursor定义在ReactFiberNewContext.js:

  1. // 定义全局 valueCursor, 用于管理<Context.Provider/>组件的value
  2. const valueCursor: StackCursor<mixed> = createCursor(null);
  4. // ...省略无关代码
  6. // 将context当前的值保存到valueCursor中, 并设置context._currentValue为最新值
  7. // 运行完成之后context为最新状态
  8. export function pushProvider<T>(providerFiber: Fiber, nextValue: T): void {
  9.   const context: ReactContext<T> = providerFiber.type._context;
  10.   push(valueCursor, context._currentValue, providerFiber);
  11.   context._currentValue = nextValue;
  12. }
  14. // 取出valueCursor中保存的旧值, 设置到context._currentValue上.
  15. // 运行完成之后context恢复到上一个状态
  16. export function popProvider(providerFiber: Fiber): void {
  17.   const currentValue = valueCursor.current;
  18.   pop(valueCursor, providerFiber);
  19.   const context: ReactContext<any> = providerFiber.type._context;
  20.   context._currentValue = currentValue;
  21. }

假设有如下组件结构(平时开发很难有这样的代码, 此处完全是为了演示context api中涉及到的栈操作):

  1. const MyContext = React.createContext(0);
  3. export default function App() {
  4.   return (
  5.     // 第一级
  6.     <MyContext.Provider value={1}>
  7.       <MyContext.Consumer>
  8.         {value1 => (
  9.           //第二级嵌套
  10.           <MyContext.Provider value={2}>
  11.             <MyContext.Consumer>
  12.               {value2 => (
  13.                 // 第三级嵌套
  14.                 <MyContext.Provider value={3}>
  15.                   <MyContext.Consumer>
  16.                     {value3 => (
  17.                       <span>
  18.                         {value1}-{value2}-{value3}
  19.                       </span>
  20.                     )}
  21.                   </MyContext.Consumer>
  22.                 </MyContext.Provider>
  23.               )}
  24.             </MyContext.Consumer>
  25.           </MyContext.Provider>
  26.         )}
  27.       </MyContext.Consumer>
  28.     </MyContext.Provider>
  29.   );
  30. }

可在codesandbox中查看运行结果.

将fiber树构造过程中MyContext对象在栈中的变化情况表示出来:

  1. beginWork阶段: 入栈

    • reconciler之前, 由于const MyContext = React.createContext(0);已经创建了MyContext对象, 所以其初始值是0.
    • reconciler过程中, 每当遇到Context.Provider类型的节点, 则会执行pushProvider.

React 算法之栈操作 - 图1

  1. completeWork阶段: 出栈
    • reconciler过程中, 每当遇到Context.Provider类型的节点, 则会执行popProvider.
    • reconciler之后, valueStack和valueCursor以及MyContext都恢复到了初始状态.

React 算法之栈操作 - 图2

注意:

  • 本节只分析context实现源码中与栈相关的部分, 所以只涉及到了Context.Provider(供应者)节点.
  • 对于Context.Consumer(消费者)以及更新阶段context的运行机制的深入解读放在context原理章节中.

executionContext 执行上下文

executionContext是在ReactFiberWorkLoop.js中定义的一个全局变量(相对于该闭包), 且定义成二进制变量, 通过位运算来维护其状态(在React 算法之位运算一文中已有介绍).

表面上看executionContext和栈并没有直接关系, 但实际在改变executionContext的时候, 巧妙的利用了函数调用栈, 实现executionContext状态的维护.

本节主要是体现executionContext和函数调用栈之间的配合运用(具体源码), 这里以batchedUpdates和unbatchedUpdates为例进行分析.

  1. export function batchedUpdates<A, R>(fn: A => R, a: A): R {
  2.   // 在执行回调之前, 先改变 executionContext
  3.   const prevExecutionContext = executionContext;
  4.   executionContext |= BatchedContext;
  5.   try {
  6.     return fn(a);
  7.   } finally {
  8.     // 回调执行完毕之后, 再恢复到以前的值 prevExecutionContext
  9.     executionContext = prevExecutionContext;
  10.     // ... 省略无关代码
  11.   }
  12. }
  14. export function unbatchedUpdates<A, R>(fn: (a: A) => R, a: A): R {
  15.   const prevExecutionContext = executionContext;
  16.   executionContext &= ~BatchedContext;
  17.   executionContext |= LegacyUnbatchedContext;
  18.   try {
  19.     return fn(a);
  20.   } finally {
  21.     executionContext = prevExecutionContext;
  22.     // ... 省略无关代码
  23.   }
  24. }
  26. // ... 省略其他函数

这些函数的共性:

  1. 执行回调之前, 先保存当前值为prevExecutionContext, 再改变 executionContext.
  2. 在执行回调fn期间, 无论函数fn调用栈有多深, 被改变过的executionContext始终有效.
  3. 回调执行完毕之后, 恢复到以前的值 prevExecutionContext.

总结

本节主要介绍了栈在react源码中的使用情况. 涉及入栈出栈等基本操作(Context 状态管理), 以及对函数调用栈的巧妙运用(改变executionContext执行上下文).

由于reconciler过程是一个深度优先遍历过程, 对于fiber树来讲, 向下探寻(beginWork阶段)和向上回溯(completeWork阶段)天然就和栈的入栈(push)和出栈(pop)能够无缝配合(context 机制就是在这个特性上建立起来的).

参考资料