[Bug] Parser incorrectly falls back to implicit 'program' when 'module' is preceded by multiple preprocessor blocks

[uwabami]

Description

The parser incorrectly identifies a file as an implicit program instead of a module when the module definition is preceded by multiple preprocessor directives (#ifdef) interleaved with comments.

The module keyword is not recognized as the start of a module, but rather as an identifier inside an implicit program body, leading to parse errors.

Steps to Reproduce

1. Create a file named repro.f90 with the following content:

#ifdef A
! comment 1
#endif
#ifdef B
! comment 2
#endif
#ifdef C
! comment 2
#endif
! comment ...
module my_mod
  integer :: a
  integer :: b
contains
  function foo
  end function foo
end module my_mod

2. Run the tree-sitter CLI: tree-sitter parse repro.f90

Actual Behavior

The parser produces a program node at the root and fails to parse the module keyword, treating it as an identifier erro

(translation_unit [0, 0] - [17, 0]
  (program [0, 0] - [17, 0]
    (preproc_ifdef [0, 0] - [2, 6]
      name: (identifier [0, 7] - [0, 8])
      (comment [1, 0] - [1, 11]))
    (preproc_ifdef [3, 0] - [5, 6]
      name: (identifier [3, 7] - [3, 8])
      (comment [4, 0] - [4, 11]))
    (preproc_ifdef [6, 0] - [8, 6]
      name: (identifier [6, 7] - [6, 8])
      (comment [7, 0] - [7, 11]))
    (comment [9, 0] - [9, 13])
    (ERROR [10, 0] - [11, 0]       <-- 'module' keyword fails here
      (identifier [10, 0] - [10, 6]))
    (variable_declaration [11, 0] - [11, 12]
      type: (intrinsic_type [11, 0] - [11, 7])
      declarator: (identifier [11, 11] - [11, 12]))
    (variable_declaration [12, 0] - [12, 12]
      type: (intrinsic_type [12, 0] - [12, 7])
      declarator: (identifier [12, 11] - [12, 12]))
    (internal_procedures [13, 0] - [16, 0]
      (contains_statement [13, 0] - [13, 8])
      (function [14, 0] - [16, 0]
        (function_statement [14, 0] - [15, 0]
          name: (name [14, 9] - [14, 12]))
        (end_function_statement [15, 0] - [16, 0]
          (name [15, 13] - [15, 16]))))
    (end_program_statement [16, 0] - [17, 0]
      (name [16, 4] - [16, 10])
      (ERROR [16, 11] - [16, 17]))))

Expected Behavior

The translation_unit should contain a module node instead of a program node. The preprocessor directives and comments preceding the module statement should be parsed as siblings of the module node (or correctly recognized as trivia), and the module statement itself should be parsed without errors.

(translation_unit
  (preproc_ifdef ...)
  ...
  (module ...))

[ZedThree]

Thanks for the bug report @uwabami! Here's an even more cut down example:

#if A
#endif

#define B

module my_mod
end module my_mod

expected parse:

(translation_unit
  (preproc_if
    (identifier))
  (preproc_def
    name: (identifier))
  (module
    (module_statement
      (name))
    (end_module_statement)))

actual parse:

(translation_unit
  (ERROR
    (preproc_if
      condition: (identifier))
    (preproc_def
      name: (identifier))
    (identifier)))

This has the same problem of expecting an implicit-program body after the preproc_def.

Unfortunately, debugging why the grammar gets stuck like this is a bit of a nightmare, so this might take some time to fix.

[mscfd]

It seems to boil down to the optional $.program_statement line in:

    program: $ => seq(
      optional($.program_statement),
      repeat(
        choice(
          $._specification_part,
          alias($.preproc_if_in_specification_part, $.preproc_if),
          alias($.preproc_ifdef_in_specification_part, $.preproc_ifdef)
        ),
      ),
      repeat($._statement),
      optional($.internal_procedures),
      $.end_program_statement,
      $._end_of_statement
    ),

If optional is removed it works. After preprocessor statements the parser faces the ambiguity, whether module is a keyword or whether it is an identifier of the specification_part of program. Note that the specification part can contain the same preprocessor statements _top_level_item. Hence, it is really ambiguous whether preprocessor statements belong to _top_level_item or _specification_part:

#define A
#define B
module = 5
print *,module

A and/or B could belong to both and module is an identifier.

I did not have any success in applying some prec rules. This ambiguity seems just a bit too match for the parser to resolve.

But it also seems to go the other way:

module mod
end module mod

module = 5
end

Here, the parser fails to recognise that module is an identifier and parses it as a module keyword (gfortran compiles).

I think that the main problem is how to resolve module versus identifier in the program rule. Depending on statements before (not necessarily preprocessor) such a module line, and thus the internal parser state it is in when it encounters module, it can fail in both directions.

[ZedThree]

I did not have any success in applying some prec rules. This ambiguity seems just a bit too match for the parser to resolve.

I did have some success with a very stripped down version of the grammar, but it caused more issues than it solved with the full grammar.

I think part of the issue is how tree-sitter resolves conflicts, and one of the winning conditions is match length. Here the implicit-program is clearly winning on length. I'm not certain though, as it seems to be impossible to get information about why a particular state was ruled out.

One idea I've not tried is to split program into two rules, _implicit_program and _program, and make the first low precedence.

Here, the parser fails to recognise that module is an identifier and parses it as a module keyword (gfortran compiles).

Oh, this probably "just" needs caseInsensitive('module') adding to the identifier rule. Sometimes some more futzing around is necessary. This is due to Fortran's lack of reserved keywords (a Bad Idea).

This does fix your example, but isn't enough to fix the original issue.

[mscfd]

Oh, this probably "just" needs caseInsensitive('module') adding to the identifier rule. Sometimes some more futzing around is necessary. This is due to Fortran's lack of reserved keywords (a Bad Idea).
I was already wondering why that was missing, but initially it made no difference.

Another problem I noticed are newlines in extras. That seems to be at least a problematic idea with respect to conflict resolution. If the scanner can just swallow newlines, why not parse:

#define A

module mod

as

#define A module ???

But removing newlines from extras and extending the scanner to handle empty lines did not help in this case either.

Another idea to remove ambiguity:

    translation_unit: $ => seq(
      repeat(seq(repeat($._top_level_item_pp), $._top_level_item)),
      optional($.program),
    ),

    _top_level_item: $ => prec(2, choice(
      $.include_statement,
      $.program_with_program_stmt,
      $.module,
      $.submodule,
      $.interface,
      $.subroutine,
      $.function,
      $.block_data,
    )),


    _top_level_item_pp: $ => choice(
      $.preproc_if,
      $.preproc_ifdef,
      $.preproc_include,
      $.preproc_def,
      $.preproc_function_def,
      $.preproc_call,
    ),

But it does not help either, but might avoid some conflicts with preprocessor statements.

[ZedThree]

Ah, I have a fix:

modified   grammar.js
@@ -173,7 +173,7 @@ module.exports = grammar({
       token.immediate(/\r?\n/),
     ),
 
-    ...preprocIf('', $ => repeat($._top_level_item)),
+    ...preprocIf('', $ => repeat($._top_level_item), 4),
     ...preprocIf('_in_module', $ => seq(
       repeat($._specification_part),
       optional($.internal_procedures)

Need to increase the precedence on creating the preproc_if sub-rules. Will make a PR