Lehem 的时间胶囊

Flutter 生成抽象语法树

01 Dec 2020 | Flutter

抽象语法树

在计算机科学中, 抽象语法树(Abstract Syntax Tree, 下面简称 AST), 是编程语言源代码抽象语法结构的树表示. 树的每个节点表示在源代码中内容

本篇目录

从某种意义上说, 该语法是”抽象的”, 它并不代表实际语法中出现的每个细节, 而仅代表结构或与内容相关的细节. 例如, 分组括号在树结构中是隐式的, 他不是一个单独的节点. 也可以用单节点的三个分支来表示类似if-condition-then表达式的语法

举个例子, int a = 1 + 2; 转换之后的图

查看树状图

Dart 生成 AST

Dart的analyzer提供了静态分析Dart语法的能力, 很多官方工具的都是依赖了这个库:

  • dartfmt, Dart代码格式化工具
  • dartdoc, Dart文档生成工具
  • Dart Analysis Server 给IDE编辑器用的代码分析服务

能实现这些功能的核心在于, analyzer 支持从源码生成AST

写这个文章的时候, analyzer版本是 0.41.2

AST 数据结构

我们可以简单使用parseString方法生成经过解析过后的AST原始数据unit

  String content = 'int a = 1 + 2;';
  ParseStringResult result = parseString(content: content);
  CompilationUnit unit = result.unit;

可以通过定义看到, CompilationUnit实现了AstNode, 可以视为一个AST的一个节点

abstract class CompilationUnit implements AstNode

int a = 1 + 2;的AST结构如下

查看CompilationUnit

可以看到, CompilationUnit包含了解析后所有的AST结构信息

AST 生成 DSL

DSL直译为领域特定语言(Domain-specific Language), 表示专门针对特定问题领域的编程语言或者规范语言
像CompilationUnit这种类结构, 需要定义相关类之后才能使用, 很难被用来通用, 采用DSL数据交换的通用结构, 可以用来无损传达结AST的信息
常见的DSL有XML,HTML, 这里采用JSON生成DSL, 因为方便和Map转换, 方便用于HTTP结构, 思路基本相同

访问者模式

CompilationUnit已经生成了, 我们还需要访问这个树形结构, 访问到所有的节点
在的实现类CompilationUnitImpl里面, _declarations的存储了的所以有的子节点数据, _elements实际存储了各种节点类型

class CompilationUnitImpl extends AstNodeImpl implements CompilationUnit {
  ...
  NodeList<CompilationUnitMember> _declarations;
}

class NodeListImpl<E extends AstNode> with ListMixin<E> implements NodeList<E> {
  ... 
  List<E> _elements = <E>[];
}

对于一个或者多个操作访问一组对象, 这些对象还不是同一种类型, 使用访问者模式是最适合的, 确保职责单一, 满足开闭原则

analyzer遵循访问者模式, 提供了几种Visitor用来访问:

  • RecursiveAstVisitor, 递归遍历所有节点
  • GeneralizingAstVisitor, 在递归遍历所有节点的同时, 额外遍历语法节点的子类, 有visitNode方法, 覆盖面比较广
  • UnifyingAstVisitor, 递归遍历所有节点, 对于所有节点, 都会调用一次visitNode方法
  • SimpleAstVisitor, 遍历时候什么都不干, 适用于只关注某几个节点做事情
  • ThrowingAstVisitor, 遍历时候, 如果子类没有覆盖节点方法, 就会抛出异常
  • TimedAstVisitor, 遍历的时候统计调用耗时
  • BreadthFirstVisitor, 继承GeneralizingAstVisitor, 广度遍历所有节点
  • DelegatingAstVisitor, 继承UnifyingAstVisitor, 便利时候触发传入的代理方法

访问实现

我们直接可以使用GeneralizingAstVisitor来访问CompilationUnit数据, 完整代码如下

main () {
  String content = 'int a = 1 + 2;';
  ParseStringResult result = parseString(content: content);
  CompilationUnit unit = result.unit;
  unit.visitChildren(GVisitor());
}

class GVisitor extends GeneralizingAstVisitor {
  @override
  visitNode(AstNode node) {
    // 打印出每个节点的内容
    print("${node.runtimeType} ------ ${node.toSource()}");
    return super.visitNode(node);
  }
}

利用Visitor, 可以打印出节点的结构

TopLevelVariableDeclarationImpl ------ int a = 1 + 2;
VariableDeclarationListImpl ------ int a = 1 + 2
TypeNameImpl ------ int
SimpleIdentifierImpl ------ int
VariableDeclarationImpl ------ a = 1 + 2
DeclaredSimpleIdentifier ------ a
BinaryExpressionImpl ------ 1 + 2
IntegerLiteralImpl ------ 1
IntegerLiteralImpl ------ 2

生成定制 DSL

从上面的打印信息可以看出, 生成的AST是存在信息冗余的, 抽象成DSL的时候, 可以精简掉不需要的内容, 这时候使用SimpleAstVisitor就再适合不过了, 只需要关注想要实现的节点

使用SimpleAstVisitor几个注意点:

  • 方法返回Map类型, 可以集约所有的访问结果
  • 需要主动调用下个节点的accept方法, 否则调用链路会中断
  • 节点类型属于NodeList的, 需要遍历后再调用 accept 方法
  • 有些节点下可能是有多个子节点需要调用, 子节点需要分别调用accept, 例如VariableDeclarationListImpl的visitChildren方法里, _type和_variables都调用了accept
//VariableDeclarationListImpl 的 visitChildren 有多个子节点

  @override
  void visitChildren(AstVisitor visitor) {
    super.visitChildren(visitor);
    _type?.accept(visitor);
    _variables.accept(visitor);
  }

使用SimpleAstVisitor的完整代码如下

main () {
  String content = 'int a = 1 + 2;';
  ParseStringResult result = parseString(content: content);
  CompilationUnit unit = result.unit;
  unit.visitChildren(SVisitor());
}

class SVisitor extends SimpleAstVisitor {
  List<Map> accept(elements, AstVisitor visitor) {
    List<Map> list = [];
    int length = elements.length;
    for (var i = 0; i < length; i++) {
      Map res = elements[i].accept(visitor);
      list.add(res);
    }
    return list;
  }

  @override
  Map visitCompilationUnit(CompilationUnit node) {
    var res = {'unit': accept(node.declarations, this)};
    print(JsonEncoder.withIndent('  ').convert(res));
    return res;
  }

  @override
  Map visitTopLevelVariableDeclaration(TopLevelVariableDeclaration node) {
    return {'top': node.variables.accept(this)};
  }

  @override
  Map visitVariableDeclarationList(VariableDeclarationList node) {
    return {
      'type': node.type.accept(this),
      'var': accept(node.variables, this)
    };
  }

  @override
  Map visitTypeName(TypeName node) {
    return {'name': node.name.name};
  }

  @override
  Map visitSimpleIdentifier(SimpleIdentifier node) {
    return {'identifier': node.name};
  }

  @override
  Map visitVariableDeclaration(VariableDeclaration node) {
    return {
      'name': node.name.accept(this),
      'initializer': node.initializer.accept(this)
    };
  }

  @override
  Map visitBinaryExpression(BinaryExpression node) {
    return {
      "operator": node.operator.lexeme,
      "left": node.leftOperand.accept(this),
      "right": node.rightOperand.accept(this)
    };
  }

  @override
  Map visitIntegerLiteral(IntegerLiteral node) {
    return {'value': node.value};
  }
}

打印出节点结构

{
  "unit": [
    {
      "top": {
        "type": {
          "name": "int"
        },
        "var": [
          {
            "name": {
              "identifier": "a"
            },
            "initializer": {
              "operator": "+",
              "left": {
                "value": 1
              },
              "right": {
                "value": 2
              }
            }
          }
        ]
      }
    }
  ]
}

Flutter 语法生成

Flutter生成同理

import 'package:flutter/material.dart';

class MyWidget extends StatelessWidget {
  @override
  Widget build(BuildContext context) {
    return Container(
      padding: const EdgeInsets.fromLTRB(12.0, 8.0, 12.0, 0.0),
      child: Column(
        children: [
          const Text('line 111'),
          const Text('line 222'),
        ],
      ),
    );
  }
}

生成AST部分截图如下 查看树状图

后续

有了AST之后, 可以做什么:

  1. 解析AST, 再执行AST,提供局部动态/动态的能力,
    1. 布局/逻辑全部动态: 美团
    2. 只有布局动态: Fair 这类
  2. 自定义方法统计
  3. 自定义分析插件

Related Posts

Comments