Match strings with wildcards
Common Lisp, 368 340

Encoding is implementation-dependent, but UTF-8 is generally supported among implementations (see also the set of standard characters that must be supported).



(ql:quickload'cl-ppcre)(lambda(s g)(ppcre:scan(do(e(L(coerce g'list))c p)((not L)`(:sequence,@(reverse e):end-anchor))(push(case(setf c(pop L))(#\*'(:regex".*"))(#\? :everything)(#\[(prog1`(,(or(and(char=(car L)#\^)(pop L):inverted-char-class):char-class),@(subseq L 0(setf p(position #\] L :start 1))))(setf L(nthcdr(1+ p)L))))(t c))e))s))


Pretty-printed

(lambda (s g)
  (cl-ppcre:scan
   (do (e
        (l (coerce g 'list))
        c
        p)
       ((not l) `(:sequence ,@(reverse e) :end-anchor))
     (push
      (case (setf c (pop l))
        (#\* '(regex".*")
        (#\? :everything)
        (#\[
         (prog1
             `(,(if (char= (car l) #\^)
                    (prog1 :inverted-char-class (pop l))
                    :char-class)
               ,@(subseq l 0 (setf p (position #\] l :start 1))))
           (setf l (nthcdr (1+ p) l))))
        (t c))
      e))
   s))


Converting to regex is not so hard when using non-string representations of regexes. CL-PPCRE is a regular expression library by Edi Weitz which accepts two ways of defining such expressions:


the usual string-based syntax, or
a more lispy approach using a DSL


Today I answered a question about alternative syntaxes for regular expressions, and this challenge is a good example of why a structured format can be useful instead of strings.

Example

For the following glob, "ww*[w-c]?*", the regular expression being built is described by this form:

(:sequence #\w
           #\w
           (:regex ".*")
           (:char-class #\w #\- #\c)
           :everything
           (:regex ".*"))


And we match "www-". The (:char-class ...) list takes indiviudal charaters, which does not need escaping like it would if I wrote "[w-c]" as a string regex.

Test suite

(loop for (glob match no-match) in
      '(("w*c*d"      ("wildcard")    ("wildcards"))
        ("ww*w*d"     ("wwwdwd")      ("wwd"))
        ("ww*[w-c]?*" ("www-" "wwcc") ("wwc"))
        ("[a-c]"      ("-")           ("b"))
        ("^[*][^]]"   ("^*[")         ("^?[" "^*]" "**]"))
        ("w*\\*s"     ("wild\\ness")  ()))

      for matchp = (lambda(s)(funcall *fun* s glob))

      always (every matchp match)
      never (some matchp no-match))

=&gt; T