; Module      : LLVM backend - list implementation
; Description : Contains our list implementation - based on a linked list (and in fact
;               uses the same data structures as our linked stack).
; Maintainers : Tilman Blumenbach et al.
; License     : MIT
;
; Lists are implemented as linked lists of stack_wrapper elements, i. e. just like our
; normal linked stack. The data type "list" is represented as a stack_element with type
; 1 and a data pointer pointing to the head of the aforementioned stack_wrapper linked list.
; Thus, an empty list is a stack_element with type 1 and a null data pointer.


; Types

; Types defined in linked_stack.ll.
%stack_element = type opaque
%stack_wrapper = type opaque


; External declarations

; Own external LLVM variables/functions
declare %stack_element* @stack_element_new(i8, i8*)
declare void @stack_element_unref(%stack_element*)
declare void @stack_element_set_data(%stack_element*, i8*)
declare i8* @stack_element_get_data(%stack_element*)
declare %stack_wrapper* @stack_wrapper_new(%stack_element*, %stack_wrapper*)
declare void @stack_wrapper_free(%stack_wrapper*)
declare %stack_element* @stack_wrapper_get_element(%stack_wrapper*)
declare %stack_wrapper* @stack_wrapper_get_next(%stack_wrapper*)
declare void @push_struct(%stack_element*)
declare %stack_element* @pop_struct()
declare void @stack_element_assert_type(%stack_element*, i8)
declare void @stack_element_assert_is_non_empty_list(%stack_element*)
declare i1 @do_equal(%stack_element* %struct_a, %stack_element*)


; Function definitions

; Create a new, empty list (also called "nil") with a refcount of 1.
define %stack_element* @list_new() {
    ; Type 1 is reserved for the "list" type.
    ; Empty lists are simply stack_element structs with a null data pointer.
    %elm = call %stack_element* @stack_element_new(i8 1, i8* null)
    ret %stack_element* %elm
}

; Decrement the refcount of each element of a list.
;
; This does not free the stack_element which holds the list itself.
; That one is free'd by stack_element_unref().
define void @list_unref_elements(%stack_element* %list) {
top:
    %head_wrapper0 = call i8* @stack_element_get_data(%stack_element* %list)
    %head_wrapper1 = bitcast i8* %head_wrapper0 to %stack_wrapper*
    br label %free_list_elements

free_list_elements:
    %curr_wrapper = phi %stack_wrapper* [ %head_wrapper1, %top ], [ %next_wrapper, %free_one_list_element ]

    %is_null = icmp eq %stack_wrapper* %curr_wrapper, null
    br i1 %is_null, label %done, label %free_one_list_element

free_one_list_element:
    %next_wrapper = call %stack_wrapper* @stack_wrapper_get_next(%stack_wrapper* %curr_wrapper)
    %elm = call %stack_element* @stack_wrapper_get_element(%stack_wrapper* %curr_wrapper)
    call void @stack_element_unref(%stack_element* %elm)
    call void @stack_wrapper_free(%stack_wrapper* %curr_wrapper)

    br label %free_list_elements

done:
    ; Nothing to do since the list is empty.
    ret void
}

; Prepend a stack_element to a list (also called "cons").
;
; Returns its first parameter.
define %stack_element* @list_prepend(%stack_element* %list, %stack_element* %element) {
    ; A list contains a stack_wrapper as its data. This is the wrapped head of the list.
    %head_wrapper0 = call i8* @stack_element_get_data(%stack_element* %list)
    %head_wrapper1 = bitcast i8* %head_wrapper0 to %stack_wrapper*

    ; Now create a new wrapper for the element we want to prepend.
    %new_head_wrapper = call %stack_wrapper* @stack_wrapper_new(%stack_element* %element, %stack_wrapper* %head_wrapper1)

    ; This is the new list head, so store it in the topmost stack_element.
    %data = bitcast %stack_wrapper* %new_head_wrapper to i8*
    call void @stack_element_set_data(%stack_element* %list, i8* %data)

    ; That's it!
    ret %stack_element* %list
}

; Pop the head off a non-empty list.
define %stack_element* @list_pop(%stack_element* %list) {
    ; Get the top stack_wrapper of the list.
    %head_wrapper0 = call i8* @stack_element_get_data(%stack_element* %list)
    %head_wrapper1 = bitcast i8* %head_wrapper0 to %stack_wrapper*

    ; Get the contents of the wrapper.
    %top_elm = call %stack_element* @stack_wrapper_get_element(%stack_wrapper* %head_wrapper1)

    ; What's the new head of the list?
    %new_head0 = call %stack_wrapper* @stack_wrapper_get_next(%stack_wrapper* %head_wrapper1)
    %new_head1 = bitcast %stack_wrapper* %new_head0 to i8*
    call void @stack_element_set_data(%stack_element* %list, i8* %new_head1)

    ; Now we can free the old topmost wrapper.
    call void @stack_wrapper_free(%stack_wrapper* %head_wrapper1)

    ; That's it!
    ret %stack_element* %top_elm
}

; Compare two lists.
;
; Returns 1 if both lists are equal or 0 otherwise.
;
; Crashes the program on errors (prints an appropriate error message).
define i1 @list_equal(%stack_element* %list_a, %stack_element* %list_b) {
top:
    ; Get the top stack_wrappers of both lists.
    %head_wrapper_a0 = call i8* @stack_element_get_data(%stack_element* %list_a)
    %head_wrapper_a1 = bitcast i8* %head_wrapper_a0 to %stack_wrapper*

    %head_wrapper_b0 = call i8* @stack_element_get_data(%stack_element* %list_b)
    %head_wrapper_b1 = bitcast i8* %head_wrapper_b0 to %stack_wrapper*

    br label %compare_lists

compare_lists:
    %curr_wrapper_a = phi %stack_wrapper* [ %head_wrapper_a1, %top ], [ %next_wrapper_a, %compare_elements ]
    %curr_wrapper_b = phi %stack_wrapper* [ %head_wrapper_b1, %top ], [ %next_wrapper_b, %compare_elements ]

    ; If at least one wrapper is null, we may either have reached the end
    ; of BOTH lists (which means that they are equal) or one list is shorter
    ; than the other, which means that they are NOT equal.
    %wrapper_a_is_null = icmp eq %stack_wrapper* %curr_wrapper_a, null
    %wrapper_b_is_null = icmp eq %stack_wrapper* %curr_wrapper_b, null
    %at_least_one_null = or i1 %wrapper_a_is_null, %wrapper_b_is_null
    br i1 %at_least_one_null, label %null_check, label %compare_elements

null_check:
    ; If both wrappers are null, we are finished and the lists are equal.
    ; Otherwise one list is shorter than the other and the lists are NOT
    ; equal.
    %both_null = icmp eq %stack_wrapper* %curr_wrapper_a, %curr_wrapper_b
    br i1 %both_null, label %end_equal, label %end_not_equal

compare_elements:
    ; We have two elements which are both not null, so we can compare them.
    ; Set next pointers:
    %next_wrapper_a = call %stack_wrapper* @stack_wrapper_get_next(%stack_wrapper* %curr_wrapper_a)
    %next_wrapper_b = call %stack_wrapper* @stack_wrapper_get_next(%stack_wrapper* %curr_wrapper_b)

    ; Get the wrapped stack elements.
    %elm_a = call %stack_element* @stack_wrapper_get_element(%stack_wrapper* %curr_wrapper_a)
    %elm_b = call %stack_element* @stack_wrapper_get_element(%stack_wrapper* %curr_wrapper_b)

    ; Now we can do the actual comparison.
    %are_equal = call i1 @do_equal(%stack_element* %elm_a, %stack_element* %elm_b)
    ; If the elements are equal, check the next pair, else exit.
    br i1 %are_equal, label %compare_lists, label %end_not_equal

end_equal:
    ret i1 1

end_not_equal:
    ret i1 0
}


; Convenience functions for use in generated code.

; Push nil (an empty list) onto the stack.
define void @gen_list_push_nil() {
    %list = call %stack_element* @list_new()
    call void @push_struct(%stack_element* %list)
    ret void
}

; Prepend the topmost element to the list, which is the stack element after
; the topmost element, and push the resulting list.
define void @gen_list_cons() {
    %elm_to_prepend = call %stack_element* @pop_struct()
    %list = call %stack_element* @pop_struct()

    ; Make sure %list is a list.
    call void @stack_element_assert_type(%stack_element* %list, i8 1)

    ; Now we can prepend the element to the list...
    call %stack_element* @list_prepend(%stack_element* %list, %stack_element* %elm_to_prepend)

    ; ...and push the list again.
    call void @push_struct(%stack_element* %list)

    ret void
}

define void @gen_list_breakup() {
    %list = call %stack_element* @pop_struct()
    call void @stack_element_assert_is_non_empty_list(%stack_element* %list)

    ; Now pop the topmost list element.
    %top = call %stack_element* @list_pop(%stack_element* %list)

    ; Now we can push the list and its former first element again.
    call void @push_struct(%stack_element* %list)
    call void @push_struct(%stack_element* %top)

    ret void
}