Skip to content

ArrayIndexOutOfBoundsException during grammar parsing #1079

New issue
New issue
Open
Open
ArrayIndexOutOfBoundsException during grammar parsing#1079
Labels
bug
Milestone
stable release 0.18.x
@zborowa

Description

@zborowa
zborowa
opened on May 15, 2017

The error

I'm developing a Rust parser in Rascal and during the parsing process of a specific test file I get the following java out of bounds. I'm on the most up-to-date version of unstable Rascal together with Eclipse Neon.3. I can easily reproduce this error.

java.lang.ArrayIndexOutOfBoundsException: -1(internal error)    at $root$(|main://$root$|)
java.lang.ArrayIndexOutOfBoundsException: -1
        at org.rascalmpl.parser.gtd.util.IntegerObjectList.getKey(IntegerObjectList.java:71)
        at org.rascalmpl.parser.gtd.stack.AbstractStackNode.updateOvertakenNode(AbstractStackNode.java:586)
        at org.rascalmpl.parser.gtd.SGTDBF.propagateEdgesAndPrefixes(SGTDBF.java:454)
        at org.rascalmpl.parser.gtd.SGTDBF.updateNextNode(SGTDBF.java:186)
        at org.rascalmpl.parser.gtd.SGTDBF.moveToNext(SGTDBF.java:686)
        at org.rascalmpl.parser.gtd.SGTDBF.move(SGTDBF.java:748)
        at org.rascalmpl.parser.gtd.SGTDBF.reduce(SGTDBF.java:763)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1164)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1236)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1241)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1245)
        at org.rascalmpl.interpreter.Evaluator.parseObject(Evaluator.java:694)
        at org.rascalmpl.interpreter.Evaluator.parseObject(Evaluator.java:117)
        at org.rascalmpl.semantics.dynamic.Expression$AsType.interpret(Expression.java:1086)
        at org.rascalmpl.semantics.dynamic.Declarator$Default.interpret(Declarator.java:53)
        at org.rascalmpl.semantics.dynamic.LocalVariableDeclaration$Default.interpret(LocalVariableDeclaration.java:36)
        at org.rascalmpl.semantics.dynamic.Statement$VariableDeclaration.interpret(Statement.java:1005)
        at org.rascalmpl.semantics.dynamic.Statement$NonEmptyBlock.interpret(Statement.java:759)
        at org.rascalmpl.semantics.dynamic.Statement$Try.evalStatementTry(Statement.java:941)
        at org.rascalmpl.semantics.dynamic.Statement$Try.interpret(Statement.java:934)
        at org.rascalmpl.semantics.dynamic.Statement$NonEmptyBlock.interpret(Statement.java:759)
        at org.rascalmpl.semantics.dynamic.Statement$For.interpret(Statement.java:468)
        at org.rascalmpl.interpreter.result.RascalFunction.runBody(RascalFunction.java:383)
        at org.rascalmpl.interpreter.result.RascalFunction.call(RascalFunction.java:322)
        at org.rascalmpl.semantics.dynamic.Expression$CallOrTree.interpret(Expression.java:528)
        at org.rascalmpl.semantics.dynamic.Statement$Expression.interpret(Statement.java:365)
        at org.rascalmpl.interpreter.result.RascalFunction.runBody(RascalFunction.java:383)
        at org.rascalmpl.interpreter.result.RascalFunction.call(RascalFunction.java:292)
        at org.rascalmpl.semantics.dynamic.Expression$CallOrTree.interpret(Expression.java:528)
        at org.rascalmpl.semantics.dynamic.Statement$Expression.interpret(Statement.java:365)
        at org.rascalmpl.interpreter.Evaluator.eval(Evaluator.java:882)
        at org.rascalmpl.semantics.dynamic.Command$Statement.interpret(Command.java:125)
        at org.rascalmpl.interpreter.Evaluator.eval(Evaluator.java:1090)
        at org.rascalmpl.interpreter.Evaluator.eval(Evaluator.java:959)
        at org.rascalmpl.interpreter.Evaluator.eval(Evaluator.java:914)
        at org.rascalmpl.repl.RascalInterpreterREPL.evalStatement(RascalInterpreterREPL.java:115)
        at org.rascalmpl.eclipse.repl.RascalTerminalConnector$2.evalStatement(RascalTerminalConnector.java:280)
        at org.rascalmpl.repl.BaseRascalREPL.handleInput(BaseRascalREPL.java:99)
        at org.rascalmpl.repl.BaseREPL.run(BaseREPL.java:282)
        at org.rascalmpl.eclipse.repl.RascalTerminalConnector$1.run(RascalTerminalConnector.java:115)

Does this have to do with my code or something within Rascal?
(0.8.4.201705151236)

The situation

To better paint the picture here is a simple example of how to trigger this error within my project on commit 6a0b58a. The current situation of the project expects macros (similar to C macros) to be parsed into token trees and to be later written back into a file. They don't need any special treatment so to achieve this the following rules have been written.

syntax Macro_tokens 
	= ![{}()\[\]\"]
	| Macro_enclosure
	| String
	;

syntax Macro_enclosure
	= "{" Macro_tokens* "}"
	| "(" Macro_tokens* ")"
	| "[" Macro_tokens* "]"
	;

syntax Item_macro
	= macro: Path_expression "!" Identifier? Macro_enclosure ";"?
	;

This situation applies to macro creation and invocation. This means that I can replace all the macro related rules with this rule. The invocation and the creation use a similar syntax mainly being denoted by the macro label.

The macros are also incorporated to be a part of the expressions within the language. In the previous case I tried to parse the macros correctly with the right indentation and association but this has changed into the current situation. Because of the macros being a part of the expressions they can also be replaced by the macro enclosure (Item_macro). By doing so I get the earlier stated error. And example of how the macro expressions rules looks can be seen here:

syntax Macro_expression
	= Path_expression "!" Identifier? Parens_delimited_token_trees
	| Path_expression "!" Identifier? Brackets_delimited_token_trees
	;

syntax Parens_delimited_token_trees
	= bracket "(" {Token_tree Sep_token}* Sep_token? ")"
	;

syntax Brackets_delimited_token_trees
	= bracket "[" {Token_tree Sep_token}* Sep_token? "]"
	;

The recreation

By replacing Macro_expression on line 815 in the grammar in the Expression rule, with Item_macro which can be seen on line 188 in the grammar and run the project we can get the error. Running of the project can be done by importing the main file and running the main function:

import main;
main();

This will run the project which starts parsing 8499 Rust files so it can take a minute or two to complete. This can also be recreated by for examples parsing a specific file. An example of this could be the following. The strange thing about parsing the file directly through the repl is that both ways give us different errors as can be seen. First import the needed libraries.

import ParseTree;
import lang::rust::\syntax::Rust;

Then parse the file:

rascal>parse(#start[Crate], |project://oxidize/rust/src/librustdoc/html/markdown.rs|);
|std:///ParseTree.rsc|(14522,194,<448,0>,<450,87>): Java("ArrayIndexOutOfBoundsException","-1")
        at org.rascalmpl.parser.gtd.util.IntegerObjectList.getKey(|unknown:///IntegerObjectList.java|(0,0,<71,0>,<71,0>))
        at org.rascalmpl.parser.gtd.stack.AbstractStackNode.updateOvertakenNode(|unknown:///AbstractStackNode.java|(0,0,<586,0>,<586,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.propagateEdgesAndPrefixes(|unknown:///SGTDBF.java|(0,0,<454,0>,<454,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.updateNextNode(|unknown:///SGTDBF.java|(0,0,<186,0>,<186,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.moveToNext(|unknown:///SGTDBF.java|(0,0,<686,0>,<686,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.move(|unknown:///SGTDBF.java|(0,0,<748,0>,<748,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.reduce(|unknown:///SGTDBF.java|(0,0,<763,0>,<763,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.parse(|unknown:///SGTDBF.java|(0,0,<1164,0>,<1164,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.parse(|unknown:///SGTDBF.java|(0,0,<1236,0>,<1236,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.parse(|unknown:///SGTDBF.java|(0,0,<1241,0>,<1241,0>))
        at org.rascalmpl.parser.gtd.SGTDBF.parse(|unknown:///SGTDBF.java|(0,0,<1245,0>,<1245,0>))
        at org.rascalmpl.interpreter.Evaluator.parseObject(|unknown:///Evaluator.java|(0,0,<694,0>,<694,0>))
        at org.rascalmpl.interpreter.Evaluator.parseObject(|unknown:///Evaluator.java|(0,0,<733,0>,<733,0>))
        at org.rascalmpl.library.Prelude.parse(|unknown:///Prelude.java|(0,0,<2129,0>,<2129,0>))
        at org.rascalmpl.library.Prelude.parse(|unknown:///Prelude.java|(0,0,<2120,0>,<2120,0>))
        at sun.reflect.NativeMethodAccessorImpl.invoke0(|unknown:///NativeMethodAccessorImpl.java|(0,0,<0,0>,<0,0>))
        at parse(|std:///ParseTree.rsc|(14709,5,<450,80>,<450,85>))

or

rascal>[start[Crate]]|project://oxidize/rust/src/librustdoc/html/markdown.rs|
java.lang.ArrayIndexOutOfBoundsException: -1(internal error)    at $root$(|main://$root$|)
java.lang.ArrayIndexOutOfBoundsException: -1
        at org.rascalmpl.parser.gtd.util.IntegerObjectList.getKey(IntegerObjectList.java:71)
        at org.rascalmpl.parser.gtd.stack.AbstractStackNode.updateOvertakenNode(AbstractStackNode.java:586)
        at org.rascalmpl.parser.gtd.SGTDBF.propagateEdgesAndPrefixes(SGTDBF.java:454)
        at org.rascalmpl.parser.gtd.SGTDBF.updateNextNode(SGTDBF.java:186)
        at org.rascalmpl.parser.gtd.SGTDBF.moveToNext(SGTDBF.java:686)
        at org.rascalmpl.parser.gtd.SGTDBF.move(SGTDBF.java:748)
        at org.rascalmpl.parser.gtd.SGTDBF.reduce(SGTDBF.java:763)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1164)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1236)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1241)
        at org.rascalmpl.parser.gtd.SGTDBF.parse(SGTDBF.java:1245)
        at org.rascalmpl.interpreter.Evaluator.parseObject(Evaluator.java:694)
        at org.rascalmpl.interpreter.Evaluator.parseObject(Evaluator.java:733)
        at org.rascalmpl.semantics.dynamic.Expression$AsType.interpret(Expression.java:1091)
        at org.rascalmpl.semantics.dynamic.Command$Expression.interpret(Command.java:61)
        at org.rascalmpl.interpreter.Evaluator.eval(Evaluator.java:1090)
        at org.rascalmpl.interpreter.Evaluator.eval(Evaluator.java:959)
        at org.rascalmpl.interpreter.Evaluator.eval(Evaluator.java:914)
        at org.rascalmpl.repl.RascalInterpreterREPL.evalStatement(RascalInterpreterREPL.java:115)
        at org.rascalmpl.eclipse.repl.RascalTerminalConnector$2.evalStatement(RascalTerminalConnector.java:280)
        at org.rascalmpl.repl.BaseRascalREPL.handleInput(BaseRascalREPL.java:99)
        at org.rascalmpl.repl.BaseREPL.run(BaseREPL.java:282)
        at org.rascalmpl.eclipse.repl.RascalTerminalConnector$1.run(RascalTerminalConnector.java:115)

Metadata

Metadata

Assignees

No one assigned

    Labels

    bug

    Type

    No type

    Projects

    No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions