Regex Insufficient Memory in Template Parser

[abtris]

@bobdercole opened apiaryio/snowcrash#399

Hello,

I am using API Blueprint Sublime Text Plugin and Aglio. I'm having a common issue which I've narrowed down to Snowcrash's URI template parser. The parser seems to fail with very long URI templates.

Here is a working example:

[/test{?abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab}]

Here is a failing example (notice the additional character at the end):

[/test{?abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc}]

I've tried running the win regex match code with the above strings and this expression in an isolated environment and was able to reproduce the issue. I'm on Windows built with MSVC2015. The regex_error exception is as follows:

There was insufficient memory to determine whether the regular expression could match the specified character sequence.

For the record, I've tried running Aglio with the provided Dockerfile and it works fine with long URI templates.

Any ideas? Thank you!

[abtris]

@kylef commented

Hi @bobdercole thanks for the detailed report. Would you be able to share how much memory you have available while running this code?

[abtris]

@bobdercole commented

Sure. Here is my isolated sample code along with GlobalMemoryStatusEx. I'm not sure if GlobalMemoryStatusEx provides everything you're looking for. Let me know if there is something else I can share.

#include "stdafx.h"
#include <iomanip>
#include <iostream>
#include <regex>
#include <string>
#include <windows.h>
#include <stdio.h>
#include <tchar.h>

#define DIV 1024
#define WIDTH 7

void main()
{
    std::regex pattern("^([?|#|+|&]?(([A-Z|a-z|0-9|_|,])*|(%[A-F|a-f|0-9]{2})*)*\\*?)$", std::regex_constants::extended);
    std::string input = "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc";

    bool result = false;

    try
    {
        result = regex_search(input, pattern);
    }
    catch (const std::regex_error& e)
    {
        std::cout << "regex_error caught: " << e.what() << std::endl;
    }

    std::cout << "regex_search result: " << result << std::endl;

    MEMORYSTATUSEX statex;
    statex.dwLength = sizeof(statex);
    GlobalMemoryStatusEx(&statex);

    _tprintf(TEXT("There is  %*ld percent of memory in use.\n"), WIDTH, statex.dwMemoryLoad);
    _tprintf(TEXT("There are %*I64d total KB of physical memory.\n"), WIDTH, statex.ullTotalPhys / DIV);
    _tprintf(TEXT("There are %*I64d free  KB of physical memory.\n"), WIDTH, statex.ullAvailPhys / DIV);
    _tprintf(TEXT("There are %*I64d total KB of paging file.\n"), WIDTH, statex.ullTotalPageFile / DIV);
    _tprintf(TEXT("There are %*I64d free  KB of paging file.\n"), WIDTH, statex.ullAvailPageFile / DIV);
    _tprintf(TEXT("There are %*I64d total KB of virtual memory.\n"), WIDTH, statex.ullTotalVirtual / DIV);
    _tprintf(TEXT("There are %*I64d free  KB of virtual memory.\n"), WIDTH, statex.ullAvailVirtual / DIV);
    _tprintf(TEXT("There are %*I64d free  KB of extended memory.\n"), WIDTH, statex.ullAvailExtendedVirtual / DIV);
}

Here is the output:

regex_error caught: regex_error(error_stack): There was insufficient memory to determine whether the regular expression could match the specified character sequence.
regex_search result: 0
There is       33 percent of memory in use.
There are 16681676 total KB of physical memory.
There are 11175972 free  KB of physical memory.
There are 33361492 total KB of paging file.
There are 27716812 free  KB of paging file.
There are 2097024 total KB of virtual memory.
There are 2083268 free  KB of virtual memory.
There are       0 free  KB of extended memory.

[kylef]

As of Drafter 5.0.0-rc.1, this issue is no longer applicable as the parser for URI Templates does not use regex and suffer this problem.