in packages/pyright-internal/src/analyzer/codeFlowEngine.ts [325:1007]
function getTypeFromFlowNode(
flowNode: FlowNode,
reference: CodeFlowReferenceExpressionNode | undefined,
targetSymbolId: number | undefined,
initialType: Type | undefined,
isInitialTypeIncomplete: boolean
): FlowNodeTypeResult {
let curFlowNode = flowNode;
let usedOuterScopeAlias = false;
// Record how many times this function has been called.
const codeFlowInvocationsAtStart = codeFlowInvocations;
codeFlowInvocations++;
// This is a frequently-called routine, so it's a good place to call
// the cancellation check. If the operation is canceled, an exception
// will be thrown at this point.
evaluator.checkForCancellation();
while (true) {
// Have we already been here? If so, use the cached value.
const cachedEntry = getCacheEntry(curFlowNode, usedOuterScopeAlias);
if (cachedEntry) {
if (!cachedEntry.isIncomplete) {
return cachedEntry;
}
// If the cached entry is incomplete, we can use it only if nothing
// has changed that may cause the previously-reported incomplete type to change.
if (cachedEntry.generationCount === flowIncompleteGeneration) {
return {
type: cachedEntry?.type ? removeUnknownFromUnion(cachedEntry.type) : undefined,
usedOuterScopeAlias,
isIncomplete: true,
};
}
}
if (curFlowNode.flags & FlowFlags.Unreachable) {
// We can get here if there are nodes in a compound logical expression
// (e.g. "False and x") that are never executed but are evaluated.
// The type doesn't matter in this case.
return setCacheEntry(curFlowNode, undefined, usedOuterScopeAlias, /* isIncomplete */ false);
}
if (curFlowNode.flags & FlowFlags.VariableAnnotation) {
const varAnnotationNode = curFlowNode as FlowVariableAnnotation;
curFlowNode = varAnnotationNode.antecedent;
continue;
}
if (curFlowNode.flags & FlowFlags.Call) {
const callFlowNode = curFlowNode as FlowCall;
// If this function returns a "NoReturn" type, that means
// it always raises an exception or otherwise doesn't return,
// so we can assume that the code before this is unreachable.
if (isCallNoReturn(callFlowNode.node)) {
return setCacheEntry(curFlowNode, undefined, usedOuterScopeAlias, /* isIncomplete */ false);
}
curFlowNode = callFlowNode.antecedent;
continue;
}
if (curFlowNode.flags & FlowFlags.Assignment) {
const assignmentFlowNode = curFlowNode as FlowAssignment;
// Are we targeting the same symbol? We need to do this extra check because the same
// symbol name might refer to different symbols in different scopes (e.g. a list
// comprehension introduces a new scope).
if (reference) {
if (
targetSymbolId === assignmentFlowNode.targetSymbolId &&
isMatchingExpression(reference, assignmentFlowNode.node)
) {
// Is this a special "unbind" assignment? If so,
// we can handle it immediately without any further evaluation.
if (curFlowNode.flags & FlowFlags.Unbind) {
return setCacheEntry(
curFlowNode,
UnboundType.create(),
usedOuterScopeAlias,
/* isIncomplete */ false
);
}
// If there was a cache entry already, that means we hit a recursive
// case (something like "int: int = 4"). Avoid infinite recursion
// by returning an undefined type.
if (cachedEntry && cachedEntry.type === undefined) {
return { type: undefined, usedOuterScopeAlias, isIncomplete: true };
}
// Set the cache entry to undefined before evaluating the
// expression in case it depends on itself.
setCacheEntry(
curFlowNode,
reference ? undefined : initialType,
usedOuterScopeAlias,
/* isIncomplete */ true
);
let flowTypeResult = evaluateAssignmentFlowNode(assignmentFlowNode);
if (flowTypeResult) {
if (isTypeAliasPlaceholder(flowTypeResult.type)) {
flowTypeResult = undefined;
} else if (
reference.nodeType === ParseNodeType.MemberAccess &&
evaluator.isAsymmetricDescriptorAssignment(assignmentFlowNode.node)
) {
flowTypeResult = undefined;
}
}
return setCacheEntry(
curFlowNode,
flowTypeResult?.type,
usedOuterScopeAlias,
!!flowTypeResult?.isIncomplete
);
} else if (isPartialMatchingExpression(reference, assignmentFlowNode.node)) {
// If the node partially matches the reference, we need to "kill" any narrowed
// types further above this point. For example, if we see the sequence
// a.b = 3
// a = Foo()
// x = a.b
// The type of "a.b" can no longer be assumed to be Literal[3].
return {
type: initialType,
usedOuterScopeAlias,
isIncomplete: isInitialTypeIncomplete,
};
}
}
curFlowNode = assignmentFlowNode.antecedent;
continue;
}
if (curFlowNode.flags & FlowFlags.AssignmentAlias) {
const aliasFlowNode = curFlowNode as FlowAssignmentAlias;
// If the target symbol ID matches, replace with its alias
// and continue to traverse the code flow graph.
if (targetSymbolId === aliasFlowNode.targetSymbolId) {
targetSymbolId = aliasFlowNode.aliasSymbolId;
usedOuterScopeAlias = true;
}
curFlowNode = aliasFlowNode.antecedent;
continue;
}
if (curFlowNode.flags & FlowFlags.BranchLabel) {
const branchFlowNode = curFlowNode as FlowBranchLabel;
if (curFlowNode.flags & FlowFlags.PostContextManager) {
// Determine whether any of the context managers support exception
// suppression. If not, none of its antecedents are reachable.
const contextMgrNode = curFlowNode as FlowPostContextManagerLabel;
if (
!contextMgrNode.expressions.some((expr) =>
isExceptionContextManager(expr, contextMgrNode.isAsync)
)
) {
return setCacheEntry(
curFlowNode,
undefined,
usedOuterScopeAlias,
/* isIncomplete */ false
);
}
}
// Is the current symbol modified in any way within the scope of the branch?
// If not, we can skip all processing within the branch scope.
if (reference && branchFlowNode.preBranchAntecedent && branchFlowNode.affectedExpressions) {
if (!subexpressionReferenceKeys) {
subexpressionReferenceKeys = createKeysForReferenceSubexpressions(reference);
}
if (
!subexpressionReferenceKeys.some((key) =>
branchFlowNode.affectedExpressions!.has(key)
) &&
isFlowNodeReachable(curFlowNode, branchFlowNode.preBranchAntecedent)
) {
curFlowNode = branchFlowNode.preBranchAntecedent;
continue;
}
}
const labelNode = curFlowNode as FlowLabel;
const typesToCombine: Type[] = [];
let branchUsedOuterScopeAlias = usedOuterScopeAlias;
let sawIncomplete = false;
// Set the cache entry to undefined before evaluating the
// expression in case it depends on itself.
setCacheEntry(
curFlowNode,
reference ? undefined : initialType,
usedOuterScopeAlias,
/* isIncomplete */ true
);
labelNode.antecedents.forEach((antecedent) => {
const flowTypeResult = getTypeFromFlowNode(
antecedent,
reference,
targetSymbolId,
initialType,
isInitialTypeIncomplete
);
if (flowTypeResult.isIncomplete) {
sawIncomplete = true;
}
if (flowTypeResult.usedOuterScopeAlias) {
branchUsedOuterScopeAlias = true;
}
if (flowTypeResult.type) {
typesToCombine.push(flowTypeResult.type);
}
});
const effectiveType =
!!reference || typesToCombine.length > 0 ? combineTypes(typesToCombine) : undefined;
// Limit the number of recursive calls before we give up and call the type
// complete. This can theoretically result in incorrect type information in
// very complex code flows, but it's preferable to extremely long analysis times.
if (codeFlowInvocations - codeFlowInvocationsAtStart > maxCodeFlowInvocationsPerLoop) {
sawIncomplete = false;
}
return setCacheEntry(curFlowNode, effectiveType, branchUsedOuterScopeAlias, sawIncomplete);
}
if (curFlowNode.flags & FlowFlags.LoopLabel) {
const loopNode = curFlowNode as FlowLabel;
// Is the current symbol modified in any way within the loop? If not, we can skip all
// processing within the loop and assume that the type comes from the first antecedent,
// which feeds the loop.
if (reference) {
if (!subexpressionReferenceKeys) {
subexpressionReferenceKeys = createKeysForReferenceSubexpressions(reference);
}
if (!subexpressionReferenceKeys.some((key) => loopNode.affectedExpressions!.has(key))) {
curFlowNode = loopNode.antecedents[0];
continue;
}
}
let sawIncomplete = false;
let loopUsedOuterScopeAlias = usedOuterScopeAlias;
// See if we've been here before. If so, there will be an incomplete cache entry.
let cacheEntry = getCacheEntry(curFlowNode, usedOuterScopeAlias);
let typeAtStart: Type | undefined;
if (cacheEntry === undefined) {
// We haven't been here before, so create a new incomplete cache entry.
cacheEntry = setCacheEntry(
curFlowNode,
reference ? undefined : initialType,
usedOuterScopeAlias,
/* isIncomplete */ true
);
} else {
typeAtStart = cacheEntry.type;
}
const isRecursive =
cacheEntry.incompleteSubtypes !== undefined &&
cacheEntry.incompleteSubtypes.some((subtype) => subtype.isPending);
const visitCount = incrementFlowNodeVisitCount(curFlowNode);
loopNode.antecedents.forEach((antecedent, index) => {
cacheEntry = getCacheEntry(curFlowNode, usedOuterScopeAlias)!;
// Have we already been here (i.e. does the entry exist and is
// not marked "pending")? If so, we can use the type that was already
// computed if it is complete.
const subtypeEntry =
cacheEntry.incompleteSubtypes !== undefined &&
index < cacheEntry.incompleteSubtypes.length
? cacheEntry.incompleteSubtypes[index]
: undefined;
if (
subtypeEntry === undefined ||
(!subtypeEntry?.isPending && subtypeEntry?.isIncomplete)
) {
// Set this entry to "pending" to prevent infinite recursion.
// We'll mark it "not pending" below.
cacheEntry = setIncompleteSubtype(
curFlowNode,
index,
subtypeEntry?.type ?? (reference ? undefined : initialType),
/* isIncomplete */ true,
/* isPending */ true,
usedOuterScopeAlias
);
try {
const flowTypeResult = getTypeFromFlowNode(
antecedent,
reference,
targetSymbolId,
initialType,
isInitialTypeIncomplete
);
if (flowTypeResult.isIncomplete) {
sawIncomplete = true;
}
if (flowTypeResult.usedOuterScopeAlias) {
loopUsedOuterScopeAlias = true;
}
cacheEntry = setIncompleteSubtype(
curFlowNode,
index,
flowTypeResult.type,
flowTypeResult.isIncomplete,
/* isPending */ false,
loopUsedOuterScopeAlias
);
} catch (e) {
setIncompleteSubtype(
curFlowNode,
index,
undefined,
/* isIncomplete */ true,
/* isPending */ false,
usedOuterScopeAlias
);
throw e;
}
}
});
if (isRecursive) {
// This was not the first time through the loop, so we are recursively trying
// to resolve other parts of the incomplete type. It will be marked complete
// once the stack pops back up to the first caller.
// If we have visited the loop node maxFlowNodeLoopVisitCount times already
// and some of the subtypes are still incomplete, bail and base the
// isIncomplete flag on the first subtype, which is the one that feeds
// the top of the loop.
let isIncomplete =
visitCount >= maxFlowNodeLoopVisitCount
? cacheEntry.incompleteSubtypes![0].isIncomplete
: reference !== undefined;
// Limit the number of recursive calls before we give up and call the type
// complete. This can theoretically result in incorrect type information in
// very complex code flows, but it's preferable to extremely long analysis times.
if (codeFlowInvocations - codeFlowInvocationsAtStart > maxCodeFlowInvocationsPerLoop) {
isIncomplete = false;
}
return {
type: cacheEntry.type,
usedOuterScopeAlias,
isIncomplete,
};
}
// If we've been here more than once and the type has converged (didn't change
// since last time), assume that the type is complete.
if (sawIncomplete && typeAtStart && cacheEntry.type) {
if (isTypeSame(typeAtStart, cacheEntry.type)) {
// The type was the same more than two times, so it is not oscillating
// or changing. It's safe to conclude that additional times through
// the loop won't cause it to change further.
if (incrementFlowNodeConvergenceCount(flowNode) > 2) {
sawIncomplete = false;
}
} else {
// The type changed since last time, so reset the convergence count.
incrementFlowNodeConvergenceCount(flowNode, /* reset */ true);
}
}
// The result is incomplete if one or more entries were incomplete.
if (sawIncomplete) {
// If there is an "Unknown" type within a union type, remove
// it. Otherwise we might end up resolving the cycle with a type
// that includes an undesirable unknown.
// Note that we return isIncomplete = false here but do not
// save the cached entry for next time. This is because the
return {
type: cacheEntry?.type ? removeUnknownFromUnion(cacheEntry.type) : undefined,
usedOuterScopeAlias: loopUsedOuterScopeAlias,
isIncomplete: false,
};
}
// We have made it all the way through all the antecedents, and we can
// mark the type as complete.
return setCacheEntry(
curFlowNode,
cacheEntry!.type,
loopUsedOuterScopeAlias,
/* isIncomplete */ false
);
}
if (curFlowNode.flags & (FlowFlags.TrueCondition | FlowFlags.FalseCondition)) {
const conditionalFlowNode = curFlowNode as FlowCondition;
if (reference) {
// Before calling getTypeNarrowingCallback, set the type
// of this flow node in the cache to prevent recursion.
setCacheEntry(
curFlowNode,
reference ? undefined : initialType,
usedOuterScopeAlias,
/* isIncomplete */ true
);
try {
const typeNarrowingCallback = getTypeNarrowingCallback(
evaluator,
reference,
conditionalFlowNode.expression,
!!(
conditionalFlowNode.flags &
(FlowFlags.TrueCondition | FlowFlags.TrueNeverCondition)
)
);
if (typeNarrowingCallback) {
const flowTypeResult = getTypeFromFlowNode(
conditionalFlowNode.antecedent,
reference,
targetSymbolId,
initialType,
isInitialTypeIncomplete
);
let flowType = flowTypeResult.type;
if (flowType) {
flowType = typeNarrowingCallback(flowType);
}
return setCacheEntry(
curFlowNode,
flowType,
flowTypeResult.usedOuterScopeAlias,
flowTypeResult.isIncomplete
);
}
deleteCacheEntry(curFlowNode);
} catch (e) {
// We don't use finally here because the debugger
// doesn't handle it well during single stepping.
deleteCacheEntry(curFlowNode);
throw e;
}
}
curFlowNode = conditionalFlowNode.antecedent;
continue;
}
if (curFlowNode.flags & (FlowFlags.TrueNeverCondition | FlowFlags.FalseNeverCondition)) {
const conditionalFlowNode = curFlowNode as FlowCondition;
if (conditionalFlowNode.reference) {
// Make sure the reference type has a declared type. If not,
// don't bother trying to infer its type because that would be
// too expensive.
const symbolWithScope = evaluator.lookUpSymbolRecursive(
conditionalFlowNode.reference,
conditionalFlowNode.reference.value,
/* honorCodeFlow */ false
);
if (symbolWithScope && symbolWithScope.symbol.getTypedDeclarations().length > 0) {
// Before calling getTypeNarrowingCallback, set the type
// of this flow node in the cache to prevent recursion.
setCacheEntry(
curFlowNode,
reference ? undefined : initialType,
usedOuterScopeAlias,
/* isIncomplete */ true
);
try {
const typeNarrowingCallback = getTypeNarrowingCallback(
evaluator,
conditionalFlowNode.reference,
conditionalFlowNode.expression,
!!(
conditionalFlowNode.flags &
(FlowFlags.TrueCondition | FlowFlags.TrueNeverCondition)
)
);
if (typeNarrowingCallback) {
const refTypeInfo = evaluator.getTypeOfExpression(
conditionalFlowNode.reference!
);
const narrowedType =
typeNarrowingCallback(refTypeInfo.type) || refTypeInfo.type;
// If the narrowed type is "never", don't allow further exploration.
if (isNever(narrowedType)) {
return setCacheEntry(
curFlowNode,
undefined,
usedOuterScopeAlias,
!!refTypeInfo.isIncomplete
);
}
}
deleteCacheEntry(curFlowNode);
} catch (e) {
// We don't use finally here because the debugger
// doesn't handle it well during single stepping.
deleteCacheEntry(curFlowNode);
throw e;
}
}
}
curFlowNode = conditionalFlowNode.antecedent;
continue;
}
if (curFlowNode.flags & FlowFlags.ExhaustedMatch) {
const exhaustedMatchFlowNode = curFlowNode as FlowExhaustedMatch;
const narrowedTypeResult = evaluator.evaluateTypeForSubnode(exhaustedMatchFlowNode.node, () => {
evaluator.evaluateTypesForMatchNode(exhaustedMatchFlowNode.node);
});
// If the narrowed type is "never", don't allow further exploration.
if (narrowedTypeResult && isNever(narrowedTypeResult.type)) {
return setCacheEntry(
curFlowNode,
undefined,
usedOuterScopeAlias,
!!narrowedTypeResult.isIncomplete
);
}
curFlowNode = exhaustedMatchFlowNode.antecedent;
continue;
}
if (curFlowNode.flags & FlowFlags.NarrowForPattern) {
const patternFlowNode = curFlowNode as FlowNarrowForPattern;
if (!reference || isMatchingExpression(reference, patternFlowNode.subjectExpression)) {
const typeResult = evaluator.evaluateTypeForSubnode(patternFlowNode.statement, () => {
if (patternFlowNode.statement.nodeType === ParseNodeType.Case) {
evaluator.evaluateTypesForCaseNode(patternFlowNode.statement);
} else {
evaluator.evaluateTypesForMatchNode(patternFlowNode.statement);
}
});
if (typeResult) {
if (!reference) {
if (isNever(typeResult.type)) {
return setCacheEntry(
curFlowNode,
undefined,
usedOuterScopeAlias,
!!typeResult.isIncomplete
);
}
} else {
return setCacheEntry(
curFlowNode,
typeResult.type,
usedOuterScopeAlias,
!!typeResult.isIncomplete
);
}
}
}
curFlowNode = patternFlowNode.antecedent;
continue;
}
if (curFlowNode.flags & FlowFlags.PreFinallyGate) {
const preFinallyFlowNode = curFlowNode as FlowPreFinallyGate;
if (preFinallyFlowNode.isGateClosed) {
return { type: undefined, usedOuterScopeAlias, isIncomplete: false };
}
// Before recursively calling, set the cache entry to prevent infinite recursion.
setCacheEntry(
curFlowNode,
reference ? undefined : initialType,
usedOuterScopeAlias,
/* isIncomplete */ true
);
try {
const flowTypeResult = getTypeFromFlowNode(
preFinallyFlowNode.antecedent,
reference,
targetSymbolId,
initialType,
isInitialTypeIncomplete
);
// Mark the result as incomplete even if the result of the recursive
// call indicated it was complete. This will prevent the type from
// being permanently cached. We want to cache the type only if
// we're evaluating the "gate closed" path.
return setCacheEntry(
curFlowNode,
flowTypeResult.type,
usedOuterScopeAlias,
/* isIncomplete */ true
);
} catch (e) {
deleteCacheEntry(curFlowNode);
throw e;
}
}
if (curFlowNode.flags & FlowFlags.PostFinally) {
const postFinallyFlowNode = curFlowNode as FlowPostFinally;
const wasGateClosed = postFinallyFlowNode.preFinallyGate.isGateClosed;
try {
postFinallyFlowNode.preFinallyGate.isGateClosed = true;
let flowTypeResult: FlowNodeTypeResult | undefined;
// Use speculative mode for the remainder of the finally suite
// because the final types within this parse node block should be
// evaluated when the gate is open.
evaluator.useSpeculativeMode(postFinallyFlowNode.finallyNode, () => {
flowTypeResult = getTypeFromFlowNode(
postFinallyFlowNode.antecedent,
reference,
targetSymbolId,
initialType,
isInitialTypeIncomplete
);
});
// If the type is incomplete, don't write back to the cache.
return flowTypeResult!.isIncomplete
? flowTypeResult!
: setCacheEntry(
curFlowNode,
flowTypeResult!.type,
flowTypeResult!.usedOuterScopeAlias,
/* isIncomplete */ false
);
} finally {
postFinallyFlowNode.preFinallyGate.isGateClosed = wasGateClosed;
}
}
if (curFlowNode.flags & FlowFlags.Start) {
return setCacheEntry(curFlowNode, initialType, usedOuterScopeAlias, isInitialTypeIncomplete);
}
if (curFlowNode.flags & FlowFlags.WildcardImport) {
const wildcardImportFlowNode = curFlowNode as FlowWildcardImport;
if (reference && reference.nodeType === ParseNodeType.Name) {
const nameValue = reference.value;
if (wildcardImportFlowNode.names.some((name) => name === nameValue)) {
const type = getTypeFromWildcardImport(wildcardImportFlowNode, nameValue);
return setCacheEntry(curFlowNode, type, usedOuterScopeAlias, /* isIncomplete */ false);
}
}
curFlowNode = wildcardImportFlowNode.antecedent;
continue;
}
// We shouldn't get here.
fail('Unexpected flow node flags');
return setCacheEntry(curFlowNode, undefined, usedOuterScopeAlias, /* isIncomplete */ false);
}
}