はじめての正規表現とベストプラクティス11: 最もシンプルなReDoSと回避方法

SpaceMatcherNoRegexが正規表現を使わない方法です。

比較対象となるSpaceMatcherRegexの正規表現は、今回最も高速だった絶対最大量指定子による[ ]++$を使いました。

# Copilot経由でGemini 3 Previewを用いて生成
require 'benchmark'

# Match result type
Match = Data.define(:begin_pos, :end_pos)

class SpaceMatcherRegex
  # Possessive quantifier for trailing spaces
  TRAIL_RE = /[ ]++$/

  def initialize(text)
    @text = text
  end

  def match
    results = []
    offset = 0

    @text.each_line do |line|
      # Remove newlines manually to match the logic provided
      s = line.delete_suffix("\n").delete_suffix("\r")

      if (m = TRAIL_RE.match(s))
        results << Match.new(
          begin_pos: offset + m.begin(0),
          end_pos:   offset + m.end(0)
        )
      end

      offset += line.length
    end

    results
  end
end

class SpaceMatcherNoRegex
  def initialize(text)
    @text = text
  end

  def match
    results = []
    offset = 0

    @text.each_line do |line|
      # Calculate content length without trailing newline
      len = line.length
      content_len = len
      if line.end_with?("\n")
        content_len -= 1
        if content_len > 0 && line[content_len - 1] == "\r"
          content_len -= 1
        end
      end

      # Scan backwards from the end of content
      # We want to find a sequence of spaces at the end of the content.
      # i points to the character we are checking.
      i = content_len - 1
      while i >= 0 && line[i] == ' '
        i -= 1
      end

      # i is now the index of the last non-space character.
      # The spaces start at i + 1.
      start_index = i + 1

      # Check if we found any spaces at the end
      if start_index < content_len
        results << Match.new(
          begin_pos: offset + start_index,
          end_pos:   offset + content_len
        )
      end

      offset += len
    end

    results
  end
end

# Test string as requested
text = " " * 100_000 + "1"

puts "Benchmarking with text length: #{text.length}"

# Verify correctness (simple verification, though intended for benchmark)
r1 = SpaceMatcherRegex.new(text).match
r2 = SpaceMatcherNoRegex.new(text).match

# Since the test string ends in "1", there are no trailing spaces at the end of the line.
# Let's add a case aimed at matching trailing spaces too for verification.
text_match = "1" + " " * 100_000
r1_match = SpaceMatcherRegex.new(text_match).match
r2_match = SpaceMatcherNoRegex.new(text_match).match

if r1_match != r2_match
  puts "WARNING: Results do not match!"
  puts "Regex:    #{r1_match.inspect}"
  puts "No Regex: #{r2_match.inspect}"
end

Benchmark.bm(15) do |x|
  x.report("Regex ([ ]++$):") do
    100.times { SpaceMatcherRegex.new(text).match }
  end

  x.report("No Regex:") do
    100.times { SpaceMatcherNoRegex.new(text).match }
  end
end