pkg/analyzer/lib/src/error/dead_code_verifier.dart

// Copyright (c) 2019, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

import 'package:analyzer/dart/analysis/features.dart';
import 'package:analyzer/dart/ast/token.dart';
import 'package:analyzer/dart/ast/visitor.dart';
import 'package:analyzer/dart/element/element.dart';
import 'package:analyzer/source/source_range.dart';
import 'package:analyzer/src/dart/ast/ast.dart';
import 'package:analyzer/src/dart/element/element.dart';
import 'package:analyzer/src/dart/element/type.dart';
import 'package:analyzer/src/dart/element/type_system.dart';
import 'package:analyzer/src/dart/resolver/flow_analysis_visitor.dart';
import 'package:analyzer/src/diagnostic/diagnostic.dart' as diag;
import 'package:analyzer/src/error/codes.dart';
import 'package:analyzer/src/error/listener.dart';

/// State information captured by [NullSafetyDeadCodeVerifier.for_conditionEnd]
/// for later use by [NullSafetyDeadCodeVerifier.for_updaterBegin].
class DeadCodeForPartsState {
  /// Whether a dead interval had started at the time of the call to
  /// [NullSafetyDeadCodeVerifier.for_conditionEnd].
  final bool _hadFirstDeadNode;

  DeadCodeForPartsState._({required bool hadFirstDeadNode})
    : _hadFirstDeadNode = hadFirstDeadNode;
}

/// A visitor that finds dead code, other than unreachable code that is
/// handled in [NullSafetyDeadCodeVerifier].
class DeadCodeVerifier extends RecursiveAstVisitor2<void> {
  /// The diagnostic reporter by which diagnostics will be reported.
  final DiagnosticReporter _diagnosticReporter;

  /// The object used to track the usage of labels within a given label scope.
  _LabelTracker? _labelTracker;

  /// Whether the `wildcard_variables` feature is enabled.
  final bool _wildCardVariablesEnabled;

  DeadCodeVerifier(this._diagnosticReporter, LibraryElement library)
    : _wildCardVariablesEnabled = library.featureSet.isEnabled(
        Feature.wildcard_variables,
      );

  @override
  void visitBreakStatement(BreakStatement node) {
    _labelTracker?.recordUsage(node.label?.name.lexeme);
  }

  @override
  void visitContinueStatement(ContinueStatement node) {
    _labelTracker?.recordUsage(node.label?.name.lexeme);
  }

  @override
  void visitExportDirective(covariant ExportDirectiveImpl node) {
    var libraryExport = node.libraryExport;
    if (libraryExport != null) {
      // The element is null when the URI is invalid.
      var library = libraryExport.exportedLibrary;
      if (library != null && !library.isOriginNotExistingFile) {
        for (Combinator combinator in node.combinators) {
          _checkCombinator(library, combinator);
        }
      }
    }
    super.visitExportDirective(node);
  }

  @override
  void visitFunctionDeclaration(FunctionDeclaration node) {
    var element = node.declaredFragment!.element;
    // TODO(pq): ask the FunctionElement once implemented
    if (_wildCardVariablesEnabled &&
        element is LocalFunctionElement &&
        element.name == '_') {
      _diagnosticReporter.report(diag.deadCode.at(node));
    }
    super.visitFunctionDeclaration(node);
  }

  @override
  void visitImportDirective(covariant ImportDirectiveImpl node) {
    var libraryImport = node.libraryImport;
    if (libraryImport != null) {
      // The element is null when the URI is invalid, but not when the URI is
      // valid but refers to a nonexistent file.
      var library = libraryImport.importedLibrary;
      if (library != null && !library.isOriginNotExistingFile) {
        for (Combinator combinator in node.combinators) {
          _checkCombinator(library, combinator);
        }
      }
    }
    super.visitImportDirective(node);
  }

  @override
  void visitLabeledStatement(LabeledStatement node) {
    _withLabelTracker(node.labels, () {
      super.visitLabeledStatement(node);
    });
  }

  @override
  void visitSwitchStatement(SwitchStatement node) {
    List<Label> labels = <Label>[];
    for (SwitchMember member in node.members) {
      labels.addAll(member.labels);
    }
    _withLabelTracker(labels, () {
      super.visitSwitchStatement(node);
    });
  }

  @override
  void visitVariableDeclaration(VariableDeclaration node) {
    var initializer = node.initializer2;
    if (initializer != null && node.isLate) {
      var element = node.declaredFragment!.element;
      // TODO(pq): ask the LocalVariableElement once implemented
      if (_wildCardVariablesEnabled &&
          element is LocalVariableElement &&
          element.name == '_') {
        _diagnosticReporter.report(
          diag.deadCodeLateWildcardVariableInitializer.at(initializer),
        );
      }
    }

    super.visitVariableDeclaration(node);
  }

  /// Resolve the names in the given [combinator] in the scope of the given
  /// [library].
  void _checkCombinator(LibraryElementImpl library, Combinator combinator) {
    DiagnosticWithArguments<
      LocatableDiagnostic Function({
        required String library,
        required String name,
      })
    >
    warningCode;
    if (combinator is HideCombinator) {
      warningCode = diag.undefinedHiddenName;
    } else {
      warningCode = diag.undefinedShownName;
    }
    for (var name in combinator.names) {
      if (name.element == null && name.setterElement == null) {
        var nameStr = name.name.lexeme;
        _diagnosticReporter.report(
          warningCode
              .withArguments(library: '${library.uri}', name: nameStr)
              .at(name),
        );
      }
    }
  }

  void _withLabelTracker(List<Label> labels, void Function() f) {
    var labelTracker = _LabelTracker(_labelTracker, labels);
    try {
      _labelTracker = labelTracker;
      f();
    } finally {
      for (Label label in labelTracker.unusedLabels()) {
        _diagnosticReporter.report(
          diag.unusedLabel.withArguments(name: label.name.lexeme).at(label),
        );
      }
      _labelTracker = labelTracker.outerTracker;
    }
  }
}

/// Helper for tracking dead code - [CatchClause]s and unreachable code.
///
/// [CatchClause]s are checked separately, as we visit AST we may make some
/// of them as dead, and record [_deadCatchClauseRanges].
///
/// When an unreachable node is found, and [_firstDead] is `null`, we set
/// [_firstDead], so start a new dead nodes interval. The dead code
/// interval ends when [flowEnd] is invoked with a node that is the start
/// node, or contains it. So, we end the end of the covering control flow.
class NullSafetyDeadCodeVerifier {
  final TypeSystemImpl _typeSystem;
  final DiagnosticReporter _diagnosticReporter;
  final FlowAnalysisHelper? _flowAnalysis;

  /// The stack of verifiers of (potentially nested) try statements.
  final List<_CatchClausesVerifier> _catchClausesVerifiers = [];

  /// When a sequence [CatchClause]s is found to be dead, we don't want to
  /// report additional dead code inside of already dead code.
  final List<SourceRange> _deadCatchClauseRanges = [];

  /// When this field is `null`, we are in reachable code. Once we find the
  /// first unreachable node, we store its structural anchor and first token
  /// here.
  ///
  /// When this field is not `null`, and we see an unreachable node, this new
  /// node is ignored, because it continues the same dead code range.
  _DeadCodeStart? _firstDead;

  NullSafetyDeadCodeVerifier(
    this._typeSystem,
    this._diagnosticReporter,
    this._flowAnalysis,
  );

  /// The [node] ends a basic block in the control flow. If [_firstDead] is
  /// not `null`, and is covered by the [node], then we reached the end of
  /// the current dead code interval.
  void flowEnd(AstNode node) {
    // Note that `firstDeadNode` could be a node that will later be replaced
    // in the syntax tree. It's not safe to query whether it is _equal_ to, for
    // example, another node's child.
    // TODO(srawlins): Change this code to avoid this issue.
    var firstDead = _firstDead;
    if (firstDead == null) {
      return;
    }
    var firstDeadNode = firstDead.node;

    if (!_containsFirstDeadNode(node)) {
      return;
    }

    if (node is SwitchMember && node == firstDeadNode) {
      _diagnosticReporter.report(diag.deadCode.at(node.keyword));
      _firstDead = null;
      return;
    }

    var parent = firstDeadNode.parent2;
    if (parent is Assertion && identical(firstDeadNode, parent.message2)) {
      // Don't report "dead code" for the message part of an assert statement,
      // because this causes nuisance warnings for redundant `!= null`
      // asserts.
    } else if (parent is ConstructorDeclaration &&
        firstDeadNode is EmptyFunctionBody) {
      // Don't report "dead code" for an unreachable, but syntacically required,
      // semicolon that follows one or more constructor initializers.
    } else if (parent is ConstructorDeclaration &&
        firstDeadNode is BlockFunctionBody &&
        firstDeadNode.block.statements.isEmpty) {
      // Don't report "dead code" for an unreachable, but empty block body that
      // follows one or more constructor initializers.
    } else {
      var offset = firstDead.firstToken.offset;
      // We know that [node] is the first dead node, or contains it.
      // So, technically the code interval ends at the end of [node].
      // But we trim it to the last statement for presentation purposes.
      if (node != firstDeadNode) {
        if (node is FunctionDeclaration) {
          node = node.functionExpression.body;
        }
        if (node is TopLevelGetterDeclaration) {
          node = node.body;
        }
        if (node is FunctionExpression) {
          node = node.body;
        }
        if (node is MethodDeclaration) {
          node = node.body;
        }
        if (node is BlockFunctionBody) {
          node = node.block;
        }
        if (node is Block && node.statements.isNotEmpty) {
          node = node.statements.last;
        }
        if (node is SwitchMember && node.statements.isNotEmpty) {
          node = node.statements.last;
        }
      } else if (parent is BinaryOperatorInvocation) {
        offset = parent.operator.offset;
      } else if (parent is IfNull) {
        offset = parent.operator.offset;
      }
      if (parent is ConstructorInitializer) {
        _diagnosticReporter.report(
          diag.deadCode.atOffset(
            offset: parent.offset,
            length: parent.end - parent.offset,
          ),
        );
        offset = node.end;
      } else if (parent is DoStatement) {
        var whileOffset = parent.whileKeyword.offset;
        var whileEnd = parent.semicolon.end;
        var body = parent.body;
        if (body is Block) {
          whileOffset = body.rightBracket.offset;
        }
        _diagnosticReporter.report(
          diag.deadCode.atOffset(
            offset: whileOffset,
            length: whileEnd - whileOffset,
          ),
        );
        offset = parent.semicolon.next!.offset;
        if (parent.hasBreakStatement) {
          offset = node.end;
        }
      } else if (parent is ForParts) {
        if (parent.updaters2.lastOrNull case var last?) node = last;
      } else if (parent is BinaryOperatorInvocation) {
        offset = parent.operator.offset;
        node = parent.rightOperand;
      } else if (parent is IfNull) {
        offset = parent.operator.offset;
        node = parent.rightOperand;
      } else if (parent is LogicalAnd) {
        offset = parent.operator.offset;
        node = parent.rightOperand;
      } else if (parent is LogicalOr) {
        offset = parent.operator.offset;
        node = parent.rightOperand;
      } else if (parent is LogicalOrPattern &&
          firstDeadNode == parent.rightOperand) {
        offset = parent.operator.offset;
      } else if (parent is AnonymousMethodInvocation) {
        offset = parent.operator.offset;
      }

      var length = node.end - offset;
      if (length > 0) {
        _diagnosticReporter.report(
          diag.deadCode.atOffset(offset: offset, length: length),
        );
      }
    }

    _firstDead = null;
  }

  /// Performs the necessary dead code analysis when reaching the end of the
  /// `condition` part of [ForParts].
  ///
  /// Some state is returned, which should be passed to [for_updaterBegin] after
  /// visiting the body of the loop.
  DeadCodeForPartsState for_conditionEnd() {
    // Capture the state of this class so that `for_updaterBegin` can use it to
    // decide whether it's necessary to create an extra dead code report for the
    // updaters.
    return DeadCodeForPartsState._(hadFirstDeadNode: _firstDead != null);
  }

  /// Performs the necessary dead code analysis when reaching the beginning of
  /// the `updaters` part of [ForParts].
  ///
  /// [state] should be the state returned by [for_conditionEnd].
  void for_updaterBegin(
    NodeListImpl<ExpressionImpl> updaters,
    DeadCodeForPartsState state,
  ) {
    var isReachable = _flowAnalysis?.flow?.isReachable ?? true;
    if (!isReachable && !state._hadFirstDeadNode) {
      // A dead code range started either at the beginning of the loop body or
      // somewhere inside it, and so the updaters are dead. Since the updaters
      // appear textually before the loop body, they need their own dead code
      // warning.
      var beginToken = updaters.beginToken;
      var endToken = updaters.endToken;
      if (beginToken != null && endToken != null) {
        _diagnosticReporter.report(
          diag.deadCode.atOffset(
            offset: beginToken.offset,
            length: endToken.end - beginToken.offset,
          ),
        );
      }
    }
  }

  /// Rewites the first dead node if it is equal to [oldNode], as [oldNode] is
  /// being rewritten into [newNode] in the syntax tree.
  void maybeRewriteFirstDeadNode(AstNode oldNode, AstNode newNode) {
    if (_firstDead case var firstDead? when firstDead.node == oldNode) {
      firstDead.node = newNode;
    }
  }

  /// Records a dead interval structurally anchored at [node] and beginning at
  /// [firstToken].
  ///
  /// Canonical property nodes store the selected name as a token, so unlike
  /// their V1 projections they have no name child at which dead-code
  /// traversal can begin.
  void recordDeadIntervalAt(AstNode node, Token firstToken) {
    _visitNode(node, firstToken);
  }

  void tryStatementEnter(TryStatement node) {
    var verifier = _CatchClausesVerifier(_typeSystem, (
      first,
      last,
      locatableDiagnostic,
    ) {
      var offset = first.offset;
      var length = last.end - offset;
      _diagnosticReporter.report(
        locatableDiagnostic.atOffset(offset: offset, length: length),
      );
      _deadCatchClauseRanges.add(SourceRange(offset, length));
    }, node.catchClauses);
    _catchClausesVerifiers.add(verifier);
  }

  void tryStatementExit(TryStatement node) {
    _catchClausesVerifiers.removeLast();
  }

  void verifyCascadeExpression(CascadeExpression node) {
    var first = node.sections.firstOrNull;
    var body = first?.body;
    if (body is CascadePropertyExtraction ||
        body is CascadeMethodInvocation ||
        body is CascadeIndexExpression) {
      _verifyUnassignedVariable(node, node.target2, first!.operator);
    }
  }

  void verifyCatchClause(CatchClauseImpl node) {
    var verifier = _catchClausesVerifiers.last;
    if (verifier._done) return;

    verifier.nextCatchClause(node);
  }

  void verifyNullAwareAccess(
    AstNode node,
    Expression receiver,
    Token operator,
  ) {
    _verifyUnassignedVariable(node, receiver, operator);
  }

  void verifyReceiverIndexExpression(ReceiverIndexExpression node) {
    if (node.receiver case Expression receiver) {
      _verifyUnassignedVariable(node, receiver, node.question);
    }
  }

  void visitNode(AstNode node) {
    _visitNode(node, node.beginToken);
  }

  bool _containsFirstDeadNode(AstNode parent) {
    for (var node = _firstDead?.node; node != null; node = node.parent2) {
      if (node == parent) return true;
    }
    return false;
  }

  void _verifyUnassignedVariable(
    AstNode node,
    Expression? target,
    Token? operator,
  ) {
    var flowAnalysis = _flowAnalysis;
    if (flowAnalysis == null) return;

    if (operator == null) return;
    var operatorType = operator.type;
    if (operatorType != TokenType.QUESTION &&
        operatorType != TokenType.QUESTION_PERIOD &&
        operatorType != TokenType.QUESTION_PERIOD_PERIOD) {
      return;
    }
    if (target?.staticType?.nullabilitySuffix != NullabilitySuffix.question) {
      return;
    }

    target = target?.unParenthesized2;
    var element = switch (target) {
      UnqualifiedNameExpression(
        resolution: VariableReadResolution(:var element),
      ) =>
        element,
      _ => null,
    };
    if (target != null && element is PromotableElementImpl) {
      if (flowAnalysis.isDefinitelyUnassigned(target, element)) {
        var parent = node.parent2;
        while (parent is FunctionInvocation ||
            parent is ParsedExpression ||
            parent is PropertyExtraction ||
            parent is IndexExpression2) {
          node = parent!;
          parent = node.parent2;
        }
        _diagnosticReporter.report(
          diag.deadCode.atOffset(
            offset: operator.offset,
            length: node.end - operator.offset,
          ),
        );
      }
    }
  }

  void _visitNode(AstNode node, Token firstToken) {
    // Comments are visited after bodies of functions.
    // So, they look unreachable, but this does not make sense.
    if (node is Comment) return;

    var flowAnalysis = _flowAnalysis;
    if (flowAnalysis == null) return;
    flowAnalysis.checkUnreachableNode(node);

    // If the first dead node is not `null`, even if this new node is
    // unreachable, we can ignore it as it is part of the same dead code
    // range anyway.
    if (_firstDead != null) return;

    var flow = flowAnalysis.flow;
    if (flow == null) return;

    if (flow.isReachable) return;

    // If in a dead `CatchClause`, no need to report dead code.
    for (var range in _deadCatchClauseRanges) {
      if (range.contains(node.offset)) {
        return;
      }
    }

    _firstDead = _DeadCodeStart(node: node, firstToken: firstToken);
  }
}

/// A visitor that finds a [BreakStatement] for a specified [DoStatement].
class _BreakDoStatementVisitor extends RecursiveAstVisitor2<void> {
  bool hasBreakStatement = false;
  final DoStatement doStatement;

  _BreakDoStatementVisitor(this.doStatement);

  @override
  void visitBreakStatement(BreakStatement node) {
    if (node.target == doStatement) {
      hasBreakStatement = true;
    }
  }
}

class _CatchClausesVerifier {
  final TypeSystemImpl _typeSystem;
  final void Function(
    CatchClause first,
    CatchClause last,
    LocatableDiagnostic locatableDiagnostic,
  )
  _reportDiagnostic;
  final List<CatchClause> catchClauses;

  bool _done = false;
  final List<TypeImpl> _visitedTypes = [];

  _CatchClausesVerifier(
    this._typeSystem,
    this._reportDiagnostic,
    this.catchClauses,
  );

  void nextCatchClause(CatchClauseImpl catchClause) {
    var currentType = catchClause.exceptionType?.type;

    // Found catch clause that doesn't have an exception type.
    // Generate a diagnostic on any following catch clauses.
    if (currentType == null || currentType.isDartCoreObject) {
      if (catchClause != catchClauses.last) {
        var index = catchClauses.indexOf(catchClause);
        _reportDiagnostic(
          catchClauses[index + 1],
          catchClauses.last,
          diag.deadCodeCatchFollowingCatch,
        );
        _done = true;
      }
      return;
    }

    // An on-catch clause was found; verify that the exception type is not a
    // subtype of a previous on-catch exception type.
    for (var type in _visitedTypes) {
      if (_typeSystem.isSubtypeOf(currentType, type)) {
        _reportDiagnostic(
          catchClause,
          catchClauses.last,
          diag.deadCodeOnCatchSubtype.withArguments(
            subtype: currentType,
            supertype: type,
          ),
        );
        _done = true;
        return;
      }
    }

    _visitedTypes.add(currentType);
  }
}

/// The structural and syntactic start of a dead-code interval.
final class _DeadCodeStart {
  AstNode node;
  final Token firstToken;

  _DeadCodeStart({required this.node, required this.firstToken});
}

/// An object used to track the usage of labels within a single label scope.
class _LabelTracker {
  /// The tracker for the outer label scope.
  final _LabelTracker? outerTracker;

  /// The labels whose usage is being tracked.
  final List<Label> labels;

  /// A list of flags corresponding to the list of [labels] indicating whether
  /// the corresponding label has been used.
  late final List<bool> used;

  /// A map from the names of labels to the index of the label in [labels].
  final Map<String, int> labelMap = <String, int>{};

  /// Initialize a newly created label tracker.
  _LabelTracker(this.outerTracker, this.labels) {
    used = List.filled(labels.length, false);
    for (int i = 0; i < labels.length; i++) {
      labelMap[labels[i].name.lexeme] = i;
    }
  }

  /// Record that the label with the given [labelName] has been used.
  void recordUsage(String? labelName) {
    if (labelName != null) {
      var index = labelMap[labelName];
      if (index != null) {
        used[index] = true;
      } else {
        outerTracker?.recordUsage(labelName);
      }
    }
  }

  /// Return the unused labels.
  Iterable<Label> unusedLabels() sync* {
    for (int i = 0; i < labels.length; i++) {
      if (!used[i]) {
        yield labels[i];
      }
    }
  }
}

extension DoStatementExtension on DoStatement {
  bool get hasBreakStatement {
    var visitor = _BreakDoStatementVisitor(this);
    body.visitChildren2(visitor);
    return visitor.hasBreakStatement;
  }
}