git.cworth.org Git - vogl/blob - src/voglcore/vogl_regex.cpp

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_regex.cpp
  28 #include "vogl_core.h"
  29 #include "vogl_regex.h"
  30 #include "vogl_strutils.h"
  31
  32 namespace vogl
  33 {
  34     regexp::regexp()
  35         : m_is_initialized(false)
  36     {
  37     }
  38
  39     regexp::regexp(const char *pPattern, uint flags)
  40         : m_is_initialized(false)
  41     {
  42         init(pPattern, flags);
  43     }
  44
  45     regexp::~regexp()
  46     {
  47         deinit();
  48     }
  49
  50     void regexp::deinit()
  51     {
  52         if (m_is_initialized)
  53         {
  54             vogl_regfree(&m_regex);
  55             m_is_initialized = false;
  56         }
  57
  58         m_error.clear();
  59         m_match_strings.clear();
  60         m_match_locs.clear();
  61     }
  62
  63     bool regexp::init(const char *pPattern, uint flags)
  64     {
  65         deinit();
  66
  67         flags |= REG_EXTENDED;
  68
  69         int errcode = vogl_regcomp(&m_regex, pPattern, flags);
  70         if (errcode != 0)
  71         {
  72             size_t errbuf_size = vogl_regerror(errcode, &m_regex, NULL, 0);
  73             if ((errbuf_size) && (errbuf_size < cUINT32_MAX))
  74             {
  75                 vogl::vector<char> errbuf(static_cast<uint>(errbuf_size));
  76
  77                 vogl_regerror(errcode, &m_regex, errbuf.get_ptr(), errbuf_size);
  78
  79                 m_error.set(errbuf.get_ptr());
  80             }
  81             else
  82             {
  83                 m_error = "unknown regex error";
  84             }
  85
  86             return false;
  87         }
  88
  89         m_is_initialized = true;
  90
  91         return true;
  92     }
  93
  94     bool regexp::find_any(const char *pString)
  95     {
  96         if (!m_is_initialized)
  97         {
  98             VOGL_ASSERT_ALWAYS;
  99             return false;
 100         }
 101
 102         return vogl_regexec(&m_regex, pString, 0, NULL, 0) == 0;
 103     }
 104
 105     const char *regexp::find_first(const char *pString, int &begin, int &end)
 106     {
 107         begin = 0;
 108         end = 0;
 109
 110         if (!m_is_initialized)
 111         {
 112             VOGL_ASSERT_ALWAYS;
 113             return NULL;
 114         }
 115
 116         regmatch_t match;
 117         if ((vogl_regexec(&m_regex, pString, 1, &match, 0)) != 0)
 118             return NULL;
 119
 120         if (match.rm_so < 0)
 121             return NULL;
 122
 123         begin = static_cast<int>(match.rm_so);
 124         end = static_cast<int>(match.rm_eo);
 125
 126         return pString + match.rm_so;
 127     }
 128
 129     bool regexp::full_match(const char *pString)
 130     {
 131         int begin, end;
 132         const char *p = find_first(pString, begin, end);
 133         if (!p)
 134             return false;
 135
 136         return (!begin) && (pString[end] == '\0');
 137     }
 138
 139     uint regexp::find(const char *pString)
 140     {
 141         if (!m_is_initialized)
 142             return false;
 143
 144         m_match_strings.resize(0);
 145         m_match_locs.resize(0);
 146
 147         regmatch_t match;
 148         const char *pCur = pString;
 149
 150         for (;;)
 151         {
 152             if ((vogl_regexec(&m_regex, pCur, 1, &match, 0)) != 0)
 153                 break;
 154
 155             if (match.rm_so < 0)
 156                 break;
 157
 158             if ((match.rm_eo >= cMaxDynamicStringLen) || (match.rm_so >= cMaxDynamicStringLen))
 159             {
 160                 VOGL_ASSERT_ALWAYS;
 161                 break;
 162             }
 163
 164             int len = static_cast<int>(match.rm_eo) - static_cast<int>(match.rm_so);
 165             if ((len < 0) || (len >= cMaxDynamicStringLen))
 166             {
 167                 VOGL_ASSERT_ALWAYS;
 168                 break;
 169             }
 170
 171             dynamic_string str;
 172             str.set_len(len);
 173             str.set_from_buf(pCur + match.rm_so, static_cast<int>(len));
 174
 175             m_match_strings.enlarge(1)->swap(str);
 176             m_match_locs.enlarge(1)->set(static_cast<int>(pCur - pString) + static_cast<int>(match.rm_so), len);
 177
 178             pCur += match.rm_eo;
 179             if (match.rm_so == match.rm_eo)
 180                 break;
 181
 182             if (*pCur == '\0')
 183                 break;
 184         }
 185
 186         return m_match_strings.size();
 187     }
 188
 189     uint regexp::replace(dynamic_string &result, const char *pString, const char *pReplacement)
 190     {
 191         uint n = find(pString);
 192         if (!n)
 193         {
 194             result = pString;
 195             return 0;
 196         }
 197
 198         result.set_len(0);
 199
 200         uint str_len = vogl_strlen(pString);
 201         uint cur_ofs = 0;
 202
 203         for (uint i = 0; i < n; i++)
 204         {
 205             const regexp_match_loc &cur_match = m_match_locs[i];
 206
 207             VOGL_ASSERT(cur_match.m_start >= cur_ofs);
 208
 209             if (cur_match.m_start > cur_ofs)
 210                 result.append(pString + cur_ofs, cur_match.m_start - cur_ofs);
 211
 212             if (pReplacement)
 213                 result.append(pReplacement);
 214
 215             cur_ofs = cur_match.m_start + cur_match.m_len;
 216         }
 217
 218         if (cur_ofs < str_len)
 219         {
 220             result.append(pString + cur_ofs, str_len - cur_ofs);
 221         }
 222
 223         return n;
 224     }
 225
 226     static uint regexp_test(const char *pPat, const char *pStr)
 227     {
 228         dynamic_string_array matches(regexp_find(pStr, pPat));
 229         printf("Pattern: \"%s\" String: \"%s\" Find: %u\n", pPat, pStr, matches.size());
 230         for (uint i = 0; i < matches.size(); i++)
 231             printf("\"%s\"\n", matches[i].get_ptr());
 232         return matches.size();
 233     }
 234
 235     static bool regexp_test2(const char *pPat, const char *pStr)
 236     {
 237         bool result = regexp_find_any(pStr, pPat);
 238         printf("Pattern: \"%s\" String: \"%s\" FindAny: %u\n", pPat, pStr, result);
 239         return result;
 240     }
 241
 242     static bool regexp_test3(const char *pPat, const char *pStr)
 243     {
 244         bool result = regexp_full_match(pStr, pPat);
 245         printf("Pattern: \"%s\" String: \"%s\" Match: %u\n", pPat, pStr, result);
 246         return result;
 247     }
 248
 249     static uint g_regexp_test_fail_count;
 250     static void regexp_test_check(bool success)
 251     {
 252         if (!success)
 253         {
 254             g_regexp_test_fail_count++;
 255             VOGL_VERIFY(0);
 256         }
 257     }
 258
 259     bool regexp_test()
 260     {
 261         g_regexp_test_fail_count = 0;
 262
 263         // Some of these tests where borrowed from stb.h.
 264
 265         regexp_test_check(regexp_test("ab+c", "ab") == 0);
 266         regexp_test_check(regexp_test("ab+c", "abc blah") == 1);
 267         regexp_test_check(regexp_test("ab+c$", "abc blah") == 0);
 268         regexp_test_check(regexp_test("ab+c$", "abc") == 1);
 269         regexp_test_check(regexp_test("ab+c", "abc") == 1);
 270         regexp_test_check(regexp_test("ab+c", "abbc") == 1);
 271         regexp_test_check(regexp_test("get|set", "getter") == 1);
 272         regexp_test_check(regexp_test("get|set", "setter") == 1);
 273         regexp_test_check(regexp_test("[a.c]", "a") == 1);
 274         regexp_test_check(regexp_test("[a.c]", "z") == 0);
 275         regexp_test_check(regexp_test("[a.c]", ".") == 1);
 276         regexp_test_check(regexp_test("[a.c]", "c") == 1);
 277         regexp_test_check(regexp_test("gr(a|e)y", "grey") == 1);
 278         regexp_test_check(regexp_test("gr(a|e)y", "gray") == 1);
 279         regexp_test_check(regexp_test("gr(a|e)y", "gry") == 0);
 280         regexp_test_check(regexp_test("g{1}", "g") == 1);
 281         regexp_test_check(regexp_test("g{3,5}", "gg") == 0);
 282         regexp_test_check(regexp_test("g{3,5}", "gggg") == 1);
 283         regexp_test_check(regexp_test("g{3,5}", "ggggg") == 1);
 284         regexp_test_check(regexp_test("g{3,5}", "gggggg") == 1);
 285         regexp_test_check(regexp_test("g{3,5}", "ggggggXggg") == 2);
 286         regexp_test_check(regexp_test("(g{3,5}|x{3,7})", "ggggggXxxx!gggg") == 3);
 287         regexp_test_check(regexp_test2("Uniform", "glUniform") == 1);
 288         regexp_test_check(regexp_test3("Uniform", "Uniform") == 1);
 289         regexp_test_check(regexp_test3("Uniform$", "Uniform") == 1);
 290         regexp_test_check(regexp_test3("Uniform$", "UniformBlah") == 0);
 291         regexp_test_check(regexp_test3("Uniform", "UniformBlah") == 0);
 292         regexp_test_check(regexp_test3("Uniform", "glUniformBlah") == 0);
 293
 294         regexp_test_check(regexp_test("<h(.)>([^<]+)", "<h2>Egg prices</h2>") == 1);
 295
 296         {
 297             dynamic_string x;
 298             regexp r;
 299             r.init("[az]");
 300             r.replace(x, "AaThis is a test zz BlAh", "!!!!!!");
 301             printf("%s\n", x.get_ptr());
 302             regexp_test_check(x.compare("A!!!!!!This is !!!!!! test !!!!!!!!!!!! BlAh", true) == 0);
 303         }
 304
 305         {
 306             dynamic_string x;
 307             regexp r;
 308             r.init("[az]");
 309             r.replace(x, "aThis is a test zz BlAh", "!!!!!!");
 310             printf("%s\n", x.get_ptr());
 311             regexp_test_check(x.compare("!!!!!!This is !!!!!! test !!!!!!!!!!!! BlAh", true) == 0);
 312         }
 313
 314         {
 315             dynamic_string x;
 316             regexp r;
 317             r.init("[az]");
 318             r.replace(x, "aThis is a test zz BlAha", "!!!!!!");
 319             printf("%s\n", x.get_ptr());
 320             regexp_test_check(x.compare("!!!!!!This is !!!!!! test !!!!!!!!!!!! BlAh!!!!!!", true) == 0);
 321         }
 322
 323         regexp_test_check(regexp_replace("Blah", "a", "!").compare("Bl!h", true) == 0);
 324         regexp_test_check(regexp_replace("Blah", "Blah", "!").compare("!", true) == 0);
 325         regexp_test_check(regexp_replace("BlahX", "Blah", "!").compare("!X", true) == 0);
 326         regexp_test_check(regexp_replace("BlahX", "Blah", "X").compare("XX", true) == 0);
 327         regexp_test_check(regexp_replace("Blah", "Blah", "") == "");
 328         regexp_test_check(regexp_replace("XBlahX", "Blah", "").compare("XX", true) == 0);
 329         regexp_test_check(regexp_replace("XBlahX", "Blah", NULL).compare("XX", true) == 0);
 330
 331         const char *z = "foo.*[bd]ak?r";
 332         regexp_test_check(regexp_test(z, "muggle man food is barfy") == 1);
 333         regexp_test_check(regexp_test("foo.*bar", "muggle man food is farfy") == 0);
 334         regexp_test_check(regexp_test("[^a-zA-Z]foo[^a-zA-Z]", "dfoobar xfood") == 0);
 335         regexp_test_check(regexp_test(z, "muman foob is bakrfy") == 1);
 336         z = "foo.*[bd]bk?r";
 337         regexp_test_check(regexp_test(z, "muman foob is bakrfy") == 0);
 338         regexp_test_check(regexp_test(z, "muman foob is bbkrfy") == 1);
 339
 340         regexp_test_check(regexp_test("ab+c", "abc") == 1);
 341         regexp_test_check(regexp_test("ab+c", "abbc") == 1);
 342         regexp_test_check(regexp_test("ab+c", "abbbc") == 1);
 343         regexp_test_check(regexp_test("ab+c", "ac") == 0);
 344
 345         regexp_test_check(regexp_test("ab?c", "ac") == 1);
 346         regexp_test_check(regexp_test("ab?c", "abc") == 1);
 347         regexp_test_check(regexp_test("ab?c", "abbc") == 0);
 348         regexp_test_check(regexp_test("ab?c", "abbbc") == 0);
 349         regexp_test_check(regexp_test("ab?c", "babbbc") == 0);
 350
 351         regexp_test_check(regexp_test("gr(a|e)y", "grey") == 1);
 352         regexp_test_check(regexp_test("gr(a|e)y", "graey") == 0);
 353         regexp_test_check(regexp_test("gr(a|e)y", "gray") == 1);
 354         regexp_test_check(regexp_test("gr(a?|e)y", "gry") == 1);
 355         regexp_test_check(regexp_test("gr(a?|e)y", "grey") == 1);
 356         regexp_test_check(regexp_test("gr(a?|e)y", "gray") == 1);
 357
 358         regexp_test_check(regexp_test("(a|b)*", "") == 1);
 359         regexp_test_check(regexp_test("(a|b)*", "a") == 1);
 360         regexp_test_check(regexp_test("(a|b)*", "ab") == 1);
 361         regexp_test_check(regexp_test("(a|b)*", "aa") == 1);
 362         regexp_test_check(regexp_test("(a|b)*", "ba") == 1);
 363         regexp_test_check(regexp_test("(a|b)*", "bb") == 1);
 364         regexp_test_check(regexp_test("(a|b)*", "aaa") == 1);
 365         regexp_test_check(regexp_test("(a|b)", "z") == 0);
 366         regexp_test_check(regexp_test("*", "z") == 0); // purposely bogus
 367
 368         regexp_test_check(regexp_test("", "abc") == 0); // purposely bogus
 369         regexp_test_check(regexp_test("(a|b)*", "abc") == 2);
 370         regexp_test_check(regexp_test("(a|b)*", "c") == 1);
 371         regexp_test_check(regexp_test("(a|b)*c", "abcab") == 1);
 372         regexp_test_check(regexp_test("(a|b)*c", "abcbac") == 2);
 373
 374         {
 375             regexp r;
 376             r.init(".*foo.*bar.*");
 377             regexp_test_check(r.find_any("foobarx") == 1);
 378             regexp_test_check(r.find_any("foobar") == 1);
 379             regexp_test_check(r.find_any("foo bar") == 1);
 380             regexp_test_check(r.find_any("fo foo ba ba bar ba") == 1);
 381             regexp_test_check(r.find_any("fo oo oo ba ba bar foo") == 0);
 382         }
 383
 384         {
 385             regexp r;
 386             r.init(".*foo.?bar.*");
 387             regexp_test_check(r.find_any("abfoobarx") == 1);
 388             regexp_test_check(r.find_any("abfoobar") == 1);
 389             regexp_test_check(r.find_any("abfoo bar") == 1);
 390             regexp_test_check(r.find_any("abfoo  bar") == 0);
 391             regexp_test_check(r.find_any("abfo foo ba ba bar ba") == 0);
 392             regexp_test_check(r.find_any("abfo oo oo ba ba bar foo") == 0);
 393         }
 394
 395         {
 396             regexp r;
 397             r.init(".*m((foo|bar)*baz)m.*");
 398             regexp_test_check(r.find_any("abfoobarx") == 0);
 399             regexp_test_check(r.find_any("a mfoofoofoobazm d") == 1);
 400             regexp_test_check(r.find_any("a mfoobarbazfoom d") == 0);
 401             regexp_test_check(r.find_any("a mbarbarfoobarbazm d") == 1);
 402             regexp_test_check(r.find_any("a mfoobarfoo bazm d") == 0);
 403             regexp_test_check(r.find_any("a mm foobarfoobarfoobar ") == 0);
 404         }
 405
 406         {
 407             regexp r;
 408             r.init("f*|z");
 409             regexp_test_check(r.find_any("fz") == 1);
 410             regexp_test_check(r.find("fz") == 2);
 411             regexp_test_check(r.find_any("ff") == 1);
 412             regexp_test_check(r.find_any("z") == 1);
 413         }
 414
 415         {
 416             regexp r;
 417             r.init("m(f|z*)n");
 418             regexp_test_check(r.find_any("mfzn") == 0);
 419             regexp_test_check(r.find_any("mffn") == 0);
 420             regexp_test_check(r.find_any("mzn") == 1);
 421             regexp_test_check(r.find_any("mn") == 1);
 422             regexp_test_check(r.find_any("mzfn") == 0);
 423
 424             regexp_test_check(r.find_any("manmanmannnnnnnmmmmmmmmm       ") == 0);
 425             regexp_test_check(r.find_any("manmanmannnnnnnmmmmmmmmm       ") == 0);
 426             regexp_test_check(r.find_any("manmanmannnnnnnmmmmmmmmmffzzz  ") == 0);
 427             regexp_test_check(r.find_any("manmanmannnnnnnmmmmmmmmmnfzzz  ") == 1);
 428             regexp_test_check(r.find_any("mmmfn aanmannnnnnnmmmmmm fzzz  ") == 1);
 429             regexp_test_check(r.find_any("mmmzzn anmannnnnnnmmmmmm fzzz  ") == 1);
 430             regexp_test_check(r.find_any("mm anmannnnnnnmmmmmm fzmzznzz  ") == 1);
 431             regexp_test_check(r.find_any("mm anmannnnnnnmmmmmm fzmzzfnzz ") == 0);
 432             regexp_test_check(r.find_any("manmfnmannnnnnnmmmmmmmmmffzzz  ") == 1);
 433         }
 434
 435         {
 436             regexp r;
 437             r.init(".*m((foo|bar)*|baz)m.*");
 438             regexp_test_check(r.find_any("abfoobarx") == 0);
 439             regexp_test_check(r.find_any("a mfoofoofoobazm d") == 0);
 440             regexp_test_check(r.find_any("a mfoobarbazfoom d") == 0);
 441             regexp_test_check(r.find_any("a mbazm d") == 1);
 442             regexp_test_check(r.find_any("a mfoobarfoom d") == 1);
 443             regexp_test_check(r.find_any("a mm foobarfoobarfoobar ") == 1);
 444         }
 445
 446         {
 447             regexp r;
 448             r.init("[a-fA-F]..[^]a-zA-Z]");
 449             regexp_test_check(r.find_any("Axx1") == 1);
 450             regexp_test_check(r.find_any("Fxx1") == 1);
 451             regexp_test_check(r.find_any("Bxx]") == 0);
 452             regexp_test_check(r.find_any("Cxxz") == 0);
 453             regexp_test_check(r.find_any("gxx[") == 0);
 454             regexp_test_check(r.find_any("-xx0") == 0);
 455         }
 456
 457         vogl_check_heap();
 458
 459         return !g_regexp_test_fail_count;
 460     }
 461
 462 } // namespace vogl