Catastrophic Backtracking while using `Binds`
- Dominant language
- Python
- Stars
- 91
- Forks
- 38
- Avg merge
- 6m
- Merged PRs (30d)
- 1
Description
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
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.