Some counterexamples seem to be repeated for -Wcounterexamples

[zmajeed]

bison 3.7.5 seems to print some counterexamples twice with -Wcounterexamples

The output below is for a grammar provided by Christoph Grüninger on the help-bison mailing list asking for help with resolving the conflicts - https://lists.gnu.org/archive/html/help-bison/2021-02/msg00000.html - the grammar file cmDependsJavaParser.y
is at https://lists.gnu.org/archive/html/help-bison/2021-02/txtD1gzy_c0wb.txt

I've numbered each counterexample - you'll notice there are 6 counterexamples for 4 conflicts. And counterexamples 2 and 5 seem to be the same. Similarly 3 and 6 seem duplicates.

The true story is the duplicate counterexamples are for different parser states. But this is apparent only when the diagnostics report file is generated with --report=counterexamples --report-file=report.txt. The report shows each conflict and counterexample by parser state. Without the report the output can be confusing.

Could parser states be referenced in the output for -Wcounterexamples?

$ bison -Wcounterexamples cmDependsJavaParser.y

cmDependsJavaParser.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]

1. cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_SEMICOL [-Wcounterexamples]
Example: ClassBodyDeclarations MethodHeader MethodBody • jp_SEMICOL
Shift derivation
ClassBodyDeclarations
↳ 79: ClassBodyDeclarations ClassBodyDeclaration
                            ↳ 80: ClassMemberDeclaration
                                  ↳ 85: MethodDeclaration
                                        ↳ 97: MethodHeader MethodBody • jp_SEMICOL
Example: ClassBodyDeclarations MethodHeader MethodBody • jp_SEMICOL
Reduce derivation
ClassBodyDeclarations
↳ 79: ClassBodyDeclarations                                                   ClassBodyDeclaration
      ↳ 79: ClassBodyDeclarations ClassBodyDeclaration                        ↳ 83: TypeDeclaration
                                  ↳ 80: ClassMemberDeclaration                      ↳ 52: jp_SEMICOL
                                        ↳ 85: MethodDeclaration
                                              ↳ 96: MethodHeader MethodBody •

2. cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT [-Wcounterexamples]
Example: jp_THIS • jp_DOT Identifier
Shift derivation
FieldAccess
↳ 268: jp_THIS • jp_DOT Identifier
Example: jp_THIS • jp_DOT Identifier
Reduce derivation
FieldAccess
↳ 266: Primary                  jp_DOT Identifier
       ↳ 239: PrimaryNoNewArray
              ↳ 242: jp_THIS •

3. cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT [-Wcounterexamples]
Example: jp_THIS • jp_DOT Identifier jp_PARESTART jp_PAREEND
Shift derivation
MethodInvocation
↳ 273: jp_THIS • jp_DOT Identifier jp_PARESTART ArgumentListopt jp_PAREEND
                                                ↳ 273: ε
Example: jp_THIS • jp_DOT Identifier jp_PARESTART jp_PAREEND
Reduce derivation
MethodInvocation
↳ 271: Primary                  jp_DOT Identifier jp_PARESTART ArgumentListopt jp_PAREEND
       ↳ 239: PrimaryNoNewArray                                ↳ 271: ε
              ↳ 242: jp_THIS •

4. cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_SEMICOL [-Wcounterexamples]
Example: ClassBodyDeclarations Modifiersopt ConstructorDeclarator Throwsopt ConstructorBody • jp_SEMICOL
Shift derivation
ClassBodyDeclarations
↳ 79: ClassBodyDeclarations ClassBodyDeclaration
                            ↳ 82: ConstructorDeclaration
                                  ↳ 115: Modifiersopt ConstructorDeclarator Throwsopt ConstructorBody • jp_SEMICOL
Example: ClassBodyDeclarations Modifiersopt ConstructorDeclarator Throwsopt ConstructorBody • jp_SEMICOL
Reduce derivation
ClassBodyDeclarations
↳ 79: ClassBodyDeclarations                                                                                   ClassBodyDeclaration
      ↳ 79: ClassBodyDeclarations ClassBodyDeclaration                                                        ↳ 83: TypeDeclaration
                                  ↳ 82: ConstructorDeclaration                                                      ↳ 52: jp_SEMICOL
                                        ↳ 114: Modifiersopt ConstructorDeclarator Throwsopt ConstructorBody •

5. cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT [-Wcounterexamples]
Example: jp_THIS • jp_DOT Identifier
Shift derivation
FieldAccess
↳ 268: jp_THIS • jp_DOT Identifier
Example: jp_THIS • jp_DOT Identifier
Reduce derivation
FieldAccess
↳ 266: Primary                  jp_DOT Identifier
       ↳ 239: PrimaryNoNewArray
              ↳ 242: jp_THIS •

6. cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT [-Wcounterexamples]
Example: jp_THIS • jp_DOT Identifier jp_PARESTART jp_PAREEND
Shift derivation
MethodInvocation
↳ 273: jp_THIS • jp_DOT Identifier jp_PARESTART ArgumentListopt jp_PAREEND
                                                ↳ 273: ε
Example: jp_THIS • jp_DOT Identifier jp_PARESTART jp_PAREEND
Reduce derivation
MethodInvocation
↳ 271: Primary                  jp_DOT Identifier jp_PARESTART ArgumentListopt jp_PAREEND
       ↳ 239: PrimaryNoNewArray                                ↳ 271: ε
              ↳ 242: jp_THIS •

[akimd]

@Xaec6 Would you have a look at this issue?

[Xaec6]

I'll check this out this weekend

[Xaec6]

So what's happening here is the identical conflicts are coming from different states. FWIW, the 'warning: 4 shift/reduce conflicts' includes 1, 2, 4, 5. @akimd the conflicts counter is considering 2,3 and 5,6 to be the duplicates here because it doesn't differentiate between different s/r conflicts on the same token. I guess it's up to you which component should change its behavior so they match.

As for this duplicate, perhaps we change
cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT [-Wcounterexamples]
to
cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT in state 475 [-Wcounterexamples]
so it's more obvious these are different. While I could also add some logic to not report duplicates, it would frequently cause the number of counterexamples reported to be lower than the s/r conflict count which would be confusing.

[zmajeed]

Thanks for looking into this - adding the state as you show looks good to me - couple suggestions to improve the output

1. report total and duplicate/unique counts
2. mark duplicate counterexamples somehow

On the face of it it looks like the duplicates are (2, 5) and (3, 6) - so I'm surprised you found (2, 3) and (5, 6) as duplicates

[akimd]

@Xaec6 Thanks a lot for having looked at this into more details. I'm sorry I took so long to answer, but I think I needed a break.

I don't want to report state numbers in the diagnostics, IMHO that's really something that make only sense in the reports. I do agree that this situation is annoying though, and I definitely would like the "duplicate" counterexamples to not be displayed (I don't think it helps to see it several times. After all it is the same set of rules that have the same problem, but in some "duplicate subautomaton"). Maybe we should report when a counterexample applies for several conflicts, something like

cmDependsJavaParser.y: warning: shift/reduce conflict on token jp_DOT (in 2 states) [-Wcounterexamples]
Example: jp_THIS • jp_DOT Identifier
[...]

or (I prefer this one):

cmDependsJavaParser.y: warning: 2 shift/reduce conflicts on token jp_DOT [-Wcounterexamples]
Example: jp_THIS • jp_DOT Identifier
[...]

I had never realized (or I forgot) that we were counting multiple S/R conflicts in the same place as a single one. It would definitely make sense to count each conflict, but I'm afraid we can't change that, given that some people might be relying on this fact in their %expect requirements. That would break compatibility. I have no idea if some people do indeed rely on the current situation though.

We might have a way out by implementing both ways of counting, and enabling the new one only when %require "3.8" (or better) is enabled. And in a distant future, we might phase out the old way to counting.

[akimd]

Hi @zmajeed

On the face of it it looks like the duplicates are (2, 5) and (3, 6) - so I'm surprised you found (2, 3) and (5, 6) as duplicates

Vincent is referring to something else. 2 and 5 are indeed "twice the same counterexample", but 2 and 3 are actually two SR conflicts in the same state-and-lookahead, and are counted as a single contribution to the overall number of conflicts. That's why the report is about "4 shift/reduce conflicts", and not 6.

I'm not sure what the cutest grammar to show this phenomenon would be, but the following one does it:

$ cat foo.y
%%
exp: a 'x' | 'x'
a: 'x' |
  
$ LC_ALL=C ∫ foo.y -Wcex
foo.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
foo.y: warning: shift/reduce conflict on token 'x' [-Wcounterexamples]
  Example: . 'x'
  Shift derivation
    exp
    `-> . 'x'
  Example: . 'x'
  Reduce derivation
    exp
    `-> a     'x'
        `-> .
foo.y: warning: shift/reduce conflict on token 'x' [-Wcounterexamples]
  First example: 'x'
  Shift derivation
    exp
    `-> 'x'
  Second example: 'x'
  Reduce derivation
    exp
    `-> 'x'
foo.y:3.9: warning: rule useless in parser due to conflicts [-Wother]
    3 | a: 'x' |
      |         ^

[zmajeed]

Thanks for elaborating Akim - I think I understand the difference between duplicate counterexamples and two SR conflicts being counted as one - I'll need to go back to the states report to really figure this out

As for the changes you propose I too prefer the second suggestion "2 shift/reduce conflicts on token" - I can see why state numbers should not be referenced outside of the report itself since there's nothing tying the counterexamples output to the states report - also this format calls out duplicate counterexamples - and the multiplicity allows both unique and duplicate counts to be calculated