lib/standard/re.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2014 Alexis Laferrière <alexis.laf@xymus.net>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # Regular expression support for all services based on `Pattern`
  18 #
  19 # Implemented using libc regular expressions.
  20 #
  21 # The main entities are `Text::to_re` and `Regex`.
  22 module re
  23
  24 import string_search
  25 import gc
  26 import error
  27
  28 in "C Header" `{
  29         #include <sys/types.h>
  30         #include <regex.h>
  31 `}
  32
  33 # Main extern class to wrap libc regular expression support
  34 #
  35 # It is recommanded to use the higher level API offered by the class `Regex`,
  36 # but it can still be used for advanced purpose or in optimized code.
  37 #
  38 # To use this class and other `private` entities of this module, use `intrude import standard::re`
  39 private extern class NativeRegex `{ regex_t* `}
  40         # Allocate a new `NativeRegex`, it must then be compiled using `regcomp` before calling `regexec`
  41         new malloc `{ return malloc(sizeof(regex_t)); `}
  42
  43         # Compile the regular expression `regex` into a form that is suitable for subsequent `regexec` searches
  44         fun regcomp(regex: NativeString, cflags: Int): Int `{
  45                 return regcomp(recv, regex, cflags);
  46         `}
  47
  48         # Match `string` against the precompiled pattern buffer of `self`, locating matches
  49         #
  50         # `nmatch` and `pmatch` are used to provide information regarding the location of any matches.
  51         # `eflags` may be the bitwise-or of one or both of `flag_notbol` and `flag_noteol`.
  52         fun regexec(string: NativeString, nmatch: Int, pmatch: NativeMatchArray, eflags: Int): Int `{
  53                 return regexec(recv, string, nmatch, pmatch, eflags);
  54         `}
  55
  56         # Match `string` against the precompiled pattern buffer of `self`, do not locate matches
  57         #
  58         # `eflags` may be the bitwise-or of one or both of `flag_notbol` and `flag_noteol`.
  59         fun regexec_match_only(string: NativeString, eflags: Int): Int `{
  60                 return regexec(recv, string, 0, NULL, eflags);
  61         `}
  62
  63         # Free the memory allocated to the pattern buffer by the compiling process
  64         #
  65         # Does not free the memory holding `self`, use `free` for this purpose.
  66         fun regfree `{ regfree(recv); `}
  67
  68         # Turn the error codes that can be returned by both `regcomp` and `regexec` into error message strings
  69         fun regerror(errcode: Int): NativeString `{
  70                 size_t len = regerror(errcode, recv, NULL, 0);
  71                 char *message = malloc(len);
  72                 regerror(errcode, recv, message, len);
  73
  74                 return message;
  75         `}
  76
  77         # This field holds the number of parenthetical subexpressions in the regular expression that was compiled.
  78         fun re_nsub: Int `{ return recv->re_nsub; `}
  79 end
  80
  81 # Flags for `NativeRegex::regcomp`
  82
  83 private fun flag_extended: Int `{ return REG_EXTENDED; `}
  84 private fun flag_icase: Int `{ return REG_ICASE; `}
  85 private fun flag_nosub: Int `{ return REG_NOSUB; `}
  86 private fun flag_newline: Int `{ return REG_NEWLINE; `}
  87
  88 # Flags for `NativeRegex::regexec`
  89
  90 private fun flag_notbol: Int `{ return REG_NOTBOL; `}
  91 private fun flag_noteol: Int `{ return REG_NOTEOL; `}
  92
  93 # Errors of `NativeRegex::regexec`
  94
  95 private fun error_nomatch: Int `{ return REG_NOMATCH; `}
  96 private fun error_espace: Int `{ return REG_ESPACE; `}
  97
  98 redef universal Int
  99         private fun is_nomatch: Bool `{ return recv == REG_NOMATCH; `}
 100 end
 101
 102 # An array of `regmatch_t` or a pointer to one
 103 private extern class NativeMatchArray `{ regmatch_t* `}
 104         # Allocate a new array of `length` `regmatch_t`
 105         new malloc(length: Int) `{ return malloc(length * sizeof(regmatch_t)); `}
 106
 107         # The offset in string of the beginning of a substring
 108         fun rm_so: Int `{ return recv->rm_so; `}
 109
 110         # The offset in string of the end of the substring
 111         fun rm_eo: Int `{ return recv->rm_eo; `}
 112
 113         # Get a pointer to the element at `index`, can also be used as a subarray
 114         fun [](index: Int): NativeMatchArray `{ return recv + index; `}
 115 end
 116
 117 redef extern class NativeString
 118         private fun substring_from(index: Int): NativeString `{ return recv + index; `}
 119 end
 120
 121 redef class Text
 122         # Get a `Regex` instance from `self`
 123         fun to_re: Regex do return new Regex(self.to_s)
 124 end
 125
 126 # A regular expression pattern
 127 #
 128 # Used as a `Pattern` on intances of `Text` to call `has`, `search_all`, `replace`, etc.
 129 #
 130 # Example:
 131 #
 132 #     var re = "ab+a".to_re
 133 #     assert "aabbbbaaaaba".search_all(re).join(", ") == "abbbba, aba"
 134 #     assert "aabbbbaaaaba".has(re)
 135 #     assert "aabbbbaaaaba".replace(re, "+") == "a+aa+"
 136 #     assert "aabbbbaaaaba".split(re) == ["a", "aa", ""]
 137 class Regex
 138         super Finalizable
 139         super Pattern
 140
 141         # The `String` source of this regular expression
 142         var string: String is writable
 143
 144         # Treat the pattern as a POSIX extended regular expression (the default)
 145         #
 146         # If `false`, it is treated as a POSIX basic regular expression (BRE).
 147         #
 148         # The extended syntax supports `?`, `+` and `|`. Also, `\` causes the following
 149         # character to be used as literal.
 150         var extended = true is writable
 151
 152         # Ignore case when matching letters
 153         var ignore_case = false is writable
 154
 155         # Optimize `self` for `is_in` and `String::has`, but do not support searches
 156         #
 157         # If `true`, `self` cannont be used with `String::search_all`, `String::replace`
 158         # or `String::split`.
 159         var optimize_is_in = false is writable
 160
 161         # Treat a newline in string as dividing string into multiple lines
 162         #
 163         # So that `$` can match before the newline and `^` can match after.
 164         # Also, don’t permit `.` to match a newline, and don’t permit `[^…]` to match a newline.
 165         #
 166         # Otherwise, newline acts like any other ordinary character.
 167         var newline = false is writable
 168
 169         # Do not regard the beginning of the specified string as the beginning of a line
 170         #
 171         # More generally, don’t make any assumptions about what text might precede it.
 172         var not_bol = false is writable
 173
 174         # Do not regard the end of the specified string as the end of a line
 175         #
 176         # More generally, don’t make any assumptions about what text might follow it.
 177         var not_eol = false is writable
 178
 179         # Cache of the last used compiled regular expression
 180         private var native: nullable NativeRegex = null
 181
 182         # Cache of a single `regmatch_t` to prevent many calls to `malloc`
 183         private var native_match = new NativeMatchArray.malloc(1) is lazy
 184
 185         # `cflags` of the last successful `compile`
 186         private var cflags_cache = 0
 187
 188         # `string` of the last successful `compile`
 189         private var string_cache: nullable String = null
 190
 191         # Compile the regular expression, if needed
 192         #
 193         # Return `null` on success and an `Error` otherwise.
 194         #
 195         # This method is always called by `get_match` and `has_match`, but the user
 196         # should call it to check for errors.
 197         #
 198         #     assert "ab".to_re.compile == null
 199         #     assert "[ab".to_re.compile.message == "Unmatched [ or [^"
 200         fun compile: nullable Error
 201         do
 202                 var cflags = 0
 203                 if extended then cflags = cflags.bin_or(flag_extended)
 204                 if ignore_case then cflags = cflags.bin_or(flag_icase)
 205                 if optimize_is_in then cflags = cflags.bin_or(flag_nosub)
 206                 if newline then cflags = cflags.bin_or(flag_newline)
 207
 208                 var native = self.native
 209                 var need_compilation = native == null or cflags != cflags_cache or string != string_cache
 210
 211                 if need_compilation then
 212
 213                         # Initial allocation
 214                         if native == null then
 215                                 native = new NativeRegex.malloc
 216                                 self.native = native
 217                         end
 218
 219                         var res = native.regcomp(string.to_cstring, cflags)
 220
 221                         # All is good
 222                         if res == 0 then
 223                                 # Update the cache
 224                                 self.native = native
 225
 226                                 # We store these to know if we need to recompile or not
 227                                 self.cflags_cache = cflags
 228                                 self.string_cache = string
 229
 230                                 return null
 231                         end
 232
 233                         var error_cstr = native.regerror(res)
 234
 235                         # We leave it to the lib to decide how to allocate the string that we keep
 236                         var error_str = error_cstr.to_s_with_copy
 237                         error_cstr.free
 238
 239                         return new Error(error_str)
 240                 end
 241
 242                 return null
 243         end
 244
 245         redef fun finalize
 246         do
 247                 var native = self.native
 248                 if native != null then
 249                         native.regfree
 250                         native.free
 251                         self.native = null
 252                         self.native_match.free
 253                 end
 254         end
 255
 256         private fun gather_eflags: Int
 257         do
 258                 var eflags = 0
 259                 if not_bol then eflags = eflags.bin_or(flag_notbol)
 260                 if not_eol then eflags = eflags.bin_or(flag_noteol)
 261                 return eflags
 262         end
 263
 264         private fun get_error(errcode: Int): String
 265         do
 266                 # Error, should be out of memory but we cover any possible error anyway
 267                 var error_cstr = native.regerror(errcode)
 268
 269                 # We leave it to the lib to decide how to allocate the string that we keep
 270                 var error_str = error_cstr.to_s_with_copy
 271                 error_cstr.free
 272
 273                 return error_str
 274         end
 275
 276         #     assert "ab".to_re.is_in("abcd")
 277         #     assert "ab".to_re.is_in("cdab")
 278         #     assert not "ab".to_re.is_in("acdb")
 279         #     assert "ab".to_re.is_in("ab")
 280         redef fun is_in(text)
 281         do
 282                 var comp_res = compile
 283                 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
 284
 285                 # Actually execute
 286                 var eflags = gather_eflags
 287                 var res = native.regexec_match_only(text.to_cstring, eflags)
 288
 289                 # Got a match?
 290                 if res == 0 then return true
 291
 292                 # Got no match, not an error?
 293                 if res.is_nomatch then return false
 294
 295                 # Error, should be out of memory but we cover any possible error anyway
 296                 var error_str = get_error(res)
 297                 "Regex search failed with: {error_str}\n".output
 298                 abort
 299         end
 300
 301         # require: not optimize_is_in
 302         #
 303         #     assert "l".to_re.search_index_in("hello world", 0) == 2
 304         #     assert "el+o".to_re.search_index_in("hello world", 0) == 1
 305         #     assert "l+".to_re.search_index_in("hello world", 3) == 3
 306         #     assert "z".to_re.search_index_in("hello world", 0) == -1
 307         redef fun search_index_in(text, from)
 308         do
 309                 assert not optimize_is_in
 310
 311                 var comp_res = compile
 312                 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
 313
 314                 # Actually execute
 315                 text = text.to_s
 316                 var cstr = text.substring_from(from).to_cstring
 317                 var eflags = gather_eflags
 318                 var match = self.native_match
 319
 320                 var res = native.regexec(cstr, 1, match, eflags)
 321
 322                 # Found one?
 323                 if res == 0 then return match.rm_so + from
 324
 325                 # No more match?
 326                 if res.is_nomatch then return -1
 327
 328                 # Error, should be out of memory but we cover any possible error anyway
 329                 var error_str = get_error(res)
 330                 "Regex search failed with: {error_str}\n".output
 331                 abort
 332         end
 333
 334         # require: not optimize_is_in
 335         #
 336         #     assert "l".to_re.search_in("hello world", 0).from == 2
 337         #     assert "el+o".to_re.search_in("hello world", 0).from == 1
 338         #     assert "l+".to_re.search_in("hello world", 3).from == 3
 339         #     assert "z".to_re.search_in("hello world", 0) == null
 340         redef fun search_in(text, from)
 341         do
 342                 assert not optimize_is_in
 343
 344                 var comp_res = compile
 345                 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
 346
 347                 # Actually execute
 348                 text = text.to_s
 349                 var cstr = text.substring_from(from).to_cstring
 350                 var eflags = gather_eflags
 351                 var match = self.native_match
 352                 var matches = new Array[Match]
 353
 354                 var res = native.regexec(cstr, 1, match, eflags)
 355
 356                 # Found one?
 357                 if res == 0 then return new Match(text, from + match.rm_so, match.rm_eo - match.rm_so)
 358
 359                 # No more match?
 360                 if res.is_nomatch then return null
 361
 362                 # Error, should be out of memory but we cover any possible error anyway
 363                 var error_str = get_error(res)
 364                 "Regex search failed with: {error_str}\n".output
 365                 abort
 366         end
 367
 368         # require: not optimize_is_in
 369         #
 370         #     assert "ab".to_re.search_all_in("abbab").join(", ") == "ab, ab"
 371         #     assert "b+".to_re.search_all_in("abbabaabbbbbcab").join(", ") == "bb, b, bbbbb, b"
 372         redef fun search_all_in(text)
 373         do
 374                 assert not optimize_is_in
 375
 376                 var comp_res = compile
 377                 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
 378
 379                 # Actually execute
 380                 text = text.to_s
 381                 var cstr = text.to_cstring
 382                 var eflags = gather_eflags
 383                 var eflags_or_notbol = eflags.bin_or(flag_notbol)
 384                 var match = self.native_match
 385                 var matches = new Array[Match]
 386
 387                 var res = native.regexec(cstr, 1, match, eflags)
 388                 var d = 0
 389                 while res == 0 do
 390                         matches.add new Match(text, d + match.rm_so, match.rm_eo - match.rm_so)
 391                         if d == match.rm_eo then
 392                                 d += 1
 393                         else d = d + match.rm_eo
 394                         cstr = cstr.substring_from(match.rm_eo)
 395                         res = native.regexec(cstr, 1, match, eflags_or_notbol)
 396                 end
 397
 398                 # No more match?
 399                 if res.is_nomatch then return matches
 400
 401                 # Error, should be out of memory but we cover any possible error anyway
 402                 var error_str = get_error(res)
 403                 "Regex search failed with: {error_str}\n".output
 404                 abort
 405         end
 406
 407         redef fun to_s do return "/{string}/"
 408 end