1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2014 Alexis Laferrière <alexis.laf@xymus.net>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # Regular expression support for all services based on `Pattern`
19 # Implemented using libc regular expressions.
21 # The main entities are `Text::to_re` and `Regex`.
29 #include <sys/types.h>
33 # Main extern class to wrap libc regular expression support
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.
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)); `}
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);
48 # Match `string` against the precompiled pattern buffer of `self`, locating matches
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);
56 # Match `string` against the precompiled pattern buffer of `self`, do not locate matches
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);
63 # Free the memory allocated to the pattern buffer by the compiling process
65 # Does not free the memory holding `self`, use `free` for this purpose.
66 fun regfree
`{ regfree(recv); `}
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
);
77 # Number of parenthetical subexpressions in this compiled regular expression
78 fun re_nsub: Int `{ return recv->re_nsub; `}
81 # Flags for `NativeRegex::regcomp`
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; `}
88 # Flags for `NativeRegex::regexec`
90 private fun flag_notbol
: Int `{ return REG_NOTBOL; `}
91 private fun flag_noteol: Int `{ return REG_NOTEOL; `}
93 # Errors of `NativeRegex::regexec`
95 private fun error_nomatch
: Int `{ return REG_NOMATCH; `}
96 private fun error_espace: Int `{ return REG_ESPACE; `}
99 private fun is_nomatch
: Bool `{ return recv == REG_NOMATCH; `}
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)); `}
107 # The offset in string of the beginning of a substring
108 fun rm_so: Int `{ return recv->rm_so; `}
110 # The offset in string of the end of the substring
111 fun rm_eo
: Int `{ return recv->rm_eo; `}
113 # Get a pointer to the element at `index
`, can also be used as a subarray
114 fun [](index: Int): NativeMatchArray `{ return recv + index; `}
117 redef extern class NativeString
118 private fun substring_from
(index
: Int): NativeString `{ return recv + index; `}
122 # Get a `Regex` instance from `self`
123 fun to_re: Regex do return new Regex(self.to_s)
126 # A regular expression pattern
128 # Used as a `Pattern` on intances of `Text` to call `has
`, `search_all
`, `replace
`, etc.
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", ""]
141 # The `String` source of this regular expression
142 var string: String is writable
144 # Treat the pattern as a POSIX extended regular expression (the default)
146 # If `false`, it is treated as a POSIX basic regular expression (BRE).
148 # The extended syntax supports `?`, `+` and `|`. Also, `\
` causes the following
149 # character to be used as literal.
150 var extended = true is writable
152 # Ignore case when matching letters
153 var ignore_case = false is writable
155 # Optimize `self` for `is_in
` and `String::has
`, but do not support searches
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
161 # Treat a newline in string as dividing string into multiple lines
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.
166 # Otherwise, newline acts like any other ordinary character.
167 var newline = false is writable
169 # Do not regard the beginning of the specified string as the beginning of a line
171 # More generally, don’t make any assumptions about what text might precede it.
172 var not_bol = false is writable
174 # Do not regard the end of the specified string as the end of a line
176 # More generally, don’t make any assumptions about what text might follow it.
177 var not_eol = false is writable
179 # Cache of the last used compiled regular expression
180 private var native: nullable NativeRegex = null
182 # Cache of a single `regmatch_t
` to prevent many calls to `malloc
`
183 private var native_match: NativeMatchArray is lazy do
184 native_match_is_init = true
185 return new NativeMatchArray.malloc(native.re_nsub+1)
188 private var native_match_is_init = false
190 # `cflags
` of the last successful `compile
`
191 private var cflags_cache = 0
193 # `string
` of the last successful `compile
`
194 private var string_cache: nullable String = null
196 # Compile the regular expression, if needed
198 # Return `null` on success and an `Error` otherwise.
200 # This method is always called by `get_match
` and `has_match
`, but the user
201 # should call it to check for errors.
203 # assert "ab".to_re.compile == null
204 # assert "[ab".to_re.compile.message == "Unmatched [ or [^"
205 fun compile: nullable Error
208 if extended then cflags = cflags.bin_or(flag_extended)
209 if ignore_case then cflags = cflags.bin_or(flag_icase)
210 if optimize_is_in then cflags = cflags.bin_or(flag_nosub)
211 if newline then cflags = cflags.bin_or(flag_newline)
213 var native = self.native
214 var need_compilation = native == null or cflags != cflags_cache or string != string_cache
216 if need_compilation then
219 if native == null then
220 native = new NativeRegex.malloc
224 var res = native.regcomp(string.to_cstring, cflags)
231 # We store these to know if we need to recompile or not
232 self.cflags_cache = cflags
233 self.string_cache = string
238 var error_cstr = native.regerror(res)
240 # We leave it to the lib to decide how to allocate the string that we keep
241 var error_str = error_cstr.to_s_with_copy
244 return new Error(error_str)
252 var native = self.native
253 if native != null then
258 if native_match_is_init then
259 self.native_match.free
264 private fun gather_eflags: Int
267 if not_bol then eflags = eflags.bin_or(flag_notbol)
268 if not_eol then eflags = eflags.bin_or(flag_noteol)
272 private fun get_error(errcode: Int): String
274 # Error, should be out of memory but we cover any possible error anyway
275 var error_cstr = native.regerror(errcode)
277 # We leave it to the lib to decide how to allocate the string that we keep
278 var error_str = error_cstr.to_s_with_copy
284 # assert "ab".to_re.is_in("abcd")
285 # assert "ab".to_re.is_in("cdab")
286 # assert not "ab".to_re.is_in("acdb")
287 # assert "ab".to_re.is_in("ab")
288 redef fun is_in(text)
290 var comp_res = compile
291 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
294 var eflags = gather_eflags
295 var res = native.regexec_match_only(text.to_cstring, eflags)
298 if res == 0 then return true
300 # Got no match, not an error?
301 if res.is_nomatch then return false
303 # Error, should be out of memory but we cover any possible error anyway
304 var error_str = get_error(res)
305 "Regex search failed with: {error_str}\n".output
309 # require: not optimize_is_in
311 # assert "l".to_re.search_index_in("hello world", 0) == 2
312 # assert "el+o".to_re.search_index_in("hello world", 0) == 1
313 # assert "l+".to_re.search_index_in("hello world", 3) == 3
314 # assert "z".to_re.search_index_in("hello world", 0) == -1
315 redef fun search_index_in(text, from)
317 assert not optimize_is_in
319 var comp_res = compile
320 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
324 var cstr = text.substring_from(from).to_cstring
325 var eflags = gather_eflags
326 var match = self.native_match
328 var res = native.regexec(cstr, 1, match, eflags)
331 if res == 0 then return match.rm_so + from
334 if res.is_nomatch then return -1
336 # Error, should be out of memory but we cover any possible error anyway
337 var error_str = get_error(res)
338 "Regex search failed with: {error_str}\n".output
342 # require: not optimize_is_in
344 # assert "l".to_re.search_in("hello world", 0).from == 2
345 # assert "el+o".to_re.search_in("hello world", 0).from == 1
346 # assert "l+".to_re.search_in("hello world", 3).from == 3
347 # assert "z".to_re.search_in("hello world", 0) == null
348 redef fun search_in(text, from)
350 assert not optimize_is_in
352 var comp_res = compile
353 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
357 var cstr = text.substring_from(from).to_cstring
358 var eflags = gather_eflags
359 var native_match = self.native_match
361 var nsub = native.re_nsub
362 var res = native.regexec(cstr, nsub+1, native_match, eflags)
366 var match = new Match(text,
367 from + native_match.rm_so,
368 native_match.rm_eo - native_match.rm_so)
370 # Add sub expressions
371 for i in [1..nsub] do
372 match.subs.add new Match( text,
373 native_match[i].rm_so,
374 native_match[i].rm_eo - native_match[i].rm_so)
381 if res.is_nomatch then return null
383 # Error, should be out of memory but we cover any possible error anyway
384 var error_str = get_error(res)
385 "Regex search failed with: {error_str}\n".output
389 # require: not optimize_is_in
391 # assert "ab".to_re.search_all_in("abbab").join(", ") == "ab, ab"
392 # assert "b+".to_re.search_all_in("abbabaabbbbbcab").join(", ") == "bb, b, bbbbb, b"
393 redef fun search_all_in(text)
395 assert not optimize_is_in
397 var comp_res = compile
398 assert comp_res == null else "Regex compilation failed with: {comp_res.message}\n".output
402 var cstr = text.to_cstring
403 var eflags = gather_eflags
404 var eflags_or_notbol = eflags.bin_or(flag_notbol)
405 var native_match = self.native_match
406 var matches = new Array[Match]
408 var nsub = native.re_nsub
409 var res = native.regexec(cstr, nsub+1, native_match, eflags)
412 var match = new Match(text,
413 d + native_match.rm_so,
414 native_match.rm_eo - native_match.rm_so)
417 # Add sub expressions
418 for i in [1..nsub] do
419 match.subs.add new Match( text,
420 d + native_match[i].rm_so,
421 native_match[i].rm_eo - native_match[i].rm_so)
424 if d == native_match.rm_eo then
426 else d = d + native_match.rm_eo
427 cstr = cstr.substring_from(native_match.rm_eo)
428 res = native.regexec(cstr, nsub+1, native_match, eflags_or_notbol)
432 if res.is_nomatch then return matches
434 # Error, should be out of memory but we cover any possible error anyway
435 var error_str = get_error(res)
436 "Regex search failed with: {error_str}\n".output
440 redef fun to_s do return "/{string}/"
444 # Parenthesized subexpressions in this match
447 # var re = "c (d e+) f".to_re
448 # var match = "a b c d eee f g".search(re)
449 # assert match.subs.length == 1
450 # assert match.subs.first.to_s == "d eee"
452 var subs = new Array[Match] is lazy
454 # Get the `n
`th expression in this match
456 # `n
== 0` returns this match, and a greater `n
` returns the corresponding
459 # Require: `n
>= 0 and n
<= subs
.length
`
462 # var re = "c (d e+) f".to_re
463 # var match = "a b c d eee f g".search(re)
464 # assert match[0].to_s == "c d eee f"
465 # assert match[1].to_s == "d eee"
467 fun [](n: Int): Match do
468 if n == 0 then return self
469 assert n > 0 and n <= subs.length