In this short paper we provide a systematic proposal to add regular expression operators to the OCL standard library for the String type, and we discuss other String operators which could be included in the library. The String type is a central data type in most forms of software, however the String type facilities in the OCL 2.4 standard are quite restricted (only 17 specific operators are defined) [ 9]. One category of omitted operations are those concerning substitution within strings and string matching against regular expressions. Furthermore, since strings can be regarded as sequences of characters (strings of size 1), it would seem natural to adopt sequence operators such as first , last, front, tail and insertAt for strings. We consider the addition of regular expression operators in Section 2, and the addition of other operators in Section 3. Implementation of the operators is discussed in Section 4, and performance evaluation in Section 6.
Regular expressions are an important facility in many software systems, especially for validation
of textual data, data filtering and transformation. We found that these facilities were of key
importance in the development of software engineering tools for MDE, in particular our
codegenerator DSL, ℒ [
Most mainstream programming languages provide regular expression facilities, but there are
considerable diferences in the level of support and operations provided (eg., Java str.matches(patt)
requires that the entire str is a single match for patt, whilst Python patt.match(str) only requires
matching of patt to a substring of str, and C# patt.Matches(str) returns all matches of patt within
str). Specification languages such as EOL and ATL’s OCL version also provide some regular
expression facilities [
We propose a cohesive set of String operators to enable the use of regular expressions in OCLbased specifications. These operators clearly distinguish between diferent forms of matching and replacement: • isMatch(patt : String) : Boolean – returns true only if the entire text of self is a single match for the regular expression patt. • hasMatch(patt : String) : Boolean – returns true if some non-empty substring of self satisfies the regular expression patt. • allMatches(patt : String) : Sequence(String) – returns the sequence of non-overlapping and non-empty substrings of self which match patt, in the order of their occurrence in self . • replaceAllMatches(patt : String, rep : String) : String – A copy of self with each substring in allMatches(patt) replaced by rep. • split(patt : String) : Sequence(String) – the sequence of substrings of self formed by removing the substrings in allMatches(patt).
For additional clarity, split could alternatively be named splitOnMatches. Useful auxiliary
operations are
• firstMatch (patt : String) : String
• replaceFirstMatch(patt : String, rep : String) : String
It is also useful to support replacement substituteFirst and substituteAll of substrings based on
literal string equality, as in [
Because of the general utility of such operations, we consider that they should be included
into the OCL standard library, rather than in a specialised library.
2.1. Regular expression semantics
We assume a core regular expression language, such as POSIX ERE, consisting of the standard
metacharacters ., * , +, ?, [, ], |, literal characters, character ranges c1− c2, and escaped special
characters ∖∖s. This language is supported by all mainstream programming languages. It has a
semantics given in terms of sets of sequences of characters [
We assume that some matching relation str |= r exists between literal strings and regular expressions, this means that str.characters() ∈ [[r]]. For example, “Augustus” |= “[A− Z ][a− z]+” and not(“+ + * ” |= “[A− Z ][a− z]+”). str |= patt means that the entire string str satisfies patt. Thus but not(“C + +” |= “[A− Z ]+”).
isMatch can then be defined directly in terms of |=. str.isMatch(patt) is invalid if str or patt
is invalid, otherwise it is null if either str or patt is null. For valid arguments we define:
isMatch(patt : String) : Boolean
pre: true
post:
if size() = 0 then result = false
else if patt.size() = 0 then result = false
else if str |= patt then result = true
else result = false
endif endif endif
This definition provides a formal definition of isMatch, suitable for inclusion in Section A.2.1.3
of [
The other regular expression operators can then be defined in terms of isMatch. hasMatch is: hasMatch(patt : String) : Boolean pre: true post: result =
Sequence{1..size()}->exists( x, y |
x <= y and str.substring(x,y).isMatch(patt) ) We assume that str.substring(i, j) is “” if j < i1.
ifrstMatch (patt : String) is defined by: firstMatch(patt : String) : String pre: true post: if not(hasMatch(patt)) then result = null else if
Sequence{1..size()}->exists( y | substring(1,y).isMatch(patt) ) then result = Sequence{1..size()}->collect( y | substring(1,y) ) ->select( str | str.isMatch(patt) )->max() else
result = substring(2,size()).firstMatch(patt) endif endif The use of max here means that we take the largest match of patt (the longest matching substring of self ) starting from a given index. This is the most common matching strategy for regular expressions (‘greedy’ matching), but alternative strategies can be specified analogously.
str.allMatches(patt) is also defined recursively:
allMatches(patt : String) : Sequence(String)
pre: true
post:
if size() = 0 then result = Sequence{}
1This case is not defined in [
self.indexOf(m)+m.size(),self.size()).allMatches(patt)) endif endif Matches cannot be the empty string, by definition of isMatch, therefore this recursion is welldefined. An example is “abracadabra”.allMatches(“ab”) = Sequence{“ab”, “ab”}.
str.replaceAllMatches(patt, rep) is defined by a similar recursion. It is invalid if any of str, patt or rep are invalid. If patt or rep or str are null, the result is str. replaceAllMatches(patt : String, rep : String) : String pre: true post: if patt.size() = 0 or self.size() = 0 then result = self else if not(str.hasMatch(patt)) then result = self else let m : String = self.firstMatch(patt) in result = substring(1,indexOf(m)-1) + rep + substring(indexOf(m)+m.size(),size()).
replaceAllMatches(patt,rep) endif endif An example is “abracadabra”.replaceAllMatches(“ab”, “”) = “racadra”.
replaceFirstMatch is: replaceFirstMatch(patt : String, rep : String) : String pre: true post: if patt.size() = 0 or self.size() = 0 then result = self else if not(str.hasMatch(patt)) then result = self else let m : String = self.firstMatch(patt) in result = substring(1,indexOf(m)-1) + rep +
substring(indexOf(m)+m.size(),size()) endif endif str.split(patt) is defined similarly. It is invalid if either str or patt are invalid, and Sequence{str} if either are null. split(patt : String) : Sequence(String) pre: true post: if self.size() = 0 or patt.size() = 0 then result = Sequence{self} else if not(hasMatch(patt)) then result = Sequence{self} else let m : String = self.firstMatch(patt) in let ind : Integer = indexOf(m) in if ind > 1 then result = Sequence{substring(1,ind-1)}->union(
substring(ind+m.size(),size()).split(patt)) else
result = substring(ind+m.size(),size()).split(patt) endif endif endif An example is “abracadabra”.split(“ab”) = Sequence{“racad”, “ra”}.
An alternative to using isMatch as the core regex operator would be to use firstMatch : both isMatch and hasMatch can be derived from firstMatch .
Since strings can also be regarded as sequences (of characters), it is often convenient to apply
some sequence operators to strings. The size() and at(i) operators are already common to both
types in [
We suggest that first (), last(), front() and tail() are natural convenience operators to adopt
for String. These can be directly defined in terms of substring, so do not require extension of
Annex A of [
s.substring(1, i − 1) + str + s.substring(i, s.size())
Other widely-used string operators are trim() to remove leading and trailing whitespace, lastIndexOf (str), hasPrefix (str)/startsWith(str), hasSufix (str)/endsWith(str) and after(str) and before(str). Thus we also recommend these for inclusion in the OCL String library.
However there are many specialised string operators which are more appropriately defined
in external extension libraries. For example, computation of the edit distance of two strings [
The operators isMatch, hasMatch, firstMatch , allMatches, replaceFirstMatch, replaceAllMatches
and split have been incorporated into the AgileUML toolset [
Code-generation for specifications using the regular expression operators is supported by
extended OCL libraries for Java 4, 6, 7 and 8, C#, C++, C, Python and Swift, available from
[
In some cases, such as Java, the programming languages directly provide the required operators. In other cases (eg., C, Swift), the operators need to be implemented in terms of more basic matching facilities. We have primarily used iterative algorithms for eficiency.
We provide implementations of first (), last(), front(), tail(), reverse(), insertAt(i, str), trim(), lastIndexOf (str), after(str) and before(str) String operators in the AgileUML OCL implementations for Java, C#, C++, C, Python and Swift.
Extension operators such as edit distance are instead defined as static operations of a StringLib component. In specifications these are invoked as StringLib.editDist(s1, s2). Implementations of StringLib need to be provided in each target programming language. More advanced regular expression facilities, such as first-class patterns and match groups, could also be provided in an extension component.
The OCL 2.4 library [
The Eclipse OCL [
EOL [
ATL OCL [
In order to evaluate the performance of the regular expression implementations in diferent
languages we defined examples for (i) allMatches and (ii) replaceAllMatches with the regular
expression [a− zA− Z ]+ applied to a string of length 1000 containing 100 words in case (i) and
expression ∖∖([⌢∖∖(∖∖)] * ∖∖ ) applied to a string of length 500 in (ii). The latter expression
matches against ()-bracketed texts which contain no ( or ) brackets within them. The examples
are in oclregexExamples.zip at [
N
This means that for Java each match takes about 10− 4ms and each replacement about 4 * 10− 4ms in the largest case. Performance figures are similar for other languages.
In this paper we have provided a rationale for adding a core set of regular expression facilities to OCL, we also described their semantics and how the operators can be translated into diferent programming language implementations. We also discussed the possible inclusion of other widely-used string operators.