4
\$\begingroup\$

I have a bit of code that converts a Sql Like expression to a regex expression for the purposes of a Linq to objects Like extension method. For some time I have been using this conversion.

This conversion replaces all "%" with ".*?" which works for contains patterns but is over matching for starts with or ends with patterns. So the conversion of %abc to .*?abc is capturing both "abcdef" and "123abcdef".

I've amended the conversion algorithm to account for starts with and ends with LIKE expressions.

Here is my code:

internal static string ConvertLikeToRegex(string pattern)
{
    // Turn "off" all regular expression related syntax in the pattern string. 
    StringBuilder builder = new StringBuilder(Regex.Escape(pattern));

    // these are needed because the .*? replacement below at the begining or end of the string is not
    // accounting for cases such as LIKE '%abc' or LIKE 'abc%'
    bool startsWith = pattern.StartsWith("%") && !pattern.EndsWith("%");
    bool endsWith = !pattern.StartsWith("%") && pattern.EndsWith("%");

    // this is a little tricky
    // ends with in like is '%abc'
    // in regex it's 'abc$'
    // so need to tanspose
    if (startsWith)
    {
        builder.Replace("%", "", 0, 1);
        builder.Append("$");
    }

    // same but inverse here
    if (endsWith)
    {
        builder.Replace("%", "", pattern.Length - 1, 1);
        builder.Insert(0, "^");
    }

    /* Replace the SQL LIKE wildcard metacharacters with the
    * equivalent regular expression metacharacters. */
    builder.Replace("%", ".*?").Replace("_", ".");

    /* The previous call to Regex.Escape actually turned off
    * too many metacharacters, i.e. those which are recognized by
    * both the regular expression engine and the SQL LIKE
    * statement ([...] and [^...]). Those metacharacters have
    * to be manually unescaped here. */
    builder.Replace(@"\[", "[").Replace(@"\]", "]").Replace(@"\^", "^");

    return builder.ToString();
}

My initial units test are passing but not being overly conversant in regex syntax I am wondering if this is the best approach or if there are gaps in the conversion I am not seeing.

\$\endgroup\$
2
  • \$\begingroup\$ What if it starts with and endsWith? I don't understand the need for startsWith to check that it doesn't also endWith \$\endgroup\$
    – Cruncher
    Dec 7, 2013 at 16:16
  • \$\begingroup\$ LIKE '%abc%' (i.e. contains) converts to ".*?abc.*?" which captures abcdef and 123abcdef The regex ^abc$ (which is what would happen without those tests) only captures strings both starting and ending with abc. \$\endgroup\$
    – dkackman
    Dec 7, 2013 at 16:26

5 Answers 5

10
\$\begingroup\$

I think you're overcomplicating this and your code still doesn't work correctly. The LIKE pattern bcd shouldn't match abcde, but it does with your code.

What you should do is to always add ^ at the start and $ at the end.

This means the following conversions:

  • bcd^bcd$
  • %bcd^.*?bcd$
  • bcd%^bcd.*?$
  • %bcd%^.*?bcd.*?$

In the cases where the pattern starts with %, the ^ is not necessary (and similarly for $ and % at the end), but it also doesn't do any harm.

\$\endgroup\$
6
  • \$\begingroup\$ Even simpler than my suggestion. Nice! \$\endgroup\$ Dec 7, 2013 at 17:12
  • \$\begingroup\$ Perfect. Works like a charm. I figured I was missing something much more straightforward. \$\endgroup\$
    – dkackman
    Dec 7, 2013 at 17:22
  • \$\begingroup\$ nb: "?" is not needed since LIKE will always match the entire string anyway. \$\endgroup\$
    – Sylverdrag
    Dec 7, 2013 at 19:54
  • \$\begingroup\$ @Sylverdrag Yeah, I think you're right, I just copied that from the code in the question. \$\endgroup\$
    – svick
    Dec 7, 2013 at 20:10
  • 1
    \$\begingroup\$ BUT, note that regex treats some string literals like . as special selectors. So, for a LIKE fragment asdf.qwer% with (python syntax) regex re.match('^asdf.qwer.*$', 'asdfXqwer') will result in a match incorrectly because . means "any single character here". You also need to escape any regex-special chars in LIKE fragment before piping to regex. Example in this case: re.match('^asdf\.qwer.*$', 'asdfXqwer') == proper no match \$\endgroup\$
    – ddotsenko
    Aug 25, 2020 at 17:11
6
\$\begingroup\$

Because the LIKE clause has a defined syntax, to do this right (meaning no clause will be incorrectly converted), you will need to use (or create) a simple lexer to parse the LIKE clause. A sample grammar could look like:

expr := wild-card + expr
      | wild-char + expr
      | escape + expr
      | string + expr
      | ""

wild-card := %  
wild-char := _  
escape := [%|_]  
string := [^%_]+ (One or > more characters that are not wild-card or wild-char)

NOTE: Although the above grammar will work by default, note that SQL allows the user to specify a user-defined ESCAPE character (see T-SQL)

The steps to accomplish the LIKE syntax conversion are as follows:

  1. Define your Token classes:

    public abstract class Token {
        private final String value;
    
        public Token(String value) {
            this.value = value;
        }
    
        public abstract String convert();
    
        public String getValue() {
            return value;
        }
    }
    
    public class EscapeToken extends Token {
        public EscapeToken(String value) {
            super(value);
        }
    
        @Override
        public String convert() {
            return getValue();
        }
    }
    
    public class WildcardToken extends Token {
        public WildcardToken(String value) {
            super(value);
        }
    
        @Override
        public String convert() {
            return ".*";
        }
    }
    
    public class WildcharToken extends Token {
        public WildcharToken(String value) {
            super(value);
        }
    
        @Override
        public String convert() {
            return ".";
        }
    }
    
    public class StringToken extends Token {
        public StringToken(String value) {
            super(value);
        }
    
        @Override
        public String convert() {
            return Pattern.quote(getValue());
        }
    }
    
  2. Create a Lexer (or Tokenizer):

    public class Tokenizer {
    
       private Collection<Tuple> patterns = new LinkedList<>();
    
       public <T extends Token> Tokenizer add(String regex, Function<String, Token> creator) {
           this.patterns.add(Tuple.of(Pattern.compile(regex), creator));
           return this;
        }
    
        public Collection<Token> tokenize(String clause) throws ParseException {
            Collection<Token> tokens = new ArrayList<>();
            String copy = String.copyValueOf(clause.toCharArray());
    
            int position = 0;
            while (!copy.equals("")) {
                boolean found = false;
                for (Tuple tuple : this.patterns) {
                    Pattern pattern = tuple.get(0, Pattern.class);
                    Matcher m = pattern.matcher(copy);
                    if (m.find()) {
                        found = true;
                        String token = m.group(1);
                        Function<String, Token> fn = (Function<String, Token>) tuple.get(1);
                        tokens.add(fn.apply(token));
                        copy = m.replaceFirst("");
                        position += token.length();
                        break;
                    }
                }
    
                if (!found) {
                    throw new ParseException("Unexpected sequence found in input string.", ++position);
                }
            }
    
            return tokens;
    
        }
    }
    
  3. Create SQL LIKE to RegEx Transpiler:

    public class SqlLikeTranspiler {
        private static Tokenizer TOKENIZER = new Tokenizer()
                .add("^(\\[[^]]*])", ConstantToken::new)
                .add("^(%)", WildcardToken::new)
                .add("^(_)", WildcharToken::new)
                .add("^([^\\[\\]%_]+)", StringToken::new);
    
        public static String toRegEx(String pattern) throws ParseException {
            StringBuilder sb = new StringBuilder().append("^");
            for (Token token : TOKENIZER.tokenize(pattern)) {
                sb.append(token.convert());
            }
    
            return sb.append("$").toString();
        }
    }
    

NOTE: We ensure the match is not too generous by indicating the resulting regular expression has start and end tags (^ and $ respectively).

By creating a lexer and converting using this methodology, we can prevent LIKE clauses like %abc[%]%, which should match any string with the sub-string abc% in it, from being converted to a regular expression like .*abc[.*].* which will match any string with either the sub-string abc. or abc*.

The provided code is Java.

\$\endgroup\$
1
  • \$\begingroup\$ I created a C# version of your code put it in a library with xUnit tests and published it under the MIT license on GitHub at github.com/paviad/sql-like-to-regex I also believe you have an error there, you reference ConstantToken but I believe you should refer to EscapeToken - and also a better name for that would be SetOrRangeToken or simply SetToken \$\endgroup\$
    – Aviad P.
    Jun 16, 2023 at 8:08
4
\$\begingroup\$

Your name "startsWith" is confusing because it looks at both ends, and controls the placement of the trailing $. I'd simplify this:

bool startsWith = pattern.StartsWith("%") && !pattern.EndsWith("%");
bool endsWith = !pattern.StartsWith("%") && pattern.EndsWith("%");

if (startsWith)
{
    builder.Replace("%", "", 0, 1);
    builder.Append("$");
}
if (endsWith)
{
    builder.Replace("%", "", pattern.Length - 1, 1);
    builder.Insert(0, "^");
}

to this:

bool leadingLiteral = !pattern.StartsWith("%");
if (leadingLiteral)
{
    builder.Insert(0, "^");
}

bool trailingLiteral = !pattern.EndsWith("%");
if (trailingLiteral)
{
    builder.Append("$");
}

You may also note that I left the named Boolean variables in the code. I like using "explanatory variables" instead of comments. The optimizer will get rid of them in a production build, so they cost nothing to the runtime. But I think they make the code more readable and therefore more maintainable. They encourage you, the developer, to think about what you're doing. And they encourage you to think of an appropriate name. If you find it hard to name a thing, that may be a sign that it's unclear, or is doing too much.

\$\endgroup\$
3
\$\begingroup\$

In LIKE patterns, the interpretation of characters between square brackets is more literal than normal. What SQL dialect are you targeting? See, for example, the T-SQL documentation for LIKE (under Using Wildcard Characters as Literals). LIKE '5[%]' should be translated as regex '^5%$'.

\$\endgroup\$
1
  • \$\begingroup\$ I think a more natural (and equivalent) translation would be ^5[%]$. \$\endgroup\$
    – svick
    Dec 7, 2013 at 18:14
2
\$\begingroup\$

See @svick excellent answer, but, note that it does not account for regex special syntax character escaping.

Literals like . are special selectors in regex. So, for a LIKE fragment asdf.qwer% a (python syntax) regex re.match('^asdf.qwer.*$', 'asdfXqwer') would INCORRECTLY match because . means "any single character here".

You also need to escape any regex-special chars in LIKE fragment before piping to regex. Example in this case: re.match('^asdf\.qwer.*$', 'asdfXqwer') == proper no match.

Ansi SQL special characters % and _ are wonderfully NOT regex special selector characters. So, it's super easy to escape ANSI SQL like fragments, and then replace % and _ with regex eqivalents.

# Python example
# note that in python, you need to escape `\` in code too :) 
# resulting in `\\` in code representation. print the string to see single `\`

_special_regex_chars = {
    ch : '\\'+ch
    for ch in '.^$*+?{}[]|()\\'
}

def _sql_like_fragment_to_regex_string(fragment):
    # https://codereview.stackexchange.com/a/36864/229677
    safe_fragment = ''.join([
        _special_regex_chars.get(ch, ch)
        for ch in fragment
    ])
    return '^' + safe_fragment.replace('%', '.*?').replace('_', '.') + '$'

Or, in one go (because there is no overlap between ANSI SQL selectors and Python Regex selectors):

_char_regex_map = {
    ch : '\\'+ch
    for ch in '.^$*+?{}[]|()\\'
}
_char_regex_map['%'] = '.*?'
_char_regex_map['_'] = '.'

def sql_like_fragment_to_regex_string(fragment):
    return '^' + ''.join([
        _char_regex_map.get(ch, ch)
        for ch in fragment
    ]) + '$'
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.