Re: [RFC] Allow %expect and %expect annotations on rules

[Akim Demaille]

I’m surprised (and somewhat disappointed) that there are no answers about this 
thread.  I like Paul’s contribution a lot, and was expecting some comments.

Since none of the 0 responses were about critical issue I failed to see, I will 
install these patches in master (when the CI is done checking the one below).

The previous email was about fixing the computation of per-rule SR conflicts.  
This one is about fixing the computation of the per-rule RR conflicts.  In both 
cases ‘fixing’ might be an unfair way to describe the change: I find ‘my’ way 
to compute easier to understand that Paul’s, since when you sum them, you get 
the overall numbers of conflicts.  It’s also easier for the human to compute, 
since you get the numbers of conflicts that you see in the *.output file.

However, Paul’s computations might have advantages that I have not foreseen, or 
are more important than I think (e.g., robustness to changes in the lookahead 
sets).


While I’m very happy with per-rule %expect (s/r), I’m not entirely satisfied 
with the current %expect-rr (r/r).  More on this later.


commit 6ca1b418e4ff6e5c7e61e00fb26b401b33d7cb1e
Author: Akim Demaille <address@hidden>
Date:   Fri Nov 9 17:29:29 2018 +0100

    %expect-rr: tune the number of conflicts per rule
    
    Currently on a grammar such as
    
        exp : a '1' | a '2' | a '3' | b '1' | b '2' | b '3'
        a:
        b:
    
    we count only one rr-conflict on the `b:` rule, i.e., we expect:
    
        b: %expect-rr 1
    
    although there are 3 conflicts in total.  That's because in the
    conflicted state we count only a single conflict, although there are
    three (one for each of the lookaheads: '1', '2', '3').
    
        State 0
    
            0 $accept: . exp $end
            1 exp: . a '1'
            2    | . a '2'
            3    | . a '3'
            4    | . b '1'
            5    | . b '2'
            6    | . b '3'
            7 a: . %empty  ['1', '2', '3']
            8 b: . %empty  ['1', '2', '3']
    
            '1'       reduce using rule 7 (a)
            '1'       [reduce using rule 8 (b)]
            '2'       reduce using rule 7 (a)
            '2'       [reduce using rule 8 (b)]
            '3'       reduce using rule 7 (a)
            '3'       [reduce using rule 8 (b)]
            $default  reduce using rule 7 (a)
    
            exp  go to state 1
            a    go to state 2
            b    go to state 3
    
    See https://lists.gnu.org/archive/html/bison-patches/2013-02/msg00106.html.
    
    * src/conflicts.c (rule_has_state_rr_conflicts): Rename as...
    (count_rule_state_sr_conflicts): this.
    DWIM.
    (count_rule_rr_conflicts): Adjust.
    * tests/conflicts.at (%expect-rr in grammar rules)
    (%expect-rr too much in grammar rules)
    (%expect-rr not enough in grammar rules): New.

diff --git a/src/conflicts.c b/src/conflicts.c
index af67aaea..f081f2af 100644
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -483,7 +483,7 @@ count_state_rr_conflicts (state *s)
       int count = 0;
       for (int j = 0; j < reds->num; ++j)
         count += bitset_test (reds->lookahead_tokens[j], i);
-      if (count >= 2)
+      if (2 <= count)
         res += count-1;
     }
 
@@ -546,23 +546,25 @@ count_rule_sr_conflicts (rule *r)
 | involved in reduce/reduce conflicts.                             |
 `-----------------------------------------------------------------*/
 
-static bool
-rule_has_state_rr_conflicts (rule *r, state *s)
+static size_t
+count_rule_state_rr_conflicts (rule *r, state *s)
 {
-  reductions *reds = s->reductions;
+  size_t res = 0;
+  const reductions *reds = s->reductions;
+  bitset lookaheads = bitset_create (ntokens, BITSET_FIXED);
 
   for (int i = 0; i < reds->num; ++i)
     if (reds->rules[i] == r)
-      {
-        bitset lookaheads = reds->lookahead_tokens[i];
-        for (int j = 0; j < reds->num; ++j)
-          if (reds->rules[j] != r &&
-              !bitset_disjoint_p (lookaheads, reds->lookahead_tokens[j]))
-            return true;
-        break;
-      }
-
-  return false;
+      for (int j = 0; j < reds->num; ++j)
+        if (reds->rules[j] != r)
+          {
+            bitset_and (lookaheads,
+                        reds->lookahead_tokens[i],
+                        reds->lookahead_tokens[j]);
+            res += bitset_count (lookaheads);
+          }
+  bitset_free (lookaheads);
+  return res;
 }
 
 static size_t
@@ -570,8 +572,7 @@ count_rule_rr_conflicts (rule *r)
 {
   size_t res = 0;
   for (state_number i = 0; i < nstates; ++i)
-    if (conflicts[i] && rule_has_state_rr_conflicts (r, states[i]))
-      res++;
+    res += count_rule_state_rr_conflicts (r, states[i]);
   return res;
 }
 
diff --git a/tests/conflicts.at b/tests/conflicts.at
index c5fd512f..bddd8b83 100644
--- a/tests/conflicts.at
+++ b/tests/conflicts.at
@@ -1318,6 +1318,89 @@ AT_BISON_CHECK([-o input.c input.y], 1, [],
 AT_CLEANUP
 
 
+## ---------------------------- ##
+## %expect-rr in grammar rule.  ##
+## ---------------------------- ##
+
+AT_SETUP([%expect-rr in grammar rule])
+
+AT_DATA([input.y],
+[[%glr-parser
+%expect-rr 3
+%%
+exp
+: a '1'
+| a '2'
+| a '3'
+| b '1'
+| b '2'
+| b '3'
+a:
+b: %expect-rr 3
+]])
+
+AT_BISON_CHECK([-o input.c input.y])
+AT_CLEANUP
+
+
+## ------------------------------------- ##
+## %expect-rr too much in grammar rule.  ##
+## ------------------------------------- ##
+
+AT_SETUP([%expect-rr too much in grammar rule])
+
+AT_DATA([input.y],
+[[%glr-parser
+%expect-rr 3
+%%
+exp
+: a '1'
+| a '2'
+| a '3'
+| b '1'
+| b '2'
+| b '3'
+a:
+b: %expect-rr 4
+]])
+
+AT_BISON_CHECK([-fcaret -o input.c input.y], 1, [],
+[[input.y:12.4-15: error: reduce/reduce conflicts for rule 8: 3 found, 4 
expected
+ b: %expect-rr 4
+    ^^^^^^^^^^^^
+]])
+AT_CLEANUP
+
+
+## --------------------------------------- ##
+## %expect-rr not enough in grammar rule.  ##
+## --------------------------------------- ##
+
+AT_SETUP([%expect-rr not enough in grammar rule])
+
+AT_DATA([input.y],
+[[%glr-parser
+%expect-rr 3
+%%
+exp
+: a '1'
+| a '2'
+| a '3'
+| b '1'
+| b '2'
+| b '3'
+a:
+b: %expect-rr 2
+]])
+
+AT_BISON_CHECK([-fcaret -o input.c input.y], 1, [],
+[[input.y:12.4-15: error: reduce/reduce conflicts for rule 8: 3 found, 2 
expected
+ b: %expect-rr 2
+    ^^^^^^^^^^^^
+]])
+AT_CLEANUP
+
+
 ## ------------------------- ##
 ## %prec with user strings.  ##
 ## ------------------------- ##