slre.c File Reference

#include <stdio.h>
#include <assert.h>
#include <ctype.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include "slre.h"

Include dependency graph for slre.c:

Go to the source code of this file.

Data Structures
struct	slre
struct	cap

Enumerations
enum	{   END, BRANCH, ANY, EXACT,   ANYOF, ANYBUT, OPEN, CLOSE,   BOL, EOL, STAR, PLUS,   STARQ, PLUSQ, QUEST, SPACE,   NONSPACE, DIGIT }

Functions
static void	set_jump_offset (struct slre *r, int pc, int offset)
static void	emit (struct slre *r, int code)
static void	store_char_in_data (struct slre *r, int ch)
static void	exact (struct slre *r, const char **re)
static int	get_escape_char (const char **re)
static void	anyof (struct slre *r, const char **re)
static void	relocate (struct slre *r, int begin, int shift)
static void	quantifier (struct slre *r, int prev, int op)
static void	exact_one_char (struct slre *r, int ch)
static void	fixup_branch (struct slre *r, int fixup)
static void	compile (struct slre *r, const char **re)
static const char *	compile2 (struct slre *r, const char *re)
static const char *	match (const struct slre *, int, const char *, int, int *, struct cap *)
static void	loop_greedy (const struct slre *r, int pc, const char *s, int len, int *ofs)
static void	loop_non_greedy (const struct slre *r, int pc, const char *s, int len, int *ofs)
static int	is_any_of (const unsigned char *p, int len, const char *s, int *ofs)
static int	is_any_but (const unsigned char *p, int len, const char *s, int *ofs)
static int	lowercase (const char *s)
static int	casecmp (const void *p1, const void *p2, size_t len)
static const char *	match2 (const struct slre *r, const char *buf, int len, struct cap *caps)
static const char *	capture_float (const struct cap *cap, void *p, size_t len)
static const char *	capture_string (const struct cap *cap, void *p, size_t len)
static const char *	capture_int (const struct cap *cap, void *p, size_t len)
static const char *	capture (const struct cap *caps, int num_caps, va_list ap)
const char *	slre_match (enum slre_option options, const char *re, const char *buf, int buf_len,...)

Variables
static const char *	meta_characters = "|.*+?()[\\"
static const char *	error_no_match = "No match"

Enumeration Type Documentation

anonymous enum

Enumerator
END
BRANCH
ANY
EXACT
ANYOF
ANYBUT
OPEN
CLOSE
BOL
EOL
STAR
PLUS
STARQ
PLUSQ
QUEST
SPACE
NONSPACE
DIGIT

Definition at line 49 of file slre.c.

     {
  END, BRANCH, ANY, EXACT, ANYOF, ANYBUT, OPEN, CLOSE, BOL, EOL, STAR, PLUS,
  STARQ, PLUSQ, QUEST, SPACE, NONSPACE, DIGIT
};

Function Documentation

static void anyof ( struct slre *  r, const char **  re  )

static

Definition at line 140 of file slre.c.

                                                   {
  int  esc, old_data_size = r->data_size, op = ANYOF;

  while (**re != '\0')

    switch (*(*re)++) {
      case ']':
        emit(r, op);
        emit(r, old_data_size);
        emit(r, r->data_size - old_data_size);
        return;
        // NOTREACHED
        break;
      case '\\':
        esc = get_escape_char(re);
        if ((esc & 0xff) == 0) {
          store_char_in_data(r, 0);
          store_char_in_data(r, esc >> 8);
        } else {
          store_char_in_data(r, esc);
        }
        break;
      default:
        store_char_in_data(r, (*re)[-1]);
        break;
    }

  r->error_string = "No closing ']' bracket";
}

Here is the call graph for this function:

Here is the caller graph for this function:

static const char* capture ( const struct cap *  caps, int  num_caps, va_list  ap  )

static

Definition at line 626 of file slre.c.

                                                                             {
  int i, type;
  size_t size;
  void *p;
  const char *err = NULL;

  for (i = 0; i < num_caps; i++) {
    type = va_arg(ap, int);
    size = va_arg(ap, size_t);
    p = va_arg(ap, void *);
    switch (type) {
      case SLRE_INT: err = capture_int(&caps[i], p, size); break;
      case SLRE_FLOAT: err = capture_float(&caps[i], p, size); break;
      case SLRE_STRING: err = capture_string(&caps[i], p, size); break;
      default: err = "Unknown type, expected SLRE_(INT|FLOAT|STRING)"; break;
    }
  }
  return err;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static const char* capture_float ( const struct cap *  cap, void *  p, size_t  len  )

static

Definition at line 588 of file slre.c.

                                                                             {
  const char *fmt;
  char buf[20];

  switch (len) {
    case sizeof(float): fmt = "f"; break;
    case sizeof(double): fmt = "lf"; break;
    default: return "SLRE_FLOAT: unsupported size";
  }

  sprintf(buf, "%%%d%s", cap->len, fmt);
  return sscanf(cap->ptr, buf, p) == 1 ? NULL : "SLRE_FLOAT: capture failed";
}

Here is the caller graph for this function:

static const char* capture_int ( const struct cap *  cap, void *  p, size_t  len  )

static

Definition at line 611 of file slre.c.

                                                                           {
  const char *fmt;
  char buf[20];

  switch (len) {
    case sizeof(char): fmt = "hh"; break;
    case sizeof(short): fmt = "h"; break;
    case sizeof(int): fmt = "d"; break;
    default: return "SLRE_INT: unsupported size";
  }

  sprintf(buf, "%%%d%s", cap->len, fmt);
  return sscanf(cap->ptr, buf, p) == 1 ? NULL : "SLRE_INT: capture failed";
}

Here is the caller graph for this function:

static const char* capture_string ( const struct cap *  cap, void *  p, size_t  len  )

static

Definition at line 602 of file slre.c.

                                                                              {
  if ((int) len <= cap->len) {
    return "SLRE_STRING: buffer size too small";
  }
  memcpy(p, cap->ptr, cap->len);
  ((char *) p)[cap->len] = '\0';
  return NULL;
}

Here is the caller graph for this function:

static int casecmp ( const void *  p1, const void *  p2, size_t  len  )

static

Definition at line 392 of file slre.c.

                                                               {
  const char *s1 = (const char *) p1, *s2 = (const char *) p2;
  int diff = 0;

  if (len > 0)
    do {
      diff = lowercase(s1++) - lowercase(s2++);
    } while (diff == 0 && s1[-1] != '\0' && --len > 0);

  return diff;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void compile ( struct slre *  r, const char **  re  )

static

Definition at line 203 of file slre.c.

                                                     {
  int  op, esc, branch_start, last_op, fixup, cap_no, level;

  fixup = 0;
  level = r->num_caps;
  branch_start = last_op = r->code_size;

  for (;;)
    switch (*(*re)++) {

      case '\0':
        (*re)--;
        return;
        // NOTREACHED
        break;

      case '.':
        last_op = r->code_size;
        emit(r, ANY);
        break;

      case '[':
        last_op = r->code_size;
        anyof(r, re);
        break;

      case '\\':
        last_op = r->code_size;
        esc = get_escape_char(re);
        if (esc & 0xff00) {
          emit(r, esc >> 8);
        } else {
          exact_one_char(r, esc);
        }
        break;

      case '(':
        last_op = r->code_size;
        cap_no = ++r->num_caps;
        emit(r, OPEN);
        emit(r, cap_no);

        compile(r, re);
        if (*(*re)++ != ')') {
          r->error_string = "No closing bracket";
          return;
        }

        emit(r, CLOSE);
        emit(r, cap_no);
        break;

      case ')':
        (*re)--;
        fixup_branch(r, fixup);
        if (level == 0) {
          r->error_string = "Unbalanced brackets";
          return;
        }
        return;
        // NOTREACHED
        break;

      case '+':
      case '*':
        op = (*re)[-1] == '*' ? STAR: PLUS;
        if (**re == '?') {
          (*re)++;
          op = op == STAR ? STARQ : PLUSQ;
        }
        quantifier(r, last_op, op);
        break;

      case '?':
        quantifier(r, last_op, QUEST);
        break;

      case '|':
        fixup_branch(r, fixup);
        relocate(r, branch_start, 3);
        r->code[branch_start] = BRANCH;
        set_jump_offset(r, branch_start + 1, branch_start);
        fixup = branch_start + 2;
        r->code[fixup] = 0xff;
        break;

      default:
        (*re)--;
        last_op = r->code_size;
        exact(r, re);
        break;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static const char* compile2 ( struct slre *  r, const char *  re  )

static

Definition at line 299 of file slre.c.

                                                            {
  r->error_string = NULL;
  r->code_size = r->data_size = r->num_caps = r->anchored = 0;

  emit(r, OPEN);  // This will capture what matches full RE
  emit(r, 0);

  while (*re != '\0') {
    compile(r, &re);
  }

  if (r->code[2] == BRANCH) {
    fixup_branch(r, 4);
  }

  emit(r, CLOSE);
  emit(r, 0);
  emit(r, END);

#if 0
  static void dump(const struct slre *, FILE *);
  dump(r, stdout);
#endif

  return r->error_string;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void emit ( struct slre *  r, int  code  )

static

Definition at line 95 of file slre.c.

                                           {
  if (r->code_size >= (int) (sizeof(r->code) / sizeof(r->code[0]))) {
    r->error_string = "RE is too long (code overflow)";
  } else {
    r->code[r->code_size++] = (unsigned char) code;
  }
}

Here is the caller graph for this function:

static void exact ( struct slre *  r, const char **  re  )

static

Definition at line 111 of file slre.c.

                                                   {
  int  old_data_size = r->data_size;

  while (**re != '\0' && (strchr(meta_characters, **re)) == NULL) {
    store_char_in_data(r, *(*re)++);
  }

  emit(r, EXACT);
  emit(r, old_data_size);
  emit(r, r->data_size - old_data_size);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void exact_one_char ( struct slre *  r, int  ch  )

static

Definition at line 189 of file slre.c.

                                                   {
  emit(r, EXACT);
  emit(r, r->data_size);
  emit(r, 1);
  store_char_in_data(r, ch);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void fixup_branch ( struct slre *  r, int  fixup  )

static

Definition at line 196 of file slre.c.

                                                    {
  if (fixup > 0) {
    emit(r, END);
    set_jump_offset(r, fixup, fixup - 2);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int get_escape_char ( const char **  re )

static

Definition at line 123 of file slre.c.

                                            {
  int  res;

  switch (*(*re)++) {
    case 'n':  res = '\n';    break;
    case 'r':  res = '\r';    break;
    case 't':  res = '\t';    break;
    case '0':  res = 0;    break;
    case 'S':  res = NONSPACE << 8;  break;
    case 's':  res = SPACE << 8;  break;
    case 'd':  res = DIGIT << 8;  break;
    default:  res = (*re)[-1];  break;
  }

  return res;
}

Here is the caller graph for this function:

static int is_any_but ( const unsigned char *  p, int  len, const char *  s, int *  ofs  )

static

Definition at line 373 of file slre.c.

                                {
  int  i, ch;

  ch = s[*ofs];

  for (i = 0; i < len; i++)
    if (p[i] == ch) {
      return 0;
    }

  (*ofs)++;
  return 1;
}

Here is the caller graph for this function:

static int is_any_of ( const unsigned char *  p, int  len, const char *  s, int *  ofs  )

static

Definition at line 359 of file slre.c.

                                                                               {
  int  i, ch;

  ch = s[*ofs];

  for (i = 0; i < len; i++)
    if (p[i] == ch) {
      (*ofs)++;
      return 1;
    }

  return 0;
}

Here is the caller graph for this function:

static void loop_greedy ( const struct slre *  r, int  pc, const char *  s, int  len, int *  ofs  )

static

Definition at line 329 of file slre.c.

                                  {
  int  saved_offset, matched_offset;

  saved_offset = matched_offset = *ofs;

  while (!match(r, pc + 2, s, len, ofs, NULL)) {
    saved_offset = *ofs;
    if (!match(r, pc + r->code[pc + 1], s, len, ofs, NULL)) {
      matched_offset = saved_offset;
    }
    *ofs = saved_offset;
  }

  *ofs = matched_offset;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void loop_non_greedy ( const struct slre *  r, int  pc, const char *  s, int  len, int *  ofs  )

static

Definition at line 346 of file slre.c.

                                               {
  int  saved_offset = *ofs;

  while (!match(r, pc + 2, s, len, ofs, NULL)) {
    saved_offset = *ofs;
    if (!match(r, pc + r->code[pc + 1], s, len, ofs, NULL))
      break;
  }

  *ofs = saved_offset;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int lowercase ( const char *  s )

static

Definition at line 388 of file slre.c.

                                    {
  return tolower(* (const unsigned char *) s);
}

Here is the caller graph for this function:

static const char * match ( const struct slre *  r, int  pc, const char *  s, int  len, int *  ofs, struct cap *  caps  )

static

Definition at line 404 of file slre.c.

                                                     {
  int n, saved_offset;
  const char *error_string = NULL;
  int (*cmp)(const void *string1, const void *string2, size_t len);

  while (error_string == NULL && r->code[pc] != END) {

    assert(pc < r->code_size);
    assert(pc < (int) (sizeof(r->code) / sizeof(r->code[0])));

    switch (r->code[pc]) {
      case BRANCH:
        saved_offset = *ofs;
        error_string = match(r, pc + 3, s, len, ofs, caps);
        if (error_string != NULL) {
          *ofs = saved_offset;
          error_string = match(r, pc + r->code[pc + 1], s, len, ofs, caps);
        }
        pc += r->code[pc + 2];
        break;

      case EXACT:
        error_string = error_no_match;
        n = r->code[pc + 2];  // String length
        cmp = r->options & SLRE_CASE_INSENSITIVE ? casecmp : memcmp;
        if (n <= len - *ofs && !cmp(s + *ofs, r->data + r->code[pc + 1], n)) {
          (*ofs) += n;
          error_string = NULL;
        }
        pc += 3;
        break;

      case QUEST:
        error_string = NULL;
        saved_offset = *ofs;
        if (match(r, pc + 2, s, len, ofs, caps) != NULL) {
          *ofs = saved_offset;
        }
        pc += r->code[pc + 1];
        break;

      case STAR:
        error_string = NULL;
        loop_greedy(r, pc, s, len, ofs);
        pc += r->code[pc + 1];
        break;

      case STARQ:
        error_string = NULL;
        loop_non_greedy(r, pc, s, len, ofs);
        pc += r->code[pc + 1];
        break;

      case PLUS:
        if ((error_string = match(r, pc + 2, s, len, ofs, caps)) != NULL)
          break;

        loop_greedy(r, pc, s, len, ofs);
        pc += r->code[pc + 1];
        break;

      case PLUSQ:
        if ((error_string = match(r, pc + 2, s, len, ofs, caps)) != NULL)
          break;

        loop_non_greedy(r, pc, s, len, ofs);
        pc += r->code[pc + 1];
        break;

      case SPACE:
        error_string = error_no_match;
        if (*ofs < len && isspace(((const unsigned char *)s)[*ofs])) {
          (*ofs)++;
          error_string = NULL;
        }
        pc++;
        break;

      case NONSPACE:
        error_string = error_no_match;
        if (*ofs <len && !isspace(((const unsigned char *)s)[*ofs])) {
          (*ofs)++;
          error_string = NULL;
        }
        pc++;
        break;

      case DIGIT:
        error_string = error_no_match;
        if (*ofs < len && isdigit(((const unsigned char *)s)[*ofs])) {
          (*ofs)++;
          error_string = NULL;
        }
        pc++;
        break;

      case ANY:
        error_string = error_no_match;
        if (*ofs < len) {
          (*ofs)++;
          error_string = NULL;
        }
        pc++;
        break;

      case ANYOF:
        error_string = error_no_match;
        if (*ofs < len)
          error_string = is_any_of(r->data + r->code[pc + 1], r->code[pc + 2],
                                   s, ofs) ? NULL : error_no_match;
        pc += 3;
        break;

      case ANYBUT:
        error_string = error_no_match;
        if (*ofs < len)
          error_string = is_any_but(r->data + r->code[pc + 1], r->code[pc + 2],
                                    s, ofs) ? NULL : error_no_match;
        pc += 3;
        break;

      case BOL:
        error_string = *ofs == 0 ? NULL : error_no_match;
        pc++;
        break;

      case EOL:
        error_string = *ofs == len ? NULL : error_no_match;
        pc++;
        break;

      case OPEN:
        if (caps != NULL)
          caps[r->code[pc + 1]].ptr = s + *ofs;
        pc += 2;
        break;

      case CLOSE:
        if (caps != NULL)
          caps[r->code[pc + 1]].len = (s + *ofs) -
            caps[r->code[pc + 1]].ptr;
        pc += 2;
        break;

      case END:
        pc++;
        break;

      default:
        printf("unknown cmd (%d) at %d\n", r->code[pc], pc);
        assert(0);
        break;
    }
  }

  return error_string;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static const char* match2 ( const struct slre *  r, const char *  buf, int  len, struct cap *  caps  )

static

Definition at line 571 of file slre.c.

                                            {
  int  i, ofs = 0;
  const char *error_string = error_no_match;

  if (r->anchored) {
    error_string = match(r, 0, buf, len, &ofs, caps);
  } else {
    for (i = 0; i < len && error_string != NULL; i++) {
      ofs = i;
      error_string = match(r, 0, buf, len, &ofs, caps);
    }
  }

  return error_string;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void quantifier ( struct slre *  r, int  prev, int  op  )

static

Definition at line 176 of file slre.c.

                                                         {
  if (r->code[prev] == EXACT && r->code[prev + 2] > 1) {
    r->code[prev + 2]--;
    emit(r, EXACT);
    emit(r, r->code[prev + 1] + r->code[prev + 2]);
    emit(r, 1);
    prev = r->code_size - 3;
  }
  relocate(r, prev, 2);
  r->code[prev] = op;
  set_jump_offset(r, prev + 1, prev);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void relocate ( struct slre *  r, int  begin, int  shift  )

static

Definition at line 170 of file slre.c.

                                                           {
  emit(r, END);
  memmove(r->code + begin + shift, r->code + begin, r->code_size - begin);
  r->code_size += shift;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void set_jump_offset ( struct slre *  r, int  pc, int  offset  )

static

Definition at line 86 of file slre.c.

                                                                {
  assert(offset < r->code_size);
  if (r->code_size - offset > 0xff) {
    r->error_string = "Jump offset is too big";
  } else {
    r->code[pc] = (unsigned char) (r->code_size - offset);
  }
}

Here is the caller graph for this function:

const char* slre_match	(	enum slre_option	options,
		const char *	re,
		const char *	buf,
		int	buf_len,
			...
	)

Definition at line 646 of file slre.c.

                                                          {
  struct slre slre;
  struct cap caps[20];
  va_list ap;
  const char *error_string = NULL;

  slre.options = options;
  if ((error_string = compile2(&slre, re)) == NULL &&
      (error_string = match2(&slre, buf, buf_len, caps)) == NULL) {
    va_start(ap, buf_len);
    error_string = capture(caps + 1, slre.num_caps, ap);
    va_end(ap);
  }

  return error_string;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void store_char_in_data ( struct slre *  r, int  ch  )

static

Definition at line 103 of file slre.c.

                                                       {
  if (r->data_size >= (int) sizeof(r->data)) {
    r->error_string = "RE is too long (data overflow)";
  } else {
    r->data[r->data_size++] = ch;
  }
}

Here is the caller graph for this function:

Variable Documentation

const char* error_no_match = "No match"

static

Definition at line 84 of file slre.c.

const char* meta_characters = "|.*+?()[\\"

static

Definition at line 83 of file slre.c.