Recursive async function never returns to caller | TypeScript Community | Page 1

runic rampart Mar 26, 2023, 6:45 PM

#

I have a function with the statement:

const candidateParent = await getParentFromAncestor(candidateAncestor, node);

where

const getParentFromAncestor = async(potentialAncestor: ASTNode, potentialDescendant: ASTNode): Promise<ASTNode | null>

is a recursive function that traverses the tree of candidateAncestor's children to find node. This functions well in nearly all circumstances, but I have a situation in which after getParentFromAncestor() has conducted an unsuccessful search and unwound the recursive stack, it returns null and yet execution does not resume at the call site; things simply stall.

I have logs both just above the return null statement in getParentFromAncestor() and just after the statement at the call site, but only the former gets printed. Unfortunately, I cannot get VSCode to attach to the process in order to determine what is happening at the point of stalling (see: https://discord.com/channels/508357248330760243/1088992613081813164).

I would be extremely grateful for any assistance in the matter.

stone sorrel Mar 26, 2023, 6:46 PM

#

can you show the function itself? or at least a snippet of the recursive part

#

also if possible, an mcve would probably help here

runic rampart Mar 26, 2023, 6:52 PM

#

The function is a bit long, but reducing it to the code path that actually gets executed, it looks like this:

const getParentFromAncestor = async(potentialAncestor: ASTNode, potentialDescendant: ASTNode): Promise<ASTNode | null> =>
{
    for (var child of potentialAncestor.children)
    {
      if (areEqual(child, potentialDescendant))
      {
        return potentialAncestor;
      }
      else
      {
        const childSearch = await getParentFromAncestor(child, potentialDescendant);
        if (childSearch)
        {
            return childSearch;
        }
      }
    }

        myLog.appendLine('Failed to find node in potentialAncestor\'s tree.');
    return null;
}

Unfortunately the program is complex enough that it would be difficult to produce a reasonably minimal example. 😕

stone sorrel Mar 26, 2023, 7:02 PM

#

it only needs to return null if the loop fails to find a match right

#

just to make sure, have you tried this with an artificial small tree

runic rampart Mar 26, 2023, 7:08 PM

#

I haven't tried it on artificially small trees, only on real data, which includes shallow trees.

#

(That is, cases where potentialAncestor has no children or only one child.)

stone sorrel Mar 26, 2023, 7:10 PM

#

could you maybe construct a tree that just follows this codepath

runic rampart Mar 26, 2023, 7:11 PM

#

When you say "this codepath", which one do you mean specifically, sorry?

stone sorrel Mar 26, 2023, 7:12 PM

#

oh. yeah. uh a tree that only involves going through the code shown?

runic rampart Mar 26, 2023, 7:23 PM

#

Ah right, yeah, so that's what I have in the failure case. Specifically, the tree given to me by Clang goes
Var { Pointer { Elaborated { Record } } } }
and the complete logs go

Getting candidateParent [this is the original call site that never gets returned to]
getParentFromAncestor() called with potentialAncestor == Var (16:0 -> 16:42)
looking at potential ancestor's child: Pointer (16:16 -> 16:30)
it's not a match, looking in children's children [this logs a childSearch]
getParentFromAncestor() called with potentialAncestor == Pointer (16:16 -> 16:30)
looking at potential ancestor's child: Elaborated (16:16 -> 16:28)
it's not a match, looking in children's children
getParentFromAncestor() called with potentialAncestor == Elaborated (16:16 -> 16:28)
looking at potential ancestor's child: Record (16:16 -> 16:28)
it's not a match, looking in children's children
getParentFromAncestor() called with potentialAncestor == Record (16:16 -> 16:28)
potentialAncestor.children is null, returning null with potentialAncestor == Record (16:16 -> 16:28) [guard statement]
child search failed
failed to find parent, returning null with potentialAncestor == Elaborated (16:16 -> 16:28) [final return]
child search failed
failed to find parent, returning null with potentialAncestor == Pointer (16:16 -> 16:30)
child search failed
failed to find parent, returning null with potentialAncestor == Var (16:0 -> 16:42)

That is, in the case of Var, its child Pointer and its grandchild Elaborated, a recursive childSearch gets conducted but fails, so the final return null gets executed; in the case of its great-grandchild Record, a childSearch also gets conducted but since it has no children, a return null in a guard statement that I cut out for brevity gets executed.

#

Also, I'd never let the stall run long enough for this to happen before typing out that post, but while I was doing that, I got an OOM with the following callstack:

    at C.process.exit (c:\Users\Thomas\AppData\Local\Programs\Microsoft VS Code\resources\app\out\vs\workbench\api\node\extensionHostProcess.js:122:14225)
    at fatalError (node:internal/async_hooks:174:11)
    at emitInitNative (node:internal/async_hooks:208:5)
    at emitInitScript (node:internal/async_hooks:506:3)
    at promiseInitHook (node:internal/async_hooks:321:3)
    at promiseInitHookWithDestroyTracking (node:internal/async_hooks:325:3)
    at Promise.then (<anonymous>)
    at Object.appendLine (c:\Users\Thomas\AppData\Local\Programs\Microsoft VS Code\resources\app\out\vs\workbench\api\node\extensionHostProcess.js:107:2682)
    at getParentAstNode (.././src/clangd/editor-services.ts:232:23)
    at runNextTicks (node:internal/process/task_queues:61:5)
    at process.processImmediate (node:internal/timers:437:9)
    at process.callbackTrampoline (node:internal/async_hooks:130:17)
    at async highlightAstNode (.././src/clangd/editor-services.ts:51:24)

#Recursive async function never returns to caller