/**
 * Provides classes for working with a data flow graph-based
 * program representation.
 *
 * We currently consider three kinds of data flow:
 *
 *   1. Flow within an expression, for example from the operands of a `&&`
 *      expression to the expression itself.
 *   2. Flow through local variables, that is, from definitions to uses.
 *      Captured variables are treated flow-insensitively, that is, all
 *      definitions are considered to flow to all uses, while for non-captured
 *      variables only definitions that can actually reach a use are considered.
 *   3. Flow into and out of immediately invoked function expressions, that is,
 *      flow from arguments to parameters, and from returned expressions to the
 *      function expression itself.
 *
 * Flow through global variables, object properties or function calls is not
 * modeled (except for immediately invoked functions as explained above).
 */

import javascript

module DataFlow {
  private cached newtype TNode =
     TValueNode(AST::ValueNode nd)
  or TSsaDefNode(SsaDefinition d)
  or TPropNode(@property p)
  or TRestPatternNode(DestructuringPattern dp, Expr rest) { rest = dp.getRest() }
  or TDestructuringPatternNode(DestructuringPattern dp)
  or TElementPatternNode(ArrayPattern ap, Expr p) { p = ap.getElement(_) }
  or TElementNode(ArrayExpr arr, Expr e) { e = arr.getAnElement() }
  or TReflectiveCallNode(MethodCallExpr ce, string kind) {
       ce.getMethodName() = kind and (kind = "call" or kind = "apply")
     }
  or TThisNode(StmtContainer f) { f.(Function).getThisBinder() = f or f instanceof TopLevel }

  /**
   * A node in the data flow graph.
   */
  class Node extends TNode {
    /**
     * Gets a data flow node from which data may flow to this node in one local step.
     */
    Node getAPredecessor() {
      localFlowStep(result, this)
    }

    /**
     * Gets a data flow node to which data may flow from this node in one local step.
     */
    Node getASuccessor() {
      localFlowStep(this, result)
    }

    /**
     * Gets a source node from which data may flow to this node in zero or more local steps.
     */
    SourceNode getALocalSource() {
      result.flowsTo(this)
    }

    /**
     * Holds if the flow information for this node is incomplete.
     *
     * This predicate holds if there may be a source flow node from which data flows into
     * this node, but that node is not a result of `getALocalSource()` due to analysis
     * incompleteness. The parameter `cause` is bound to a string describing the source of
     * incompleteness.
     *
     * For example, since this analysis is intra-procedural, data flow from actual arguments
     * to formal parameters is not modeled. Hence, if `p` is an access to a parameter,
     * `p.getALocalSource()` does _not_ return the corresponding argument, and
     * `p.isIncomplete("call")` holds.
     */
    predicate isIncomplete(Incompleteness cause) {
      isIncomplete(this, cause)
    }

    /** Gets type inference results for this data flow node. */
    AnalyzedNode analyze() {
      result = this
    }

    /** Gets the expression corresponding to this data flow node, if any. */
    Expr asExpr() { this = TValueNode(result) }

    /** Gets the AST node corresponding to this data flow node, if any. */
    ASTNode getAstNode() { none() }

    /** Gets the basic block to which this node belongs. */
    BasicBlock getBasicBlock() { none() }

    /** Gets the container in which this node occurs. */
    StmtContainer getContainer() { result = getBasicBlock().getContainer() }

    /**
     * Holds if this data flow node accesses the global variable `g`, either directly
     * or through the `window` object.
     */
    predicate accessesGlobal(string g) {
      globalVarRef(g).flowsTo(this)
    }

    /** Holds if this node may evaluate to the string `s`. */
    predicate mayHaveStringValue(string s) {
      getAPredecessor().mayHaveStringValue(s)
    }

    /** Holds if this node may evaluate to the Boolean value `b`. */
    predicate mayHaveBooleanValue(boolean b) {
      b = analyze().getAValue().(AbstractBoolean).getBooleanValue()
    }

    /**
     * Holds if this expression may refer to the initial value of parameter `p`.
     */
    predicate mayReferToParameter(Parameter p) {
      parameterNode(p).(SourceNode).flowsTo(this)
    }

    /**
     * Holds if this element is at the specified location.
     * The location spans column `startcolumn` of line `startline` to
     * column `endcolumn` of line `endline` in file `filepath`.
     * For more information, see
     * [LGTM locations](https://lgtm.com/help/ql/locations).
     */
    predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                              int endline, int endcolumn) {
      filepath = "" and
      startline = 0 and startcolumn = 0 and
      endline = 0 and endcolumn = 0
    }

    /** Gets the file this data flow node comes from. */
    File getFile() {
      hasLocationInfo(result.getAbsolutePath(), _, _, _, _)
    }

    /** Gets the start line of this data flow node. */
    int getStartLine() {
      hasLocationInfo(_, result, _, _, _)
    }

    /** Gets the start column of this data flow node. */
    int getStartColumn() {
      hasLocationInfo(_, _, result, _, _)
    }

    /** Gets the end line of this data flow node. */
    int getEndLine() {
      hasLocationInfo(_, _, _, result, _)
    }

    /** Gets the end column of this data flow node. */
    int getEndColumn() {
      hasLocationInfo(_, _, _, _, result)
    }

    /** Gets a textual representation of this element. */
    string toString() { none() }
  }

  /**
   * An expression or a declaration of a function, class, namespace or enum,
   * viewed as a node in the data flow graph.
   */
  class ValueNode extends Node, TValueNode {
    AST::ValueNode astNode;

    ValueNode() {
      this = TValueNode(astNode)
    }

    /** Gets the expression or declaration this node corresponds to. */
    override AST::ValueNode getAstNode() {
      result = astNode
    }

    override predicate mayHaveStringValue(string s) {
      Node.super.mayHaveStringValue(s) or
      astNode.(ConstantString).getStringValue() = s
    }

    override BasicBlock getBasicBlock() {
      astNode = result.getANode()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      astNode.getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = astNode.toString()
    }
  }

  /**
   * A node in the data flow graph which corresponds to an SSA variable definition.
   */
  class SsaDefinitionNode extends Node, TSsaDefNode {
    SsaDefinition ssa;

    SsaDefinitionNode() { this = TSsaDefNode(ssa) }

    /** Gets the SSA variable defined at this data flow node. */
    SsaVariable getSsaVariable() {
      result = ssa.getVariable()
    }

    override BasicBlock getBasicBlock() {
      result = ssa.getBasicBlock()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      ssa.hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = ssa.getSourceVariable().getName()
    }

    override ASTNode getAstNode() {
      none()
    }
  }

  /**
   * A node in the data flow graph which corresponds to a `@property`.
   */
  private class PropNode extends Node, TPropNode {
    @property prop;

    PropNode() { this = TPropNode(prop) }

    override BasicBlock getBasicBlock() {
      result = prop.(ControlFlowNode).getBasicBlock()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      prop.(Locatable).getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = prop.(ASTNode).toString()
    }

    override ASTNode getAstNode() {
      result = prop
    }
  }

  /**
   * A node in the data flow graph which corresponds to the rest pattern of a
   * destructuring pattern.
   */
  private class RestPatternNode extends Node, TRestPatternNode {
    DestructuringPattern pattern;
    Expr rest;

    RestPatternNode() { this = TRestPatternNode(pattern, rest) }

    override BasicBlock getBasicBlock() {
      result = rest.getBasicBlock()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      rest.getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = "..." + rest.toString()
    }

    override ASTNode getAstNode() {
      result = rest
    }
  }

  /**
   * A node in the data flow graph which corresponds to the value destructured by an
   * object or array pattern.
   */
  private class DestructuringPatternNode extends Node, TDestructuringPatternNode {
    DestructuringPattern pattern;

    DestructuringPatternNode() { this = TDestructuringPatternNode(pattern) }

    override BasicBlock getBasicBlock() {
      result = pattern.getBasicBlock()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      pattern.getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = pattern.toString()
    }

    override ASTNode getAstNode() {
      result = pattern
    }
  }

  /**
   * A node in the data flow graph which corresponds to an element pattern of an
   * array pattern.
   */
  private class ElementPatternNode extends Node, TElementPatternNode {
    ArrayPattern pattern;
    Expr elt;

    ElementPatternNode() { this = TElementPatternNode(pattern, elt) }

    override BasicBlock getBasicBlock() {
      result = elt.getBasicBlock()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      elt.getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = elt.toString()
    }

    override ASTNode getAstNode() {
      result = elt
    }
  }

  /**
   * A node in the data flow graph which represents the (implicit) write of an element
   * in an array expression to the underlying array.
   *
   * That is, for an array expression `["first", ,"third"]`, we have two array element nodes,
   * one representing the write of expression `"first"` into the 0th element of the array,
   * and one representing the write of `"third"` into its second element.
   */
  private class ElementNode extends Node, TElementNode {
    ArrayExpr arr;
    Expr elt;

    ElementNode() {
      this = TElementNode(arr, elt)
    }

    override BasicBlock getBasicBlock() {
      result = elt.getBasicBlock()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      elt.getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = elt.toString()
    }

    override ASTNode getAstNode() {
      result = elt
    }
  }

  /**
   * A node in the data flow graph which corresponds to the reflective call performed
   * by a `.call` or `.apply` invocation.
   */
  private class ReflectiveCallNode extends Node, TReflectiveCallNode {
    MethodCallExpr call;
    string kind;

    ReflectiveCallNode() { this = TReflectiveCallNode(call, kind) }

    override BasicBlock getBasicBlock() {
      result = call.getBasicBlock()
    }

    override predicate hasLocationInfo(string filepath, int startline, int startcolumn,
                                       int endline, int endcolumn) {
      call.getLocation().hasLocationInfo(filepath, startline, startcolumn, endline, endcolumn)
    }

    override string toString() {
      result = "reflective call"
    }
  }

  /**
   * A data flow node that reads or writes an object property or class member.
   *
   * The default subclasses do not model global variable references or variable
   * references inside `with` statements as property references.
   */
  abstract class PropRef extends Node {
    /**
     * Gets the data flow node corresponding to the base object
     * whose property is read from or written to.
     */
    abstract Node getBase();

    /**
     * Gets the expression specifying the name of the property being
     * read or written, if any.
     *
     * This is usually either an identifier or a literal.
     */
    abstract Expr getPropertyNameExpr();

    /**
     * Gets the name of the property being read or written,
     * if it can be statically determined.
     *
     * By default, this predicate is undefined for dynamic property references
     * such as `e[computePropertyName()]` and for spread/rest properties.
     */
    abstract string getPropertyName();

    /**
     * Holds if this data flow node accesses property `p` on base node `base`.
     */
    pragma[noinline]
    predicate accesses(Node base, string p) {
      getBase() = base and getPropertyName() = p
    }
  }

  /**
   * A data flow node that writes to an object property.
   */
  abstract class PropWrite extends PropRef {
    /**
     * Gets the data flow node corresponding to the value being written,
     * if it can be statically determined.
     *
     * This predicate is undefined for spread properties, accessor
     * properties, and most uses of `Object.defineProperty`.
     */
    abstract Node getRhs();

    /**
     * Holds if this data flow node writes the value of `rhs` to property
     * `prop` of the object that `base` evaluates to.
     */
    pragma[noinline]
    predicate writes(DataFlow::Node base, string prop, DataFlow::Node rhs) {
      base = getBase() and
      prop = getPropertyName() and
      rhs = getRhs()
    }
  }

  /**
   * A property access in lvalue position, viewed as a property definition node.
   */
  private class PropLValueAsPropWrite extends PropWrite, ValueNode {
    override PropAccess astNode;

    PropLValueAsPropWrite() { astNode instanceof LValue }

    override Node getBase() {
      result = valueNode(astNode.getBase())
    }

    override Expr getPropertyNameExpr() {
      result = astNode.getPropertyNameExpr()
    }

    override string getPropertyName() {
      result = astNode.getPropertyName()
    }

    override Node getRhs() {
      result = valueNode(astNode.(LValue).getRhs())
    }
  }

  /**
   * A property of an object literal, viewed as a data flow node that writes
   * to the corresponding property.
   */
  private class PropInitAsPropWrite extends PropWrite, PropNode {
    override Property prop;

    override Node getBase() {
      result = valueNode(prop.getObjectExpr())
    }

    override Expr getPropertyNameExpr() {
      result = prop.getNameExpr()
    }

    override string getPropertyName() {
      result = prop.getName()
    }

    override Node getRhs() {
      result = valueNode(prop.(ValueProperty).getInit())
    }
  }

  /**
   * A call to `Object.defineProperty`, viewed as a data flow node that
   * writes to the corresponding property.
   */
  private class ObjectDefinePropertyAsPropWrite extends PropWrite, ValueNode {
    CallToObjectDefineProperty odp;

    ObjectDefinePropertyAsPropWrite() { odp = this }

    override Node getBase() {
      result = odp.getBaseObject()
    }

    override Expr getPropertyNameExpr() {
      result = odp.getArgument(1).asExpr()
    }

    override string getPropertyName() {
      result = odp.getPropertyName()
    }

    override Node getRhs() {
      exists (ObjectLiteralNode propdesc |
        propdesc.flowsTo(odp.getPropertyDescriptor()) and
        propdesc.hasPropertyWrite("value", result)
      )
    }
  }

  /**
   * A static member definition, viewed as a data flow node that adds
   * a property to the class.
   */
  private class ClassMemberAsPropWrite extends PropWrite, PropNode {
    override MemberDefinition prop;

    override Node getBase() {
      prop.isStatic() and
      result = valueNode(prop.getDeclaringClass())
    }

    override Expr getPropertyNameExpr() {
      result = prop.getNameExpr()
    }

    override string getPropertyName() {
      result = prop.getName()
    }

    override Node getRhs() {
      not prop instanceof AccessorMethodDefinition and
      result = valueNode(prop.getInit())
    }
  }

  /**
   * A JSX attribute definition, viewed as a data flow node that writes properties to
   * the JSX element it is in.
   */
  private class JsxAttributeAsPropWrite extends PropWrite, PropNode {
    override JSXAttribute prop;

    override Node getBase() {
      result = valueNode(prop.getElement())
    }

    override Expr getPropertyNameExpr() {
      result = prop.getNameExpr()
    }

    override string getPropertyName() {
      result = prop.getName()
    }

    override Node getRhs() {
      result = valueNode(prop.getValue())
    }
  }

  /**
   * A data flow node that reads an object property.
   */
  abstract class PropRead extends PropRef, SourceNode {
  }

  /**
   * A property access in rvalue position.
   */
  private class PropRValueAsPropRead extends PropRead, ValueNode {
    override PropAccess astNode;

    PropRValueAsPropRead() { astNode instanceof RValue }

    override Node getBase() {
      result = valueNode(astNode.getBase())
    }

    override Expr getPropertyNameExpr() {
      result = astNode.getPropertyNameExpr()
    }

    override string getPropertyName() {
      result = astNode.getPropertyName()
    }
  }

  /**
   * A property pattern viewed as a property read; for instance, in
   * `var { p: q } = o`, `p` is a read of property `p` of `o`.
   */
  private class PropPatternAsPropRead extends PropRead, PropNode {
    override PropertyPattern prop;

    /** Gets the value pattern of this property pattern. */
    Expr getValuePattern() {
      result = prop.getValuePattern()
    }

    override Node getBase() {
      result = TDestructuringPatternNode(prop.getObjectPattern())
    }

    override Expr getPropertyNameExpr() {
      result = prop.getNameExpr()
    }

    override string getPropertyName() {
      result = prop.getName()
    }
  }

  /**
   * A rest pattern viewed as a property read; for instance, in
   * `var { ...ps } = o`, `ps` is a read of all properties of `o`, and similar
   * for `[ ...elts ] = arr`.
   */
  private class RestPatternAsPropRead extends PropRead, RestPatternNode {
    override Node getBase() {
      result = TDestructuringPatternNode(pattern)
    }

    override Expr getPropertyNameExpr() { none() }

    override string getPropertyName() { none() }
  }

  /**
   * An array element pattern viewed as a property read; for instance, in
   * `var [ x, y ] = arr`, `x` is a read of property 0 of `arr` and similar
   * for `y`.
   *
   * Note: We currently do not expose the array index as the property name,
   * instead treating it as a read of an unknown property.
   */
  private class ElementPatternAsPropRead extends PropRead, ElementPatternNode {
    override Node getBase() {
      result = TDestructuringPatternNode(pattern)
    }

    override Expr getPropertyNameExpr() { none() }

    override string getPropertyName() { none() }
  }

  /**
   * Provides classes representing various kinds of calls.
   *
   * Subclass the classes in this module to introduce new kinds of calls. If you want to
   * refine the behaviour of the analysis on existing kinds of calls, subclass `InvokeNode`
   * instead.
   */
  module Impl {
    /**
     * A data flow node representing a function invocation, either explicitly or reflectively,
     * and either with or without `new`.
     */
    abstract class InvokeNodeDef extends DataFlow::Node {
      /** Gets the name of the function or method being invoked, if it can be determined. */
      abstract string getCalleeName();

      /** Gets the data flow node specifying the function to be called. */
      abstract DataFlow::Node getCalleeNode();

      /** Gets the data flow node corresponding to the `i`th argument of this invocation. */
      abstract DataFlow::Node getArgument(int i);

      /** Gets the data flow node corresponding to an argument of this invocation. */
      abstract DataFlow::Node getAnArgument();

      /** Gets the number of arguments of this invocation, if it can be determined. */
      abstract int getNumArgument();
    }

    /**
     * A data flow node representing a function call without `new`, either explicitly or
     * reflectively.
     */
    abstract class CallNodeDef extends InvokeNodeDef {
      /** Gets the data flow node corresponding to the receiver of this call, if any. */
      DataFlow::Node getReceiver() { none() }
    }

    /**
     * A data flow node representing a method call.
     */
    abstract class MethodCallNodeDef extends CallNodeDef {
      /** Gets the name of the method being invoked, if it can be determined. */
      abstract string getMethodName();
    }

    /**
     * A data flow node representing a function invocation with `new`.
     */
    abstract class NewNodeDef extends InvokeNodeDef {
    }

    /**
     * A data flow node representing an explicit (that is, non-reflective) function invocation.
     */
    class ExplicitInvokeNode extends InvokeNodeDef, DataFlow::ValueNode {
      override InvokeExpr astNode;

      override string getCalleeName() {
        result = astNode.getCalleeName()
      }

      override DataFlow::Node getCalleeNode() {
        result = DataFlow::valueNode(astNode.getCallee())
      }

      override DataFlow::Node getArgument(int i) {
        not astNode.isSpreadArgument([0..i]) and result = DataFlow::valueNode(astNode.getArgument(i))
      }

      override DataFlow::Node getAnArgument() {
        exists (Expr arg | arg = astNode.getAnArgument() |
          not arg instanceof SpreadElement and
          result = DataFlow::valueNode(arg)
        )
      }

      override int getNumArgument() {
        not astNode.isSpreadArgument(_) and result = astNode.getNumArgument()
      }
    }

    /**
     * A data flow node representing an explicit (that is, non-reflective) function call.
     */
    private class ExplicitCallNode extends CallNodeDef, ExplicitInvokeNode {
      override CallExpr astNode;
    }

    /**
     * A data flow node representing an explicit (that is, non-reflective) method call.
     */
    private class ExplicitMethodCallNode extends MethodCallNodeDef, ExplicitCallNode {
      override MethodCallExpr astNode;
      override DataFlow::Node getReceiver() { result = DataFlow::valueNode(astNode.getReceiver()) }
      override string getMethodName() { result = astNode.getMethodName() }
    }

    /**
     * A data flow node representing a `new` expression.
     */
    private class ExplicitNewNode extends NewNodeDef, ExplicitInvokeNode {
      override NewExpr astNode;
    }

    /**
     * A data flow node representing a reflective function call.
     */
    private class ReflectiveCallNodeDef extends CallNodeDef {
      ExplicitMethodCallNode originalCall;
      string kind;

      ReflectiveCallNodeDef() {
        this = TReflectiveCallNode(originalCall.asExpr(), kind)
      }

      override string getCalleeName() { none() }

      override DataFlow::Node getCalleeNode() {
        result = originalCall.getReceiver()
      }

      override DataFlow::Node getReceiver() {
        result = originalCall.getArgument(0)
      }

      override DataFlow::Node getArgument(int i) {
        i >= 0 and kind = "call" and result = originalCall.getArgument(i+1)
      }

      override DataFlow::Node getAnArgument() {
        kind = "call" and result = originalCall.getAnArgument() and result != getReceiver()
      }

      override int getNumArgument() {
        result >= 0 and kind = "call" and result = originalCall.getNumArgument()-1
      }
    }
  }

  /**
   * An array element viewed as a property write; for instance, in
   * `var arr = ["first", , "third"]`, `"first"` is a write of property 0 of `arr`
   * and `"third"` is a write of property 2 of `arr`.
   *
   * Note: We currently do not expose the array index as the property name,
   * instead treating it as a write of an unknown property.
   */
  private class ElementNodeAsPropWrite extends PropWrite, ElementNode {
    override Expr getPropertyNameExpr() {
      none()
    }

    override string getPropertyName() {
      none()
    }

    override Node getRhs() {
      result = valueNode(elt)
    }

    override Node getBase() {
      result = valueNode(arr)
    }
  }

  /**
   * Gets the data flow node corresponding to `nd`.
   *
   * This predicate is only defined for expressions, properties, and for statements that declare
   * a function, a class, or a TypeScript namespace or enum.
   */
  ValueNode valueNode(ASTNode nd) { result.getAstNode() = nd }

  /** Gets the data flow node corresponding to `ssa`. */
  SsaDefinitionNode ssaDefinitionNode(SsaDefinition ssa) {
    result = TSsaDefNode(ssa)
  }

  /** Gets the node corresponding to the initialization of parameter `p`. */
  ParameterNode parameterNode(Parameter p) {
    result.getParameter() = p
  }

  /**
   * INTERNAL: Use `parameterNode(Parameter)` instead.
   */
  predicate parameterNode(DataFlow::Node nd, Parameter p) {
    exists (SsaExplicitDefinition ssa |
      nd = ssaDefinitionNode(ssa) and
      p = ssa.getDef() and
      p instanceof SimpleParameter
    )
    or
    nd = TDestructuringPatternNode(p)
  }

  /**
   * INTERNAL: Use `thisNode(StmtContainer container)` instead.
   */
  predicate thisNode(DataFlow::Node node, StmtContainer container) {
    node = TThisNode(container)
  }

  /**
   * A classification of flows that are not modeled, or only modeled incompletely, by
   * `DataFlowNode`:
   *
   * - `"await"`: missing flow through promises;
   * - `"call"`: missing inter-procedural data flow;
   * - `"eval"`: missing reflective data flow;
   * - `"global"`: missing ata flow through global variables;
   * - `"heap"`: missing data flow through properties;
   * - `"import"`: missing data flow through module imports;
   * - `"namespace"`: missing data flow through exported namespace members;
   * - `"yield"`: missing data flow through generators.
   */
  class Incompleteness extends string {
    Incompleteness() {
      this = "await" or
      this = "call" or
      this = "eval" or
      this = "global" or
      this = "heap" or
      this = "import" or
      this = "namespace" or
      this = "yield"
    }
  }

  /**
   * Holds if `call` may call `callee`, and this call should be
   * tracked by local data flow.
   */
  private predicate localCall(InvokeExpr call, Function callee) {
    call = callee.(ImmediatelyInvokedFunctionExpr).getInvocation()
  }

  /**
   * Holds if some call passes `arg` as the value of `parm`, and this
   * call should be tracked by local data flow.
   */
  private predicate localArgumentPassing(Expr arg, Parameter parm) {
    any(ImmediatelyInvokedFunctionExpr iife).argumentPassing(parm, arg)
  }

  /**
   * Holds if data can flow from `node1` to `node2` in one local step.
   */
  cached
  predicate localFlowStep(Node pred, Node succ) {
    // flow into local variables
    exists (SsaDefinition ssa | succ = TSsaDefNode(ssa) |
      // from the rhs of an explicit definition into the variable
      exists (SsaExplicitDefinition def | def = ssa |
        pred = defSourceNode(def.getDef(), def.getSourceVariable())
      )
      or
      // from any explicit definition or implicit init of a captured variable into
      // the capturing definition
      exists (SsaSourceVariable v, SsaDefinition predDef |
        v = ssa.(SsaVariableCapture).getSourceVariable() and
        predDef.getSourceVariable() = v and
        pred = TSsaDefNode(predDef) |
        predDef instanceof SsaExplicitDefinition or
        predDef instanceof SsaImplicitInit
      )
      or
      // from the inputs of phi and pi nodes into the node itself
      pred = TSsaDefNode(ssa.(SsaPseudoDefinition).getAnInput().getDefinition())
    )
    or
    // flow out of local variables
    exists (SsaVariable v |
      pred = TSsaDefNode(v.getDefinition()) and
      succ = valueNode(v.getAUse())
    )
    or
    exists (Expr predExpr, Expr succExpr |
      pred = valueNode(predExpr) and succ = valueNode(succExpr) |
      predExpr = succExpr.(ParExpr).getExpression()
      or
      predExpr = succExpr.(SeqExpr).getLastOperand()
      or
      predExpr = succExpr.(LogicalBinaryExpr).getAnOperand()
      or
      predExpr = succExpr.(AssignExpr).getRhs()
      or
      predExpr = succExpr.(ConditionalExpr).getABranch()
      or
      predExpr = succExpr.(TypeAssertion).getExpression()
      or
      predExpr = succExpr.(NonNullAssertion).getExpression()
      or
      predExpr = succExpr.(ExpressionWithTypeArguments).getExpression()
      or
      exists (Function f |
        predExpr = f.getAReturnedExpr() and
        localCall(succExpr, f)
      )
    )
    or
    exists (VarDef def |
      // from `e` to `{ p: x }` in `{ p: x } = e`
      pred = valueNode(defSourceNode(def)) and
      succ = TDestructuringPatternNode(def.getTarget())
    )
    or
    // flow from 'this' parameter into 'this' expressions
    exists (ThisExpr thiz |
      pred = TThisNode(thiz.getBindingContainer()) and
      succ = valueNode(thiz))
  }

  /**
   * Gets the data flow node representing the source of definition `def`, taking
   * flow through IIFE calls into account.
   */
  private AST::ValueNode defSourceNode(VarDef def) {
    result = def.getSource() or localArgumentPassing(result, def)
  }

  /**
   * Gets the data flow node representing the source of the definition of `v` at `def`,
   * if any.
   */
  private Node defSourceNode(VarDef def, SsaSourceVariable v) {
    exists (BindingPattern lhs, VarRef r |
      lhs = def.getTarget() and r = lhs.getABindingVarRef() and r.getVariable() = v |
      // follow one step of the def-use chain if the lhs is a simple variable reference
      lhs = r and
      result = TValueNode(defSourceNode(def))
      or
      // handle destructuring assignments
      exists (PropertyPattern pp | r = pp.getValuePattern() |
        result = TPropNode(pp)
      )
      or
      result = TElementPatternNode(_, r)
    )
  }

  /**
   * Holds if the flow information for this node is incomplete.
   *
   * This predicate holds if there may be a source flow node from which data flows into
   * this node, but that node is not a result of `getALocalSource()` due to analysis incompleteness.
   * The parameter `cause` is bound to a string describing the source of incompleteness.
   *
   * For example, since this analysis is intra-procedural, data flow from actual arguments
   * to formal parameters is not modeled. Hence, if `p` is an access to a parameter,
   * `p.getALocalSource()` does _not_ return the corresponding argument, and
   * `p.isIncomplete("call")` holds.
   */
  predicate isIncomplete(Node nd, Incompleteness cause) {
    exists (SsaVariable ssa | nd = TSsaDefNode(ssa.getDefinition()) |
      defIsIncomplete(ssa.(SsaExplicitDefinition).getDef(), cause)
      or
      exists (Variable v | v = ssa.getSourceVariable() |
        v.isNamespaceExport() and cause = "namespace" or
        any(DirectEval e).mayAffect(v) and cause = "eval"
      )
    )
    or
    exists (GlobalVarAccess va |
      nd = valueNode((VarUse)va) and
      cause = "global"
    )
    or
    exists (Expr e | e = nd.asExpr() and cause = "call" |
      e instanceof InvokeExpr and
      not localCall(e, _)
      or
      e instanceof ThisExpr or e instanceof SuperExpr
      or
      e instanceof NewTargetExpr
      or
      e instanceof FunctionBindExpr
      or
      e instanceof TaggedTemplateExpr
    )
    or
    nd.asExpr() instanceof ExternalModuleReference and
    cause = "import"
    or
    nd.asExpr() instanceof PropAccess and
    cause = "heap"
    or
    exists (Expr e | e = nd.asExpr() |
      (e instanceof YieldExpr or e instanceof FunctionSentExpr) and
      cause = "yield"
      or
      (e instanceof AwaitExpr or e instanceof DynamicImportExpr) and
      cause = "await"
    )
  }

  /**
   * Holds if definition `def` cannot be completely analyzed due to `cause`.
   */
  private predicate defIsIncomplete(VarDef def, Incompleteness cause) {
    def instanceof Parameter and
    not localArgumentPassing(_, def) and
    cause = "call"
    or
    def instanceof ImportSpecifier and
    cause = "import"
    or
    exists (EnhancedForLoop efl | def = efl.getIteratorExpr()) and
    cause = "heap"
    or
    exists (ComprehensionBlock cb | def = cb.getIterator()) and
    cause = "yield"
    or
    def.getTarget() instanceof DestructuringPattern and
    cause = "heap"
  }

  import Nodes
  import Sources
  import TypeInference
  import Configuration
  import TrackedNodes
}
