preprocess.c

#include "preprocess.h"

struct macro_entry *macro_table[MACRO_TABLE_SIZE];

struct pp_list *object_macro_invocation(struct preprocessor *pp, struct macro_entry *macro);
struct pp_list *function_macro_invocation(struct preprocessor *pp, struct macro_entry *macro, struct pp_list **args, int args_size);
int conditional_expression(struct pp_node **node);
void group(struct preprocessor *pp);
void skip_line(struct preprocessor *pp);
void skip_group(struct preprocessor *pp);
struct pp_list *parse_preprocessing_file(unsigned char *file);

// pp_list
struct pp_list *allocate_pp_list() {
  struct pp_list *list = (struct pp_list *) malloc(sizeof(struct pp_list));
  if(list == NULL) {
    perror("malloc");
    exit(1);
  }
  list->head = NULL;
  list->tail = &(list->head);
  return list;
}

void free_pp_list(struct pp_list *list) {
  struct pp_node *node = list->head;
  while(node != NULL) {
    struct pp_node *next = node->next;
    free(node);
    node = next;
  }
  free(list);
}

void append_pp_list(struct pp_list *list, struct pp_token *token) {
  struct pp_node *node = (struct pp_node *) malloc(sizeof(struct pp_node));
  node->token = token;
  node->next = NULL;
  node->skip = 0;
  *(list->tail) = node;
  list->tail = &(node->next);
}

void concat_pp_list(struct pp_list *list1, struct pp_list *list2) {
  if(list2->head != NULL) {
    *(list1->tail) = list2->head;
    list1->tail = list2->tail;
  }
}

// macro_entry
struct macro_entry *allocate_macro_entry() {
  struct macro_entry *macro = (struct macro_entry *) malloc(sizeof(struct macro_entry));
  if(macro == NULL) {
    perror("malloc");
    exit(1);
  }
  macro->replacement_list = allocate_pp_list();
  macro->expanded = 0;
  return macro;
}

void free_macro_entry(struct macro_entry *macro) {
  free_pp_list(macro->replacement_list);
  free(macro);
}

int ident_hash(const unsigned char *ident) {
  const int BASE = 257;
  int h = 0;
  for(int i = 0; ident[i] != '\0'; i++) {
    h = (h * BASE + ident[i]) % MACRO_TABLE_SIZE;
  }
  return h;
}

int compare_macro(const struct macro_entry *macro1, const struct macro_entry *macro2) {
  if(macro1->type != macro2->type) {
    return 0;
  }

  if(macro1->type == MACRO_FUNCTION) {
    if(macro1->parameter_ellipsis != macro2->parameter_ellipsis) return 0;
    if(macro1->parameter_size != macro2->parameter_size) return 0;
    for(int i = 0; i < macro1->parameter_size; i++) {
      if(strcmp(macro1->parameters[i]->head, macro2->parameters[i]->head) != 0) return 0;
    }
  }

  struct pp_node *node1 = macro1->replacement_list->head;
  struct pp_node *node2 = macro2->replacement_list->head;
  while(1) {
    if(node1 == NULL || node2 == NULL) {
      if(node1 == NULL && node2 == NULL) break;
      return 0;
    }
    if(node1->token->type != node2->token->type) return 0;
    if(strcmp(node1->token->text->head, node2->token->text->head) != 0) return 0;
    node1 = node1->next;
    node2 = node2->next;
  }

  return 1;
}

void insert_macro_table(struct macro_entry *macro) {
  int h1 = ident_hash(macro->identifier);
  for(int i = 0, h = h1; i < MACRO_TABLE_SIZE; i++, h = (h + 1) % MACRO_TABLE_SIZE) {
    if(macro_table[h] == NULL) {
      macro_table[h] = macro;
      break;
    } else {
      if(strcmp(macro_table[h]->identifier, macro->identifier) == 0) {
        if(compare_macro(macro_table[h], macro)) {
          break;
        } else {
          error("duplicated macro definition: %s\n", macro->identifier);
        }
      }
    }
  }
}

void delete_macro_table(const unsigned char *identifier) {
  int h1 = ident_hash(identifier);
  for(int i = 0, h = h1; i < MACRO_TABLE_SIZE; i++, h = (h + 1) % MACRO_TABLE_SIZE) {
    if(macro_table[h] == NULL) break;
    if(strcmp(macro_table[h]->identifier, identifier) == 0) {
      macro_table[h] = NULL;
      h = (h + 1) % MACRO_TABLE_SIZE;
      for(int j = i; j < MACRO_TABLE_SIZE; j++, h = (h + 1) % MACRO_TABLE_SIZE) {
        if(macro_table[h] == NULL) break;
        struct macro_entry *t = macro_table[h];
        macro_table[h] = NULL;
        insert_macro_table(t);
      }
      break;
    }
  }
}

struct macro_entry *search_macro_table(const unsigned char *identifier) {
  int h1 = ident_hash(identifier);
  for(int i = 0, h = h1; i < MACRO_TABLE_SIZE; i++, h = (h + 1) % MACRO_TABLE_SIZE) {
    if(macro_table[h] == NULL) break;
    if(strcmp(macro_table[h]->identifier, identifier) == 0) {
      return macro_table[h];
    }
  }
  return NULL;
}

// macro replacement
int check_object_macro_invocation(struct preprocessor *pp, struct pp_node *node) {
  if(node->token->type != PP_IDENT) return 0;
  if(node->skip) return 0;

  struct macro_entry *macro = search_macro_table(node->token->text->head);
  return macro != NULL && !macro->expanded && macro->type == MACRO_OBJECT;
}

int check_function_macro_invocation(struct preprocessor *pp, struct pp_node *node) {
  if(node->token->type != PP_IDENT) return 0;
  if(node->skip) return 0;

  struct macro_entry *macro = search_macro_table(node->token->text->head);
  if(macro == NULL || macro->expanded || macro->type != MACRO_FUNCTION) {
    return 0;
  }

  struct pp_node *current = node->next;
  if(current == NULL) {
    return 0;
  }
  if(current->token->type == PP_NEW_LINE || current->token->type == PP_SPACE) {
    current = current->next;
    if(current == NULL) return 0;
  }
  if(current->token->type != PP_LPAREN) return 0;

  return 1;
}

struct pp_list *scan_macro(struct preprocessor *pp, struct pp_list *list) {
  struct pp_list *result = allocate_pp_list();

  for(struct pp_node *node = list->head; node != NULL; node = node->next) {
    struct macro_entry *macro = search_macro_table(node->token->text->head);

    // object-like macro invocation
    if(check_object_macro_invocation(pp, node)) {
      struct macro_entry *macro = search_macro_table(node->token->text->head);
      struct pp_list *list = object_macro_invocation(pp, macro);
      concat_pp_list(result, list);
    }

    // function-like macro invocation
    else if(check_function_macro_invocation(pp, node)) {
      struct macro_entry *macro = search_macro_table(node->token->text->head);
      struct pp_list *args[MACRO_PARAMS_LIMIT];
      int args_count = 0;
      int level = 0;
      int valid = 0;

      node = node->next;
      if(node->token->type == PP_NEW_LINE || node->token->type == PP_SPACE) {
        node = node->next;
      }
      node = node->next;

      if(node != NULL && (node->token->type == PP_NEW_LINE || node->token->type == PP_SPACE)) {
        node = node->next;
      }

      // parse arguments
      if(node != NULL && node->token->type == PP_RPAREN) {
        valid = 1;
      } else if(node != NULL) {
        args[args_count] = allocate_pp_list();
        if(macro->parameter_size > 0) {
          for(; node != NULL; node = node->next) {
            struct pp_token *token = node->token;
            if(token->type == PP_LPAREN) {
              append_pp_list(args[args_count], token);
              level++;
            } else if(token->type == PP_RPAREN) {
              if(level == 0) {
                args_count++;
                valid = 1;
                break;
              }
              append_pp_list(args[args_count], token);
              level--;
            } else if(level == 0 && token->type == PP_COMMA) {
              args_count++;
              args[args_count] = allocate_pp_list();
              if(args_count == macro->parameter_size) {
                if(macro->parameter_ellipsis && !valid) {
                  node = node->next;
                  break;
                } else {
                  error("too many arguments.\n");
                }
                break;
              }
            } else {
              append_pp_list(args[args_count], node->token);
            }
          }
        }
        if(macro->parameter_ellipsis && !valid) {
          for(; node != NULL; node = node->next) {
            if(node->token->type == PP_RPAREN) {
              break;
            }
            append_pp_list(args[args_count], node->token);
          }
          args_count++;
          valid = 1;
        }
      }

      if(!valid) {
        error("macro arguments list is not terminated.\n");
      }

      for(int i = 0; i < args_count; i++) {
        if(args[i]->head == NULL) {
          continue;
        }
        if(args[i]->head->token->type == PP_NEW_LINE || args[i]->head->token->type == PP_SPACE) {
          args[i]->head = args[i]->head->next;
        }
        if(args[i]->head != NULL) {
          struct pp_node **arg_node = &(args[i]->head);
          for(; (*arg_node)->next != NULL; arg_node = &((*arg_node)->next));
          if((*arg_node)->token->type == PP_NEW_LINE || (*arg_node)->token->type == PP_SPACE) {
            *arg_node = NULL;
          }
        }
      }

      struct pp_list *list = function_macro_invocation(pp, macro, args, args_count);
      concat_pp_list(result, list);
    }

    // not replaced
    else {
      append_pp_list(result, node->token);
    }
  }

  return result;
}

struct pp_list *concat_macro_token(struct pp_list *list) {
  struct pp_list *result = allocate_pp_list();

  for(struct pp_node *node = list->head; node != NULL; node = node->next) {
    struct pp_node *left = node;
    struct pp_node *middle = left->next;
    if(middle != NULL && middle->token->type == PP_SPACE) {
      middle = middle->next;
    }
    struct pp_node *right = middle != NULL ? middle->next : NULL;
    if(right != NULL && right->token->type == PP_SPACE) {
      right = right->next;
    }

    if(middle != NULL && right != NULL && middle->token->type == PP_CONCAT && !middle->token->concat) {
      struct pp_token *l = left->token;
      struct pp_token *r = right->token;

      struct string *str = allocate_string();
      concat_string(str, l->text);
      concat_string(str, r->text);

      struct pp_token_lexer lexer;
      lexer.queue = (struct utf8c *) malloc(sizeof(struct utf8c) * (str->size + 1));
      lexer.queue_head = 0;
      lexer.queue_size = 0;
      lexer.queue_allocate_size = str->size + 1;
      lexer.context = CTX_NORMAL;

      for(int i = 0; i < str->size;) {
        struct utf8c uc;
        uc.bytes = count_bytes(str->head[i]);
        for(int j = 0; j < uc.bytes; j++) {
          uc.sequence[j] = str->head[i++];
        }
        uc.sequence[uc.bytes] = '\0';
        lexer.queue[lexer.queue_size++] = uc;
      }
      lexer.queue[lexer.queue_size++] = ueof;

      struct pp_token *new_token = next_pp_token(&lexer);
      new_token->concat = 1;
      if(lexer.queue_size > 1) {
        error("invalid token concatnation: %s ## %s\n", l->text->head, r->text->head);
      }
      append_pp_list(result, new_token);

      node = right;
    } else {
      append_pp_list(result, node->token);
    }
  }

  // remove place marker
  for(struct pp_node **node = &(result->head); *node != NULL;) {
    if((*node)->token->type == PP_PLACE_MARKER) {
      *node = (*node)->next;
    } else {
      node = &((*node)->next);
    }
  }

  return result;
}

struct pp_list *object_macro_invocation(struct preprocessor *pp, struct macro_entry *macro) {
  macro->expanded = 1;

  struct pp_list *list = allocate_pp_list();
  for(struct pp_node *node = macro->replacement_list->head; node != NULL; node = node->next) {
    append_pp_list(list, node->token);
  }

  struct pp_list *concat_list = concat_macro_token(list);
  struct pp_list *result = scan_macro(pp, concat_list);

  macro->expanded = 0;
  return result;
}

struct pp_list *function_macro_invocation(struct preprocessor *pp, struct macro_entry *macro, struct pp_list **args, int args_size) {
  macro->expanded = 1;

  struct pp_list *replaced_args[MACRO_PARAMS_LIMIT];
  for(int i = 0; i < args_size; i++) {
    if(args[i]->head != NULL) {
      replaced_args[i] = scan_macro(pp, args[i]);
    } else {
      struct pp_token *place_marker = allocate_pp_token();
      place_marker->type = PP_PLACE_MARKER;
      place_marker->name = pp_token_name[PP_PLACE_MARKER];

      replaced_args[i] = allocate_pp_list();
      append_pp_list(replaced_args[i], place_marker);

      append_pp_list(args[i], place_marker);
    }
  }

  struct pp_list *list = allocate_pp_list();
  for(struct pp_node *node = macro->replacement_list->head; node != NULL; node = node->next) {
    if(node->token->type == PP_SHARP) {
      node = node->next;
      if(node->token->type == PP_SPACE) {
        node = node->next;
      }

      int matched;
      for(int i = 0; i < args_size; i++) {
        if(node->token->type == PP_IDENT && strcmp(node->token->text->head, macro->parameters[i]->head) == 0) {
          matched = i;
        }
      }

      struct pp_token *new_token = allocate_pp_token();
      new_token->type = PP_STR;
      new_token->name = pp_token_name[PP_STR];
      append_string(new_token->text, '"');
      for(struct pp_node *arg_node = args[matched]->head; arg_node != NULL; arg_node = arg_node->next) {
        for(int i = 0; i < arg_node->token->text->size; i++) {
          unsigned char c = arg_node->token->text->head[i];
          if(c == '\\' || c == '"') {
            append_string(new_token->text, '\\');
          }
          append_string(new_token->text, c);
        }
      }
      append_string(new_token->text, '"');
      append_pp_list(list, new_token);

      continue;
    }

    struct pp_node *left = node;
    struct pp_node *middle = left->next;
    if(middle != NULL && middle->token->type == PP_SPACE) {
      middle = middle->next;
    }
    struct pp_node *right = middle != NULL ? middle->next : NULL;
    if(right != NULL && right->token->type == PP_SPACE) {
      right = right->next;
    }
    if(middle != NULL && middle->token->type == PP_CONCAT && !middle->token->concat) {
      int left_replaced = 0;
      for(int i = 0; i < args_size; i++) {
        if(left->token->type == PP_IDENT && strcmp(left->token->text->head, macro->parameters[i]->head) == 0) {
          for(struct pp_node *arg_node = args[i]->head; arg_node != NULL; arg_node = arg_node->next) {
            append_pp_list(list, arg_node->token);
          }
          left_replaced = 1;
          break;
        }
      }
      if(!left_replaced) {
        append_pp_list(list, left->token);
      }
      if(left->next != middle) {
        append_pp_list(list, left->next->token);
      }
      append_pp_list(list, middle->token);
      if(middle->next != right) {
        append_pp_list(list, middle->next->token);
      }
      int right_replaced = 0;
      for(int i = 0; i < args_size; i++) {
        if(right->token->type == PP_IDENT && strcmp(right->token->text->head, macro->parameters[i]->head) == 0) {
          for(struct pp_node *arg_node = args[i]->head; arg_node != NULL; arg_node = arg_node->next) {
            append_pp_list(list, arg_node->token);
          }
          right_replaced = 1;
          break;
        }
      }
      if(!right_replaced) {
        append_pp_list(list, right->token);
      }
      node = right;
      continue;
    }

    int replaced = 0;
    for(int i = 0; i < args_size; i++) {
      if(node->token->type == PP_IDENT && strcmp(node->token->text->head, macro->parameters[i]->head) == 0) {
        for(struct pp_node *arg_node = replaced_args[i]->head; arg_node != NULL; arg_node = arg_node->next) {
          append_pp_list(list, arg_node->token);
        }
        replaced = 1;
        break;
      }
    }

    if(!replaced) {
      append_pp_list(list, node->token);
    }
  }

  struct pp_list *concat_list = concat_macro_token(list);
  struct pp_list *result = scan_macro(pp, concat_list);

  macro->expanded = 0;
  return result;
}

// preprocessor
struct pp_token *peek_pp_token(struct preprocessor *pp) {
  if(pp->token_queue_size == 0) {
    pp->token_queue[pp->token_queue_size++] = next_pp_token(pp->lexer);
  }
  return pp->token_queue[0];
}

struct pp_token *read_pp_token(struct preprocessor *pp) {
  if(pp->token_queue_size == 0) {
    pp->token_queue[pp->token_queue_size++] = next_pp_token(pp->lexer);
  }
  return pp->token_queue[--pp->token_queue_size];
}

int check_pp_token(struct preprocessor *pp, enum pp_token_type type) {
  return peek_pp_token(pp)->type == type;
}

int check_keyword(struct preprocessor *pp, char *text) {
  struct pp_token *token = peek_pp_token(pp);
  return token->type == PP_IDENT && strcmp(token->text->head, text) == 0;
}

void skip_pp_token(struct preprocessor *pp) {
  struct pp_token *token = read_pp_token(pp);
  free_pp_token(token);
}

void remove_white_space(struct preprocessor *pp) {
  if(check_pp_token(pp, PP_SPACE)) skip_pp_token(pp);
}

struct pp_token *expect_pp_token(struct preprocessor *pp, enum pp_token_type type) {
  struct pp_token *token = read_pp_token(pp);
  if(token->type != type) error("%s is expected.\n", pp_token_name[type]);
  return token;
}

void discard_new_line(struct preprocessor *pp) {
  struct pp_token *token = expect_pp_token(pp, PP_NEW_LINE);
  free_pp_token(token);
}

struct pp_token *read_pp_token_with_space(struct preprocessor *pp) {
  struct pp_token *token = read_pp_token(pp);
  remove_white_space(pp);
  return token;
}

void skip_pp_token_with_space(struct preprocessor *pp) {
  struct pp_token *token = read_pp_token(pp);
  free_pp_token(token);
  remove_white_space(pp);
}

#define unexpected_pp_token(pp) { \
  struct pp_token *token = read_pp_token(pp); \
  error("unexpected preprocessing token: %s.", pp_token_name[token->type]); \
}

// if_directive
int primary_expression(struct pp_node **node) {
  if((*node)->token->type == PP_NUM) {
    int value = 0;
    int base = 10;
    unsigned char *s = (*node)->token->text->head;
    for(int i = 0; i < (*node)->token->text->size; i++) {
      char c = s[i];
      if(i == 0 && c == '0') {
        base = 8;
      }
      if(i == 1 && (c == 'x' || c == 'X') && base == 8) {
        base = 16;
        break;
      }
      if(c == 'l' || c == 'L') break;
      if(base == 10) {
        if('0' <= c && c <= '9') {
          value = value * 10 + (c - '0');
        } else {
          error("invalid integer constant: \"%s\"\n", (*node)->token->text->head);
        }
      } else if(base == 8) {
        if('0' <= c && c <= '7') {
          value = value * 8 + (c - '0');
        } else {
          error("invalid integer constant: \"%s\"\n", (*node)->token->text->head);
        }
      } else if(base == 16) {
        if('0' <= c && c <= '9') {
          value = value * 16 + (c - '0');
        } else if('a' <= c && c <= 'f') {
          value = value * 16 + (c - 'a' + 10);
        } else if('A' <= c && c <= 'F') {
          value = value * 16 + (c - 'A' + 10);
        } else {
          error("invalid integer constant: \"%s\"\n", (*node)->token->text->head);
        }
      }
    }
    *node = (*node)->next;
    return value;
  } else if((*node)->token->type == PP_CHAR) {
    int value = (*node)->token->text->head[0];
    *node = (*node)->next;
    return value;
  } else if((*node)->token->type == PP_LPAREN) {
    *node = (*node)->next;
    int value = conditional_expression(node);
    *node = (*node)->next;
    return value;
  }
  error("invalid integer constant expression: %s\n", (*node)->token->text->head);
}

int unary_expression(struct pp_node **node) {
  if((*node)->token->type == PP_PLUS) {
    *node = (*node)->next;
    return +primary_expression(node);
  } else if((*node)->token->type == PP_MINUS) {
    *node = (*node)->next;
    return -primary_expression(node);
  } else if((*node)->token->type == PP_TILDE) {
    *node = (*node)->next;
    return ~primary_expression(node);
  } else if((*node)->token->type == PP_NOT) {
    *node = (*node)->next;
    return !primary_expression(node);
  }
  return primary_expression(node);
}

int multiplicative_expression(struct pp_node **node) {
  int result = unary_expression(node);
  while((*node) && ((*node)->token->type == PP_MUL || (*node)->token->type == PP_DIV || (*node)->token->type == PP_MOD)) {
    enum pp_token_type type = (*node)->token->type;
    *node = (*node)->next;
    int value = unary_expression(node);
    if(type == PP_MUL) {
      result = result * value;
    } else if(type == PP_DIV) {
      result = result / value;
    } else if(type == PP_MOD) {
      result = result % value;
    }
  }
  return result;
}

int additive_expression(struct pp_node **node) {
  int result = multiplicative_expression(node);
  while((*node) && ((*node)->token->type == PP_PLUS || (*node)->token->type == PP_MINUS)) {
    enum pp_token_type type = (*node)->token->type;
    *node = (*node)->next;
    int value = multiplicative_expression(node);
    if(type == PP_PLUS) {
      result = result + value;
    } else if(value == PP_MINUS) {
      result = result - value;
    }
  }
  return result;
}

int shift_expression(struct pp_node **node) {
  int result = additive_expression(node);
  while((*node) && ((*node)->token->type == PP_LSHIFT || (*node)->token->type == PP_RSHIFT)) {
    enum pp_token_type type = (*node)->token->type;
    *node = (*node)->next;
    int value = additive_expression(node);
    if(type == PP_LSHIFT) {
      result = result << value;
    } else if(type == PP_RSHIFT) {
      result = result >> value;
    }
  }
  return result;
}

int relational_expression(struct pp_node **node) {
  int result = shift_expression(node);
  while((*node) && ((*node)->token->type == PP_LT || (*node)->token->type == PP_GT || (*node)->token->type == PP_LTE || (*node)->token->type == PP_GTE)) {
    enum pp_token_type type = (*node)->token->type;
    *node = (*node)->next;
    int value = shift_expression(node);
    if(type == PP_LT) {
      result = result < value;
    } else if(type == PP_GT) {
      result = result > value;
    } else if(type == PP_LTE) {
      result = result <= value;
    } else if(type == PP_GTE) {
      result = result >= value;
    }
  }
  return result;
}

int equality_expression(struct pp_node **node) {
  int result = relational_expression(node);
  while((*node) && ((*node)->token->type == PP_EQ || (*node)->token->type == PP_NEQ)) {
    enum pp_token_type type = (*node)->token->type;
    *node = (*node)->next;
    int value = relational_expression(node);
    if(type == PP_EQ) {
      result = result == value;
    } else if(type == PP_NEQ) {
      result = result == value;
    }
  }
  return result;
}

int and_expression(struct pp_node **node) {
  int result = equality_expression(node);
  while((*node) && (*node)->token->type == PP_AND) {
    *node = (*node)->next;
    int value = equality_expression(node);
    result = result & value;
  }
  return result;
}

int exclusive_or_expression(struct pp_node **node) {
  int result = and_expression(node);
  while((*node) && (*node)->token->type == PP_XOR) {
    *node = (*node)->next;
    int value = and_expression(node);
    result = result ^ value;
  }
  return result;
}

int inclusive_or_expression(struct pp_node **node) {
  int result = exclusive_or_expression(node);
  while((*node) && (*node)->token->type == PP_OR) {
    *node = (*node)->next;
    int value = exclusive_or_expression(node);
    result = result | value;
  }
  return result;
}

int logical_and_expression(struct pp_node **node) {
  int result = inclusive_or_expression(node);
  while((*node) && (*node)->token->type == PP_LAND) {
    *node = (*node)->next;
    int value = inclusive_or_expression(node);
    result = result && value;
  }
  return result;
}

int logical_or_expression(struct pp_node **node) {
  int result = logical_and_expression(node);
  while((*node) && (*node)->token->type == PP_LOR) {
    *node = (*node)->next;
    int value = logical_and_expression(node);
    result = result || value;
  }
  return result;
}

int conditional_expression(struct pp_node **node) {
  int result = logical_or_expression(node);
  if((*node) && (*node)->token->type == PP_QUESTION) {
    *node = (*node)->next;
    int left = conditional_expression(node);
    *node = (*node)->next;
    int right = conditional_expression(node);
    result = result ? left : right;
  }
  return result;
}

struct pp_node *check_defined_operator(struct pp_node **node) {
  struct pp_node *ident;

  *node = (*node)->next;
  if((*node)->token->type == PP_SPACE) {
    *node = (*node)->next;
  }

  if((*node)->token->type == PP_IDENT) {
    ident = *node;
  } else if((*node)->token->type == PP_LPAREN) {
    *node = (*node)->next;
    if((*node)->token->type == PP_SPACE) {
      *node = (*node)->next;
    }

    if((*node)->token->type == PP_IDENT) {
      ident = *node;
      *node = (*node)->next;

      if((*node)->token->type != PP_RPAREN) {
        error("%s is expected.\n", pp_token_name[PP_RPAREN]);
      }
    } else {
      error("%s is expected.\n", pp_token_name[PP_IDENT]);
    }
  } else {
    error("%s or %s is expected.\n", pp_token_name[PP_IDENT], pp_token_name[PP_RPAREN]);
  }

  return ident;
}

int if_control(struct preprocessor *pp) {
  struct pp_list *list = allocate_pp_list();
  while(!check_pp_token(pp, PP_NEW_LINE)) {
    struct pp_token *token = read_pp_token(pp);
    append_pp_list(list, token);
  }
  discard_new_line(pp);

  for(struct pp_node *node = list->head; node != NULL; node = node->next) {
    if(node->token->type == PP_IDENT && strcmp(node->token->text->head, "defined") == 0) {
      struct pp_node *ident = check_defined_operator(&node);
      ident->skip = 1;
    }
  }

  list = scan_macro(pp, list);

  struct pp_token *zero = allocate_pp_token();
  zero->type = PP_NUM;
  zero->name = pp_token_name[PP_NUM];
  append_string(zero->text, '0');

  struct pp_token *one = allocate_pp_token();
  one->type = PP_NUM;
  one->name = pp_token_name[PP_NUM];
  append_string(one->text, '1');

  struct pp_list *replaced = allocate_pp_list();
  for(struct pp_node *node = list->head; node != NULL; node = node->next) {
    if(node->token->type == PP_IDENT && strcmp(node->token->text->head, "defined") == 0) {
      struct pp_node *ident = check_defined_operator(&node);
      struct macro_entry *macro = search_macro_table(ident->token->text->head);
      append_pp_list(replaced, macro == NULL ? zero : one);
    } else {
      append_pp_list(replaced, node->token->type != PP_IDENT ? node->token : zero);
    }
  }

  for(struct pp_node **node = &(replaced->head); *node != NULL;) {
    if((*node)->token->type == PP_SPACE || (*node)->token->type == PP_SPACE) {
      *node = (*node)->next;
    } else {
       node = &((*node)->next);
    }
  }

  return conditional_expression(&(replaced->head));
}

void conditional_include(struct preprocessor *pp, int condition) {
  if(condition) group(pp);
  else skip_group(pp);
}

int if_directive(struct preprocessor *pp) {
  skip_pp_token_with_space(pp);

  int control = if_control(pp);
  conditional_include(pp, control);

  return control;
}

int ifdef_directive(struct preprocessor *pp) {
  skip_pp_token_with_space(pp);

  struct pp_token *ident = expect_pp_token(pp, PP_IDENT);
  discard_new_line(pp);

  struct macro_entry *macro = search_macro_table(ident->text->head);
  int control = macro != NULL;
  conditional_include(pp, control);

  return control;
}

int ifndef_directive(struct preprocessor *pp) {
  skip_pp_token_with_space(pp);

  struct pp_token *ident = expect_pp_token(pp, PP_IDENT);
  discard_new_line(pp);

  struct macro_entry *macro = search_macro_table(ident->text->head);
  int control = macro == NULL;
  conditional_include(pp, control);

  return control;
}

int elif_directive(struct preprocessor *pp, int skip) {
  skip_pp_token_with_space(pp);

  int control = if_control(pp);
  conditional_include(pp, !skip && control);

  return skip || control;
}

void else_directive(struct preprocessor *pp, int skip) {
  skip_pp_token_with_space(pp);
  discard_new_line(pp);

  conditional_include(pp, !skip);
}

void endif_directive(struct preprocessor *pp) {
  skip_pp_token_with_space(pp);
  discard_new_line(pp);
}

void if_section(struct preprocessor *pp) {
  int skip;

  if(check_keyword(pp, "if")) {
    skip = if_directive(pp);
  } else if(check_keyword(pp, "ifdef")) {
    skip = ifdef_directive(pp);
  } else if(check_keyword(pp, "ifndef")) {
    skip = ifndef_directive(pp);
  }

  while(check_keyword(pp, "elif")) {
    skip = elif_directive(pp, skip);
  }

  if(check_keyword(pp, "else")) {
    else_directive(pp, skip);
  }

  if(check_keyword(pp, "endif")) {
    endif_directive(pp);
  } else {
    error("#endif directive is missing.\n");
  }
}

// include directive
int try_fopen(char *file) {
  FILE *fp = fopen(file, "r");

  if(fp == NULL) return 0;

  fclose(fp);
  return 1;
}

struct string *search_header_file(struct string *text) {
  char location[4][64] = {
    "/usr/lib/gcc/x86_64-linux-gnu/7/include/",
    "/usr/include/",
    "/usr/include/linux/",
    "/usr/include/x86_64-linux-gnu/"
  };

  for(int k = 0; k < 4; k++) {
    struct string *path = allocate_string();
    write_string(path, location[k]);
    for(int i = 1; i < text->size - 1; i++) {
      append_string(path, text->head[i]);
    }

    if(try_fopen(path->head)) return path;

    free_string(path);
  }

  // failed to search header file
  return NULL;
}

struct string *search_named_source_file(struct string *text, const char *current_file) {
  int last_slash = 0;
  for(int i = 0; current_file[i]; i++) {
    if(current_file[i] == '/') {
      last_slash = i;
    }
  }

  struct string *dir = allocate_string();
  if(last_slash > 0) {
    for(int i = 0; i < last_slash; i++) {
      append_string(dir, current_file[i]);
    }
    append_string(dir, '/');
  }

  struct string *path = allocate_string();
  concat_string(path, dir);
  for(int i = 1; i < text->size - 1; i++) {
    append_string(path, text->head[i]);
  }

  if(try_fopen(path->head)) {
    return path;
  }

  free_string(path);

  // reprocess as if header file was read
  return search_header_file(text);
}

void include_directive(struct preprocessor *pp) {
  struct pp_token *header;
  if(peek_pp_token(pp)->type == PP_H_NAME) {
    header = read_pp_token(pp);
  } else {
    error("macro-replaced include directive is not implemented yet.\n");
  }
  discard_new_line(pp);

  struct string *path;
  if(header->type == PP_H_NAME && header->text->head[0] == '<') {
    path = search_header_file(header->text);
  } else if(header->type == PP_H_NAME && header->text->head[0] == '"') {
    path = search_named_source_file(header->text, pp->lexer->src->file);
  }

  if(path == NULL) {
    error("failed to search include file\n");
  }

  struct pp_list *list = parse_preprocessing_file(path->head);
  concat_pp_list(pp->list, list);
}

// define, undef directive
int check_parameter(struct macro_entry *macro, struct pp_token *token) {
  int parameter_size = macro->parameter_size;
  if(macro->parameter_ellipsis) parameter_size++;

  if(token->type == PP_IDENT) {
    for(int i = 0; i < parameter_size; i++) {
      if(strcmp(token->text->head, macro->parameters[i]->head) == 0) {
        return 1;
      }
    }
  }

  return 0;
}

int check_stringify_operator(struct macro_entry *macro) {
  struct pp_list *list = macro->replacement_list;

  for(struct pp_node *node = list->head; node != NULL; node = node->next) {
    if(node->token->type == PP_SHARP) {
      struct pp_node *target = node->next;

      if(target == NULL) return 0;
      if(target->token->type == PP_SPACE) target = target->next;
      if(!check_parameter(macro, target->token)) return 0;

      node = target;
    }
  }

  return 1;
}

int check_concat_operator(struct macro_entry *macro) {
  struct pp_list *list = macro->replacement_list;

  for(struct pp_node *node = list->head; node != NULL; node = node->next) {
    if(node->token->type == PP_CONCAT) {
      if(node == list->head) return 0;
      if(node->next == NULL) return 0;
    }
  }

  return 1;
}

void define_directive(struct preprocessor *pp) {
  struct macro_entry *macro = allocate_macro_entry();

  macro->identifier = expect_pp_token(pp, PP_IDENT)->text->head;

  if(check_pp_token(pp, PP_SPACE) || check_pp_token(pp, PP_NEW_LINE)) {
    macro->type = MACRO_OBJECT;
    remove_white_space(pp);
  } else if(check_pp_token(pp, PP_LPAREN)) {
    macro->type = MACRO_FUNCTION;
    macro->parameter_size = 0;

    skip_pp_token_with_space(pp);

    if(check_pp_token(pp, PP_RPAREN)) {
      macro->parameter_ellipsis = 0;
      skip_pp_token_with_space(pp);
    } else {
      while(1) {
        if(check_pp_token(pp, PP_IDENT)) {
          if(macro->parameter_size == MACRO_PARAMS_LIMIT) {
            error("too many macro parameters.\n");
          }

          struct pp_token *token = read_pp_token_with_space(pp);
          macro->parameters[macro->parameter_size++] = token->text;

          if(check_pp_token(pp, PP_COMMA)) {
            skip_pp_token_with_space(pp);
          } else if(check_pp_token(pp, PP_RPAREN)) {
            macro->parameter_ellipsis = 0;
            skip_pp_token_with_space(pp);
            break;
          } else {
            unexpected_pp_token(pp);
          }
        } else if(check_pp_token(pp, PP_ELLIPSIS)) {
          skip_pp_token_with_space(pp);

          struct string *va_args = allocate_string();
          write_string(va_args, "__VA_ARGS__");
          macro->parameters[macro->parameter_size] = va_args;
          macro->parameter_ellipsis = 1;

          if(check_pp_token(pp, PP_RPAREN)) {
            skip_pp_token_with_space(pp);
            break;
          } else {
            unexpected_pp_token(pp);
          }
        }
        else {
          unexpected_pp_token(pp);
        }
      }
    }
  } else {
    unexpected_pp_token(pp);
  }

  while(!check_pp_token(pp, PP_NEW_LINE)) {
    struct pp_token *token = read_pp_token(pp);
    append_pp_list(macro->replacement_list, token);
  }

  discard_new_line(pp);

  if(macro->type == MACRO_FUNCTION && !check_stringify_operator(macro)) {
    error("invalid # operator.\n");
  }
  if(!check_concat_operator(macro)) {
    error("invalid ## operator.\n");
  }

  insert_macro_table(macro);
}

void undef_directive(struct preprocessor *pp) {
  struct pp_token *ident = expect_pp_token(pp, PP_IDENT);
  discard_new_line(pp);
  delete_macro_table(ident->text->head);
}

// text line
void parse_text_line(struct preprocessor *pp) {
  struct pp_list *text = allocate_pp_list();

  while(1) {
    struct pp_token *token = read_pp_token(pp);
    append_pp_list(text, token);
    if(token->type == PP_NEW_LINE) {
      struct pp_token *next = peek_pp_token(pp);
      if(next->type == PP_SHARP || next->type == PP_NONE) {
        break;
      }
    }
  }

  struct pp_list *replaced = scan_macro(pp, text);
  concat_pp_list(pp->list, replaced);
}

// group
int check_if_section(struct preprocessor *pp) {
  if(check_keyword(pp, "if")) return 1;
  if(check_keyword(pp, "ifdef")) return 1;
  if(check_keyword(pp, "ifndef")) return 1;
  return 0;
}

int check_group_end(struct preprocessor *pp) {
  if(check_keyword(pp, "elif")) return 1;
  if(check_keyword(pp, "else")) return 1;
  if(check_keyword(pp, "endif")) return 1;
  return 0;
}

void group(struct preprocessor *pp) {
  while(!check_pp_token(pp, PP_NONE)) {
    if(check_pp_token(pp, PP_SHARP)) {
      skip_pp_token_with_space(pp);

      if(check_if_section(pp)) {
        if_section(pp);
      } else if(check_group_end(pp)) {
        break;
      } else if(check_keyword(pp, "include")) {
        skip_pp_token_with_space(pp);
        include_directive(pp);
      } else if(check_keyword(pp, "define")) {
        skip_pp_token_with_space(pp);
        define_directive(pp);
      } else if(check_keyword(pp, "undef")) {
        skip_pp_token_with_space(pp);
        undef_directive(pp);
      } else if(check_keyword(pp, "line")) {
        warning("#line directive is not implemented yet.\n");
        skip_line(pp);
      } else if(check_keyword(pp, "error")) {
        warning("#error directive is not implemented yet.\n");
        skip_line(pp);
      } else if(check_keyword(pp, "pragma")) {
        warning("#pragma directive is not implemented yet.\n");
        skip_line(pp);
      } else if(check_pp_token(pp, PP_SPACE)) {
        skip_line(pp);
      } else {
        struct pp_token *directive = read_pp_token(pp);
        error("unknown directive: \"#%s\".\n", directive->text->head);
      }
    } else {
      parse_text_line(pp);
    }
  }
}

void skip_line(struct preprocessor *pp) {
  while(1) {
    struct pp_token *token = read_pp_token(pp);
    if(token->type == PP_NEW_LINE) break;
  }
}

void skip_group(struct preprocessor *pp) {
  while(peek_pp_token(pp)->type != PP_NONE) {
    if(peek_pp_token(pp)->type == PP_SHARP) {
      read_pp_token_with_space(pp);

      if(check_if_section(pp)) {
        skip_line(pp);
        skip_group(pp);
        while(check_keyword(pp, "elif")) {
          skip_line(pp);
          skip_group(pp);
        }
        if(check_keyword(pp, "else")) {
          skip_line(pp);
          skip_group(pp);
        }
        if(check_keyword(pp, "endif")) {
          skip_line(pp);
        }
      } else if(check_group_end(pp)) {
        break;
      } else {
        skip_line(pp);
      }
    } else {
      skip_line(pp);
    }
  }
}

struct pp_list *parse_preprocessing_file(unsigned char *file) {
  struct preprocessor pp;
  pp.lexer = allocate_pp_token_lexer(file);
  pp.token_queue_size = 0;
  pp.list = allocate_pp_list();

  group(&pp);

  if(!check_pp_token(&pp, PP_NONE)) {
    if(check_keyword(&pp, "elif")) {
      error("invalid #elif directive appeared.\n");
    } else if(check_keyword(&pp, "else")) {
      error("invalid #else directive appeared.\n");
    } else if(check_keyword(&pp, "endif")) {
      error("invalid #endif directive appeared.\n");
    }
  }

  return pp.list;
}

struct pp_list *preprocess(unsigned char *file) {
  struct macro_entry *arch = allocate_macro_entry();
  arch->identifier = "__x86_64__";
  insert_macro_table(arch);

  struct pp_list *list = parse_preprocessing_file(file);

  for(int i = 0; i < MACRO_TABLE_SIZE; i++) {
    if(macro_table[i] != NULL) {
      free_macro_entry(macro_table[i]);
    }
  }

  return list;
}