token_store.c

   1 /*
   2  * smatch/token_store.c
   3  *
   4  * Copyright (C) 2012 Oracle.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include <string.h>
  13 #include "lib.h"
  14 #include "parse.h"
  15 #include "allocate.h"
  16
  17 struct line {
  18         struct position pos;
  19         struct line *prev;
  20         struct token *token;
  21         struct line *next;
  22 };
  23
  24 __ALLOCATOR(struct token, "token store", perm_token);
  25 ALLOCATOR(line, "line of tokens");
  26
  27 static struct token *copy_token(struct token *token)
  28 {
  29         struct token *new;
  30
  31         new = __alloc_perm_token(0);
  32         memcpy(new, token, sizeof(*token));
  33         new->next = NULL;
  34         return new;
  35 }
  36
  37 static struct line *cursor;
  38
  39 static void find_line(struct position pos)
  40 {
  41         if (!cursor)
  42                 return;
  43         if (pos.line == cursor->pos.line)
  44                 return;
  45         if (pos.line < cursor->pos.line) {
  46                 if (!cursor->prev)
  47                         return;
  48                 cursor = cursor->prev;
  49                 find_line(pos);
  50                 return;
  51         }
  52         if (!cursor->next)
  53                 return;
  54         if (pos.line < cursor->next->pos.line)
  55                 return;
  56         cursor = cursor->next;
  57         find_line(pos);
  58 }
  59
  60 static void insert_into_line(struct token **current, struct token *new)
  61 {
  62         if (!*current) {
  63                 *current = new;
  64                 return;
  65         }
  66
  67         if (new->pos.pos < (*current)->pos.pos) {
  68                 new->next = *current;
  69                 *current = new;
  70                 return;
  71         }
  72
  73         if (new->pos.pos == (*current)->pos.pos)
  74                 return;
  75
  76         insert_into_line(&(*current)->next, new);
  77 }
  78
  79 static void store_token(struct token *token)
  80 {
  81         token = copy_token(token);
  82
  83         find_line(token->pos);
  84
  85         if (!cursor) {
  86                 cursor = __alloc_line(0);
  87                 cursor->pos = token->pos;
  88                 cursor->token = token;
  89                 return;
  90         }
  91
  92         if (token->pos.line < cursor->pos.line) {
  93                 cursor->prev = __alloc_line(0);
  94                 cursor->prev->next = cursor;
  95                 cursor = cursor->prev;
  96                 cursor->pos = token->pos;
  97                 cursor->token = token;
  98                 return;
  99         }
 100
 101         if (token->pos.line == cursor->pos.line) {
 102                 insert_into_line(&cursor->token, token);
 103                 return;
 104         }
 105
 106         cursor->next = __alloc_line(0);
 107         cursor->next->prev = cursor;
 108         cursor = cursor->next;
 109         cursor->pos = token->pos;
 110         cursor->token = token;
 111 }
 112
 113 void store_all_tokens(struct token *token)
 114 {
 115         while (token_type(token) != TOKEN_STREAMEND) {
 116                 store_token(token);
 117                 token = token->next;
 118         }
 119 }
 120
 121 struct token *first_token_from_line(struct position pos)
 122 {
 123         find_line(pos);
 124
 125         if (!cursor)
 126                 return NULL;
 127
 128         if (cursor->pos.stream != pos.stream)
 129                 return NULL;
 130         if (cursor->pos.line != pos.line)
 131                 return NULL;
 132
 133         return cursor->token;
 134 }
 135
 136 struct token *pos_get_token(struct position pos)
 137 {
 138         struct token *token;
 139
 140         token = first_token_from_line(pos);
 141         while (token) {
 142                 if (pos.pos == token->pos.pos)
 143                         return token;
 144                 if (pos.pos < token->pos.pos)
 145                         return NULL;
 146                 token = token->next;
 147         }
 148         return NULL;
 149 }
 150
 151 char *pos_ident(struct position pos)
 152 {
 153         struct token *token;
 154
 155         token = pos_get_token(pos);
 156         if (!token)
 157                 return NULL;
 158         if (token_type(token) != TOKEN_IDENT)
 159                 return NULL;
 160         return token->ident->name;
 161 }
 162