Refactor `visit` function

[IvanGoncharov]

Extracted from #1145:

I very frequently use visit function in my work. However I never fully understood how it's working especially since entire visitor.js lacks typing.

I managed to figure out some things and add typings to entire file (with the exception of a few any) and all tests are passing. But I stuck since I can't understand original intentions for some of the features:

@leebyron Could you please review this PR and also answer a few questions:

1. It looks likevisit was designed to handle arrays in root as an argument, but this feature is not used anywhere. Is it required functionality?
2. parent of visitor callback is very strange. If the current node is not in an array it has a value of parent node as expected but if it's inside an array then parent is undefined. In this PR I made parent to always point to parent ASTNode as I think it's what's expected. Is it possible to merge such change?
3. key parameter is always equal to the last element of path array and can be either number or string depending on node location. I see that absolute majority of callback ignores this parameter, so maybe it's worth removing it (you always can get the same value from the path) to simplify callback signature?
4. ancestors is an array of both ASTNodes and arrays of ASTNodes which is very confusing + you can get the same array from root using path elements as indexes. In my PR I changed ancestors to be an array of parent ASTNodes. Is it possible to merge such change?

I saw you made a few small breaking changes in the recent PRs. I think it would be great to also include some interface cleanup of visit function. Since at the moment it scares away 3rd-party developers from writing tooling or contributing to existing projects. For example here is an issue reported on GraphQL Faker repository:

We have done some investigation and it appears that the culprit is this method /src/proxy.ts@master#L122. Unfortunately, this is where we run out of depth, as we currently don't have the bandwidth to study the visit method / API properly.

[IvanGoncharov]

Another idea it to replace false return value with something more readable, suggested by @mjmahone here:
#1466 (review)

[yaacovCR]

Hi! Happy to continue discussion here about visitorKeys as mentioned in #3250. I think it’s useful to speed up the entire function to be able to specify what nodes should be visited. You can enter a node and return false to stop visiting, but then in certain scenarios I guess you would need to check the parent node type (like if you only want to enter certain name or value nodes). And it’s always a tiny bit faster to just not enter a node than you enter it and stop.

I am happy to discuss further. I am not sure why this feature is so low level or brittle, as characterized in #3250 comment but would be happy to hear more about that. I’m just basically hoping to keep visiting at least as fast as it is currently.

[IvanGoncharov]

I propose to have a new API for defining visitors:

const visitor = new ASTVisitor({
    Field {
      skip(node) {
        return node.name.value.startsWith('__');
      }
      'key:arguments': {
        Argument {
          ValueNode(node, ancestors: [FieldNode]) {
            // Only on values of field arguments for non-introspection fields
            // Also note that ancestors are typed here based on visitor heirachy
          }
        }
      }
    }
});

visit(document, visitor);

Compare it to the current API:

const visitor = {
   Field(node) {
     if (node.name.value.startsWith('__')) {
       return false;
     }
   }
   Argument(node) {
     // Only on field arguments for non-introspection fields
   }
}
const keys = {
  Document: ['definitions'],
  OperationDefinition: ['selectionSet'],
  SelectionSet: ['selections'],
  Field: ['arguments'],
  Argument: ['name', 'value'],
  InlineFragment: ['selectionSet'],
  FragmentDefinition: ['selectionSet'],
}

The second variant is not only longer but also brittle.
For example, if we add a new type of AST node that can contain fields (e.g. scoped fragment spreads as discussed in WG) second variant will never visit arguments there.

Performance wise proposed API can be even faster than the second variant.
We can not only automatically generate keys in the constructor of the first version, we can even be embedded visitors callbacks into keys and remove map lookup (it is the most consuming part of the visit at the moment).

[joelmukuthu]

EDIT: it may also just be a bug in my code (as the documentation suggestions that it should be possible to do two things), but I wasn't able to get the return null and return BREAK use-case to work.

By returning different values from the enter and leave functions, the behavior of the visitor can be altered, including skipping over a sub-tree of the AST (by returning false), editing the AST by returning a value or null to remove the value, or to stop the whole traversal by returning BREAK.

---

Original comment:

Just some feedback: it would also be nice to be able to be able to perform multiple actions e.g. delete a note (return null;) and then stop traversing (return BREAK;). As far as I could tell, this is currently not possible since you can't return two things from a function.

I'm posting this here as this issue came up when I was googling for a solution, but I imagine this use-case could also be solved without requiring a full rewrite.