Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

Catastrophic Backtracking while using `Binds`

オープン
  • 何か問題がありますか？
#411 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
35/100
issue の種類
バグ
明瞭さ
おおむね明確
活発さ
停滞
技術スタック
python
領域
cli, devtools

調査の方向性

iotedgehubdev/compose_parser.py の MOUNT_WIN_REGEX と iotedgehubdev/constants.py の MOUNT_MODE_REGEX から始め、次に、深さを増した Windows バインドを使って報告された実行時間を再現します。createOptions がパターンをどのように適用するかを追跡し、大文字を含む有効なパスで matching 時間が指数関数的に増加しなくなったことを確認します。

索引モデルが issue の本文から書いたものです。

説明

Trying to use Binds in createOptions (binding Windows directory to Linux container) seems to raise catastrophic backtracking. The pattern responsible is MOUNT_WIN_REGEX
https://github.com/Azure/iotedgehubdev/blob/7eede7286a0603e565c8b183d090f2585521aae6/iotedgehubdev/compose_parser.py#L190

The following is the result of applying MOUNT_WIN_REGEX on different binds:

C:/:/app/ took 0.009343099998659454
C:/Folder1/:/app/ took 0.00018330000239075162
C:/Folder1/Folder2/:/app/ took 0.003711700002895668
C:/Folder1/Folder2/Folder3/:/app/ took 0.28317089999836753
C:/Folder1/Folder2/Folder3/Folder4/:/app/ took 18.772531900001923

as you can see, runtime grows exponentially. The fifth depth didn't return any result even after 5 minutes. This is the code I ran:

bind = "C:/"
counter = 1

def match(bind):

    return regex.match(MOUNT_WIN_REGEX, bind)

while counter < 10:
    
    result = timeit.timeit(lambda: match(f"{bind}:/app/"), number=1)
    print(f"{bind}:/app/ took {result}")
    bind += f"Folder{counter}/"
    counter += 1

The reason seems to be the inline modifier (?i) in MOUNT_MODE_REGEX:
https://github.com/Azure/iotedgehubdev/blob/7eede7286a0603e565c8b183d090f2585521aae6/iotedgehubdev/constants.py#L48

The modifier somehow is propagated to the whole pattern. Removing the modifier will solve the catastrophic backtracking, but the pattern won't match paths with capital letters. By including the range A-Z in the pattern, the issue of backtracking resurfaces.

Suggestions:

  • split the bind string by :, and apply smaller patterns on split strings instead of applying the huge regex patterns on the whole string
  • instead of applying two huge regex patterns, break them up and use if-elif for pattern matching
主要言語
Python
スター
91
フォーク
38
30日以内にマージされた PR はありません

環境構築

Codespaces で開く

このプロジェクトの開発コンテナを、あなたの GitHub アカウントでブラウザ上に起動します。

  • Dockerfile・Docker Compose ファイルなし
  • プルリクエストのテンプレートなし
  • コントリビューションガイドなし

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

Azure/iotedgehubdev のほかの issue

Azure/iotedgehubdev の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。