RegexMatchCache

Synopsis

Declared in <folly/container/RegexMatchCache.h>

class RegexMatchCache;

Description

A cache around boost::regex_match(string, regex).

For efficiency, assumes several constraints and makes several guarantees.

The data structure owns regexes but does not own strings. The lifetimes of all strings in the cache must surround their additions to the cache and their subsequent removals from the cache or destruction of the cache.

The data structure is in two parts: * A bidirectional match‐cache contains all known matches. * a bidirectional string‐queue contains unknown, hypothetical matches.

Cached lookup operates only over the match‐cache. When the string‐queue for a given regex is not empty, that regex is said to be uncoalesced. Cached lookups are not permitted for an uncoalesced regex; that regex must first be coalesced.

Addition of a string adds the string to the string‐queue corresponding to all known regexes. It does not perform any regex‐match operations.

Addition and coalesce of a regex performs regex‐matches for that regex only. The string‐queue for the given regex is removed and all elements matched against the regex, and matching strings are added to the match‐cache.

Lookup must follow a pattern like this:

if (!cache.isReadyToFindMatches(regex)) { // const cache.prepareToFindMatches(regex); // non‐const } auto matches = cache.findMatches(regex); // const

This is to support concurrent lookups, where the cache is protected by a shared mutex.

The data structure is exception‐safe in a sense. If an exception is thrown within any non‐const member function and escapes, the data structure may purge all cached regexes while leaving all strings. In most such member functions, only a memory‐allocation failure would cause an exception to be thrown. But in prepareToFindMatches, the provided regex may be syntactically invalid and parsing it may throw, or it may be pathological and evaluating it over a string may throw. In any event, the resolution is to clear out all added regexes and to leave only the added strings. The reason is that this resolution is simple and likely to be correct, while any other mechanism would be complex and would be likely to have bugs.

Types

Name

Description

ConsistencyReportMatcher

Recomputes regex/string matches for the consistency check.

FindMatchesUnsafeResult

A non‐owning view over a regex's set of matching strings.

InspectView

A printable view of a cache's internal state.

KeyMap

Interface mapping regex keys back to their string views.

Type Aliases

Name

Description

clock

The clock used for regex last‐access timestamps.

regex_key

The key type identifying a regex.

regex_key_and_view

The composite key and view type identifying a regex.

time_point

The time point type produced by the cache's clock.

Member Functions

Name

Description

RegexMatchCache [constructor]

Constructs an empty cache with no regexes or strings.

~RegexMatchCache [destructor]

Destroys the cache and its owned regexes.

addRegex

Adds a regex to the cache.

addString

Adds a string to the cache without performing any regex matches.

clear

Removes all regexes and strings from the cache.

consistency

Checks the cache for internal consistency, reporting any problems found.

eraseRegex

Removes a regex from the cache.

eraseString

Removes a string from the cache.

findMatches

Returns a copy of the cached matches for a regex.

findMatchesUncached

Computes the strings matching a regex without consulting the cache.

findMatchesUnsafe

Returns the cached matches for a regex as a view over internal storage.

getRegexList

Returns the views of all regexes currently in the cache.

getStringList

Returns pointers to all strings currently in the cache.

hasItemsToPurge

Returns whether any regex has not been accessed since the expiry time.

hasRegex

Returns whether the given regex is in the cache.

hasString

Returns whether the given string is in the cache.

inspect

Returns a printable view of the cache's internal state.

isReadyToFindMatches

Returns whether cached matches for the regex are ready to query.

prepareToFindMatches

Coalesces queued strings for a regex so its matches can be queried.

purge

Removes regexes not accessed since the expiry time.

Created with MrDocs