From a1b01e7701f9fc370f8dff777aad6d39a2c5a3e3 Mon Sep 17 00:00:00 2001
From: Yuichiro Kaneko <spiketeika@gmail.com>
Date: Fri, 12 May 2023 18:25:10 +0900
Subject: Use Lrama LALR parser generator instead of Bison

https://bugs.ruby-lang.org/issues/19637

Co-authored-by: Nobuyoshi Nakada <nobu@ruby-lang.org>
---
 tool/lrama/lib/lrama/digraph.rb | 53 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)
 create mode 100644 tool/lrama/lib/lrama/digraph.rb

(limited to 'tool/lrama/lib/lrama/digraph.rb')

diff --git a/tool/lrama/lib/lrama/digraph.rb b/tool/lrama/lib/lrama/digraph.rb
new file mode 100644
index 0000000000..28f26781b1
--- /dev/null
+++ b/tool/lrama/lib/lrama/digraph.rb
@@ -0,0 +1,53 @@
+module Lrama
+  # Algorithm Digraph of https://dl.acm.org/doi/pdf/10.1145/69622.357187 (P. 625)
+  class Digraph
+    def initialize(sets, relation, base_function)
+      # X in the paper
+      @sets = sets
+      # R in the paper
+      @relation = relation
+      # F' in the paper
+      @base_function = base_function
+      # S in the paper
+      @stack = []
+      # N in the paper
+      @h = Hash.new(0)
+      # F in the paper
+      @result = {}
+    end
+
+    def compute
+      @sets.each do |x|
+        next if @h[x] != 0
+        traverse(x)
+      end
+
+      return @result
+    end
+
+    private
+
+    def traverse(x)
+      @stack.push(x)
+      d = @stack.count
+      @h[x] = d
+      @result[x] = @base_function[x] # F x = F' x
+
+      @relation[x] && @relation[x].each do |y|
+        traverse(y) if @h[y] == 0
+        @h[x] = [@h[x], @h[y]].min
+        @result[x] |= @result[y] # F x = F x + F y
+      end
+
+      if @h[x] == d
+        while true do
+          z = @stack.pop
+          @h[z] = Float::INFINITY
+          @result[z] = @result[x] # F (Top of S) = F x
+
+          break if z == x
+        end
+      end
+    end
+  end
+end
-- 
cgit v1.2.3