페이지

2012년 10월 25일 목요일

Using AST in CDT

CDT AST(abstract syntax tree)

History

revisionchangesauthor
0.1initial version 2012-10-25 목 Darren Ha
0.2getting simplified ast tree using index 2012-10-31 수 Darren Ha

Introduction

AST는 코드에서 refactoring 등의 기능을 지원하기 위해서 만든 data structure이며 트리 구조를 가지고 있다. 이것을 이용해서 JDT 나 CDT 등에서 아주 강력하고 개발자에게 많은 도움을 주는 툴들을 만들 수 있다. refactoring 기능이나 static analyzer등의 기능들. 그렇다면 CDT의 index 와는 뭐가 틀릴까? index가 전체 프로젝트의 단위에서 동작하고 각 심볼단위(function or variable)로만 동작했다면, AST는 translation unit(header file or source file)단위로 정보를 get 할 수 있고, 각 function안의 statement 한 줄 한 줄에 대한 정보를 모두 가지고 있다. detail면에서는 ast훨씬 더 정교한 데이터를 가지고 있는 셈이다. <br/>

Creating With AST

// getting ast from CDE CoreModel
Path path = new Path("hello/src/hello.cpp");
ITranslationUnit tu = (ITranslationUnit) CoreModel.getDefault().create(path);
IASTTranslationUnit ast = tu.getAST(); // it's full ast
// excludes header from ast, much simplified ast.
IASTTranslationUnit simpleast = tu.getAST(index, ITranslationUnit.AST_SKIP_ALL_HEADERS); 
tu.getAST()의 경우는 header를 포함한 모든 ast node를 리턴하지만, tu.getAST(index, ..)의 경우는 헤더를 포함할지 하지 않을지 선택할 수 있다. 헤더를 포함하고 싶지 않을 경우에 사용하면 된다. C++의 헤더 디펜던시를 생각하면, performance gain이 크다.

Visiting AST

// traversing AST
ast.accept(new ASTVisitor() {
        {
            shouldVisitDeclarations = true;
        }
        @Override
        public int visit(IASTDeclaration declaration) {
            System.out.println(declaration);
            return PROCESS_CONTINUE;
        } // visit
    });  
ast tree는 visitor 패턴을 통해서 traverse할 수 있고, ASTVisitor의 생성자에서 visit하고 싶은 대상을 정할 수 있다. ASTVisitor::shouldVisitXXXXX 의 변수를 true로 해주면 매칭되는 node를 visit하게 된다.
예로 아래의 c++ function을 ast tree로 나타내 보자. 그럼 이해가 어느정도 될 것이다.
Application*
BasicApp::CreateInstance(void)
{
    int a;
    return new BasicApp();
}
위의 소스를 ast tree로 보면 아래처럼 표현된다. 소스에 비해서 아주 자세하게 표현되고 있다.
  • ICPPASTFunctionDefinition: BasicApp::CreateInstance
    • ICPPASTNamedTypeSepcifier: Application
    • ICPPFunctionDeclarator: Application*
      • IASTPointer
      • ICPPASTQualifiedName: BasicApp::CreateInstance
      • ICPPASTParameterDeclaration
        • ICPPASTSimpleDeclSpecifier: void
    • ICPPASTCompoundStatement: {}
      • IASTDeclarationStatement
        • ICPPASTSimpleDeclaration: a
          • ICPPASTSimpleDeclSpecifier: int
          • ICPPASTDeclarator, IASTImplicitNameOwner
            • IASTName: a
      • IASTReturnStatement: return new BasicApp();
        • IASTNewExpression
          • ICPPASTTypeId
            • ICPPASTNamedTypeSpecifier:BasicApp
              • IASTName: BasicApp
            • ICPPASTConstructorInitializer

Application

ast로 이런것을 할 수 있다. 다음은 c++에서 흔히 저지르는 실수인 if (a == b) 대신에 if (a=b) 로 assignment가 되는 실수를 detect하는 visitor를 만든 예이다. 이 예제는 reference 1에서 가져온 예임을 밝힙니다.
class CheckCodeVisitor extends ASTVisitor {
    CheckCodeVisitor() {
        shouldVisitExpressions= true;
    }
    public int visit(IASTExpression expression) {
        if (isAssignmentExpression(expression) && isUsedAsCondition(expression)) {
            System.out.println("warning ..." + expression.getFileLocation());
        }
        return PROCESS_CONTINUE;
    }
    private boolean isAssignmentExpression(IASTExpression e) {
        if (e instanceof IASTBinaryExpression) {
            IASTBinaryExpression binExpr= (IASTBinaryExpression) e;
            return binExpr.getOperator() == IASTBinaryExpression.op_assign;
        }
        return false;
    }
    private boolean isUsedAsCondition(IASTExpression expression) {
        ASTNodeProperty prop = expression.getPropertyInParent();
        if (prop == IASTForStatement.CONDITION || prop == IASTIfStatement.CONDITION)
            return true;
        return false;
    }
}

DOM AST(AST viewer)

CDT에는 DOM AST라는 AST트리를 보여주는 아주 훌륭한 viewer가 있었는데, 언젠가부터 org.eclipse.cdt.ui.tests 패키지에 포함되어 버려서 현재는 소스를 빌드하지 않으면 볼 수가없다. AST 관련 작업을 해야 한다면 필수 유틸 되겠다.