Bei Rostelecom-Solar entwickeln wir einen statischen Code-Analysator für Schwachstellen und NDV, der auch für Analysebäume funktioniert. Um sie zu erstellen, verwenden wir eine optimierte Version von ANTLR4 , einem Tool zum Entwickeln von Compilern, Dolmetschern und Übersetzern.
Das Repository enthält Grammatiken vieler Programmiersprachen. Es fehlt jedoch die Ruby-Grammatik, die anscheinend niemand implementiert hat. Es gibt nur eine Grammatik einer ähnlichen hausgemachten Sprache, nur die einfachsten Fälle zu analysieren. Dies ist nicht überraschend, da die Ruby-Grammatik schwierig zu implementieren ist, da die Sprache eine nicht triviale Syntax hat. Aber es wäre sehr nützlich für diejenigen, die zum Beispiel ihre eigene Sprache schreiben und darüber nachdenken möchten, wie es geht. Oder für diejenigen, die die in unserem Artikel beschriebenen technischen Schwierigkeiten lösen müssen. Nun, wir müssen eine neue Grammatik schreiben, was wir gleich hier tun werden.
ANTLR schlägt vor, die Sprachanalyse in Lexer und Parser aufzuteilen.
Lexer ist damit beschäftigt, Token basierend auf den angegebenen Zeichenfolgen aus dem Alphabet der Sprache zu generieren. Wenn eine Zeichenfolge mit der Definition mehrerer Token übereinstimmt, wird die längste ausgewählt, und unter diesen - die erste mit Priorität (die durch die Schreibreihenfolge festgelegt wird).
Der Parser bildet Sätze (vollständige Befehle) der Sprache unter Verwendung von Token (auch Terminalzeichen genannt), die vom Lexer erhalten werden.
Im Allgemeinen unterscheidet sich die Schreibweise der Grammatik nicht von anderen Sprachen. Sie können aus dem Buch des Autors , der Dokumentation oder durch zahlreiche Tutorials wie dieses lernen .
In diesem Artikel wird die grundlegende Implementierung weggelassen und nur die technischen Schwierigkeiten beim Schreiben werden berücksichtigt.
Lexer Probleme
Im Allgemeinen ist das einzig mögliche Problem in einem Lexer die Ausgabe eines gültigen Tokens durch eine Folge von Zeichen und die damit verbundenen Hindernisse.
Interpolation
Einige Zeichenfolgen in Ruby ermöglichen die Interpolation - das Einfügen von beliebigem Code mithilfe der Syntax
#{code}. Zum Beispiel:
a = 3
"Hello #{if a%2==1 then "Habr!" else "World!" end}"
Wir werden mit Hilfe von Modi fertig werden - spezifischen "kleinen Lexern", die für eine bestimmte Aufgabe entwickelt wurden, wie das Parsen eines Strings:
DoubleQuote: '"' {++nestedStringLevel;} -> pushMode(InterpolationString);
Auf jeder Verschachtelungsebene muss die Anzahl der offenen Klammern aufgrund von Situationen der Form beibehalten werden (Sie müssen die Interpolation an der 2. schließenden geschweiften Klammer beenden):
"Kappa #{
buf = ''
[1, 2, 3].each { |x| buf += x.to_s }
buf
}"
Dazu erstellen wir einen Stapel
openedCurlyBracesInsideString. Insgesamt haben wir einen Token im Mod:
StartInterpolation: '#{' {openedCurlyBracesInsideString.push(0);} -> pushMode(DEFAULT_MODE);
Jetzt müssen Sie den normalen Modus (DEFAULT_MODE) rechtzeitig verlassen, dazu fügen wir den Code zu den Token hinzu:
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);
}
}
};
% -Notationen
Ruby verfügt über eine zusätzliche Perl-inspirierte Syntax zum Schreiben von Zeichenfolgen, Arrays von Zeichenfolgen und Symbolen (was in Ruby im üblichen Sinne kein Symbol ist), regulären Ausdrücken und Shell-Befehlen. Die Syntax für diese Befehle lautet%, gefolgt von einer optionalen Typkennung und einem Trennzeichen. Zum Beispiel:
%w|a b c|- ein Array von drei Zeichenfolgen. Es kann jedoch auch als Trennzeichen für gepaarte Klammern verwendet werden {} [] () <>. Es funktioniert nicht nur, alle möglichen Bezeichner anzugeben - dann zum Beispiel die Reihenfolge
q = 3
5%q
wird nicht richtig erkannt. Der Lexer frisst einfach die längste Zeichenfolge, indem er ein Token erstellt
%q.
Indem Sie eine Prüfung auf das Fehlen eines offensichtlich ungültigen Trennzeichens wie eines Leerzeichens, einer Ziffer und eines Buchstabens erstellen und es dem Token als Prädikat hinzufügen (eine Bedingung, die an einer bestimmten Stelle erfüllt sein muss, um mit der Erstellung des Tokens fortzufahren),
StringArrayConstructorwToken: '%w' {canBeDelimiter()}?;
Wir bekommen Schutz, der fast immer funktioniert (dazu später mehr). Abhängig von der Alternative fügen wir auch eine Erwartung des entsprechenden Trennzeichens hinzu.
StartArrayConstructorNotInterpolated
: StringArrayConstructorwToken ( Brackets {setPairDelimiter();} | ~[(<{[] {setCharDelimiter();} ) {startStringMode(ArrayConstructorw);}
fragment Brackets: '(' | '[' | '{' | '<';
Wo
startStringModeist eine Utility-Funktion für die Modusumschaltung und Verschachtelungsunterstützung.
public void startStringMode(final int mode) {
pushMode(mode);
++nestedStringLevel;
}
Gegenbeispiel:
5%q|1 - Nur im Kontext eines Parsers korrekt analysiert, wenn bekannt ist, dass nach 5 Zuweisungen keine Zeichenfolge mehr vorhanden sein kann.
Sie könnten denken, dass es ausreicht, einen passenden Begrenzer zu finden, indem Sie nach vorne schauen, aber es gibt auch ein Beispiel dafür -
5%q|1|1. Woher wird klar, dass ein solcher Fall beim Aufteilen in einen Lexer und einen Parser nicht analysiert werden kann.
Dies kommt jedoch sehr selten vor, so dass ¯ \ _ (ツ) _ / ¯ ausreicht. Im Modus warten wir nur auf das Trennzeichen.
ArraywWhitespace: WhitespaceAll -> skip;
ArraywText: ({!isDelimiter()}? ArraywTextFragment)+ -> type(StringPart);
ArraywEnd: . {nestedStringLevel--;} -> type(HereDocEnd), popMode;
Dabei
typewird der Typ der generierten Token der Einfachheit halber geändert.
Teilung oder Beginn der Regex
Die Syntax für reguläre Ausdrücke lautet wie folgt
/regexp/(sowie die oben genannte prozentuale Notation). Das gleiche Problem des Parser-Kontexts tritt auf wie im vorherigen Absatz. Um dies zu vermeiden, erstellen wir eine Prüfung
public boolean canBeRegex() {
return isPrevWS && " \t\r\u000B\f\b\n".indexOf((char) _input.LA(1)) == -1 || isPrevNL || isOp || prevNonWsType == StartInterpolation;
}
und zum Token hinzufügen
Divide: '/' {
if (canBeRegex()) {
startHereDoc(RegExp);
}
};
Neu zu berechnen , die Variablen
isOp, isPrevNL, isPrevWSund überschreibt emit-function der endgültigen Erstellung des Tokens
@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);
}
Wo
OPERATORSist die Hashmap aller Operatoren?
Parser-Probleme
Leerzeichen
Eine unangenehme Überraschung war die Auswirkung von Leerzeichen auf das Parsen. Normalerweise beeinflussen sie die Grammatik in keiner Weise und werden einfach mit Hilfe
-> skipoder Übersetzung in einen anderen Kanal aus dem Stream entfernt . Einige Sprachen unterscheiden jedoch immer noch einige Konstrukte mit ihrer Hilfe.
So zum Beispiel
a+3und a + 3kann kein Funktionsaufruf ohne Klammern sein, aber +3vielleicht. Daher sehen alle Parserregeln folgendermaßen aus (NL - Newline, WS - Whitespace):
| expression WS* op=('+' | '-') (NL | WS)* expression
Um das Problem zu beheben, schreiben wir einen Listener , der unseren Analysebaum von diesem Müll befreit.
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 und Parser
Spezielle Syntax zur Angabe mehrzeiliger Zeichenfolgen. Vielleicht so
<<STR
content line 1
content line 2
STR
oder sogar das (interessanterweise erkennt Markdown die Syntax nicht richtig).
value = 123
print <<STR_WITH_INTERPOLATION, <<'STR_WITHOUT_INTERPOLATION'.strip
content 1 and #{value}
STR_WITH_INTERPOLATION
content 2 and #{value}
STR_WITHOUT_INTERPOLATION
Das Problem ist, dass Sie verstehen müssen, wo die Zeile endet, und es wäre auch praktisch zu wissen, welcher Inhalt zu welcher Zeile gehört. Erstellen Sie dazu zunächst eine Liste der Heredocs, deren Analyse aussteht (der Parser kann je nach Kontext und Modus eine beliebige Anzahl von Token vorwärts laden).
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;
}
}
und wir werden sie hinzufügen, sobald sie verfügbar sind
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;
}Nachdem wir das Ende der Zeile mit ausstehenden Heredocs gesehen haben, rufen wir die Verarbeitungsfunktion auf.
NL: '\n' {
final int next = _input.LA(1);
if (HEREDOCS.toProcess > 0 && isFirstNL) {
startHereDocRoutine();
isFirstNL = false;
insideHeredoc = true;
}
};
Die Verarbeitungsfunktion selbst ist unten dargestellt: Hier verarbeiten wir nur die letzten Heredocs (der Lexer hätte weitermachen können, aber der Parser hat in diesem Fall die Token noch nicht absorbiert, sodass wir die Informationen speichern).
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();
}
Es muss überschrieben werden
nextToken, um den Modus zu verlassen und die Anzahl der Token für jeden Heredoc zu zählen
@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;
}
Beginnen wir nun mit dem Parser.
Fügen Sie mithilfe der Hilfe
@parser::membersdem Parser Folgendes hinzu: einen Link zu einem Lexer, Zeichenfolgenknoten, auf die wir deren Inhalt übertragen, die Anzahl der Interpolationsknoten (analog zu einem heredocTokensCountLexer) sowie einen Stapel von Anweisungen, die auf die Notwendigkeit der Verarbeitung hinweisen.
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;
}
}
Lassen Sie uns die Codeeinheit direkt ändern:
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- Der Code, der ausgeführt wird, wenn der Parser die Regel eingibt @after- wenn er beendet wird.
Der Stack ist erforderlich, um der erforderlichen Anweisung Heredocs zuzuweisen, da Es können neue innerhalb der Interpolation sein.
Um Fälle korrekt zu erkennen, in denen Heredoc ein gewöhnlicher Ausdruck sein kann und eine Zeichenfolge als Token in einer Reihe betrachtet werden kann, sowie komplexe Fälle, in denen das Ende einer Zeichenfolge hinter dem aktuellen Ausdruck liegt, schreiben wir den folgenden Parser-Code:
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);
}
}
...
Für die gleiche Zählung von Interpolationsknoten ändern wir den Regelcode mit dem Zeichenfolgeninhalt (
+ 2hier müssen die Token gezählt werden, die die Interpolation öffnen und schließen).
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);
}
}
;
Wo
localsist eine Liste lokaler Variablen (auf die Sie verweisen müssen $), und Whitespace-Token werden seitdem nicht gezählt werden während der Baumkonstruktion von unserem Hörer entfernt.
Schreiben wir nun die Funktion selbst
processHeredocs. Zählen wir, wie viele Knoten aufgenommen werden sollen
int heredocNodesCount = 0;
for (int i = 0; i < CONTEXTS.size(); ++i) {
heredocNodesCount += lexer.HEREDOCS.entries.get(i).partsNumber;
heredocNodesCount += heredocRulesCount.get(i);
}
Beginnend mit welchem Kind werden wir beginnen, den Inhalt der Zeilen an ihre Stelle zu werfen
int currentChild = ctx.getChildCount() - heredocNodesCount;
Verknüpfen von Inhalten mit dem entsprechenden Knoten
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;
}
}
}
Wir löschen den Knoten selbst, Heredoc-Kontexte und die Liste der Anzahl der Interpolationsknoten
for (int i = 0; i < heredocNodesCount; ++i) {
ctx.removeLastChild();
}
clear();
private void clear() {
CONTEXTS.clear();
heredocRulesCount.clear();
}
Der letzte Schliff besteht darin, eine unnötige Zwischenregel für den Umgang mit
statementWithoutHeredocTailHeredocs zu entfernen, indem die untergeordneten Elemente des Knotens mit demselben Listener erneut an seinen Vorfahren angehängt werden
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);
}
}
);
}
}
}
Mehrdeutigkeit
Ein ungelöstes Problem war die Unterscheidung zwischen Funktionsaufrufen und beispielsweise gewöhnlicher Addition (sowie das Symbol einer gleichzeitig unären und binären Operation), die nur zur Laufzeit mit Symboltabellen gelöst werden kann.
Die Quintessenz ist, dass am Eingang
a +a +a +a...jedes Schritts sowohl eine gewöhnliche Addition als auch ein Funktionsaufruf ohne Argumente erfolgen können (obwohl Ruby in diesem Fall das Fehlen eines Leerzeichens nach dem Vorzeichen des ersten Arguments erfordert), was anscheinend zu einem exponentiellen Wachstum des Gehens entlang des Graphen führt Vorhersagen.
Das einfache Deaktivieren des ANTLR-Leerzeichens nach einem unären Operator im Kontext funktioniert jedoch nicht. Sie müssen den linken rekursiven Ausdruck manuell neu schreiben, der für den Fall automatisch ohne Argumente aufgelöst wird. Aufgrund der Tatsache, dass „niemand“ ohne Grund mehr als dreißig Begriffe schreibt, verschwindet dieses Problem.
Fazit
Experimentell kann diese Grammatik 99% der Dateien analysieren.
Also, aws-sdk-Rubin , mit 3024 Rubin - Dateien, stürzt nur auf sieben, fastlane , mit 1028, auf 2-x, und Ruby on Rails auf 2081, auf 19.
Es gibt jedoch immer noch grundsätzlich wunde Punkte wie Heredocs, die im Ausdruck enthalten sind
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
oder als Ausdrücke verwendet, beliebige Blocktypen
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)
Ich hoffe, die in diesem Artikel beschriebenen Techniken helfen Ihnen, die Schwierigkeiten Ihrer Grammatik zu bewältigen. Wenn Sie der Meinung sind, dass eines der Probleme besser gelöst werden kann, begrüßen Sie die Kommentare.
Autor: Fedor Usov, Entwickler von Solar appScreener