inet::PatternMatcher Class Reference

Glob-style pattern matching class, adopted to special OMNeT++ requirements. More...

#include <PatternMatcher.h>

Classes
struct	Elem

Public Member Functions
	PatternMatcher ()
	Constructor. More...
	PatternMatcher (const char *pattern, bool dottedpath, bool fullstring, bool casesensitive)
	Constructor. More...
	~PatternMatcher ()
	Destructor. More...
void	setPattern (const char *pattern, bool dottedpath, bool fullstring, bool casesensitive)
	Sets the pattern to be used by subsequent calls to matches(). More...
bool	matches (const char *line)
	Returns true if the line matches the pattern with the given settings. More...
const char *	patternPrefixMatches (const char *line, int suffixoffset)
	Similar to matches(): it returns non-nullptr iif (1) the pattern ends in a string literal (and not, say, '*' or '**') which contains the line suffix (which begins at suffixoffset characters of line) and (2) pattern matches the whole line, except that (3) in matching the pattern's last string literal, it is also accepted if line is shorter than the pattern. More...
std::string	debugStr ()
	Returns the internal representation of the pattern as a string. More...
void	dump ()
	Prints the internal representation of the pattern on the standard output. More...

Static Public Member Functions
static bool	containsWildcards (const char *pattern)
	Utility function to determine whether a given string contains wildcards. More...

Private Types
enum	ElemType {   LITERALSTRING = 0, ANYCHAR, COMMONCHAR, SET,   NEGSET, NUMRANGE, ANYSEQ, COMMONSEQ,   END }

Private Member Functions
void	parseSet (const char *&s, Elem &e)
void	parseNumRange (const char *&s, Elem &e)
void	parseLiteralString (const char *&s, Elem &e)
bool	parseNumRange (const char *&str, char closingchar, long &lo, long &up)
std::string	debugStrFrom (int from)
bool	isInSet (char c, const char *set)
bool	doMatch (const char *line, int patternpos, int suffixlen)

Private Attributes
std::vector< Elem >	pattern
bool	iscasesensitive = false
std::string	rest

Detailed Description

Glob-style pattern matching class, adopted to special OMNeT++ requirements.

One instance represents a pattern to match.

Pattern syntax:

• ? : matches any character except '.'
• * : matches zero or more characters except '.'
• ** : matches zero or more character (any character)
• {a-z} : matches a character in range a-z
• {^a-z} : matches a character NOT in range a-z
• {32..255} : any number (ie. sequence of digits) in range 32..255 (e.g. "99")
• [32..255] : any number in square brackets in range 32..255 (e.g. "[99]")
• backslash \ : takes away the special meaning of the subsequent character

The "except '.'" phrases in the above rules apply only in "dottedpath" mode (see below).

There are three option switches (see setPattern() method):

• dottedpath: dottedpath=yes is the mode used in omnetpp.ini for matching module parameters, like this: "**.mac[*].retries=9". In this mode mode, '*' cannot "eat" dot, so it can only match one component (module name) in the path. '**' can be used to match more components. (This is similar to e.g. Java Ant's usage of the asterisk.) In dottedpath=false mode, '*' will match anything.
• fullstring: selects between full string and substring match. The pattern "ate" will match "whatever" in substring mode, but not in full string mode.
• case sensitive: selects between case sensitive and case insensitive mode.

Rule details:

• sets, negated sets: They can contain several character ranges and also enumeration of characters. For example: "{_a-zA-Z0-9}","{xyzc-f}". To include '-' in the set, put it at a position where it cannot be interpreted as character range, for example: "{a-z-}" or "{-a-z}". If you want to include '}' in the set, it must be the first character: "{}a-z}", or as a negated set: "{^}a-z}". A backslash is always taken as literal backslash (and NOT as escape character) within set definitions. When doing case-insensitive match, avoid ranges that include both alpha (a-zA-Z) and non-alpha characters, because they might cause funny results.
• numeric ranges: only nonnegative integers can be matched. The start or the end of the range (or both) can be omitted: "{10..}", "{..99}" or "{..}" are valid numeric ranges (the last one matches any number). The specification must use exactly two dots. Caveat: "*{17..19}" will match "a17","117" and "963217" as well.

Member Enumeration Documentation

enum inet::PatternMatcher::ElemType

private

Enumerator
LITERALSTRING
ANYCHAR
COMMONCHAR
SET
NEGSET
NUMRANGE
ANYSEQ
COMMONSEQ
END

                  {
        LITERALSTRING = 0,
        ANYCHAR,
        COMMONCHAR,    // any char except "."
        SET,
        NEGSET,
        NUMRANGE,
        ANYSEQ,    // "**": sequence of any chars
        COMMONSEQ,    // "*": seq of any chars except "."
        END
    };

Constructor & Destructor Documentation

inet::PatternMatcher::PatternMatcher

(

)

Constructor.

{
}

inet::PatternMatcher::PatternMatcher	(	const char *	pattern,
		bool	dottedpath,
		bool	fullstring,
		bool	casesensitive
	)

Constructor.

{
    setPattern(pattern, dottedpath, fullstring, casesensitive);
}

inet::PatternMatcher::~PatternMatcher

(

)

Destructor.

{
}

Member Function Documentation

bool inet::PatternMatcher::containsWildcards ( const char *  pattern )

static

Utility function to determine whether a given string contains wildcards.

If it does not, a simple strcmp() might be a faster option than using PatternMatcher.

{
    return strchr(pattern, '?') || strchr(pattern, '*') ||
           strchr(pattern, '\\') || strchr(pattern, '{') ||
           strstr(pattern, "..");
}

std::string inet::PatternMatcher::debugStr ( )

inline

Returns the internal representation of the pattern as a string.

May be useful for debugging purposes.

{ return debugStrFrom(0); }

std::string inet::PatternMatcher::debugStrFrom ( int  from )

private

{
    std::string result;
    for (int k = from; k < (int)pattern.size(); k++) {
        Elem& e = pattern[k];
        switch (e.type) {
            case LITERALSTRING:
                result = result + "\"" + e.literalstring + "\"";
                break;

            case ANYCHAR:
                result += "?!";
                break;

            case COMMONCHAR:
                result += "?";
                break;

            case SET:
                result = result + "SET(" + e.setchars + ")";
                break;

            case NEGSET:
                result = result + "NEGSET(" + e.setchars + ")";
                break;

            case NUMRANGE: {
                char buf[100];
                sprintf(buf, "%ld..%ld", e.fromnum, e.tonum);
                result += buf;
            } break;

            case ANYSEQ:
                result += "**";
                break;

            case COMMONSEQ:
                result += "*";
                break;

            case END:
                break;

            default:
                ASSERT(0);
                break;
        }
        result += " ";
    }
    return result;
}

bool inet::PatternMatcher::doMatch ( const char *  line, int  patternpos, int  suffixlen  )

private

Referenced by matches(), and patternPrefixMatches().

{
    while (true) {
        Elem& e = pattern[k];
        long num;    // case NUMRANGE
        int len;    // case LITERALSTRING
        switch (e.type) {
            case LITERALSTRING:
                len = e.literalstring.length();
                // special case: last string literal with prefix match: allow s to be shorter
                if (suffixlen > 0 && k == (int)pattern.size() - 2)
                    len -= suffixlen;
                // compare
                if (iscasesensitive ?
                    strncmp(s, e.literalstring.c_str(), len) :
                    strncasecmp(s, e.literalstring.c_str(), len)
                    )
                    return false;
                s += len;
                break;

            case ANYCHAR:
                if (!*s)
                    return false;
                s++;
                break;

            case COMMONCHAR:
                if (!*s || *s == '.')
                    return false;
                s++;
                break;

            case SET:
                if (!*s)
                    return false;
                if (!isInSet(*s, e.setchars.c_str()))
                    return false;
                s++;
                break;

            case NEGSET:
                if (!*s)
                    return false;
                if (isInSet(*s, e.setchars.c_str()))
                    return false;
                s++;
                break;

            case NUMRANGE:
                if (!opp_isdigit(*s))
                    return false;
                num = atol(s);
                while (opp_isdigit(*s))
                    s++;
                if ((e.fromnum >= 0 && num < e.fromnum) || (e.tonum >= 0 && num > e.tonum))
                    return false;
                break;

            case ANYSEQ:
                // potential shortcuts: if pattern ends in ANYSEQ, rest of the input
                // can be anything; if pattern ends in ANYSEQ LITERAL, it's enough if
                // input ends in the literal string
                if (k == (int)pattern.size() - 2)
                    return true;
                if (k == (int)pattern.size() - 3 && pattern[k + 1].type == LITERALSTRING)
                    return opp_stringendswith(s, pattern[k + 1].literalstring.c_str());

                // general case
                while (true) {
                    if (doMatch(s, k + 1, suffixlen))
                        return true;
                    if (!*s)
                        return false;
                    s++;
                }
                break;    // at EOS

            case COMMONSEQ:
                while (true) {
                    if (doMatch(s, k + 1, suffixlen))
                        return true;
                    if (!*s || *s == '.')
                        return false;
                    s++;
                }
                break;

            case END:
                return !*s;

            default:
                ASSERT(0);
                break;
        }
        k++;
        ASSERT(k < (int)pattern.size());
    }
}

void inet::PatternMatcher::dump ( )

inline

Prints the internal representation of the pattern on the standard output.

May be useful for debugging purposes.

{ printf("%s", debugStr().c_str()); }

bool inet::PatternMatcher::isInSet ( char  c, const char *  set  )

private

Referenced by doMatch().

{
    ASSERT((strlen(set) & 1) == 0);
    if (!iscasesensitive)
        c = opp_toupper(c); // set is already uppercase here
    while (*set) {
        if (c >= *set && c <= *(set + 1))
            return true;
        set += 2;
    }
    return false;
}

bool inet::PatternMatcher::matches

(

const char *

line

)

Returns true if the line matches the pattern with the given settings.

See setPattern().

Referenced by inet::ospf::OSPFConfigReader::loadConfigFromXML(), and inet::IPv4RoutingTable::updateNetmaskRoutes().

{
    ASSERT(pattern[pattern.size() - 1].type == END);

    // shortcut: omnetpp.ini keys often begin with "*" or "**"
    // but end in a string literal. So it's usually a performance win to
    // to first check that the last string literal of the pattern matches
    // the end of the string. (We do the shortcut only in the case-sensitive
    // case. omnetpp.ini is case sensitive.)

    if (pattern.size() >= 2 && iscasesensitive) {
        Elem& e = pattern[pattern.size() - 2];
        if (e.type == LITERALSTRING) {
            // return if last 2 chars don't match
            int pattlen = e.literalstring.size();
            int linelen = strlen(line);
            if (pattlen >= 2 && linelen >= 2 && (line[linelen - 1] != e.literalstring.at(pattlen - 1) ||
                                                 line[linelen - 2] != e.literalstring.at(pattlen - 2))) //FIXME why doesn't work for pattlen==1 ?
                return false;
        }
    }

    // perform full-blown pattern matching
    return doMatch(line, 0, 0);
}

void inet::PatternMatcher::parseLiteralString ( const char *&  s, Elem &  e  )

private

Referenced by setPattern().

{
    e.type = LITERALSTRING;
    while (*s && *s != '?' && *s != '{' && *s != '*') {
        long dummy;
        const char *s1;
        if (*s == '\\')
            e.literalstring += *(++s);
        else
            e.literalstring += *s;
        if (*s == '[' && parseNumRange((s1 = s), ']', dummy, dummy))
            break;
        s++;
    }
}

void inet::PatternMatcher::parseNumRange ( const char *&  s, Elem &  e  )

private

Referenced by parseLiteralString(), and setPattern().

bool inet::PatternMatcher::parseNumRange ( const char *&  str, char  closingchar, long &  lo, long &  up  )

private

{
    //
    // try to parse "[n..m]" or "{n..m}" and return true on success.
    // str should point at "[" or "{"; on success return it'll point to "]" or "}",
    // and on failure it'll be unchanged. n and m will be stored in lo and up.
    // They are optional -- if missing, lo or up will be set to -1.
    //
    lo = up = -1L;
    const char *s = str + 1;    // skip "[" or "{"
    if (opp_isdigit(*s)) {
        lo = atol(s);
        while (opp_isdigit(*s))
            s++;
    }
    if (*s != '.' || *(s + 1) != '.')
        return false;
    s += 2;
    if (opp_isdigit(*s)) {
        up = atol(s);
        while (opp_isdigit(*s))
            s++;
    }
    if (*s != closingchar)
        return false;
    str = s;
    return true;
}

void inet::PatternMatcher::parseSet ( const char *&  s, Elem &  e  )

private

Referenced by setPattern().

{
    s++;    // skip "{"
    e.type = SET;
    if (*s == '^') {
        e.type = NEGSET;
        s++;
    }
    // Note: to make "}" part of the set, it must be first within the braces
    const char *sbeg = s;
    while (*s && (*s != '}' || s == sbeg)) {
        char range[3];
        range[2] = 0;
        if (*(s + 1) == '-' && *(s + 2) && *(s + 2) != '}') {
            // store "A-Z" as "AZ"
            range[0] = *s;
            range[1] = *(s + 2);
            s += 3;
        }
        else {
            // store "X" as "XX"
            range[0] = range[1] = *s;
            s++;
        }
        if (!iscasesensitive) {
            // if one end of range is alpha and the other is not, funny things will happen
            range[0] = opp_toupper(range[0]);
            range[1] = opp_toupper(range[1]);
        }
        e.setchars += range;
    }
    if (!*s)
        throw cRuntimeError("unmatched '}' in expression");
    s++;    // skip "}"
}

const char * inet::PatternMatcher::patternPrefixMatches	(	const char *	line,
		int	suffixoffset
	)

Similar to matches(): it returns non-nullptr iif (1) the pattern ends in a string literal (and not, say, '*' or '**') which contains the line suffix (which begins at suffixoffset characters of line) and (2) pattern matches the whole line, except that (3) in matching the pattern's last string literal, it is also accepted if line is shorter than the pattern.

If the above conditions hold, it returns the rest of the pattern. The returned pointer is valid until the next call to this method.

This method is used by cIniFile's getEntriesWithPrefix(), used e.g. to find RNG mapping entries for a module. For that, we have to find all ini file entries (keys) like "net.host1.gen.rng-NN" where NN=0,1,2,... In cIniFile, every entry is a pattern ("**.host*.gen.rng-1", "**.*.gen.rng-0", etc.). So we'd invoke patternPrefixMatches("net.host1.gen.rng-", 13) (i.e. suffix=".rng-") to find those entries (patterns) which can expand to "net.host1.gen.rng-0", "net.host1.gen.rng-1", etc.

See matches().

{
    if (!iscasesensitive)
        throw cRuntimeError("PatternMatcher: patternPrefixMatches() doesn't support case-insensitive match");

    // pattern must end in a literal string...
    ASSERT(pattern[pattern.size() - 1].type == END);
    if (pattern.size() < 2)
        return nullptr;
    Elem& e = pattern[pattern.size() - 2];
    if (e.type != LITERALSTRING)
        return nullptr;

    // ...with the suffixlen characters at the end of 'line'
    const char *pattstring = e.literalstring.c_str();
    const char *p = strstr(pattstring, line + suffixoffset);
    if (!p)
        return nullptr;
    p += strlen(line + suffixoffset);
    rest = p;
    int pattsuffixlen = e.literalstring.size() - (p - pattstring);

    // pattern, if we cut off the 'rest', must exactly match 'line'
    return doMatch(line, 0, pattsuffixlen) ? rest.c_str() : nullptr;
}

void inet::PatternMatcher::setPattern	(	const char *	pattern,
		bool	dottedpath,
		bool	fullstring,
		bool	casesensitive
	)

Sets the pattern to be used by subsequent calls to matches().

See the general class description for the meaning of the rest of the arguments. Throws cException if the pattern is bogus.

Referenced by PatternMatcher().

{
    pattern.clear();
    iscasesensitive = casesensitive;

    // "tokenize" pattern
    const char *s = patt;
    while (*s != '\0') {
        Elem e;
        switch (*s) {
            case '?':
                e.type = dottedpath ? COMMONCHAR : ANYCHAR;
                s++;
                break;

            case '[':
                if (pattern.empty() || pattern.back().type != LITERALSTRING || !parseNumRange(s, ']', e.fromnum, e.tonum))
                    parseLiteralString(s, e);
                else
                    e.type = NUMRANGE;
                break;

            case '{':
                if (parseNumRange(s, '}', e.fromnum, e.tonum)) {
                    e.type = NUMRANGE;
                    s++;
                }
                else
                    parseSet(s, e);
                break;

            case '*':
                if (*(s + 1) == '*') {
                    e.type = ANYSEQ;
                    s += 2;
                }
                else {
                    e.type = dottedpath ? COMMONSEQ : ANYSEQ;
                    s++;
                }
                break;

            default:
                parseLiteralString(s, e);
                break;
        }
        pattern.push_back(e);
    }

    if (!fullstring) {
        // for substring match, we add "**" at both ends of the pattern (unless already there)
        Elem e;
        e.type = ANYSEQ;
        if (pattern.empty() || pattern.back().type != ANYSEQ)
            pattern.push_back(e);
        if (pattern.front().type != ANYSEQ)
            pattern.insert(pattern.begin(), e);
    }
    Elem e;
    e.type = END;
    pattern.push_back(e);
}

Member Data Documentation

bool inet::PatternMatcher::iscasesensitive = false

private

Referenced by doMatch(), isInSet(), matches(), parseSet(), patternPrefixMatches(), and setPattern().

std::vector<Elem> inet::PatternMatcher::pattern

private

Referenced by debugStrFrom(), doMatch(), matches(), patternPrefixMatches(), and setPattern().

std::string inet::PatternMatcher::rest

private

Referenced by patternPrefixMatches().

---

The documentation for this class was generated from the following files:

• PatternMatcher.h
• PatternMatcher.cc