aoc-2022/day_7/parser.y

/* Require bison minimal version */
%require "3.2"

/* write out a header file containing the token defines */
%header

// Code for the header file generated by bison
%code requires {
    #include "filetree.h"

    typedef void* yyscan_t;

    struct dirstack {
        struct dirstack *next;
        struct dirnode *item;
    };

    struct parser_state {
        struct dirnode *root;
        struct dirnode *cur;

        /// models the current directory stack we're in for simplicity
        struct dirstack *stackptr;
    };

    struct dirstack* dirstack_push(struct dirstack *stack, struct dirnode *item);
    struct dirstack* dirstack_pop(struct dirstack *stack);
}

// Code for the c file
%{
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "parser.h"
    #include "lexer.h"

    const unsigned long upper_bound = 100000;
    const unsigned long fs_size = 70000000;
    const unsigned long needed_space = 30000000;

    struct dirstack* dirstack_push(struct dirstack *stack, struct dirnode *item) {
        struct dirstack *head = calloc(1, sizeof(struct dirstack));
        if (!head) {
            fprintf(stderr, "\033[91m[error] Ran out of memory\033[0m\n");
            return NULL;
        }

        head->item = item;
        head->next = stack;

        return head;
    }

    struct dirstack* dirstack_pop(struct dirstack *stack) {
        if (!stack) {
            fprintf(stderr, "\033[91m[error] Called `dirstack_pop on an empty stack\033[0m\n");
            return NULL;
        }
        
        struct dirstack *next_item = stack->next;
        free(stack);

        return next_item;
    }

    void yyerror(struct parser_state* state, yyscan_t scanner, const char* msg) {
        (void)state;
        (void)scanner;
        fprintf(stderr, "\033[93mSyntax Error: %s\033[0m\n", msg);
    }
%}

// define a reentrant parser
%define api.pure

// enable parser tracing and detailed error messages (plus Lookahead Correction)
%define parse.trace
%define parse.error detailed
%define parse.lac full

%lex-param   { yyscan_t scanner }
%parse-param { struct parser_state* state }
%parse-param { yyscan_t scanner }

%union {
    char *path;
    unsigned long num;
}

%start input
%token NEWLINE SPACE
%token PROMPT CHDIR LIST
%token ROOT PARENT DIRECTORY
%token <path> PATHSPEC
%token <num> SIZE
%term END_OF_FILE

%%

input
    : command input
    | END_OF_FILE   { return 0; }
    ;

command
    : PROMPT CHDIR SPACE ROOT NEWLINE       {
                                                while (state->stackptr->next) {
                                                    state->stackptr = dirstack_pop(state->stackptr);
                                                }
                                                state->cur = state->stackptr->item;
                                            }
    | PROMPT CHDIR SPACE PARENT NEWLINE     {
                                                state->stackptr = dirstack_pop(state->stackptr);
                                                state->cur = state->stackptr->item;
                                            }
    | PROMPT CHDIR SPACE PATHSPEC NEWLINE   {
                                                // printf("searching in %s now for path %s\n", state->cur->name, $4);
                                                    
                                                // move into the new directory (creating it if it doesn't exist is not necessary, LIST does that)
                                                struct dirnode *cur_node = state->cur;
                                                // search for the directory name
                                                size_t found = 0;
                                                int c = -1;
                                                size_t i;
                                                for (i = 0; i < cur_node->num_dirs; i++) {
                                                    if (strcmp($4, cur_node->directories[i]->name) == 0) {
                                                        found = i;
                                                        c = 0;
                                                        // printf("equal: [%s] and [%s]\n", $4, cur_node->directories[i]->name);
                                                    } else {
                                                        // printf("not equal: [%s] and [%s]\n", $4, cur_node->directories[i]->name);
                                                    }
                                                }

                                                if (c == -1) {
                                                    fprintf(stderr, "\033[91m[error] got no such directory lol\033[0m\n");
                                                    // TODO: error, directory not found
                                                } // else {
                                                    // printf("found it\n");
                                                // }

                                                struct dirnode *next = cur_node->directories[found];

                                                // actually move into the new directory
                                                state->stackptr = dirstack_push(state->stackptr, next);
                                                state->cur = next;
                                            }
    | PROMPT LIST NEWLINE output
    | NEWLINE
    ;

output
    : listing NEWLINE output
    |
    ;

listing
    : DIRECTORY SPACE PATHSPEC  {
                                    struct dirnode *item = calloc(1, sizeof(struct dirnode));
                                    if (!item) {
                                        // TODO: error handling
                                    }

                                    item->name = $3;

                                    add_directory(state->cur, item);
                                }
    | SIZE SPACE PATHSPEC       {
                                    struct filenode *item = calloc(1, sizeof(struct filenode));
                                    if (!item) {
                                        // TODO: error handling
                                    }

                                    item->name = $3;
                                    item->size = $1;

                                    add_file(state->cur, item);
                                }
    ;

%%


unsigned long sum_and_count(struct dirnode *node) {
    unsigned long total_sum = 0;

    for (size_t i = 0; i < node->num_files; i++) {
        node->size += node->files[i]->size;
    }

    for (size_t j = 0; j < node->num_dirs; j++) {
        // recursively call function on subdirectory to compute its size
        total_sum += sum_and_count(node->directories[j]);
        node->size += node->directories[j]->size;
    }

    if (node->size <= upper_bound) {
        total_sum += node->size;
    }

    return total_sum;
}


struct dirnode* find_deletion_candidate(struct dirnode *cur, unsigned long needed_space) {
    if (cur->size < needed_space) {
        // abort recursion if directory sizes get too small
        return NULL;
    }

    struct dirnode *best_candidate = cur;
    unsigned long best_diff = best_candidate->size - needed_space;

    for (size_t i = 0; i < cur->num_dirs; i++) {
        struct dirnode *candidate = find_deletion_candidate(cur->directories[i], needed_space);
        // only proceed if there's an actual candidate
        if (candidate) {
            unsigned long delta = candidate->size - needed_space;
            if (delta < best_diff) {
                best_candidate = candidate;
                best_diff = delta;
            }
        }
    }

    return best_candidate;
}


int main(void) {
    struct dirnode *root = calloc(1, sizeof(struct dirnode));
    if (!root) {
        fprintf(stderr, "\033[91m[error] Ran out of memory\033[0m\n");
        return EXIT_FAILURE;
    }
    root->name = "/\0";

    struct dirstack *stack_ptr = dirstack_push(NULL, root);

    struct parser_state *state = calloc(1, sizeof(struct parser_state));
    if (!state) {
        fprintf(stderr, "\033[91m[error] Ran out of memory\033[0m\n");
        return EXIT_FAILURE;
    }
    state->root = root;
    state->cur = root;
    state->stackptr = stack_ptr;


    yyscan_t scanner;
    if (yylex_init(&scanner)) {
        fprintf(stderr, "\033[91m[error] Could not initialize lexer\033[0m\n");
        return EXIT_FAILURE;
    }

    if (yyparse(state, scanner)) {
		// TODO: Error handling https://www.gnu.org/software/bison/manual/html_node/Parser-Function.html
		// error during parse occured
		return EXIT_FAILURE;
	}

    yylex_destroy(scanner);

    // task 1
    unsigned long sum_of_sizes = sum_and_count(root);
    printf("The sum of all directory sizes < %zu is: %zu\n", upper_bound, sum_of_sizes);

    // task 2
    unsigned long free_space = fs_size - root->size;
    unsigned long to_clear = needed_space - free_space;

    printf("------------------------------------------------\n");
    printf("Total Disk Space Available: %zu\n", fs_size);
    printf("Total Disk Space Used:      %zu\n", root->size);
    printf("Free Disk Space:            %zu\n", free_space);
    printf("Required Disk Space:        %zu\n", needed_space);
    printf("------------------------------------------------\n\n");
    printf("Looking to free %zu units\n", to_clear);

    struct dirnode *closest_match = find_deletion_candidate(root, to_clear);

    printf("Recommended deletion candidate: `%s` (size %zu)\n", closest_match->name, closest_match->size);

    return 0;
}