8 files changed, 292 insertions, 0 deletions
diff --git a/tool/lrama/lib/lrama/counterexamples/derivation.rb b/tool/lrama/lib/lrama/counterexamples/derivation.rb
new file mode 100644
index 0000000000..691e935356
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/derivation.rb
@@ -0,0 +1,63 @@
+module Lrama
+  class Counterexamples
+    class Derivation
+      attr_reader :item, :left, :right
+      attr_writer :right
+
+      def initialize(item, left, right = nil)
+        @item = item
+        @left = left
+        @right = right
+      end
+
+      def to_s
+        "#<Derivation(#{item.display_name})>"
+      end
+      alias :inspect :to_s
+
+      def render_strings_for_report
+        result = []
+        _render_for_report(self, 0, result, 0)
+        result.map(&:rstrip)
+      end
+
+      def render_for_report
+        render_strings_for_report.join("\n")
+      end
+
+      private
+
+      def _render_for_report(derivation, offset, strings, index)
+        item = derivation.item
+        if strings[index]
+          strings[index] << " " * (offset - strings[index].length)
+        else
+          strings[index] = " " * offset
+        end
+        str = strings[index]
+        str << "#{item.rule_id}: #{item.symbols_before_dot.map(&:display_name).join(" ")} "
+
+        if derivation.left
+          len = str.length
+          str << "#{item.next_sym.display_name}"
+          length = _render_for_report(derivation.left, len, strings, index + 1)
+          # I want String#ljust!
+          str << " " * (length - str.length)
+        else
+          str << " • #{item.symbols_after_dot.map(&:display_name).join(" ")} "
+          return str.length
+        end
+
+        if derivation.right&.left
+          length = _render_for_report(derivation.right.left, str.length, strings, index + 1)
+          str << "#{item.symbols_after_dot[1..-1].map(&:display_name).join(" ")} "
+          str << " " * (length - str.length) if length > str.length
+        elsif item.next_next_sym
+          str << "#{item.symbols_after_dot[1..-1].map(&:display_name).join(" ")} "
+        end
+
+        return str.length
+      end
+    end
+  end
+end
diff --git a/tool/lrama/lib/lrama/counterexamples/example.rb b/tool/lrama/lib/lrama/counterexamples/example.rb
new file mode 100644
index 0000000000..62244a77e0
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/example.rb
@@ -0,0 +1,124 @@
+module Lrama
+  class Counterexamples
+    class Example
+      attr_reader :path1, :path2, :conflict, :conflict_symbol
+
+      # path1 is shift conflict when S/R conflict
+      # path2 is always reduce conflict
+      def initialize(path1, path2, conflict, conflict_symbol, counterexamples)
+        @path1 = path1
+        @path2 = path2
+        @conflict = conflict
+        @conflict_symbol = conflict_symbol
+        @counterexamples = counterexamples
+      end
+
+      def type
+        @conflict.type
+      end
+
+      def path1_item
+        @path1.last.to.item
+      end
+
+      def path2_item
+        @path2.last.to.item
+      end
+
+      def derivations1
+        @derivations1 ||= _derivations(path1)
+      end
+
+      def derivations2
+        @derivations2 ||= _derivations(path2)
+      end
+
+      private
+
+      def _derivations(paths)
+        derivation = nil
+        current = :production
+        lookahead_sym = paths.last.to.item.end_of_rule? ? @conflict_symbol : nil
+
+        paths.reverse_each do |path|
+          item = path.to.item
+
+          case current
+          when :production
+            case path
+            when StartPath
+              derivation = Derivation.new(item, derivation)
+              current = :start
+            when TransitionPath
+              derivation = Derivation.new(item, derivation)
+              current = :transition
+            when ProductionPath
+              derivation = Derivation.new(item, derivation)
+              current = :production
+            end
+
+            if lookahead_sym && item.next_next_sym && item.next_next_sym.first_set.include?(lookahead_sym)
+              state_item = @counterexamples.transitions[[path.to, item.next_sym]]
+              derivation2 = find_derivation_for_symbol(state_item, lookahead_sym)
+              derivation.right = derivation2
+              lookahead_sym = nil
+            end
+
+          when :transition
+            case path
+            when StartPath
+              derivation = Derivation.new(item, derivation)
+              current = :start
+            when TransitionPath
+              # ignore
+              current = :transition
+            when ProductionPath
+              # ignore
+              current = :production
+            end
+          else
+            raise "BUG: Unknown #{current}"
+          end
+
+          break if current == :start
+        end
+
+        derivation
+      end
+
+      def find_derivation_for_symbol(state_item, sym)
+        queue = []
+        queue << [state_item]
+
+        while (sis = queue.shift)
+          si = sis.last
+          next_sym = si.item.next_sym
+
+          if next_sym == sym
+            derivation = nil
+
+            sis.reverse_each do |si|
+              derivation = Derivation.new(si.item, derivation)
+            end
+
+            return derivation
+          end
+
+          if next_sym.nterm? && next_sym.first_set.include?(sym)
+            @counterexamples.productions[si].each do |next_item|
+              next if next_item.empty_rule?
+              next_si = StateItem.new(si.state, next_item)
+              next if sis.include?(next_si)
+              queue << (sis + [next_si])
+            end
+
+            if next_sym.nullable
+              next_si = @counterexamples.transitions[[si, next_sym]]
+              queue << (sis + [next_si])
+            end
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/tool/lrama/lib/lrama/counterexamples/path.rb b/tool/lrama/lib/lrama/counterexamples/path.rb
new file mode 100644
index 0000000000..edba67a3b6
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/path.rb
@@ -0,0 +1,23 @@
+module Lrama
+  class Counterexamples
+    class Path
+      def initialize(from_state_item, to_state_item)
+        @from_state_item = from_state_item
+        @to_state_item = to_state_item
+      end
+
+      def from
+        @from_state_item
+      end
+
+      def to
+        @to_state_item
+      end
+
+      def to_s
+        "#<Path(#{type})>"
+      end
+      alias :inspect :to_s
+    end
+  end
+end
diff --git a/tool/lrama/lib/lrama/counterexamples/production_path.rb b/tool/lrama/lib/lrama/counterexamples/production_path.rb
new file mode 100644
index 0000000000..d7db688518
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/production_path.rb
@@ -0,0 +1,17 @@
+module Lrama
+  class Counterexamples
+    class ProductionPath < Path
+      def type
+        :production
+      end
+
+      def transition?
+        false
+      end
+
+      def production?
+        true
+      end
+    end
+  end
+end
diff --git a/tool/lrama/lib/lrama/counterexamples/start_path.rb b/tool/lrama/lib/lrama/counterexamples/start_path.rb
new file mode 100644
index 0000000000..4a6821cd0f
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/start_path.rb
@@ -0,0 +1,21 @@
+module Lrama
+  class Counterexamples
+    class StartPath < Path
+      def initialize(to_state_item)
+        super nil, to_state_item
+      end
+
+      def type
+        :start
+      end
+
+      def transition?
+        false
+      end
+
+      def production?
+        false
+      end
+    end
+  end
+end
diff --git a/tool/lrama/lib/lrama/counterexamples/state_item.rb b/tool/lrama/lib/lrama/counterexamples/state_item.rb
new file mode 100644
index 0000000000..930ff4a5f8
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/state_item.rb
@@ -0,0 +1,6 @@
+module Lrama
+  class Counterexamples
+    class StateItem < Struct.new(:state, :item)
+    end
+  end
+end
diff --git a/tool/lrama/lib/lrama/counterexamples/transition_path.rb b/tool/lrama/lib/lrama/counterexamples/transition_path.rb
new file mode 100644
index 0000000000..96e611612a
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/transition_path.rb
@@ -0,0 +1,17 @@
+module Lrama
+  class Counterexamples
+    class TransitionPath < Path
+      def type
+        :transition
+      end
+
+      def transition?
+        true
+      end
+
+      def production?
+        false
+      end
+    end
+  end
+end
diff --git a/tool/lrama/lib/lrama/counterexamples/triple.rb b/tool/lrama/lib/lrama/counterexamples/triple.rb
new file mode 100644
index 0000000000..e802beccf4
--- /dev/null
+++ b/tool/lrama/lib/lrama/counterexamples/triple.rb
@@ -0,0 +1,21 @@
+module Lrama
+  class Counterexamples
+    # s: state
+    # itm: item within s
+    # l: precise lookahead set
+    class Triple < Struct.new(:s, :itm, :l)
+      alias :state :s
+      alias :item :itm
+      alias :precise_lookahead_set :l
+
+      def state_item
+        StateItem.new(state, item)
+      end
+
+      def inspect
+        "#{state.inspect}. #{item.display_name}. #{l.map(&:id).map(&:s_value)}"
+      end
+      alias :to_s :inspect
+    end
+  end
+end