implementation module SymbolTable;

//import macSymbolTable;
//import pcSymbolTable;
import pdSymbolTable;



foldSt op r l :== fold_st r l;
	where
	{
		fold_st [] st		= st;
		fold_st [a:x] st	= fold_st x (op a st);
	}
	
// -------------------------------------------------------------------------------------------------------------------------------------------------------	
	
/* MAC:
*/

/*
create_xcoff_mark_and_offset_arrays2 :: Int Int Int Int LibraryList [*Xcoff] -> (!*{#Bool},!*{#Int},!*{#*Xcoff});
create_xcoff_mark_and_offset_arrays2 n_xcoff_files n_xcoff_symbols n_libraries n_library_symbols library_list list0
	=	(createArray (n_xcoff_symbols+n_library_symbols) False,offset_array1,xcoff_a);
	{
		(offset_array1,xcoff_a) = fill_offsets 0 0 list0 (createArray (n_xcoff_files+n_libraries) 0) (xcoff_array n_xcoff_files);

		xcoff_array :: Int -> !*{#*Xcoff};
		xcoff_array n = { empty_xcoff \\ i<-[0..dec n]};
		
		fill_offsets :: Int Int [*Xcoff] *{#Int} *{#*Xcoff} -> (!*{#Int},!*{#*Xcoff});
		fill_offsets file_n offset [xcoff=:{n_symbols}:xcoff_list] offset_array xcoff_a
			= fill_offsets (inc file_n) (offset+n_symbols) xcoff_list {offset_array & [file_n]=offset} {xcoff_a & [file_n]=xcoff};
		fill_offsets file_n offset [] offset_array xcoff_a
			= (fill_library_offsets library_list file_n offset offset_array,xcoff_a);
		
		fill_library_offsets :: LibraryList Int Int *{#Int} -> *{#Int};
		fill_library_offsets (Library _ symbols n_symbols libraries) file_n offset offset_array
			= fill_library_offsets libraries (inc file_n) (offset+n_symbols) {offset_array & [file_n]=offset};
		fill_library_offsets EmptyLibraryList file_n offset offset_array
			= offset_array;
	}
*/


/* PC:
*/
create_xcoff_boolean_array :: Int Int Int Int LibraryList [*Xcoff] -> (!*{#Bool},!*{#Int},!*{#*Xcoff});
create_xcoff_boolean_array n_xcoff_files n_xcoff_symbols n_libraries n_library_symbols library_list list0
	=	(createArray (n_xcoff_symbols+n_library_symbols) False, offset_array1,xcoff_a);
	{
		(offset_array1,xcoff_a)=fill_offsets 0 0 list0 (createArray (n_xcoff_files+n_libraries) 0)
			//	(createArray n_xcoff_files empty_xcoff);
				(xcoff_array n_xcoff_files);
				
		xcoff_array :: !Int -> !*{#*Xcoff};
		xcoff_array n = { empty_xcoff \\ i<-[0..dec n]};

		
		fill_offsets :: Int Int [*Xcoff] *{#Int} *{#*Xcoff} -> (!*{#Int},!*{#*Xcoff});
		fill_offsets file_n offset [] offset_array xcoff_a
			= (fill_library_offsets library_list file_n offset offset_array,xcoff_a);
		fill_offsets file_n offset [xcoff=:{n_symbols}:xcoff_list] offset_array xcoff_a
			= fill_offsets (inc file_n) (offset+n_symbols) xcoff_list {offset_array & [file_n]=offset} {xcoff_a & [file_n]=xcoff};
		
		/*
		fill_library_offsets :: LibraryList Int Int *{#Int} -> *{#Int};
		fill_library_offsets EmptyLibraryList file_n offset offset_array
			= offset_array;
		fill_library_offsets (Library _ _ symbols n_symbols libraries) file_n offset offset_array
			= fill_library_offsets libraries (inc file_n) (offset+n_symbols) {offset_array & [file_n]=offset};
		*/
	}

// -------------------------------------------------------------------------------------------------------------------------------------------------------
mark_modules_list :: ![String] !*[*Xcoff] !Int !Int !Int !LibraryList [(!Bool,!String,!Int,!Int)] !NamesTable -> (![String],!Int,!*{#Bool},!*{#Int},!*{#*Xcoff},!NamesTable);
mark_modules_list undefined_symbols xcoff_list n_xcoff_files n_libraries n_library_symbols library_list symbols names_table
	#! (n_xcoff_symbols,xcoff_list)
		= n_symbols_of_xcoff_list 0 xcoff_list;
	#! already_marked_bool_a 
		= createArray (n_xcoff_symbols+n_library_symbols) False;
	#! (marked_bool_a,marked_offset_a,xcoff_a)
		= create_xcoff_boolean_array n_xcoff_files n_xcoff_symbols n_libraries n_library_symbols library_list xcoff_list;
	#! (undefined_symbols,already_marked_bool_a,marked_bool_a,marked_offset_a,xcoff_a,names_table,error)
		= foldSt find_index_pairs symbols (undefined_symbols,already_marked_bool_a,marked_bool_a,marked_offset_a,xcoff_a,names_table,"");
	= (undefined_symbols,n_xcoff_symbols,marked_bool_a,marked_offset_a,xcoff_a,names_table)
where {
	find_index_pairs /*label*/ label=:(_,s,file_n,symbol_n) (undefined_symbols,already_marked_bool_a,marked_bool_a,marked_offset_a,xcoff_a,names_table,"")
		// at this all root labels are defined
		#! (undefined_symbols,marked_offset_a,marked_bool_a,xcoff_a)
			= (mark_used_modules symbol_n file_n undefined_symbols already_marked_bool_a marked_bool_a marked_offset_a xcoff_a);  
				
				// NEUTRAL (undefined_symbols,marked_offset_a,marked_bool_a,xcoff_a);
				// PC (mark_used_modules symbol_n file_n undefined_symbols already_marked_bool_a marked_bool_a marked_offset_a xcoff_a);
				// MAC # (undefined_symbols,marked_bool_a,xcoff_a)	= mark_used_modules main_symbol_n main_file_n marked_bool_a marked_offset_a xcoff_a;

		= (undefined_symbols,already_marked_bool_a,marked_bool_a,marked_offset_a,xcoff_a,names_table,"");
			
	find_index_pairs label (undefined_symbols,already_marked_bool_a,marked_bool_a,marked_offset_a,xcoff_a,names_table,e)
		= (undefined_symbols,already_marked_bool_a,marked_bool_a,marked_offset_a,xcoff_a,names_table,e);

	find_name2 :: !String !NamesTable -> (!Bool,!Int,!Int,!NamesTable);
	find_name2 name names_table 
		# (names_table_element,names_table)
			= find_symbol_in_symbol_table name names_table;
		= case names_table_element of {
			(NamesTableElement _ symbol_n file_n _)
				-> (True,file_n,symbol_n,names_table);
			_
				-> (False,0,0,names_table);
	  }
}


//n_symbols_of_xcoff_list :: Int ![u:Xcoff] -> (!Int,![v:Xcoff]), [u <= v];
n_symbols_of_xcoff_list :: Int ![*Xcoff] -> (!Int,![*Xcoff]);
n_symbols_of_xcoff_list n_symbols0 []
	= (n_symbols0,[]);
n_symbols_of_xcoff_list n_symbols0 [xcoff=:{n_symbols}:xcoff_list0]
	= (n_symbols1,[xcoff:xcoff_list1]);
	{
		(n_symbols1,xcoff_list1)=n_symbols_of_xcoff_list (n_symbols0+n_symbols) xcoff_list0;
	}

/*
::	SortArray :== {#SortElement};
::	SortElement = { index::!Int, offset::!Int };

sort_symbols :: !SymbolIndexList !SymbolArray -> (!SymbolIndexList,!SymbolArray);
sort_symbols symbols symbol_array0
	=	(array_to_list sorted_array 0,symbol_array1);
	{
		sorted_array=heap_sort array;
		(array,symbol_array1)=fill_array new_array 0 symbols symbol_array0;
		new_array=createArray n_elements {index=0,offset=0};
		n_elements=length_of_symbol_index_list symbols 0;
		
		fill_array :: *SortArray Int SymbolIndexList SymbolArray -> (!*SortArray,!SymbolArray);
		fill_array a i EmptySymbolIndex symbol_array
			= (a,symbol_array);
		fill_array a i (SymbolIndex index l) symbol_array=:{[index]=m}
			= c a i m symbol_array;
			{
				c :: *SortArray Int Symbol SymbolArray -> (!*SortArray,!SymbolArray);
				c a i (Module _ offset _ _ _ _ _) symbol_array
					= fill_array {a & [i]={index=index,offset=offset}} (inc i) l symbol_array;
			};
		
		array_to_list :: SortArray Int -> SymbolIndexList;
		array_to_list a i
			| i<n_elements
				= SymbolIndex a.[i].index (array_to_list a (inc i));
				= EmptySymbolIndex;
			
		heap_sort :: *SortArray -> *SortArray;
		heap_sort a
			| n_elements<2
				=	a
				=	sort_heap max_index (init_heap (n_elements>>1) a);
				{
					sort_heap :: Int *SortArray -> *SortArray;
					sort_heap i a=:{[i]=a_i,[0]=a_0}
						| i==1
							= { a & [0]=a_i,[i]=a_0}; 
							= sort_heap deci (add_element_to_heap {a & [i]=a_0} a_i 0 deci);{
								deci=dec i;
							}
				
					init_heap :: Int *SortArray -> *SortArray;
					init_heap i a0
						| i>=0
							= init_heap (dec i) (add_element_to_heap1 a0 i max_index); {
								add_element_to_heap1 :: *SortArray Int Int -> *SortArray;
								add_element_to_heap1 a=:{[i]=ir} i max_index
									= add_element_to_heap a ir i max_index;
							}
							= a0;
					
					max_index=dec n_elements;
				}
		
		add_element_to_heap :: *SortArray SortElement Int Int -> *SortArray;
		add_element_to_heap a ir i max_index
			= heap_sort_lp a i (inc (i+i)) max_index ir;
		{
			heap_sort_lp :: *SortArray Int Int Int SortElement-> *SortArray;
			heap_sort_lp a i j max_index ir
				| j<max_index
					= heap_sort1 a i j max_index ir;
				{
					heap_sort1 :: !*SortArray !Int !Int !Int !SortElement -> *SortArray;
					heap_sort1 a=:{[j]=a_j,[j1]=a_j_1} i j max_index ir
						= heap_sort1 a_j a_j_1 a i j max_index ir;
					{
						heap_sort1 :: !SortElement !SortElement !*SortArray !Int !Int !Int !SortElement -> *SortArray;
						heap_sort1 a_j a_j_1 a i j max_index ir
						| a_j.offset < a_j_1.offset
							= heap_sort2 a i (inc j) max_index ir;
							= heap_sort2 a i j max_index ir;

						j1=inc j;
					}
				}
				| j>max_index
					= {a & [i] = ir};
				// j==max_index
					= heap_sort2 a i j max_index ir;
				{}{
					heap_sort2 a=:{[j]=a_j} i j max_index ir
						= heap_sort2 a_j a i j max_index ir;
					{
						heap_sort2 :: SortElement *SortArray !Int !Int !Int SortElement-> *SortArray;
						heap_sort2 a_j a i j max_index ir
						| ir.offset<a_j.offset
							= heap_sort_lp {a & [i] = a_j} j (inc (j+j)) max_index ir;
			   				= {a & [i] = ir};
			   		}
				}
		}
	}

length_of_symbol_index_list EmptySymbolIndex length
	= length;
length_of_symbol_index_list (SymbolIndex _ l) length
	= length_of_symbol_index_list l (inc length);

symbols_are_sorted :: SymbolIndexList {!Symbol} -> Bool;
symbols_are_sorted EmptySymbolIndex symbol_array
	= True;
symbols_are_sorted (SymbolIndex i1 l) symbol_array
	=	sorted_symbols2 i1 l symbol_array;
	{
		sorted_symbols2 :: Int SymbolIndexList {!Symbol} -> Bool;
		sorted_symbols2 i1 EmptySymbolIndex symbol_array
			= True;
		sorted_symbols2 i1 (SymbolIndex i2 l) symbol_array
			= symbol_index_less_or_equal i1 i2 symbol_array && sorted_symbols2 i2 l symbol_array;
	}

reverse_and_sort_symbols :: !SymbolIndexList !SymbolArray -> (!SymbolIndexList,!SymbolArray);
reverse_and_sort_symbols symbols symbol_array
	| symbols_are_sorted reversed_symbols symbol_array
		= (reversed_symbols,symbol_array);
		= sort_symbols reversed_symbols symbol_array;
//	| symbols_are_sorted sorted_symbols symbol_array1
//		= (sorted_symbols,symbol_array1);
	{}{
//		(sorted_symbols,symbol_array1) = sort_symbols reversed_symbols symbol_array;
		reversed_symbols=reverse_symbols symbols;
	}

reverse_symbols l = reverse_symbols l EmptySymbolIndex;
{
	reverse_symbols EmptySymbolIndex t = t;
	reverse_symbols (SymbolIndex i l) t = reverse_symbols l (SymbolIndex i t);
}

	symbol_index_less_or_equal :: Int Int {!Symbol} -> Bool;
	symbol_index_less_or_equal i1 i2 {[i1]=m1,[i2]=m2}
		= case (m1,m2) of {
			(Module _ offset1 _ _ _ _ _,Module _ offset2 _ _ _ _ _)
				-> offset1<=offset2; 
		}

sort_modules :: !*SXcoff -> .SXcoff;
sort_modules xcoff
	= { xcoff & symbol_table = 
		{ symbol_table &
			text_symbols=text_symbols1,
			data_symbols=data_symbols1,
			bss_symbols=bss_symbols1,
			symbols=symbols3
		}
	  };
	{
		(text_symbols1,symbols1)=reverse_and_sort_symbols text_symbols symbols0;
		(data_symbols1,symbols2)=reverse_and_sort_symbols data_symbols symbols1;
		(bss_symbols1,symbols3)=reverse_and_sort_symbols bss_symbols symbols2;
		
		{symbol_table} = xcoff;
		{text_symbols,data_symbols,bss_symbols,symbols=symbols0} = symbol_table;
	}
	*/