WP3: Mutation & aliasing model (@analyzer subagent)

<file>
00001| # The Mutability & Aliasing Model
00002| 
00003| This document describes the new (as of June 2025) mutability and aliasing model powering React Compiler. The mutability and aliasing system is a conceptual subcomponent whose primary role is to determine minimal sets of values that mutate together, and the range of instructions over which those mutations occur. These minimal sets of values that mutate together, and the corresponding instructions doing those mutations, are ultimately grouped into reactive scopes, which then translate into memoization blocks in the output (after substantial additional processing described in the comments of those passes).
00004| 
00005| To build an intuition, consider the following example:
00006| 
00007| ```js
00008| function Component() {
00009|     // a is created and mutated over the course of these two instructions:
00010|     const a = {};
00011|     mutate(a);
00012| 
00013|     // b and c are created and mutated together — mutate might modify b via c
00014|     const b = {};
00015|     const c = {b};
00016|     mutate(c);
00017| 
00018|     // does not modify a/b/c
00019|     return <Foo a={a} c={c} />
00020| }
00021| ```
00022| 
00023| The goal of mutability and aliasing inference is to understand the set of instructions that create/modify a, b, and c.
00024| 
00025| In code, the mutability and aliasing model is compromised of the following phases:
00026| 
00027| * `InferMutationAliasingEffects`. Infers a set of mutation and aliasing effects for each instruction. The approach is to generate a set of candidate effects based purely on the semantics of each instruction and the types of the operands, then use abstract interpretation to determine the actual effects (or errros) that would apply. For example, an instruction that by default has a Capture effect might downgrade to an ImmutableCapture effect if the value is known to be frozen.
00028| * `InferMutationAliasingRanges`. Infers a mutable range (start:end instruc...

<file>
00001| /**
00002|  * Copyright (c) Meta Platforms, Inc. and affiliates.
00003|  *
00004|  * This source code is licensed under the MIT license found in the
00005|  * LICENSE file in the root directory of this source tree.
00006|  */
00007| 
00008| import {CompilerDiagnostic} from '../CompilerError';
00009| import {
00010|   FunctionExpression,
00011|   GeneratedSource,
00012|   Hole,
00013|   IdentifierId,
00014|   ObjectMethod,
00015|   Place,
00016|   SourceLocation,
00017|   SpreadPattern,
00018|   ValueKind,
00019|   ValueReason,
00020| } from '../HIR';
00021| import {FunctionSignature} from '../HIR/ObjectShape';
00022| import {printSourceLocation} from '../HIR/PrintHIR';
00023| 
00024| /**
00025|  * `AliasingEffect` describes a set of "effects" that an instruction/terminal has on one or
00026|  * more values in a program. These effects include mutation of values, freezing values,
00027|  * tracking data flow between values, and other specialized cases.
00028|  */
00029| export type AliasingEffect =
00030|   /**
00031|    * Marks the given value and its direct aliases as frozen.
00032|    *
00033|    * Captured values are *not* considered frozen, because we cannot be sure that a previously
00034|    * captured value will still be captured at the point of the freeze.
00035|    *
00036|    * For example:
00037|    * const x = {};
00038|    * const y = [x];
00039|    * y.pop(); // y dosn't contain x anymore!
00040|    * freeze(y);
00041|    * mutate(x); // safe to mutate!
00042|    *
00043|    * The exception to this is FunctionExpressions - since it is impossible to change which
00044|    * value a function closes over[1] we can transitively freeze functions and their captures.
00045|    *
00046|    * [1] Except for `let` values that are reassigned and closed over by a function, but we
00047|    * handle this explicitly with StoreContext/LoadContext.
00048|    */
00049|   | {kind: 'Freeze'; value: Place; reason: ValueReason}
00050|   /**
00051|    * Mutate ...

<file>
00001| /**
00002|  * Copyright (c) Meta Platforms, Inc. and affiliates.
00003|  *
00004|  * This source code is licensed under the MIT license found in the
00005|  * LICENSE file in the root directory of this source tree.
00006|  */
00007| 
00008| import {BindingKind} from '@babel/traverse';
00009| import * as t from '@babel/types';
00010| import {
00011|   CompilerDiagnostic,
00012|   CompilerError,
00013|   ErrorCategory,
00014| } from '../CompilerError';
00015| import {assertExhaustive} from '../Utils/utils';
00016| import {Environment, ReactFunctionType} from './Environment';
00017| import type {HookKind} from './ObjectShape';
00018| import {Type, makeType} from './Types';
00019| import {z} from 'zod/v4';
00020| import type {AliasingEffect} from '../Inference/AliasingEffects';
00021| import {isReservedWord} from '../Utils/Keyword';
00022| import {Err, Ok, Result} from '../Utils/Result';
00023| 
00024| /*
00025|  * *******************************************************************************************
00026|  * *******************************************************************************************
00027|  * ************************************* Core Data Model *************************************
00028|  * *******************************************************************************************
00029|  * *******************************************************************************************
00030|  */
00031| 
00032| // AST -> (lowering) -> HIR -> (analysis) -> Reactive Scopes -> (codegen) -> AST
00033| 
00034| /*
00035|  * A location in a source file, intended to be used for providing diagnostic information and
00036|  * transforming code while preserving source information (ie to emit source maps).
00037|  *
00038|  * `GeneratedSource` indicates that there is no single source location from which the code derives.
00039|  */
00040| export const GeneratedSource = Symbol();
00041| export type SourceLocation = t.SourceLocation | typeof Generate...

<file>
00001| (** Closure decomposition: scope analysis -> Worker groups -> IR.
00002| 
00003|     Algorithm: 1. Seed groups from mutable state: functions that capture the
00004|     same mutable variable are placed in the same group. 2. Remaining functions
00005|     (no mutable captures) become their own group. 3. Cross-group function calls
00006|     become service binding dependencies. 4. Convert groups to IR Workers with KV
00007|     and service bindings. *)
00008| 
00009| type worker_group = {
00010|   name : string;
00011|   functions : string list;
00012|   owned_state : string list;
00013|   service_deps : string list;
00014| }
00015| 
00016| (** Find which group a function belongs to. *)
00017| let find_group_of_function (groups : worker_group list) (fn_name : string) :
00018|     string option =
00019|   List.find_map
00020|     (fun g -> if List.mem fn_name g.functions then Some g.name else None)
00021|     groups
00022| 
00023| (** Derive a group name from the mutable state variable name. e.g. "store" ->
00024|     "storage", "cache" -> "cache" *)
00025| let group_name_of_state (state_var : string) : string =
00026|   if state_var = "store" then "storage" else state_var
00027| 
00028| let clamp_score (score : int) : int = max 0 (min 100 score)
00029| 
00030| let contains_substr (s : string) (sub : string) : bool =
00031|   let len_s = String.length s in
00032|   let len_sub = String.length sub in
00033|   if len_sub = 0 then true
00034|   else if len_sub > len_s then false
00035|   else
00036|     let rec loop i =
00037|       if i > len_s - len_sub then false
00038|       else if String.sub s i len_sub = sub then true
00039|       else loop (i + 1)
00040|     in
00041|     loop 0
00042| 
00043| let any_name_matches (names : string list) (keywords : string list) : bool =
00044|   List.exists
00045|     (fun name ->
00046|       let lowered = String.lowercase_ascii name in
00047|       List.exists (fun keyword -> contains_substr lowered keyword) keyword...

<file>
00001| (** Closure decomposition: scope analysis results -> IR config.
00002| 
00003|     Groups closures into Workers based on shared mutable state, generates KV
00004|     bindings for mutable state and service bindings for cross-group function
00005|     calls. *)
00006| 
00007| type worker_group = {
00008|   name : string;
00009|   functions : string list;
00010|   owned_state : string list;
00011|   service_deps : string list;
00012| }
00013| (** A logical group of functions that will become a single Worker. *)
00014| 
00015| val decompose : Scope.analysis_result -> worker_group list
00016| 
00017| val find_group_of_function : worker_group list -> string -> string option
00018| (** [find_group_of_function groups fn_name] returns the name of the group
00019|     that contains [fn_name], or [None]. *)
00020| 
00021| val do_fit_score : worker_group -> Scope.analysis_result -> int
00022| (** [do_fit_score group analysis] is a heuristic score in [0, 100] indicating
00023|     how well [group] fits Durable Object coordination semantics. *)
00024| 
00025| val infer_do_annotation :
00026|   worker_group -> Scope.analysis_result -> Ir.do_annotation option
00027| (** [infer_do_annotation group analysis] derives a Durable Object hint for
00028|     [group] when the fit score is high enough. *)
00029| 
00030| val to_ir : worker_group list -> Scope.analysis_result -> Ir.config
00031| 

(End of file - total 31 lines)
</file>

<file>
00001| /**
00002|  * Copyright (c) Meta Platforms, Inc. and affiliates.
00003|  *
00004|  * This source code is licensed under the MIT license found in the
00005|  * LICENSE file in the root directory of this source tree.
00006|  */
00007| 
00008| import {
00009|   CompilerDiagnostic,
00010|   CompilerError,
00011|   Effect,
00012|   SourceLocation,
00013|   ValueKind,
00014| } from '..';
00015| import {
00016|   BasicBlock,
00017|   BlockId,
00018|   DeclarationId,
00019|   Environment,
00020|   FunctionExpression,
00021|   GeneratedSource,
00022|   getHookKind,
00023|   HIRFunction,
00024|   Hole,
00025|   IdentifierId,
00026|   Instruction,
00027|   InstructionKind,
00028|   InstructionValue,
00029|   isArrayType,
00030|   isJsxType,
00031|   isMapType,
00032|   isPrimitiveType,
00033|   isRefOrRefValue,
00034|   isSetType,
00035|   makeIdentifierId,
00036|   Phi,
00037|   Place,
00038|   SpreadPattern,
00039|   Type,
00040|   ValueReason,
00041| } from '../HIR';
00042| import {
00043|   eachInstructionValueOperand,
00044|   eachPatternItem,
00045|   eachTerminalOperand,
00046|   eachTerminalSuccessor,
00047| } from '../HIR/visitors';
00048| import {Ok, Result} from '../Utils/Result';
00049| import {
00050|   assertExhaustive,
00051|   getOrInsertDefault,
00052|   getOrInsertWith,
00053|   Set_isSuperset,
00054| } from '../Utils/utils';
00055| import {
00056|   printAliasingEffect,
00057|   printAliasingSignature,
00058|   printIdentifier,
00059|   printInstruction,
00060|   printInstructionValue,
00061|   printPlace,
00062| } from '../HIR/PrintHIR';
00063| import {FunctionSignature} from '../HIR/ObjectShape';
00064| import prettyFormat from 'pretty-format';
00065| import {createTemporaryPlace} from '../HIR/HIRBuilder';
00066| import {
00067|   AliasingEffect,
00068|   AliasingSignature,
00069|   hashEffect,
00070|   MutationReason,
00071| } from './AliasingEffects';
00072| import {ErrorCategory} from '../CompilerError';
00073| 
00074| const DEBUG = false;...

<file>
00001| /**
00002|  * Copyright (c) Meta Platforms, Inc. and affiliates.
00003|  *
00004|  * This source code is licensed under the MIT license found in the
00005|  * LICENSE file in the root directory of this source tree.
00006|  */
00007| 
00008| import {CompilerError, SourceLocation} from '..';
00009| import {
00010|   BlockId,
00011|   Effect,
00012|   HIRFunction,
00013|   Identifier,
00014|   IdentifierId,
00015|   InstructionId,
00016|   isJsxType,
00017|   makeInstructionId,
00018|   ValueKind,
00019|   ValueReason,
00020|   Place,
00021|   isPrimitiveType,
00022| } from '../HIR/HIR';
00023| import {
00024|   eachInstructionLValue,
00025|   eachInstructionValueOperand,
00026|   eachTerminalOperand,
00027| } from '../HIR/visitors';
00028| import {assertExhaustive, getOrInsertWith} from '../Utils/utils';
00029| import {Err, Ok, Result} from '../Utils/Result';
00030| import {AliasingEffect, MutationReason} from './AliasingEffects';
00031| 
00032| /**
00033|  * This pass builds an abstract model of the heap and interprets the effects of the
00034|  * given function in order to determine the following:
00035|  * - The mutable ranges of all identifiers in the function
00036|  * - The externally-visible effects of the function, such as mutations of params and
00037|  *   context-vars, aliasing between params/context-vars/return-value, and impure side
00038|  *   effects.
00039|  * - The legacy `Effect` to store on each Place.
00040|  *
00041|  * This pass builds a data flow graph using the effects, tracking an abstract notion
00042|  * of "when" each effect occurs relative to the others. It then walks each mutation
00043|  * effect against the graph, updating the range of each node that would be reachable
00044|  * at the "time" that the effect occurred.
00045|  *
00046|  * This pass also validates against invalid effects: any function that is reachable
00047|  * by being called, or via a Render effect, is validated against mutating globals
00048|  * or calli...

<file>
00501|         instr,
00502|       );
00503|       context.instructionSignatureCache.set(instr, instructionSignature);
00504|     }
00505|     const effects = applySignature(context, state, instructionSignature, instr);
00506|     instr.effects = effects;
00507|   }
00508|   const terminal = block.terminal;
00509|   if (terminal.kind === 'try' && terminal.handlerBinding != null) {
00510|     context.catchHandlers.set(terminal.handler, terminal.handlerBinding);
00511|   } else if (terminal.kind === 'maybe-throw' && terminal.handler !== null) {
00512|     const handlerParam = context.catchHandlers.get(terminal.handler);
00513|     if (handlerParam != null) {
00514|       CompilerError.invariant(state.kind(handlerParam) != null, {
00515|         reason:
00516|           'Expected catch binding to be intialized with a DeclareLocal Catch instruction',
00517|         loc: terminal.loc,
00518|       });
00519|       const effects: Array<AliasingEffect> = [];
00520|       for (const instr of block.instructions) {
00521|         if (
00522|           instr.value.kind === 'CallExpression' ||
00523|           instr.value.kind === 'MethodCall'
00524|         ) {
00525|           /**
00526|            * Many instructions can error, but only calls can throw their result as the error
00527|            * itself. For example, `c = a.b` can throw if `a` is nullish, but the thrown value
00528|            * is an error object synthesized by the JS runtime. Whereas `throwsInput(x)` can
00529|            * throw (effectively) the result of the call.
00530|            *
00531|            * TODO: call applyEffect() instead. This meant that the catch param wasn't inferred
00532|            * as a mutable value, though. See `try-catch-try-value-modified-in-catch-escaping.js`
00533|            * fixture as an example
00534|            */
00535|           state.appendAlias(handlerParam, instr.lvalue);
00536|           const kind = state.kind(instr.lvalue).kind;
00537|           if (kind...

<file>
00501|   const ignoredErrors = new CompilerError();
00502|   for (const param of [...fn.params, ...fn.context, fn.returns]) {
00503|     const place = param.kind === 'Identifier' ? param : param.place;
00504|     tracked.push(place);
00505|   }
00506|   for (const into of tracked) {
00507|     const mutationIndex = index++;
00508|     state.mutate(
00509|       mutationIndex,
00510|       into.identifier,
00511|       null,
00512|       true,
00513|       MutationKind.Conditional,
00514|       into.loc,
00515|       null,
00516|       ignoredErrors,
00517|     );
00518|     for (const from of tracked) {
00519|       if (
00520|         from.identifier.id === into.identifier.id ||
00521|         from.identifier.id === fn.returns.identifier.id
00522|       ) {
00523|         continue;
00524|       }
00525|       const fromNode = state.nodes.get(from.identifier);
00526|       CompilerError.invariant(fromNode != null, {
00527|         reason: `Expected a node to exist for all parameters and context variables`,
00528|         loc: into.loc,
00529|       });
00530|       if (fromNode.lastMutated === mutationIndex) {
00531|         if (into.identifier.id === fn.returns.identifier.id) {
00532|           // The return value could be any of the params/context variables
00533|           functionEffects.push({
00534|             kind: 'Alias',
00535|             from,
00536|             into,
00537|           });
00538|         } else {
00539|           // Otherwise params/context-vars can only capture each other
00540|           functionEffects.push({
00541|             kind: 'Capture',
00542|             from,
00543|             into,
00544|           });
00545|         }
00546|       }
00547|     }
00548|   }
00549| 
00550|   if (errors.hasAnyErrors() && !isFunctionExpression) {
00551|     return Err(errors);
00552|   }
00553|   return Ok(functionEffects);
00554| }
00555| 
00556| function appendFunctionErrors(errors: CompilerError, fn: HIRFunction): void {
00557|   fo...

<file>
01001|           state.initialize(value, {
01002|             kind: fromKind,
01003|             reason: new Set(fromValue.reason),
01004|           });
01005|           state.define(effect.into, value);
01006|           break;
01007|         }
01008|         default: {
01009|           state.assign(effect.into, effect.from);
01010|           effects.push(effect);
01011|           break;
01012|         }
01013|       }
01014|       break;
01015|     }
01016|     case 'Apply': {
01017|       const functionValues = state.values(effect.function);
01018|       if (
01019|         functionValues.length === 1 &&
01020|         functionValues[0].kind === 'FunctionExpression' &&
01021|         functionValues[0].loweredFunc.func.aliasingEffects != null
01022|       ) {
01023|         /*
01024|          * We're calling a locally declared function, we already know it's effects!
01025|          * We just have to substitute in the args for the params
01026|          */
01027|         const functionExpr = functionValues[0];
01028|         let signature = context.functionSignatureCache.get(functionExpr);
01029|         if (signature == null) {
01030|           signature = buildSignatureFromFunctionExpression(
01031|             state.env,
01032|             functionExpr,
01033|           );
01034|           context.functionSignatureCache.set(functionExpr, signature);
01035|         }
01036|         if (DEBUG) {
01037|           console.log(
01038|             `constructed alias signature:\n${printAliasingSignature(signature)}`,
01039|           );
01040|         }
01041|         const signatureEffects = context.cacheApplySignature(
01042|           signature,
01043|           effect,
01044|           () =>
01045|             computeEffectsForSignature(
01046|               state.env,
01047|               signature,
01048|               effect.into,
01049|               effect.receiver,
01050|               effect.args,
01051|               functionExpr.loweredFunc.func.cont...

<file>
01501|       }
01502|       case 'Mutate':
01503|       case 'MutateTransitive': {
01504|         switch (kind) {
01505|           case ValueKind.Mutable:
01506|           case ValueKind.Context: {
01507|             return 'mutate';
01508|           }
01509|           case ValueKind.Primitive: {
01510|             // technically an error, but it's not React specific
01511|             return 'none';
01512|           }
01513|           case ValueKind.Frozen: {
01514|             return 'mutate-frozen';
01515|           }
01516|           case ValueKind.Global: {
01517|             return 'mutate-global';
01518|           }
01519|           case ValueKind.MaybeFrozen: {
01520|             return 'mutate-frozen';
01521|           }
01522|           default: {
01523|             assertExhaustive(kind, `Unexpected kind ${kind}`);
01524|           }
01525|         }
01526|       }
01527|       default: {
01528|         assertExhaustive(variant, `Unexpected mutation variant ${variant}`);
01529|       }
01530|     }
01531|   }
01532| 
01533|   /*
01534|    * Combine the contents of @param this and @param other, returning a new
01535|    * instance with the combined changes _if_ there are any changes, or
01536|    * returning null if no changes would occur. Changes include:
01537|    * - new entries in @param other that did not exist in @param this
01538|    * - entries whose values differ in @param this and @param other,
01539|    *    and where joining the values produces a different value than
01540|    *    what was in @param this.
01541|    *
01542|    * Note that values are joined using a lattice operation to ensure
01543|    * termination.
01544|    */
01545|   merge(other: InferenceState): InferenceState | null {
01546|     let nextValues: Map<InstructionValue, AbstractValue> | null = null;
01547|     let nextVariables: Map<IdentifierId, Set<InstructionValue>> | null = null;
01548| 
01549|     for (const [id, thisValue] of this.#values) {
01550|       const o...

/home/jm/data/ai/cloudlang-trees/react/lib/scope.ml

<file>
00001| (** Scope analysis for TypeScript ESTree AST.
00002| 
00003|     Two-pass analysis: 1. Declaration pass: collect all module-scope const/let
00004|     bindings, noting which are mutable state (new Map/Set) and which are
00005|     functions. 2. Reference pass: for each arrow function body, collect
00006|     Identifier references that are not locally declared -> these are free
00007|     variables. *)
00008| 
00009| type error = Expected_program_node
00010| 
00011| let error_to_string = function
00012|   | Expected_program_node -> "expected Program node"
00013| 
00014| type var_info = { name : string; is_mutable_state : bool; is_function : bool }
00015| 
00016| type closure_info = {
00017|   name : string;
00018|   free_vars : string list;
00019|   called_functions : string list;
00020|   captures_mutable : string list;
00021| }
00022| 
00023| type analysis_result = {
00024|   closures : closure_info list;
00025|   module_vars : var_info list;
00026|   exports : string list;
00027| }
00028| 
00029| (** Check whether an init expression is [new Map(...)], [new Set(...)], etc. *)
00030| let is_mutable_init = function
00031|   | Ast.NewExpression { callee = Ast.Identifier { name }; _ }
00032|     when name = "Map" || name = "Set" || name = "Array" ->
00033|       true
00034|   | _ -> false
00035| 
00036| (** Check whether an init expression is an arrow function. *)
00037| let is_arrow_init = function
00038|   | Ast.ArrowFunctionExpression _ -> true
00039|   | _ -> false
00040| 
00041| let option_exists predicate = function
00042|   | Some value -> predicate value
00043|   | None -> false
00044| 
00045| (** Extract parameter names from an arrow function's param list. *)
00046| let param_names params =
00047|   List.filter_map
00048|     (function Ast.Identifier { name } -> Some name | _ -> None)
00049|     params
00050| 
00051| (** Collect all identifiers referenced in an expression/statement, excluding
00052|     property names on the right side of member ...

300 /home/jm/data/ai/cloudlang-trees/react/.opencode/context/react-compiler-mutation-aliasing-analysis.md