import re
 
# バックトラッキングの詳細な動作を追跡
 
# パターン: a+b
# 入力: "aaac"
 
# エンジンの動作:
# 位置0: a+ → "aaa" にマッチ(貪欲)
#         b  → 'c' ≠ 'b' → 失敗
#         バックトラック: a+ → "aa" にマッチ
#         b  → 'a' ≠ 'b' → 失敗
#         バックトラック: a+ → "a" にマッチ
#         b  → 'a' ≠ 'b' → 失敗
# 位置1: a+ → "aa" にマッチ
#         b  → 'c' ≠ 'b' → 失敗
#         バックトラック...
# 位置2: a+ → "a" にマッチ
#         b  → 'c' ≠ 'b' → 失敗
# 位置3: a+ → マッチしない
# 結果: マッチなし
 
# このパターンは安全 -- バックトラックは線形回数
 
# 危険なパターン: (a+)+b -- バックトラックが指数的になる

# 各言語のバックトラック制限
#
# Python re:      制限なし（デフォルト）
# Python regex:   timeout パラメータで制限可能
# JavaScript V8:  --regexp-backtracks-limit（デフォルト: 数百万）
# Java:           制限なし（デフォルト）
# .NET:           Regex.MatchTimeout で制限可能
# PCRE2:          pcre2_set_match_limit で制限可能
# Perl:           制限なし（デフォルト）
 
# JavaScript V8 の例:
# node --regexp-backtracks-limit=10000 script.js
 
# .NET の例:
# var regex = new Regex(pattern, RegexOptions.None,
#                       TimeSpan.FromSeconds(1));

import re
import time
 
# 脆弱なパターン: (a+)+b
pattern = re.compile(r'(a+)+b')
 
# 安全な入力: 即座に完了
start = time.time()
pattern.search("aaaaab")
print(f"安全な入力: {time.time() - start:.4f}秒")
 
# 悪意のある入力: 指数的に遅くなる
# 注意: 以下は実行すると非常に遅くなる
for length in [15, 20, 25]:
    malicious = "a" * length + "c"  # マッチしない入力
    start = time.time()
    pattern.search(malicious)
    elapsed = time.time() - start
    print(f"長さ {length}: {elapsed:.4f}秒")
 
# 出力例:
# 長さ 15: 0.01秒
# 長さ 20: 0.30秒
# 長さ 25: 9.50秒    ← 指数的増加!

# === 類型1: 量指定子のネスト ===
 
# パターン: (a+)+
# なぜ危険？
# 内側の a+ は「1個以上のa」にマッチ
# 外側の + は「そのグループを1回以上繰り返す」
# → "aaaa" を (aa)(aa), (a)(aaa), (aaa)(a), (a)(a)(aa), ... と
#   指数的に分割可能
 
# パターン: (\d+)*
# なぜ危険？
# 内側の \d+ は「1個以上の数字」
# 外側の * は「0回以上繰り返す」
# → "12345" を (12)(345), (1)(2345), (123)(45), ... と分割
 
# === 類型2: 選択の重複 ===
 
# パターン: (a|ab)+
# なぜ危険？
# "ab" を a + b としてマッチするか、ab としてマッチするか
# の2通りの選択が毎回発生
# → n個の "ab" の連続に対して 2^n 通り
 
# パターン: (\w|\d)+
# なぜ危険？
# \d は \w に包含される
# 数字に対して \w と \d の両方を試行
# → 数字のみの入力で指数的バックトラック
 
# === 類型3: 量指定子の重複 ===
 
# パターン: \d+\d+\d+
# なぜ危険？
# "12345" を各 \d+ にどう分配するか
# (1)(2)(345), (1)(23)(45), (12)(3)(45), ...
# → 組み合わせが爆発

# 脆弱パターンのカタログ (実行は避けること)
 
vulnerable_patterns = {
    # 量指定子のネスト
    "(a+)+":           "aaaaaaaaaaaaaaac",
    "(a+)+b":          "aaaaaaaaaaaaaaac",
    "(a*)*b":          "aaaaaaaaaaaaaaac",
    "([a-z]+)+$":      "aaaaaaaaaaaaaaa!",
 
    # 選択の重複
    "(a|a)+b":         "aaaaaaaaaaaaaaac",
    "(\\w|\\d)+$":     "aaaaaaaaaaaaaaaa!",
    "(.*a){20}":       "aaaaaaaaaaaaaaaaaaaaX",
 
    # 実世界の脆弱パターン
    # メールアドレス検証
    r"^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@)":
        "aaaaaaaaaaaaaaaaaaaaa!",
 
    # URL 検証
    r"^(https?://)([\w-]+(\.[\w-]+)+)(/[\w-./?%&=]*)*$":
        "http://a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p!",
}

import re
 
# 原則1: 量指定子のネストを排除
 
# NG: (a+)+
# OK: a+
pattern_safe1 = r'a+b'
 
# 原則2: 選択肢の重複を排除
 
# NG: (\w|\d)+  (\w は \d を含む)
# OK: \w+
pattern_safe2 = r'\w+$'
 
# 原則3: 否定文字クラスで明確に制限
 
# NG: ".*"  (貪欲で " を超えてマッチ)
# OK: "[^"]*"  (引用符内のみ)
pattern_safe3 = r'"[^"]*"'
 
# 原則4: アトミックグループまたは独占的量指定子を使用
# (Python regex モジュール、Java、PCRE)
 
# NG: (a+)+b       → バックトラック爆発
# OK: (?>a+)+b     → アトミックグループ (バックトラック禁止)
 
# 原則5: 入力長の制限
# パターン修正だけでなく、入力自体を制限する
 
def safe_match(pattern, text, max_length=10000):
    """入力長を制限した安全なマッチ"""
    if len(text) > max_length:
        raise ValueError(f"入力が長すぎます: {len(text)} > {max_length}")
    return re.search(pattern, text)

import re
 
# 例1: メールアドレス検証
# NG: 脆弱
email_bad = r'^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@)'
 
# OK: 安全で実用的
email_good = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
 
# 例2: HTML タグの内容抽出
# NG: 脆弱 (ネストした量指定子)
tag_bad = r'<(\w+)(\s+\w+="[^"]*")*>'
 
# OK: 安全
tag_good = r'<\w+(?:\s+\w+="[^"]*")*>'
 
# 例3: CSV フィールド
# NG: 脆弱
csv_bad = r'^("(?:[^"]|"")*"|[^,]*)(,("(?:[^"]|"")*"|[^,]*))*$'
 
# OK: フィールド単位で処理
csv_good = r'"(?:[^"]|"")*"|[^,]+'
 
text = '"hello, world","test""quote"",normal'
print(re.findall(csv_good, text))
 
# 例4: 空白の処理
# NG: 脆弱 (\s+\s* のような重複)
whitespace_bad = r'(\s+\w+)*\s*$'
 
# OK: 安全 (明確な区切り)
whitespace_good = r'(?:\s+\w+)*\s*$'
# さらに安全: 否定文字クラスで制限
whitespace_best = r'(?:\s\S+)*\s*$'
 
# 例5: 複数行テキストの処理
# NG: .* が行を超えてマッチ
multiline_bad = r'START.*END'
 
# OK: 行内のみマッチ
multiline_good = r'START[^\n]*END'
# または DOTALL フラグを明示的に制御

# 独占的量指定子 (Possessive Quantifier): X++, X*+, X?+
# アトミックグループ (Atomic Group): (?>X)
#
# どちらもバックトラックを禁止する
# → 一度マッチした文字は手放さない
 
# Python regex モジュールでのアトミックグループ
import regex
 
# 通常の量指定子: バックトラックする
# パターン: a+b に対して "aaac"
# a+ → "aaa" → b期待だがcが来る → バックトラック
# a+ → "aa" → b期待だがaが来る → バックトラック
# ...
 
# アトミックグループ: バックトラックしない
# パターン: (?>a+)b に対して "aaac"
# (?>a+) → "aaa" (バックトラック禁止) → b期待だがcが来る → 即座に失敗
 
pattern_atomic = regex.compile(r'(?>a+)b')
print(pattern_atomic.search("aaab"))   # => マッチ
print(pattern_atomic.search("aaac"))   # => None (即座に失敗)
 
# 独占的量指定子(Java, PCRE2, regex モジュール)
pattern_possessive = regex.compile(r'a++b')
print(pattern_possessive.search("aaab"))   # => マッチ
print(pattern_possessive.search("aaac"))   # => None
 
# ReDoS 対策としてのアトミックグループ
# NG: (a+)+b → バックトラック爆発
# OK: (?>(a+))+b → 内側の a+ がアトミック → 爆発しない
safe_pattern = regex.compile(r'(?>(a+))+b')
import time
start = time.time()
safe_pattern.search("a" * 30 + "c")
print(f"アトミック版: {time.time() - start:.4f}秒")
# => 即座に完了

// Java での独占的量指定子
import java.util.regex.*;
 
public class PossessiveExample {
    public static void main(String[] args) {
        // 通常: バックトラックあり
        Pattern greedy = Pattern.compile("(a+)+b");
 
        // 独占的: バックトラックなし
        Pattern possessive = Pattern.compile("(a++)+b");
 
        String input = "a".repeat(30) + "c";
 
        // 独占的量指定子は即座に失敗する
        long start = System.nanoTime();
        possessive.matcher(input).find();
        long elapsed = System.nanoTime() - start;
        System.out.println("独占的: " + (elapsed / 1_000_000) + "ms");
        // => 独占的: 0ms
    }
}

import re
import signal
 
# Python: signal を使ったタイムアウト(Unix系のみ)
class RegexTimeout(Exception):
    pass
 
def timeout_handler(signum, frame):
    raise RegexTimeout("正規表現がタイムアウトしました")
 
def safe_search(pattern, text, timeout_sec=1):
    """タイムアウト付き正規表現検索"""
    signal.signal(signal.SIGALRM, timeout_handler)
    signal.alarm(timeout_sec)
    try:
        result = re.search(pattern, text)
        signal.alarm(0)  # タイマー解除
        return result
    except RegexTimeout:
        return None
 
# 使用例
result = safe_search(r'(a+)+b', "a" * 30 + "c", timeout_sec=2)
if result is None:
    print("タイムアウトまたはマッチなし")

# multiprocessing を使ったクロスプラットフォームのタイムアウト
import re
from multiprocessing import Process, Queue
import time
 
def regex_worker(pattern_str, text, result_queue):
    """別プロセスで正規表現を実行"""
    try:
        pattern = re.compile(pattern_str)
        result = pattern.search(text)
        result_queue.put(('success', result is not None))
    except Exception as e:
        result_queue.put(('error', str(e)))
 
def safe_regex_search(pattern_str, text, timeout_sec=2):
    """プロセスベースのタイムアウト付き正規表現検索"""
    result_queue = Queue()
    p = Process(target=regex_worker, args=(pattern_str, text, result_queue))
    p.start()
    p.join(timeout=timeout_sec)
 
    if p.is_alive():
        p.terminate()
        p.join()
        return None, "タイムアウト"
 
    if not result_queue.empty():
        status, result = result_queue.get()
        return result, status
 
    return None, "不明なエラー"
 
# 使用例
result, status = safe_regex_search(r'(a+)+b', "a" * 30 + "c", timeout_sec=2)
print(f"結果: {result}, ステータス: {status}")

// JavaScript: 安全な正規表現のサードパーティライブラリ
// re2 パッケージ (RE2 エンジンのバインディング)
// npm install re2
 
// const RE2 = require('re2');
// const pattern = new RE2('(a+)+b');
// RE2 ではこれは自動的に最適化される
 
// Worker を使ったタイムアウト
function safeRegexTest(pattern, text, timeoutMs = 1000) {
    return new Promise((resolve, reject) => {
        const worker = new Worker(
            URL.createObjectURL(new Blob([`
                self.onmessage = function(e) {
                    const regex = new RegExp(e.data.pattern);
                    const result = regex.test(e.data.text);
                    self.postMessage({ result });
                };
            `]))
        );
 
        const timer = setTimeout(() => {
            worker.terminate();
            reject(new Error('Regex timeout'));
        }, timeoutMs);
 
        worker.onmessage = (e) => {
            clearTimeout(timer);
            worker.terminate();
            resolve(e.data.result);
        };
 
        worker.postMessage({ pattern: pattern.source, text });
    });
}

import re
import time
 
text = "The quick brown fox jumps over the lazy dog" * 1000
 
# NG: ループ内で毎回コンパイル
start = time.time()
for _ in range(10000):
    re.search(r'\b\w{5}\b', text)
time_uncompiled = time.time() - start
 
# OK: 事前コンパイル
pattern = re.compile(r'\b\w{5}\b')
start = time.time()
for _ in range(10000):
    pattern.search(text)
time_compiled = time.time() - start
 
print(f"未コンパイル: {time_uncompiled:.3f}秒")
print(f"コンパイル済: {time_compiled:.3f}秒")
# コンパイル済みのほうが高速(特に繰り返し使用時)
 
# 注: Python は内部的にキャッシュ(最大512個)を持つが
# 明示的なコンパイルが推奨される

import re
import time
 
# アンカーがあるとエンジンが不要な位置をスキップできる
 
text = "2024-01-15 Some log entry here" * 10000
 
# 遅い: 全位置で試行
slow = r'\d{4}-\d{2}-\d{2}'
 
# 速い: 行頭のみで試行
fast = r'^\d{4}-\d{2}-\d{2}'
 
# 速い: 単語境界で限定
fast2 = r'\b\d{4}-\d{2}-\d{2}\b'
 
# ベンチマーク
for label, pattern in [("アンカーなし", slow), ("^付き", fast), ("\\b付き", fast2)]:
    compiled = re.compile(pattern)
    start = time.time()
    for _ in range(1000):
        compiled.search(text)
    elapsed = time.time() - start
    print(f"  {label}: {elapsed:.4f}秒")

import re
import time
 
html = '<div class="test">' * 10000 + 'content</div>'
 
# 遅い: 怠惰量指定子(バックトラックが発生)
start = time.time()
re.search(r'<div.*?>', html)
lazy_time = time.time() - start
 
# 速い: 否定文字クラス(バックトラックなし)
start = time.time()
re.search(r'<div[^>]*>', html)
negated_time = time.time() - start
 
print(f"怠惰量指定子: {lazy_time:.6f}秒")
print(f"否定文字クラス: {negated_time:.6f}秒")
 
# なぜ否定文字クラスが速いのか？
#
# 怠惰量指定子 .*?> の動作:
#   1. .  にマッチ (0文字から開始)
#   2. > を試行 → 失敗
#   3. . にもう1文字マッチ
#   4. > を試行 → 失敗
#   5. 繰り返し... (毎回2ステップ)
#
# 否定文字クラス [^>]*> の動作:
#   1. [^>]* で > 以外の文字を一気にマッチ
#   2. > を試行 → 成功
#   (バックトラックが発生しない)

import re
 
# 1. 固定文字列の先行チェック
text = "long text without the target pattern..."
 
# 遅い: 毎回正規表現で検索
if re.search(r'target\s+\w+\s+pattern', text):
    pass
 
# 速い: 文字列検索で先行チェック
if 'target' in text and 'pattern' in text:
    if re.search(r'target\s+\w+\s+pattern', text):
        pass
 
# 2. 固定プレフィックスの活用
# エンジンは固定プレフィックスを最適化できる
 
# 最適化しやすい: 固定文字列で始まる
good = r'ERROR: \w+'
 
# 最適化しにくい: 可変パターンで始まる
bad = r'.*ERROR: \w+'
 
# 3. 不要なキャプチャを排除
# キャプチャグループ → 非キャプチャグループ
slow = r'(https?)://([\w.]+)/([\w/]+)'
fast = r'(?:https?)://(?:[\w.]+)/(?:[\w/]+)'
 
# 4. 選択の順序最適化
# 頻度の高い選択肢を先に
slow_alt = r'(?:rare_pattern|common_pattern)'
fast_alt = r'(?:common_pattern|rare_pattern)'
 
# 5. 具体的な文字クラスの使用
# 遅い: .* (何でもマッチ → バックトラックの元)
slow_dot = r'<.*>'
# 速い: [^>]* (限定的 → バックトラック最小化)
fast_neg = r'<[^>]*>'
 
# 6. 必要な部分だけマッチ
# 遅い: 全体をマッチしてからグループを取得
slow_full = r'^.*?(\d{4}-\d{2}-\d{2}).*$'
# 速い: 必要な部分だけを探す
fast_part = r'\d{4}-\d{2}-\d{2}'

import re
import time
 
# 大量のログファイル処理の最適化
 
def benchmark(name, func, lines, iterations=3):
    """ベンチマーク実行"""
    times = []
    for _ in range(iterations):
        start = time.perf_counter()
        func(lines)
        times.append(time.perf_counter() - start)
    avg = sum(times) / len(times)
    print(f"  {name}: {avg:.4f}秒 (平均)")
 
# テストデータ生成
log_lines = []
for i in range(100000):
    if i % 3 == 0:
        log_lines.append(f"2024-01-15 10:30:{i%60:02d} [ERROR] Something failed: {i}")
    elif i % 3 == 1:
        log_lines.append(f"2024-01-15 10:30:{i%60:02d} [INFO] Processing item {i}")
    else:
        log_lines.append(f"some other line without timestamp {i}")
 
# 方法1: ナイーブ（毎行で re.search）
def naive_search(lines):
    results = []
    for line in lines:
        m = re.search(r'\[ERROR\]', line)
        if m:
            results.append(line)
    return results
 
# 方法2: プリコンパイル
error_pattern = re.compile(r'\[ERROR\]')
def compiled_search(lines):
    results = []
    for line in lines:
        if error_pattern.search(line):
            results.append(line)
    return results
 
# 方法3: 文字列検索で先行フィルタ
def prefiltered_search(lines):
    results = []
    for line in lines:
        if '[ERROR]' in line:
            results.append(line)
    return results
 
# 方法4: リスト内包表記（Python最適化）
def list_comp_search(lines):
    return [line for line in lines if '[ERROR]' in line]
 
# ベンチマーク実行
print("ベンチマーク結果 (10万行):")
benchmark("ナイーブ re.search", naive_search, log_lines)
benchmark("プリコンパイル", compiled_search, log_lines)
benchmark("文字列先行フィルタ", prefiltered_search, log_lines)
benchmark("リスト内包表記", list_comp_search, log_lines)

import re
import time
 
# いつ正規表現を使い、いつ文字列操作を使うべきか
 
text = "user@example.com" * 10000
 
# タスク: "@" を含むかチェック
 
# 方法1: re.search
pattern = re.compile(r'@')
start = time.perf_counter()
for _ in range(100000):
    pattern.search(text)
regex_time = time.perf_counter() - start
 
# 方法2: in 演算子
start = time.perf_counter()
for _ in range(100000):
    '@' in text
string_time = time.perf_counter() - start
 
print(f"re.search: {regex_time:.4f}秒")
print(f"in 演算子: {string_time:.4f}秒")
print(f"速度比: {regex_time / string_time:.1f}x")
 
# 一般的なガイドライン:
# - 単純な文字列検索 → in, find(), startswith(), endswith()
# - パターンマッチ → 正規表現
# - 文字列置換(固定) → str.replace()
# - 文字列置換(パターン) → re.sub()
# - 文字列分割(固定) → str.split()
# - 文字列分割(パターン) → re.split()

import re
 
class InputValidator:
    """多層防御による入力検証"""
 
    def __init__(self, max_length=1000, allowed_chars=None,
                 pattern=None, timeout_sec=1):
        self.max_length = max_length
        self.allowed_chars = allowed_chars
        self.pattern = re.compile(pattern) if pattern else None
        self.timeout_sec = timeout_sec
 
    def validate(self, value: str) -> tuple[bool, str]:
        """入力値を検証"""
        # Layer 1: 長さ制限
        if not value:
            return False, "空の入力"
        if len(value) > self.max_length:
            return False, f"入力が長すぎます ({len(value)} > {self.max_length})"
 
        # Layer 2: 文字種制限
        if self.allowed_chars:
            invalid = set(value) - set(self.allowed_chars)
            if invalid:
                return False, f"許可されていない文字: {invalid}"
 
        # Layer 3: 正規表現チェック
        if self.pattern:
            if not self.pattern.match(value):
                return False, "パターンに一致しません"
 
        return True, "OK"
 
# 使用例: メールアドレスバリデータ
email_validator = InputValidator(
    max_length=254,
    pattern=r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
)
 
test_emails = [
    "user@example.com",
    "a" * 300 + "@test.com",
    "invalid-email",
    "<script>alert('xss')</script>@evil.com",
]
 
for email in test_emails:
    valid, msg = email_validator.validate(email)
    print(f"  {email[:40]:40s} => {msg}")

import re
 
# NG: ユーザー入力をそのまま正規表現として使用
def search_bad(user_input: str, text: str):
    return re.search(user_input, text)  # ReDoS攻撃が可能!
 
# 攻撃例:
# user_input = "(a+)+b"
# text = "a" * 30 + "c"
# → CPU が100%に
 
# OK: ユーザー入力はエスケープする
def search_safe(user_input: str, text: str):
    escaped = re.escape(user_input)  # メタ文字を全てエスケープ
    return re.search(escaped, text)
 
# OK: または DFA エンジンを使う
# import re2
# def search_safe_re2(pattern: str, text: str):
#     return re2.search(pattern, text)  # O(n) 保証
 
# OK: 制限付きの正規表現サブセットのみ許可
def search_limited(user_pattern: str, text: str, max_length=100):
    """安全な正規表現サブセットのみ許可"""
    if len(user_pattern) > max_length:
        raise ValueError("パターンが長すぎます")
 
    # 危険な構文を検出
    dangerous = [
        r'\(.+[+*]\).+[+*]',  # ネストした量指定子
        r'\(\?\:.*\|.*\)[+*]', # 選択の繰り返し
    ]
    for d in dangerous:
        if re.search(d, user_pattern):
            raise ValueError("危険なパターンが検出されました")
 
    return re.search(user_pattern, text)

import re
 
# WAF ルールの安全な設計
 
# NG: 危険な WAF ルール
waf_rules_bad = {
    'sql_injection': r"('.+--)|(--.+')",  # ネストなし但し .+ は危険
    'xss': r"(<script.*>.*</script.*>)",  # .* が危険
}
 
# OK: 安全な WAF ルール
waf_rules_good = {
    'sql_injection': r"(?:'\s*(?:--|;|/\*)|(?:--|;|/\*)\s*')",
    'xss': r"<script[^>]*>[^<]*</script[^>]*>",
    'path_traversal': r"(?:\.\./|\.\.\\){2,}",
}
 
def check_waf_rules(input_text: str, rules: dict) -> list[str]:
    """WAF ルールに基づく入力チェック"""
    violations = []
    for rule_name, pattern in rules.items():
        compiled = re.compile(pattern, re.IGNORECASE)
        if compiled.search(input_text):
            violations.append(rule_name)
    return violations
 
# テスト
test_inputs = [
    "normal input",
    "'; DROP TABLE users; --",
    "<script>alert('xss')</script>",
    "../../../etc/passwd",
]
 
for inp in test_inputs:
    violations = check_waf_rules(inp, waf_rules_good)
    if violations:
        print(f"  [BLOCKED] '{inp[:40]}' => {violations}")
    else:
        print(f"  [PASS]    '{inp[:40]}'")

import re
import time
import statistics
 
class RegexBenchmark:
    """正規表現のパフォーマンスベンチマーク"""
 
    def __init__(self, pattern: str, description: str = ""):
        self.pattern = re.compile(pattern)
        self.pattern_str = pattern
        self.description = description
 
    def run(self, text: str, iterations: int = 1000,
            warmup: int = 100) -> dict:
        """ベンチマークを実行"""
        # ウォームアップ
        for _ in range(warmup):
            self.pattern.search(text)
 
        # 計測
        times = []
        for _ in range(iterations):
            start = time.perf_counter_ns()
            self.pattern.search(text)
            elapsed = time.perf_counter_ns() - start
            times.append(elapsed)
 
        return {
            'pattern': self.pattern_str,
            'description': self.description,
            'iterations': iterations,
            'min_ns': min(times),
            'max_ns': max(times),
            'mean_ns': statistics.mean(times),
            'median_ns': statistics.median(times),
            'stdev_ns': statistics.stdev(times) if len(times) > 1 else 0,
            'p95_ns': sorted(times)[int(len(times) * 0.95)],
            'p99_ns': sorted(times)[int(len(times) * 0.99)],
        }
 
    def print_result(self, result: dict):
        """結果を表示"""
        print(f"パターン: {result['pattern']}")
        print(f"説明: {result['description']}")
        print(f"  平均: {result['mean_ns']/1000:.2f}μs")
        print(f"  中央値: {result['median_ns']/1000:.2f}μs")
        print(f"  P95: {result['p95_ns']/1000:.2f}μs")
        print(f"  P99: {result['p99_ns']/1000:.2f}μs")
        print()
 
# 使用例
text = "The quick brown fox jumps over the lazy dog" * 100
 
benchmarks = [
    RegexBenchmark(r'\bfox\b', '単語境界マッチ'),
    RegexBenchmark(r'fox', 'シンプルマッチ'),
    RegexBenchmark(r'(?<=\s)fox(?=\s)', 'ルックアラウンドマッチ'),
    RegexBenchmark(r'.*fox.*', '.* マッチ'),
    RegexBenchmark(r'[^ ]*fox[^ ]*', '否定文字クラスマッチ'),
]
 
print("=== ベンチマーク結果 ===\n")
for bench in benchmarks:
    result = bench.run(text)
    bench.print_result(result)

import re
import time
 
def scalability_test(pattern_str: str, char: str = 'a',
                     lengths: list[int] = None):
    """入力長に対するスケーラビリティをテスト"""
    if lengths is None:
        lengths = [10, 50, 100, 500, 1000, 5000, 10000]
 
    pattern = re.compile(pattern_str)
    print(f"パターン: {pattern_str}")
    print(f"{'長さ':>10s} {'時間(μs)':>12s} {'比率':>8s}")
    print("-" * 35)
 
    prev_time = None
    for n in lengths:
        text = char * n
        start = time.perf_counter()
        pattern.search(text)
        elapsed = (time.perf_counter() - start) * 1_000_000  # μs
 
        ratio = f"{elapsed / prev_time:.1f}x" if prev_time else "-"
        prev_time = elapsed
 
        print(f"{n:>10d} {elapsed:>12.2f} {ratio:>8s}")
 
        # 安全のため1秒超えたら中断
        if elapsed > 1_000_000:
            print("  [中断: 1秒超過]")
            break
 
# テスト
print("=== 安全なパターン ===")
scalability_test(r'[a-z]+$')
print()
 
print("=== 線形パターン(否定文字クラス) ===")
scalability_test(r'[^b]*b')
print()
 
# 注意: 以下は長い入力で極めて遅くなる可能性がある
# print("=== 危険なパターン ===")
# scalability_test(r'(a+)+b', lengths=[10, 15, 20, 25])

import re
 
# Python での ReDoS 対策
 
# 対策1: regex モジュールの timeout パラメータ
import regex
try:
    result = regex.search(r'(a+)+b', 'a' * 30 + 'c', timeout=1)
except TimeoutError:
    print("タイムアウト")
 
# 対策2: google-re2 パッケージ
# pip install google-re2
# import re2
# result = re2.search(r'(a+)+b', 'a' * 30 + 'c')
# RE2 は自動的に安全なパターンに変換
 
# 対策3: パターンの静的解析
def audit_pattern(pattern_str: str) -> list[str]:
    """パターンの安全性を監査"""
    warnings = []
 
    # 量指定子のネスト
    if re.search(r'\([^)]*[+*][^)]*\)[+*]', pattern_str):
        warnings.append("量指定子のネスト")
 
    # .* のアンカーなし使用
    if '.*' in pattern_str and not pattern_str.startswith('^'):
        warnings.append("アンカーなしの .*")
 
    # 巨大な繰り返し
    large_repeat = re.search(r'\{(\d+)\}', pattern_str)
    if large_repeat and int(large_repeat.group(1)) > 1000:
        warnings.append(f"大きな繰り返し回数: {large_repeat.group(1)}")
 
    return warnings
 
# テスト
patterns = [
    r'(a+)+b',
    r'^[a-z]+$',
    r'.*error.*',
    r'a{10000}',
]
 
for p in patterns:
    warnings = audit_pattern(p)
    status = "WARN" if warnings else "OK"
    print(f"  [{status}] {p}: {warnings or 'clean'}")

// JavaScript / Node.js での ReDoS 対策
 
// 対策1: re2 パッケージを使用
// const RE2 = require('re2');
// const safe = new RE2('(a+)+b');
 
// 対策2: safe-regex パッケージで静的解析
// const safe = require('safe-regex');
// if (!safe(userPattern)) {
//     throw new Error('Unsafe regex pattern');
// }
 
// 対策3: vm モジュールでサンドボックス実行
// const vm = require('vm');
// const script = new vm.Script(`
//     const result = /${pattern}/.test(input);
// `);
// const context = vm.createContext({ input, pattern });
// script.runInContext(context, { timeout: 1000 });
 
// 対策4: Node.js v20+ の RegExp タイムアウト (experimental)
// --experimental-regexp-engine を使用すると
// RE2 風の安全なエンジンが利用可能になる場合がある
 
// ベストプラクティス:
// 1. ユーザー入力は必ずエスケープ
function escapeRegex(str) {
    return str.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
}
 
// 2. パターンの複雑さを制限
function isPatternSafe(pattern) {
    // ネストした量指定子を検出
    if (/\(.+[+*]\).+[+*]/.test(pattern)) return false;
    // パターン長を制限
    if (pattern.length > 200) return false;
    return true;
}
 
// 3. 入力長を制限
function safeMatch(pattern, text, maxLength) {
    maxLength = maxLength || 10000;
    if (text.length > maxLength) {
        throw new Error('Input too long');
    }
    return new RegExp(pattern).test(text);
}

import java.util.regex.*;
import java.util.concurrent.*;
 
public class SafeRegex {
 
    // 対策1: タイムアウト付き正規表現マッチ
    public static boolean safeMatch(String pattern, String text,
                                     long timeoutMs)
            throws TimeoutException {
        ExecutorService executor = Executors.newSingleThreadExecutor();
        Future<Boolean> future = executor.submit(() -> {
            Pattern p = Pattern.compile(pattern);
            return p.matcher(text).matches();
        });
 
        try {
            return future.get(timeoutMs, TimeUnit.MILLISECONDS);
        } catch (TimeoutException e) {
            future.cancel(true);
            throw e;
        } catch (Exception e) {
            throw new RuntimeException(e);
        } finally {
            executor.shutdownNow();
        }
    }
 
    // 対策2: 独占的量指定子の使用
    public static void possessiveExample() {
        // 通常: バックトラックあり
        Pattern greedy = Pattern.compile("(a+)+b");
 
        // 独占的: バックトラック禁止
        Pattern possessive = Pattern.compile("(a++)+b");
 
        // アトミックグループ
        Pattern atomic = Pattern.compile("(?>a+)+b");
    }
 
    // 対策3: パターンの事前検証
    public static boolean isPatternSafe(String pattern) {
        // ネストした量指定子を検出
        if (pattern.matches(".*\\(.+[+*]\\).+[+*].*")) {
            return false;
        }
        // パターン長の制限
        if (pattern.length() > 200) {
            return false;
        }
        return true;
    }
}

package main
 
import (
    "fmt"
    "regexp"
    "time"
)
 
func main() {
    // Go の regexp パッケージは RE2 ベース
    // → ReDoS に対して本質的に安全
 
    pattern := regexp.MustCompile(`(a+)+b`)
    input := string(make([]byte, 30)) + "c"
    for i := range input[:30] {
        input = input[:i] + "a" + input[i+1:]
    }
 
    start := time.Now()
    pattern.MatchString("a]" + input)
    elapsed := time.Since(start)
    fmt.Printf("RE2: %v\n", elapsed)
    // => 常に高速(O(n))
 
    // ただし RE2 の制約:
    // - 後方参照 (\1) 不可
    // - ルックアラウンド (?=) (?<=) 不可
    // - 独占的量指定子 (a++) 不可（不要）
    // - アトミックグループ (?>...) 不可（不要）
 
    // 制約がある機能が必要な場合:
    // github.com/dlclark/regexp2 パッケージを使用
    // ただし ReDoS リスクが発生する
}

use regex::Regex;
use std::time::Instant;
 
fn main() {
    // Rust の regex クレートは RE2 同様の DFA ベース
    // → ReDoS に対して本質的に安全
 
    let re = Regex::new(r"(a+)+b").unwrap();
    // 注: Rust regex は自動的に安全なパターンに変換する
 
    let input = "a".repeat(100) + "c";
    let start = Instant::now();
    re.is_match(&input);
    let elapsed = start.elapsed();
    println!("Rust regex: {:?}", elapsed);
    // => 常に高速(O(n))
 
    // ルックアラウンドが必要な場合:
    // fancy-regex クレートを使用
    // use fancy_regex::Regex;
    // ただし ReDoS リスクが発生する
 
    // regex クレートの制約:
    // - 後方参照不可
    // - ルックアラウンド不可
    // - コンパイル時間の制限あり
    //   (複雑すぎるパターンはコンパイルエラー)
}

# recheck: 正規表現の脆弱性を検出
# npm install -g recheck
# recheck "(a+)+b"
 
# redos-checker (Python)
# pip install redos-checker
 
# safe-regex (JavaScript)
# npm install safe-regex
 
# semgrep: コード全体の静的解析
# semgrep --config "p/regex-dos" .

// safe-regex の使用例
// const safe = require('safe-regex');
// console.log(safe('(a+)+b'));      // => false (脆弱)
// console.log(safe('[a-z]+'));       // => true  (安全)
// console.log(safe('(a|b|c)+'));     // => true  (安全)

import re
 
def is_potentially_vulnerable(pattern: str) -> tuple[bool, list[str]]:
    """正規表現パターンの脆弱性を簡易チェック"""
    warnings = []
 
    # 量指定子のネスト検出
    if re.search(r'\([^)]*[+*][^)]*\)[+*]', pattern):
        warnings.append("量指定子のネストが検出されました")
 
    # .* の無制限使用検出
    if re.search(r'\.\*(?!\?)', pattern) and '^' not in pattern:
        warnings.append("アンカーなしの .* が検出されました")
 
    # 選択肢の重複検出(簡易)
    if re.search(r'\((?:[^)]*\|[^)]*)\)[+*]', pattern):
        warnings.append("選択肢を含む繰り返しが検出されました")
 
    # 巨大な繰り返し回数
    large_repeat = re.search(r'\{(\d+)', pattern)
    if large_repeat and int(large_repeat.group(1)) > 1000:
        warnings.append(f"大きな繰り返し回数: {large_repeat.group(1)}")
 
    # バックリファレンスの使用
    if re.search(r'\\[1-9]', pattern):
        warnings.append("後方参照が使用されています（パフォーマンスに注意）")
 
    return (len(warnings) > 0, warnings)
 
# テスト
patterns = [
    r'(a+)+b',
    r'(\w|\d)+',
    r'[a-z]+',
    r'.*error.*',
    r'^[a-z]+$',
    r'(\w+\.)+\w+',
    r'(.)\1{100}',
    r'a{10000}',
]
 
for p in patterns:
    vulnerable, msgs = is_potentially_vulnerable(p)
    status = "脆弱" if vulnerable else "安全"
    print(f"  {status}: {p}")
    for msg in msgs:
        print(f"    - {msg}")

#!/usr/bin/env python3
"""
regex_audit.py -- CI/CDパイプラインで正規表現を監査するスクリプト
 
使用方法:
    python regex_audit.py path/to/source/
 
戻り値:
    0: 問題なし
    1: 警告あり
    2: 危険なパターンあり
"""
 
import re
import sys
import os
 
def find_regex_patterns(filepath: str) -> list[tuple[int, str]]:
    """ソースコードから正規表現パターンを抽出"""
    patterns = []
 
    # Python: re.compile(), re.search(), re.match() 等
    regex_call = re.compile(
        r're\.(?:compile|search|match|findall|sub|split)\s*\(\s*'
        r'(?:r)?"\'["\']'
    )
 
    try:
        with open(filepath, 'r', encoding='utf-8') as f:
            for lineno, line in enumerate(f, 1):
                for m in regex_call.finditer(line):
                    patterns.append((lineno, m.group(1)))
    except (UnicodeDecodeError, PermissionError):
        pass
 
    return patterns
 
def audit_pattern(pattern: str) -> list[str]:
    """パターンの安全性を監査"""
    warnings = []
 
    # 量指定子のネスト
    if re.search(r'\([^)]*[+*][^)]*\)[+*]', pattern):
        warnings.append("CRITICAL: 量指定子のネスト")
 
    # .* のアンカーなし使用
    if '.*' in pattern and not pattern.startswith('^'):
        warnings.append("WARNING: アンカーなしの .*")
 
    # 巨大な繰り返し
    repeat = re.search(r'\{(\d+)', pattern)
    if repeat and int(repeat.group(1)) > 100:
        warnings.append(f"WARNING: 大きな繰り返し回数: {repeat.group(1)}")
 
    return warnings
 
def main():
    if len(sys.argv) < 2:
        print("Usage: python regex_audit.py <path>")
        sys.exit(1)
 
    path = sys.argv[1]
    exit_code = 0
 
    for root, dirs, files in os.walk(path):
        for filename in files:
            if filename.endswith('.py'):
                filepath = os.path.join(root, filename)
                patterns = find_regex_patterns(filepath)
                for lineno, pattern in patterns:
                    warnings = audit_pattern(pattern)
                    for w in warnings:
                        print(f"{filepath}:{lineno}: {w}: {pattern}")
                        if 'CRITICAL' in w:
                            exit_code = max(exit_code, 2)
                        elif 'WARNING' in w:
                            exit_code = max(exit_code, 1)
 
    if exit_code == 0:
        print("All regex patterns passed audit.")
    sys.exit(exit_code)
 
if __name__ == '__main__':
    main()

import re
 
# 良いドキュメント化の例
EMAIL_PATTERN = re.compile(
    r'''
    ^                       # 文字列の先頭
    [a-zA-Z0-9._%+-]+      # ローカルパート: 英数字と特殊文字
    @                       # @ 記号
    [a-zA-Z0-9.-]+          # ドメイン: 英数字、ドット、ハイフン
    \.                      # ドットセパレータ
    [a-zA-Z]{2,}            # TLD: 2文字以上のアルファベット
    $                       # 文字列の末尾
    ''',
    re.VERBOSE              # 空白とコメントを許可
)
 
# VERBOSE フラグなしの場合はコメントで補足
# RFC 5322 簡易版。国際化ドメインは未対応。
# ReDoS 安全性: OK（量指定子のネストなし、否定文字クラス使用）
# 最大入力長: 254文字に制限すること

import re
 
# NG: ユーザー入力をそのまま正規表現として使用
def search_bad(user_input: str, text: str):
    return re.search(user_input, text)  # ReDoS攻撃が可能!
 
# OK: ユーザー入力はエスケープする
def search_safe(user_input: str, text: str):
    escaped = re.escape(user_input)  # メタ文字を全てエスケープ
    return re.search(escaped, text)

import re
 
# NG: 大量のログを非効率に処理
def process_logs_bad(log_lines: list[str]):
    results = []
    for line in log_lines:
        # 毎行で複雑な正規表現を実行
        m = re.search(r'(\d{4}-\d{2}-\d{2})\s+(\d{2}:\d{2}:\d{2})\s+\[(\w+)\]\s+(.*)', line)
        if m:
            results.append(m.groups())
    return results
 
# OK: プリコンパイル + 先行フィルタ
def process_logs_good(log_lines: list[str]):
    pattern = re.compile(
        r'(\d{4}-\d{2}-\d{2})\s+(\d{2}:\d{2}:\d{2})\s+\[(\w+)\]\s+(.*)'
    )
    results = []
    for line in log_lines:
        if '[' in line:  # 先行フィルタ: [ を含む行のみ処理
            m = pattern.search(line)
            if m:
                results.append(m.groups())
    return results

import re
 
# NG: 単純な操作に正規表現を使う
def check_email_bad(email):
    return bool(re.match(r'.+@.+', email))
 
# OK: 文字列操作で十分
def check_email_good(email):
    return '@' in email and '.' in email.split('@')[1]
 
# NG: 固定文字列の置換に正規表現
text = "Hello World"
result_bad = re.sub(r'World', 'Python', text)
 
# OK: str.replace() を使う
result_good = text.replace('World', 'Python')
 
# NG: 固定文字列での分割に正規表現
data = "a,b,c,d"
parts_bad = re.split(r',', data)
 
# OK: str.split() を使う
parts_good = data.split(',')

import re, time
 
def stress_test(pattern_str, char='a', max_len=30):
    pattern = re.compile(pattern_str)
    for n in range(10, max_len + 1, 5):
        text = char * n + '!'
        start = time.time()
        pattern.search(text)
        elapsed = time.time() - start
        print(f"  n={n}: {elapsed:.4f}秒")
        if elapsed > 1.0:
            print("  → 脆弱性あり!")
            break

# regex モジュールのタイムアウト
import regex
try:
    result = regex.search(r'(a+)+b', 'a' * 30 + 'c', timeout=1)
except TimeoutError:
    print("タイムアウト")

# 固定文字列の検索 → in 演算子
if 'error' in log_line:  # re.search(r'error', log_line) より速い
 
# 先頭/末尾の一致 → startswith() / endswith()
if filename.endswith('.py'):  # re.match(r'.*\.py$', filename) より速い
 
# 単純な分割 → str.split()
fields = line.split(',')  # re.split(r',', line) より速い
 
# 単純な置換 → str.replace()
result = text.replace('old', 'new')  # re.sub(r'old', 'new', text) より速い
 
# 構造化データのパース → 専用パーサー
import json  # JSON には json モジュール
import csv   # CSV には csv モジュール
# HTML → Beautiful Soup / lxml
# XML → ElementTree
# URL → urllib.parse

# 怠惰量指定子: .*? (バックトラックが発生する)
# 否定文字クラス: [^X]* (バックトラックが発生しない)
 
# 例: HTML タグの属性値を抽出
# 遅い: <div class=".*?">
# 速い: <div class="[^"]*">
 
# 例: 引用符内の文字列を抽出
# 遅い: ".*?"
# 速い: "[^"]*"
 
# 例: コメントの抽出
# 遅い: /\*.*?\*/  (DOTALL 必要)
# 速い: /\*[^*]*\*+(?:[^/*][^*]*\*+)*/
# ↑ 複雑になる場合は可読性とのトレードオフ