Issue with recursive javascript grammar

[CityOfLight77]

Hi @h1994st

I'm trying to use nautilus grammars. With ruby grammar just fine, but javascript grammar I have error with it.

cityoflight@v8:~/Grammar-Mutator$ make -j8 GRAMMAR_FILE=grammars/javascript.json
Found antlr-4.8-complete: /usr/local/lib/antlr-4.8-complete.jar
Selected grammar name: javascript (from /home/cityoflight/Grammar-Mutator/grammars/javascript.json)
python3 grammars/f1_c_gen.py /home/cityoflight/Grammar-Mutator/grammars/javascript.json /home/cityoflight/Grammar-Mutator
python3 grammars/f1_c_gen.py /home/cityoflight/Grammar-Mutator/grammars/javascript.json /home/cityoflight/Grammar-Mutator
make[1]: Entering directory '/home/cityoflight/Grammar-Mutator/third_party'
make[2]: Entering directory '/home/cityoflight/Grammar-Mutator/third_party/Cyan4973_xxHash'
make[2]: Nothing to be done for 'all'.
make[2]: Leaving directory '/home/cityoflight/Grammar-Mutator/third_party/Cyan4973_xxHash'
make[2]: Entering directory '/home/cityoflight/Grammar-Mutator/third_party/rxi_map'
make[2]: Nothing to be done for 'all'.
make[2]: Leaving directory '/home/cityoflight/Grammar-Mutator/third_party/rxi_map'
make[2]: Entering directory '/home/cityoflight/Grammar-Mutator/third_party/antlr4-cpp-runtime'
make[2]: Nothing to be done for 'all'.
make[2]: Leaving directory '/home/cityoflight/Grammar-Mutator/third_party/antlr4-cpp-runtime'
make[1]: Leaving directory '/home/cityoflight/Grammar-Mutator/third_party'

^CTraceback (most recent call last):
  File "grammars/f1_c_gen.py", line 646, in <module>
Traceback (most recent call last):
  File "grammars/f1_c_gen.py", line 646, in <module>
    main(json.load(fp), sys.argv[2])
  File "grammars/f1_c_gen.py", line 632, in main
    fuzz_hdr, fuzz_src = CFuzzer(c_grammar).fuzz_src()
  File "grammars/f1_c_gen.py", line 317, in __init__
    main(json.load(fp), sys.argv[2])
  File "grammars/f1_c_gen.py", line 632, in main
    super().__init__(grammar)
  File "grammars/f1_c_gen.py", line 262, in __init__
    self.compute_rule_recursion()
  File "grammars/f1_c_gen.py", line 310, in compute_rule_recursion
    fuzz_hdr, fuzz_src = CFuzzer(c_grammar).fuzz_src()
  File "grammars/f1_c_gen.py", line 317, in __init__
    self.rule_recursion[n] = self.is_rule_recursive(n, rule, set())
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    super().__init__(grammar)
  File "grammars/f1_c_gen.py", line 262, in __init__
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    self.compute_rule_recursion()
  File "grammars/f1_c_gen.py", line 310, in compute_rule_recursion
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  [Previous line repeated 16 more times]
KeyboardInterrupt
    self.rule_recursion[n] = self.is_rule_recursive(n, rule, set())
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  [Previous line repeated 15 more times]
  File "grammars/f1_c_gen.py", line 276, in is_rule_recursive
    for token in rule:
KeyboardInterrupt
make: *** [GNUmakefile:102: include/f1_c_fuzz.h] Interrupt
make: *** [GNUmakefile:102: src/f1_c_fuzz.c] Interrupt

I have to stop it with control C. And changing ctx.rule(u'PROGRAM',u'{STATEMENT}\n{PROGRAM}') to ctx.rule(u'PROGRAM',u'{STATEMENT}\n') still get same error.

I don't know the issue is in the javascript nautilus grammar file, or the generator grammars/f1_c_gen.py. If the recursive issue is in the grammar, what kind of pattern should I avoid?

[h1994st]

@CityOfLight77 That's weird. I will take a look today

[CityOfLight77]

And reducing number of VAR from 8 to 4 return another error

cityoflight@tesgrammar:~/Grammar-Mutator$ make -j$(nproc) GRAMMAR_FILE=grammars/javascript.json
Found antlr-4.8-complete: /usr/local/lib/antlr-4.8-complete.jar
Create or update .grammar
Selected grammar name: javascript (from /home/cityoflight/Grammar-Mutator/grammars/javascript.json)
python3 grammars/f1_c_gen.py /home/cityoflight/Grammar-Mutator/grammars/javascript.json /home/cityoflight/Grammar-Mutator
python3 grammars/f1_c_gen.py /home/cityoflight/Grammar-Mutator/grammars/javascript.json /home/cityoflight/Grammar-Mutator
^CTraceback (most recent call last):
Traceback (most recent call last):
  File "grammars/f1_c_gen.py", line 646, in <module>
  File "grammars/f1_c_gen.py", line 646, in <module>
    main(json.load(fp), sys.argv[2])
  File "grammars/f1_c_gen.py", line 632, in main
    main(json.load(fp), sys.argv[2])
  File "grammars/f1_c_gen.py", line 632, in main
    fuzz_hdr, fuzz_src = CFuzzer(c_grammar).fuzz_src()
    fuzz_hdr, fuzz_src = CFuzzer(c_grammar).fuzz_src()
  File "grammars/f1_c_gen.py", line 317, in __init__
  File "grammars/f1_c_gen.py", line 317, in __init__
    super().__init__(grammar)
    super().__init__(grammar)
  File "grammars/f1_c_gen.py", line 262, in __init__
  File "grammars/f1_c_gen.py", line 262, in __init__
    self.compute_rule_recursion()
    self.compute_rule_recursion()
  File "grammars/f1_c_gen.py", line 310, in compute_rule_recursion
  File "grammars/f1_c_gen.py", line 310, in compute_rule_recursion
    self.rule_recursion[n] = self.is_rule_recursive(n, rule, set())
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    self.rule_recursion[n] = self.is_rule_recursive(n, rule, set())
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  File "grammars/f1_c_gen.py", line 285, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  [Previous line repeated 12 more times]
  File "grammars/f1_c_gen.py", line 280, in is_rule_recursive
    v = self.is_rule_recursive(rname, trule, seen | {rn})
  [Previous line repeated 11 more times]
    rn = self.kr_to_s(token, i)
  File "grammars/f1_c_gen.py", line 265, in kr_to_s
  File "grammars/f1_c_gen.py", line 280, in is_rule_recursive
    return 'gen_%s_%d' % (self.k_to_s(key), i)
  File "grammars/f1_c_gen.py", line 252, in k_to_s
    rn = self.kr_to_s(token, i)
  File "grammars/f1_c_gen.py", line 265, in kr_to_s
    return k[1:-1].replace('-', '_')
KeyboardInterrupt
    return 'gen_%s_%d' % (self.k_to_s(key), i)
KeyboardInterrupt
make: *** [GNUmakefile:102: src/f1_c_fuzz.c] Interrupt
make: *** [GNUmakefile:102: include/f1_c_fuzz.h] Interrupt

[h1994st]

Hi @CityOfLight77,

The error is due to the outdated codes about recursion calculation, which have been deleted right now.

Please try the latest dev branch and let me know if the issue is resolved. Thanks.

[CityOfLight77]

The issue is resolved. But I have another issue with recursion rule. I want to create a rule for javascript key-value object like this:

var obj = {key1: value1, key2: value2};

Then I make a rule similar to ARRAY

ctx.rule(u'LITERAL',u'{KEYVALUEOBJECT}')
...
ctx.rule(u'KEYVALUEOBJECT',u'\\{ {KEYVALUEOBJECTCONTENT} \\}')
ctx.rule(u'KEYVALUEOBJECT',u'\\{  \\}')
ctx.rule(u'KEYVALUEOBJECTCONTENT',u'{VAR}: {NUMBER}, {KEYVALUEOBJECTCONTENT}')

And got an error

cityoflight@tesgrammar:~/Grammar-Mutator$ make -j$(nproc) GRAMMAR_FILE=grammars/javascript.json
Found antlr-4.8-complete: /usr/local/lib/antlr-4.8-complete.jar
Create or update .grammar
Selected grammar name: javascript (from /home/cityoflight/Grammar-Mutator/grammars/javascript.json)
python3 grammars/f1_c_gen.py /home/cityoflight/Grammar-Mutator/grammars/javascript.json /home/cityoflight/Grammar-Mutator
python3 grammars/f1_c_gen.py /home/cityoflight/Grammar-Mutator/grammars/javascript.json /home/cityoflight/Grammar-Mutator
Traceback (most recent call last):
  File "grammars/f1_c_gen.py", line 587, in <module>
    main(json.load(fp), sys.argv[2])
  File "grammars/f1_c_gen.py", line 573, in main
    fuzz_hdr, fuzz_src = CFuzzer(c_grammar).fuzz_src()
  File "grammars/f1_c_gen.py", line 257, in __init__
    super().__init__(grammar)
  File "grammars/f1_c_gen.py", line 146, in __init__
    self.c_grammar = self.cheap_grammar()
  File "grammars/f1_c_gen.py", line 162, in cheap_grammar
    min_cost = crules[0][0]
IndexError: list index out of range
make: *** [GNUmakefile:102: include/f1_c_fuzz.h] Error 1
make: *** Waiting for unfinished jobs....
Traceback (most recent call last):
  File "grammars/f1_c_gen.py", line 587, in <module>
    main(json.load(fp), sys.argv[2])
  File "grammars/f1_c_gen.py", line 573, in main
    fuzz_hdr, fuzz_src = CFuzzer(c_grammar).fuzz_src()
  File "grammars/f1_c_gen.py", line 257, in __init__
    super().__init__(grammar)
  File "grammars/f1_c_gen.py", line 146, in __init__
    self.c_grammar = self.cheap_grammar()
  File "grammars/f1_c_gen.py", line 162, in cheap_grammar
    min_cost = crules[0][0]
IndexError: list index out of range
make: *** [GNUmakefile:102: src/f1_c_fuzz.c] Error 1

I don't know why recursive ARRAYCONTENT is not error, but KEYVALUEOBJECTCONTENT error

[h1994st]

Hi @CityOfLight77

The added grammar is problematic, because the KEYVALUEOBJECTCONTENT rule is non-terminal. Please see the newly appended line as below:

ctx.rule(u'LITERAL',u'{KEYVALUEOBJECT}')
...
ctx.rule(u'KEYVALUEOBJECT',u'\\{ {KEYVALUEOBJECTCONTENT} \\}')
ctx.rule(u'KEYVALUEOBJECT',u'\\{  \\}')
ctx.rule(u'KEYVALUEOBJECTCONTENT',u'{VAR}: {NUMBER}, {KEYVALUEOBJECTCONTENT}')
ctx.rule(u'KEYVALUEOBJECTCONTENT',u'{VAR}: {NUMBER}')  # <-- this line

[CityOfLight77]

Thanks for the help. Now my issues are resolved