More Pythonic version of finding substring with one glob-like expression
Language interpretation


  Should one be able to escape escapes? –  icktoofay Jun 21 at 23:47
  
  No, one should not :) –  ProfHase85 Jun 22 at 8:26


I agree with @icktoofay's suggestion.  In the absence of any indication to the contrary, I would assume that any backslash in the globlike expression should cause the following character to be interpreted literally.  That means that \\ (a pair of backslashes) should be interpreted as one literal backslash.

In general, any sane language that has an escaping mechanism must also have a way to let you specify a literal sequence of characters that looks like an escape.  Examples:


String literals in C and Python: \\ is a literal backslash.
printf() format strings: %% produces a literal % character in the output.
HTML and XML: &amp;amp; is a literal &amp;.
LDAP search filters: \5c matches a literal \.


If it were not possible to escape escapes, how would one search for a literal \* (backslash, asterisk) in the text?  Based on norms established by C string literals, I would expect the globlike expression \\\* to accomplish that goal.

With that interpretation,

re.split(r'(?&lt;!\\)\*', ss)


is insufficient for the task. The interpretation should depend on whether there are an even or odd number of backslashes preceding the asterisk.

Search technique

Anything other than a one-pass search is likely doomed to failure.  If you search for literal substrings, you are likely to have problems handling overlapping sequences.  Even if you fix the overlap problem, you would likely still have problems dealing with repeating substrings in the pattern.  If there are multiple wildcards in the pattern, you would also need to support backtracking.

In short, I don't recommend that approach at all.

Driver


   for line in open(sys.argv[1]).read().splitlines():
       if line:
           print is_ss(*line.split(','))



I recommend using fileinput.input() so that the program will read its data from either stdin or a given filename.

Personally, I would also prefer not to read in the entire file at once, for scalability.

I would consider it good practice to limit split() to two elements.  The problem is silent on how a third comma on the line should be interpreted, but I would treat it as a literal character in the globlike expression (even if it will always result in a match failure).

I would also decompose the problem differently.  is_ss(s, ss) (confusingly named function and parameters, by the way) is responsible for interpreting ss as a pattern, performing the match, and returning "true" or "false".  That's actually two or three separate tasks.

Suggested solution

Since matching individual substrings is a problematic strategy, and writing a pattern matcher from scratch seems like it would be tedious, I've chosen to translate globs into regular expressions.  The trick is to escape everything except unescaped asterisks.

As a bonus, obtaining a regular expression converts the task to a solved problem.  The performance characteristics of regular expression matching in Python are well known.  Pushing the responsibility of performing the match to the main loop is also a benefit, in my opinion.

import fileinput
import itertools
import os
import re

def globlike_to_re(expr):
    def unescaped_globlike_to_re(expr):
        '''Convert a globlike expression to a regex pattern.  The expr
        parameter is guaranteed to contain no backslashes, unless it is the
        last character.  Therefore, any asterisk in expr means "match
        anything", and everything else is taken literally.'''
        return r'.*'.join(re.escape(literal) for literal in expr.split('*'))

    # [glob, literal, glob, literal, ..., glob]
    pairs = re.split(r'\\(.)', expr)

    lang = itertools.cycle([unescaped_globlike_to_re, re.escape])
    return re.compile(''.join(interp(expr) for interp, expr in zip(lang, pairs)))

for line in fileinput.input():
    haystack, needle = line.rstrip(os.linesep).split(',', 2)
    print 'true' if globlike_to_re(needle).search(haystack) else 'false'