ツリー構造処理と統合されたAST

このシリーズの前回の記事は、 ANTLRとRoslynを使用したソース解析の理論に専念しました。 PT Application Inspectorプロジェクトでのコードの署名分析のプロセスは、次の段階に分かれていることに注意してください。

1. 言語依存表現（抽象構文ツリー、AST）への解析。
2. ASTを言語に依存しない統一された形式（Unified AST、UAST）に変換します。
3. DSLで説明されているテンプレートへの直接マッピング。

この記事は第2段階、つまり、訪問者とリスナーの戦略を使用してASTを処理し、ASTを統一フォーマットに変換し、ASTを簡素化し、ツリー構造マッチングアルゴリズムに専念します。

内容

• ASTバイパス
  
  • 訪問者とリスナー
  • ANTLRとRoslynの訪問者の違い
  • ANTLRの文法とビジター
  • ANTLRの代替ラベルと要素ラベル
• 統合ASTノードタイプ
• コンバーターのテスト
• UASTを簡素化
• 木構造マッチングアルゴリズム
• おわりに

ASTバイパス

ご存知のように、パーサーはソースコードを、ASTと呼ばれる解析ツリー（すべての重要でないトークンが削除されたツリー）に変換します。 このようなツリーを処理するにはさまざまな方法があります。 最も単純なのは、子孫の再帰的な縦断を使用してツリーを処理することです。 ただし、この方法は、ノードのタイプが少なく、処理ロジックが単純な非常に単純な場合にのみ適用できます。 その他の場合、各タイプのノードの処理ロジックを別々のメソッドに転送する必要があります。 これは、訪問者とリスナーという2つの典型的なアプローチ（設計パターン）を使用して実現されます。

訪問者とリスナー

訪問者では、ノードの子孫を処理するには、メソッドを手動で呼び出してそれらをバイパスする必要があります。 さらに、親に3つの子孫があり、2つのノードのみがメソッドを呼び出す場合、サブツリーの一部はまったく処理されません。 リスナー（Walker）では、すべての子孫を訪問するメソッドが自動的に呼び出されます。 リスナーには、ノード訪問の開始時に呼び出されるメソッド（enterNode）と、ノード訪問後に呼び出されるメソッド（exitNode）があります。 これらのメソッドは、イベントメカニズムを使用して実装することもできます。 リスナーとは異なり、ビジターメソッドはオブジェクトを返すことができ、入力することもできます。 CSharpSyntaxVisitorを宣言すると、各VisitメソッドはAstNodeオブジェクトを返します。これは、この場合、統合ASTの他のすべてのノードの共通の祖先です。

したがって、訪問者のデザインパターンを使用する場合、訪問したノードに関する情報を保存する必要がないため、ツリー変換コードはより機能的かつ簡潔です。 下の図では、たとえば、PHP言語を変換するときに、不要なHTMLおよびCSSノードが切断されていることがわかります。 走査順序は数字で示されます。 リスナーは通常、データを（たとえば、CSVファイルから）集約し、あるコードを別のコードに変換するときに使用されます（JSON-> XML）。 詳細については、 The Definitive ANTLR 4 Referenceを参照してください 。

ANTLRとRoslynの訪問者の違い。

VisitorとListenerの実装は、ライブラリによって異なる場合があります。 たとえば、次の表は、RoslynおよびANTLRのVisitorおよびListenerクラスとメソッドを説明しています。

ANTLRとRoslynの両方には、デフォルトで結果を返すメソッド（何らかの構文のVisitorメソッドがオーバーライドされていない場合）と、一般的なVisitメソッドがあり、それ自体がどの特別なVisitorメソッドを呼び出すかを決定します。

ANTLR訪問者は、構文文法規則ごとに独自の訪問者を生成します。 特別なタイプのメソッドもあります。

• VisitChild(IRuleNode node) ; デフォルトでノードのバイパスを実装するために使用されます。
• VisitTerminal(IRuleNode node) ; ターミナルノードのバイパスに使用されます。 トークン。
• VisitErrorNode(IErrorNode node) ; 字句エラーまたは構文エラーのあるコードの解析の結果として取得されたトークンをバイパスするために使用されます。 たとえば、文の最後にセミコロンが含まれている場合、パーサーはそのようなトークンを挿入し、エラーであることを示します。 解析エラーの詳細については、前の記事をご覧ください 。
• AggregateResult(AstNode aggregate, AstNode nextResult) ; 子トラバーサルの結果を集約するために設計された、めったに使用されない方法。
• ShouldVisitNextChild(IRuleNode node, AstNode currentResult) ; currentNodeノードをトラバースした結果に応じて、 node次の子孫を処理するかどうかを決定するために設計された、めったに使用されないメソッド。

Roslyn Visitorには、各構文用の特別なメソッドと、すべてのノード用の一般的なVisitメソッドがあります。 ただし、ANTLRとは異なり、「中間」構造をバイパスする方法はありません。 たとえば、RoslynにはVisitStatementのメソッドはなく、特別なVisitDoStatement 、 VisitExpressionStatement 、 VisitForStatementなどのみがあります。 一般的なVisitをVisitStatementとして使用できます。 もう1つの違いは、単純（SyntaxTrivia）ノードのバイパスメソッド、つまり コードに関する情報（スペース、コメント）を失うことなく削除できるノードは、メインノードとトークンをバイパスするメソッドとともに呼び出されます。

ANTLRビジターの欠点は、生成されたビジターメソッドの名前が文法規則の記述スタイルに直接依存するため、コードの一般的なスタイルに適合しない場合があることです。 たとえば、SQL文法では、アンダースコアを使用して単語を区切る、いわゆるSnake caseを使用するのが一般的です。 Roslynメソッドは、C＃コードのスタイルで記述されています。 違いはありますが、RoslynとANTLRのツリー構造の処理方法は新しいバージョンとますます統合されており、これは朗報です（ANTLRバージョン3以下では、訪問者とリスナーのメカニズムはありませんでした）。

ANTLRの文法とビジター。

ANTLRのルール

 ifStatement : If parenthesis statement elseIfStatement* elseStatement? | If parenthesis ':' innerStatementList elseIfColonStatement* elseColonStatement? EndIf ';' ; 

VisitIfStatement(PHPParser.IfStatementContext context)メソッドVisitIfStatement(PHPParser.IfStatementContext context)が生成されます。このコンテキストには次のフィールドがあります。

• parenthesis -単一のノード。
• elseIfStatement* -ノードの配列。 構文がない場合、配列の長さはゼロです。
• elseStatement? -オプションのノード。 構文がない場合、null。
• If 、 EndIfターミナルノード、大文字で始まります。
• ':' 、 ';' -ターミナルノードはコンテキストに含まれません（GetChild（）を介してのみアクセス可能）。

文法のルールが少ないほど、Visitorを書くのが簡単で速くなることに注意してください。 ただし、構文の繰り返しは、個別のルールにする必要もあります。

ANTLRの代替ラベルと要素ラベル

多くの場合、ルールにはいくつかの選択肢があり、これらの選択肢を別の方法で処理する方が論理的です。 幸いなことに、ANTLR 4には、 #記号で始まり、各代替ルールの後に追加される特別な代替ラベルがあります。 パーサーコードを生成すると、ラベルごとに個別のVisitorメソッドが生成されます。これにより、ルールに多くの選択肢がある場合に大量のコードを回避できます。 すべての選択肢にラベルを付けるか、ラベルを付けないでください。 また、多くの値を受け入れる端末を指定するには、ルール要素ラベルを使用できます。

 expression : op=('+'|'-'|'++'|'--') expression #UnaryOperatorExpression | expression op=('*'|'/'|'%') expression #MultiplyExpression | expression op=('+'|'-') expression #AdditionExpression | expression op='&&' expression #LogicalAndExpression | expression op='?' expression op2=':' expression #TernaryOperatorExpression ; 

このルールでは、ANTLRは訪問者VisitExpression 、 VisitUnaryOperatorExpression 、 VisitMultiplyExpressionなどを生成します。各訪問者には、1または2つの要素で構成される式配列とopリテラルがあります。 タグのおかげで、訪問者のコードはより簡潔で簡潔になります。

 public override AstNode VisitUnaryOperatorExpression(TestParser.UnaryOperatorExpressionContext context) { var op = new MyUnaryOperator(context.op().GetText()); var expr = (Expression)VisitExpression(context.expression(0)); return new MyUnaryExpression(op, expr); } public override AstNode VisitMultiplyExpression(TestParser.MultiplyExpressionContext context) { var left = (Expression)VisitExpression(context.expression(0)); var op = new MyBinaryOpeartor(context.op().GetText()); var right = (Expression)VisitExpression(context.expression(1)); return new MyBinaryExpression(left, op, right); } public override AstNode VisitTernaryOperatorExpression(TestParser.TernaryOperatorExpressionContext context) { var first = (Expression)VisitExpression(context.expression(0)); var second = (Expression)VisitExpression(context.expression(1)); var third = (Expression)VisitExpression(context.expression(2)); return new MyTernaryExpression(first, second, third); } ... 

代替ラベルがなければ、式の処理は1つのメソッドになり、コードは次のようになります。

 public override AstNode VisitExpression(TestParser.ExpressionContext context) { Expression expr, expr2, expr3; if (context.ChildCount == 2) // Unary { var op = new MyUnaryOperator(context.GetChild<ITerminalNode>(0).GetText()); expr = (Expression)VisitExpression(context.expression(0)); return new MyUnaryExpression(op, expr); } else if (context.ChildCount == 3) // Binary { expr = (Expression)VisitExpression(context.expression(0)); var binaryOp = new MyBinaryOpeartor(context.GetChild<ITerminalNode>(0).GetText()); expr2 = (Expression)VisitExpression(context.expression(1)); return new MyBinaryExpression(expr, binaryOp, expr2); ... } else // Ternary { var first = (Expression)VisitExpression(context.expression(0)); var second = (Expression)VisitExpression(context.expression(1)); var third = (Expression)VisitExpression(context.expression(2)); return new MyTernaryExpression(first, second, third); } } 

ANTLRだけでなく、文法を記述する他の手段にも代替ラベルが存在することに注意してください。 たとえば、 Nitraでは、 ANTLRとは異なり、代替記号の左側に割り当て記号の付いたラベルが配置されます。

 syntax Expression { | IntegerLiteral | BooleanLiteral | NullLiteral = "null"; | Parenthesized = "(" Expression ")"; | Cast1 = "(" !Expression AnyType ")" Expression; | ThisAccess = "this"; | BaseAccessMember = "base" "." QualifiedName; | RegularStringLiteral; 

統合ASTノードタイプ

統合されたAST構造を開発するとき、 NRefactoryプロジェクトからのAST構造に導かれましたが、それは私たちにとって非常にシンプルであり、信頼できるツリー（忠実度、文字に対して正確なソースコードに可逆）を取得する必要はありませんでした。 任意のノードはAstNodeの後継であり、独自のタイプNodeTypeを持ちます。これは、テンプレートとのマッチングの段階で、およびJSONからデシリアライズするときにも使用されます。 ノードの構造は次のようになりました。

タイプに加えて、各ノードには、コード（TextSpan）内の場所を格納するプロパティがあります。このプロパティは、テンプレートとの一致時にソースコードに表示するために使用されます。 非終端ノードには子ノードのリストが格納され、終端ノードには数値、文字列、またはその他のプリミティブ値が格納されます。

異なる言語のASTノードを比較するために、行が特定のノードの構文であり、列が次のようなC＃、Java、PHPでの実装であるテーブルがコンパイルされました。

この表には：

• 表現 式には戻り値があります。
• 声明; ステートメント（命令）には戻り値がありません。
• リテラル ターミナルノード。
• 最も一般的なAst （MCA）は、最も統一されたASTです。 このノードは、3つすべての言語にこのノードまたは類似のノードのタイプ（IfStatement、AssignmentExpressionなど）が含まれている場合に構築されます。
• 最も詳細なAst （MDA）最も詳細なAST。 このノードは、少なくとも1つの言語にこのタイプのノードが含まれている場合に構築されます（たとえば、C＃のFixedStatenemt fixed (a) { } ）。 T-SQLとC＃の間の最後の宣言言語は、たとえばPHPとC＃の間よりもはるかに異なるため、これらのノードはSQLに似た言語により関連しています。

図に示すノード（および次のセクションで説明する「パターンノード」）に加えて、Most Common Astノードを構築するための人工ノードがありますが、構文はできるだけ「失います」。 これらのノードは以下のとおりです。

• MultichildExpression; Expressionから継承され、他のExpressionのコレクションが含まれます。
• WrapperExpression; Expressionを継承し、任意のタイプのAstNodeを持つノードが含まれます。
• WrapperStatement; Statementを継承し、任意のタイプのAstNodeを持つノードを含みます。

命令型プログラミング言語では、基本的な構成要素は式式とステートメントステートメントです。 前者には戻り値があり、後者は操作を実行するために使用されます。 したがって、このモジュールでは、主にそれらにも集中しました。 これらは、将来汚染分析を実装するために必要なCFGおよびソースコードの他の表現を実装するための基本的な構成要素です。 コード内の脆弱性を検索するために、構文糖、ジェネリック、およびその他の言語固有のものに関する知識は不要であることを追加する価値があります。 したがって、構文糖を標準構造に拡張し、特定のものに関する情報を完全に削除できます。

パターンノードは、カスタムパターンを表す人工的なノードです。 たとえば、数値の範囲、正規表現はリテラルパターンとして使用されます。

コンバーターのテスト

コードアナライザーの優先順位は、個々の部分ではなくコード全体をテストすることです。 この問題を解決するために、すべてのタイプのノードのビジターメソッドを再定義することにしました。 この場合、ビジターが使用されていない場合、 new ShouldNotBeVisitedException(context)例外をスローします。 IntelliSenseはオーバーライドされているメソッドとオーバーライドされていないメソッドを考慮に入れるため、このアプローチは開発を簡素化します。したがって、訪問者が既に実装しているメソッドを簡単に判別できます。

また、すべてのコードのカバレッジテストを改善する方法についても考えています。 統合ASTの各ノードには、対応するソースコードの座標が格納されます。 さらに、すべての端末はトークンで接続されています。 文字の特定の配列。 可能であればすべてのトークンを処理する必要があるため、合計カバレッジ係数は次の式で表すことができます。ここで、 utermsは統一されたASTの端末であり、 termsは通常のRoslynまたはANTLR ASTの端末です。

このメトリックは、1つの係数でコードカバレッジを表します。 もちろん、この係数の推定値は概算ですが、訪問者のコードのリファクタリングと改善に使用できます。 より信頼性の高い分析のために、カバーされた端末のグラフィカルな表現を使用することもできます。

簡素化AST

通常のASTをUASTに変換した後、後者を単純化する必要があります。 最も単純で便利な最適化は、定数の折りたたみ（定数の折りたたみ）です。 たとえば、Cookieの有効期間が長すぎる設定に関連するコードの欠陥があります： cookie.setMaxAge(2147483647); 括弧内の引数は、 86400などの単一の数値、または60 * 60 * 24などの何らかの演算式として記述できます。 別の例は、SQLインジェクションおよびその他の脆弱性を探す際の文字列の連結です。

このタスクを実装するために、カスタムインターフェイスが実装され、Visitor自体はUAST専用です。 ASTを単純化するとツリーノードの数が単純に減少するため、Visitorは入力され、同じタイプを受け入れて返しました。 .NETでのリフレクションのサポートのおかげで、少量のコードでそのような訪問者を実装することがわかりました。 各ノードには他のノードまたはターミナルプリミティブ値が含まれているため、リフレクションを使用すると、特定のノードのすべてのメンバーを抽出して処理し、他の訪問者を再帰的に呼び出すことができます。

ASTおよびパターンマッチングアルゴリズム

テンプレート検索アルゴリズムは、すべてのASTノードを列挙し、各ノードをツリー構造の形式で提示されたテンプレートと照合することで構成されます。 2つのノードが同じタイプであり、タイプに応じて、いくつかの条件が満たされている場合、2つのノードは同等です。

• 子孫の再帰的な比較。
• 単純なリテラル型（識別子、文字列、数字）の比較。
• 拡張リテラル型（正規表現、範囲）の比較。 コメントはこのグループにあります。
• 複雑な拡張型（式、ステートメントシーケンス）の比較。

このアルゴリズムは、それらを実装する比較的少量のコードで高いパフォーマンスを実現できる単純な原則に基づいています。 後者は、ノードを比較するためのCompareToメソッドが基本クラス、端末、および少数の他のノードに対して実装されているという事実により実現されます。 状態マシンに基づいてパフォーマンスを改善するためのより高度なマッチングアルゴリズムはまだ実装されていません。 ただし、このアルゴリズムは、たとえば言語のセマンティクスを考慮するなど、より高度な分析に使用するには問題があります（または不可能ですらあります）。 異なるASTノード間の接続。

おわりに

この記事では、ツリーを処理するための訪問者とリスナーのパターンを検討し、統一されたASTの構造についても話しました。 次の記事で教えてくれます：

• テンプレートストレージアプローチ（ハードコード、Json、DSL）。
• パターンを記述するためのDSLの開発と使用。
• 実際のテンプレートとオープンソースプロジェクトでの検索の例;
• CFG、DFGおよび汚染分析。