/*
 * @author fenrir (http://fenrir.naruoka.org/)
 * 
 * reg_compile.c
 * コンパイル動作
 */

#include "reg_core.h"
#include "reg_util.h"
#include "reg_string.h"
#include "reg_char.h"
#include <string.h>

#ifdef __cplusplus
extern "C"{
#endif

/* ユーティリティメソッド */

/**
 * 状態をコピーします。
 * 
 * @param dist コピー先
 * @param src コピー元
 * @return コピー先のポインタ(memcpyの返却値)
 */
static reg_state_t *state_copy(reg_state_t *dist, reg_state_t *src){
  return (reg_state_t *)memcpy(dist, src, sizeof(reg_state_t));
}

/**
 * 遷移ノードをコピーします。
 * 
 * @param dist コピー先
 * @param src コピー元
 * @return コピー先のポインタ(memcpyの返却値)
 */
static reg_node_t *node_copy(reg_node_t *dist, reg_node_t *src){
  return (reg_node_t *)memcpy(dist, src, sizeof(reg_node_t));
}

/**
 * 状態が等しいか調べます。
 * 
 * @param state1 状態1
 * @param state2 状態2
 * @return 等しい場合は0以外、等しくない場合は0
 */
static boolean state_equal(reg_state_t *state1, reg_state_t *state2){
  return (state1->node == state2->node) ?
            (state1->input_index == state2->input_index) :
            FALSE;
}

/* 遷移アルゴリズム */

/**
 * 遷移アルゴリズム0(NULL)
 * 何もしません。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *null(reg_state_t *current, reg_stack_t *stack){
  return stack->top;
}

/**
 * 遷移アルゴリズム1(GO)
 * 遷移ノード列で一つ先のノードをスタックに積みます。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *go(reg_state_t *current, reg_stack_t *stack){
  current->node++;
  return ++(stack->top);
}

/**
 * 遷移アルゴリズム2(JUMP)
 * 遷移ノード列で現在のノードのinfoで指定されたノードをスタックに積みます。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *jump(reg_state_t *current, reg_stack_t *stack){
  current->node = (reg_node_t *)current->node->info;
  return ++(stack->top);
}

/**
 * 遷移アルゴリズム3(GO_JUMP)
 * 遷移ノード列で現在のノードのinfoで指定されたノードをスタックに積み、
 * その後遷移ノード列で一つ先のノードをスタックに積みます。
 * つまりGOが優先です。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *go_jump(reg_state_t *current, reg_stack_t *stack){
  state_copy(current + 1, current);
  jump(current, stack);
  
  /* ループ検出 */
  reg_state_t *old;
  for(old = current - 1; old >= (stack->bottom); old--){
    if(state_equal(current, old)){
      return --(stack->top);
    }  
  }
  
  /* オーバーフロー検出 */
  if((++current) - stack->bottom >= stack->size){return NULL;}
  
  return go(current, stack);
}

/**
 * 遷移アルゴリズム4(JUMP_GO)
 * 遷移ノード列で一つ先のノードをスタックに積み、
 * その後遷移ノード列で現在のノードのinfoで指定されたノードをスタックに積みます。
 * つまりJUMPが優先です。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *jump_go(reg_state_t *current, reg_stack_t *stack){
  state_copy(current + 1, current);
  go(current, stack);
  
  /* ループ検出 */
  reg_state_t *old;
  for(old = current - 1; old >= (stack->bottom); old--){
    if(state_equal(current, old)){
      return --(stack->top);
    }  
  }
  
  /* オーバーフロー検出 */
  if((++current) - stack->bottom >= stack->size){return NULL;}
  
  return jump(current, stack);
}

/**
 * 遷移アルゴリズム5(EQUAL)
 * もし現在のノードのinfoと現在の状態がマッチした場合、
 * 遷移ノード列で一つ先のノードをスタックに積みます。
 * しなかった場合はスタックになにも積みません。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *equal(reg_state_t *current, reg_stack_t *stack){
  if(reg_compare((char *)current->node->info, current->input_index) == MATCH){
    current->input_index = reg_char_shift(current->input_index, 1);
    return go(current, stack);
  }
  return stack->top;
}

/**
 * 遷移アルゴリズム6(GO_WITH_START_MARK)
 * 現在のノードのinfoにあるサブマッチ開始ノードをスタックに積んだあと、
 * 遷移ノード列で一つ先のノードをスタックに積みます。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *go_with_start_mark(reg_state_t *current, reg_stack_t *stack){
  state_copy(current + 1, current);
  current->node = ((reg_submatch_t *)current->node->info)->start;
  (stack->top)++;
  
  /* オーバーフロー検出 */
  if((++current) - stack->bottom >= stack->size){return NULL;}
  
  return go(current, stack);
}

/**
 * 遷移アルゴリズム7(GO_WITH_END_MARK)
 * 現在のノードのinfoにあるサブマッチ終了ノードをスタックに積んだあと、
 * 遷移ノード列で一つ先のノードをスタックに積みます。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *go_with_end_mark(reg_state_t *current, reg_stack_t *stack){
  state_copy(current + 1, current);
  current->node = ((reg_submatch_t *)current->node->info)->end;
  (stack->top)++;
  
  /* オーバーフロー検出 */
  if((++current) - stack->bottom >= stack->size){return NULL;}
  
  return go(current, stack);
}

/**
 * 遷移アルゴリズム8(INVOKED_BY_SUBMATCH_START_NODE)
 * サブマッチ開始ノードがスタックからポップした際に呼び出されるアルゴリズムです。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *invoked_by_submatch_start_node(reg_state_t *current, reg_stack_t *stack){
  
  return null(current, stack);
}

/**
 * 遷移アルゴリズム9(INVOKED_BY_SUBMATCH_END_NODE)
 * サブマッチ終了ノードがスタックからポップした際に呼び出されるアルゴリズムです。
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *invoked_by_submatch_end_node(reg_state_t *current, reg_stack_t *stack){

  return null(current, stack);
}

/**
 * 遷移アルゴリズム10(EQUAL_BACKREF)
 * 
 * @param current 現在の状態
 * @param stack スタック
 * @return スタックの先頭
 */
static reg_state_t *equal_backref(reg_state_t *current, reg_stack_t *stack){

  reg_range_t *range;
  if(!(range = find_submatch((reg_submatch_t *)current->node->info, stack))){return NULL;}
  
  char *target = range->start;
  while(target < range->end){
    if(reg_char_compare(target, current->input_index) != MATCH){return stack->top;}
    target = reg_char_shift(target, 1);
    current->input_index = reg_char_shift(current->input_index, 1);
  }
  return go(current, stack);
}


/* 正規表現コンパイラ */

/**
 * ノードを複製します。
 * コピー先とコピー元が重なった場合も正しく処理されます。
 * 
 * @param dist コピー先
 * @param src コピー元
 * @param length ノードの数
 */
static void duplicate(reg_node_t *dist, reg_node_t *src, int length){
  int shift;
  if(dist == src){return;}
  if(dist > src){
    dist += (length - 1);
    src += (length - 1);
    shift = -1;
  }else{shift = 1;}

  for(;length > 0; dist += shift, src += shift, length--){
    node_copy(dist, src);
    if((src->transit == jump) ||
          (src->transit == go_jump) ||
          (src->transit == jump_go)){
      dist->info = (void *)((reg_node_t *)src->info - src + dist);
    }
  }
}

/* バッファアンダーランの抑制 */
#define check_node_size(_regexp, size)\
if((_regexp->list.end - _regexp->list.top + size) > _regexp->list.max){return NULL;}

#define check_submatch_size(_regexp, size)\
if((_regexp->match_object.submatch_end - _regexp->match_object.submatch_top + size) > _regexp->match_object.submatch_max){return NULL;}


/**
 * 正規表現文字列でトークンの直後を返します。
 * トークンとは文字や文字クラスのことです。
 * 
 * @param regexp_str 正規表現文字列
 * @param status エラーが起きた場合にエラー情報を格納するための変数へのポインタ
 * @return トークンの直後
 */
static char *after_token(char *regexp_str, reg_status_t *status){
  switch(*regexp_str){
    case CHAR_CLASS_START:
      regexp_str++;
      while(regexp_str = reg_char_shift(regexp_str, (*regexp_str == ESCAPE_CHARACTER ? 2 : 1))){
        if(*regexp_str == NULL_CHAR){
          *status = REG_ERR_C_TOO_FEW_BRACKET;
          return NULL;
        }
        if(*regexp_str == CHAR_CLASS_END){break;}
      }
      break;
    case ESCAPE_CHARACTER:
      regexp_str++;
      break;
  }
  return reg_char_shift(regexp_str, 1);
}

#define UNLIMITED -1

static char *parse_one_phrase(regexp_t *regexp, char *regexp_str, char exit_char);

/**
 * 正規表現文字列にて1つの正規表現文字を処理します。
 * 1つの正規表現文字とは
 * トークン + 回数指定のことです。
 * 戻り値は次の正規表現文字の先頭です。
 *
 * @param regexp コンパイル済み正規表現を格納する先
 * @param regexp_str 正規表現文字列
 * @return 次の正規表現文字
 */
static char *parse_and_next(regexp_t *regexp, char *regexp_str){
  
  /* 正規表現文字の処理
   * もしグループ開始文字の場合は、再帰によってグループ内の文字を処理
   * また、マークする必要があるかもみる
   * 
   * その後、トークンの直後へ移動
   * 繰り返し指定がある場合は繰り返し指定に
   * さもない場合は同レベルの次の文字に
   */
  reg_node_t *pre = regexp->list.end;
  reg_submatch_t *mark = NULL;
  if(*regexp_str == GROUP_START){
    (regexp->status)++;
    if(*(++regexp_str) == GROUP_WITHOUT_MARK){regexp_str++;}
    else{
      check_submatch_size(regexp, 1);
      mark = regexp->match_object.submatch_end++;
    }
    if((regexp_str = parse_one_phrase(regexp, regexp_str, GROUP_END)) == NULL){return NULL;}
    (regexp->status)--;
    regexp_str++;
  }else{
    check_node_size(regexp, 1);
    int backref;
    if((backref = reg_backref_index(regexp_str)) > 0){
      /* このバックリファレンスが有効なものであるか確かめる
       * 遷移表を前へ検索していき、対応するサブマッチがあればOK
       */
      reg_submatch_t *target = regexp->match_object.submatch_top + backref;
      reg_node_t *node;
      for(node = regexp->list.end - 1; node >= regexp->list.top; node--){
        if(node->transit == go_with_end_mark && node->info == target){break;}
      }
      if(node < regexp->list.top){regexp->status = REG_ERR_C_IREGAL_BACKREF; return NULL;}
      regexp->list.end->info = target;
      regexp->list.end->transit = equal_backref;
    }else{
      /* 文字の場合 */
      regexp->list.end->info = regexp_str;
      regexp->list.end->transit = equal;
    }
    regexp->list.end++;
    if((regexp_str = after_token(regexp_str, &(regexp->status))) == NULL){return NULL;}
  }
  
  /* 繰り返し指定の判別
   * 最小値、最大値、よくばりモードについて検証
   */
  int min, max;
  boolean greedy = TRUE;
  if((*regexp_str == ZERO_OR_ONE) || 
        (*regexp_str == ZERO_TO_ANY) ||
        (*regexp_str == ONE_TO_ANY) ||
        (*regexp_str == MIN_MAX_START)){
    switch(*regexp_str){
      case ZERO_OR_ONE: min = 0; max = 1;         break;
      case ZERO_TO_ANY: min = 0; max = UNLIMITED; break;
      case ONE_TO_ANY:  min = 1; max = UNLIMITED; break;
      case MIN_MAX_START:{
        int *ref = &min;
        min = max = 0;
        while(*(++regexp_str) != MIN_MAX_END){
          if(*regexp_str == MIN_MAX_SEPARATOR){
            if(ref == &min){ref = &max; continue;}
            else{
              regexp->status = REG_ERR_C_IREGAL_LOOP_NUMBER;
              return NULL;
            }
          }
          int digit;
          if((digit = *regexp_str - '0') * (*regexp_str - '9') > 0){
            regexp->status = REG_ERR_C_IREGAL_LOOP_NUMBER;
            return NULL;
          }
          *ref = (*ref * 10) + digit;
        }
        if(max == 0){max = ((ref == &max) ? UNLIMITED : min);}
        break;
        }
    }
    if(*(++regexp_str) == NON_GREEDY){
      greedy = FALSE;
      regexp_str++;
    }
  }else{min = max = 1;}
  
  /* 繰り返し指定の処理
   * 次のようにマッピングを行う
   * 
   * 正規表現トークン{min}
   * if(max == UNLIMITED){
   *   + (正規表現トークン jump_go[=> before])
   * }else{
   *   + (go_jump[=> next] 正規表現トークン){max - min}
   * }
   * 
   * [=> hoge] hogeはjump先
   * non_greedyの場合にはgo_jumpとjump_goを入れ替える。
   */
  int element_size = regexp->list.end - pre;
  int copy = 1;
  if(min == 0){
    check_node_size(regexp, 1);
    duplicate(pre + 1, pre, element_size);
    regexp->list.end++;
  }else{
    check_node_size(regexp, element_size * (min - copy));
    for(; copy < min; copy++){
      duplicate(regexp->list.end, pre, element_size);
      regexp->list.end += element_size;
    }
  }
  
  reg_node_t *min_top = regexp->list.end - element_size;
  
  if(mark){
    check_node_size(regexp, 2);
    duplicate(min_top + 1, min_top, element_size);
    min_top->transit = go_with_start_mark;
    (++(regexp->list.end))->transit = go_with_end_mark;
    min_top->info = ((regexp->list.end)++)->info = mark;
    element_size += 2;
  }
  
  if(max == UNLIMITED){
    if(min == 0){
      pre->transit = jump;
      pre->info = regexp->list.end;
    }
    check_node_size(regexp, 1);
    regexp->list.end->transit = (greedy ? jump_go : go_jump);
    regexp->list.end->info = regexp->list.end - element_size;
    regexp->list.end++;
  }else{
    check_node_size(regexp, (element_size + 1) * (max - copy));
    reg_node_t *next;
    if(min == 0){
      pre->transit = (greedy ? go_jump : jump_go);
      pre->info = next = regexp->list.end + (element_size + 1) * (max - 1);
    }else{
      next = regexp->list.end + (element_size + 1) * (max - min);
    }
    for(; copy < max; copy++){
      regexp->list.end->transit = (greedy ? go_jump : jump_go);
      regexp->list.end->info = next;
      regexp->list.end++;
      duplicate(regexp->list.end, min_top, element_size);
      regexp->list.end += element_size;
    }
  }
  
  return regexp_str;
}

#undef UNLIMITED

/**
 * 1つの節を処理します。
 * 1つの節とは同じ階層レベル(例えばグルーピングなどで括弧で囲まれた中など)の正規表現文字列のことです。
 * 
 * @param regexp コンパイル済み遷移ノードを格納する先
 * @param regexp_str 正規表現文字列
 * @param exit_char 終端文字
 * @return 次の文字、コンパイル中にエラーが起きた場合はNULL
 */
static char *parse_one_phrase(regexp_t *regexp, char *regexp_str, char exit_char){
  
  /* 階層に入ってすぐNULL文字だったら変だ
   */
  if(*regexp_str == NULL){
    regexp->status = REG_ERR_C_TOO_FEW_CHARACTERS;
    return NULL;
  }
  
  reg_node_t *top = regexp->list.end;
  while(regexp_str = parse_and_next(regexp, regexp_str)){
    if(*regexp_str == REGEXP_OR){
      check_node_size(regexp, 2);
      duplicate(top + 1, top, regexp->list.end - top);
      reg_node_t *end = ++(regexp->list.end);
      regexp->list.end++;
      top->transit = go_jump;
      top->info = regexp->list.end;
      if((regexp_str = parse_one_phrase(regexp, regexp_str + 1, exit_char)) == NULL){break;}
      end->transit = jump;
      end->info = regexp->list.end;
      return regexp_str;
    }else if(*regexp_str == exit_char){
      return regexp_str;
    }else if(*regexp_str == NULL_CHAR){
      regexp->status = REG_ERR_C_TOO_FEW_PARENTHESIS;
      break;
    }
  }
  
  return NULL;
}

/**
 * 正規表現文字列をコンパイルして遷移表にします。
 * 
 * @param regexp コンパイル済み遷移ノードを格納する先
 * @param regexp_str 正規表現文字列
 * @param コンパイル済み遷移ノード列の先頭、コンパイル中にエラーが起きた場合はNULL
 */
regexp_t *reg_compile(regexp_t *regexp, char *regexp_str){
  
  regexp->list.end = regexp->list.top;
  regexp->match_object.submatch_end = regexp->match_object.submatch_top;
  regexp->status = 0;
  
  reg_node_t *top = regexp->list.end++;
  top->transit = go_with_start_mark;
  top->info = regexp->match_object.submatch_end++;
  if(parse_one_phrase(regexp, regexp_str, NULL_CHAR) == NULL){return NULL;}
  
  check_node_size(regexp, 1);
  regexp->list.end->transit = go_with_end_mark;
  regexp->list.end->info = top->info;
  regexp->list.end++;
  
  reg_match_t *match_object = &(regexp->match_object);
  int submatch_size = match_object->submatch_end - match_object->submatch_top;
  check_node_size(regexp, submatch_size * 2 + 1);
  reg_node_t *submatch_node = regexp->list.end + 1;
  int index;
  for(index = 0; index < submatch_size; index++){
    submatch_node->transit = invoked_by_submatch_start_node;
    submatch_node->info = (void *)(match_object->submatch_top + index);
    (match_object->submatch_top + index)->start = submatch_node++;
    submatch_node->transit = invoked_by_submatch_end_node;
    submatch_node->info = (void *)(match_object->submatch_top + index);
    (match_object->submatch_top + index)->end = submatch_node++;
  }
  
  return regexp;
}

/* コンパイルに関わる処理 */

/**
 * コンパイルの前処理をします。
 * コンパイルされた情報を格納する先の指定などを行います。
 * 
 * @param regexp 正規表現
 * @param node 格納先ノード
 * @param node_max ノード最大サイズ
 * @param submatch 格納先サブマッチ
 * @param submatch_max サブマッチ最大サイズ
 * @return regexp
 */
regexp_t *reg_before_compile(regexp_t *regexp,
                             reg_node_t *node, int node_max,
                             reg_submatch_t *submatch, int submatch_max){
 
  regexp->match_object.submatch_top = submatch;
  regexp->match_object.submatch_max = submatch_max;
  
  regexp->list.top = node;
  regexp->list.max = node_max;
  
  return regexp;
}

/* デバック用 */

/**
 * 遷移ノード情報をダンプします。
 * 
 * @param node 遷移ノード
 */
void reg_node_dump(reg_node_t *node){
  printf("NODE_ID:\t%d\n", node);
  char *type = "undefined";
  char info_type = 'N';
  if(node->transit == go){type = "go";}
  else if(node->transit == jump){type = "jump"; info_type = 'J';}
  else if(node->transit == go_jump){type = "go_jump"; info_type = 'J';}
  else if(node->transit == jump_go){type = "jump_go"; info_type = 'J';}
  else if(node->transit == equal){type = "equal"; info_type = 'S';}
  else if(node->transit == go_with_start_mark){type = "start_mark"; info_type = 'T';}
  else if(node->transit == go_with_end_mark){type = "end_mark"; info_type = 'T';}
  printf("TYPE:\t%s\n", type);
  switch(info_type){
    case 'N': break;
    case 'J': printf("JUMP:\t%d\n", node->info);   break;
    case 'S': printf("STRING:\t%s\n", node->info); break;
    case 'T': printf("TARGET:\t%d\n", node->info); break;
  }
  printf("\n");
}

#ifdef __cplusplus
};
#endif