GNU Octave  4.0.0
A high-level interpreted language, primarily intended for numerical computations, mostly compatible with Matlab
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Pages
lo-regexp.cc
Go to the documentation of this file.
1 /*
2 
3 Copyright (C) 2012 John W. Eaton
4 Copyright (C) 2005-2015 David Bateman
5 Copyright (C) 2002-2005 Paul Kienzle
6 
7 This file is part of Octave.
8 
9 Octave is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3 of the License, or (at your
12 option) any later version.
13 
14 Octave is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with Octave; see the file COPYING. If not, see
21 <http://www.gnu.org/licenses/>.
22 
23 */
24 
25 #ifdef HAVE_CONFIG_H
26 #include <config.h>
27 #endif
28 
29 #include <list>
30 #include <sstream>
31 #include <string>
32 #include <vector>
33 
34 #if defined (HAVE_PCRE_H)
35 #include <pcre.h>
36 #elif defined (HAVE_PCRE_PCRE_H)
37 #include <pcre/pcre.h>
38 #endif
39 
40 #include "Matrix.h"
41 #include "base-list.h"
42 #include "lo-error.h"
43 #include "oct-locbuf.h"
44 #include "quit.h"
45 #include "lo-regexp.h"
46 #include "str-vec.h"
47 
48 // Define the maximum number of retries for a pattern
49 // that possibly results in an infinite recursion.
50 #define PCRE_MATCHLIMIT_MAX 10
51 
52 // FIXME: should this be configurable?
53 #define MAXLOOKBEHIND 10
54 
55 static bool lookbehind_warned = false;
56 
57 // FIXME: don't bother collecting and composing return values
58 // the user doesn't want.
59 
60 void
62 {
63  if (data)
64  pcre_free (static_cast<pcre *> (data));
65 }
66 
67 void
69 {
70  // If we had a previously compiled pattern, release it.
71  free ();
72 
73  size_t max_length = MAXLOOKBEHIND;
74 
75  size_t pos = 0;
76  size_t new_pos;
77  int inames = 0;
78  std::ostringstream buf;
79 
80  while ((new_pos = pattern.find ("(?", pos)) != std::string::npos)
81  {
82  if (pattern.at (new_pos + 2) == '<'
83  && !(pattern.at (new_pos + 3) == '='
84  || pattern.at (new_pos + 3) == '!'))
85  {
86  // The syntax of named tokens in pcre is "(?P<name>...)" while
87  // we need a syntax "(?<name>...)", so fix that here. Also an
88  // expression like
89  // "(?<first>\w+)\s+(?<last>\w+)|(?<last>\w+),\s+(?<first>\w+)"
90  // should be perfectly legal, while pcre does not allow the same
91  // named token name on both sides of the alternative. Also fix
92  // that here by replacing name tokens by dummy names, and dealing
93  // with the dummy names later.
94 
95  size_t tmp_pos = pattern.find_first_of ('>', new_pos);
96 
97  if (tmp_pos == std::string::npos)
98  {
99  (*current_liboctave_error_handler)
100  ("regexp: syntax error in pattern");
101  return;
102  }
103 
104  std::string tmp_name =
105  pattern.substr (new_pos+3, tmp_pos-new_pos-3);
106 
107  bool found = false;
108 
109  for (int i = 0; i < nnames; i++)
110  {
111  if (named_pats(i) == tmp_name)
112  {
113  named_idx.resize (dim_vector (inames+1, 1));
114  named_idx(inames) = i;
115  found = true;
116  break;
117  }
118  }
119 
120  if (! found)
121  {
122  named_idx.resize (dim_vector (inames+1, 1));
123  named_idx(inames) = nnames;
124  named_pats.append (tmp_name);
125  nnames++;
126  }
127 
128  if (new_pos - pos > 0)
129  buf << pattern.substr (pos, new_pos-pos);
130  if (inames < 10)
131  buf << "(?P<n00" << inames++;
132  else if (inames < 100)
133  buf << "(?P<n0" << inames++;
134  else
135  buf << "(?P<n" << inames++;
136 
137  pos = tmp_pos;
138  }
139  else if (pattern.at (new_pos + 2) == '<')
140  {
141  // Find lookbehind operators of arbitrary length (ie like
142  // "(?<=[a-z]*)") and replace with a maximum length operator
143  // as PCRE can not yet handle arbitrary length lookahead
144  // operators. Use the string length as the maximum length to
145  // avoid issues.
146 
147  int brackets = 1;
148  size_t tmp_pos1 = new_pos + 2;
149  size_t tmp_pos2 = tmp_pos1;
150 
151  while (tmp_pos1 < pattern.length () && brackets > 0)
152  {
153  char ch = pattern.at (tmp_pos1);
154 
155  if (ch == '(')
156  brackets++;
157  else if (ch == ')')
158  {
159  if (brackets > 1)
160  tmp_pos2 = tmp_pos1;
161 
162  brackets--;
163  }
164 
165  tmp_pos1++;
166  }
167 
168  if (brackets != 0)
169  {
170  buf << pattern.substr (pos, new_pos - pos) << "(?";
171  pos = new_pos + 2;
172  }
173  else
174  {
175  size_t tmp_pos3 = pattern.find_first_of ("*+", tmp_pos2);
176 
177  if (tmp_pos3 != std::string::npos && tmp_pos3 < tmp_pos1)
178  {
179  if (!lookbehind_warned)
180  {
181  lookbehind_warned = true;
182  (*current_liboctave_warning_with_id_handler)
183  ("Octave:regexp-lookbehind-limit",
184  "%s: arbitrary length lookbehind patterns are only supported up to length %d",
185  who.c_str (), MAXLOOKBEHIND);
186  }
187 
188  buf << pattern.substr (pos, new_pos - pos) << "(";
189 
190  size_t i;
191 
192  if (pattern.at (tmp_pos3) == '*')
193  i = 0;
194  else
195  i = 1;
196 
197  for (; i < max_length + 1; i++)
198  {
199  buf << pattern.substr (new_pos, tmp_pos3 - new_pos)
200  << "{" << i << "}";
201  buf << pattern.substr (tmp_pos3 + 1,
202  tmp_pos1 - tmp_pos3 - 1);
203  if (i != max_length)
204  buf << "|";
205  }
206  buf << ")";
207  }
208  else
209  buf << pattern.substr (pos, tmp_pos1 - pos);
210 
211  pos = tmp_pos1;
212  }
213  }
214  else
215  {
216  buf << pattern.substr (pos, new_pos - pos) << "(?";
217  pos = new_pos + 2;
218  }
219 
220  }
221 
222  buf << pattern.substr (pos);
223 
224  const char *err;
225  int erroffset;
226  std::string buf_str = buf.str ();
227 
228  int pcre_options
229  = ((options.case_insensitive () ? PCRE_CASELESS : 0)
230  | (options.dotexceptnewline () ? 0 : PCRE_DOTALL)
231  | (options.lineanchors () ? PCRE_MULTILINE : 0)
232  | (options.freespacing () ? PCRE_EXTENDED : 0));
233 
234  data = pcre_compile (buf_str.c_str (), pcre_options, &err, &erroffset, 0);
235 
236  if (! data)
237  (*current_liboctave_error_handler)
238  ("%s: %s at position %d of expression", who.c_str (),
239  err, erroffset);
240 }
241 
243 regexp::match (const std::string& buffer)
244 {
245  regexp::match_data retval;
246 
247  std::list<regexp::match_element> lst;
248 
249  int subpatterns;
250  int namecount;
251  int nameentrysize;
252  char *nametable;
253  size_t idx = 0;
254 
255  pcre *re = static_cast<pcre *> (data);
256 
257  pcre_fullinfo (re, 0, PCRE_INFO_CAPTURECOUNT, &subpatterns);
258  pcre_fullinfo (re, 0, PCRE_INFO_NAMECOUNT, &namecount);
259  pcre_fullinfo (re, 0, PCRE_INFO_NAMEENTRYSIZE, &nameentrysize);
260  pcre_fullinfo (re, 0, PCRE_INFO_NAMETABLE, &nametable);
261 
262  OCTAVE_LOCAL_BUFFER (int, ovector, (subpatterns+1)*3);
263  OCTAVE_LOCAL_BUFFER (int, nidx, namecount);
264 
265  for (int i = 0; i < namecount; i++)
266  {
267  // Index of subpattern in first two bytes MSB first of name.
268  // Extract index.
269  nidx[i] = (static_cast<int> (nametable[i*nameentrysize])) << 8
270  | static_cast<int> (nametable[i*nameentrysize+1]);
271  }
272 
273  while (true)
274  {
275  OCTAVE_QUIT;
276 
277  int matches = pcre_exec (re, 0, buffer.c_str (),
278  buffer.length (), idx,
279  (idx ? PCRE_NOTBOL : 0),
280  ovector, (subpatterns+1)*3);
281 
282  if (matches == PCRE_ERROR_MATCHLIMIT)
283  {
284  // Try harder; start with default value for MATCH_LIMIT
285  // and increase it.
286  (*current_liboctave_warning_with_id_handler)
287  ("Octave:regexp-match-limit",
288  "your pattern caused PCRE to hit its MATCH_LIMIT; trying harder now, but this will be slow");
289 
290  pcre_extra pe;
291 
292  pcre_config (PCRE_CONFIG_MATCH_LIMIT,
293  static_cast<void *> (&pe.match_limit));
294 
295  pe.flags = PCRE_EXTRA_MATCH_LIMIT;
296 
297  int i = 0;
298  while (matches == PCRE_ERROR_MATCHLIMIT
299  && i++ < PCRE_MATCHLIMIT_MAX)
300  {
301  OCTAVE_QUIT;
302 
303  pe.match_limit *= 10;
304  matches = pcre_exec (re, &pe, buffer.c_str (),
305  buffer.length (), idx,
306  (idx ? PCRE_NOTBOL : 0),
307  ovector, (subpatterns+1)*3);
308  }
309  }
310 
311  if (matches < 0 && matches != PCRE_ERROR_NOMATCH)
312  {
313  (*current_liboctave_error_handler)
314  ("%s: internal error calling pcre_exec; error code from pcre_exec is %i",
315  who.c_str (), matches);
316  return retval;
317  }
318  else if (matches == PCRE_ERROR_NOMATCH)
319  break;
320  else if (ovector[1] <= ovector[0] && ! options.emptymatch ())
321  {
322  // Zero length match. Skip to next char.
323  idx = ovector[0] + 1;
324  if (idx < buffer.length ())
325  continue;
326  else
327  break;
328  }
329  else
330  {
331  int pos_match = 0;
332  Matrix token_extents (matches-1, 2);
333 
334  for (int i = 1; i < matches; i++)
335  {
336  if (ovector[2*i] >= 0 && ovector[2*i+1] > 0
337  && (i == 1 || ovector[2*i] != ovector[2*i-2]
338  || ovector[2*i-1] != ovector[2*i+1]))
339  {
340  token_extents(pos_match,0) = double (ovector[2*i]+1);
341  token_extents(pos_match++,1) = double (ovector[2*i+1]);
342  }
343  }
344 
345  token_extents.resize (pos_match, 2);
346 
347  double start = double (ovector[0]+1);
348  double end = double (ovector[1]);
349 
350  const char **listptr;
351  int status = pcre_get_substring_list (buffer.c_str (), ovector,
352  matches, &listptr);
353 
354  if (status == PCRE_ERROR_NOMEMORY)
355  {
356  (*current_liboctave_error_handler)
357  ("%s: cannot allocate memory in pcre_get_substring_list",
358  who.c_str ());
359  return retval;
360  }
361 
362  string_vector tokens (pos_match);
363  string_vector named_tokens (nnames);
364  int pos_offset = 0;
365  pos_match = 0;
366 
367  for (int i = 1; i < matches; i++)
368  {
369  if (ovector[2*i] >= 0 && ovector[2*i+1] > 0)
370  {
371  if (i == 1 || ovector[2*i] != ovector[2*i-2]
372  || ovector[2*i-1] != ovector[2*i+1])
373  {
374  if (namecount > 0)
375  {
376  // FIXME: Should probably do this with a map()
377  // rather than a linear search. However,
378  // the number of captured, named expressions
379  // is usually pretty small (< 4)
380  for (int j = 0; j < namecount; j++)
381  {
382  if (nidx[j] == i)
383  {
384  named_tokens(named_idx(j)) =
385  std::string (*(listptr+i-pos_offset));
386  break;
387  }
388  }
389  }
390 
391  tokens(pos_match++) = std::string (*(listptr+i));
392  }
393  else
394  pos_offset++;
395  }
396  }
397 
398  std::string match_string = std::string (*listptr);
399 
400  pcre_free_substring_list (listptr);
401 
402  regexp::match_element new_elem (named_tokens, tokens, match_string,
403  token_extents, start, end);
404  lst.push_back (new_elem);
405 
406  if (ovector[1] <= ovector[0])
407  {
408  // Zero length match. Skip to next char.
409  idx = ovector[0] + 1;
410  if (idx <= buffer.length ())
411  continue;
412  }
413  else
414  idx = ovector[1];
415 
416  if (options.once () || idx >= buffer.length ())
417  break;
418  }
419  }
420 
421  retval = regexp::match_data (lst, named_pats);
422 
423  return retval;
424 }
425 
426 bool
427 regexp::is_match (const std::string& buffer)
428 {
429  regexp::match_data rx_lst = match (buffer);
430 
431  return rx_lst.size () > 0;
432 }
433 
436 {
437  octave_idx_type len = buffer.length ();
438 
439  Array<bool> retval (dim_vector (len, 1));
440 
441  for (octave_idx_type i = 0; i < buffer.length (); i++)
442  retval(i) = is_match (buffer(i));
443 
444  return retval;
445 }
446 
447 // Declare rep_token_t used in processing replacement string
448 typedef struct
449 {
450  size_t pos;
451  int num;
452 } rep_token_t;
453 
454 
455 std::string
456 regexp::replace (const std::string& buffer, const std::string& replacement)
457 {
458  std::string retval;
459 
460  regexp::match_data rx_lst = match (buffer);
461 
462  size_t num_matches = rx_lst.size ();
463 
464  if (num_matches == 0)
465  {
466  retval = buffer;
467  return retval;
468  }
469 
470  // Identify replacement tokens; build a vector of group numbers in
471  // the replacement string so that we can quickly calculate the size
472  // of the replacement.
473 
474  // FIXME: All code assumes that only 10 tokens ($0-$9) exist.
475  // $11 represents $1 followed by the character '1' rather than
476  // the eleventh capture buffer.
477 
478  std::string repstr = replacement;
479  std::vector<rep_token_t> tokens;
480  tokens.reserve (5); // Reserve memory for 5 pattern replacements
481 
482  for (size_t i=0; i < repstr.size (); i++)
483  {
484  if (repstr[i] == '\\')
485  {
486  if (i < repstr.size () - 1 && repstr[i+1] == '$')
487  {
488  repstr.erase (i,1); // erase backslash
489  i++; // skip over '$'
490  continue;
491  }
492  if (i < repstr.size () - 1 && repstr[i+1] == '\\')
493  {
494  repstr.erase (i,1); // erase 1st backslash
495  continue;
496  }
497  }
498  else if (repstr[i] == '$')
499  {
500  if (i < repstr.size () - 1 && isdigit (repstr[i+1]))
501  {
502  rep_token_t tmp_token;
503 
504  tmp_token.pos = i;
505  tmp_token.num = repstr[i+1]-'0';
506  tokens.push_back (tmp_token);
507  }
508  }
509  }
510 
511  std::string rep;
512  int num_tokens = tokens.size ();
513 
514  if (num_tokens > 0)
515  {
516  // Determine replacement length
517  const size_t replen = repstr.size () - 2*num_tokens;
518  int delta = 0;
520  for (size_t i = 0; i < num_matches; i++)
521  {
522  OCTAVE_QUIT;
523 
524  double start = p->start ();
525  double end = p->end ();
526 
527  const Matrix pairs (p->token_extents ());
528  size_t pairlen = 0;
529  for (int j = 0; j < num_tokens; j++)
530  {
531  if (tokens[j].num == 0)
532  pairlen += static_cast<size_t> (end - start) + 1;
533  else if (tokens[j].num <= pairs.rows ())
534  pairlen += static_cast<size_t> (pairs(tokens[j].num-1,1)
535  - pairs(tokens[j].num-1,0)) + 1;
536  }
537  delta += (static_cast<int> (replen + pairlen)
538  - static_cast<int> (end - start + 1));
539  p++;
540  }
541 
542  // Build replacement string
543  rep.reserve (buffer.size () + delta);
544  size_t from = 0;
545  p = rx_lst.begin ();
546  for (size_t i = 0; i < num_matches; i++)
547  {
548  OCTAVE_QUIT;
549 
550  double start = p->start ();
551  double end = p->end ();
552 
553  const Matrix pairs (p->token_extents ());
554  rep.append (&buffer[from], static_cast<size_t> (start - 1) - from);
555  from = static_cast<size_t> (end);
556 
557  size_t cur_pos = 0;
558 
559  for (int j = 0; j < num_tokens; j++)
560  {
561  rep.append (&repstr[cur_pos], (tokens[j].pos) - cur_pos);
562  cur_pos = tokens[j].pos+2;
563 
564  int k = tokens[j].num;
565  if (k == 0)
566  {
567  // replace with entire match
568  rep.append (&buffer[static_cast<size_t> (end - 1)],
569  static_cast<size_t> (end - start) + 1);
570  }
571  else if (k <= pairs.rows ())
572  {
573  // replace with group capture
574  rep.append (&buffer[static_cast<size_t> (pairs(k-1,0)-1)],
575  static_cast<size_t> (pairs(k-1,1)
576  - pairs(k-1,0)) + 1);
577  }
578  else
579  {
580  // replace with nothing
581  }
582  }
583  if (cur_pos < repstr.size ())
584  rep.append (&repstr[cur_pos], repstr.size () - cur_pos);
585 
586  p++;
587  }
588  rep.append (&buffer[from], buffer.size () - from);
589  }
590  else
591  {
592  // Determine repstr length
593  const size_t replen = repstr.size ();
594  int delta = 0;
596  for (size_t i = 0; i < num_matches; i++)
597  {
598  OCTAVE_QUIT;
599  delta += static_cast<int> (replen)
600  - static_cast<int> (p->end () - p->start () + 1);
601  p++;
602  }
603 
604  // Build replacement string
605  rep.reserve (buffer.size () + delta);
606  size_t from = 0;
607  p = rx_lst.begin ();
608  for (size_t i = 0; i < num_matches; i++)
609  {
610  OCTAVE_QUIT;
611  rep.append (&buffer[from],
612  static_cast<size_t> (p->start () - 1) - from);
613  from = static_cast<size_t> (p->end ());
614  rep.append (repstr);
615  p++;
616  }
617  rep.append (&buffer[from], buffer.size () - from);
618  }
619 
620  retval = rep;
621  return retval;
622 }
Array< int > named_idx
Definition: lo-regexp.h:236
std::string who
Definition: lo-regexp.h:237
void emptymatch(bool val)
Definition: lo-regexp.h:129
std::string pattern
Definition: lo-regexp.h:226
void resize(octave_idx_type nr, octave_idx_type nc, double rfv=0)
Definition: dMatrix.h:130
void dotexceptnewline(bool val)
Definition: lo-regexp.h:128
void freespacing(bool val)
Definition: lo-regexp.h:130
void compile_internal(void)
Definition: lo-regexp.cc:68
string_vector named_pats
Definition: lo-regexp.h:234
size_t pos
Definition: lo-regexp.cc:450
string_vector & append(const std::string &s)
Definition: str-vec.cc:140
void resize(const dim_vector &dv, const T &rfv)
Definition: Array.cc:1033
std::list< match_element >::const_iterator const_iterator
Definition: base-list.h:37
int nnames
Definition: lo-regexp.h:235
Definition: dMatrix.h:35
void once(bool val)
Definition: lo-regexp.h:132
iterator begin(void)
Definition: base-list.h:78
#define MAXLOOKBEHIND
Definition: lo-regexp.cc:53
octave_idx_type length(void) const
Number of elements in the array.
Definition: Array.h:267
std::string replace(const std::string &buffer, const std::string &replacement)
Definition: lo-regexp.cc:456
void case_insensitive(bool val)
Definition: lo-regexp.h:127
match_data match(const std::string &buffer)
Definition: lo-regexp.cc:243
void free(void)
Definition: lo-regexp.cc:61
#define OCTAVE_LOCAL_BUFFER(T, buf, size)
Definition: oct-locbuf.h:197
void lineanchors(bool val)
Definition: lo-regexp.h:131
#define PCRE_MATCHLIMIT_MAX
Definition: lo-regexp.cc:50
#define OCTAVE_QUIT
Definition: quit.h:130
static bool lookbehind_warned
Definition: lo-regexp.cc:55
bool is_match(const std::string &buffer)
Definition: lo-regexp.cc:427
Matrix append(const Matrix &a) const
Definition: dMatrix.cc:460
size_t size(void) const
Definition: base-list.h:44
void * data
Definition: lo-regexp.h:231
opts options
Definition: lo-regexp.h:228