Difficultés ANTLR: rédaction d'une grammaire Ruby

Chez Rostelecom-Solar, nous développons un analyseur de code statique pour les vulnérabilités et NDV, qui fonctionne également sur les arbres d'analyse. Pour les construire, nous utilisons une version optimisée d' ANTLR4 , un outil de développement de compilateurs, d'interprètes et de traducteurs.



Le référentiel contient les grammaires de nombreux langages de programmation. Cependant, il manque la grammaire Ruby, que personne n'a apparemment implémentée. Il n'y a qu'une grammaire d'une langue maison similaire, analysant uniquement les cas les plus simples. Cela n'est pas surprenant, car la grammaire Ruby est difficile à implémenter, car le langage a une syntaxe non triviale. Mais ce serait très utile pour ceux qui, par exemple, veulent écrire leur propre langue et réfléchir à la manière de le faire. Ou pour ceux qui ont besoin de résoudre les difficultés techniques évoquées dans notre article. Eh bien, nous devrons écrire une nouvelle grammaire, ce que nous ferons ici.



ANTLR propose de scinder l'analyse du langage en lexer et parser.



Lexer est engagé dans la génération de jetons basés sur des séquences spécifiées de caractères de l'alphabet de la langue. Si une séquence de caractères correspond à la définition de plusieurs jetons, le plus long est sélectionné, et parmi eux - le premier en priorité (qui est spécifié par l'ordre d'écriture).



L'analyseur forme des phrases (commandes complètes) du langage à l'aide de jetons (également appelés caractères terminaux) obtenus à partir du lexer.



En général, l'orthographe de la grammaire n'est pas différente des autres langues. Vous pouvez apprendre à partir du livre de l' auteur , de la documentation ou de nombreux tutoriels comme celui-ci .



Dans cet article, l'implémentation de base sera omise et seules les difficultés techniques d'écriture seront prises en compte.

Problèmes de Lexer

En général, le seul problème possible dans un lexer est l'émission d'un jeton valide sur une séquence de caractères et les obstacles associés.

Interpolation

Certaines chaînes Ruby permettent l'interpolation - l'insertion de code arbitraire à l'intérieur en utilisant la syntaxe #{code}. Par exemple:

a = 3
"Hello #{if a%2==1 then "Habr!" else "World!" end}"

Nous allons faire face à l'aide de modes - des «petits lexers» spécifiques conçus pour une tâche spécifique, comme notre analyse d'une chaîne:

DoubleQuote: '"' {++nestedStringLevel;}    -> pushMode(InterpolationString);

À chaque niveau d'imbrication, le nombre d'accolades ouvertes doit être maintenu en raison des situations de la forme (vous devez quitter l'interpolation à la 2ème accolade fermante):

"Kappa #{
    buf = ''
    [1, 2, 3].each { |x| buf += x.to_s }
    buf
}"

Pour ce faire, créons une pile openedCurlyBracesInsideString. Au total, nous avons un jeton à l'intérieur du mod:

StartInterpolation: '#{' {openedCurlyBracesInsideString.push(0);}    -> pushMode(DEFAULT_MODE);

Maintenant, vous devez quitter le mode normal (DEFAULT_MODE) à temps, pour cela, nous ajoutons le code aux jetons:

OpenCurlyBracket:             '{' {
    if (nestedStringLevel > 0 && !openedCurlyBracesInsideString.empty()) {
        final int buf = openedCurlyBracesInsideString.pop();
        openedCurlyBracesInsideString.push(buf + 1);
    }
};
CloseCurlyBracket:            '}' {
    if (nestedStringLevel > 0 && openedCurlyBracesInsideString.peek() <= 0) {
       popMode();
       openedCurlyBracesInsideString.pop();
    } else {
        if (!openedCurlyBracesInsideString.empty()) {
            final int buf = openedCurlyBracesInsideString.pop();
            openedCurlyBracesInsideString.push(buf - 1);
        }
    }
};

% -notations

Ruby a une syntaxe supplémentaire inspirée de Perl pour écrire des chaînes, des tableaux de chaînes et des symboles (qui n'est pas un symbole dans Ruby au sens habituel), des expressions régulières et des commandes shell. La syntaxe de ces commandes est% suivi d'un identificateur de type facultatif et d'un caractère de séparation. Par exemple: %w|a b c|- un tableau de trois chaînes. Cependant, il peut également être utilisé comme parenthèse paire de séparateurs {} [] () <>. Cela ne fonctionnera pas simplement de spécifier tous les identificateurs possibles - alors, par exemple, la séquence

q = 3
5%q

ne sera pas reconnu correctement. Le lexer mange simplement la plus longue chaîne de caractères en créant un jeton %q.



En créant une vérification de l'absence d'un séparateur manifestement invalide, tel qu'un caractère espace, un chiffre et une lettre, et en l'ajoutant au jeton comme prédicat (une condition qui doit être remplie à un certain endroit pour continuer à construire le jeton),

StringArrayConstructorwToken: '%w' {canBeDelimiter()}?;

nous obtenons une protection qui fonctionne presque toujours (nous en reparlerons plus tard). Nous ajoutons également une attente du séparateur correspondant en fonction de l'alternative.

StartArrayConstructorNotInterpolated
    : StringArrayConstructorwToken ( Brackets {setPairDelimiter();} | ~[(<{[] {setCharDelimiter();} ) {startStringMode(ArrayConstructorw);}

fragment Brackets: '(' | '[' | '{' | '<';

où startStringModeest une fonction utilitaire pour la commutation de mode et la prise en charge de l'imbrication.

public void startStringMode(final int mode) {
    pushMode(mode);
    ++nestedStringLevel;
}

Contre-exemple: 5%q|1 - analysé correctement uniquement dans le cadre d'un analyseur, quand on sait qu'il ne peut y avoir aucune chaîne après 5 affectations.



Vous pourriez penser qu'il suffit de trouver un séparateur correspondant en regardant vers l'avant, mais il existe un exemple pour un tel cas - 5%q|1|1. D'où il devient clair que lors de la division en un lexer et un analyseur, un tel cas ne peut pas être analysé.



Cependant, cela arrive très rarement, donc ¯ \ _ (ツ) _ / ¯ fera l'affaire. A l'intérieur du mode, on attend juste le séparateur.

ArraywWhitespace: WhitespaceAll                           -> skip;
ArraywText:       ({!isDelimiter()}? ArraywTextFragment)+ -> type(StringPart);
ArraywEnd:        . {nestedStringLevel--;}                -> type(HereDocEnd), popMode;

où typechange le type de jetons générés pour plus de commodité.

Division ou début de regex

La syntaxe des expressions régulières est la suivante /regexp/(ainsi que la notation en pourcentage susmentionnée). Le même problème du contexte de l'analyseur se pose que dans le paragraphe précédent, pour l'atténuer, on crée une vérification

public boolean canBeRegex() {
    return isPrevWS && " \t\r\u000B\f\b\n".indexOf((char) _input.LA(1)) == -1 || isPrevNL || isOp || prevNonWsType == StartInterpolation;
}

et ajouter au jeton

Divide:                       '/' {
    if (canBeRegex()) {
        startHereDoc(RegExp);
    }
};

Pour les variables recalcule isOp, isPrevNL, isPrevWSet override emit-fonction de la création finale du jeton

@Override
public void emit(final Token token) {
    final String txt = token.getText();
    final int type = token.getType();
    isPrevNL = type == NL;
    isPrevWS = type == WS;
    if (!isPrevWS && !isPrevNL && type != SingleLineComment && type != MultiLineComment) {
        isOp = OPERATORS.contains(type);
        prevNonWsChar = txt.charAt(txt.length() - 1);
        prevNonWsType = type;
    }
    super.emit(token);
}

où OPERATORSest le hashmap de tous les opérateurs.

Problèmes d'analyseur

Caractères d'espaces blancs

L'effet des espaces sur l'analyse est une très mauvaise surprise. Habituellement, ils n'affectent en aucune façon la grammaire et sont simplement supprimés du flux avec l'aide -> skipou la traduction dans un autre canal. Cependant, un certain nombre de langages distinguent encore certaines constructions avec leur aide.



Donc, par exemple, a+3et a + 3ne peut pas être un appel de fonction sans parenthèses, mais +3peut-être. Par conséquent, toutes les règles de l'analyseur ressemblent à ceci (NL - nouvelle ligne, WS - espace):

    | expression WS* op=('+' | '-') (NL | WS)* expression

Pour atténuer le problème, écrivons un écouteur qui nettoiera notre arbre d'analyse de ces déchets.

public class RemovingTokensListener implements ParseTreeListener {
        private List<Integer> unwantedTokens;

        ...

        @Override
        public void visitTerminal(final TerminalNode node) {
            if (this.unwantedTokens.contains(node.getSymbol().getType())) {
                ((ParserRuleContext) node.getParent().getRuleContext()).removeLastChild();
            }
        }
}

Heredoc - Lexer et analyseur

Syntaxe spéciale pour spécifier des chaînes multilignes. Peut-être

<<STR
content line 1
content line 2
STR

ou même cela (fait intéressant, markdown ne reconnaît pas correctement la syntaxe).

value = 123
print <<STR_WITH_INTERPOLATION, <<'STR_WITHOUT_INTERPOLATION'.strip
content 1 and #{value}
STR_WITH_INTERPOLATION
     content 2 and #{value}
STR_WITHOUT_INTERPOLATION

Le problème est que vous devez comprendre où se termine la ligne, et il serait également pratique de savoir quel contenu appartient à quelle ligne. Pour ce faire, créez d'abord une liste d'heredocs en attente d'analyse (l'analyseur, selon le contexte et le mode, peut charger un nombre arbitraire de jetons en avant)

public final HeredocsHolder HEREDOCS = new HeredocsHolder();

public static final class HereDocEntry {
    public final String name;
    public final HereDocType type;
    public final boolean isInterpolated;
    public int partsNumber;

    public HereDocEntry(final String name, final HereDocType type, final boolean isInterpolated) {
        this.name = name;
        this.type = type;
        this.isInterpolated = isInterpolated;
        this.partsNumber = 0;
    }
}

public static final class HeredocsHolder {
    public final List<HereDocEntry> entries;
    public int toProcess;

    HeredocsHolder() {
        this.entries = new ArrayList<>();
        this.toProcess = 0;
    }
}

et nous les ajouterons dès qu'ils seront disponibles

StartHereDoc
    : HereDocToken HereDocName {
        heredocIdentifier = getHeredocIdentifier('\'');
        setText(getText().trim());
        keepHereDoc(HereDoc, false);
    }
    ;

public void keepHereDoc(final int mode, final boolean isInterpolated) {
    HEREDOCS.entries.add(new HereDocEntry(heredocIdentifier, getHereDocType(), isInterpolated));
    ++HEREDOCS.toProcess;
    isFirstNL = true;
}

De plus, ayant vu la fin de la ligne avec les heredocs en attente, nous appelons la fonction de traitement.

NL:                           '\n' {
    final int next = _input.LA(1);
    if (HEREDOCS.toProcess > 0 && isFirstNL) {
        startHereDocRoutine();
        isFirstNL = false;
        insideHeredoc = true;
    }
};

La fonction de traitement elle-même est illustrée ci-dessous: ici nous ne traitons que les derniers heredocs (le lexer aurait pu aller de l'avant, mais l'analyseur dans ce cas n'a pas encore absorbé les jetons, nous sauvegardons donc les informations)

public void startHereDocRoutine() {
    final int stopIdx = HEREDOCS.entries.size() - HEREDOCS.toProcess;
    for (int i = HEREDOCS.entries.size() - 1; i >= stopIdx; --i) {
        if (HEREDOCS.entries.get(i).isInterpolated) {
            pushMode(HereDocInterpolated);
        } else {
            pushMode(HereDoc);
        }
    }
    nestedStringLevel += HEREDOCS.toProcess;
    currentHeredocIt = HEREDOCS.entries.listIterator(HEREDOCS.entries.size() - HEREDOCS.toProcess);
    currentHeredoc = currentHeredocIt.next();
}

Il doit être écrasé nextTokenpour quitter le mode et compter le nombre de jetons pour chaque heredoc

@Override
public Token nextToken()
{
    final CommonToken token = (CommonToken)super.nextToken();
    final int ttype = token.getType();
    if (insideHeredoc && ttype == StartInterpolation) {
        ++heredocTokensCount;
    }
    if (_mode == HereDoc || _mode == HereDocInterpolated) {
        if (ttype == VarName) {
            ++heredocTokensCount;
        } else if (ttype == StringPart) {
            ++heredocTokensCount;
            final String txt = token.getText();
            if (CheckHeredocEnd(txt)) {
                token.setText(txt.trim());
                token.setType(HereDocEnd);
                nestedStringLevel--;
                popMode();
                currentHeredoc.partsNumber = heredocTokensCount;
                if (currentHeredocIt.hasNext()) {
                    currentHeredoc = currentHeredocIt.next();
                }
                heredocTokensCount = 0;
                --HEREDOCS.toProcess;
                if (_mode == DEFAULT_MODE) {
                    insideHeredoc = false;
                }
            }
        }
    }
    return token;
}

Commençons maintenant par l'analyseur.



Avec l'aide, @parser::membersajoutez à l'analyseur: un lien vers le lexer, des nœuds de chaîne où nous transférerons leur contenu, le nombre de nœuds d'interpolation (par analogie avec le heredocTokensCountlexer), ainsi qu'une pile d'instructions indiquant le besoin de traitement.

    private final RubyLexer lexer = (RubyLexer)_input.getTokenSource();
    private final List<ParserRuleContext> CONTEXTS = new ArrayList<>();
    private final List<Integer> heredocRulesCount = new ArrayList<>();
    private final Stack<StatementEntry> statements = new Stack<>();

    private static final class StatementEntry {
        public boolean needProcess;
        public int currentHeredoc;

        StatementEntry() {
            this.needProcess = false;
            this.currentHeredoc = 0;
        }
    }

Modifions directement l'unité de code:

statement
@init {
    statements.push(new StatementEntry());
}
@after {
    if (statements.peek().needProcess) {
        processHeredocs($ctx);
    }
    statements.pop();
}
    : statementWithoutHeredocTail ({statements.peek().needProcess}? interpolatedStringPart* HereDocEnd {++statements.peek().currentHeredoc;})*
    ;

@init- le code qui est exécuté lorsque l'analyseur entre dans la règle @after- à sa sortie.



La pile est nécessaire pour affecter heredocs à l'instruction requise, car il peut y en avoir de nouveaux dans l'interpolation.



Afin de reconnaître correctement les cas où heredoc peut être une expression ordinaire et où une chaîne peut être considérée comme des jetons dans une ligne, ainsi que les cas complexes où la fin d'une chaîne se trouve derrière l'expression actuelle, nous écrivons le code d'analyse suivant:

string:
...
    | StartInterpolatedHereDoc (memberAccess* WS* NL interpolatedStringPart* HereDocEnd)? {
        if ($ctx.HereDocEnd() == null) {
            CONTEXTS.add($ctx);
            heredocRulesCount.add(0);
            statements.peek().needProcess = true;
        } else {
             lexer.HEREDOCS.entries.remove(0);
        }
    }
...

Pour le même comptage des nœuds d'interpolation, nous modifions le code de règle avec le contenu de la chaîne ( + 2ici, il est nécessaire de compter les jetons qui ouvrent et ferment l'interpolation)

interpolatedStringPart
locals[int nodesCount = 0]
    : StringPart
    | VarName
    | StartInterpolation (WS* statement {++$nodesCount;})* (WS* rawStatement {++$nodesCount;})? WS* '}' {
        final int cur = statements.peek().currentHeredoc;
        if (cur < heredocRulesCount.size()) {
            heredocRulesCount.set(cur, heredocRulesCount.get(cur) + $nodesCount + 2);
        }
    }
    ;

où se localstrouve une liste de variables locales (vous devez y faire référence via $), et les jetons d'espaces ne sont pas comptés, car sont supprimés lors de la construction de l'arbre par notre auditeur.



Maintenant écrivons la fonction elle-même processHeredocs. Comptons le nombre de nœuds à récupérer

int heredocNodesCount = 0;
for (int i = 0; i < CONTEXTS.size(); ++i) {
    heredocNodesCount += lexer.HEREDOCS.entries.get(i).partsNumber;
    heredocNodesCount += heredocRulesCount.get(i);
}

En commençant par quel enfant, nous commencerons à jeter le contenu des lignes à leur place

int currentChild = ctx.getChildCount() - heredocNodesCount;

Accrocher le contenu au nœud correspondant

for (int i = 0; i < CONTEXTS.size(); ++i) {
    final RubyLexer.HereDocEntry entry = lexer.HEREDOCS.entries.remove(0);
    final ParserRuleContext currentContext = CONTEXTS.get(i);
    final int currentNodesCount = entry.partsNumber + heredocRulesCount.get(i);
    for (int j = 0; j < currentNodesCount; ++j, ++currentChild) {
        final ParseTree child = ctx.getChild(currentChild);
        if (child instanceof TerminalNode) {
            ((TerminalNodeImpl) child).setParent(currentContext);
            currentContext.addChild((TerminalNodeImpl) child);
        } else if (child instanceof ParserRuleContext) {
            ((ParserRuleContext) child).setParent(currentContext);
            currentContext.addChild((ParserRuleContext) child);
        } else {
            // parser failed
            clear();
            return;
        }
    }
}

On efface le nœud lui-même, les contextes heredoc et la liste du nombre de nœuds d'interpolation

for (int i = 0; i < heredocNodesCount; ++i) {
    ctx.removeLastChild();
}
clear();

private void clear() {
    CONTEXTS.clear();
    heredocRulesCount.clear();
}

En guise de touche finale, vous pouvez supprimer une règle intermédiaire inutile pour le traitement des statementWithoutHeredocTailheredocs - en accrochant à nouveau les enfants du nœud à son ancêtre, en utilisant le même écouteur

public class RemovingRulesListener implements ParseTreeListener {
    private List<Integer> unwantedRules;

    ...

    @Override
    public void exitEveryRule(final ParserRuleContext ctx) {
        if (this.unwantedRules.contains(ctx.getRuleIndex())) {
            final ParserRuleContext parentCtx =
                    (ParserRuleContext) ctx.getParent().getRuleContext();
            parentCtx.children.remove(ctx);
            ctx.children.forEach(
                    child -> {
                        if (child instanceof RuleContext) {
                            ((RuleContext) child).setParent(parentCtx);
                            parentCtx.addChild((RuleContext) child);
                        } else if (child instanceof TerminalNode) {
                            ((TerminalNodeImpl) child).setParent(parentCtx);
                            parentCtx.addChild((TerminalNodeImpl) child);
                        }
                    }
            );
        }
    }
}

Ambiguïté

Un problème non résolu était la distinction entre les appels de fonction et, par exemple, l'addition ordinaire (ainsi que le symbole de toute opération simultanément unaire et binaire), qui ne peut être résolu qu'en utilisant des tables de symboles au moment de l'exécution.



L'essentiel est qu'à l'entrée a +a +a +a...de chaque étape, il peut y avoir à la fois une addition ordinaire et un appel de fonction sans arguments (bien que dans ce cas Ruby ne nécessite aucun espace après le signe du premier argument), ce qui conduit apparemment à une croissance exponentielle des marches le long du graphe prédictions.



Cependant, interdire simplement l'espace ANTLR après un opérateur unaire dans le contexte ne fonctionnera pas - vous devez réécrire manuellement l'expression récursive gauche, qui est automatiquement résolue pour le cas sans arguments. S'appuyant sur le fait que «personne» n'écrit plus de trente termes sans raison, ce problème disparaît.

Conclusion

Expérimentalement, cette grammaire peut analyser 99% des fichiers.



Ainsi, aws-sdk-ruby , contenant 3024 fichiers ruby, plante uniquement sur sept, fastlane , contenant 1028, sur 2-x, et Ruby sur Rails à partir de 2081, sur 19.



Cependant, il y a encore des points fondamentalement douloureux comme les heredocs inclus dans l'expression

option(:sts_regional_endpoints,
  default: 'legacy',
  doc_type: String,
  docstring: <<-DOCS) do |cfg|
Passing in 'regional' to enable regional endpoint for STS for all supported
regions (except 'aws-global'), defaults to 'legacy' mode, using global endpoint
for legacy regions.
  DOCS
  resolve_sts_regional_endpoints(cfg)
end

ou utilisé comme expressions, tout type de bloc

def test_group_by_with_order_by_virtual_count_attribute
    expected = { "SpecialPost" => 1, "StiPost" => 2 }
    actual = Post.group(:type).order(:count).limit(2).maximum(:comments_count)
    assert_equal expected, actual
end if current_adapter?(:PostgreSQLAdapter)

J'espère que les techniques décrites dans cet article vous aideront à faire face aux difficultés de votre grammaire. Si vous pensez que l'un des problèmes peut être mieux résolu, bienvenue dans les commentaires.



Auteur: Fedor Usov, développeur de Solar appScreener