[m-rev.] [reuse] diff: user-annotated aliasing

[Nancy Mazur]

Hi Peter,

Okay... this is the full diff... I will commit it now. 
I've annotated array.m to test the changes, and it seems
to work smoothlessly. What I haven't checked yet is the
purpose of converting the pragma-annotations back to strings. 
So for the alias-annotatations, it's still incomplete. But
I don't know to what extent it has to be really complete
(is a bit more tricky than the other ones, as there are 
variables involved). 

Oh yes, next question, how can I change the library, and 
have all the stuff bootchecked with an annotated string-module ?

Nancy

PS: in attach my annotated module marray.m and the 
resulting marray.trans_opt.


===================================================================


Estimated hours taken: 8
Branches: reuse

Alias-annotations in pragma_foreign_code is now either: 
	- no_aliasing
	- unknown_aliasing
	- or alias(MaybeTypes, AliasList)
such that
	MaybeTypes = yes( Full List of the types of the variables involved
			in the foreign code)
		   = no
	AliasList = list of aliases expressed as
			cel(Var, TypeSelectorList) - cel(OtherVar, OterSel)

The analysis correctly performs all the necessary renaming. 



make_hlds.m:
	Rename the aliasing-attribute of the pragma. 

pa_alias_as.m:
pa_selector.m:
	- Change extend_foreign_code so that it also uses the user-provided
	aliases. 
	- Add parsing and conversion predicates for dealing with the
	user defined aliases. 

prog_data.m:
prog_io_pragma.m:
	Deal with new alias annoations for pragma foreign code.


Index: make_hlds.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/make_hlds.m,v
retrieving revision 1.347.2.11
diff -u -r1.347.2.11 make_hlds.m
--- make_hlds.m	2001/02/07 14:29:27	1.347.2.11
+++ make_hlds.m	2001/03/22 09:54:47
@@ -5314,13 +5314,21 @@
 		map__apply_to_list(Args0, Subst, TermArgs),
 		term__term_list_to_var_list(TermArgs, Args),
 
+		% rename the aliasing information from their variables
+		% to the actual variables (prog_var's as well as type-
+		% variables. 
+		aliasing(Attributes, Aliasing0), 
+		rename_aliasing(Aliasing0, Args0, HeadVars, OrigArgTypes, 
+			Aliasing), 
+		set_aliasing(Attributes, Aliasing, Attributes1), 
+
 			% build the pragma_c_code
 		goal_info_init(GoalInfo0),
 		goal_info_set_context(GoalInfo0, Context, GoalInfo1),
 		% Put the purity in the goal_info in case
 		% this foreign code is inlined
 		add_goal_info_purity_feature(GoalInfo1, Purity, GoalInfo),
-		HldsGoal0 = pragma_foreign_code(Attributes, PredId, 
+		HldsGoal0 = pragma_foreign_code(Attributes1, PredId, 
 			ModeId, Args, ArgInfo, OrigArgTypes, PragmaImpl)
 			- GoalInfo
 		}, 
@@ -5344,6 +5352,25 @@
 			TI_VarMap, TCI_VarMap)
 		}
 	).
+
+:- pred rename_aliasing(aliasing::in, list(prog_var)::in, 
+	list(prog_var)::in, list(type)::in, aliasing::out) is det.
+rename_aliasing(ActualAliasing, ActualHVs, FormalHVs, FormalTypes, 
+			FormalAliasing):- 
+	ActualAliasing = aliasing(MaybeActualTypes, ActualAlias),
+	map__from_corresponding_lists(ActualHVs, FormalHVs, VarMapping), 
+	pa_alias_as__rename(VarMapping, ActualAlias, Alias0), 
+	(
+		MaybeActualTypes = yes(ActualTypes)
+	->
+		pa_alias_as__rename_types(ActualTypes, FormalTypes, 
+				Alias0, FormalAlias)
+	;
+		FormalAlias = Alias0
+	), 
+	% NB: MaybeActualTypes are not needed after this renaming
+	FormalAliasing = aliasing(no, FormalAlias). 
+		
 
 :- pred allocate_vars_for_saved_vars(list(string), list(pair(prog_var, string)),
 	prog_varset, prog_varset).
Index: pa_alias_as.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_alias_as.m,v
retrieving revision 1.1.2.16
diff -u -r1.1.2.16 pa_alias_as.m
--- pa_alias_as.m	2001/03/21 13:19:43	1.1.2.16
+++ pa_alias_as.m	2001/03/22 09:54:48
@@ -156,6 +156,12 @@
 :- pred parse_read_aliases_from_single_term(term(T), alias_as).
 :- mode parse_read_aliases_from_single_term(in, out) is det.
 
+:- pred parse_user_declared_aliases(term, aliasing).
+:- mode parse_user_declared_aliases(in, out) is semidet.
+
+:- pred to_user_declared_aliases(aliasing, string). 
+:- mode to_user_declared_aliases(in, out) is det.
+
 	% Live = live(IN_USE,LIVE_0,ALIASES).
 	% compute the live-set based upon an initial IN_USE set, 
 	% and a list of aliases.
@@ -472,19 +478,22 @@
 
 
 %-----------------------------------------------------------------------------%
-extend_foreign_code(_ProcInfo, HLDS, GoalInfo,
+extend_foreign_code(ProcInfo, HLDS, GoalInfo,
 			Attrs, Vars, MaybeModes, Types, Alias0, Alias):-
 	to_trios(Vars, MaybeModes, Types, Trios), 
 	% remove all unique objects
 	remove_all_unique_vars(HLDS, Trios, NonUniqueVars), 
 	% keep only the output vars
 	collect_all_output_vars(HLDS, NonUniqueVars, OutputVars), 
-%	collect_all_input_vars(HLDS, NonUniqueVars, InputVars), 
 	(
+		aliasing(Attrs, UserDefinedAlias),
+		UserDefinedAlias = aliasing(_MaybeTypes, UserAlias),
+		UserAlias \= top(_)
+	->
+		extend(ProcInfo, HLDS, UserAlias, Alias0, Alias)
+	;	
 		(
 			OutputVars = [] 
-		;
-			aliasing(Attrs, no_aliasing)
 %		; 
 %			% XXXXXXXXXXXXXXXXX !!
 %			OutputVars = [_], InputVars = []
@@ -506,14 +515,9 @@
 		; 
 
 			goal_info_get_context(GoalInfo, Context), 
-			term__context_line(Context, ContextLine), 
-			term__context_file(Context, ContextFile), 
-			string__int_to_string(ContextLine, ContextLineS), 
-
+			format_context(Context, ContextStr), 
 			string__append_list(["pragma_foreign_code:",
-						" (",ContextFile, ":", 
-						ContextLineS, ")"], Msg), 
-			
+						" (",ContextStr, ")"], Msg), 
 			pa_alias_as__top(Alias0, Msg, Alias)
 		)
 	).
@@ -634,9 +638,9 @@
 	).
 		
 
-%-------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
 % printing routines
-%-------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
 
 	% MaybeAs = yes(Alias_as) -> print out Alias_as
 	%         = no		   -> print "not available"
@@ -705,9 +709,9 @@
 	).
 
 
-%-------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
 % parsing routines
-%-------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
 
 parse_read_aliases(LISTTERM ,AS):- 
 	(
@@ -743,11 +747,9 @@
 		; 
 			CONS = "top"
 		->
-			term__context_line(Context, ContextLine), 
-			term__context_file(Context, ContextFile), 
-			string__int_to_string(ContextLine, ContextLineS), 
+			format_context(Context, ContextString), 
 			string__append_list(["imported top (", 
-				ContextFile, ":", ContextLineS, ")"], 
+				ContextString, ")"], 
 					Msg),
 			top(Msg, AS)
 		;
@@ -786,7 +788,135 @@
                 error("(pa_alias_as) parse_list_alias_term: term is not a functor")
 	).
 
+%-----------------------------------------------------------------------------%
+% user declared aliases
+%-----------------------------------------------------------------------------%
+
+parse_user_declared_aliases(term__functor(term__atom("no_aliasing"), [], _),
+                Aliasing):-
+        pa_alias_as__init(BottomAlias),
+	Aliasing = aliasing(no, BottomAlias). 
+parse_user_declared_aliases(term__functor(term__atom("unknown_aliasing"), 
+				[], Context), Aliasing):-
+	format_context(Context, ContextString), 
+	string__append_list(["user declared top (", ContextString, ")"], Msg),
+        pa_alias_as__top(Msg, TopAlias), 
+	Aliasing = aliasing(no, TopAlias). 
+parse_user_declared_aliases(term__functor(term__atom("alias"), 
+		[TypesTerm,AliasTerm], _), Aliasing):-
+	(
+		TypesTerm = term__functor(term__atom("yes"), 
+					ListTypesTerms, _), 
+		list__map(term__coerce, ListTypesTerms, Types), 
+		MaybeTypes = yes(Types)
+	;
+		TypesTerm = term__functor(term__atom("no"),[],_), 
+		MaybeTypes = no
+	), 
+	parse_user_declared_aliases_2(AliasTerm, AliasAs), 
+	Aliasing = aliasing(MaybeTypes, AliasAs). 
+
+:- pred format_context(term__context::in, string::out) is det.
+format_context(Context, String):- 
+	term__context_line(Context, ContextLine), 
+	term__context_file(Context, ContextFile), 
+	string__int_to_string(ContextLine, ContextLineS), 
+	string__append_list([ContextFile, ":", ContextLineS], 
+			String).
 
+:- pred parse_user_declared_aliases_2(term::in, alias_as::out) is det.
+parse_user_declared_aliases_2(ListTerm, AliasAS):- 
+	(
+		parse_list_term(ListTerm, AllTerms)
+	-> 
+		list__map(parse_single_user_declared_alias, 
+				AllTerms, AliasList),
+		pa_alias_set__from_pair_alias_list(AliasList, AliasSet),
+		wrap(AliasSet, AliasAS)
+	;
+		error("(pa_alias_as) parse_user_declared_aliases_2: term not a functor")
+	).
+
+:- pred parse_list_term(term::in, list(term)::out) is semidet.
+parse_list_term(ListTerm, Terms):- 
+	ListTerm = term__functor(term__atom(Cons), Args, _), 
+	(
+		Cons = "."
+	->
+		Args = [FirstTerm, RestTerm],
+		parse_list_term(RestTerm, RestList), 
+		Terms = [FirstTerm | RestList]
+	;
+		Cons = "[]"
+	->
+		Terms = []
+	; 
+		fail
+	). 
+
+:- pred parse_single_user_declared_alias(term::in, alias::out) is det.
+parse_single_user_declared_alias(Term, Alias):- 
+	(
+		Term = term__functor(term__atom("-"), [Left, Right], _)
+	->
+		% Left and Right have shape "cel(ProgVar, Types)"
+		parse_user_datastruct(Left, LeftData), 
+		parse_user_datastruct(Right, RightData), 
+		Alias = LeftData - RightData
+	;
+		error("(pa_alias_as) parse_single_user_declared_alias: wrong functor.")
+	).
+
+:- import_module pa_selector. 
+:- pred parse_user_datastruct(term::in, 
+		pa_datastruct__datastruct::out) is det. 
+parse_user_datastruct(Term, Data):- 
+	(
+		Term = term__functor(term__atom("cel"),
+			[VarTerm, TypesTerm], Context)
+	->
+		(
+			VarTerm = term__variable(GenericVar),
+			term__coerce_var(GenericVar, ProgVar) 
+		-> 
+			( 
+				parse_list_term(TypesTerm, ListTypesTerms)
+			-> 
+				list__map(term__coerce, ListTypesTerms, Types),
+				pa_selector__from_types(Types, Selector), 
+				pa_datastruct__create(ProgVar, Selector, Data)
+			;
+				format_context(Context, ContextString), 
+				string__append_list([
+				"(pa_alias_as) parse_user_datastruct: ", 
+				"error in declared selector (", 
+					ContextString, ")"], Msg), 
+				error(Msg)
+				
+			)
+		;
+			format_context(Context, ContextString), 
+			string__append_list([
+				"(pa_alias_as) parse_user_datastruct: ", 
+				"error in declared alias (", 
+				ContextString, ")"], Msg), 
+			error(Msg)
+		)
+	;
+		error("(pa_alias_as) parse_user_datastruct: wrong datastructure description -- should be cel/2")
+	).
+
+		
+to_user_declared_aliases(aliasing(_, bottom), "no_aliasing"). 
+to_user_declared_aliases(aliasing(_, top(_)), "unknown_aliasing").
+to_user_declared_aliases(aliasing(_, real_as(_)), "alias([])"). 
+
+%-----------------------------------------------------------------------------%
+
+%-----------------------------------------------------------------------------%
+% Extra 
+%-----------------------------------------------------------------------------%
 :- pred wrap(pa_alias_set__alias_set, alias_as).
 :- mode wrap(in, out) is det.
 
@@ -837,6 +967,7 @@
 	pa_alias_set__apply_widening(ModuleInfo, ProcInfo, 
 			AliasSet0, AliasSet), 
 	A = real_as(AliasSet).
+
 %-----------------------------------------------------------------------------%
 % computing LIVE_SET
 %-----------------------------------------------------------------------------%
Index: pa_selector.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/Attic/pa_selector.m,v
retrieving revision 1.1.2.4
diff -u -r1.1.2.4 pa_selector.m
--- pa_selector.m	2001/03/05 17:06:51	1.1.2.4
+++ pa_selector.m	2001/03/22 09:54:48
@@ -48,6 +48,8 @@
 	% create an initial selector with given constructor and index.
 :- pred init(cons_id::in, int::in, selector::out) is det.
 
+:- pred from_types(list(type)::in, selector::out) is det.
+
 	% check whether the selector is a top-selector.
 :- pred top(selector::in) is semidet.
 
@@ -109,6 +111,13 @@
 init(CONS, INDEX, SEL):-
 	US = us(CONS, INDEX),
 	SEL = [US].
+from_types(Types, Selector):- 
+	list__map(
+		pred(T::in, US::out) is det :- 
+			US = ts(T),
+		Types,
+		Selector). 	
+		
 
 top([]).
 
Index: prog_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/prog_data.m,v
retrieving revision 1.58.2.8
diff -u -r1.58.2.8 prog_data.m
--- prog_data.m	2001/03/21 13:19:45	1.58.2.8
+++ prog_data.m	2001/03/22 09:54:48
@@ -535,6 +535,7 @@
 		% `pragma_c_code_attribute's.
 :- type pragma_foreign_code_attributes.
 
+
 :- pred default_attributes(foreign_language, pragma_foreign_code_attributes).
 :- mode default_attributes(in, out) is det.
 
@@ -592,9 +593,14 @@
 	--->	not_tabled_for_io
 	;	tabled_for_io.
 
-:- type aliasing
-	--->	no_aliasing
-	;	unknown_aliasing.
+% :- type aliasing
+%	--->	no_aliasing
+%	;	unknown_aliasing.
+:- type aliasing 
+	---> 	aliasing(maybe(list(type)), % this is only needed when the
+					    % user expresses aliases in terms
+					    % of type-variables.
+			 pa_alias_as__alias_as). 
 
 :- type pragma_var    
 	--->	pragma_var(prog_var, string, mode).
@@ -987,7 +993,9 @@
 
 default_attributes(Language, 
 	attributes(Language, may_call_mercury, not_thread_safe, 
-		not_tabled_for_io, unknown_aliasing)).
+		not_tabled_for_io, Aliasing)):-
+	pa_alias_as__top("Default top", TopAlias), 
+	Aliasing = aliasing(no, TopAlias).
 
 may_call_mercury(Attrs, Attrs ^ may_call_mercury).
 
@@ -1040,14 +1048,8 @@
 	;
 		TabledForIO = not_tabled_for_io,
 		TabledForIOStr = "not_tabled_for_io"
-	),
-	(
-		Aliasing = no_aliasing,
-		AliasingStr = "no_aliasing"
-	;
-		Aliasing = unknown_aliasing,
-		AliasingStr = "unknown_aliasing"
 	),
+	to_user_declared_aliases(Aliasing, AliasingStr), 
 	StringList = [MayCallMercuryStr, ThreadSafeStr, TabledForIOStr,
 			AliasingStr].
 
Index: prog_io_pragma.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/prog_io_pragma.m,v
retrieving revision 1.23.2.7
diff -u -r1.23.2.7 prog_io_pragma.m
--- prog_io_pragma.m	2001/03/21 13:19:49	1.23.2.7
+++ prog_io_pragma.m	2001/03/22 09:54:49
@@ -1175,7 +1175,7 @@
 	--->	may_call_mercury(may_call_mercury)
 	;	thread_safe(thread_safe)
 	;	tabled_for_io(tabled_for_io)
-	;	aliasing(aliasing).
+	;	collected_aliasing(aliasing).
 
 :- pred parse_pragma_foreign_code_attributes_term(foreign_language, term, 
 		pragma_foreign_code_attributes).
@@ -1216,12 +1216,16 @@
 	;
 		Attributes3 = Attributes2
 	),
-	( list__member(aliasing(no_aliasing), AttrList) ->
-		( list__member(aliasing(unknown_aliasing), AttrList) ->
+	( list__filter(
+			pred(C::in) is semidet :- 
+				C = collected_aliasing(_), 
+			AttrList, 
+			AliasInfo), AliasInfo \= [] ->
+		( AliasInfo = [collected_aliasing(Aliasing)] ->
+			set_aliasing(Attributes3, Aliasing, Attributes)
+		;
 			% XXX an error message would be nice
 			fail
-		;
-			set_aliasing(Attributes3, no_aliasing, Attributes)
 		)
 	;
 		Attributes = Attributes3
@@ -1260,7 +1264,7 @@
 	; parse_tabled_for_io(Term, TabledForIo) ->
 		Flag = tabled_for_io(TabledForIo)
 	; parse_aliasing(Term, Aliasing) ->
-		Flag = aliasing(Aliasing)
+		Flag = collected_aliasing(Aliasing)
 	;
 		fail
 	).
@@ -1296,10 +1300,8 @@
 :- pred parse_aliasing(term, aliasing).
 :- mode parse_aliasing(in, out) is semidet.
 
-parse_aliasing(term__functor(term__atom("no_aliasing"), [], _),
-	no_aliasing).
-parse_aliasing(term__functor(term__atom("unknown_aliasing"), [], _),
-	unknown_aliasing).
+parse_aliasing(Term, Aliasing):- 
+	pa_alias_as__parse_user_declared_aliases(Term, Aliasing). 
 
 % parse a pragma foreign_code declaration
 

-------------- next part --------------
%-----------------------------------------------------------------------------%
% Copyright (C) 1993-1995, 1997-2001 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%-----------------------------------------------------------------------------%

% File: marray.m
% Main authors: fjh, bromage
% Stability: medium-low

% This module provides dynamically-sized one-dimensional marrays.
% Array indices start at zero.

% By default, the marray__set and marray__lookup procedures will check
% for bounds errors.  But for better performance, it is possible to
% disable some of the checking by compiling with `--intermodule-optimization'
% and with the C macro symbol `ML_OMIT_ARRAY_BOUNDS_CHECKS'
% defined, e.g. by using `MCFLAGS=--intermodule-optimization' and
% `CFLAGS=-DML_OMIT_ARRAY_BOUNDS_CHECKS' in your Mmakefile,
% or by compiling with the command
% `mmc --intermodule-optimization --cflags -DML_OMIT_ARRAY_BOUNDS_CHECKS'.
%
% For maximum performance, all bounds checking can be disabled by
% recompiling this module using `CFLAGS=-DML_OMIT_ARRAY_BOUNDS_CHECKS'
% or `mmc --cflags -DML_OMIT_ARRAY_BOUNDS_CHECKS' as above. You can
% either recompile the entire library, or just copy `marray.m' to your
% application's source directory and link with it directly instead of as
% part of the library.
%

% WARNING!
%
% Arrays are currently not unique objects - until this situation is
% resolved it is up to the programmer to ensure that marrays are used
% in such a way as to preserve correctness.  In the absence of mode
% reordering, one should therefore assume that evaluation will take
% place in left-to-right order.  For example, the following code will
% probably not work as expected (f is a function, A an marray, I an
% index, and X an appropriate value):
%
%       Y = f(A ^ elem(I) := X, A ^ elem(I))
%
% The compiler is likely to compile this as
%
%       V0 = A ^ elem(I) := X,
%       V1 = A ^ elem(I),
%       Y  = f(V0, V1)
%
% and will be unaware that the first line should be ordered
% *after* the second.  The safest thing to do is write things out
% by hand in the form
%
%       A0I = A0 ^ elem(I),
%       A1  = A0 ^ elem(I) := X,
%       Y   = f(A1, A0I)

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

:- module marray.
:- interface.
:- import_module list, std_util, random.

:- type marray(T).

:- inst marray(I) = bound(marray(I)).
:- inst marray == marray(ground).
:- inst marray_skel == marray(free).

	% XXX the current Mercury compiler doesn't support `ui' modes,
	% so to work-around that problem, we currently don't use
	% unique modes in this module.

% :- inst uniq_marray(I) = unique(marray(I)).
% :- inst uniq_marray == uniq_marray(unique).
:- inst uniq_marray(I) = bound(marray(I)). % XXX work-around
:- inst uniq_marray == uniq_marray(ground). % XXX work-around
:- inst uniq_marray_skel == uniq_marray(free).

:- mode marray_di == di(uniq_marray).
:- mode marray_uo == out(uniq_marray).
:- mode marray_ui == in(uniq_marray).

% :- inst mostly_uniq_marray(I) = mostly_unique(marray(I)).
% :- inst mostly_uniq_marray == mostly_uniq_marray(mostly_unique).
:- inst mostly_uniq_marray(I) = bound(marray(I)).	% XXX work-around
:- inst mostly_uniq_marray == mostly_uniq_marray(ground).	% XXX work-around
:- inst mostly_uniq_marray_skel == mostly_uniq_marray(free).

:- mode marray_mdi == mdi(mostly_uniq_marray).
:- mode marray_muo == out(mostly_uniq_marray).
:- mode marray_mui == in(mostly_uniq_marray).

%-----------------------------------------------------------------------------%

	% marray__make_empty_marray(Array) creates an marray of size zero
	% starting at lower bound 0.
:- pred marray__make_empty_marray(marray(T)).
:- mode marray__make_empty_marray(marray_uo) is det.

:- func marray__make_empty_marray = marray(T).
:- mode marray__make_empty_marray = marray_uo is det.

	% marray__init(Size, Init, Array) creates an marray
	% with bounds from 0 to Size-1, with each element initialized to Init.
:- pred marray__init(int, T, marray(T)).
:- mode marray__init(in, in, marray_uo) is det.

:- func marray__init(int, T) = marray(T).
:- mode marray__init(in, in) = marray_uo is det.

	% marray/1 is a function that constructs an marray from a list.
	% (It does the same thing as the predicate marray__from_list/2.)
	% The syntax `marray([...])' is used to represent marrays
	% for io__read, io__write, term_to_type, and type_to_term.
:- func marray(list(T)) = marray(T).
:- mode marray(in) = marray_uo is det.

%-----------------------------------------------------------------------------%

	% marray__min returns the lower bound of the marray.
	% Note: in this implementation, the lower bound is always zero.
:- pred marray__min(marray(_T), int).
:- mode marray__min(marray_ui, out) is det.
:- mode marray__min(in, out) is det.

:- func marray__min(marray(_T)) = int.
:- mode marray__min(marray_ui) = out is det.
:- mode marray__min(in) = out is det.

	% marray__max returns the upper bound of the marray.
:- pred marray__max(marray(_T), int).
:- mode marray__max(marray_ui, out) is det.
:- mode marray__max(in, out) is det.

:- func marray__max(marray(_T)) = int.
:- mode marray__max(marray_ui) = out is det.
:- mode marray__max(in) = out is det.

	% marray__size returns the length of the marray,
	% i.e. upper bound - lower bound + 1.
:- pred marray__size(marray(_T), int).
:- mode marray__size(marray_ui, out) is det.
:- mode marray__size(in, out) is det.

:- func marray__size(marray(_T)) = int.
:- mode marray__size(marray_ui) = out is det.
:- mode marray__size(in) = out is det.

	% marray__bounds returns the upper and lower bounds of an marray.
	% Note: in this implementation, the lower bound is always zero.
:- pred marray__bounds(marray(_T), int, int).
:- mode marray__bounds(marray_ui, out, out) is det.
:- mode marray__bounds(in, out, out) is det.

	% marray__in_bounds checks whether an index is in the bounds
	% of an marray.
:- pred marray__in_bounds(marray(_T), int).
:- mode marray__in_bounds(marray_ui, in) is semidet.
:- mode marray__in_bounds(in, in) is semidet.

%-----------------------------------------------------------------------------%

	% marray__lookup returns the Nth element of an marray.
	% It is an error if the index is out of bounds.
:- pred marray__lookup(marray(T), int, T).
:- mode marray__lookup(marray_ui, in, out) is det.
:- mode marray__lookup(in, in, out) is det.

:- func marray__lookup(marray(T), int) = T.
:- mode marray__lookup(marray_ui, in) = out is det.
:- mode marray__lookup(in, in) = out is det.

	% marray__semidet_lookup returns the Nth element of an marray.
	% It fails if the index is out of bounds.
:- pred marray__semidet_lookup(marray(T), int, T).
:- mode marray__semidet_lookup(marray_ui, in, out) is semidet.
:- mode marray__semidet_lookup(in, in, out) is semidet.

	% marray__set sets the nth element of an marray, and returns the
	% resulting marray (good opportunity for destructive update ;-).  
	% It is an error if the index is out of bounds.
:- pred marray__set(marray(T), int, T, marray(T)).
:- mode marray__set(marray_di, in, in, marray_uo) is det.

:- func marray__set(marray(T), int, T) = marray(T).
:- mode marray__set(marray_di, in, in) = marray_uo is det.

	% marray__semidet_set sets the nth element of an marray,
	% and returns the resulting marray.
	% It fails if the index is out of bounds.
:- pred marray__semidet_set(marray(T), int, T, marray(T)).
:- mode marray__semidet_set(marray_di, in, in, marray_uo) is semidet.

	% marray__slow_set sets the nth element of an marray,
	% and returns the resulting marray.  The initial marray is not
	% required to be unique, so the implementation may not be able to use
	% destructive update.
	% It is an error if the index is out of bounds.
:- pred marray__slow_set(marray(T), int, T, marray(T)).
:- mode marray__slow_set(marray_ui, in, in, marray_uo) is det.
:- mode marray__slow_set(in, in, in, marray_uo) is det.

:- func marray__slow_set(marray(T), int, T) = marray(T).
:- mode marray__slow_set(marray_ui, in, in) = marray_uo is det.
:- mode marray__slow_set(in, in, in) = marray_uo is det.

	% marray__semidet_slow_set sets the nth element of an marray,
	% and returns the resulting marray.  The initial marray is not
	% required to be unique, so the implementation may not be able to use
	% destructive update.
	% It fails if the index is out of bounds.
:- pred marray__semidet_slow_set(marray(T), int, T, marray(T)).
:- mode marray__semidet_slow_set(marray_ui, in, in, marray_uo) is semidet.
:- mode marray__semidet_slow_set(in, in, in, marray_uo) is semidet.

	% Field selection for marrays.
	% Array ^ elem(Index) = marray__lookup(Array, Index).
:- func marray__elem(int, marray(T)) = T.
:- mode marray__elem(in, marray_ui) = out is det.
:- mode marray__elem(in, in) = out is det.

	% Field update for marrays.
	% (Array ^ elem(Index) := Value) = marray__set(Array, Index, Value).
:- func 'marray__elem :='(int, marray(T), T) = marray(T).
:- mode 'marray__elem :='(in, marray_ui, in) = marray_uo is det.

%-----------------------------------------------------------------------------%

	% marray__copy(Array0, Array):
	% Makes a new unique copy of an marray.
:- pred marray__copy(marray(T), marray(T)).
:- mode marray__copy(marray_ui, marray_uo) is det.
:- mode marray__copy(in, marray_uo) is det.

:- func marray__copy(marray(T)) = marray(T).
:- mode marray__copy(marray_ui) = marray_uo is det.
:- mode marray__copy(in) = marray_uo is det.

	% marray__resize(Array0, Size, Init, Array):
	% The marray is expanded or shrunk to make it fit
	% the new size `Size'.  Any new entries are filled
	% with `Init'.
:- pred marray__resize(marray(T), int, T, marray(T)).
:- mode marray__resize(marray_di, in, in, marray_uo) is det.

:- func marray__resize(marray(T), int, T) = marray(T).
:- mode marray__resize(marray_di, in, in) = marray_uo is det.

	% marray__shrink(Array0, Size, Array):
	% The marray is shrunk to make it fit the new size `Size'.
	% It is an error if `Size' is larger than the size of `Array0'.
:- pred marray__shrink(marray(T), int, marray(T)).
:- mode marray__shrink(marray_di, in, marray_uo) is det.

:- func marray__shrink(marray(T), int) = marray(T).
:- mode marray__shrink(marray_di, in) = marray_uo is det.

	% marray__from_list takes a list,
	% and returns an marray containing those elements in
	% the same order that they occured in the list.
:- pred marray__from_list(list(T), marray(T)).
:- mode marray__from_list(in, marray_uo) is det.

:- func marray__from_list(list(T)) = marray(T).
:- mode marray__from_list(in) = marray_uo is det.

	% marray__to_list takes an marray and returns a list containing
	% the elements of the marray in the same order that they
	% occurred in the marray.
:- pred marray__to_list(marray(T), list(T)).
:- mode marray__to_list(marray_ui, out) is det.
:- mode marray__to_list(in, out) is det.

:- func marray__to_list(marray(T)) = list(T).
:- mode marray__to_list(marray_ui) = out is det.
:- mode marray__to_list(in) = out is det.

	% marray__fetch_items takes an marray and a lower and upper
	% index, and places those items in the marray between these
	% indices into a list.  It is an error if either index is
	% out of bounds.
:- pred marray__fetch_items(marray(T), int, int, list(T)).
:- mode marray__fetch_items(in, in, in, out) is det.

:- func marray__fetch_items(marray(T), int, int) = list(T).
:- mode marray__fetch_items(marray_ui, in, in) = out is det.
:- mode marray__fetch_items(in, in, in) = out is det.

	% marray__bsearch takes an marray, an element to be found
	% and a comparison predicate and returns the position of
	% the element in the marray.  Assumes the marray is in sorted
	% order.  Fails if the element is not present.  If the
	% element to be found appears multiple times, the index of
	% the first occurrence is returned.
:- pred marray__bsearch(marray(T), T, pred(T, T, comparison_result),
			maybe(int)).
:- mode marray__bsearch(marray_ui, in, pred(in, in, out) is det, out) is det.
:- mode marray__bsearch(in, in, pred(in, in, out) is det, out) is det.

:- func marray__bsearch(marray(T), T, func(T,T) = comparison_result) = maybe(int).
:- mode marray__bsearch(marray_ui, in, func(in,in) = out is det) = out is det.
:- mode marray__bsearch(in, in, func(in,in) = out is det) = out is det.

	% marray__map(Closure, OldArray, NewArray) applys `Closure' to
	% each of the elements of `OldArray' to create `NewArray'.
:- pred marray__map(pred(T1, T2), marray(T1), marray(T2)).
:- mode marray__map(pred(in, out) is det, marray_di, marray_uo) is det.

:- func marray__map(func(T1) = T2, marray(T1)) = marray(T2).
:- mode marray__map(func(in) = out is det, marray_di) = marray_uo is det.

:- func marray_compare(marray(T), marray(T)) = comparison_result.
:- mode marray_compare(in, in) = out is det.

	% marray__sort(Array) returns a version of Array sorted
	% into ascending order.
	%
	% This sort is not stable.  That is, elements that
	% compare/3 decides are equal will appear together in
	% the sorted marray, but not necessarily in the same
	% order in which they occurred in the input marray.
	% This is primarily only an issue with types with
	% user-defined equivalence for which `equivalent'
	% objects are otherwise distinguishable.
	%
:- func marray__sort(marray(T)) = marray(T).
:- mode marray__sort(marray_di) = marray_uo is det.

	% marray__foldl(Fn, Array, X) is equivalent to
	% 	list__foldl(Fn, marray__to_list(Array), X)
	% but more efficient.
	%
:- func marray__foldl(func(T1, T2) = T2, marray(T1), T2) = T2.
:- mode marray__foldl(func(in, in) = out is det, marray_ui, in) = out is det.
:- mode marray__foldl(func(in, in) = out is det, in, in) = out is det.
:- mode marray__foldl(func(in, di) = uo is det, marray_ui, di) = uo is det.
:- mode marray__foldl(func(in, di) = uo is det, in, di) = uo is det.

	% marray__foldr(Fn, Array, X) is equivalent to
	% 	list__foldr(Fn, marray__to_list(Array), X)
	% but more efficient.
	%
:- func marray__foldr(func(T1, T2) = T2, marray(T1), T2) = T2.
:- mode marray__foldr(func(in, in) = out is det, marray_ui, in) = out is det.
:- mode marray__foldr(func(in, in) = out is det, in, in) = out is det.
:- mode marray__foldr(func(in, di) = uo is det, marray_ui, di) = uo is det.
:- mode marray__foldr(func(in, di) = uo is det, in, di) = uo is det.

	% marray__random_permutation(A0, A, RS0, RS) permutes the elements in
	% A0 given random seed RS0 and returns the permuted marray in A
	% and the next random seed in RS.
	%
:- pred marray__random_permutation(marray(T), marray(T),
		random__supply, random__supply).
:- mode marray__random_permutation(marray_di, marray_uo, mdi, muo) is det.

%-----------------------------------------------------------------------------%
:- implementation.

% Everything beyond here is not intended as part of the public interface,
% and will not appear in the Mercury Library Reference Manual.

%-----------------------------------------------------------------------------%
:- interface.

	% The following predicates have to be declared in the interface,
	% otherwise dead code elimination will remove them.
	% But they're an implementation detail; user code should just
	% use the generic versions.

	% unify/2 for marrays

:- pred marray_equal(marray(T), marray(T)).
:- mode marray_equal(in, in) is semidet.

	% compare/3 for marrays

:- pred marray_compare(comparison_result, marray(T), marray(T)).
:- mode marray_compare(out, in, in) is det.

%-----------------------------------------------------------------------------%

:- implementation.
:- import_module int.

/****
lower bounds other than zero are not supported
	% marray__resize takes an marray and new lower and upper bounds.
	% the marray is expanded or shrunk at each end to make it fit
	% the new bounds.
:- pred marray__resize(marray(T), int, int, marray(T)).
:- mode marray__resize(in, in, in, out) is det.
****/

%-----------------------------------------------------------------------------%

% Arrays are implemented using the C interface.

% The C type which defines the representation of marrays is
% MR_ArrayType; it is defined in runtime/mercury_library_types.h.

%-----------------------------------------------------------------------------%

:- pragma foreign_decl("C", "
#ifdef MR_HIGHLEVEL_CODE
  bool MR_CALL mercury__marray__do_unify__marray_1_0(
  	MR_Mercury_Type_Info type_info, MR_Box x, MR_Box y);
  bool MR_CALL mercury__marray____Unify____marray_1_0(
	MR_Mercury_Type_Info type_info, MR_Array x, MR_Array y);
  void MR_CALL mercury__marray__do_compare__marray_1_0(MR_Mercury_Type_Info
 	 type_info, MR_Comparison_Result *result, MR_Box x, MR_Box y);
  void MR_CALL mercury__marray____Compare____marray_1_0(MR_Mercury_Type_Info
	type_info, MR_Comparison_Result *result, MR_Array x, MR_Array y);
#endif
").

:- pragma foreign_code("C", "

#ifdef MR_HIGHLEVEL_CODE

MR_define_type_ctor_info(marray, marray, 1, MR_TYPECTOR_REP_ARRAY);

/* forward decl, to suppress gcc -Wmissing-decl warning */
void sys_init_marray_module_builtins(void);

/*
** This empty initialization function is needed just to
** match the one that we use for LLDS grades.
*/
void
sys_init_marray_module_builtins(void)
{
	/* no initialization needed */
}

bool MR_CALL
mercury__marray__do_unify__marray_1_0(MR_Mercury_Type_Info type_info,
	MR_Box x, MR_Box y)
{
	return mercury__marray____Unify____marray_1_0(
		type_info, (MR_Array) x, (MR_Array) y);
}

bool MR_CALL
mercury__marray____Unify____marray_1_0(MR_Mercury_Type_Info type_info,
	MR_Array x, MR_Array y)
{
	return mercury__marray__marray_equal_2_p_0(type_info, x, y);
}

void MR_CALL
mercury__marray__do_compare__marray_1_0(
	MR_Mercury_Type_Info type_info, MR_Comparison_Result *result,
	MR_Box x, MR_Box y)
{
	mercury__marray____Compare____marray_1_0(
		type_info, result, (MR_Array) x, (MR_Array) y);
}

void MR_CALL
mercury__marray____Compare____marray_1_0(
	MR_Mercury_Type_Info type_info, MR_Comparison_Result *result,
	MR_Array x, MR_Array y)
{
	mercury__marray__marray_compare_3_p_0(type_info, result, x, y);
}

#else

MR_DEFINE_BUILTIN_TYPE_CTOR_INFO(marray, marray, 1, MR_TYPECTOR_REP_ARRAY);

MR_declare_entry(mercury__marray__marray_equal_2_0);
MR_declare_entry(mercury__marray__marray_compare_3_0);

MR_BEGIN_MODULE(marray_module_builtins)
	MR_init_entry(mercury____Unify___marray__marray_1_0);
	MR_init_entry(mercury____Compare___marray__marray_1_0);
MR_BEGIN_CODE

MR_define_entry(mercury____Unify___marray__marray_1_0);
	/* this is implemented in Mercury, not hand-coded low-level C */
	MR_tailcall(MR_ENTRY(mercury__marray__marray_equal_2_0),
		MR_ENTRY(mercury____Unify___marray__marray_1_0));

MR_define_entry(mercury____Compare___marray__marray_1_0);
	/* this is implemented in Mercury, not hand-coded low-level C */
	MR_tailcall(MR_ENTRY(mercury__marray__marray_compare_3_0),
		MR_ENTRY(mercury____Compare___marray__marray_1_0));

MR_END_MODULE

/* Ensure that the initialization code for the above module gets run. */
/*
INIT sys_init_marray_module_builtins
*/

MR_MODULE_STATIC_OR_EXTERN MR_ModuleFunc marray_module_builtins;

void sys_init_marray_module_builtins(void);
		/* suppress gcc -Wmissing-decl warning */
void sys_init_marray_module_builtins(void) {
	marray_module_builtins();
	MR_INIT_TYPE_CTOR_INFO(
		mercury_data_marray__type_ctor_info_marray_1,
		marray__marray_1_0);
	MR_register_type_ctor_info(
		&mercury_data_marray__type_ctor_info_marray_1);
}

#endif /* ! MR_HIGHLEVEL_CODE */

").

:- pragma foreign_code("MC++", "
    MR_DEFINE_BUILTIN_TYPE_CTOR_INFO(marray, marray, 1, MR_TYPECTOR_REP_ARRAY)

    static int
    __Unify____marray_1_0(MR_Word type_info, 
		MR_Word x, MR_Word y)
    {
            mercury::runtime::Errors::SORRY(""unify for marray"");
            return 0;
    }

    static void
    __Compare____marray_1_0(
            MR_Word type_info, MR_Word_Ref result, MR_Word x, MR_Word y)
    {
            mercury::runtime::Errors::SORRY(""compare for marray"");
    }

    static int
    do_unify__marray_1_0(MR_Word type_info, MR_Box x, MR_Box y)
    {
            return mercury::marray__c_code::__Unify____marray_1_0(
                    type_info, 
                    dynamic_cast<MR_Array>(x),
                    dynamic_cast<MR_Array>(y));
    }

    static void
    do_compare__marray_1_0(
            MR_Word type_info, MR_Word_Ref result, MR_Box x, MR_Box y)
    {
            mercury::marray__c_code::__Compare____marray_1_0(
                    type_info, result, 
                    dynamic_cast<MR_Array>(x),
                    dynamic_cast<MR_Array>(y));
    }
").


%-----------------------------------------------------------------------------%

	% unify/2 for marrays

marray_equal(Array1, Array2) :-
	marray__size(Array1, Size),
	marray__size(Array2, Size),
	marray__equal_elements(0, Size, Array1, Array2).

:- pred marray__equal_elements(int, int, marray(T), marray(T)).
:- mode marray__equal_elements(in, in, in, in) is semidet.

marray__equal_elements(N, Size, Array1, Array2) :-
	( N = Size ->
		true
	;
		marray__lookup(Array1, N, Elem),
		marray__lookup(Array2, N, Elem),
		N1 is N + 1,
		marray__equal_elements(N1, Size, Array1, Array2)
	).

	% compare/3 for marrays

marray_compare(Result, Array1, Array2) :-
	marray__size(Array1, Size1),
	marray__size(Array2, Size2),
	compare(SizeResult, Size1, Size2),
	( SizeResult = (=) ->
		marray__compare_elements(0, Size1, Array1, Array2, Result)
	;
		Result = SizeResult
	).

:- pred marray__compare_elements(int, int, marray(T), marray(T),
			comparison_result).
:- mode marray__compare_elements(in, in, in, in, out) is det.

marray__compare_elements(N, Size, Array1, Array2, Result) :-
	( N = Size ->
		Result = (=)
	;
		marray__lookup(Array1, N, Elem1),
		marray__lookup(Array2, N, Elem2),
		compare(ElemResult, Elem1, Elem2),
		( ElemResult = (=) ->
			N1 is N + 1,
			marray__compare_elements(N1, Size, Array1, Array2,
				Result)
		;
			Result = ElemResult
		)
	).

%-----------------------------------------------------------------------------%

:- pragma foreign_decl("C", "
#include ""mercury_heap.h""		/* for MR_maybe_record_allocation() */
#include ""mercury_library_types.h""	/* for MR_ArrayType */
#include ""mercury_misc.h""		/* for MR_fatal_error() */
").

:- pragma foreign_decl("C", "
MR_ArrayType *ML_make_marray(MR_Integer size, MR_Word item);
").

:- pragma foreign_code("C", "
MR_ArrayType *
ML_make_marray(MR_Integer size, MR_Word item)
{
	MR_Integer i;
	MR_ArrayType *marray;

	marray = MR_make_marray(size);
	marray->size = size;
	for (i = 0; i < size; i++) {
		marray->elements[i] = item;
	}
	return marray;
}
").

:- pragma foreign_proc("C", 
		marray__init(Size::in, Item::in, Array::marray_uo),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	MR_maybe_record_allocation(Size + 1, MR_PROC_LABEL, ""marray:marray/1"");
	Array = (MR_Word) ML_make_marray(Size, Item);
").

:- pragma foreign_proc("C",
		marray__make_empty_marray(Array::marray_uo),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	MR_maybe_record_allocation(1, MR_PROC_LABEL, ""marray:marray/1"");
	Array = (MR_Word) ML_make_marray(0, 0);
").

:- pragma foreign_proc("MC++", 
		marray__init(Size::in, Item::in, Array::marray_uo),
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
		// XXX still need to do init
	Array = (MR_Word) System::Array::CreateInstance(Item->GetType(), Size);
").

:- pragma foreign_proc("MC++",
		marray__make_empty_marray(Array::marray_uo),
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
		// XXX this is inefficient.
	Array = (MR_Word) 
		System::Array::CreateInstance(
			(new System::Object)->GetType(), 0);
").


%-----------------------------------------------------------------------------%

:- pragma foreign_proc("C",
		marray__min(Array::marray_ui, Min::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	/* Array not used */
	Min = 0;
").
:- pragma foreign_proc("C", 
		marray__min(Array::in, Min::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	/* Array not used */
	Min = 0;
").

:- pragma foreign_proc("MC++",
		marray__min(Array::marray_ui, Min::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	/* Array not used */
	Min = 0;
").
:- pragma foreign_proc("MC++", 
		marray__min(Array::in, Min::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	/* Array not used */
	Min = 0;
").

:- pragma foreign_proc("C", 
		marray__max(Array::marray_ui, Max::out), 
		[will_not_call_mercury, thread_safe, no_aliasing], "
	Max = ((MR_ArrayType *)Array)->size - 1;
").
:- pragma foreign_proc("C",
		marray__max(Array::in, Max::out), 
		[will_not_call_mercury, thread_safe, no_aliasing], "
	Max = ((MR_ArrayType *)Array)->size - 1;
").
:- pragma foreign_proc("MC++", 
		marray__max(Array::marray_ui, Max::out), 
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	Max = Array->get_Length() - 1;
").
:- pragma foreign_proc("MC++",
		marray__max(Array::in, Max::out), 
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	Max = Array->get_Length() - 1;
").


marray__bounds(Array, Min, Max) :-
	marray__min(Array, Min),
	marray__max(Array, Max).

%-----------------------------------------------------------------------------%

:- pragma foreign_proc("C",
		marray__size(Array::marray_ui, Max::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	Max = ((MR_ArrayType *)Array)->size;
").
:- pragma foreign_proc("C",
		marray__size(Array::in, Max::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	Max = ((MR_ArrayType *)Array)->size;
").

:- pragma foreign_proc("MC++",
		marray__size(Array::marray_ui, Max::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	Max = Array->get_Length() - 1;
").
:- pragma foreign_proc("MC++",
		marray__size(Array::in, Max::out),
		[will_not_call_mercury, thread_safe, no_aliasing], "
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	Max = Array->get_Length() - 1;
").


%-----------------------------------------------------------------------------%

marray__in_bounds(Array, Index) :-
	marray__bounds(Array, Min, Max),
	Min =< Index, Index =< Max.

marray__semidet_lookup(Array, Index, Item) :-
	marray__in_bounds(Array, Index),
	marray__lookup(Array, Index, Item).

marray__semidet_set(Array0, Index, Item, Array) :-
	marray__in_bounds(Array0, Index),
	marray__set(Array0, Index, Item, Array).

marray__semidet_slow_set(Array0, Index, Item, Array) :-
	marray__in_bounds(Array0, Index),
	marray__slow_set(Array0, Index, Item, Array).

marray__slow_set(Array0, Index, Item, Array) :-
	marray__copy(Array0, Array1),
	marray__set(Array1, Index, Item, Array).

%-----------------------------------------------------------------------------%

:- pragma foreign_proc("C",
		marray__lookup(Array::marray_ui, Index::in, Item::out),
		[will_not_call_mercury, thread_safe, 
		alias(yes(marray(T), int, I), 
			[ cel(Array, [T]) - cel(Item, []) ]) ], "{
	MR_ArrayType *marray = (MR_ArrayType *)Array;
#ifndef ML_OMIT_ARRAY_BOUNDS_CHECKS
	if ((MR_Unsigned) Index >= (MR_Unsigned) marray->size) {
		MR_fatal_error(""marray__lookup: marray index out of bounds"");
	}
#endif
	Item = marray->elements[Index];
}").
:- pragma foreign_proc("C",
		marray__lookup(Array::in, Index::in, Item::out),
		[will_not_call_mercury, thread_safe, 
		alias(yes(marray(T), int, I), 
			[ cel(Array, [T]) - cel(Item, []) ]) ], "{
	MR_ArrayType *marray = (MR_ArrayType *)Array;
#ifndef ML_OMIT_ARRAY_BOUNDS_CHECKS
	if ((MR_Unsigned) Index >= (MR_Unsigned) marray->size) {
		MR_fatal_error(""marray__lookup: marray index out of bounds"");
	}
#endif
	Item = marray->elements[Index];
}").

:- pragma foreign_proc("MC++",
		marray__lookup(Array::marray_ui, Index::in, Item::out),
		[will_not_call_mercury, thread_safe, 
		alias(yes(marray(T), int, I), 
			[ cel(Array, [T]) - cel(Item, []) ]) ], "{
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	Item = Array->GetValue(Index);
}").
:- pragma foreign_proc("MC++",
		marray__lookup(Array::in, Index::in, Item::out),
		[will_not_call_mercury, thread_safe, 
		alias(yes(marray(T), int, I), 
			[ cel(Array, [T]) - cel(Item, []) ]) ], "{
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
	Item = Array->GetValue(Index);
}").


%-----------------------------------------------------------------------------%

:- pragma foreign_proc("C",
		marray__set(Array0::marray_di, Index::in,
		Item::in, Array::marray_uo),
		[will_not_call_mercury, thread_safe, 
		alias( yes(marray(T), int, T, marray(T)), 
			[ cel(Item,[]) - cel(Array, [T]) ]) ], "{
	MR_ArrayType *marray = (MR_ArrayType *)Array0;
#ifndef ML_OMIT_ARRAY_BOUNDS_CHECKS
	if ((MR_Unsigned) Index >= (MR_Unsigned) marray->size) {
		MR_fatal_error(""marray__set: marray index out of bounds"");
	}
#endif
	marray->elements[Index] = Item;	/* destructive update! */
	Array = Array0;
}").

:- pragma foreign_proc("MC++",
		marray__set(Array0::marray_di, Index::in,
		Item::in, Array::marray_uo),
		[will_not_call_mercury, thread_safe, 
		alias( yes(marray(T), int, T, marray(T)), 
			[ cel(Item,[]) - cel(Array, [T]) ]) ], "{
	Array0->SetValue(Item, Index);	/* destructive update! */
	Array = Array0;
        mercury::runtime::Errors::SORRY(""foreign code for this predicate"");
}").


%-----------------------------------------------------------------------------%

:- pragma foreign_decl("C", "
MR_ArrayType * ML_resize_marray(MR_ArrayType *old_marray,
					MR_Integer marray_size, MR_Word item);
").

:- pragma foreign_code("C", "
MR_ArrayType *
ML_resize_marray(MR_ArrayType *old_marray, MR_Integer marray_size,
				MR_Word item)
{
	MR_Integer i;
	MR_ArrayType* marray;
	MR_Integer elements_to_copy;

	elements_to_copy = old_marray->size;
	if (elements_to_copy == marray_size) return old_marray;
	if (elements_to_copy > marray_size) {
		elements_to_copy = marray_size;
	}

	marray = (MR_ArrayType *) MR_GC_NEW_ARRAY(MR_Word, marray_size + 1);
	marray->size = marray_size;
	for (i = 0; i < elements_to_copy; i++) {
		marray->elements[i] = old_marray->elements[i];
	}
	for (; i < marray_size; i++) {
		marray->elements[i] = item;
	}

	/*
	** since the mode on the old marray is `marray_di', it is safe to
	** deallocate the storage for it
	*/
	MR_GC_free(old_marray);

	return marray;
}
").

:- pragma foreign_proc("C",
		marray__resize(Array0::marray_di, Size::in, Item::in,
		Array::marray_uo), 
		[will_not_call_mercury, thread_safe, 
		alias( yes(marray(T), int, T, marray(T)), 
			[ cel(Item,[]) - cel(Array, [T]) ]) ], "
	MR_maybe_record_allocation(Size + 1, MR_PROC_LABEL, ""marray:marray/1"");
	Array = (MR_Word) ML_resize_marray(
				(MR_ArrayType *) Array0, Size, Item);
").
:- pragma foreign_proc("MC++",
		marray__resize(_Array0::marray_di, _Size::in, _Item::in,
		_Array::marray_uo), [will_not_call_mercury, thread_safe], "
	mercury::runtime::Errors::SORRY(""foreign code for this function"");
").


%-----------------------------------------------------------------------------%

:- pragma foreign_decl("C", "
MR_ArrayType * ML_shrink_marray(MR_ArrayType *old_marray,
					MR_Integer marray_size);
").

:- pragma foreign_code("C", "
MR_ArrayType *
ML_shrink_marray(MR_ArrayType *old_marray, MR_Integer marray_size)
{
	MR_Integer i;
	MR_ArrayType* marray;
	MR_Integer old_marray_size;

	old_marray_size = old_marray->size;
	if (old_marray_size == marray_size) return old_marray;
	if (old_marray_size < marray_size) {
		MR_fatal_error(
			""marray__shrink: can't shrink to a larger size"");
	}

	marray = (MR_ArrayType *) MR_GC_NEW_ARRAY(MR_Word, marray_size + 1);
	marray->size = marray_size;
	for (i = 0; i < marray_size; i++) {
		marray->elements[i] = old_marray->elements[i];
	}

	/*
	** since the mode on the old marray is `marray_di', it is safe to
	** deallocate the storage for it
	*/
	MR_GC_free(old_marray);

	return marray;
}
").

:- pragma foreign_proc("C",
		marray__shrink(Array0::marray_di, Size::in, Array::marray_uo),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	MR_maybe_record_allocation(Size + 1, MR_PROC_LABEL, ""marray:marray/1"");
	Array = (MR_Word) ML_shrink_marray(
				(MR_ArrayType *) Array0, Size);
").
:- pragma foreign_proc("MC++",
		marray__shrink(_Array0::marray_di, _Size::in, _Array::marray_uo),
		[will_not_call_mercury, thread_safe], "
	mercury::runtime::Errors::SORRY(""foreign code for this function"");
").


%-----------------------------------------------------------------------------%

:- pragma foreign_decl("C", "
MR_ArrayType *ML_copy_marray(MR_ArrayType *old_marray);
").

:- pragma foreign_code("C", "
MR_ArrayType *
ML_copy_marray(MR_ArrayType *old_marray)
{
	/*
	** Any changes to this function will probably also require
	** changes to deepcopy() in runtime/deep_copy.c.
	*/

	MR_Integer i;
	MR_ArrayType* marray;
	MR_Integer marray_size;

	marray_size = old_marray->size;
	marray = MR_make_marray(marray_size);
	marray->size = marray_size;
	for (i = 0; i < marray_size; i++) {
		marray->elements[i] = old_marray->elements[i];
	}
	return marray;
}
").

:- pragma foreign_proc("C",
		marray__copy(Array0::marray_ui, Array::marray_uo),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	MR_maybe_record_allocation((((MR_ArrayType *) Array0)->size) + 1,
		MR_PROC_LABEL, ""marray:marray/1"");
	Array = (MR_Word) ML_copy_marray((MR_ArrayType *) Array0);
").

:- pragma foreign_proc("C",
		marray__copy(Array0::in, Array::marray_uo),
		[will_not_call_mercury, thread_safe, no_aliasing], "
	MR_maybe_record_allocation((((MR_ArrayType *) Array0)->size) + 1,
		MR_PROC_LABEL, ""marray:marray/1"");
	Array = (MR_Word) ML_copy_marray((MR_ArrayType *) Array0);
").

:- pragma foreign_proc("MC++",
		marray__copy(Array0::marray_ui, Array::marray_uo),
		[will_not_call_mercury, thread_safe], "
		// XXX need to deep copy it
	mercury::runtime::Errors::SORRY(""foreign code for this function"");
	Array = Array0;

").

:- pragma foreign_proc("MC++",
		marray__copy(Array0::in, Array::marray_uo),
		[will_not_call_mercury, thread_safe], "
	mercury::runtime::Errors::SORRY(""foreign code for this function"");
		// XXX need to deep copy it
	Array = Array0;
").

%-----------------------------------------------------------------------------%

marray(List) = Array :-
	marray__from_list(List, Array).

marray__from_list([], Array) :-
	marray__make_empty_marray(Array).
marray__from_list(List, Array) :-
        List = [ Head | Tail ],
        list__length(List, Len),
        marray__init(Len, Head, Array0),
        marray__insert_items(Tail, 1, Array0, Array).

%-----------------------------------------------------------------------------%

:- pred marray__insert_items(list(T), int, marray(T), marray(T)).
:- mode marray__insert_items(in, in, marray_di, marray_uo) is det.

marray__insert_items([], _N, Array, Array).
marray__insert_items([Head|Tail], N, Array0, Array) :-
        marray__set(Array0, N, Head, Array1),
        N1 is N + 1,
        marray__insert_items(Tail, N1, Array1, Array).

%-----------------------------------------------------------------------------%

marray__to_list(Array, List) :-
        marray__bounds(Array, Low, High),
        marray__fetch_items(Array, Low, High, List).

%-----------------------------------------------------------------------------%

marray__fetch_items(Array, Low, High, List) :-
	List = foldr_0(func(X, Xs) = [X | Xs], Array, [], Low, High).

%-----------------------------------------------------------------------------%

marray__bsearch(A, El, Compare, Result) :-
	marray__bounds(A, Lo, Hi),
	marray__bsearch_2(A, Lo, Hi, El, Compare, Result).

:- pred marray__bsearch_2(marray(T), int, int, T,
			pred(T, T, comparison_result), maybe(int)).
:- mode marray__bsearch_2(in, in, in, in, pred(in, in, out) is det,
				out) is det.
marray__bsearch_2(Array, Lo, Hi, El, Compare, Result) :-
	Width is Hi - Lo,

	% If Width < 0, there is no range left.
	( Width < 0 ->
	    Result = no
	;
	    % If Width == 0, we may just have found our element.
	    % Do a Compare to check.
	    ( Width = 0 ->
	        marray__lookup(Array, Lo, X),
	        ( call(Compare, El, X, (=)) ->
		    Result = yes(Lo)
	        ;
		    Result = no
	        )
	    ;
	        % Otherwise find the middle element of the range
	        % and check against that.
	        Mid is (Lo + Hi) >> 1,	% `>> 1' is hand-optimized `div 2'.
	        marray__lookup(Array, Mid, XMid),
	        call(Compare, XMid, El, Comp),
	        ( Comp = (<),
		    Mid1 is Mid + 1,
		    marray__bsearch_2(Array, Mid1, Hi, El, Compare, Result)
	        ; Comp = (=),
		    marray__bsearch_2(Array, Lo, Mid, El, Compare, Result)
	        ; Comp = (>),
		    Mid1 is Mid - 1,
		    marray__bsearch_2(Array, Lo, Mid1, El, Compare, Result)
	        )
	    )
	).

%-----------------------------------------------------------------------------%

marray__map(Closure, OldArray, NewArray) :-
	( marray__semidet_lookup(OldArray, 0, Elem0) ->
		marray__size(OldArray, Size),
		call(Closure, Elem0, Elem),
		marray__init(Size, Elem, NewArray0),
		marray__map_2(1, Size, Closure, OldArray,
		NewArray0, NewArray)
	;
		marray__make_empty_marray(NewArray)
	).

:- pred marray__map_2(int, int, pred(T1, T2), marray(T1), marray(T2), marray(T2)).
:- mode marray__map_2(in, in, pred(in, out) is det, in, marray_di, marray_uo)
		is det.

marray__map_2(N, Size, Closure, OldArray, NewArray0, NewArray) :-
	( N >= Size ->
		NewArray = NewArray0
	;
		marray__lookup(OldArray, N, OldElem),
		Closure(OldElem, NewElem),
		marray__set(NewArray0, N, NewElem, NewArray1),
		marray__map_2(N + 1, Size, Closure, OldArray,
		NewArray1, NewArray)
	).

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
% Ralph Becket <rwab1 at cam.sri.com> 24/04/99
%	Function forms added.

marray__make_empty_marray = A :-
	marray__make_empty_marray(A).

marray__init(N, X) = A :-
	marray__init(N, X, A).

marray__min(A) = N :-
	marray__min(A, N).

marray__max(A) = N :-
	marray__max(A, N).

marray__size(A) = N :-
	marray__size(A, N).

marray__lookup(A, N) = X :-
	marray__lookup(A, N, X).

marray__set(A1, N, X) = A2 :-
	marray__set(A1, N, X, A2).

marray__slow_set(A1, N, X) = A2 :-
	marray__slow_set(A1, N, X, A2).

marray__copy(A1) = A2 :-
	marray__copy(A1, A2).

marray__resize(A1, N, X) = A2 :-
	marray__resize(A1, N, X, A2).

marray__shrink(A1, N) = A2 :-
	marray__shrink(A1, N, A2).

marray__from_list(Xs) = A :-
	marray__from_list(Xs, A).

marray__to_list(A) = Xs :-
	marray__to_list(A, Xs).

marray__fetch_items(A, N1, N2) = Xs :-
	marray__fetch_items(A, N1, N2, Xs).

marray__bsearch(A, X, F) = MN :-
	P = ( pred(X1::in, X2::in, C::out) is det :- C = F(X1, X2) ),
	marray__bsearch(A, X, P, MN).

marray__map(F, A1) = A2 :-
	P = ( pred(X::in, Y::out) is det :- Y = F(X) ),
	marray__map(P, A1, A2).

marray_compare(A1, A2) = C :-
	marray_compare(C, A1, A2).

marray__elem(Index, Array) = marray__lookup(Array, Index).

'marray__elem :='(Index, Array, Value) = marray__set(Array, Index, Value).

% ---------------------------------------------------------------------------- %

    % marray__sort/1 has type specialised versions for marrays of
    % ints and strings on the expectation that these constitute
    % the common case and are hence worth providing a fast-path.
    %
    % Experiments indicate that type specialisation improves
    % marray__sort/1 by a factor of 30-40%.
    %
:- pragma type_spec(marray__sort/1, T = int).
:- pragma type_spec(marray__sort/1, T = string).

marray__sort(A) = samsort_submarray(A, marray__min(A), marray__max(A)).

%------------------------------------------------------------------------------%

marray__random_permutation(A0, A, RS0, RS) :-
	Lo = marray__min(A0),
	Hi = marray__max(A0),
	Sz = marray__size(A0),
	permutation_2(Lo, Lo, Hi, Sz, A0, A, RS0, RS).



:- pred permutation_2(int, int, int, int, marray(T), marray(T),
		random__supply, random__supply).
:- mode permutation_2(in, in, in, in, marray_di, marray_uo, mdi, muo) is det.

permutation_2(I, Lo, Hi, Sz, A0, A, RS0, RS) :-
	( if I > Hi then
		A  = A0,
		RS = RS0
	  else
	  	random__random(R, RS0, RS1),
	  	J  = Lo + (R `rem` Sz),
		A1 = swap_elems(A0, I, J),
		permutation_2(I + 1, Lo, Hi, Sz, A1, A, RS1, RS)
	).

%------------------------------------------------------------------------------%

:- func swap_elems(marray(T), int, int) = marray(T).
:- mode swap_elems(marray_di, in, in) = marray_uo is det.

swap_elems(A0, I, J) = A :-
	XI = A0 ^ elem(I),
	XJ = A0 ^ elem(J),
	A  = ((A0 ^ elem(I) := XJ)
		  ^ elem(J) := XI).

% ---------------------------------------------------------------------------- %

marray__foldl(Fn, A, X) =
	foldl_0(Fn, A, X, marray__min(A), marray__max(A)).



:- func foldl_0(func(T1, T2) = T2, marray(T1), T2, int, int) = T2.
:- mode foldl_0(func(in, in) = out is det, marray_ui, in, in, in) = out is det.
:- mode foldl_0(func(in, in) = out is det, in, in, in, in) = out is det.
:- mode foldl_0(func(in, di) = uo is det, marray_ui, di, in, in) = uo is det.
:- mode foldl_0(func(in, di) = uo is det, in, di, in, in) = uo is det.

foldl_0(Fn, A, X, I, Max) =
	( if Max < I	then X
			else foldl_0(Fn, A, Fn(A ^ elem(I), X), I + 1, Max)
	).

% ---------------------------------------------------------------------------- %

marray__foldr(Fn, A, X) =
	foldr_0(Fn, A, X, marray__min(A), marray__max(A)).



:- func foldr_0(func(T1, T2) = T2, marray(T1), T2, int, int) = T2.
:- mode foldr_0(func(in, in) = out is det, marray_ui, in, in, in) = out is det.
:- mode foldr_0(func(in, in) = out is det, in, in, in, in) = out is det.
:- mode foldr_0(func(in, di) = uo is det, marray_ui, di, in, in) = uo is det.
:- mode foldr_0(func(in, di) = uo is det, in, di, in, in) = uo is det.

foldr_0(Fn, A, X, Min, I) =
	( if I < Min	then X
			else foldr_0(Fn, A, Fn(A ^ elem(I), X), Min, I - 1)
	).

% ---------------------------------------------------------------------------- %

    % SAMsort (smooth applicative merge) invented by R.A. O'Keefe.
    %
    % SAMsort is a mergesort variant that works by identifying contiguous
    % monotonic sequences and merging them, thereby taking advantage of
    % any existing order in the input sequence.
    %
:- func samsort_submarray(marray(T), int, int) = marray(T).
:- mode samsort_submarray(marray_di, in, in) = marray_uo is det.

:- pragma type_spec(samsort_submarray/3, T = int).
:- pragma type_spec(samsort_submarray/3, T = string).

samsort_submarray(A0, Lo, Hi) = A :-
    samsort_up(0, A0, _, marray__copy(A0), A, Lo, Hi, Lo).



:- pred samsort_up(int, marray(T), marray(T), marray(T), marray(T), int, int, int).
:- mode samsort_up(in, marray_di, marray_uo, marray_di, marray_uo, in, in, in)
            is det.

:- pragma type_spec(samsort_up/8, T = int).
:- pragma type_spec(samsort_up/8, T = string).

    % Precondition:
    %   We are N levels from the bottom (leaf nodes) of the tree.
    %   A0 is sorted from Lo .. I - 1.
    %   A0 and B0 are identical from I .. Hi.
    % Postcondition:
    %   B is sorted from Lo .. Hi.
    %
samsort_up(N, A0, A, B0, B, Lo, Hi, I) :-

    ( if I > Hi then

        A = A0,
        B = B0

      else if N > 0 then

        samsort_down(N - 1, B0, B1, A0, A1, I, Hi, J),

            % A1 is sorted from I .. J - 1.
            % A1 and B1 are identical from J .. Hi.

        B2 = merge_submarrays(A1, B1, Lo, I - 1, I, J - 1, Lo),
        A2 = A1,

            % B2 is sorted from Lo .. J - 1.

        samsort_up(N + 1, B2, B, A2, A, Lo, Hi, J)

      else /* N = 0, I = Lo */

        copy_run_ascending(A0, B0, B1, Lo, Hi, J),

            % B1 is sorted from Lo .. J - 1.

        samsort_up(N + 1, B1, B, A0, A, Lo, Hi, J)
    ).



:- pred samsort_down(int,marray(T),marray(T),marray(T),marray(T),int,int,int).
:- mode samsort_down(in, marray_di, marray_uo, marray_di, marray_uo, in, in, out)
            is det.

:- pragma type_spec(samsort_down/8, T = int).
:- pragma type_spec(samsort_down/8, T = string).

    % Precondition:
    %   We are N levels from the bottom (leaf nodes) of the tree.
    %   A0 and B0 are identical from Lo .. Hi.
    % Postcondition:
    %   B is sorted from Lo .. I - 1.
    %   A and B are identical from I .. Hi.
    %
samsort_down(N, A0, A, B0, B, Lo, Hi, I) :-

    ( if Lo > Hi then

        A = A0,
        B = B0,
        I = Lo

      else if N > 0 then

        samsort_down(N - 1, B0, B1, A0, A1, Lo, Hi, J),
        samsort_down(N - 1, B1, B2, A1, A2, J,  Hi, I),

            % A2 is sorted from Lo .. J - 1.
            % A2 is sorted from J  .. I - 1.

        A = A2,
        B = merge_submarrays(A2, B2, Lo, J - 1, J, I - 1, Lo)

            % B is sorted from Lo .. I - 1.

      else

        A = A0,
        copy_run_ascending(A0, B0, B, Lo, Hi, I)

            % B is sorted from Lo .. I - 1.
    ).

%------------------------------------------------------------------------------%

:- pred copy_run_ascending(marray(T), marray(T), marray(T), int, int, int).
:- mode copy_run_ascending(marray_ui, marray_di, marray_uo, in, in, out) is det.

:- pragma type_spec(copy_run_ascending/6, T = int).
:- pragma type_spec(copy_run_ascending/6, T = string).

copy_run_ascending(A, B0, B, Lo, Hi, I) :-
    ( if Lo < Hi, compare((>), A ^ elem(Lo), A ^ elem(Lo + 1)) then
        I = search_until((<), A, Lo, Hi),
        B = copy_submarray_reverse(A, B0, Lo, I - 1, I - 1)
      else
        I = search_until((>), A, Lo, Hi),
        B = copy_submarray(A, B0, Lo, I - 1, Lo)
    ).

%------------------------------------------------------------------------------%

:- func search_until(comparison_result, marray(T), int, int) = int.
:- mode search_until(in, marray_ui, in, in) = out is det.

:- pragma type_spec(search_until/4, T = int).
:- pragma type_spec(search_until/4, T = string).

search_until(R, A, Lo, Hi) =
    ( if Lo < Hi, not compare(R, A ^ elem(Lo), A ^ elem(Lo + 1))
      then search_until(R, A, Lo + 1, Hi)
      else Lo + 1
    ).

%------------------------------------------------------------------------------%

:- func copy_submarray(marray(T), marray(T), int, int, int) = marray(T).
:- mode copy_submarray(marray_ui, marray_di, in, in, in) = marray_uo is det.

:- pragma type_spec(copy_submarray/5, T = int).
:- pragma type_spec(copy_submarray/5, T = string).

copy_submarray(A, B, Lo, Hi, I) =
    ( if Lo =< Hi
      then copy_submarray(A, B ^ elem(I) := A ^ elem(Lo), Lo + 1, Hi, I + 1)
      else B
    ).

%------------------------------------------------------------------------------%

:- func copy_submarray_reverse(marray(T), marray(T), int, int, int) = marray(T).
:- mode copy_submarray_reverse(marray_ui, marray_di, in, in, in) = marray_uo is det.

:- pragma type_spec(copy_submarray_reverse/5, T = int).
:- pragma type_spec(copy_submarray_reverse/5, T = string).

copy_submarray_reverse(A, B, Lo, Hi, I) =
    ( if Lo =< Hi
      then copy_submarray_reverse(A, B ^ elem(I) := A ^ elem(Lo), Lo+1, Hi, I-1)
      else B
    ).

%------------------------------------------------------------------------------%

    % merges the two sorted consecutive submarrays Lo1 .. Hi1 and
    % Lo2 .. Hi2 from A into the submarray starting at I in B.
    % 
:- func merge_submarrays(marray(T), marray(T), int, int, int, int, int) = marray(T).
:- mode merge_submarrays(marray_ui, marray_di, in, in, in, in, in) = marray_uo
            is det.

:- pragma type_spec(merge_submarrays/7, T = int).
:- pragma type_spec(merge_submarrays/7, T = string).

merge_submarrays(A, B0, Lo1, Hi1, Lo2, Hi2, I) = B :-
    (      if Lo1 > Hi1 then B = copy_submarray(A, B0, Lo2, Hi2, I)
      else if Lo2 > Hi2 then B = copy_submarray(A, B0, Lo1, Hi1, I)
      else
        X1 = A ^ elem(Lo1),
        X2 = A ^ elem(Lo2),
        compare(R, X1, X2),
        (
            R = (<),
            B = merge_submarrays(A, B0^elem(I) := X1, Lo1+1, Hi1, Lo2, Hi2, I+1)
        ;
            R = (=),
            B = merge_submarrays(A, B0^elem(I) := X1, Lo1+1, Hi1, Lo2, Hi2, I+1)
        ;
            R = (>),
            B = merge_submarrays(A, B0^elem(I) := X2, Lo1, Hi1, Lo2+1, Hi2, I+1)
        )
    ).

%------------------------------------------------------------------------------%
%------------------------------------------------------------------------------%
-------------- next part --------------
:- module marray.
:- use_module builtin,int,list,private_builtin,random,std_util.

%----------- pa_alias_info/3 ------------- 

:- pragma pa_alias_info(marray:'TypeSpecOf__pred_or_func__sort__[T = int]'((marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(int)),(marray:marray(int))), yes(bottom)).
:- pragma pa_alias_info(marray:'TypeSpecOf__pred_or_func__sort__[T = string]'((marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(string)),(marray:marray(string))), yes([ pair( cel(HeadVar__1, [typesel(_T)]) , cel(HeadVar__1, [typesel(_T)]) ) , pair( cel(HeadVar__2, []) , cel(HeadVar__1, [typesel(_T)]) ) ])).
:- pragma pa_alias_info(marray:'TypeSpecOf__pred_or_func__samsort_submarray__[T = int]'((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(int)),int,int,(marray:marray(int))), yes([ pair( cel(HeadVar__2, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:'TypeSpecOf__pred_or_func__samsort_submarray__[T = string]'((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(string)),int,int,(marray:marray(string))), yes([ pair( cel(HeadVar__1, [typesel(T)]) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__2, []) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__4, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:'TypeSpecOf__pred_or_func__samsort_up__[T = int]'((builtin:in), (marray:marray_di), (marray:marray_uo), (marray:marray_di), (marray:marray_uo), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6, HeadVar__7, HeadVar__8), types(int,(marray:marray(int)),(marray:marray(int)),(marray:marray(int)),(marray:marray(int)),int,int,int), yes([ pair( cel(HeadVar__1, [typesel(T)]) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__2, []) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__3, []) , cel(HeadVar__2, []) ) , pair( cel(HeadVar__5, []) , cel(HeadVar__4, []) ) , pair( cel(HeadVar__6, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__8, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__8, []) , cel(HeadVar__4, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:'TypeSpecOf__pred_or_func__samsort_up__[T = string]'((builtin:in), (marray:marray_di), (marray:marray_uo), (marray:marray_di), (marray:marray_uo), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6, HeadVar__7, HeadVar__8), types(int,(marray:marray(string)),(marray:marray(string)),(marray:marray(string)),(marray:marray(string)),int,int,int), yes([ pair( cel(HeadVar__2, [typesel(T)]) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__3, []) , cel(HeadVar__2, []) ) , pair( cel(HeadVar__4, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__5, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__5, []) , cel(HeadVar__4, []) ) , pair( cel(HeadVar__6, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__8, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__8, []) , cel(HeadVar__4, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:make_empty_marray((marray:marray_uo)), vars(Array), types((marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info((marray:make_empty_marray) = (marray:marray_uo), vars(HeadVar__1), types((marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:init((builtin:in), (builtin:in), (marray:marray_uo)), vars(Size, Item, Array), types(int,T,(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:init((builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(int,T,(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:marray((builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((list:list(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:min((marray:marray_ui), (builtin:out)), vars(Array, Min), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:min((builtin:in), (builtin:out)), vars(Array, Min), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:min((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:min((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:max((marray:marray_ui), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:max((builtin:in), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:max((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:max((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:size((marray:marray_ui), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:size((builtin:in), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:size((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:size((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:bounds((marray:marray_ui), (builtin:out), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(_T)),int,int), yes(bottom)).
:- pragma pa_alias_info(marray:bounds((builtin:in), (builtin:out), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(_T)),int,int), yes(bottom)).
:- pragma pa_alias_info(marray:in_bounds((marray:marray_ui), (builtin:in)), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:in_bounds((builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), yes(bottom)).
:- pragma pa_alias_info(marray:lookup((marray:marray_ui), (builtin:in), (builtin:out)), vars(Array, Index, Item), types((marray:marray(T)),int,T), yes([ pair( cel(Item, []) , cel(Array, [typesel(V_4)]) ) ])).
:- pragma pa_alias_info(marray:lookup((builtin:in), (builtin:in), (builtin:out)), vars(Array, Index, Item), types((marray:marray(T)),int,T), yes([ pair( cel(Item, []) , cel(Array, [typesel(V_4)]) ) ])).
:- pragma pa_alias_info(marray:lookup((marray:marray_ui), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), yes([ pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:lookup((builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), yes([ pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:semidet_lookup((marray:marray_ui), (builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), yes([ pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(_T)]) ) ])).
:- pragma pa_alias_info(marray:semidet_lookup((builtin:in), (builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), yes([ pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(_T)]) ) ])).
:- pragma pa_alias_info(marray:set((marray:marray_di), (builtin:in), (builtin:in), (marray:marray_uo)), vars(Array0, Index, Item, Array), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(Array, [typesel(T)]) , cel(Item, []) ) ])).
:- pragma pa_alias_info(marray:set((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:semidet_set((marray:marray_di), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:slow_set((marray:marray_ui), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:slow_set((builtin:in), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:slow_set((marray:marray_ui), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:slow_set((builtin:in), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:semidet_slow_set((marray:marray_ui), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:semidet_slow_set((builtin:in), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:elem((builtin:in), (marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(int,(marray:marray(T)),T), yes([ pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:elem((builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(int,(marray:marray(T)),T), yes([ pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:'elem :='((builtin:in), (marray:marray_ui), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types(int,(marray:marray(T)),T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:copy((marray:marray_ui), (marray:marray_uo)), vars(Array0, Array), types((marray:marray(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:copy((builtin:in), (marray:marray_uo)), vars(Array0, Array), types((marray:marray(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:copy((marray:marray_ui)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:copy((builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:resize((marray:marray_di), (builtin:in), (builtin:in), (marray:marray_uo)), vars(Array0, Size, Item, Array), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(Array, [typesel(T)]) , cel(Item, []) ) ])).
:- pragma pa_alias_info(marray:resize((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), yes([ pair( cel(HeadVar__4, [typesel(T)]) , cel(HeadVar__3, []) ) ])).
:- pragma pa_alias_info(marray:shrink((marray:marray_di), (builtin:in), (marray:marray_uo)), vars(Array0, Size, Array), types((marray:marray(T)),int,(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:shrink((marray:marray_di), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:from_list((builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2), types((list:list(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:from_list((builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((list:list(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:to_list((marray:marray_ui), (builtin:out)), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), yes(bottom)).
:- pragma pa_alias_info(marray:to_list((builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), yes(bottom)).
:- pragma pa_alias_info(marray:to_list((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), yes(bottom)).
:- pragma pa_alias_info(marray:to_list((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), yes(bottom)).
:- pragma pa_alias_info(marray:fetch_items((builtin:in), (builtin:in), (builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(list:list(T))), yes(bottom)).
:- pragma pa_alias_info(marray:fetch_items((marray:marray_ui), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(list:list(T))), yes(bottom)).
:- pragma pa_alias_info(marray:fetch_items((builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(list:list(T))), yes(bottom)).
:- pragma pa_alias_info(marray:bsearch((marray:marray_ui), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,pred(T, T, (builtin:comparison_result)),(std_util:maybe(int))), yes(top)).
:- pragma pa_alias_info(marray:bsearch((builtin:in), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,pred(T, T, (builtin:comparison_result)),(std_util:maybe(int))), yes(top)).
:- pragma pa_alias_info(marray:bsearch((marray:marray_ui), (builtin:in), (func((builtin:in), (builtin:in)) = (builtin:out) is det)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,(func(T, T) = (builtin:comparison_result)),(std_util:maybe(int))), yes(top)).
:- pragma pa_alias_info(marray:bsearch((builtin:in), (builtin:in), (func((builtin:in), (builtin:in)) = (builtin:out) is det)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,(func(T, T) = (builtin:comparison_result)),(std_util:maybe(int))), yes(top)).
:- pragma pa_alias_info(marray:map((pred((builtin:in), (builtin:out)) is det), (marray:marray_di), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(pred(T1, T2),(marray:marray(T1)),(marray:marray(T2))), yes(top)).
:- pragma pa_alias_info(marray:map((func((builtin:in)) = (builtin:out) is det), (marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(((func T1) = T2),(marray:marray(T1)),(marray:marray(T2))), yes(top)).
:- pragma pa_alias_info(marray:marray_compare((builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),(marray:marray(T)),(builtin:comparison_result)), yes(bottom)).
:- pragma pa_alias_info(marray:sort((marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:foldl((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:foldl((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:foldl((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:foldl((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), yes(top)).
:- pragma pa_alias_info(marray:random_permutation((marray:marray_di), (marray:marray_uo), (builtin:mdi), (builtin:muo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),(marray:marray(T)),int,int), yes([ pair( cel(HeadVar__2, []) , cel(HeadVar__1, []) ) ])).
:- pragma pa_alias_info(marray:marray_equal((builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:marray_compare((builtin:out), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((builtin:comparison_result),(marray:marray(T)),(marray:marray(T))), yes(bottom)).
:- pragma pa_alias_info(marray:equal_elements((builtin:in), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types(int,int,(marray:marray(T)),(marray:marray(T))), yes([ pair( cel(HeadVar__1, [typesel(T)]) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:bsearch_2((builtin:in), (builtin:in), (builtin:in), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((marray:marray(T)),int,int,T,pred(T, T, (builtin:comparison_result)),(std_util:maybe(int))), yes(top)).
:- pragma pa_alias_info(marray:map_2((builtin:in), (builtin:in), (pred((builtin:in), (builtin:out)) is det), (builtin:in), (marray:marray_di), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types(int,int,pred(T1, T2),(marray:marray(T1)),(marray:marray(T2)),(marray:marray(T2))), yes(top)).
:- pragma pa_alias_info(marray:foldl_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:foldl_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:foldl_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:foldl_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:foldr_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), yes(top)).
:- pragma pa_alias_info(marray:samsort_submarray((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(marray:marray(T))), yes([ pair( cel(HeadVar__2, []) , cel(HeadVar__1, [typesel(T)]) ) ])).
:- pragma pa_alias_info(marray:samsort_up((builtin:in), (marray:marray_di), (marray:marray_uo), (marray:marray_di), (marray:marray_uo), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6, HeadVar__7, HeadVar__8), types(int,(marray:marray(T)),(marray:marray(T)),(marray:marray(T)),(marray:marray(T)),int,int,int), yes([ pair( cel(HeadVar__1, [typesel(T)]) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__2, []) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__3, []) , cel(HeadVar__1, [typesel(T)]) ) , pair( cel(HeadVar__3, []) , cel(HeadVar__2, []) ) , pair( cel(HeadVar__5, []) , cel(HeadVar__4, []) ) , pair( cel(HeadVar__6, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__8, []) , cel(HeadVar__2, [typesel(T)]) ) , pair( cel(HeadVar__8, []) , cel(HeadVar__4, [typesel(T)]) ) ])).

%----------- sr_reuse_info/3 ------------- 

:- pragma sr_reuse_info(marray:'TypeSpecOf__pred_or_func__sort__[T = int]'((marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(int)),(marray:marray(int))), no).
:- pragma sr_reuse_info(marray:'TypeSpecOf__pred_or_func__sort__[T = string]'((marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(string)),(marray:marray(string))), no).
:- pragma sr_reuse_info(marray:'TypeSpecOf__pred_or_func__samsort_submarray__[T = int]'((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(int)),int,int,(marray:marray(int))), no).
:- pragma sr_reuse_info(marray:'TypeSpecOf__pred_or_func__samsort_submarray__[T = string]'((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(string)),int,int,(marray:marray(string))), no).
:- pragma sr_reuse_info(marray:'TypeSpecOf__pred_or_func__samsort_up__[T = int]'((builtin:in), (marray:marray_di), (marray:marray_uo), (marray:marray_di), (marray:marray_uo), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6, HeadVar__7, HeadVar__8), types(int,(marray:marray(int)),(marray:marray(int)),(marray:marray(int)),(marray:marray(int)),int,int,int), no).
:- pragma sr_reuse_info(marray:'TypeSpecOf__pred_or_func__samsort_up__[T = string]'((builtin:in), (marray:marray_di), (marray:marray_uo), (marray:marray_di), (marray:marray_uo), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6, HeadVar__7, HeadVar__8), types(int,(marray:marray(string)),(marray:marray(string)),(marray:marray(string)),(marray:marray(string)),int,int,int), no).
:- pragma sr_reuse_info(marray:make_empty_marray((marray:marray_uo)), vars(Array), types((marray:marray(T))), no).
:- pragma sr_reuse_info((marray:make_empty_marray) = (marray:marray_uo), vars(HeadVar__1), types((marray:marray(T))), no).
:- pragma sr_reuse_info(marray:init((builtin:in), (builtin:in), (marray:marray_uo)), vars(Size, Item, Array), types(int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:init((builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:marray((builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((list:list(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:min((marray:marray_ui), (builtin:out)), vars(Array, Min), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:min((builtin:in), (builtin:out)), vars(Array, Min), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:min((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:min((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:max((marray:marray_ui), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:max((builtin:in), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:max((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:max((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:size((marray:marray_ui), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:size((builtin:in), (builtin:out)), vars(Array, Max), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:size((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:size((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:bounds((marray:marray_ui), (builtin:out), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(_T)),int,int), no).
:- pragma sr_reuse_info(marray:bounds((builtin:in), (builtin:out), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(_T)),int,int), no).
:- pragma sr_reuse_info(marray:in_bounds((marray:marray_ui), (builtin:in)), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:in_bounds((builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2), types((marray:marray(_T)),int), no).
:- pragma sr_reuse_info(marray:lookup((marray:marray_ui), (builtin:in), (builtin:out)), vars(Array, Index, Item), types((marray:marray(T)),int,T), no).
:- pragma sr_reuse_info(marray:lookup((builtin:in), (builtin:in), (builtin:out)), vars(Array, Index, Item), types((marray:marray(T)),int,T), no).
:- pragma sr_reuse_info(marray:lookup((marray:marray_ui), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), no).
:- pragma sr_reuse_info(marray:lookup((builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), no).
:- pragma sr_reuse_info(marray:semidet_lookup((marray:marray_ui), (builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), no).
:- pragma sr_reuse_info(marray:semidet_lookup((builtin:in), (builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,T), no).
:- pragma sr_reuse_info(marray:set((marray:marray_di), (builtin:in), (builtin:in), (marray:marray_uo)), vars(Array0, Index, Item, Array), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:set((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:semidet_set((marray:marray_di), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:slow_set((marray:marray_ui), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:slow_set((builtin:in), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:slow_set((marray:marray_ui), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:slow_set((builtin:in), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:semidet_slow_set((marray:marray_ui), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:semidet_slow_set((builtin:in), (builtin:in), (builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:elem((builtin:in), (marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(int,(marray:marray(T)),T), no).
:- pragma sr_reuse_info(marray:elem((builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(int,(marray:marray(T)),T), no).
:- pragma sr_reuse_info(marray:'elem :='((builtin:in), (marray:marray_ui), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types(int,(marray:marray(T)),T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:copy((marray:marray_ui), (marray:marray_uo)), vars(Array0, Array), types((marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:copy((builtin:in), (marray:marray_uo)), vars(Array0, Array), types((marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:copy((marray:marray_ui)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:copy((builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:resize((marray:marray_di), (builtin:in), (builtin:in), (marray:marray_uo)), vars(Array0, Size, Item, Array), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:resize((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,T,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:shrink((marray:marray_di), (builtin:in), (marray:marray_uo)), vars(Array0, Size, Array), types((marray:marray(T)),int,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:shrink((marray:marray_di), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),int,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:from_list((builtin:in), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2), types((list:list(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:from_list((builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((list:list(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:to_list((marray:marray_ui), (builtin:out)), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), no).
:- pragma sr_reuse_info(marray:to_list((builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), no).
:- pragma sr_reuse_info(marray:to_list((marray:marray_ui)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), no).
:- pragma sr_reuse_info(marray:to_list((builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(list:list(T))), no).
:- pragma sr_reuse_info(marray:fetch_items((builtin:in), (builtin:in), (builtin:in), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(list:list(T))), no).
:- pragma sr_reuse_info(marray:fetch_items((marray:marray_ui), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(list:list(T))), no).
:- pragma sr_reuse_info(marray:fetch_items((builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(list:list(T))), no).
:- pragma sr_reuse_info(marray:bsearch((marray:marray_ui), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,pred(T, T, (builtin:comparison_result)),(std_util:maybe(int))), no).
:- pragma sr_reuse_info(marray:bsearch((builtin:in), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,pred(T, T, (builtin:comparison_result)),(std_util:maybe(int))), no).
:- pragma sr_reuse_info(marray:bsearch((marray:marray_ui), (builtin:in), (func((builtin:in), (builtin:in)) = (builtin:out) is det)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,(func(T, T) = (builtin:comparison_result)),(std_util:maybe(int))), no).
:- pragma sr_reuse_info(marray:bsearch((builtin:in), (builtin:in), (func((builtin:in), (builtin:in)) = (builtin:out) is det)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),T,(func(T, T) = (builtin:comparison_result)),(std_util:maybe(int))), no).
:- pragma sr_reuse_info(marray:map((pred((builtin:in), (builtin:out)) is det), (marray:marray_di), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(pred(T1, T2),(marray:marray(T1)),(marray:marray(T2))), no).
:- pragma sr_reuse_info(marray:map((func((builtin:in)) = (builtin:out) is det), (marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3), types(((func T1) = T2),(marray:marray(T1)),(marray:marray(T2))), no).
:- pragma sr_reuse_info(marray:marray_compare((builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((marray:marray(T)),(marray:marray(T)),(builtin:comparison_result)), no).
:- pragma sr_reuse_info(marray:sort((marray:marray_di)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:foldl((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:foldl((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:foldl((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:foldl((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:foldr((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:foldr((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:foldr((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:foldr((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((func(T1, T2) = T2),(marray:marray(T1)),T2,T2), no).
:- pragma sr_reuse_info(marray:random_permutation((marray:marray_di), (marray:marray_uo), (builtin:mdi), (builtin:muo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),(marray:marray(T)),int,int), no).
:- pragma sr_reuse_info(marray:marray_equal((builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2), types((marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:marray_compare((builtin:out), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3), types((builtin:comparison_result),(marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:equal_elements((builtin:in), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types(int,int,(marray:marray(T)),(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:bsearch_2((builtin:in), (builtin:in), (builtin:in), (builtin:in), (pred((builtin:in), (builtin:in), (builtin:out)) is det), (builtin:out)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((marray:marray(T)),int,int,T,pred(T, T, (builtin:comparison_result)),(std_util:maybe(int))), no).
:- pragma sr_reuse_info(marray:map_2((builtin:in), (builtin:in), (pred((builtin:in), (builtin:out)) is det), (builtin:in), (marray:marray_di), (marray:marray_uo)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types(int,int,pred(T1, T2),(marray:marray(T1)),(marray:marray(T2)),(marray:marray(T2))), no).
:- pragma sr_reuse_info(marray:foldl_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:foldl_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:foldl_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:foldl_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:foldr_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (marray:marray_ui), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:foldr_0((func((builtin:in), (builtin:in)) = (builtin:out) is det), (builtin:in), (builtin:in), (builtin:in), (builtin:in)) = (builtin:out), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:foldr_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (marray:marray_ui), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:foldr_0((func((builtin:in), (builtin:di)) = (builtin:uo) is det), (builtin:in), (builtin:di), (builtin:in), (builtin:in)) = (builtin:uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6), types((func(T1, T2) = T2),(marray:marray(T1)),T2,int,int,T2), no).
:- pragma sr_reuse_info(marray:samsort_submarray((marray:marray_di), (builtin:in), (builtin:in)) = (marray:marray_uo), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4), types((marray:marray(T)),int,int,(marray:marray(T))), no).
:- pragma sr_reuse_info(marray:samsort_up((builtin:in), (marray:marray_di), (marray:marray_uo), (marray:marray_di), (marray:marray_uo), (builtin:in), (builtin:in), (builtin:in)), vars(HeadVar__1, HeadVar__2, HeadVar__3, HeadVar__4, HeadVar__5, HeadVar__6, HeadVar__7, HeadVar__8), types(int,(marray:marray(T)),(marray:marray(T)),(marray:marray(T)),(marray:marray(T)),int,int,int), no).