feat: Move auxiliary lines data structure out of token array

3 files changed, 207 insertions, 106 deletions

diff --git a/Makefile b/Makefile
index 107b3c0..dad5b3f 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 .PHONY: check
 
 frontend: main.c
-	clang -g -Og -O0 -Wall -Werror -pedantic -Wextra -std=c99 -lc main.c -o frontend
+	clang -g -Og -O0 -Wall -Werror -pedantic -Wextra -std=c99 -I/usr/include main.c -o frontend
 
 check: frontend
 	clang-tidy -checks=*,-google-readability-todo,-cert-err33-c,-llvmlibc-restrict-system-libc-headers,-altera-*,altera-struct-pack-align -p . main.c -- -std=c99
diff --git a/main.c b/main.c
index 0723531..4ffc5dc 100644
--- a/main.c
+++ b/main.c
@@ -5,14 +5,26 @@
 #include <stdlib.h>
 #include <string.h>
 
+#define Array(t) Array_Named(t, t)
+#define Array_Named(t, name)                                                   \
+  typedef struct name {                                                        \
+    isize length;                                                              \
+    t elements[];                                                              \
+  } name##_t
+
+Array_Named(i32, line_offsets);
+// Array_Named(i8, bytes);
+
 // Location in the source file
 typedef struct Location {
   // Offset in file of the first character
-  i32 line;
+  u32 offset;
+  // Line number (zero indexed)
+  u32 line;
   // Offset on the line of the first character
-  u16 column;
+  u32 column;
   // Length in bytes
-  u16 size;
+  u32 size;
 } Location_t;
 
 typedef struct Token {
@@ -24,50 +36,62 @@ typedef struct Token {
     t_divide,
     t_add,
     t_subtract,
-    t_whitespace,
+    t_space,
+    t_tab,
     t_newline,
     t_number,
   } type;
 
-  // Offset(s) in the buffer where the token occurs.
-  // If type is t_size, then location is an i64 "size" -- only used to store the
-  // number of tokens.
-  // If type is t_newline, then location is a Location_t line, where `line`
-  // holds the offset into the text buffer where the newline is located, column
-  // holds the line number,
-  // and size holds the length of the line.
-  union {
-    Location_t location;
-    Location_t line;
-    i64 size;
-  } location;
+  Location_t pos;
 } Token_t;
 
-// #define Location_to_i64(location) \
-//   (i64)(((i64)location.line << 32) | (location.column << 16) | location.size)
-// #define i64_to_Location(long_int) \
-//   (Location_t) { \
-//     .line = (long_int >> 32), .column = (long_int >> 16) & ((1 << 16) - 1), \
-//     .size = long_int & ((1 << 16) - 1), \
-//   }
+Array_Named(Token_t, TokenList);
+
+typedef struct AExp {
+  enum AExpType {
+    e_error,
+    e_mul,
+    e_div,
+    e_add,
+    e_sub,
+    e_number,
+  } type;
+
+  union {
+    i32 number;
+    struct AExp* e_unary;
+    struct {
+      struct AExp* a;
+      struct AExp* b;
+    } e_binary;
+  } data;
 
-// Should also add helper structure with pointers to each line
+  // Token_t* t;
+} AExp_t;
 
-static usize f_read(FILE* stream, char** dst);
-static usize f_size(FILE* stream);
-static void l_print_token(Token_t token, Location_t** lines, char* text);
-static Location_t** l_read(char const* text, usize text_length, Token_t** dst);
+static usize f_read(FILE* restrict stream, char** restrict dst);
+static usize f_size(FILE* restrict stream);
+static void l_print_token(Token_t token, char* restrict text);
+static line_offsets_t* l_read(char const* restrict text, usize text_length,
+                              TokenList_t** restrict dst);
+static AExp_t* p_arith(char const* restrict text, TokenList_t* restrict tokens);
+static AExp_t p_number(char const* restrict text, Token_t* restrict tnum);
 
 int
 main(int argc, char* argv[]) {
   if (argc == 2) {
-    FILE* srcfile        = NULL;
-    char* contents       = NULL;
-    usize content_length = 0;
-    Token_t* tokens      = NULL;
-    Location_t** lines   = NULL;
+    FILE* srcfile         = NULL;
+    // pointer to a buffer holding the raw bytes of the file
+    char* contents        = NULL;
+    // length of contents
+    usize content_length  = 0;
+    // tokens, parsed by l_read
+    TokenList_t* tokens   = NULL;
+    // auxilliary structure to keep track of the lines, used for debugging
+    // -- maybe turn off with a flag?
+    line_offsets_t* lines = NULL;
 
-    srcfile              = fopen(argv[1], "re");
+    srcfile               = fopen(argv[1], "re");
     if (srcfile == NULL) {
       fprintf(stdout, "! Failed to open file: %s\n", argv[1]);
     }
@@ -88,10 +112,42 @@ main(int argc, char* argv[]) {
     }
 
     if (lines != NULL) {
-      const i64 num_tokens = tokens[0].location.size;
+      const isize num_tokens = tokens->length;
       printf("%ld tokens\n", num_tokens);
       for (int tokenidx = 0; tokenidx < num_tokens; tokenidx++) {
-        l_print_token(tokens[tokenidx], lines, contents);
+        l_print_token(tokens->elements[tokenidx], contents);
+      }
+
+      AExp_t* expression = p_arith(contents, tokens);
+      printf("ast:\n");
+      i16 indentation = 0;
+      for (int tokenidx = 0; tokenidx < num_tokens; tokenidx++) {
+        switch (expression[tokenidx].type) {
+        case e_mul:
+          printf("%*s*\n", indentation, " ");
+          indentation++;
+          break;
+        case e_div:
+          printf("%*s/\n", indentation, " ");
+          indentation++;
+          break;
+        case e_add:
+          printf("%*s+\n", indentation, " ");
+          indentation++;
+          break;
+        case e_sub:
+          printf("%*s-\n", indentation, " ");
+          indentation++;
+          break;
+        case e_number:
+          printf("%*d\n", indentation, expression[tokenidx].data.number);
+          indentation--;
+          break;
+        case e_error:
+        default:
+          printf("%*s\n", indentation, "error: invalid token");
+          break;
+        }
       }
     }
 
@@ -116,7 +172,7 @@ main(int argc, char* argv[]) {
  * @error  returns -1 on error.
  */
 static usize
-f_read(FILE* stream, char** dst) {
+f_read(FILE* restrict stream, char** restrict dst) {
   usize file_sz = f_size(stream);
 
   if (dst == NULL) {
@@ -151,7 +207,7 @@ f_read(FILE* stream, char** dst) {
  * @error  Returns -1 on error.
  */
 static usize
-f_size(FILE* stream) {
+f_size(FILE* restrict stream) {
   // Could ftell and rewind to previous position, but scratch that
   i64 size  = -1;
   i32 error = fseek(stream, 0, SEEK_END);
@@ -176,10 +232,10 @@ f_size(FILE* stream) {
 }
 
 static void
-l_print_token(Token_t token, Location_t* lines[], char* text) {
-  fprintf(stdout, "[%d,%d:%d]", token.location.location.line + 1,
-          token.location.location.column + 1, token.location.location.size);
+l_print_token(Token_t token, char* restrict text) {
 
+  fprintf(stdout, "[%4d] %2d:%d-%d  ", token.pos.offset, token.pos.line,
+          token.pos.column, token.pos.size);
   switch (token.type) {
   case t_error:
     fputs(" error ", stdout);
@@ -201,13 +257,17 @@ l_print_token(Token_t token, Location_t* lines[], char* text) {
     break;
   case t_number:
     fputs("number:", stdout);
-    Location_t* line = lines[token.location.location.line];
-    fwrite(&text[line->line + token.location.location.column],
-           token.location.location.size, sizeof(char), stdout);
+    fwrite(&text[token.pos.offset], token.pos.size, sizeof(char), stdout);
+    break;
+  case t_space:
+    fprintf(stdout, "space:%d", token.pos.size);
+    break;
+  case t_tab:
+    fprintf(stdout, "tab:%d", token.pos.size);
     break;
   case t_newline:
-    fprintf(stdout, "\\n offset:%d line:%d length:%d", token.location.line.line,
-            token.location.line.column, token.location.line.size);
+    fprintf(stdout, "\\n offset:%d line:%d column:%d length:%d",
+            token.pos.offset, token.pos.line, token.pos.column, token.pos.size);
     break;
   default:
     break;
@@ -221,43 +281,44 @@ l_print_token(Token_t token, Location_t* lines[], char* text) {
  * @return a pointer to dst
  * @error  Returns NULL on error.
  */
-static Location_t**
-l_read(char const* text, usize text_length, Token_t** dst) {
-  Location_t** lines = NULL;
+static line_offsets_t*
+l_read(char const* restrict text, usize text_length,
+       TokenList_t** restrict dst) {
+  line_offsets_t* lines = NULL;
   if (dst == NULL) {
     fprintf(stderr, "dst is NULL");
   }
+
   if (text_length > 0 && dst != NULL && *dst == NULL) {
-    *dst = (Token_t*)malloc(text_length * sizeof(Token_t));
+    // upper bound of tokens must be equal to text_length
+    *dst  = (TokenList_t*)malloc(sizeof(isize) + text_length * sizeof(Token_t));
+    lines = (line_offsets_t*)malloc(sizeof(isize) + text_length * sizeof(i32));
   }
 
   if (text_length > 0 && dst != NULL && *dst == NULL) {
-    fprintf(stderr, "! Failed to allocate %ld bytes\n",
-            text_length * sizeof(Token_t));
+    fprintf(stderr, "! Failed to allocate %ld bytes for `dst`\n",
+            sizeof(isize) + text_length * sizeof(Token_t));
+  }
+
+  if (text_length > 0 && dst != NULL && lines == NULL) {
+    fprintf(stderr, "! Failed to allocate %ld bytes for `lines`\n",
+            sizeof(isize) + text_length * sizeof(i32));
   }
 
-  if (text_length > 0 && dst != NULL && *dst != NULL) {
-    // Offset in text (used for location.line and line.column  -- the lineno if
-    // token==newline)
-    usize offset                  = 0;
-    // Column counter
-    u16 column                    = 0;
-    // Line number
-    i32 lineno                    = 0;
+  if (text_length > 0 && dst != NULL && *dst != NULL && lines != NULL) {
     // Token counter
-    isize tokenno                 = 2;
+    isize tokenno                 = 0;
     i32 error                     = 0;
     enum TokenType token_previous = t_error;
     enum TokenType token          = t_error;
 
-    (*dst)[1].type                = t_newline;
-    Location_t* line_current      = &(*dst)[1].location.line;
-    line_current->line            = 0;
-    line_current->column          = lineno;
-    line_current->size            = 0;
+    Location_t cursor;
+    cursor.line   = 0;
+    cursor.column = 1;
+    cursor.size   = 0;
 
     do {
-      switch (text[offset]) {
+      switch (text[cursor.offset]) {
         //    case t_size:
         // break;
       case '*':
@@ -290,8 +351,11 @@ l_read(char const* text, usize text_length, Token_t** dst) {
         break;
 
       case ' ':
+        token = t_space;
+        break;
+
       case '\t':
-        token = t_whitespace;
+        token = t_tab;
         break;
 
       case '\n':
@@ -304,51 +368,88 @@ l_read(char const* text, usize text_length, Token_t** dst) {
         break;
       }
 
-      if (token == t_newline) {
-        lineno++;
-        line_current->size                   = column;
-        (*dst)[tokenno].type                 = token;
-        (*dst)[tokenno].location.line.line   = (i32)(offset + 1);
-        (*dst)[tokenno].location.line.column = lineno;
-        (*dst)[tokenno].location.line.size   = 0;
+      if (token == token_previous) {
+        (*dst)->elements[tokenno - 1].pos.size = ++cursor.size;
+      }
 
-        line_current                         = &(*dst)[tokenno].location.line;
-        column                               = 0;
-        tokenno++;
-        token_previous = token;
-      } else if (token == token_previous) {
-        (*dst)[tokenno - 1].location.location.size++;
-        column++;
-      } else {
-        (*dst)[tokenno].type                     = token;
-        (*dst)[tokenno].location.location.line   = lineno;
-        (*dst)[tokenno].location.location.column = column;
-        (*dst)[tokenno].location.location.size   = 1;
-        column++;
+      // if (token == t_newline && token == token_previous) {
+      //   cursor.size                    = 1;
+
+      //  (*dst)->elements[tokenno].type = token;
+      //  (*dst)->elements[tokenno].pos  = cursor;
+
+      //  token_previous = token;
+      //}
+
+      if (token != token_previous) {
+        cursor.size                    = 1;
+
+        (*dst)->elements[tokenno].type = token;
+        (*dst)->elements[tokenno].pos  = cursor;
         tokenno++;
         token_previous = token;
       }
 
-      offset++;
-    } while (!error && offset < text_length && offset < INT_MAX);
+      if (token == t_newline) {
+        lines->elements[cursor.line] = cursor.offset;
+        cursor.line++;
+        cursor.column = 0;
+      }
 
-    (*dst)[0].type          = t_size;
-    (*dst)[0].location.size = tokenno;
+      cursor.offset++;
+      cursor.column++;
+    } while (!error && cursor.offset < text_length && cursor.offset < INT_MAX);
 
-    if ((*dst)[tokenno - 1].type != t_newline) {
-      lineno++;
-      line_current->size = column;
-    }
+    (*dst)->length = tokenno;
+    lines->length  = cursor.line;
 
-    lines        = (Location_t**)malloc(sizeof(Location_t*) * (lineno + 1));
-    i32 line_idx = 0;
-    for (int tokenidx = 0; tokenidx < tokenno; tokenidx++) {
-      if ((*dst)[tokenidx].type == t_newline) {
-        lines[line_idx] = &(*dst)[tokenidx].location.line;
-        line_idx++;
-      }
-    }
+    // for (int line = 0; line < lines->length; line++) {
+    //   printf("%d: line:%d\n", line, lines->elements[line]);
+    // }
   }
 
   return lines;
 }
+
+static AExp_t*
+p_arith(char const* restrict text, TokenList_t* restrict tokens) {
+  i64 exp_idx          = 0;
+
+  const i64 num_tokens = tokens->length;
+  AExp_t* expression   = malloc(sizeof(AExp_t) * num_tokens * 2);
+  for (int tokenidx = 0; tokenidx < num_tokens; tokenidx++) {
+    if (tokens->elements[tokenidx].type == t_multiply) {
+      expression[exp_idx] = (AExp_t){.type = e_mul};
+      exp_idx++;
+    } else if (tokens->elements[tokenidx].type == t_add) {
+      expression[exp_idx] = (AExp_t){.type = e_add};
+      exp_idx++;
+    } else if (tokens->elements[tokenidx].type == t_number) {
+      expression[exp_idx] = p_number(text, &tokens->elements[tokenidx]);
+      exp_idx++;
+    } else if (tokens->elements[tokenidx].type == t_newline)
+      continue;
+    else if (tokens->elements[tokenidx].type == t_space)
+      continue;
+    // else
+    //   break;
+  }
+  return expression;
+}
+
+static AExp_t
+p_number(char const* restrict text, Token_t* restrict tnum) {
+
+  i32 number  = 0;
+  char* start = (char*)&text[tnum->pos.offset];
+  for (u32 i = 0; i < tnum->pos.size; i++) {
+    number *= 10;
+    number += (*start - '0');
+    start++;
+  }
+
+  return (AExp_t){
+    .type        = e_number,
+    .data.number = number,
+  };
+}
diff --git a/program.input b/program.input
index 45fd4cb..b3f56aa 100644
--- a/program.input
+++ b/program.input
@@ -1,3 +1,3 @@
 2   + 22 * 2
 
-1337 * 2
\ No newline at end of file
+1337 * 2