graph_to_string_with_descriptors.icl 12.4 KB
Newer Older
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
1 2 3 4
implementation module graph_to_string_with_descriptors;

import StdEnv;

5 6
import code from "copy_graph_to_string_interface.";
import code from "copy_graph_to_string.";
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

eval_all_nodes :: !.a -> .a;
eval_all_nodes g = code {
	push_a 0
	.d 1 0
	jsr	_eval_to_nf
	.o 0 0
}

copy_to_string :: !a -> *{#Char};
copy_to_string g = code {
	.d 1 0
		jsr _copy_graph_to_string
	.o 1 0
}

John van Groningen's avatar
John van Groningen committed
23 24 25 26
get_D_from_string s i :== IF_INT_64_OR_32 (get_D_from_string_64 s i) (get_D_from_string_32 s i);

get_D_from_string_32 :: !{#Char} !Int -> Int;
get_D_from_string_32 s i = code inline {
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
27 28 29 30 31 32
	push_a_b 0
	pop_a 1
	addI
	load_i 8
}

John van Groningen's avatar
John van Groningen committed
33 34 35 36 37 38 39 40
get_D_from_string_64 :: !{#Char} !Int -> Int;
get_D_from_string_64 s i = code inline {
	push_a_b 0
	pop_a 1
	addI
	load_i 16
}

Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
get_D_arity :: !Int -> Int;
get_D_arity a = code {
	push_b 0
	load_si16 0
	addI
	load_si16 4
}

get_D_node_arity :: !Int -> Int;
get_D_node_arity d = code inline {
	load_si16 -2
}

get_D_record_a_arity :: !Int -> Int;
get_D_record_a_arity d = code inline {
	load_si16 0
}

is_Int_D :: !Int -> Bool;
is_Int_D d = code inline {
	eq_desc_b INT 0
}

is_Char_D :: !Int -> Bool;
is_Char_D d = code inline {
	eq_desc_b CHAR 0
}

is_Real_D :: !Int -> Bool;
is_Real_D d = code inline {
	eq_desc_b REAL 0
}

is_Bool_D :: !Int -> Bool;
is_Bool_D d = code inline {
	eq_desc_b BOOL 0
}

is_Array_D :: !Int -> Bool;
is_Array_D d = code inline {
	eq_desc_b ARRAY 1
}

is__Array__D :: !Int -> Bool;
is__Array__D d = code inline {
	eq_desc_b _ARRAY_ 0
}

is__String__D :: !Int -> Bool;
is__String__D d = code inline {
	eq_desc_b _STRING_ 0
}

is__Nil_D :: !Int -> Bool;
is__Nil_D d = code inline {
	eq_desc_b _Nil 0
}

is__Cons_D :: !Int -> Bool;
is__Cons_D d = code inline {
	eq_desc_b _Cons 2
}

is__Tuple_D :: !Int -> Bool;
is__Tuple_D d = code inline {
	eq_desc_b _Tuple 0
}

get_D_name :: !Int -> {#Char};
get_D_name d = code {
	.d 0 1 i
	jsr DtoAC
	.o 1 0
}

John van Groningen's avatar
John van Groningen committed
116 117 118 119
get_D_cons_module d :== IF_INT_64_OR_32 (get_D_cons_module_64 d) (get_D_cons_module_32 d);

get_D_cons_module_32 :: !Int -> Int;
get_D_cons_module_32 d = code {
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
120 121 122 123 124 125
	push_b 0
	load_si16 0
	addI
	load_i 6
}

John van Groningen's avatar
John van Groningen committed
126 127 128 129 130 131 132 133 134 135 136 137
get_D_cons_module_64 :: !Int -> Int;
get_D_cons_module_64 d = code {
	push_b 0
	load_si16 0
	addI
	load_si32 6
}

get_D_record_module d :== IF_INT_64_OR_32 (get_D_record_module_64 d) (get_D_record_module_32 d);

get_D_record_module_32 :: !Int -> Int;
get_D_record_module_32 d = code {
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
138 139 140
	load_i -10
}

John van Groningen's avatar
John van Groningen committed
141 142 143 144 145 146 147 148 149
get_D_record_module_64 :: !Int -> Int;
get_D_record_module_64 d = code {
	load_si32 -10
}

get_module_name_size a :== IF_INT_64_OR_32 (get_module_name_size_64 a) (get_module_name_size_32 a);

get_module_name_size_32 :: !Int -> Int;
get_module_name_size_32 a = code {
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
150 151 152
	load_i 0
}

John van Groningen's avatar
John van Groningen committed
153 154 155 156 157
get_module_name_size_64 :: !Int -> Int;
get_module_name_size_64 a = code {
	load_si32 0
}

Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
158 159 160 161 162 163 164 165 166 167 168 169
get_module_name_char :: !Int !Int -> Char;
get_module_name_char a i = code {
	addI
	load_ui8 4
}

get_record_type_char :: !Int !Int -> Char;
get_record_type_char a i = code {
	addI
	load_ui8 2
}

John van Groningen's avatar
John van Groningen committed
170 171 172 173
get_array_elem_D a offset :== IF_INT_64_OR_32 (get_array_elem_D_64 a offset) (get_array_elem_D_32 a offset);

get_array_elem_D_32 :: !a !Int -> Int;
get_array_elem_D_32 a offset = code {
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
174 175 176 177 178 179
	push_a_b 0
	addI
	pop_a 1
	load_i 8
}

John van Groningen's avatar
John van Groningen committed
180 181 182 183 184 185 186 187 188 189 190 191
get_array_elem_D_64 :: !a !Int -> Int;
get_array_elem_D_64 a offset = code {
	push_a_b 0
	addI
	pop_a 1
	load_i 16
}

get_array_size a offset :== IF_INT_64_OR_32 (get_array_size_64 a offset) (get_array_size_32 a offset);

get_array_size_32 :: !a !Int -> Int;
get_array_size_32 a offset = code {
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
192 193 194 195 196 197
	push_a_b 0
	addI
	pop_a 1
	load_i 4
}

John van Groningen's avatar
John van Groningen committed
198 199 200 201 202 203 204 205
get_array_size_64 :: !a !Int -> Int;
get_array_size_64 a offset = code {
	push_a_b 0
	addI
	pop_a 1
	load_i 8
}

Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
get_record_type :: !Int -> {#Char};
get_record_type d
	= {get_record_type_char d i\\i<-[0..get_record_type_size 0 d-1]};
{
	get_record_type_size i d
		# c=get_record_type_char d i;
		| c=='\0'
			= i;
			= get_record_type_size (i+1) d;
}
	
get_module_name :: !Int -> {#Char};
get_module_name m
	= {get_module_name_char m i\\i<-[0..get_module_name_size m-1]};

get_n_non_pointers_and_array_elem_desc :: !Int !a !Int -> (!Int,!Int);
get_n_non_pointers_and_array_elem_desc d v offset
	# arity = get_D_node_arity d;
	| arity==0
		| is_Int_D d || is_Char_D d || is_Bool_D d
			= (1,0);
		| is_Real_D d
John van Groningen's avatar
John van Groningen committed
228
			= (IF_INT_64_OR_32 1 2,0);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
229 230 231 232 233 234 235
		| is__Array__D d
			# ed=get_array_elem_D v offset;
			| ed==0
				= (2,ed);
			| is_Int_D ed
				= (2+get_array_size v offset,ed);
			| is_Real_D ed
John van Groningen's avatar
John van Groningen committed
236
				= (2+(IF_INT_64_OR_32 (get_array_size v offset) (get_array_size v offset<<1)),ed);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
237
			| is_Bool_D ed
John van Groningen's avatar
John van Groningen committed
238
				= (2+((get_array_size v offset+IF_INT_64_OR_32 7 3)>>(IF_INT_64_OR_32 3 2)),ed);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
239 240 241
				# arity = get_D_node_arity ed;
				= (2 + get_array_size v offset * (arity-256-get_D_record_a_arity ed),ed);
		| is__String__D d
John van Groningen's avatar
John van Groningen committed
242
			= (1+((get_array_size v offset+IF_INT_64_OR_32 7 3)>>(IF_INT_64_OR_32 3 2)),0);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298
			= (0,0);
	| arity < 256
		= (0,0);
		= (arity-256-get_D_record_a_arity d,0);

get_module :: !Int -> Int;
get_module d
	# arity = get_D_node_arity d;
	| arity==0
		| is_Int_D d || is_Char_D d || is_Real_D d || is_Bool_D d || is__Array__D d || is__String__D d
			= 0;
		| is__Nil_D d
			= 0;
			= get_D_cons_module d;
	| arity < 256
		| is__Cons_D d
			= 0;
		| is__Tuple_D (d-arity*8)
			= 0;
			= get_D_cons_module d;
		= get_D_record_module d;

uarray :: u:{#.a} -> u:{#.a} | Array {#} a;
uarray a = a;

cast_string_to_a :: !{#Char} -> a;
cast_string_to_a s = code {
	pop_a 0
}

:: DescOrModTree
	= DescOrModTreeNode /*descriptor or module*/!Int /*descriptor_n or module_n*/!Int !DescOrModTree !DescOrModTree
	| EmptyDescOrModTree;

search_desc_or_mod_n_in_tree :: !Int !DescOrModTree -> Int;
search_desc_or_mod_n_in_tree desc_or_mod (DescOrModTreeNode tree_desc_or_mod tree_desc_or_mod_n left_desc_tree right_desc_tree)
	| desc_or_mod==tree_desc_or_mod
		= tree_desc_or_mod_n;
	| desc_or_mod<tree_desc_or_mod
		= search_desc_or_mod_n_in_tree desc_or_mod left_desc_tree;
		= search_desc_or_mod_n_in_tree desc_or_mod right_desc_tree;
search_desc_or_mod_n_in_tree desc_or_mod EmptyDescOrModTree
	= -1;

add_desc_or_mod_to_tree :: !Int !Int !u:DescOrModTree -> u:DescOrModTree;
add_desc_or_mod_to_tree desc desc_n (DescOrModTreeNode descriptor descriptor_n left_desc_tree right_desc_tree)
	| desc==descriptor
		= abort "add_desc_or_mod_to_tree: desc already in tree";
	| desc<descriptor
		= DescOrModTreeNode descriptor descriptor_n (add_desc_or_mod_to_tree desc desc_n left_desc_tree) right_desc_tree;
		= DescOrModTreeNode descriptor descriptor_n left_desc_tree (add_desc_or_mod_to_tree desc desc_n right_desc_tree);
add_desc_or_mod_to_tree desc desc_n EmptyDescOrModTree
	= DescOrModTreeNode desc desc_n EmptyDescOrModTree EmptyDescOrModTree;

store_int_in_string :: !*{#Char} !Int !Int -> *{#Char};
store_int_in_string s i n
John van Groningen's avatar
John van Groningen committed
299 300 301 302
	= IF_INT_64_OR_32
		{s & [i]=toChar n,[i+1]=toChar (n>>8),[i+2]=toChar (n>>16),[i+3]=toChar (n>>24),
			 [i+4]=toChar (n >> 32),[i+5]=toChar (n>>40),[i+6]=toChar (n>>48),[i+7]=toChar (n>>56)}
		{s & [i]=toChar n,[i+1]=toChar (n>>8),[i+2]=toChar (n>>16),[i+3]=toChar (n>>24)};
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
303 304 305 306 307 308 309

replace_descs_by_desc_numbers_and_build_desc_tree :: !Int !*{#Char} !Int !DescOrModTree -> (!*{#Char},!Int,!DescOrModTree);
replace_descs_by_desc_numbers_and_build_desc_tree i s n_descs desc_tree
	| i>=size s
		= (s,n_descs,desc_tree);
	#! desc=get_D_from_string s i;
	| desc bitand 1<>0
John van Groningen's avatar
John van Groningen committed
310
		= replace_descs_by_desc_numbers_and_build_desc_tree (i+IF_INT_64_OR_32 8 4) s n_descs desc_tree;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
311 312 313
	| desc bitand 2==0
		= abort ("unevaluated node in replace_descs_by_desc_numbers_and_build_desc_tree "+++toString desc);
	#! a=cast_string_to_a s;
John van Groningen's avatar
John van Groningen committed
314
	# (d,array_elem_desc) = get_n_non_pointers_and_array_elem_desc desc a (i+IF_INT_64_OR_32 16 8);
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
315 316
	# (s,n_descs,desc_tree) = store_desc_n_and_add_desc desc i s n_descs desc_tree;
	| array_elem_desc==0
John van Groningen's avatar
John van Groningen committed
317 318 319
		= replace_descs_by_desc_numbers_and_build_desc_tree (i+IF_INT_64_OR_32 8 4+(d<<(IF_INT_64_OR_32 3 2))) s n_descs desc_tree;
		# (s,n_descs,desc_tree) = store_desc_n_and_add_desc array_elem_desc (i+IF_INT_64_OR_32 16 8) s n_descs desc_tree;
		= replace_descs_by_desc_numbers_and_build_desc_tree (i+IF_INT_64_OR_32 8 4+(d<<(IF_INT_64_OR_32 3 2))) s n_descs desc_tree;
Rinus Plasmeijer's avatar
Rinus Plasmeijer committed
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445
{}{
	store_desc_n_and_add_desc :: Int Int !*{#Char} !Int !DescOrModTree -> (!*{#Char},!Int,!DescOrModTree);
	store_desc_n_and_add_desc desc i s n_descs desc_tree
		# desc_n=search_desc_or_mod_n_in_tree desc desc_tree;
		| desc_n>=0
			# s=store_int_in_string s i (desc_n+1);  // add 1 because 0 is used as element descriptor for lazy/boxed arrays
			= (s,n_descs,desc_tree);
			# desc_tree = add_desc_or_mod_to_tree desc n_descs desc_tree;
			# s=store_int_in_string s i (n_descs+1); // add 1 because 0 is used as element descriptor for lazy/boxed arrays
			= (s,n_descs+1,desc_tree);			
}

:: Desc_ModuleN = {desc::!Int,desc_mod_n::!Int};

make_desc_array :: !Int !DescOrModTree -> *{#Desc_ModuleN};
make_desc_array n_descs desc_tree
	= fill_desc_array desc_tree (createArray n_descs {desc=0,desc_mod_n=0});
{
	fill_desc_array :: !DescOrModTree !*{#Desc_ModuleN} -> *{#Desc_ModuleN};
	fill_desc_array (DescOrModTreeNode descriptor descriptor_n left_desc_tree right_desc_tree) a
		= fill_desc_array right_desc_tree (fill_desc_array left_desc_tree {a & [descriptor_n].desc=descriptor});
	fill_desc_array EmptyDescOrModTree a
		= a;
}

make_mod_array :: !Int !DescOrModTree -> *{#Int};
make_mod_array n_mods mod_tree
	= fill_desc_array mod_tree (createArray n_mods 0);
{
	fill_desc_array :: !DescOrModTree !*{#Int} -> *{#Int};
	fill_desc_array (DescOrModTreeNode descriptor descriptor_n left_mod_tree right_mod_tree) a
		= fill_desc_array right_mod_tree (fill_desc_array left_mod_tree {a & [descriptor_n]=descriptor});
	fill_desc_array EmptyDescOrModTree a
		= a;
}

make_module_tree :: !*{#Desc_ModuleN} -> (!*{#Desc_ModuleN},!Int,!DescOrModTree);
make_module_tree a
	= add_modules 0 a 0 EmptyDescOrModTree;
{
	add_modules i a n_mods mod_tree
		| i==size a
			= (a,n_mods,mod_tree);
			# (desc,a)=a![i].desc;
			# mod=get_module desc;
			| mod==0
				= add_modules (i+1) a n_mods mod_tree;
			# mod_n=search_desc_or_mod_n_in_tree mod mod_tree;
			| mod_n>=0
				# a = {a & [i].desc_mod_n=mod_n+1};
				= add_modules (i+1) a n_mods mod_tree;
				# mod_tree = add_desc_or_mod_to_tree mod n_mods mod_tree;
				# a = {a & [i].desc_mod_n=n_mods+1};
				= add_modules (i+1) a (n_mods+1) mod_tree;
}

arity_to_char :: !Int -> Char;
arity_to_char a
	| a<0
		= abort "arity_to_charL: incorrect arity";
	| a<10
		= toChar (48+a); // 0..
	| a<36
		= toChar (55+a); // A..
		= abort "arity_to_charL: incorrect arity";

info_of_desc_and_mod :: !Desc_ModuleN -> {#Char};
info_of_desc_and_mod {desc,desc_mod_n}
	# arity = get_D_node_arity desc;
	| arity==0
		| is_Int_D desc
			= "i";
		| is_Char_D desc
			= "c";
		| is_Real_D desc
			= "r";
		| is_Bool_D desc
			= "b";
		| is__Array__D desc
			= "a";
		| is__String__D desc
			= "s";
		| is__Nil_D desc
			= "n";
			= {'C',arity_to_char arity,arity_to_char (get_D_arity desc),toChar (desc_mod_n),toChar (desc_mod_n>>8)}
				+++get_D_name desc+++"\0";
	| arity < 256
		| is__Cons_D desc
			= ":";
		| is__Tuple_D (desc-arity*8)
			= {'t',arity_to_char arity};
		= {'C',arity_to_char arity,arity_to_char (get_D_arity desc),toChar (desc_mod_n),toChar (desc_mod_n>>8)}
			+++get_D_name desc+++"\0";
		= {'R',arity_to_char (arity-256),arity_to_char (get_D_record_a_arity desc),toChar (desc_mod_n),toChar (desc_mod_n>>8)}
			+++get_record_type desc+++"\0"
			+++get_D_name desc+++"\0";

array_of_strings_to_string :: !{#{#Char}} -> {#Char};
array_of_strings_to_string a
	#! n=size a;
	# n_s={toChar n,toChar (n>>8),toChar (n>>16),toChar (n>>24)};
 	= concat_strings [n_s : [s+++"\0"\\s<-:a]];
 {
 	concat_strings [s] = s;
 	concat_strings a = concat_strings (append_pairs a);
 	
 	append_pairs [s1,s2:l] = [s1+++s2:append_pairs l];
 	append_pairs l = l;
 }

graph_to_string_with_descriptor_and_module_table :: !a -> (!{#Char},!{#{#Char}},!{#{#Char}});
graph_to_string_with_descriptor_and_module_table g
	# g = eval_all_nodes g;
	# s = copy_to_string g;
	# (s,n_descs,desc_tree) = replace_descs_by_desc_numbers_and_build_desc_tree 0 s 0 EmptyDescOrModTree;
	# desc_a = make_desc_array n_descs desc_tree;
	# (desc_a,n_mods,mod_tree) = make_module_tree desc_a;
	# mod_a = make_mod_array n_mods mod_tree;
	# mod_s_a = uarray {get_module_name mod \\ mod<-:mod_a};
	# desc_s_a = uarray {info_of_desc_and_mod desc_and_mod \\ desc_and_mod <-:desc_a};
	= (s,desc_s_a,mod_s_a);

graph_to_string_with_descriptors :: !a -> {#Char};
graph_to_string_with_descriptors g
	# (s,desc_s_a,mod_s_a) = graph_to_string_with_descriptor_and_module_table g;
	= array_of_strings_to_string mod_s_a+++array_of_strings_to_string desc_s_a+++s;