En Rostelecom-Solar estamos desarrollando un analizador de código estático para vulnerabilidades y NDV, que también funciona en árboles de análisis. Para construirlos, utilizamos una versión optimizada de ANTLR4 , una herramienta para desarrollar compiladores, intérpretes y traductores.
El repositorio contiene gramáticas de muchos lenguajes de programación. Sin embargo, carece de la gramática Ruby, que aparentemente nadie ha implementado. Solo hay una gramática de un lenguaje casero similar., analizando solo los casos más simples. Esto no es sorprendente, ya que la gramática Ruby es difícil de implementar, ya que el lenguaje tiene una sintaxis no trivial. Pero sería muy útil para quienes, por ejemplo, quieran escribir en su propio idioma y pensar en cómo hacerlo. O para aquellos que necesitan resolver las dificultades técnicas discutidas en nuestro artículo. Bueno, tendremos que escribir una nueva gramática, lo que haremos aquí mismo.
ANTLR propone dividir el análisis del lenguaje en lexer y parser.
Lexer se dedica a generar tokens basados en secuencias específicas de caracteres del alfabeto del idioma. Si una secuencia de caracteres coincide con la definición de varios tokens, se elige el más largo y, entre ellos, el primero en prioridad (que se especifica por el orden de escritura).
El analizador forma oraciones (comandos completos) del lenguaje usando tokens (también llamados caracteres terminales) obtenidos del lexer.
En general, la ortografía de la gramática no es diferente a la de otros idiomas. Puede aprender del libro del autor , la documentación o numerosos tutoriales como este .
En este artículo, se omitirá la implementación básica y solo se considerarán las dificultades técnicas de escritura.
Problemas de Lexer
En general, el único problema posible en un lexer es la emisión de un token válido sobre una secuencia de caracteres y los obstáculos asociados.
Interpolación
Algunas cadenas de Ruby permiten la interpolación: la inserción de código arbitrario en su interior mediante la sintaxis
#{code}. Por ejemplo:
a = 3
"Hello #{if a%2==1 then "Habr!" else "World!" end}"
Nos las arreglaremos con la ayuda de modos: "pequeños lexers" específicos diseñados para una tarea específica, como nuestro análisis de una cadena:
DoubleQuote: '"' {++nestedStringLevel;} -> pushMode(InterpolationString);
En cada nivel de anidamiento, el número de llaves abiertas debe mantenerse debido a situaciones del formulario (debe salir de la interpolación en la segunda llave de cierre):
"Kappa #{
buf = ''
[1, 2, 3].each { |x| buf += x.to_s }
buf
}"
Para hacer esto, creemos una pila
openedCurlyBracesInsideString. En total, tenemos una ficha dentro del mod:
StartInterpolation: '#{' {openedCurlyBracesInsideString.push(0);} -> pushMode(DEFAULT_MODE);
Ahora necesitas salir del modo normal (DEFAULT_MODE) a tiempo, para esto agregamos el código a los tokens:
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);
}
}
};
% -notaciones
Ruby tiene una sintaxis adicional inspirada en Perl para escribir cadenas, matrices de cadenas y símbolos (que no es un símbolo en Ruby en el sentido habitual), expresiones regulares y comandos de shell. La sintaxis de estos comandos es% seguida de un identificador de tipo opcional y un carácter separador. Por ejemplo:
%w|a b c|- una matriz de tres cadenas. Sin embargo, también se puede utilizar como separador de paréntesis {} [] () <>. No funcionará solo para especificar todos los identificadores posibles; luego, por ejemplo, la secuencia
q = 3
5%q
no se reconocerá correctamente. El lexer simplemente se comerá la cadena de caracteres más larga creando un token
%q.
Al crear un cheque por la ausencia de un separador obviamente inválido, como un carácter de espacio, un dígito y una letra, y agregarlo al token como un predicado (una condición que debe cumplirse en un lugar determinado para continuar construyendo el token),
StringArrayConstructorwToken: '%w' {canBeDelimiter()}?;
obtenemos una protección que casi siempre funciona (más sobre eso más adelante). También agregamos una expectativa del separador correspondiente dependiendo de la alternativa.
StartArrayConstructorNotInterpolated
: StringArrayConstructorwToken ( Brackets {setPairDelimiter();} | ~[(<{[] {setCharDelimiter();} ) {startStringMode(ArrayConstructorw);}
fragment Brackets: '(' | '[' | '{' | '<';
donde
startStringModees una función de utilidad para el cambio de modo y el soporte de anidamiento.
public void startStringMode(final int mode) {
pushMode(mode);
++nestedStringLevel;
}
Contraejemplo:
5%q|1 - analizado correctamente solo en el contexto de un analizador, cuando se sabe que después de 5 asignaciones no puede haber cadena.
Se podría pensar que es suficiente para encontrar un separador de juego mirando hacia adelante, pero hay un ejemplo para este caso, un -
5%q|1|1. De ahí que quede claro que al dividir en un lexer y un analizador, tal caso no se puede analizar.
Sin embargo, esto ocurre muy raramente, así que ¯ \ _ (ツ) _ / ¯ servirá. Dentro del modo, solo esperamos el separador.
ArraywWhitespace: WhitespaceAll -> skip;
ArraywText: ({!isDelimiter()}? ArraywTextFragment)+ -> type(StringPart);
ArraywEnd: . {nestedStringLevel--;} -> type(HereDocEnd), popMode;
donde
typecambia el tipo de tokens generados por conveniencia.
División o inicio de expresiones regulares
La sintaxis de las expresiones regulares es la siguiente
/regexp/(así como la notación de porcentaje antes mencionada). Surge el mismo problema del contexto del analizador que en el párrafo anterior, para mitigarlo, creamos un cheque
public boolean canBeRegex() {
return isPrevWS && " \t\r\u000B\f\b\n".indexOf((char) _input.LA(1)) == -1 || isPrevNL || isOp || prevNonWsType == StartInterpolation;
}
y agregar al token
Divide: '/' {
if (canBeRegex()) {
startHereDoc(RegExp);
}
};
Para volver a calcular las variables
isOp, isPrevNL, isPrevWSy anulación emit-función de la creación final de la ficha
@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);
}
donde
OPERATORSes el mapa hash de todos los operadores.
Problemas del analizador
Caracteres de espacio en blanco
Una sorpresa bastante desagradable fue el efecto de los espacios en el análisis. Por lo general, no afectan la gramática de ninguna manera y simplemente se eliminan del flujo con la ayuda
-> skipo la traducción a otro canal. Sin embargo, varios lenguajes aún distinguen algunos constructos con su ayuda.
Entonces, por ejemplo,
a+3y a + 3no puede ser una llamada a función sin paréntesis, pero +3tal vez. Por lo tanto, todas las reglas del analizador se ven así (NL - nueva línea, WS - espacio en blanco):
| expression WS* op=('+' | '-') (NL | WS)* expression
Para mitigar el problema, escriba un oyente que limpie nuestro árbol de análisis de esa basura.
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 y analizador
Sintaxis especial para especificar cadenas de varias líneas. Tal vez sea así
<<STR
content line 1
content line 2
STR
o incluso eso (curiosamente, Markdown no reconoce la sintaxis correctamente).
value = 123
print <<STR_WITH_INTERPOLATION, <<'STR_WITHOUT_INTERPOLATION'.strip
content 1 and #{value}
STR_WITH_INTERPOLATION
content 2 and #{value}
STR_WITHOUT_INTERPOLATION
El problema es que es necesario comprender dónde termina la línea, y también sería conveniente saber qué contenido pertenece a qué línea. Para hacer esto, primero cree una lista de heredocs pendientes de análisis (el analizador, según el contexto y el modo, puede cargar un número arbitrario de tokens hacia adelante)
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;
}
}
y los agregaremos a medida que estén 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;
}Además, habiendo visto el final de la línea con heredocs pendientes, llamamos a la función de procesamiento.
NL: '\n' {
final int next = _input.LA(1);
if (HEREDOCS.toProcess > 0 && isFirstNL) {
startHereDocRoutine();
isFirstNL = false;
insideHeredoc = true;
}
};
La función de procesamiento en sí se muestra a continuación: aquí procesamos solo los últimos heredocs (el lexer podría haber seguido adelante, pero el analizador en este caso aún no ha absorbido los tokens, por lo que guardamos la información)
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();
}
Debe sobrescribirse
nextTokenpara salir del modo y contar el número de tokens para cada 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;
}
Ahora comencemos con el analizador.
Con la ayuda,
@parser::membersagregue al analizador: un enlace al lexer, nodos de cadena donde transferiremos su contenido, el número de nodos de interpolación (por analogía con el heredocTokensCountlexer), así como una pila de declaraciones que indiquen la necesidad de procesamiento.
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;
}
}
Modifiquemos la unidad de código directamente:
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- el código que se ejecuta cuando el analizador ingresa a la regla @after- cuando sale.
La pila es necesaria para asignar heredocs a la instrucción requerida, ya que puede haber otros nuevos dentro de la interpolación.
Para reconocer correctamente los casos en los que heredoc puede ser una expresión ordinaria y en los que una cadena puede considerarse tokens en una fila, así como los casos complejos en los que el final de una cadena estará detrás de la expresión actual, escribimos el siguiente código del analizador:
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);
}
}
...
Para el mismo recuento de nodos de interpolación, modificamos el código de la regla con el contenido de la cadena (
+ 2aquí es necesario contar los tokens que abren y cierran la interpolación)
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);
}
}
;
donde
localshay una lista de variables locales (debe consultarlas $), y los tokens de espacios en blanco no se cuentan, ya que son eliminados durante la construcción del árbol por nuestro oyente.
Ahora escribamos la función en sí
processHeredocs. Vamos a contar cuántos nodos recoger
int heredocNodesCount = 0;
for (int i = 0; i < CONTEXTS.size(); ++i) {
heredocNodesCount += lexer.HEREDOCS.entries.get(i).partsNumber;
heredocNodesCount += heredocRulesCount.get(i);
}
A partir de qué niño, comenzaremos a tirar el contenido de las líneas en sus lugares.
int currentChild = ctx.getChildCount() - heredocNodesCount;
Enganchando contenido al nodo correspondiente
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;
}
}
}
Limpiamos el nodo en sí, los contextos heredoc y la lista del número de nodos de interpolación
for (int i = 0; i < heredocNodesCount; ++i) {
ctx.removeLastChild();
}
clear();
private void clear() {
CONTEXTS.clear();
heredocRulesCount.clear();
}
El toque final es eliminar una regla intermedia innecesaria para el manejo de
statementWithoutHeredocTailheredocs - volviendo a colgar los hijos del nodo a su ancestro usando el mismo oyente
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);
}
}
);
}
}
}
Ambigüedad
Un problema no resuelto fue la distinción entre llamadas a funciones y, por ejemplo, la suma ordinaria (así como el símbolo de cualquier operación unaria y binaria simultáneamente), que solo puede resolverse utilizando tablas de símbolos en tiempo de ejecución.
La conclusión es que en la entrada
a +a +a +a...de cada paso, puede haber tanto una suma ordinaria como una llamada a función sin argumentos (aunque en este caso Ruby no requiere espacio después del signo del primer argumento), lo que aparentemente conduce a un crecimiento exponencial de las caminatas a lo largo del gráfico. predicciones.
Sin embargo, simplemente no permitir el espacio ANTLR después de un operador unario en el contexto no funcionará; tendrá que reescribir manualmente la expresión recursiva izquierda, que se resuelve automáticamente para el caso sin argumentos. Confiando en el hecho de que “nadie” escribe más de treinta términos sin una razón, este problema desaparece.
Conclusión
Experimentalmente, esta gramática puede analizar el 99% de los archivos.
Entonces, aws-sdk-ruby , que contiene 3024 archivos ruby, se bloquea solo en siete, fastlane , que contiene 1028, en 2-x, y Ruby on Rails en 2081, en 19.
Sin embargo, todavía hay puntos fundamentalmente dolorosos como heredocs incluidos en la expresión
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
o utilizado como expresiones, cualquier tipo de bloque
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)
Espero que las técnicas descritas en este artículo le ayuden a afrontar las dificultades de su gramática. Si cree que alguno de los problemas se puede resolver mejor, bienvenido a los comentarios.
Autor: Fedor Usov, desarrollador de Solar appScreener