Match strings with wildcards

Question

Problem: given any input string that does not contain null bytes, determine whether or not the input string matches glob as defined below:

null   is disallowed in both string in glob
*      matches zero or more characters
**     is disallowed in glob
?      matches exactly 1 character
[ch]   matches a character class of the specified characters
       to include ] in a class, it must be the first character
[^ch]  matches a character class of all but specified characters
       to include ] in a class, it must be the first character after ^

The empty glob only matches the empty string.

The system glob() on the target platform implements glob where * doesn't match a /, so you can't use it. This has infested all shells. You could try converting to a regex; however this won't be as easy it it looks.

You must specify an encoding for your program. Your program must be valid in that encoding. All bytes including null are allowed in cp437. Your score is the number of characters in your encoding.

Bonus: If your program is expressed in a well-known encoding that uses 6 or fewer bits, your score is multiplied by the number of bits used in the encoding and divided by 7. Your program will be passed its arguments in ASCII in that case.

Your program will receive the string to match or not as the first argument and the glob pattern as the second argument. Your return code must be 0 on match and nonzero on nonmatch.

You may leave it undefined what happens if you get passed a disallowed glob.

Standard loopholes are disallowed; however the following are allowed:

 You may compress your program but it must work if executed directly.
 Binaries are allowed. Submit a disassembly with it so I can read it.
 Using two different chars which look the same is allowed.
 You may use trigraphs (but I can't see how it helps).

Examples:

"w*c*d" matches "wildcard" but doesn't match "wildcards"
"ww*w*d" matches "wwwdwd" but doesn't match "wwd"
"ww*[w-c]?*" matches "www-" and "wwcc" but doesn't match "wwc"
"[a-c]" matches "-" but doesn't match "b"
"^[*][^]]" matches "^*[" but doesn't match "^?[" or "^*]" or "**]"

Answer 1

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))

=> T

Answer 2

MUMPS, 397 387 bytes

Note that this code uses features of Caché ObjectScript (specifically, the * designator in a $EXTRACT call) and does not conform to the ANSI MUMPS standard.

f(g,s) f i=1:1:$L(g) d
    . s c=$E(g,i) i 'm s:"*?[]"'[c p=p_"1"""_c_"""" s:c="*" p=p_".E" s:c="?" p=p_"1E"
    . i c="]" s p=p_"1"_$E(b,1,*-1)_")" s m=0
    . s:c="[" a=$E(g,i+1)="^",m=a+1,b="(",i=i+a
    . i m s:$E(g,i+1)="]" d=1 s k=$F(g,"]",i+d)-2+d,r=$E(g,i+1,k),i=k
    . f j=1:1:$L(r) s:m=1 b=b_"1"""_$E(r,j)_""","
    . i m=2 f j=0:1:127 s:r'[$C(j) b=b_"1"""_$S(j=34:"""""",1:$C(j))_""","
    q s?@p

Haha, OP! I've foiled your plans! Sure, your glob syntax might be tricky to convert to a regex, but my language has no regexes! Instead, it has a crippled form of "pattern matching" (see docs, section 5.7) that happens to be pretty much exactly powerful enough to handle these globs.

Basically, what the code does is it converts OP-style globs into a string corresponding to the pattern match, and then evals that string, and tests the input string against the result of that eval. The one tricky point is that MUMPS pattern matches don't have a notion of an inverted character class ([^abc]), so we instead have to construct a character class consisting of all the ASCII characters except the ones specified in in the inverted character class.

Here are some correspondences between OP-style globs and MUMPS pattern matches:

OP              MUMPS
-----------------------------------------------------------
w*c*d           1"w".E1"c".E1"d"
ww*w*d          1"w"1"w".E1"w".E1"d"
ww*[w-c]?*      1"w"1"w".E1(1"w",1"-",1"c")1E.E
[a-c]           1(1"a",1"-",1"c")
^[*][^]]        [doesn't print well, because of the inverted character class thing]

There is probably room for additional golfing here. Here is an ungolfed version:

match(glob,string) ;
    ; the golfed version assumes a clean symbol table; here, I've explicitly cleaned it.
    new i,pattern,char,mode,buffer,range,advance,delta,j,k
    for i=1:1:$LENGTH(glob) do
    . set char=$EXTRACT(glob,i)
    . if ("*?[]"'[char),(mode=0) do
    . . set pattern=pattern_"1"""_char_"""" ; 1 of `char`
    . if (char="*"),(mode=0) do
    . . set pattern=pattern_".E" ; 0+ of any character
    . if (char="?"),(mode=0) do
    . . set pattern=pattern_"1E" ; 1 of any character
    . if (char="]") do
    . . set pattern=pattern_"1"_$EXTRACT(buffer,1,$LENGTH(buffer)-1)_")"
    . . set mode=0
    . if (char="[") do
    . . set advance=($EXTRACT(glob,i+1)="^") ; 0 or 1
    . . set mode=advance+1 ; 1 = in a char class; 2 = in an inverted char class
    . . set buffer="(" ; begin constructing an alternation
    . . set i=i+advance
    . if (mode'=0) do
    . . if ($EXTRACT(glob,i+1)="]") do
    . . . set delta=1
    . . . set k=$FIND(glob,"]",i+delta)-2+delta
    . . . set range=$EXTRACT(glob,i+1,k)
    . . . set i=k
    . for j=1:1:$LENGTH(range) do
    . . if (mode=1) do
    . . . set buffer=buffer_"1"""_$EXTRACT(range,j)_"""," ; add a character to the alternation
    . if (mode=2) do
    . . for j=0:1:127 do
    . . . if (range'[$CHAR(j)) do
    . . . . set buffer=buffer_"1"""_$SELECT(j=34:"""""",1:$CHAR(j))_""","
    quit string?@pattern ; eval `pattern` and test `string` against it, and return the outcome (0 or 1)

Answer 3

Ceylon, 3514 2586 2360 2248 2228 2196 2059 1882 1620 1147 1130 858 830 693 658 bytes

import ceylon.language{B=Boolean,S=String,C=Character,o=false,r=process}shared void g(){B n(B(S)l,B(S)r)(S c)=>any{for(i in 0..c.size)l(c[0:i])&&r(c[i...])};B q(S c)=>c.size==1;B d({C*}s,B n)(S c){if(q(c),exists i=c[0]){return n!=i in s;}return o;}[B(S),S]h(S r){assert(exists s=r[0],exists e=r.firstOccurrence(']'));return[s=='^'then d(r[1..e],true)else d(r[...e],false),r[e+1...]];}B(S)p(S x){if(exists f=x[0]){value r=(f=='*'then[(S c)=>true,x.rest])else(f=='?'then[q,x.rest])else(f=='['then h(x.rest))else[d({f},o),x.rest];return n(r[0],p(r[1]));}else{return S.empty;}}assert(exists x=r.arguments[1],exists c=r.arguments[0]);r.exit(p(x)(c)then 0else 1);}

It seemed first that converting the glob to regular expressions is the easiest, but it also means escaping everything which is special in regular expressions but not in our globs ... I might try this in a different answer.

Due to popular demand I removed most of the the how-I-got-there .. who is interested, can have a look into the history.

So I build a new (limited) regexp-like matching engine, and a parser to convert our wildcard strings into such strings. (And some boiler plate for command line access and return code generation.)

Here is the same program formatted (i.e. with added whitespace) and with some documentation annotations:

import ceylon.language {
    B=Boolean,
    S=String,
    C=Character,
    o=false,
    r=process
}
"""A glob evaluation program.
   Takes two command line arguments, first is a candidate string,
   second one is a wildcard expression.

    Exits with code 0 if the expression is well-formed and
    matches the candidate, otherwise exits with 1. 
   """
shared void g() {
    """A string predicate build from a left and a right predicate.
       It matches a string if that can be split in two substrings
       so the first one is matched by the left expression and
       the second one by the right expression.
       """
    B n(B(S) l, B(S) r)(S c) =>
            any {
        for (i in 0..c.size) l(c[0:i]) && r(c[i...])
    };

    """An expression which matches any string of length 1 (i.e. a single character).
       This corresponds to the question mark (`?`), therefore the name.
       """
    B q(S c) => c.size == 1;

    """A character class, i.e. an expression which matches any string of length 1,
       as long at it is (or is not) in a given list of characters.
       """
    B d(
        "The characters to be matched (or excluded)"
        {C*} s,
        "Is this negated? If true, matches only characters not in the list."
        B n)
            (
        "The candidate string."
        S c) {
        if (q(c), exists i = c[0]) {
            return n != i in s;
        }
        return o;
    }

    """Parses a started character class (i.e. the stuff after the `[`).

       Returns a tuple of the constructed matching function
       and the remaining string to be parsed for further expressions.
       """
    throws (`class AssertionError`, "if the expression is not well-formed, i.e. there is no `]` following.")
    [B(S), S] h(S r) {
        assert (exists s = r[0], exists e = r.firstOccurrence(']'));
        return [s == '^' then d(r[1..e], true) else d(r[...e], false), r[e + 1 ...]];
    }

    """Parses an glob expression from a string.
       Returns a string predicate.
       """
    B(S) p(
        "The string with the wildcard expression."
        S x) {
        if (exists f = x[0]) {
            value r = (f == '*' then [(S c) => true, x.rest])
                    else (f == '?' then [q, x.rest])
                    else (f == '[' then h(x.rest))
                    else [d({ f }, o), x.rest];
            return n(r[0], p(r[1]));
        } else {
            return S.empty;
        }
    }
    assert (exists x = r.arguments[1], exists c = r.arguments[0]);
    r.exit(p(x)(c) then 0 else 1);
}

I'm not sure if this is actually readable enough ... see the history of this answer for the original version with more readable names (and which was using interfaces and objects instead of just functions).

Some used tricks to make this shorter:

• import with alias – we use String, Boolean and Character quite often, so give them one-letter aliases. When we are already doing this, adding the renaming for process (used three times) and false (used twice) doesn't take much overhead. (This only helps for stuff used several times – the ceylon.language stuff is imported automatically, so we have some overhead here.)
• The possibleMatchLengths method was an optimization for speed – not needed when we are code-golfing. (I guess this can make matching quite slow in some extreme cases.)
• the Implementations of the string attribute was also removed, it was just there for debugging the initial versions.
• Instead of the implementations of the Glob interface in the first versions, we have just functions Boolean(String) (or B(S) in our short format), which saves quite some braces and class/object, and some functions returning such functions. Ceylon has a nice syntax for defining functions which return functions, used for the GlobList g and the CharacterClass c – simply a function with multiple argument lists.
• I unified the methods for CharacterClass and NegatedCharacterClass, passing a boolean parameter for negated. It is used as negated != i in chars (shorter n!=i in s) instead of having one function with i in s and one with !i in s (and both having the remaining conditions twice).
• The object/function emptyGlob was replaced by the static Reference String.empty (written S.empty, of course).
• Where a function consists of just one return statement, we can write it with the "fat arrow" notation and save the braces and the return.
• If such a function is used just once, sometimes we can put it directly where used, as an anonymous function definition. This is used for the * implementation.
• The function q (for the question mark) is in addition used in the definition of the character class function d, as q(c) is shorter than c.size==1.
• Instead of first defining a value with value f = ... or even with type Character f = ... and then doing an if (exists f) { or assert(exists f);, we can move the definition into the if or assert, saving some characters.
• If we want to pass an iterable constructed from a comprehension to a function (like the any function used in the definition of g), we can write any{...} instead of any({...}) – this is the named argument syntax, which converts its last entry, if it's a comprehension, into an iterable, if the function accepts that.

Answer 4

CJam, 125

{AC+:A;}:F;0alqW+:X;{"*?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)
^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F"N/T=S/(C#=~}fCX,(\-!

CJam has no regular expressions (yet), so I just implemented the wildcard matching directly.
The encoding here is plain old ASCII (I might try some compression tricks later).

Try it online

Explanation:

The idea is to go through the pattern (glob) and keep a list of indices possibly reached so far in the input string. Initial list is [0], ? advances all indices by 1, * goes to all indices from the minimum reached so far to the end of the string, and character sets and other non-special characters just select the indices that match and advance them by 1. At the end, the string matches if the list of indices contains the string length.

Character sets are constructed on the fly and recorded as a string A and a boolean flag B (for positive/negative match), and used when reaching the closing ].

{…}:F;      define a function F
  AC+:A;    add variable C to variable A (A+=C)
0a          push [0] (initial array of indices, let's call it I)
             it will be kept and updated on the stack
l           read the first input line (containing the pattern)
q           read the rest of the input (the string to match)
W+          append the number -1 (as an array element, following the characters)
             this is a dummy guard value that avoids costly empty-string checks
:X;         save the array in X
{…}fC       for each character C in the pattern
  "…"       push that long string, containing code to handle various cases
  N/        split into (two) lines
  T=        get the T'th line; T is 1 when parsing a character set and 0 otherwise
             (T is initially 0 by default)
  S/        split by space into an array of strings
  (         take out the first item (containing special characters to check)
  C#        find the index of C in that string
  =         get the corresponding string from the array
             (when C is not found, # returns -1 which gets the last array item)
  ~         execute that string
X,(         get the length of X and decrement it
             (to get the length of the input string)
\-          calculate the set difference between it and I (the list of indices)
             the result is empty (false) iff I contained the string length
!           negate, to obtain the final 1/0 result

Now the long string with various pieces of code. Each line has a few characters to check and then a block for handling each one, and the default case.

First line: *?[ _{0=X,,>}& :) 1:T:B;L:A; {X=C=},:)

*?[       special characters to look for
######### first block, corresponding to character *
_         duplicate I on the stack
{…}&      if I is not empty
  0=      get the first (smallest) index from I
  X,      get the length of X (1 longer than the input string)
  ,       make an array [0 1 2 … length(input string)]
  >       slice the array starting at the smallest index from I
######### second block, corresponding to character ?
:)        increment all items of I
######### third block, corresponding to character [
1:T       set T=1, causing the next characters to be processed with the 2nd line
:B;       also set B=1, the boolean flag signifying positive match
L:A;      initialize A (the array of characters) with an empty string/array
######### last block, corresponding to other regular characters
{…},      filter I's items, using the block as a boolean condition
  X=      get the character from X at the given index (it wraps around)
           if the input string was empty, this will be -1 (the dummy value)
  C=      compare to C (the current character in the pattern)
:)        increment the remaining indices

Second line (for character sets): ^] A!B&{0:B;}{F}? A{0:T;{X=A-!B=},:)}{F}? F

^]        special characters to look for
######### first block, corresponding to character ^
A!B&      calculate not(A) & B, which is 1 (true) iff A is empty and B is 1
{…}       if true (first character and positive match, i.e. we're at "[^")
  0:B;    set B=0 (switch to negative match)
{…}       else
  F       call F, which just adds the character C to A
?         end if
######### second block, corresponding to character ]
A{…}      if A is not empty (it's a closing "]")
  0:T;    set T to 0, switching back to the first line
  {…},    filter I's items, using the block as a boolean condition
    X=    get the character from X at the given index
           if the input string was empty, this will be -1
    A-    calculate the set difference between it and A
    !     negate, obtaining 1 if the character was in A and 0 if it was not
    B=    compare to B (the positive/negative match indicator)
  :)      increment the remaining indices
{…}       else (A is empty, i.e. we're at "[]" or "[^]")
  F       call F to add the character to A
?         end if
######### last block, corresponding to other regular characters
F         call F

Answer 5

Python 3, 209 207 bytes

The general strategy is transforming the glob spec into a regex. That's accomplished by a function r, passed as the replacement parameter to re.sub(), (or s() in this case). If no match is found, a run-time error is thrown, causing a positive exit code.

import sys,re
_,t,g=sys.argv
s=re.sub
def r(m):a,b,c,d,e=m.groups();return a and s(r"(?=[-\\])",r"\\",a)or b and".*"or c and"."or d and"\\"+d or e
re.match(s(r"(\[\^?.+?\])|(\*)|(\?)|(\W)|(.)",r,g)+"$",t).re

The patterns produced for the example globs show how it works.

Glob            Regex pattern
w*c*d           w.*c.*d$
ww*w*d          ww.*w.*d$
ww*[w-c]?       ww.*[w\-c].$
[a-c]           [a\-c]$
^[*][^]]        \^[*][^]]$
a[\]b           a[\\]b

Answer 6

Perl, 88 bytes

$_=pop;s/((\*)|\?)|(\[\^?\]?)(.*?)\]|\W/$1?".$2":$3?qr#$3\Q$4\E]#:"\\$&"/eg/pop=~/^$_\z/

The encoding is ASCII. This works by translating to regular expressions with regular expressions. It exits with a division by zero error (hence, nonzero status) on match failure.

Some ideas adapted from recursive’s Python solution.