InferMutationAliasingEffects.ts

/**
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

import {
  CompilerError,
  Effect,
  ErrorSeverity,
  SourceLocation,
  ValueKind,
} from '..';
import {
  BasicBlock,
  BlockId,
  DeclarationId,
  Environment,
  FunctionExpression,
  HIRFunction,
  Hole,
  IdentifierId,
  Instruction,
  InstructionKind,
  InstructionValue,
  isArrayType,
  isMapType,
  isPrimitiveType,
  isRefOrRefValue,
  isSetType,
  makeIdentifierId,
  Phi,
  Place,
  SpreadPattern,
  ValueReason,
} from '../HIR';
import {
  eachInstructionValueLValue,
  eachInstructionValueOperand,
  eachTerminalOperand,
  eachTerminalSuccessor,
} from '../HIR/visitors';
import {Ok, Result} from '../Utils/Result';
import {
  getArgumentEffect,
  getFunctionCallSignature,
  isKnownMutableEffect,
  mergeValueKinds,
} from './InferReferenceEffects';
import {
  assertExhaustive,
  getOrInsertWith,
  Set_isSuperset,
} from '../Utils/utils';
import {
  printAliasingEffect,
  printAliasingSignature,
  printIdentifier,
  printInstruction,
  printInstructionValue,
  printPlace,
  printSourceLocation,
} from '../HIR/PrintHIR';
import {FunctionSignature} from '../HIR/ObjectShape';
import {getWriteErrorReason} from './InferFunctionEffects';
import prettyFormat from 'pretty-format';
import {createTemporaryPlace} from '../HIR/HIRBuilder';
import {AliasingEffect, AliasingSignature, hashEffect} from './AliasingEffects';

const DEBUG = false;

/**
 * Infers the mutation/aliasing effects for instructions and terminals and annotates
 * them on the HIR, making the effects of builtin instructions/functions as well as
 * user-defined functions explicit. These effects then form the basis for subsequent
 * analysis to determine the mutable range of each value in the program — the set of
 * instructions over which the value is created and mutated — as well as validation
 * against invalid code.
 *
 * At a high level the approach is:
 * - Determine a set of candidate effects based purely on the syntax of the instruction
 *   and the types involved. These candidate effects are cached the first time each
 *   instruction is visited. The idea is to reason about the semantics of the instruction
 *   or function in isolation, separately from how those effects may interact with later
 *   abstract interpretation.
 * - Then we do abstract interpretation over the HIR, iterating until reaching a fixpoint.
 *   This phase tracks the abstract kind of each value (mutable, primitive, frozen, etc)
 *   and the set of values pointed to by each identifier. Each candidate effect is "applied"
 *   to the current abtract state, and effects may be dropped or rewritten accordingly.
 *   For example, a "MutateConditionally <x>" effect may be dropped if x is not a mutable
 *   value. A "Mutate <y>" effect may get converted into a "MutateFrozen <error>" effect
 *   if y is mutable, etc.
 */
export function inferMutationAliasingEffects(
  fn: HIRFunction,
  {isFunctionExpression}: {isFunctionExpression: boolean} = {
    isFunctionExpression: false,
  },
): Result<void, CompilerError> {
  const initialState = InferenceState.empty(fn.env, isFunctionExpression);

  // Map of blocks to the last (merged) incoming state that was processed
  const statesByBlock: Map<BlockId, InferenceState> = new Map();

  for (const ref of fn.context) {
    // TODO: using InstructionValue as a bit of a hack, but it's pragmatic
    const value: InstructionValue = {
      kind: 'ObjectExpression',
      properties: [],
      loc: ref.loc,
    };
    initialState.initialize(value, {
      kind: ValueKind.Context,
      reason: new Set([ValueReason.Other]),
    });
    initialState.define(ref, value);
  }

  const paramKind: AbstractValue = isFunctionExpression
    ? {
        kind: ValueKind.Mutable,
        reason: new Set([ValueReason.Other]),
      }
    : {
        kind: ValueKind.Frozen,
        reason: new Set([ValueReason.ReactiveFunctionArgument]),
      };

  if (fn.fnType === 'Component') {
    CompilerError.invariant(fn.params.length <= 2, {
      reason:
        'Expected React component to have not more than two parameters: one for props and for ref',
      description: null,
      loc: fn.loc,
      suggestions: null,
    });
    const [props, ref] = fn.params;
    if (props != null) {
      inferParam(props, initialState, paramKind);
    }
    if (ref != null) {
      const place = ref.kind === 'Identifier' ? ref : ref.place;
      const value: InstructionValue = {
        kind: 'ObjectExpression',
        properties: [],
        loc: place.loc,
      };
      initialState.initialize(value, {
        kind: ValueKind.Mutable,
        reason: new Set([ValueReason.Other]),
      });
      initialState.define(place, value);
    }
  } else {
    for (const param of fn.params) {
      inferParam(param, initialState, paramKind);
    }
  }

  /*
   * Multiple predecessors may be visited prior to reaching a given successor,
   * so track the list of incoming state for each successor block.
   * These are merged when reaching that block again.
   */
  const queuedStates: Map<BlockId, InferenceState> = new Map();
  function queue(blockId: BlockId, state: InferenceState): void {
    let queuedState = queuedStates.get(blockId);
    if (queuedState != null) {
      // merge the queued states for this block
      state = queuedState.merge(state) ?? queuedState;
      queuedStates.set(blockId, state);
    } else {
      /*
       * this is the first queued state for this block, see whether
       * there are changed relative to the last time it was processed.
       */
      const prevState = statesByBlock.get(blockId);
      const nextState = prevState != null ? prevState.merge(state) : state;
      if (nextState != null) {
        queuedStates.set(blockId, nextState);
      }
    }
  }
  queue(fn.body.entry, initialState);

  const hoistedContextDeclarations = findHoistedContextDeclarations(fn);

  const context = new Context(
    isFunctionExpression,
    fn,
    hoistedContextDeclarations,
  );

  let count = 0;
  while (queuedStates.size !== 0) {
    count++;
    if (count > 1000) {
      console.log(
        'oops infinite loop',
        fn.id,
        typeof fn.loc !== 'symbol' ? fn.loc?.filename : null,
      );
      throw new Error('infinite loop');
    }
    for (const [blockId, block] of fn.body.blocks) {
      const incomingState = queuedStates.get(blockId);
      queuedStates.delete(blockId);
      if (incomingState == null) {
        continue;
      }

      statesByBlock.set(blockId, incomingState);
      const state = incomingState.clone();
      inferBlock(context, state, block);

      for (const nextBlockId of eachTerminalSuccessor(block.terminal)) {
        queue(nextBlockId, state);
      }
    }
  }
  return Ok(undefined);
}

function findHoistedContextDeclarations(
  fn: HIRFunction,
): Map<DeclarationId, Place | null> {
  const hoisted = new Map<DeclarationId, Place | null>();
  function visit(place: Place): void {
    if (
      hoisted.has(place.identifier.declarationId) &&
      hoisted.get(place.identifier.declarationId) == null
    ) {
      // If this is the first load of the value, store the location
      hoisted.set(place.identifier.declarationId, place);
    }
  }
  for (const block of fn.body.blocks.values()) {
    for (const instr of block.instructions) {
      if (instr.value.kind === 'DeclareContext') {
        const kind = instr.value.lvalue.kind;
        if (
          kind == InstructionKind.HoistedConst ||
          kind == InstructionKind.HoistedFunction ||
          kind == InstructionKind.HoistedLet
        ) {
          hoisted.set(instr.value.lvalue.place.identifier.declarationId, null);
        }
      } else {
        for (const operand of eachInstructionValueOperand(instr.value)) {
          visit(operand);
        }
      }
    }
    for (const operand of eachTerminalOperand(block.terminal)) {
      visit(operand);
    }
  }
  return hoisted;
}

class Context {
  internedEffects: Map<string, AliasingEffect> = new Map();
  instructionSignatureCache: Map<Instruction, InstructionSignature> = new Map();
  effectInstructionValueCache: Map<AliasingEffect, InstructionValue> =
    new Map();
  catchHandlers: Map<BlockId, Place> = new Map();
  isFuctionExpression: boolean;
  fn: HIRFunction;
  hoistedContextDeclarations: Map<DeclarationId, Place | null>;

  constructor(
    isFunctionExpression: boolean,
    fn: HIRFunction,
    hoistedContextDeclarations: Map<DeclarationId, Place | null>,
  ) {
    this.isFuctionExpression = isFunctionExpression;
    this.fn = fn;
    this.hoistedContextDeclarations = hoistedContextDeclarations;
  }

  internEffect(effect: AliasingEffect): AliasingEffect {
    const hash = hashEffect(effect);
    let interned = this.internedEffects.get(hash);
    if (interned == null) {
      this.internedEffects.set(hash, effect);
      interned = effect;
    }
    return interned;
  }
}

function inferParam(
  param: Place | SpreadPattern,
  initialState: InferenceState,
  paramKind: AbstractValue,
): void {
  const place = param.kind === 'Identifier' ? param : param.place;
  const value: InstructionValue = {
    kind: 'Primitive',
    loc: place.loc,
    value: undefined,
  };
  initialState.initialize(value, paramKind);
  initialState.define(place, value);
}

function inferBlock(
  context: Context,
  state: InferenceState,
  block: BasicBlock,
): void {
  for (const phi of block.phis) {
    state.inferPhi(phi);
  }

  for (const instr of block.instructions) {
    let instructionSignature = context.instructionSignatureCache.get(instr);
    if (instructionSignature == null) {
      instructionSignature = computeSignatureForInstruction(
        context,
        state.env,
        instr,
      );
      context.instructionSignatureCache.set(instr, instructionSignature);
    }
    const effects = applySignature(context, state, instructionSignature, instr);
    instr.effects = effects;
  }
  const terminal = block.terminal;
  if (terminal.kind === 'try' && terminal.handlerBinding != null) {
    context.catchHandlers.set(terminal.handler, terminal.handlerBinding);
  } else if (terminal.kind === 'maybe-throw') {
    const handlerParam = context.catchHandlers.get(terminal.handler);
    if (handlerParam != null) {
      const effects: Array<AliasingEffect> = [];
      for (const instr of block.instructions) {
        if (
          instr.value.kind === 'CallExpression' ||
          instr.value.kind === 'MethodCall'
        ) {
          /**
           * Many instructions can error, but only calls can throw their result as the error
           * itself. For example, `c = a.b` can throw if `a` is nullish, but the thrown value
           * is an error object synthesized by the JS runtime. Whereas `throwsInput(x)` can
           * throw (effectively) the result of the call.
           *
           * TODO: call applyEffect() instead. This meant that the catch param wasn't inferred
           * as a mutable value, though. See `try-catch-try-value-modified-in-catch-escaping.js`
           * fixture as an example
           */
          state.appendAlias(handlerParam, instr.lvalue);
          const kind = state.kind(instr.lvalue).kind;
          if (kind === ValueKind.Mutable || kind == ValueKind.Context) {
            effects.push({
              kind: 'Alias',
              from: instr.lvalue,
              into: handlerParam,
            });
          }
        }
      }
      terminal.effects = effects.length !== 0 ? effects : null;
    }
  } else if (terminal.kind === 'return') {
    if (!context.isFuctionExpression) {
      terminal.effects = [
        {
          kind: 'Freeze',
          value: terminal.value,
          reason: ValueReason.JsxCaptured,
        },
      ];
    }
  }
}

/**
 * Applies the signature to the given state to determine the precise set of effects
 * that will occur in practice. This takes into account the inferred state of each
 * variable. For example, the signature may have a `ConditionallyMutate x` effect.
 * Here, we check the abstract type of `x` and either record a `Mutate x` if x is mutable
 * or no effect if x is a primitive, global, or frozen.
 *
 * This phase may also emit errors, for example MutateLocal on a frozen value is invalid.
 */
function applySignature(
  context: Context,
  state: InferenceState,
  signature: InstructionSignature,
  instruction: Instruction,
): Array<AliasingEffect> | null {
  const effects: Array<AliasingEffect> = [];
  /**
   * For function instructions, eagerly validate that they aren't mutating
   * a known-frozen value.
   *
   * TODO: make sure we're also validating against global mutations somewhere, but
   * account for this being allowed in effects/event handlers.
   */
  if (
    instruction.value.kind === 'FunctionExpression' ||
    instruction.value.kind === 'ObjectMethod'
  ) {
    const aliasingEffects =
      instruction.value.loweredFunc.func.aliasingEffects ?? [];
    const context = new Set(
      instruction.value.loweredFunc.func.context.map(p => p.identifier.id),
    );
    for (const effect of aliasingEffects) {
      if (effect.kind === 'Mutate' || effect.kind === 'MutateTransitive') {
        if (!context.has(effect.value.identifier.id)) {
          continue;
        }
        const value = state.kind(effect.value);
        switch (value.kind) {
          case ValueKind.Frozen: {
            const reason = getWriteErrorReason({
              kind: value.kind,
              reason: value.reason,
              context: new Set(),
            });
            effects.push({
              kind: 'MutateFrozen',
              place: effect.value,
              error: {
                severity: ErrorSeverity.InvalidReact,
                reason,
                description:
                  effect.value.identifier.name !== null &&
                  effect.value.identifier.name.kind === 'named'
                    ? `Found mutation of \`${effect.value.identifier.name.value}\``
                    : null,
                loc: effect.value.loc,
                suggestions: null,
              },
            });
          }
        }
      }
    }
  }

  /*
   * Track which values we've already aliased once, so that we can switch to
   * appendAlias() for subsequent aliases into the same value
   */
  const aliased = new Set<IdentifierId>();

  if (DEBUG) {
    console.log(printInstruction(instruction));
  }

  for (const effect of signature.effects) {
    applyEffect(context, state, effect, aliased, effects);
  }
  if (DEBUG) {
    console.log(
      prettyFormat(state.debugAbstractValue(state.kind(instruction.lvalue))),
    );
    console.log(
      effects.map(effect => `  ${printAliasingEffect(effect)}`).join('\n'),
    );
  }
  if (
    !(state.isDefined(instruction.lvalue) && state.kind(instruction.lvalue))
  ) {
    CompilerError.invariant(false, {
      reason: `Expected instruction lvalue to be initialized`,
      loc: instruction.loc,
    });
  }
  return effects.length !== 0 ? effects : null;
}

function applyEffect(
  context: Context,
  state: InferenceState,
  _effect: AliasingEffect,
  aliased: Set<IdentifierId>,
  effects: Array<AliasingEffect>,
): void {
  const effect = context.internEffect(_effect);
  if (DEBUG) {
    console.log(printAliasingEffect(effect));
  }
  switch (effect.kind) {
    case 'Freeze': {
      const didFreeze = state.freeze(effect.value, effect.reason);
      if (didFreeze) {
        effects.push(effect);
      }
      break;
    }
    case 'Create': {
      let value = context.effectInstructionValueCache.get(effect);
      if (value == null) {
        value = {
          kind: 'ObjectExpression',
          properties: [],
          loc: effect.into.loc,
        };
        context.effectInstructionValueCache.set(effect, value);
      }
      state.initialize(value, {
        kind: effect.value,
        reason: new Set([effect.reason]),
      });
      state.define(effect.into, value);
      break;
    }
    case 'ImmutableCapture': {
      const kind = state.kind(effect.from).kind;
      switch (kind) {
        case ValueKind.Global:
        case ValueKind.Primitive: {
          // no-op: we don't need to track data flow for copy types
          break;
        }
        default: {
          effects.push(effect);
        }
      }
      break;
    }
    case 'CreateFrom': {
      const fromValue = state.kind(effect.from);
      let value = context.effectInstructionValueCache.get(effect);
      if (value == null) {
        value = {
          kind: 'ObjectExpression',
          properties: [],
          loc: effect.into.loc,
        };
        context.effectInstructionValueCache.set(effect, value);
      }
      state.initialize(value, {
        kind: fromValue.kind,
        reason: new Set(fromValue.reason),
      });
      state.define(effect.into, value);
      switch (fromValue.kind) {
        case ValueKind.Primitive:
        case ValueKind.Global: {
          // no need to track this data flow
          break;
        }
        case ValueKind.Frozen: {
          effects.push({
            kind: 'ImmutableCapture',
            from: effect.from,
            into: effect.into,
          });
          break;
        }
        default: {
          effects.push({
            // OK: recording information flow
            kind: 'CreateFrom', // prev Alias
            from: effect.from,
            into: effect.into,
          });
        }
      }
      break;
    }
    case 'CreateFunction': {
      effects.push(effect);
      /**
       * We consider the function mutable if it has any mutable context variables or
       * any side-effects that need to be tracked if the function is called.
       */
      const hasCaptures = effect.captures.some(capture => {
        switch (state.kind(capture).kind) {
          case ValueKind.Context:
          case ValueKind.Mutable: {
            return true;
          }
          default: {
            return false;
          }
        }
      });
      const hasTrackedSideEffects =
        effect.function.loweredFunc.func.aliasingEffects?.some(
          effect =>
            // TODO; include "render" here?
            effect.kind === 'MutateFrozen' ||
            effect.kind === 'MutateGlobal' ||
            effect.kind === 'Impure',
        );
      // For legacy compatibility
      const capturesRef = effect.function.loweredFunc.func.context.some(
        operand => isRefOrRefValue(operand.identifier),
      );
      const isMutable = hasCaptures || hasTrackedSideEffects || capturesRef;
      for (const operand of effect.function.loweredFunc.func.context) {
        if (operand.effect !== Effect.Capture) {
          continue;
        }
        const kind = state.kind(operand).kind;
        if (
          kind === ValueKind.Primitive ||
          kind == ValueKind.Frozen ||
          kind == ValueKind.Global
        ) {
          operand.effect = Effect.Read;
        }
      }
      state.initialize(effect.function, {
        kind: isMutable ? ValueKind.Mutable : ValueKind.Frozen,
        reason: new Set([]),
      });
      state.define(effect.into, effect.function);
      for (const capture of effect.captures) {
        applyEffect(
          context,
          state,
          {
            kind: 'Capture',
            from: capture,
            into: effect.into,
          },
          aliased,
          effects,
        );
      }
      break;
    }
    case 'Alias':
    case 'Capture': {
      /*
       * Capture describes potential information flow: storing a pointer to one value
       * within another. If the destination is not mutable, or the source value has
       * copy-on-write semantics, then we can prune the effect
       */
      const intoKind = state.kind(effect.into).kind;
      let isMutableDesination: boolean;
      switch (intoKind) {
        case ValueKind.Context:
        case ValueKind.Mutable:
        case ValueKind.MaybeFrozen: {
          isMutableDesination = true;
          break;
        }
        default: {
          isMutableDesination = false;
          break;
        }
      }
      const fromKind = state.kind(effect.from).kind;
      let isMutableReferenceType: boolean;
      switch (fromKind) {
        case ValueKind.Global:
        case ValueKind.Primitive: {
          isMutableReferenceType = false;
          break;
        }
        case ValueKind.Frozen: {
          isMutableReferenceType = false;
          effects.push({
            kind: 'ImmutableCapture',
            from: effect.from,
            into: effect.into,
          });
          break;
        }
        default: {
          isMutableReferenceType = true;
          break;
        }
      }
      if (isMutableDesination && isMutableReferenceType) {
        effects.push(effect);
      }
      break;
    }
    case 'Assign': {
      /*
       * Alias represents potential pointer aliasing. If the type is a global,
       * a primitive (copy-on-write semantics) then we can prune the effect
       */
      const fromValue = state.kind(effect.from);
      const fromKind = fromValue.kind;
      switch (fromKind) {
        case ValueKind.Frozen: {
          effects.push({
            kind: 'ImmutableCapture',
            from: effect.from,
            into: effect.into,
          });
          let value = context.effectInstructionValueCache.get(effect);
          if (value == null) {
            value = {
              kind: 'Primitive',
              value: undefined,
              loc: effect.from.loc,
            };
            context.effectInstructionValueCache.set(effect, value);
          }
          state.initialize(value, {
            kind: fromKind,
            reason: new Set(fromValue.reason),
          });
          state.define(effect.into, value);
          break;
        }
        case ValueKind.Global:
        case ValueKind.Primitive: {
          let value = context.effectInstructionValueCache.get(effect);
          if (value == null) {
            value = {
              kind: 'Primitive',
              value: undefined,
              loc: effect.from.loc,
            };
            context.effectInstructionValueCache.set(effect, value);
          }
          state.initialize(value, {
            kind: fromKind,
            reason: new Set(fromValue.reason),
          });
          state.define(effect.into, value);
          break;
        }
        default: {
          if (aliased.has(effect.into.identifier.id)) {
            state.appendAlias(effect.into, effect.from);
          } else {
            aliased.add(effect.into.identifier.id);
            state.alias(effect.into, effect.from);
          }
          effects.push(effect);
          break;
        }
      }
      break;
    }
    case 'Apply': {
      const functionValues = state.values(effect.function);
      if (
        functionValues.length === 1 &&
        functionValues[0].kind === 'FunctionExpression'
      ) {
        /*
         * We're calling a locally declared function, we already know it's effects!
         * We just have to substitute in the args for the params
         */
        const signature = buildSignatureFromFunctionExpression(
          state.env,
          functionValues[0],
        );
        if (DEBUG) {
          console.log(
            `constructed alias signature:\n${printAliasingSignature(signature)}`,
          );
        }
        const signatureEffects = computeEffectsForSignature(
          state.env,
          signature,
          effect.into,
          effect.receiver,
          effect.args,
          functionValues[0].loweredFunc.func.context,
          effect.loc,
        );
        if (signatureEffects != null) {
          if (DEBUG) {
            console.log('apply function expression effects');
          }
          applyEffect(
            context,
            state,
            {kind: 'MutateTransitiveConditionally', value: effect.function},
            aliased,
            effects,
          );
          for (const signatureEffect of signatureEffects) {
            applyEffect(context, state, signatureEffect, aliased, effects);
          }
          break;
        }
      }
      const signatureEffects =
        effect.signature?.aliasing != null
          ? computeEffectsForSignature(
              state.env,
              effect.signature.aliasing,
              effect.into,
              effect.receiver,
              effect.args,
              [],
              effect.loc,
            )
          : null;
      if (signatureEffects != null) {
        if (DEBUG) {
          console.log('apply aliasing signature effects');
        }
        for (const signatureEffect of signatureEffects) {
          applyEffect(context, state, signatureEffect, aliased, effects);
        }
      } else if (effect.signature != null) {
        if (DEBUG) {
          console.log('apply legacy signature effects');
        }
        const legacyEffects = computeEffectsForLegacySignature(
          state,
          effect.signature,
          effect.into,
          effect.receiver,
          effect.args,
          effect.loc,
        );
        for (const legacyEffect of legacyEffects) {
          applyEffect(context, state, legacyEffect, aliased, effects);
        }
      } else {
        if (DEBUG) {
          console.log('default effects');
        }
        applyEffect(
          context,
          state,
          {
            kind: 'Create',
            into: effect.into,
            value: ValueKind.Mutable,
            reason: ValueReason.Other,
          },
          aliased,
          effects,
        );
        /*
         * If no signature then by default:
         * - All operands are conditionally mutated, except some instruction
         *   variants are assumed to not mutate the callee (such as `new`)
         * - All operands are captured into (but not directly aliased as)
         *   every other argument.
         */
        for (const arg of [effect.receiver, effect.function, ...effect.args]) {
          if (arg.kind === 'Hole') {
            continue;
          }
          const operand = arg.kind === 'Identifier' ? arg : arg.place;
          if (operand !== effect.function || effect.mutatesFunction) {
            applyEffect(
              context,
              state,
              {
                kind: 'MutateTransitiveConditionally',
                value: operand,
              },
              aliased,
              effects,
            );
          }
          const mutateIterator =
            arg.kind === 'Spread' ? conditionallyMutateIterator(operand) : null;
          if (mutateIterator) {
            applyEffect(context, state, mutateIterator, aliased, effects);
          }
          applyEffect(
            context,
            state,
            // OK: recording information flow
            {kind: 'Alias', from: operand, into: effect.into},
            aliased,
            effects,
          );
          for (const otherArg of [
            effect.receiver,
            effect.function,
            ...effect.args,
          ]) {
            if (otherArg.kind === 'Hole') {
              continue;
            }
            const other =
              otherArg.kind === 'Identifier' ? otherArg : otherArg.place;
            if (other === arg) {
              continue;
            }
            applyEffect(
              context,
              state,
              {
                /*
                 * OK: a function might store one operand into another,
                 * but it can't force one to alias another
                 */
                kind: 'Capture',
                from: operand,
                into: other,
              },
              aliased,
              effects,
            );
          }
        }
      }
      break;
    }
    case 'Mutate':
    case 'MutateConditionally':
    case 'MutateTransitive':
    case 'MutateTransitiveConditionally': {
      const mutationKind = state.mutate(effect.kind, effect.value);
      if (mutationKind === 'mutate') {
        effects.push(effect);
      } else if (mutationKind === 'mutate-ref') {
        // no-op
      } else if (
        mutationKind !== 'none' &&
        (effect.kind === 'Mutate' || effect.kind === 'MutateTransitive')
      ) {
        const value = state.kind(effect.value);
        if (DEBUG) {
          console.log(`invalid mutation: ${printAliasingEffect(effect)}`);
          console.log(prettyFormat(state.debugAbstractValue(value)));
        }

        if (
          mutationKind === 'mutate-frozen' &&
          context.hoistedContextDeclarations.has(
            effect.value.identifier.declarationId,
          )
        ) {
          const description =
            effect.value.identifier.name !== null &&
            effect.value.identifier.name.kind === 'named'
              ? `Variable \`${effect.value.identifier.name.value}\` is accessed before it is declared`
              : null;
          const hoistedAccess = context.hoistedContextDeclarations.get(
            effect.value.identifier.declarationId,
          );
          if (hoistedAccess != null && hoistedAccess.loc != effect.value.loc) {
            effects.push({
              kind: 'MutateFrozen',
              place: effect.value,
              error: {
                severity: ErrorSeverity.InvalidReact,
                reason: `This variable is accessed before it is declared, which may prevent it from updating as the assigned value changes over time`,
                description,
                loc: hoistedAccess.loc,
                suggestions: null,
              },
            });
          }

          effects.push({
            kind: 'MutateFrozen',
            place: effect.value,
            error: {
              severity: ErrorSeverity.InvalidReact,
              reason: `This variable is accessed before it is declared, which prevents the earlier access from updating when this value changes over time`,
              description,
              loc: effect.value.loc,
              suggestions: null,
            },
          });
        } else {
          const reason = getWriteErrorReason({
            kind: value.kind,
            reason: value.reason,
            context: new Set(),
          });
          const description =
            effect.value.identifier.name !== null &&
            effect.value.identifier.name.kind === 'named'
              ? `Found mutation of \`${effect.value.identifier.name.value}\``
              : null;
          effects.push({
            kind:
              value.kind === ValueKind.Frozen ? 'MutateFrozen' : 'MutateGlobal',
            place: effect.value,
            error: {
              severity: ErrorSeverity.InvalidReact,
              reason,
              description,
              loc: effect.value.loc,
              suggestions: null,
            },
          });
        }
      }
      break;
    }
    case 'Impure':
    case 'Render':
    case 'MutateFrozen':
    case 'MutateGlobal': {
      effects.push(effect);
      break;
    }
    default: {
      assertExhaustive(
        effect,
        `Unexpected effect kind '${(effect as any).kind as any}'`,
      );
    }
  }
}

class InferenceState {
  env: Environment;
  #isFunctionExpression: boolean;

  // The kind of each value, based on its allocation site
  #values: Map<InstructionValue, AbstractValue>;
  /*
   * The set of values pointed to by each identifier. This is a set
   * to accomodate phi points (where a variable may have different
   * values from different control flow paths).
   */
  #variables: Map<IdentifierId, Set<InstructionValue>>;

  constructor(
    env: Environment,
    isFunctionExpression: boolean,
    values: Map<InstructionValue, AbstractValue>,
    variables: Map<IdentifierId, Set<InstructionValue>>,
  ) {
    this.env = env;
    this.#isFunctionExpression = isFunctionExpression;
    this.#values = values;
    this.#variables = variables;
  }

  static empty(
    env: Environment,
    isFunctionExpression: boolean,
  ): InferenceState {
    return new InferenceState(env, isFunctionExpression, new Map(), new Map());
  }

  get isFunctionExpression(): boolean {
    return this.#isFunctionExpression;
  }

  // (Re)initializes a @param value with its default @param kind.
  initialize(value: InstructionValue, kind: AbstractValue): void {
    CompilerError.invariant(value.kind !== 'LoadLocal', {
      reason:
        '[InferMutationAliasingEffects] Expected all top-level identifiers to be defined as variables, not values',
      description: null,
      loc: value.loc,
      suggestions: null,
    });
    this.#values.set(value, kind);
  }

  values(place: Place): Array<InstructionValue> {
    const values = this.#variables.get(place.identifier.id);
    CompilerError.invariant(values != null, {
      reason: `[InferMutationAliasingEffects] Expected value kind to be initialized`,
      description: `${printPlace(place)}`,
      loc: place.loc,
      suggestions: null,
    });
    return Array.from(values);
  }

  // Lookup the kind of the given @param value.
  kind(place: Place): AbstractValue {
    const values = this.#variables.get(place.identifier.id);
    CompilerError.invariant(values != null, {
      reason: `[InferMutationAliasingEffects] Expected value kind to be initialized`,
      description: `${printPlace(place)}`,
      loc: place.loc,
      suggestions: null,
    });
    let mergedKind: AbstractValue | null = null;
    for (const value of values) {
      const kind = this.#values.get(value)!;
      mergedKind =
        mergedKind !== null ? mergeAbstractValues(mergedKind, kind) : kind;
    }
    CompilerError.invariant(mergedKind !== null, {
      reason: `[InferMutationAliasingEffects] Expected at least one value`,
      description: `No value found at \`${printPlace(place)}\``,
      loc: place.loc,
      suggestions: null,
    });
    return mergedKind;
  }

  // Updates the value at @param place to point to the same value as @param value.
  alias(place: Place, value: Place): void {
    const values = this.#variables.get(value.identifier.id);
    CompilerError.invariant(values != null, {
      reason: `[InferMutationAliasingEffects] Expected value for identifier to be initialized`,
      description: `${printIdentifier(value.identifier)}`,
      loc: value.loc,
      suggestions: null,
    });
    this.#variables.set(place.identifier.id, new Set(values));
  }

  appendAlias(place: Place, value: Place): void {
    const values = this.#variables.get(value.identifier.id);
    CompilerError.invariant(values != null, {
      reason: `[InferMutationAliasingEffects] Expected value for identifier to be initialized`,
      description: `${printIdentifier(value.identifier)}`,
      loc: value.loc,
      suggestions: null,
    });
    const prevValues = this.values(place);
    this.#variables.set(
      place.identifier.id,
      new Set([...prevValues, ...values]),
    );
  }

  // Defines (initializing or updating) a variable with a specific kind of value.
  define(place: Place, value: InstructionValue): void {
    CompilerError.invariant(this.#values.has(value), {
      reason: `[InferMutationAliasingEffects] Expected value to be initialized at '${printSourceLocation(
        value.loc,
      )}'`,
      description: printInstructionValue(value),
      loc: value.loc,
      suggestions: null,
    });
    this.#variables.set(place.identifier.id, new Set([value]));
  }

  isDefined(place: Place): boolean {
    return this.#variables.has(place.identifier.id);
  }

  /**
   * Marks @param place as transitively frozen. Returns true if the value was not
   * already frozen, false if the value is already frozen (or already known immutable).
   */
  freeze(place: Place, reason: ValueReason): boolean {
    const value = this.kind(place);
    switch (value.kind) {
      case ValueKind.Context:
      case ValueKind.Mutable:
      case ValueKind.MaybeFrozen: {
        const values = this.values(place);
        for (const instrValue of values) {
          this.freezeValue(instrValue, reason);
        }
        return true;
      }
      case ValueKind.Frozen:
      case ValueKind.Global:
      case ValueKind.Primitive: {
        return false;
      }
      default: {
        assertExhaustive(
          value.kind,
          `Unexpected value kind '${(value as any).kind}'`,
        );
      }
    }
  }

  freezeValue(value: InstructionValue, reason: ValueReason): void {
    this.#values.set(value, {
      kind: ValueKind.Frozen,
      reason: new Set([reason]),
    });
    if (DEBUG) {
      console.log(`freeze value: ${printInstructionValue(value)} ${reason}`);
    }
    if (
      value.kind === 'FunctionExpression' &&
      (this.env.config.enablePreserveExistingMemoizationGuarantees ||
        this.env.config.enableTransitivelyFreezeFunctionExpressions)
    ) {
      for (const place of value.loweredFunc.func.context) {
        this.freeze(place, reason);
      }
    }
  }

  mutate(
    variant:
      | 'Mutate'
      | 'MutateConditionally'
      | 'MutateTransitive'
      | 'MutateTransitiveConditionally',
    place: Place,
  ): 'none' | 'mutate' | 'mutate-frozen' | 'mutate-global' | 'mutate-ref' {
    if (isRefOrRefValue(place.identifier)) {
      return 'mutate-ref';
    }
    const kind = this.kind(place).kind;
    switch (variant) {
      case 'MutateConditionally':
      case 'MutateTransitiveConditionally': {
        switch (kind) {
          case ValueKind.Mutable:
          case ValueKind.Context: {
            return 'mutate';
          }
          default: {
            return 'none';
          }
        }
      }
      case 'Mutate':
      case 'MutateTransitive': {
        switch (kind) {
          case ValueKind.Mutable:
          case ValueKind.Context: {
            return 'mutate';
          }
          case ValueKind.Primitive: {
            // technically an error, but it's not React specific
            return 'none';
          }
          case ValueKind.Frozen: {
            return 'mutate-frozen';
          }
          case ValueKind.Global: {
            return 'mutate-global';
          }
          case ValueKind.MaybeFrozen: {
            return 'none';
          }
          default: {
            assertExhaustive(kind, `Unexpected kind ${kind}`);
          }
        }
      }
      default: {
        assertExhaustive(variant, `Unexpected mutation variant ${variant}`);
      }
    }
  }

  /*
   * Combine the contents of @param this and @param other, returning a new
   * instance with the combined changes _if_ there are any changes, or
   * returning null if no changes would occur. Changes include:
   * - new entries in @param other that did not exist in @param this
   * - entries whose values differ in @param this and @param other,
   *    and where joining the values produces a different value than
   *    what was in @param this.
   *
   * Note that values are joined using a lattice operation to ensure
   * termination.
   */
  merge(other: InferenceState): InferenceState | null {
    let nextValues: Map<InstructionValue, AbstractValue> | null = null;
    let nextVariables: Map<IdentifierId, Set<InstructionValue>> | null = null;

    for (const [id, thisValue] of this.#values) {
      const otherValue = other.#values.get(id);
      if (otherValue !== undefined) {
        const mergedValue = mergeAbstractValues(thisValue, otherValue);
        if (mergedValue !== thisValue) {
          nextValues = nextValues ?? new Map(this.#values);
          nextValues.set(id, mergedValue);
        }
      }
    }
    for (const [id, otherValue] of other.#values) {
      if (this.#values.has(id)) {
        // merged above
        continue;
      }
      nextValues = nextValues ?? new Map(this.#values);
      nextValues.set(id, otherValue);
    }

    for (const [id, thisValues] of this.#variables) {
      const otherValues = other.#variables.get(id);
      if (otherValues !== undefined) {
        let mergedValues: Set<InstructionValue> | null = null;
        for (const otherValue of otherValues) {
          if (!thisValues.has(otherValue)) {
            mergedValues = mergedValues ?? new Set(thisValues);
            mergedValues.add(otherValue);
          }
        }
        if (mergedValues !== null) {
          nextVariables = nextVariables ?? new Map(this.#variables);
          nextVariables.set(id, mergedValues);
        }
      }
    }
    for (const [id, otherValues] of other.#variables) {
      if (this.#variables.has(id)) {
        continue;
      }
      nextVariables = nextVariables ?? new Map(this.#variables);
      nextVariables.set(id, new Set(otherValues));
    }

    if (nextVariables === null && nextValues === null) {
      return null;
    } else {
      return new InferenceState(
        this.env,
        this.#isFunctionExpression,
        nextValues ?? new Map(this.#values),
        nextVariables ?? new Map(this.#variables),
      );
    }
  }

  /*
   * Returns a copy of this state.
   * TODO: consider using persistent data structures to make
   * clone cheaper.
   */
  clone(): InferenceState {
    return new InferenceState(
      this.env,
      this.#isFunctionExpression,
      new Map(this.#values),
      new Map(this.#variables),
    );
  }

  /*
   * For debugging purposes, dumps the state to a plain
   * object so that it can printed as JSON.
   */
  debug(): any {
    const result: any = {values: {}, variables: {}};
    const objects: Map<InstructionValue, number> = new Map();
    function identify(value: InstructionValue): number {
      let id = objects.get(value);
      if (id == null) {
        id = objects.size;
        objects.set(value, id);
      }
      return id;
    }
    for (const [value, kind] of this.#values) {
      const id = identify(value);
      result.values[id] = {
        abstract: this.debugAbstractValue(kind),
        value: printInstructionValue(value),
      };
    }
    for (const [variable, values] of this.#variables) {
      result.variables[`$${variable}`] = [...values].map(identify);
    }
    return result;
  }

  debugAbstractValue(value: AbstractValue): any {
    return {
      kind: value.kind,
      reason: [...value.reason],
    };
  }

  inferPhi(phi: Phi): void {
    const values: Set<InstructionValue> = new Set();
    for (const [_, operand] of phi.operands) {
      const operandValues = this.#variables.get(operand.identifier.id);
      // This is a backedge that will be handled later by State.merge
      if (operandValues === undefined) continue;
      for (const v of operandValues) {
        values.add(v);
      }
    }

    if (values.size > 0) {
      this.#variables.set(phi.place.identifier.id, values);
    }
  }
}

/**
 * Returns a value that represents the combined states of the two input values.
 * If the two values are semantically equivalent, it returns the first argument.
 */
function mergeAbstractValues(
  a: AbstractValue,
  b: AbstractValue,
): AbstractValue {
  const kind = mergeValueKinds(a.kind, b.kind);
  if (
    kind === a.kind &&
    kind === b.kind &&
    Set_isSuperset(a.reason, b.reason)
  ) {
    return a;
  }
  const reason = new Set(a.reason);
  for (const r of b.reason) {
    reason.add(r);
  }
  return {kind, reason};
}

type InstructionSignature = {
  effects: ReadonlyArray<AliasingEffect>;
};

function conditionallyMutateIterator(place: Place): AliasingEffect | null {
  if (
    !(
      isArrayType(place.identifier) ||
      isSetType(place.identifier) ||
      isMapType(place.identifier)
    )
  ) {
    return {
      kind: 'MutateTransitiveConditionally',
      value: place,
    };
  }
  return null;
}

/**
 * Computes an effect signature for the instruction _without_ looking at the inference state,
 * and only using the semantics of the instructions and the inferred types. The idea is to make
 * it easy to check that the semantics of each instruction are preserved by describing only the
 * effects and not making decisions based on the inference state.
 *
 * Then in applySignature(), above, we refine this signature based on the inference state.
 *
 * NOTE: this function is designed to be cached so it's only computed once upon first visiting
 * an instruction.
 */
function computeSignatureForInstruction(
  context: Context,
  env: Environment,
  instr: Instruction,
): InstructionSignature {
  const {lvalue, value} = instr;
  const effects: Array<AliasingEffect> = [];
  switch (value.kind) {
    case 'ArrayExpression': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Mutable,
        reason: ValueReason.Other,
      });
      // All elements are captured into part of the output value
      for (const element of value.elements) {
        if (element.kind === 'Identifier') {
          effects.push({
            kind: 'Capture',
            from: element,
            into: lvalue,
          });
        } else if (element.kind === 'Spread') {
          const mutateIterator = conditionallyMutateIterator(element.place);
          if (mutateIterator != null) {
            effects.push(mutateIterator);
          }
          effects.push({
            kind: 'Capture',
            from: element.place,
            into: lvalue,
          });
        } else {
          continue;
        }
      }
      break;
    }
    case 'ObjectExpression': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Mutable,
        reason: ValueReason.Other,
      });
      for (const property of value.properties) {
        if (property.kind === 'ObjectProperty') {
          effects.push({
            kind: 'Capture',
            from: property.place,
            into: lvalue,
          });
        } else {
          effects.push({
            kind: 'Capture',
            from: property.place,
            into: lvalue,
          });
        }
      }
      break;
    }
    case 'Await': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Mutable,
        reason: ValueReason.Other,
      });
      // Potentially mutates the receiver (awaiting it changes its state and can run side effects)
      effects.push({kind: 'MutateTransitiveConditionally', value: value.value});
      /**
       * Data from the promise may be returned into the result, but await does not directly return
       * the promise itself
       */
      effects.push({
        kind: 'Capture',
        from: value.value,
        into: lvalue,
      });
      break;
    }
    case 'NewExpression':
    case 'CallExpression':
    case 'MethodCall': {
      let callee;
      let receiver;
      let mutatesCallee;
      if (value.kind === 'NewExpression') {
        callee = value.callee;
        receiver = value.callee;
        mutatesCallee = false;
      } else if (value.kind === 'CallExpression') {
        callee = value.callee;
        receiver = value.callee;
        mutatesCallee = true;
      } else if (value.kind === 'MethodCall') {
        callee = value.property;
        receiver = value.receiver;
        mutatesCallee = false;
      } else {
        assertExhaustive(
          value,
          `Unexpected value kind '${(value as any).kind}'`,
        );
      }
      const signature = getFunctionCallSignature(env, callee.identifier.type);
      effects.push({
        kind: 'Apply',
        receiver,
        function: callee,
        mutatesFunction: mutatesCallee,
        args: value.args,
        into: lvalue,
        signature,
        loc: value.loc,
      });
      break;
    }
    case 'PropertyDelete':
    case 'ComputedDelete': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      // Mutates the object by removing the property, no aliasing
      effects.push({kind: 'Mutate', value: value.object});
      break;
    }
    case 'PropertyLoad':
    case 'ComputedLoad': {
      if (isPrimitiveType(lvalue.identifier)) {
        effects.push({
          kind: 'Create',
          into: lvalue,
          value: ValueKind.Primitive,
          reason: ValueReason.Other,
        });
      } else {
        effects.push({
          kind: 'CreateFrom',
          from: value.object,
          into: lvalue,
        });
      }
      break;
    }
    case 'PropertyStore':
    case 'ComputedStore': {
      effects.push({kind: 'Mutate', value: value.object});
      effects.push({
        kind: 'Capture',
        from: value.value,
        into: value.object,
      });
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      break;
    }
    case 'ObjectMethod':
    case 'FunctionExpression': {
      /**
       * We've already analyzed the function expression in AnalyzeFunctions. There, we assign
       * a Capture effect to any context variable that appears (locally) to be aliased and/or
       * mutated. The precise effects are annotated on the function expression's aliasingEffects
       * property, but we don't want to execute those effects yet. We can only use those when
       * we know exactly how the function is invoked — via an Apply effect from a custom signature.
       *
       * But in the general case, functions can be passed around and possibly called in ways where
       * we don't know how to interpret their precise effects. For example:
       *
       * ```
       * const a = {};
       *
       * // We don't want to consider a as mutating here, this just declares the function
       * const f = () => { maybeMutate(a) };
       *
       * // We don't want to consider a as mutating here either, it can't possibly call f yet
       * const x = [f];
       *
       * // Here we have to assume that f can be called (transitively), and have to consider a
       * // as mutating
       * callAllFunctionInArray(x);
       * ```
       *
       * So for any context variables that were inferred as captured or mutated, we record a
       * Capture effect. If the resulting function is transitively mutated, this will mean
       * that those operands are also considered mutated. If the function is never called,
       * they won't be!
       *
       * This relies on the rule that:
       * Capture a -> b and MutateTransitive(b) => Mutate(a)
       *
       * Substituting:
       * Capture contextvar -> function and MutateTransitive(function) => Mutate(contextvar)
       *
       * Note that if the type of the context variables are frozen, global, or primitive, the
       * Capture will either get pruned or downgraded to an ImmutableCapture.
       */
      effects.push({
        kind: 'CreateFunction',
        into: lvalue,
        function: value,
        captures: value.loweredFunc.func.context.filter(
          operand => operand.effect === Effect.Capture,
        ),
      });
      break;
    }
    case 'GetIterator': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Mutable,
        reason: ValueReason.Other,
      });
      if (
        isArrayType(value.collection.identifier) ||
        isMapType(value.collection.identifier) ||
        isSetType(value.collection.identifier)
      ) {
        /*
         * Builtin collections are known to return a fresh iterator on each call,
         * so the iterator does not alias the collection
         */
        effects.push({
          kind: 'Capture',
          from: value.collection,
          into: lvalue,
        });
      } else {
        /*
         * Otherwise, the object may return itself as the iterator, so we have to
         * assume that the result directly aliases the collection. Further, the
         * method to get the iterator could potentially mutate the collection
         */
        effects.push({kind: 'Alias', from: value.collection, into: lvalue});
        effects.push({
          kind: 'MutateTransitiveConditionally',
          value: value.collection,
        });
      }
      break;
    }
    case 'IteratorNext': {
      /*
       * Technically advancing an iterator will always mutate it (for any reasonable implementation)
       * But because we create an alias from the collection to the iterator if we don't know the type,
       * then it's possible the iterator is aliased to a frozen value and we wouldn't want to error.
       * so we mark this as conditional mutation to allow iterating frozen values.
       */
      effects.push({kind: 'MutateConditionally', value: value.iterator});
      // Extracts part of the original collection into the result
      effects.push({
        kind: 'CreateFrom',
        from: value.collection,
        into: lvalue,
      });
      break;
    }
    case 'NextPropertyOf': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      break;
    }
    case 'JsxExpression':
    case 'JsxFragment': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Frozen,
        reason: ValueReason.JsxCaptured,
      });
      for (const operand of eachInstructionValueOperand(value)) {
        effects.push({
          kind: 'Freeze',
          value: operand,
          reason: ValueReason.JsxCaptured,
        });
        effects.push({
          kind: 'Capture',
          from: operand,
          into: lvalue,
        });
      }
      if (value.kind === 'JsxExpression') {
        if (value.tag.kind === 'Identifier') {
          // Tags are render function, by definition they're called during render
          effects.push({
            kind: 'Render',
            place: value.tag,
          });
        }
        if (value.children != null) {
          // Children are typically called during render, not used as an event/effect callback
          for (const child of value.children) {
            effects.push({
              kind: 'Render',
              place: child,
            });
          }
        }
      }
      break;
    }
    case 'DeclareLocal': {
      // TODO check this
      effects.push({
        kind: 'Create',
        into: value.lvalue.place,
        // TODO: what kind here???
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      effects.push({
        kind: 'Create',
        into: lvalue,
        // TODO: what kind here???
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      break;
    }
    case 'Destructure': {
      for (const patternLValue of eachInstructionValueLValue(value)) {
        if (isPrimitiveType(patternLValue.identifier)) {
          effects.push({
            kind: 'Create',
            into: patternLValue,
            value: ValueKind.Primitive,
            reason: ValueReason.Other,
          });
        } else {
          effects.push({
            kind: 'CreateFrom',
            from: value.value,
            into: patternLValue,
          });
        }
      }
      effects.push({kind: 'Assign', from: value.value, into: lvalue});
      break;
    }
    case 'LoadContext': {
      /*
       * Context variables are like mutable boxes. Loading from one
       * is equivalent to a PropertyLoad from the box, so we model it
       * with the same effect we use there (CreateFrom)
       */
      effects.push({kind: 'CreateFrom', from: value.place, into: lvalue});
      break;
    }
    case 'DeclareContext': {
      // Context variables are conceptually like mutable boxes
      const kind = value.lvalue.kind;
      if (
        !context.hoistedContextDeclarations.has(
          value.lvalue.place.identifier.declarationId,
        ) ||
        kind === InstructionKind.HoistedConst ||
        kind === InstructionKind.HoistedFunction ||
        kind === InstructionKind.HoistedLet
      ) {
        /**
         * If this context variable is not hoisted, or this is the declaration doing the hoisting,
         * then we create the box.
         */
        effects.push({
          kind: 'Create',
          into: value.lvalue.place,
          value: ValueKind.Mutable,
          reason: ValueReason.Other,
        });
      } else {
        /**
         * Otherwise this may be a "declare", but there was a previous DeclareContext that
         * hoisted this variable, and we're mutating it here.
         */
        effects.push({kind: 'Mutate', value: value.lvalue.place});
      }
      effects.push({
        kind: 'Create',
        into: lvalue,
        // The result can't be referenced so this value doesn't matter
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      break;
    }
    case 'StoreContext': {
      /*
       * Context variables are like mutable boxes, so semantically
       * we're either creating (let/const) or mutating (reassign) a box,
       * and then capturing the value into it.
       */
      if (
        value.lvalue.kind === InstructionKind.Reassign ||
        context.hoistedContextDeclarations.has(
          value.lvalue.place.identifier.declarationId,
        )
      ) {
        effects.push({kind: 'Mutate', value: value.lvalue.place});
      } else {
        effects.push({
          kind: 'Create',
          into: value.lvalue.place,
          value: ValueKind.Mutable,
          reason: ValueReason.Other,
        });
      }
      effects.push({
        kind: 'Capture',
        from: value.value,
        into: value.lvalue.place,
      });
      effects.push({kind: 'Assign', from: value.value, into: lvalue});
      break;
    }
    case 'LoadLocal': {
      effects.push({kind: 'Assign', from: value.place, into: lvalue});
      break;
    }
    case 'StoreLocal': {
      effects.push({
        kind: 'Assign',
        from: value.value,
        into: value.lvalue.place,
      });
      effects.push({kind: 'Assign', from: value.value, into: lvalue});
      break;
    }
    case 'PostfixUpdate':
    case 'PrefixUpdate': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      effects.push({
        kind: 'Create',
        into: value.lvalue,
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      break;
    }
    case 'StoreGlobal': {
      effects.push({
        kind: 'MutateGlobal',
        place: value.value,
        error: {
          reason:
            'Unexpected reassignment of a variable which was defined outside of the component. Components and hooks should be pure and side-effect free, but variable reassignment is a form of side-effect. If this variable is used in rendering, use useState instead. (https://react.dev/reference/rules/components-and-hooks-must-be-pure#side-effects-must-run-outside-of-render)',
          loc: instr.loc,
          suggestions: null,
          severity: ErrorSeverity.InvalidReact,
        },
      });
      effects.push({kind: 'Assign', from: value.value, into: lvalue});
      break;
    }
    case 'TypeCastExpression': {
      effects.push({kind: 'Assign', from: value.value, into: lvalue});
      break;
    }
    case 'LoadGlobal': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Global,
        reason: ValueReason.Global,
      });
      break;
    }
    case 'StartMemoize':
    case 'FinishMemoize': {
      if (env.config.enablePreserveExistingMemoizationGuarantees) {
        for (const operand of eachInstructionValueOperand(value)) {
          effects.push({
            kind: 'Freeze',
            value: operand,
            reason: ValueReason.Other,
          });
        }
      }
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      break;
    }
    case 'TaggedTemplateExpression':
    case 'BinaryExpression':
    case 'Debugger':
    case 'JSXText':
    case 'MetaProperty':
    case 'Primitive':
    case 'RegExpLiteral':
    case 'TemplateLiteral':
    case 'UnaryExpression':
    case 'UnsupportedNode': {
      effects.push({
        kind: 'Create',
        into: lvalue,
        value: ValueKind.Primitive,
        reason: ValueReason.Other,
      });
      break;
    }
  }
  return {
    effects,
  };
}

/**
 * Creates a set of aliasing effects given a legacy FunctionSignature. This makes all of the
 * old implicit behaviors from the signatures and InferReferenceEffects explicit, see comments
 * in the body for details.
 *
 * The goal of this method is to make it easier to migrate incrementally to the new system,
 * so we don't have to immediately write new signatures for all the methods to get expected
 * compilation output.
 */
function computeEffectsForLegacySignature(
  state: InferenceState,
  signature: FunctionSignature,
  lvalue: Place,
  receiver: Place,
  args: Array<Place | SpreadPattern | Hole>,
  loc: SourceLocation,
): Array<AliasingEffect> {
  const returnValueReason = signature.returnValueReason ?? ValueReason.Other;
  const effects: Array<AliasingEffect> = [];
  effects.push({
    kind: 'Create',
    into: lvalue,
    value: signature.returnValueKind,
    reason: returnValueReason,
  });
  if (signature.impure && state.env.config.validateNoImpureFunctionsInRender) {
    effects.push({
      kind: 'Impure',
      place: receiver,
      error: {
        reason:
          'Calling an impure function can produce unstable results. (https://react.dev/reference/rules/components-and-hooks-must-be-pure#components-and-hooks-must-be-idempotent)',
        description:
          signature.canonicalName != null
            ? `\`${signature.canonicalName}\` is an impure function whose results may change on every call`
            : null,
        severity: ErrorSeverity.InvalidReact,
        loc,
        suggestions: null,
      },
    });
  }
  const stores: Array<Place> = [];
  const captures: Array<Place> = [];
  function visit(place: Place, effect: Effect): void {
    switch (effect) {
      case Effect.Store: {
        effects.push({
          kind: 'Mutate',
          value: place,
        });
        stores.push(place);
        break;
      }
      case Effect.Capture: {
        captures.push(place);
        break;
      }
      case Effect.ConditionallyMutate: {
        effects.push({
          kind: 'MutateTransitiveConditionally',
          value: place,
        });
        break;
      }
      case Effect.ConditionallyMutateIterator: {
        const mutateIterator = conditionallyMutateIterator(place);
        if (mutateIterator != null) {
          effects.push(mutateIterator);
          // TODO: should we always push to captures?
          captures.push(place);
        }
        effects.push({
          kind: 'Capture',
          from: place,
          into: lvalue,
        });
        break;
      }
      case Effect.Freeze: {
        effects.push({
          kind: 'Freeze',
          value: place,
          reason: returnValueReason,
        });
        break;
      }
      case Effect.Mutate: {
        effects.push({kind: 'MutateTransitive', value: place});
        break;
      }
      case Effect.Read: {
        effects.push({
          kind: 'ImmutableCapture',
          from: place,
          into: lvalue,
        });
        break;
      }
    }
  }

  if (
    signature.mutableOnlyIfOperandsAreMutable &&
    areArgumentsImmutableAndNonMutating(state, args)
  ) {
    effects.push({
      kind: 'Alias',
      from: receiver,
      into: lvalue,
    });
    for (const arg of args) {
      if (arg.kind === 'Hole') {
        continue;
      }
      const place = arg.kind === 'Identifier' ? arg : arg.place;
      effects.push({
        kind: 'ImmutableCapture',
        from: place,
        into: lvalue,
      });
    }
    return effects;
  }

  if (signature.calleeEffect !== Effect.Capture) {
    /*
     * InferReferenceEffects and FunctionSignature have an implicit assumption that the receiver
     * is captured into the return value. Consider for example the signature for Array.proto.pop:
     * the calleeEffect is Store, since it's a known mutation but non-transitive. But the return
     * of the pop() captures from the receiver! This isn't specified explicitly. So we add this
     * here, and rely on applySignature() to downgrade this to ImmutableCapture (or prune) if
     * the type doesn't actually need to be captured based on the input and return type.
     */
    effects.push({
      kind: 'Alias',
      from: receiver,
      into: lvalue,
    });
  }
  visit(receiver, signature.calleeEffect);
  for (let i = 0; i < args.length; i++) {
    const arg = args[i];
    if (arg.kind === 'Hole') {
      continue;
    }
    const place = arg.kind === 'Identifier' ? arg : arg.place;
    const signatureEffect =
      arg.kind === 'Identifier' && i < signature.positionalParams.length
        ? signature.positionalParams[i]!
        : (signature.restParam ?? Effect.ConditionallyMutate);
    const effect = getArgumentEffect(signatureEffect, arg);

    visit(place, effect);
  }
  if (captures.length !== 0) {
    if (stores.length === 0) {
      // If no stores, then capture into the return value
      for (const capture of captures) {
        effects.push({kind: 'Alias', from: capture, into: lvalue});
      }
    } else {
      // Else capture into the stores
      for (const capture of captures) {
        for (const store of stores) {
          effects.push({kind: 'Capture', from: capture, into: store});
        }
      }
    }
  }
  return effects;
}

/**
 * Returns true if all of the arguments are both non-mutable (immutable or frozen)
 * _and_ are not functions which might mutate their arguments. Note that function
 * expressions count as frozen so long as they do not mutate free variables: this
 * function checks that such functions also don't mutate their inputs.
 */
function areArgumentsImmutableAndNonMutating(
  state: InferenceState,
  args: Array<Place | SpreadPattern | Hole>,
): boolean {
  for (const arg of args) {
    if (arg.kind === 'Hole') {
      continue;
    }
    if (arg.kind === 'Identifier' && arg.identifier.type.kind === 'Function') {
      const fnShape = state.env.getFunctionSignature(arg.identifier.type);
      if (fnShape != null) {
        return (
          !fnShape.positionalParams.some(isKnownMutableEffect) &&
          (fnShape.restParam == null ||
            !isKnownMutableEffect(fnShape.restParam))
        );
      }
    }
    const place = arg.kind === 'Identifier' ? arg : arg.place;

    const kind = state.kind(place).kind;
    switch (kind) {
      case ValueKind.Primitive:
      case ValueKind.Frozen: {
        /*
         * Only immutable values, or frozen lambdas are allowed.
         * A lambda may appear frozen even if it may mutate its inputs,
         * so we have a second check even for frozen value types
         */
        break;
      }
      default: {
        /**
         * Globals, module locals, and other locally defined functions may
         * mutate their arguments.
         */
        return false;
      }
    }
    const values = state.values(place);
    for (const value of values) {
      if (
        value.kind === 'FunctionExpression' &&
        value.loweredFunc.func.params.some(param => {
          const place = param.kind === 'Identifier' ? param : param.place;
          const range = place.identifier.mutableRange;
          return range.end > range.start + 1;
        })
      ) {
        // This is a function which may mutate its inputs
        return false;
      }
    }
  }
  return true;
}

function computeEffectsForSignature(
  env: Environment,
  signature: AliasingSignature,
  lvalue: Place,
  receiver: Place,
  args: Array<Place | SpreadPattern | Hole>,
  // Used for signatures constructed dynamically which reference context variables
  context: Array<Place> = [],
  loc: SourceLocation,
): Array<AliasingEffect> | null {
  if (
    // Not enough args
    signature.params.length > args.length ||
    // Too many args and there is no rest param to hold them
    (args.length > signature.params.length && signature.rest == null)
  ) {
    if (DEBUG) {
      if (signature.params.length > args.length) {
        console.log(
          `not enough args: ${args.length} args for ${signature.params.length} params`,
        );
      } else {
        console.log(
          `too many args: ${args.length} args for ${signature.params.length} params, with no rest param`,
        );
      }
    }
    return null;
  }
  // Build substitutions
  const mutableSpreads = new Set<IdentifierId>();
  const substitutions: Map<IdentifierId, Array<Place>> = new Map();
  substitutions.set(signature.receiver, [receiver]);
  substitutions.set(signature.returns, [lvalue]);
  const params = signature.params;
  for (let i = 0; i < args.length; i++) {
    const arg = args[i];
    if (arg.kind === 'Hole') {
      continue;
    } else if (params == null || i >= params.length || arg.kind === 'Spread') {
      if (signature.rest == null) {
        if (DEBUG) {
          console.log(`no rest value to hold param`);
        }
        return null;
      }
      const place = arg.kind === 'Identifier' ? arg : arg.place;
      getOrInsertWith(substitutions, signature.rest, () => []).push(place);

      if (arg.kind === 'Spread') {
        const mutateIterator = conditionallyMutateIterator(arg.place);
        if (mutateIterator != null) {
          mutableSpreads.add(arg.place.identifier.id);
        }
      }
    } else {
      const param = params[i];
      substitutions.set(param, [arg]);
    }
  }

  /*
   * Signatures constructed dynamically from function expressions will reference values
   * other than their receiver/args/etc. We populate the substitution table with these
   * values so that we can still exit for unpopulated substitutions
   */
  for (const operand of context) {
    substitutions.set(operand.identifier.id, [operand]);
  }

  const effects: Array<AliasingEffect> = [];
  for (const signatureTemporary of signature.temporaries) {
    const temp = createTemporaryPlace(env, receiver.loc);
    substitutions.set(signatureTemporary.identifier.id, [temp]);
  }

  // Apply substitutions
  for (const effect of signature.effects) {
    switch (effect.kind) {
      case 'Assign':
      case 'ImmutableCapture':
      case 'Alias':
      case 'CreateFrom':
      case 'Capture': {
        const from = substitutions.get(effect.from.identifier.id) ?? [];
        const to = substitutions.get(effect.into.identifier.id) ?? [];
        for (const fromId of from) {
          for (const toId of to) {
            effects.push({
              kind: effect.kind,
              from: fromId,
              into: toId,
            });
          }
        }
        break;
      }
      case 'Impure':
      case 'MutateFrozen':
      case 'MutateGlobal': {
        const values = substitutions.get(effect.place.identifier.id) ?? [];
        for (const value of values) {
          effects.push({kind: effect.kind, place: value, error: effect.error});
        }
        break;
      }
      case 'Render': {
        const values = substitutions.get(effect.place.identifier.id) ?? [];
        for (const value of values) {
          effects.push({kind: effect.kind, place: value});
        }
        break;
      }
      case 'Mutate':
      case 'MutateTransitive':
      case 'MutateTransitiveConditionally':
      case 'MutateConditionally': {
        const values = substitutions.get(effect.value.identifier.id) ?? [];
        for (const id of values) {
          effects.push({kind: effect.kind, value: id});
        }
        break;
      }
      case 'Freeze': {
        const values = substitutions.get(effect.value.identifier.id) ?? [];
        for (const value of values) {
          if (mutableSpreads.has(value.identifier.id)) {
            CompilerError.throwTodo({
              reason: 'Support spread syntax for hook arguments',
              loc: value.loc,
            });
          }
          effects.push({kind: 'Freeze', value, reason: effect.reason});
        }
        break;
      }
      case 'Create': {
        const into = substitutions.get(effect.into.identifier.id) ?? [];
        for (const value of into) {
          effects.push({
            kind: 'Create',
            into: value,
            value: effect.value,
            reason: effect.reason,
          });
        }
        break;
      }
      case 'Apply': {
        const applyReceiver = substitutions.get(effect.receiver.identifier.id);
        if (applyReceiver == null || applyReceiver.length !== 1) {
          if (DEBUG) {
            console.log(`too many substitutions for receiver`);
          }
          return null;
        }
        const applyFunction = substitutions.get(effect.function.identifier.id);
        if (applyFunction == null || applyFunction.length !== 1) {
          if (DEBUG) {
            console.log(`too many substitutions for function`);
          }
          return null;
        }
        const applyInto = substitutions.get(effect.into.identifier.id);
        if (applyInto == null || applyInto.length !== 1) {
          if (DEBUG) {
            console.log(`too many substitutions for into`);
          }
          return null;
        }
        const applyArgs: Array<Place | SpreadPattern | Hole> = [];
        for (const arg of effect.args) {
          if (arg.kind === 'Hole') {
            applyArgs.push(arg);
          } else if (arg.kind === 'Identifier') {
            const applyArg = substitutions.get(arg.identifier.id);
            if (applyArg == null || applyArg.length !== 1) {
              if (DEBUG) {
                console.log(`too many substitutions for arg`);
              }
              return null;
            }
            applyArgs.push(applyArg[0]);
          } else {
            const applyArg = substitutions.get(arg.place.identifier.id);
            if (applyArg == null || applyArg.length !== 1) {
              if (DEBUG) {
                console.log(`too many substitutions for arg`);
              }
              return null;
            }
            applyArgs.push({kind: 'Spread', place: applyArg[0]});
          }
        }
        effects.push({
          kind: 'Apply',
          mutatesFunction: effect.mutatesFunction,
          receiver: applyReceiver[0],
          args: applyArgs,
          function: applyFunction[0],
          into: applyInto[0],
          signature: effect.signature,
          loc,
        });
        break;
      }
      case 'CreateFunction': {
        CompilerError.throwTodo({
          reason: `Support CreateFrom effects in signatures`,
          loc: receiver.loc,
        });
      }
      default: {
        assertExhaustive(
          effect,
          `Unexpected effect kind '${(effect as any).kind}'`,
        );
      }
    }
  }
  return effects;
}

function buildSignatureFromFunctionExpression(
  env: Environment,
  fn: FunctionExpression,
): AliasingSignature {
  let rest: IdentifierId | null = null;
  const params: Array<IdentifierId> = [];
  for (const param of fn.loweredFunc.func.params) {
    if (param.kind === 'Identifier') {
      params.push(param.identifier.id);
    } else {
      rest = param.place.identifier.id;
    }
  }
  return {
    receiver: makeIdentifierId(0),
    params,
    rest: rest ?? createTemporaryPlace(env, fn.loc).identifier.id,
    returns: fn.loweredFunc.func.returns.identifier.id,
    effects: fn.loweredFunc.func.aliasingEffects ?? [],
    temporaries: [],
  };
}

export type AbstractValue = {
  kind: ValueKind;
  reason: ReadonlySet<ValueReason>;
};