Is there any way to traverse the Ast in preorder, postorder or Inorder in Dart

Issue

Is there any way to traverse the AST made up from dart Analyser in PreOrder, postOrder or inOrder.i am using visit Node to traverse the AST tree using GeneralizingAstVisitor but it just traverse it recursively from top to bottom of code.

import'package:analyzer/src/generated/testing/element_factory.dart';
import 'package:analyzer/analyzer.dart';
import 'dart:io';
import 'package:analyzer/dart/ast/ast.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/file_system/physical_file_system.dart';
import 'package:analyzer/src/context/builder.dart';
import 'package:analyzer/src/dart/sdk/sdk.dart';
import 'package:analyzer/src/generated/engine.dart';
import 'package:analyzer/src/generated/sdk.dart' show DartSdk;
import 'package:analyzer/src/generated/source.dart';
import 'package:analyzer/src/generated/source_io.dart';
import 'package:analyzer/src/source/source_resource.dart';

main() {
  LibraryElement libElement;
  Source source;
  AnalysisContext context;
  var ast = parseCompilationUnit(src,
      parseFunctionBodies: true, suppressErrors: true);
  print(ast.toSource());
  PhysicalResourceProvider resourceProvider = PhysicalResourceProvider.INSTANCE;
  DartSdk sdk = new FolderBasedDartSdk(resourceProvider,
      resourceProvider.getFolder("/usr/local/opt/dart/libexec"));

  var resolvers = [
    new DartUriResolver(sdk),
  ];
  context = AnalysisEngine.instance.createAnalysisContext()
    ..sourceFactory = new SourceFactory(resolvers);
  source = new FileSource(resourceProvider.getFile(
      "/Users/shubhamkumar/Sites/projects/flutterX/dart_analyser/demo.dart"));
  ChangeSet changeSet = new ChangeSet()..addedSource(source);
  context.applyChanges(changeSet);

  libElement = context.computeLibraryElement(source);
  callAST(context, source, libElement);
}

class Visitor1 extends GeneralizingAstVisitor {
  @override
  visitNode(AstNode node) {
    print("node $node ${node.runtimeType}   ");
    node.childEntities.forEach((n) => print(n));
    return super.visitNode(node);
  }
}

callAST(context, source, libElement) {
  CompilationUnit resolvedUnit =
      context.resolveCompilationUnit(source, libElement);
  var visitor = new Visitor1();
  resolvedUnit.accept(visitor);
}

Please help if u have any solution.

Solution

The pattern that GeneralizingAstVisitor does is pre-order.

In-order traversal doesn’t make sense in the context of an AST. In-order traversal is left, root, right. But an AST branch may have anywhere from 1 to infinity children. So the best you could do is define some in-order(n) traversal, where you visit the first child, second child, … nth-child, root, nth+1 child, nth+2 child… I don’t see a purpose of this.

For post-order its a bit more nuanced. If all you want to do is print the node and its child entities, then your solution is simple. You just have to call super before printing the node:

class Visitor2 extends GeneralizingAstVisitor {
  @override
  visitNode(AstNode node) {
    final val = super.visitNode(node);
    print("node $node ${node.runtimeType}   ");
    node.childEntities.forEach((n) => print(n));
    return val;
  }
}

But if you wanted custom logic for a bunch of node types, you’d have to follow that pattern in each visit handler:

class Visitor3 extends GeneralizingAstVisitor {
  @override
  visitAssignmentExpression(AssignmentExpression node) {
    final val = super.visitNode(node);
    // use assignment expression here
    return val;
  }
  @override
  visitBinaryExpression(BinaryExpression node) {
    final val = super.visitNode(node);
    // use binary expression here
    return val;
  }
  // ... more handlers
}

In this case, I would compose visitors to make this easier:

class PostOrderVisitor extends GeneralizingAstVisitor {
  AstVisitor postOrderedVisitor = new Visitor4();
  @override
  visitNode(AstNode node) {
    final val = super.visitNode(node);
    return node.accept(postOrderedVisitor);
  }
}

class Visitor4 extends AstVisitor {
  @override
  visitAssignmentExpression(AssignmentExpression node) {
    // use assignment expression here
  }
  @override
  visitBinaryExpression(BinaryExpression node) {
    // use binary expression here
  }
  // ... more handlers
}

In this case, PostOrderVisitor handles the post-ordering, and Visitor4 handles the individual nodes according to that order but should not do any recursion itself.

These should get you by for most use cases, though it’s hard to be certain without knowing what you’re trying to do.

Answered By – Mike Fairhurst

Answer Checked By – Timothy Miller (FlutterFixes Admin)