Regex.cpp revision 6ff80b2281eea0f42458bbf9790d5e340d9d7797
1ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin//===-- Regex.cpp - Regular Expression matcher implementation -------------===// 2ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// 3ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// The LLVM Compiler Infrastructure 4ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// 5ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// This file is distributed under the University of Illinois Open Source 6ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// License. See LICENSE.TXT for details. 7ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// 8ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin//===----------------------------------------------------------------------===// 9ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// 10ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// This file implements a POSIX regular expression matcher. 11ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin// 12ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin//===----------------------------------------------------------------------===// 1348ba9ff3c44f33c65c26ecf5df306f4a428d2c26Chris Lattner 14ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin#include "llvm/Support/Regex.h" 15ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin#include "llvm/Support/ErrorHandling.h" 16ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin#include "llvm/Support/raw_ostream.h" 17528700863adefca8de461ce28a7d903729fb96b4Chris Lattner#include "llvm/ADT/SmallVector.h" 18ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin#include "regex_impl.h" 19ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin#include <string> 20ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwinusing namespace llvm; 2148ba9ff3c44f33c65c26ecf5df306f4a428d2c26Chris Lattner 2238e59891ee4417a9be2f8146ce0ba3269e38ac21Benjamin KramerRegex::Regex(StringRef regex, unsigned Flags) { 23ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin unsigned flags = 0; 24528700863adefca8de461ce28a7d903729fb96b4Chris Lattner preg = new llvm_regex(); 25ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin preg->re_endp = regex.end(); 26ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin if (Flags & IgnoreCase) 27ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin flags |= REG_ICASE; 28ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin if (Flags & Newline) 29ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin flags |= REG_NEWLINE; 30ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin error = llvm_regcomp(preg, regex.data(), flags|REG_EXTENDED|REG_PEND); 31ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin} 32ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 3381f46d9ce1888308b33336f9bea72147430da36bChris LattnerRegex::~Regex() { 3481f46d9ce1888308b33336f9bea72147430da36bChris Lattner llvm_regfree(preg); 3581f46d9ce1888308b33336f9bea72147430da36bChris Lattner delete preg; 3681f46d9ce1888308b33336f9bea72147430da36bChris Lattner} 3781f46d9ce1888308b33336f9bea72147430da36bChris Lattner 3848ba9ff3c44f33c65c26ecf5df306f4a428d2c26Chris Lattnerbool Regex::isValid(std::string &Error) { 39ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin if (!error) 40ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin return true; 4181f46d9ce1888308b33336f9bea72147430da36bChris Lattner 42ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin size_t len = llvm_regerror(error, preg, NULL, 0); 4348ba9ff3c44f33c65c26ecf5df306f4a428d2c26Chris Lattner 4448ba9ff3c44f33c65c26ecf5df306f4a428d2c26Chris Lattner Error.resize(len); 4548ba9ff3c44f33c65c26ecf5df306f4a428d2c26Chris Lattner llvm_regerror(error, preg, &Error[0], len); 46ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin return false; 47ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin} 48ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 4981f46d9ce1888308b33336f9bea72147430da36bChris Lattner/// getNumMatches - In a valid regex, return the number of parenthesized 5081f46d9ce1888308b33336f9bea72147430da36bChris Lattner/// matches it contains. 5181f46d9ce1888308b33336f9bea72147430da36bChris Lattnerunsigned Regex::getNumMatches() const { 5281f46d9ce1888308b33336f9bea72147430da36bChris Lattner return preg->re_nsub; 53ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin} 54ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 5538e59891ee4417a9be2f8146ce0ba3269e38ac21Benjamin Kramerbool Regex::match(StringRef String, SmallVectorImpl<StringRef> *Matches){ 56ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin unsigned nmatch = Matches ? preg->re_nsub+1 : 0; 57ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 58ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin // pmatch needs to have at least one element. 59528700863adefca8de461ce28a7d903729fb96b4Chris Lattner SmallVector<llvm_regmatch_t, 8> pm; 60ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin pm.resize(nmatch > 0 ? nmatch : 1); 61ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin pm[0].rm_so = 0; 62ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin pm[0].rm_eo = String.size(); 63ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 64ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin int rc = llvm_regexec(preg, String.data(), nmatch, pm.data(), REG_STARTEND); 65ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 66ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin if (rc == REG_NOMATCH) 67ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin return false; 68ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin if (rc != 0) { 69ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin // regexec can fail due to invalid pattern or running out of memory. 70ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin error = rc; 71ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin return false; 72ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin } 73ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 74ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin // There was a match. 75ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 76ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin if (Matches) { // match position requested 7781f46d9ce1888308b33336f9bea72147430da36bChris Lattner Matches->clear(); 7881f46d9ce1888308b33336f9bea72147430da36bChris Lattner 7948ba9ff3c44f33c65c26ecf5df306f4a428d2c26Chris Lattner for (unsigned i = 0; i != nmatch; ++i) { 80ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin if (pm[i].rm_so == -1) { 81ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin // this group didn't match 82ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin Matches->push_back(StringRef()); 83ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin continue; 84ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin } 856ff80b2281eea0f42458bbf9790d5e340d9d7797Chris Lattner assert(pm[i].rm_eo >= pm[i].rm_so); 86ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin Matches->push_back(StringRef(String.data()+pm[i].rm_so, 87ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin pm[i].rm_eo-pm[i].rm_so)); 88ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin } 89ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin } 90ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin 91ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin return true; 92ce0c81e7dd321e9f94f628daa5528f56cab0ab88Torok Edwin} 93d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 94d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbarstd::string Regex::sub(StringRef Repl, StringRef String, 95d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar std::string *Error) { 96d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar SmallVector<StringRef, 8> Matches; 97d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 98d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Reset error, if given. 99d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar if (Error && !Error->empty()) *Error = ""; 100d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 101d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Return the input if there was no match. 102d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar if (!match(String, &Matches)) 103d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar return String; 104d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 105d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Otherwise splice in the replacement string, starting with the prefix before 106d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // the match. 107d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar std::string Res(String.begin(), Matches[0].begin()); 108d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 109d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Then the replacement string, honoring possible substitutions. 110d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar while (!Repl.empty()) { 111d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Skip to the next escape. 112d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar std::pair<StringRef, StringRef> Split = Repl.split('\\'); 113d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 114d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Add the skipped substring. 115d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Res += Split.first; 116d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 117d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Check for terminimation and trailing backslash. 118d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar if (Split.second.empty()) { 119d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar if (Repl.size() != Split.first.size() && 120d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Error && Error->empty()) 121d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar *Error = "replacement string contained trailing backslash"; 122d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar break; 123d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar } 124d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 125d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Otherwise update the replacement string and interpret escapes. 126d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Repl = Split.second; 127d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 128d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // FIXME: We should have a StringExtras function for mapping C99 escapes. 129d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar switch (Repl[0]) { 130d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Treat all unrecognized characters as self-quoting. 131d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar default: 132d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Res += Repl[0]; 133d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Repl = Repl.substr(1); 134d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar break; 135d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 136d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Single character escapes. 137d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar case 't': 138d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Res += '\t'; 139d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Repl = Repl.substr(1); 140d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar break; 141d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar case 'n': 142d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Res += '\n'; 143d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Repl = Repl.substr(1); 144d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar break; 145d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 146d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Decimal escapes are backreferences. 147d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar case '0': case '1': case '2': case '3': case '4': 148d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar case '5': case '6': case '7': case '8': case '9': { 149d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // Extract the backreference number. 150d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar StringRef Ref = Repl.slice(0, Repl.find_first_not_of("0123456789")); 151d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Repl = Repl.substr(Ref.size()); 152d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 153d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar unsigned RefValue; 154d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar if (!Ref.getAsInteger(10, RefValue) && 155d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar RefValue < Matches.size()) 156d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Res += Matches[RefValue]; 157d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar else if (Error && Error->empty()) 158d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar *Error = "invalid backreference string '" + Ref.str() + "'"; 159d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar break; 160d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar } 161d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar } 162d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar } 163d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 164d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar // And finally the suffix. 165d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar Res += StringRef(Matches[0].end(), String.end() - Matches[0].end()); 166d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar 167d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar return Res; 168d2a5c0d8562407f9acab97451a785b513edd4c9bDaniel Dunbar} 169