implementations/uvm-ncc/parser.c

   1 #include <uvm/syscalls.h>
   2 #include <string.h>
   3
   4
   5
   6
   7
   8 //
   9 // Simple cons list.
  10 //
  11
  12 #define HEAP_SIZE 1024
  13 u32 heads[HEAP_SIZE];
  14 u32 tails[HEAP_SIZE];
  15 u32 free = 1;  // cell 0 is reserved so that 0 can be the empty list.
  16 #define TYPE_OF(pointer) (pointer >> 30)
  17 #define VALUE_OF(pointer) (pointer & 0x3fffffff)
  18 #define JOY_VALUE(type, value) ((type & 3) << 30) | (value & 0x3fffffff)
  19 u32 empty_list = 0;
  20 u8 joyList = 0;
  21 u8 joyInt = 1;
  22 u8 joySymbol = 2;
  23 u8 joyBool = 3;
  24 u32
  25 cons(u32 head, u32 tail)
  26 {
  27         if (free >= HEAP_SIZE)
  28                 return -1;
  29         heads[free] = head;
  30         tails[free] = tail;
  31         u32 cell = JOY_VALUE(joyList, free);
  32         ++free;
  33         return cell;
  34 }
  35 u32 head(u32 list) { return heads[VALUE_OF(list)]; }
  36 u32 tail(u32 list) { return tails[VALUE_OF(list)]; }
  37
  38
  39 /*u32 cons(u32 head, u32 tail) { return tail; }*/
  40
  41
  42
  43
  44
  45
  46
  47 // And now for a hash table.
  48 // https://benhoyt.com/writings/hash-table-in-c/#hash-tables
  49 // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
  50 #define FNV_OFFSET 0xcbf29ce484222325
  51 #define FNV_PRIME 0x100000001b3
  52 u64
  53 hash_key(char* key)
  54 {
  55     u64 hash = FNV_OFFSET;
  56     for (char* p = key; *p; ++p) {
  57         hash = hash ^ (u64)(unsigned char)(*p);
  58         hash = hash * FNV_PRIME;
  59     }
  60     return hash;
  61 }
  62 // Capacity is a power of two (10 for now.)
  63 #define EXPONENT 10
  64 #define CAPACITY 1024
  65 #define HASH_MASK 1023
  66 char* hash_table[CAPACITY];
  67 u32
  68 ht_insert(char *symbol)
  69 {
  70         u64 hash = hash_key(symbol);
  71         u32 index = hash % CAPACITY;
  72
  73         char *candidate = hash_table[index];
  74         if (!candidate) {
  75                 //print_str("interning ");print_str(symbol);print_endl();
  76                 hash_table[index] = symbol;
  77                 return JOY_VALUE(joySymbol, VALUE_OF(hash));
  78         }
  79
  80         // https://en.wikipedia.org/wiki/Double_hashing
  81         // Rather than use another hash function I'm going to try
  82         // using the extra bits of the same hash.
  83         u32 increment = ((VALUE_OF(hash) >> EXPONENT) | 1) % CAPACITY;
  84         // If I understand correctly, making the increment odd
  85         // means it will traverse the whole (even-sized) table.
  86         while (candidate) {
  87                 // Compare pointers then hashes (since we already have
  88                 // one hash I'm guessing that that's cheaper or at least
  89                 // no more expensive than string comparision.)
  90                 if (candidate == symbol || hash == hash_key(candidate))
  91                         break;
  92                 index = (index + increment) % CAPACITY;
  93                 candidate = hash_table[index];
  94         }
  95         if (!candidate) {
  96                 //print_str("interning ");print_str(symbol);print_endl();
  97                 hash_table[index] = symbol;
  98         }
  99         return JOY_VALUE(joySymbol, VALUE_OF(hash));
 100 }
 101 char*
 102 ht_lookup(u32 hash)
 103 {
 104         // Note that hash will be truncated to N (N=30 as it happens) bits
 105         // by VALUE_OF().
 106         u32 index = hash % CAPACITY;
 107         char *candidate = hash_table[index];
 108         u32 increment = ((hash >> EXPONENT) | 1) % CAPACITY;
 109         while (candidate) {
 110                 if (hash == VALUE_OF(hash_key(candidate)))
 111                         return candidate;
 112                 index = (index + increment) % CAPACITY;
 113                 candidate = hash_table[index];
 114         }
 115         /*error = UNKNOWN_WORD_ERROR;*/
 116         return 0;
 117 }
 118
 119
 120
 121
 122
 123
 124
 125 //
 126 // Simple string storage heap.
 127 //
 128 #define STRING_HEAP_SIZE 100000
 129 char string_heap[STRING_HEAP_SIZE];
 130 u32 string_heap_top = 0;
 131 char*
 132 allocate_string(char *buffer, u32 offset, u32 length)
 133 {
 134         u64 end = string_heap_top + length + 1;
 135         if (end >= STRING_HEAP_SIZE)
 136                 return 0;
 137         memcpy(string_heap + string_heap_top, buffer + offset, length);
 138         string_heap[end] = '\0';
 139         u32 new_string = string_heap_top;
 140         string_heap_top = (u32)end + 1;
 141         //print_str("allocating ");print_str(string_heap + new_string);print_endl();
 142         return string_heap + new_string;
 143
 144 }
 145
 146
 147 u32
 148 push_symbol(char *symbol, u32 stack)
 149 {
 150         return cons(JOY_VALUE(joySymbol, ht_insert(symbol)), stack);
 151 }
 152
 153
 154
 155 char* LEFT_BRACKET_symbol = "[";
 156 char* RIGHT_BRACKET_symbol = "]";
 157 u32 LEFT_BRACKET;
 158 u32 RIGHT_BRACKET;
 159
 160 bool
 161 is_integer(char *str, u32 index, u32 length)
 162 {
 163         for (;length; --length) {
 164                 char ch = *(str + index + length - 1);
 165                 if (!(ch == '0'
 166                         || ch == '1'
 167                         || ch == '2'
 168                         || ch == '3'
 169                         || ch == '4'
 170                         || ch == '5'
 171                         || ch == '6'
 172                         || ch == '7'
 173                         || ch == '8'
 174                         || ch == '9'))
 175                 {
 176                         return 0;
 177                 }
 178         }
 179         return 1;
 180 }
 181
 182 u32
 183 convert_integer(char *str, u32 index, u32 length)
 184 {
 185         u32 result = 0;
 186         length = length + index;
 187         for (; index < length; ++index) {
 188                 char ch = *(str + index);
 189                 u8 digit = (u8)ch - (u8)'0';
 190                 result = result * 10 + digit;
 191         }
 192         //print_str("converted integer ");print_i64(result);print_endl();
 193         return JOY_VALUE(joyInt, result);
 194 }
 195
 196
 197
 198 u32
 199 tokenate(char *str, u32 index, u32 length)
 200 {
 201         if (4 == length
 202                 && *(str + index) == 't'
 203                 && *(str + index + 1) == 'r'
 204                 && *(str + index + 2) == 'u'
 205                 && *(str + index + 3) == 'e'
 206         ) {
 207                 //print_str("tokenate true");print_endl();
 208                 return JOY_VALUE(joyBool, 1);
 209         }
 210         if (5 == length
 211                 && *(str + index) == 'f'
 212                 && *(str + index + 1) == 'a'
 213                 && *(str + index + 2) == 'l'
 214                 && *(str + index + 3) == 's'
 215                 && *(str + index + 4) == 'e'
 216         ) {
 217                 //print_str("tokenate false");print_endl();
 218                 return JOY_VALUE(joyBool, 0);
 219         }
 220         if (is_integer(str, index, length)) {
 221                 //print_str("tokenate integer");print_endl();
 222                 return convert_integer(str, index, length);
 223         }
 224         // TODO: Convert bools and ints here?
 225         // Use ht_insert to avoid multiple allocations of the same string!
 226         char *token = allocate_string(str, index, length);
 227         if (!token)
 228                 return 0;  // OOM
 229         return JOY_VALUE(joySymbol, ht_insert(token));
 230 }
 231
 232
 233 u32
 234 tokenize0(char *str, u32 str_length, u32 index, u32 acc)
 235 {
 236         if (index >= str_length) {
 237                 //print_i64(index);print_str(" : ");print_str("END tokenize");print_endl();
 238                 //print_i64(acc);print_str("<");print_endl();
 239                 return acc;
 240         }
 241         //print_i64(index);print_str(" : ");print_str(str + index);print_endl();
 242         char ch = str[index];
 243         if ('[' == ch) {
 244                 acc = cons(LEFT_BRACKET, tokenize0(str, str_length, index + 1, acc));
 245                 //print_i64(acc);print_str("<[");print_endl();
 246                 return acc;
 247         }
 248         if (']' == ch) {
 249                 acc = cons(RIGHT_BRACKET, tokenize0(str, str_length, index + 1, acc));
 250                 //print_i64(acc);print_str("<]");print_endl();
 251                 return acc;
 252         }
 253         if (' ' == ch) {
 254                 return tokenize0(str, str_length, index + 1, acc);
 255         }
 256         u32 i = index + 1;
 257         for (; i < str_length; ++i) {
 258                 if (str[i] == '[' || str[i] == ']' || str[i] == ' ') {
 259                         break;
 260                 }
 261         }
 262         // i == str_length OR str[i] is a delimiter char.
 263         return cons(tokenate(str, index, i - index), tokenize0(str, str_length, i, acc));
 264
 265 }
 266
 267
 268 u32
 269 tokenize(char *str)
 270 {
 271         return tokenize0(str, strlen(str), 0, empty_list);
 272 }
 273
 274 u32
 275 rev(u32 el, u32 end)
 276 {
 277         u32 t = tail(el);
 278         tails[el] = end;
 279         if (t) {
 280                 return rev(t, el);
 281         }
 282         return el;
 283 }
 284
 285 u32
 286 reverse_list_in_place(u32 el)
 287 {
 288         if (!el) {  // Empty list.
 289                 return el;
 290         }
 291         u32 t = tail(el);
 292         if (!t) {  // Length-one list.
 293                 return el;
 294         }
 295         // Re-write  tails[el] to point to null
 296         tails[el] = empty_list;
 297         // reverse the tail of this list and prepend it to [el].
 298         return rev(t, el);
 299 }
 300
 301 u32 stack[1000];
 302 u32 stack_top = 0;
 303
 304 u32
 305 text_to_expression(char *str)
 306 {
 307         u32 frame = empty_list;
 308         u32 tokens = tokenize(str);
 309         //print_str("tokens: "); print_joy_list(tokens); print_endl();
 310         //return tokens;
 311         while (tokens) {
 312                 u32 tok = head(tokens);
 313                 tokens = tail(tokens);
 314                 if (LEFT_BRACKET == tok) {
 315                         //print_str("left bracket");print_endl();
 316                         stack[stack_top] = frame;
 317                         ++stack_top;
 318                         frame = empty_list;
 319                         continue;
 320                 }
 321                 if (RIGHT_BRACKET == tok) {
 322                         //print_str("right bracket");print_endl();
 323                         tok = reverse_list_in_place(frame);
 324                         //print_str("new list: "); print_joy_list(tok); print_endl();
 325                         --stack_top;  //  This first!  THEN get the old frame!  D'oh!
 326                         frame = stack[stack_top];
 327                 }
 328                 frame = cons(tok, frame);
 329                 //print_str("t2e frame: "); print_joy_list(frame); print_endl();
 330         }
 331         return reverse_list_in_place(frame);
 332 }
 333
 334
 335 void
 336 print_joy_value(u32 jv)
 337 {
 338         u8 type = TYPE_OF(jv);
 339         if (type == joyInt) {
 340                 print_i64(VALUE_OF(jv));
 341         } else if (type == joyBool) {
 342                 print_str(VALUE_OF(jv) ? "true" : "false");
 343         } else if (type == joyList) {
 344                 print_str("[");
 345                 print_joy_list(jv);
 346                 print_str("]");
 347         } else if (type == joySymbol) {
 348                 char *str = ht_lookup(VALUE_OF(jv));
 349                 /*if (error != NO_ERROR)*/
 350                 /*      return;*/
 351                 print_str(str);
 352         }
 353 }
 354
 355 void
 356 print_joy_list(u32 list)
 357 {
 358         while (list) {
 359                 print_joy_value(head(list));
 360                 list = tail(list);
 361                 if (list) {
 362                         print_str(" ");
 363                 }
 364         }
 365 }
 366
 367 void
 368 main()
 369 {
 370         memset(string_heap, 0, sizeof(string_heap));
 371         LEFT_BRACKET = JOY_VALUE(joySymbol, ht_insert(LEFT_BRACKET_symbol));
 372         RIGHT_BRACKET = JOY_VALUE(joySymbol, ht_insert(RIGHT_BRACKET_symbol));
 373
 374         //char *buffer = " 1[2[ 3  cats ]4] cats dogs bunnies";
 375         char *buffer = " 1[2]3 bunnies";
 376         /*print_str(allocate_string(buffer, 4, 4)); print_endl();*/
 377         /*print_str(allocate_string(buffer, 2, 4)); print_endl();*/
 378         /*print_str(allocate_string(buffer, 7, 5)); print_endl();*/
 379         u32 jv = text_to_expression(" 1[2[true 3][[]]bob]false[]bob 3[4]5");
 380         //jv = reverse_list_in_place(jv);
 381         if (LEFT_BRACKET == jv) {
 382                 print_str("boo");
 383         } else {
 384                 //jv = JOY_VALUE(joyList, jv);
 385                 print_joy_list(jv);
 386         }
 387         print_endl();
 388 }