Capturing vs. Non-capturing Regex Groups

I posted the following on Ben Nadel's excellent blog, in response to a question about why I use non-capturing groups in my regular expressions (e.g., (?:non-captured))...

I near-religiously use non-capturing groups whenever I do not need to reference a group's contents. There are only three reasons to use capturing groups:

• You're using parts of a match to construct a replacement string, or otherwise referencing parts of the match in code outside the regex.
• You need to reuse parts of the match within the regex itself. E.g., (["'])(?:\\\1|.)*?\1 would match values enclosed in either double or single quotes, while requiring that the same quote type start and end the match, and allowing inner, escaped quotes of the same type as the enclosure.
• You need to test if an optional group was part of the match so far, as the condition to evaluate within a conditional. E.g., (a)?b(?(1)c|d) only matches the values "bd" and "abc".

There are two primary reasons to use non-capturing groups if a grouping doesn't meet one of the above conditions:

• Capturing groups negatively impact performace, since creating backreferences requires that their contents be stored in memory. The performance hit may be tiny, especially when working with small strings, but it's there.
• When you need to use several groupings in a single regex, only some of which you plan to reference later, it's very convenient to have the backreferences you want to use numbered sequentially. E.g., the logic in my parseUri() UDF could not be nearly as simple if I had not made appropriate use of capturing and non-capturing groups within the same regex.

On a related note, the values of backreferences created using capturing groups with repetition operators on the end of them may not be obvious until you're familar with how it works. If you ran the regex (.)* over the string "test", although backreference 0 (i.e., the whole match) would be "test", backreference 1 would be "t", and there would be no 2nd, 3rd, or 4th backreferences created for the strings "e," "s," and "t." If you wanted the entire match of a repeated grouping to be captured into a backreference, you could use, e.g., ((?:.)*). Also note that the way both of those patterns would be evaluated is fundamentally different from how regex engines would treat (.*).

More URI-related UDFs

To follow up my parseUri() function, here are several more UDFs I've written recently to help with URI management:

• getPageUri()
  Returns a struct containing the relative and absolute URIs of the current page. The difference between getPageUri().relative and CGI.SCRIPT_NAME is that the former will include the query string, if present.
• matchUri(testUri, [masterUri])
  Returns a Boolean indicating whether or not two URIs are the same, disregarding the following differences:
  • Fragments (page anchors), e.g., "#top".
  • Inclusion of "index.cfm" in paths, e.g., "/dir/" vs. "/dir/index.cfm" (supports trailing query strings).
  If masterUri is not provided, the current page is used for comparison (supports both relative and absolute URIs).
• replaceUriQueryKey(uri, key, substring)
  Replaces a URI query key and its value with a supplied key=value pair. Works with relative and absolute URIs, as well as standalone query strings (with or without a leading "?"). This is also used to support the following two UDFs:
• addUriQueryKey(uri, key, value)
  Removes any existing instances of the supplied key, then appends it together with the provided value to the provided URI.
• removeUriQueryKey(uri, key)
  Removes one or more query keys (comma delimited) and their values from the provided URI.

Now that I have these at my disposal, I frequently find myself using them in combination with each other, e.g.,
<a href="<cfoutput>#addUriQueryKey(
    getPageUri().relative,
    "key",
    "value"
)#</cfoutput>">Link</a>.

Let me know if you find any of these useful…

<!--- Returns the relative and absolute URIs of the current page --->
<cffunction name="getPageUri" returntype="struct" output="FALSE">
    <cfset var pageProtocol = "http" />
    <cfset var pageQuery = "" />
    <cfset var uri = structNew() />
    
    <!--- Get the protocol of the current page --->
    <cfif CGI.HTTPS IS "ON">
        <cfset pageProtocol = "https" />
    </cfif>
    
    <!--- Get the query of the current page, including the leading question if the query is not empty --->
    <cfset pageQuery = reReplace("?" & CGI.QUERY_STRING, "\?$", "") />
    
    <!--- Construct the relative URI of the current page (excludes the protocol and domain) --->
    <cfset uri.relative = CGI.SCRIPT_NAME & pageQuery />
    <!--- Construct the absolute URI of the current page --->
    <cfset uri.absolute = pageProtocol & "://" & CGI.SERVER_NAME & uri.relative />
    
    <cfreturn uri />
</cffunction>

<!--- Returns a Boolean indicating whether or not two URIs are the same, disregarding the following differences:
• Fragments (page anchors), e.g., "#top".
• Inclusion of "index.cfm" in paths, e.g., "/dir/" vs. "/dir/index.cfm" (supports trailing query strings).
If masterUri is not provided, the current page is used for comparison (supports both relative and absolute URIs) --->
<cffunction name="matchUri" returntype="boolean" output="FALSE">
    <cfargument name="testUri" type="string" required="TRUE" />
    <cfargument name="masterUri" type="string" required="FALSE" default="" />
    
    <!--- If a masterUri was not provided --->
    <cfif len(masterUri) EQ 0>
        <!--- If testUri is an absolute URI --->
        <cfif reFindNoCase("^https?://", testUri) EQ 1>
            <cfset masterUri = getPageUri().absolute />
        <cfelse>
            <cfset masterUri = getPageUri().relative />
        </cfif>
    </cfif>
    
    <cfreturn reReplaceNoCase(reReplace(testUri, "##.*", ""), "/index\.cfm(?=\?|$)", "/", "ONE") IS reReplaceNoCase(reReplace(masterUri, "##.*", ""), "/index\.cfm(?=\?|$)", "/", "ONE") />
</cffunction>

<!--- Replace a URI query key and its value with a supplied key=value pair.
Works with relative and absolute URIs, as well as standalone query strings (with or without a leading "?") --->
<cffunction name="replaceUriQueryKey" returntype="string" output="FALSE">
    <cfargument name="uri" type="string" required="TRUE" />
    <cfargument name="key" type="string" required="TRUE" />
    <cfargument name="substring" type="string" required="TRUE" />
    <cfset var preQueryComponents = "" />
    <cfset var currentKey = "" />
    
    <!--- Remove any existing fragment (page anchor) from uri, since it will mess with our processing, and is unlikely to be relevant and/or correct in the new URI --->
    <cfset uri = reReplace(uri, "##.*", "", "ONE") />
    <!--- Store any pre-query URI components. For this to work, the string must start with "protocol:", "//authority", or "/" (path). Otherwise, we will assume the uri is comprised entirely of a query component --->
    <cfset preQueryComponents = reReplace(uri, "^((?:(?:[^:/?.]+:)?//[^/?]+)?(?:/[^?]*)?)?.*", "\1", "ONE") />
    <!--- Remove any pre-query components and the leading question mark from uri --->
    <cfset uri = reReplace(uri, "^(?:(?:[^:/?.]+:)?//[^/?]+)?(?:/[^?]*)?\??(.*)", "\1", "ONE") />
    <!--- Remove any superfluous ampersands in the query (this cleans up the query but is not required, and in any case this function doesn't generate superfluous ampersands) --->
    <cfset uri = reReplace(uri, "&(?=&)|&$", "", "ALL") />
    
    <!--- For each key specified, remove the corresponding key=value pair from uri. Note that key names which contain regex special characters (.,*,+,?,^,$,{,},(,),|,[,],\) which are not percent-encoded may behave unpredictably --->
    <cfloop index="currentKey" list="#key#" delimiters=",">
        <cfif len(currentKey) GT 0>
            <cfset uri = reReplaceNoCase(uri, ("(?:^|&)" & currentKey & "(?:=[^&]*)?"), "", "ALL") />
        </cfif>
    </cfloop>
    
    <!--- If we still have a value in uri after the above processing (beyond what we're about to add) --->
    <cfif len(uri) GT 0>
        <!--- Ensure the query is returned with only the necessary separator characters (? and &) --->
        <cfreturn (preQueryComponents & "?" & reReplace(uri, "^&", "") & reReplace("&" & substring, "&$", "")) />
    <cfelse>
        <!--- Append substring, including a leading question mark if substring is not empty --->
        <cfreturn (preQueryComponents & reReplace("?" & substring, "\?$", "")) />
    </cfif>
</cffunction>

<cffunction name="addUriQueryKey" returntype="string" output="FALSE">
    <cfargument name="uri" type="string" required="TRUE" />
    <cfargument name="key" type="string" required="TRUE" />
    <cfargument name="value" type="string" required="TRUE" />
    
    <!--- Until proper support is included for adding multiple keys with one call, use only the first key --->
    <cfset key = listFirst(key, ",") />
    
    <!--- Remove any existing instances of the key from uri, then add the new key=value pair.
    Do not include the trailing equals sign (=) if we're assigning an empty value to the added key --->
    <cfreturn replaceUriQueryKey(removeUriQueryKey(uri, key), "", (key & reReplace("=" & value, "=$", ""))) />
</cffunction>

<cffunction name="removeUriQueryKey" returntype="string" output="FALSE">
    <cfargument name="uri" type="string" required="TRUE" />
    <!--- Use a comma-delimited list to remove multiple keys with one call --->
    <cfargument name="key" type="string" required="TRUE" />
    
    <cfreturn replaceUriQueryKey(uri, key, "") />
</cffunction>

In other news, this cracked me up.

parseUri(): Split URLs in ColdFusion

Update: Please view the updated version of this post on my new blog:

parseUri: Split URLs in ColdFusion.

Here's a UDF I wrote recently which allows me to show off my regex skillz. parseUri() splits any well-formed URI into its components (all are optional).

The core code is already very brief, but I could replace the entire contents of the <cfloop> with one line of code if I didn't have to account for bugs in the reFind() function (tested in CF7). Note that all components are split with a single regex (using backreferences). My favorite part of this UDF is its robust support for splitting the directory path and filename (it supports directories with periods, and without a trailing backslash), which I haven't seen matched in other URI parsers.

Since the function returns a struct, you can do, e.g., parseUri(someUri).anchor, etc. Check it out:

<!--- By Steven Levithan. Splits any well-formed URI into its components --->
<cffunction name="parseUri" returntype="struct" output="FALSE">
    <cfargument name="sourceUri" type="string" required="TRUE" />
    <!--- Get arrays named len and pos, containing the lengths and positions of each URI component (all are optional) --->
    <cfset var uriPattern = reFind("^(?:([^:/?##.]+):)?(?://)?(([^:/?##]*)(?::(\d*))?)?((/(?:[^?##](?![^?##/]*\.[^?##/.]+(?:[\?##]|$)))*/?)?([^?##/]*))?(?:\?([^##]*))?(?:##(.*))?", sourceUri, 1, TRUE) />
    <!--- Create an array containing the names of each key we will add to the uri struct --->
    <cfset var uriComponentNames = listToArray("source,protocol,authority,domain,port,path,directoryPath,fileName,query,anchor") />
    <cfset var uri = structNew() />
    <cfset var i = 1 />
    
    <!--- Add the following keys to the uri struct:
    • source (when using returnSubExpressions, reFind() returns backreference 0 [i.e., the entire match] as array element 1, so we might as well use it)
    • protocol (scheme)
    • authority (includes both the domain and port)
        • domain (part of the authority component; can be an IP address)
        • port (part of the authority component)
    • path (includes both the directory path and filename)
        • directoryPath (part of the path component; supports directories with periods, and without a trailing backslash)
        • fileName (part of the path component)
    • query (does not include the leading question mark)
    • anchor (fragment) --->
    <cfloop index="i" from="1" to="10"><!--- Could also use to="#arrayLen(uriComponentNames)#" --->
        <!--- If the component was found in the source URI...
        • The arrayLen() check is needed to prevent a CF error when sourceUri is empty, because due to an apparent bug, reFind() does not populate backreferences for zero-length capturing groups when run against an empty string (though it does still populate backreference 0)
        • The pos[i] value check is needed to prevent a CF error when mid() is passed a start value of 0, because of the way reFind() considers an optional capturing group that does not match anything to have a pos of 0 --->
        <cfif (arrayLen(uriPattern.pos) GT 1) AND (uriPattern.pos[i] GT 0)>
            <!--- Add the component to its corresponding key in the uri struct --->
            <cfset uri[uriComponentNames[i]] = mid(sourceUri, uriPattern.pos[i], uriPattern.len[i]) />
        <!--- Otherwise, set the key value to an empty string --->
        <cfelse>
            <cfset uri[uriComponentNames[i]] = "" />
        </cfif>
    </cfloop>
    
    <!--- Always end directoryPath with a trailing backslash if the path component was present in the source URI (Note that a trailing backslash is NOT automatically inserted within or appended to the "path" key) --->
    <cfif len(uri.directoryPath) GT 0>
        <cfset uri.directoryPath = reReplace(uri.directoryPath, "/?$", "/") />
    </cfif>
    
    <cfreturn uri />
</cffunction>

Edit: I've written a JavaScript implementation of the above UDF. See parseUri(): Split URLs in JavaScript.

reMatch(): Improving ColdFusion's regex support

Update: Please see this post on my new blog, which includes a demo of the REMatch function:

REMatch (ColdFusion).

Following are some UDFs I wrote recently to make using regexes in ColdFusion a bit easier. The biggest deal here is my reMatch() function.

reMatch(), in its most basic usage, is similar to JavaScript's String.match() method. Compare getting the first number in a string using reMatch() vs. built-in ColdFusion functions:

• reMatch():
  <cfset num = reMatch("\d+", string) />
• reReplace():
  <cfset num = reReplace(string, "\D*(\d+).*", "\1") />
• reFind():
  <cfset matchInfo = reFind("\d+", string, 1, TRUE) />
<cfset num = mid(string, matchInfo.pos[1], matchInfo.len[1]) />

All of the above would return the same result, unless a number wasn't found in the string, in which case the reFind()-based method would throw an error since the mid() function would be passed a start value of 0. I think it's pretty clear from the above which approach is easiest to use for a situation like this.

Still, that's just the beginning of what reMatch() can do. Change the scope argument from the default of "ONE" to "ALL" (to follow the convention used by reReplace(), etc.), and the function will return an array of all matches. Finally, set the returnLenPos argument to TRUE and the function will return either a struct or array of structs (based on the value of scope) containing the len, pos, AND value of each match. This is very different from how the returnSubExpressions argument of reFind() works. When using returnSubExpressions, you get back a struct containing arrays of the len and pos (but not value) of each backreference from the first match.

Here's the code, with four additional UDFs (reMatchNoCase(), match(), matchNoCase(), and escapeReChars()) added for good measure:

<!--- UDFs by Steven Levithan --->

<cffunction name="reMatch" output="FALSE">
    <cfargument name="regEx" type="string" required="TRUE" />
    <cfargument name="string" type="string" required="TRUE" />
    <cfargument name="start" type="numeric" required="FALSE" default="1" />
    <cfargument name="scope" type="string" required="FALSE" default="ONE" />
    <cfargument name="returnLenPos" type="boolean" required="FALSE" default="FALSE" />
    <cfargument name="caseSensitive" type="boolean" required="FALSE" default="TRUE" />
    <cfset var thisMatch = "" />
    <cfset var matchInfo = structNew() />
    <cfset var matches = arrayNew(1) />
    <!--- Set the time before entering the loop --->
    <cfset var timeout = now() />
    
    <!--- Build the matches array. Continue looping until additional instances of regEx are not found. If scope is "ONE", the loop will end after the first iteration --->
    <cfloop condition="TRUE">
        <!--- By using returnSubExpressions (the fourth reFind argument), the position and length of the first match is captured in arrays named len and pos --->
        <cfif caseSensitive>
            <cfset thisMatch = reFind(regEx, string, start, TRUE) />
        <cfelse>
            <cfset thisMatch = reFindNoCase(regEx, string, start, TRUE) />
        </cfif>
        
        <!--- If a match was not found, end the loop --->
        <cfif thisMatch.pos[1] EQ 0>
            <cfbreak />
        <!--- If a match was found, and extended info was requested, append a struct containing the value, length, and position of the match to the matches array --->
        <cfelseif returnLenPos>
            <cfset matchInfo.value = mid(string, thisMatch.pos[1], thisMatch.len[1]) />
            <cfset matchInfo.len = thisMatch.len[1] />
            <cfset matchInfo.pos = thisMatch.pos[1] />
            <cfset arrayAppend(matches, matchInfo) />
        <!--- Otherwise, just append the match value to the matches array --->
        <cfelse>
            <cfset arrayAppend(matches, mid(string, thisMatch.pos[1], thisMatch.len[1])) />
        </cfif>
        
        <!--- If only the first match was requested, end the loop --->
        <cfif scope IS "ONE">
            <cfbreak />
        <!--- If the match length was greater than zero --->
        <cfelseif thisMatch.pos[1] + thisMatch.len[1] GT start>
            <!--- Set the start position for the next iteration of the loop to the end position of the match --->
            <cfset start = thisMatch.pos[1] + thisMatch.len[1] />
        <!--- If the match was zero length --->
        <cfelse>
            <!--- Advance the start position for the next iteration of the loop by one, to avoid infinite iteration --->
            <cfset start = start + 1 />
        </cfif>
        
        <!--- If the loop has run for 20 seconds, throw an error, to mitigate against overlong processing. However, note that even one pass using a poorly-written regex which triggers catastrophic backtracking could take longer than 20 seconds --->
        <cfif dateDiff("s", timeout, now()) GTE 20>
            <cfthrow message="Processing too long. Optimize regular expression for better performance" />
        </cfif>
    </cfloop>
    
    <cfif scope IS "ONE">
        <cfparam name="matches[1]" default="" />
        <cfreturn matches[1] />
    <cfelse>
        <cfreturn matches />
    </cfif>
</cffunction>

<cffunction name="reMatchNoCase" output="FALSE">
    <cfargument name="regEx" type="string" required="TRUE" />
    <cfargument name="string" type="string" required="TRUE" />
    <cfargument name="start" type="numeric" required="FALSE" default="1" />
    <cfargument name="scope" type="string" required="FALSE" default="ONE" />
    <cfargument name="returnLenPos" type="boolean" required="FALSE" default="FALSE" />
    <cfreturn reMatch(regEx, string, start, scope, returnLenPos, FALSE) />
</cffunction>

<cffunction name="match" output="FALSE">
    <cfargument name="substring" type="string" required="TRUE" />
    <cfargument name="string" type="string" required="TRUE" />
    <cfargument name="start" type="numeric" required="FALSE" default="1" />
    <cfargument name="scope" type="string" required="FALSE" default="ONE" />
    <cfargument name="returnLenPos" type="boolean" required="FALSE" default="FALSE" />
    <cfreturn reMatch(escapeReChars(substring), string, start, scope, returnLenPos, TRUE) />
</cffunction>

<cffunction name="matchNoCase" output="FALSE">
    <cfargument name="substring" type="string" required="TRUE" />
    <cfargument name="string" type="string" required="TRUE" />
    <cfargument name="start" type="numeric" required="FALSE" default="1" />
    <cfargument name="scope" type="string" required="FALSE" default="ONE" />
    <cfargument name="returnLenPos" type="boolean" required="FALSE" default="FALSE" />
    <cfreturn reMatch(escapeReChars(substring), string, start, scope, returnLenPos, FALSE) />
</cffunction>

<!--- Escape special regular expression characters (.,*,+,?,^,$,{,},(,),|,[,],\) within a string by preceding them with a forward slash (\). This allows safely using literal strings within regular expressions --->
<cffunction name="escapeReChars" returntype="string" output="FALSE">
    <cfargument name="string" type="string" required="TRUE" />
    <cfreturn reReplace(string, "[.*+?^${}()|[\]\\]", "\\\0", "ALL") />
</cffunction>

Now that I've got a deeply featured match function, all I need Adobe to add to ColdFusion in the way to regex support is lookbehinds, atomic groups, possessive quantifiers, conditionals, balancing groups, etc., etc. :-)

Hot Naked Sushi Action

Someone was telling me yesterday about how ancient and wonderful an art form nyotaimori (aka naked sushi) is. This may or may not exactly (wikipedia.org) be true, but it did get me looking online for more information. The practice has actually been outlawed in China (bbc.co.uk), but then the Chinese don’t allow snoring in the military or cooking children’s arms (mainichi-msn.co.jp) either. Communists.

Fortunately for the sophisticated misogynist, there are a few establishments Stateside that offer nyotaimori, most famously Gary Arabia’s (globalcuisinecatering.com) Global Cuisine (aolcityguide.com) in LA.

I spent a few minutes searching for local spots, and according to ClubZone.com, Café Japone (clubzone.com) in Dupont Circle does naked sushi Saturday nights. Hmm… why haven’t I heard about this before? I’m skeptical. If it is true, however, I may have to pay them a visit, being a fan of both sushi and naked women.

Thinking…I'm sure they have rules about not talking to the models, but really, where would a conversation with someone you were eating off go?

Me: So… Sushi… you a big sushi person?
Table: Well, not really.
Me: Ah. Well. Being a table, then. How's that working out for you?
Table: Not too bad. Pays the rent. I, uh, go home smelling like fish though.
Me: Oh.

…It could go on like that for a very long, akward time.

For those who know I grew up in Japan, I’ll note that I haven’t tried eating off a naked woman yet, though I have on many occasions ea…… [Post interrupted by Poor Taste Alert®]

Dymanic Properties

A cool, little-known, IE5+ only CSS bastardization

I'm just starting to learn about Dynamic Properties (aka CSS Expressions). Thought this might be interesting to my hordes of readers (not) in the WebDev community…

• About Dynamic Properties (msdn.microsoft.com)
• Be More Dynamic (msdn.microsoft.com)
• Introduction to Dynamic Properties (IE) (javascriptkit.com)

You Got Mightily Owned, My Friend

Discovered this via my buddy Dave… Check out Aninote.com. It allows you to dynamically generate Flash presentations … you can insert any recipient name in the animations simply by sticking it before the domain name for the animation you wish to use.

See, for example:

• http://steven.segal.justgotowned.com
• http://michael.jackson.youaremighty.com
• http://chocolate.balls.youaremyfriend.com

Mighty awesome.

World RPS Society

Check it: Worldwide Governing Body of the Sport of Rock Paper Scissors (worldrps.com).

Looks like it’s a big thing. Weird. Still, this has to be one of the most unintentionally funny sites ever. Check out, for example, their 2002 dedication to the Official Year of the Rock (in particular, check out the last two photo captions within the article).

At first glance, the rules of Rock Paper Scissors seem simple. As you look deeper, however, they’re still pretty simple. Let’s not kid ourselves.

• Rock smashes scissors (rock wins)
• Scissors cut paper (scissors win)
• Paper covers rock (paper wins)
• Flounder slaps penguin (flounder wins … for expert use only)

…Or so I thought. Here is the 3-page How to Play – Quick Start, and the 7-page must read for all aspiring RPS gurus: Advanced RPS tactics.

Check out this excerpt from the World RPS Society, showing just how high-demand of a sport Rock Paper Scissors can really be:

… In other events, Chad Leatherstep (Co-Chair Disciplinary Committee) in his address delivered a landmark speech pledging a crackdown on performance enhancing drugs in professional level play. “It is the worst kept secret that the dressing rooms at many tournaments have become literal ‘hotboxes’ of abuse. We will be targeting specific suspicious players for random drug testing.”

Imagine that. Your friendly, local Rock Paper Scissors tournament, unbeknowest to you, might have become a literal “hotbox” of performance-enhancing drug abuse!

It makes sense in a way, I guess … these people have to be on something potent to be at an RPS tournament in the first place.

Related stuff:

• The cult of roshambo (emf.net) — devoted to the religion of Rock Paper Scissors
• Play Rock Paper Scissors via email (brunching.com)

And here’s some stirring RPS haiku gleaned from the RPS Society’s Bullboard:

Always throw paper.
How can you lose with paper?
Forget scissors, man.

You delayed your prime
Won’t synchronize your rhythm
That’s just dirty play

Paper is the throw
For the narcissistic fool
The masturbator

Few are perfect forms
The rock however is one
Likewise breasts are too