Home /Examples/lib/examples/regex/MODERATE-wildcard-match.sleela

MODERATE-wildcard-match.sleela

lib/examples/regex/MODERATE-wildcard-match.sleela · 71 line(s) · sleela

#sleela 1.7
// MODERATE: glob-style matching with '?' (any one character) and '*' (any run,
// including empty). Implemented on arrays of character codes. We use the code
// -1 inside a pattern to mean '?' and -2 to mean '*', so the matcher stays pure
// arithmetic. This is the recursive-free, two-pointer backtracking algorithm
// that every shell uses for filename globbing.
class ModerateWildcardMatch {
    static int ANY1 = -1;   // '?'
    static int ANYRUN = -2; // '*'

    boolean match(int[] text, int[] pat) {
        int ti = 0;
        int pi = 0;
        int starPi = -1;   // last '*' position in pattern, or -1
        int starTi = 0;    // text position when that '*' was taken

        while (ti < arrayLength(text)) {
            boolean advanced = false;
            if (pi < arrayLength(pat)) {
                int pc = pat[pi];
                if (pc == ANYRUN) {
                    starPi = pi;
                    starTi = ti;
                    pi = pi + 1;
                    advanced = true;
                }
                if (!advanced && (pc == ANY1 || pc == text[ti])) {
                    ti = ti + 1;
                    pi = pi + 1;
                    advanced = true;
                }
            }
            if (!advanced) {
                // Mismatch: if we saw a '*', let it swallow one more char.
                if (starPi >= 0) {
                    pi = starPi + 1;
                    starTi = starTi + 1;
                    ti = starTi;
                }
                if (starPi < 0) return false;
            }
        }
        // Consume any trailing '*' in the pattern.
        while (pi < arrayLength(pat) && pat[pi] == ANYRUN) pi = pi + 1;
        return pi == arrayLength(pat);
    }

    void main() {
        // text = "report.txt"
        int[] text = new int[10];
        text[0]=114; text[1]=101; text[2]=112; text[3]=111; text[4]=114;
        text[5]=116; text[6]=46;  text[7]=116; text[8]=120; text[9]=116;

        // pattern "*.txt"  ->  [* . t x t]
        int[] p1 = new int[5];
        p1[0]=ANYRUN; p1[1]=46; p1[2]=116; p1[3]=120; p1[4]=116;

        // pattern "re?ort*"  ->  [r e ? o r t *]
        int[] p2 = new int[7];
        p2[0]=114; p2[1]=101; p2[2]=ANY1; p2[3]=111; p2[4]=114; p2[5]=116; p2[6]=ANYRUN;

        // pattern "*.csv"  ->  [* . c s v]
        int[] p3 = new int[5];
        p3[0]=ANYRUN; p3[1]=46; p3[2]=99; p3[3]=115; p3[4]=118;

        print("'report.txt' matches '*.txt'   ? " + match(text, p1));
        print("'report.txt' matches 're?ort*' ? " + match(text, p2));
        print("'report.txt' matches '*.csv'   ? " + match(text, p3));
    }
}