Hi,

this is a call for a "style review". This is code that has been taken from the
reuse branch, but almost entirely rewritten (some predicate-renaming, 
extra documentation, even new implementation). It is not tested yet, as the
analysis system needs to be transscribed still. So there is no use in really
looking at the implementation. Yet, any style comments would already be
helpful.

In the meantime I'm continuing with the actual analysis. 

Nancy

PS: sorry, I did the diff in the compiler/ directory instead of the main
directory. No time to do better now (slow connection). 

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


Estimated hours taken: 40
Branches: main

Definition of the structure sharing domain. The public
representation is defined in prog_data.m, the private
representation is defined in structure_sharing.domain.m. 

Structure sharing operations depend on datastructure and selector operations, 
which are defined in their own seperate modules. The modules are at the
ctgc toplevel as they are needed in the structure reuse analysis too. 

ctgc.m:
ctgc.datastruct.m:
ctgc.selector.m:
	New modules. 

prog_data.m:
	Public representation for sharing.

structure_sharing.m:
structure_sharing.domain.m:
	Private representation for sharing. 


Index: ctgc.datastruct.m
===================================================================
RCS file: ctgc.datastruct.m
diff -N ctgc.datastruct.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ ctgc.datastruct.m	16 Jan 2006 10:38:41 -0000
@@ -0,0 +1,66 @@
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: ctgc.datastruct.m
+% Main authors: nancy
+%
+% Definition of predicates and functions for the manipulation of 
+% datastructures. 
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.datastruct.
+
+:- interface.
+
+:- import_module parse_tree.prog_data.
+
+:- import_module map.
+:- import_module std_util.
+
+	% Create an initial top-datastruct of the given variable.
+:- func init(prog_var) = datastruct.
+:- func init(prog_var, selector) = datastruct.
+:- func init(prog_var, cons_id, int) = datastruct.
+
+	% Verify whether the given datastructs are idenitical.
+:- pred equal(datastruct::in, datastruct::in) is semidet.
+
+:- pred rename(map(prog_var, prog_var)::in, maybe(tsubst)::in,
+	datastruct::in, datastruct::out) is det.
+
+	% Select a subterm of the given datastructure using the specified
+	% selector. 
+	% It is assumed that the selector is a valid selector for that
+	% datastructure. 
+:- pred termshift(selector::in, datastruct::in, datastruct::out) is det.
+:- func termshift(selector, datastruct) = datastruct. 
+
+:- implementation.
+
+:- import_module transform_hlds.ctgc.selector.
+
+:- import_module list.
+
+init(V) = init(V, []).
+init(V, Sel) = selected_cel(V, Sel). 
+init(V, ConsId, Int) = init(V, selector.init(ConsId, Int)).
+
+equal(D1, D2) :- D1 = D2. 
+
+rename(ProgVarMap, MaybeSubst, Data0, Data) :-
+	Data0 = selected_cel(Var0, Sel0),
+	map__lookup(ProgVarMap, Var0, Var),
+	ctgc.selector.rename_types(MaybeSubst, Sel0, Sel), 
+	Data = selected_cel(Var, Sel).
+
+termshift(Sel, Data0, Data) :- 
+	DSel = Data0 ^ sc_selector, 
+	selector.termshift(DSel, Sel, NewSel), 
+	Data = Data0 ^ sc_selector := NewSel.
+termshift(Sel, Data0) = Data :- 
+	termshift(Sel, Data0, Data).
+
+:- end_module transform_hlds.ctgc.datastruct.
Index: ctgc.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ctgc.m,v
retrieving revision 1.1
diff -u -d -r1.1 ctgc.m
--- ctgc.m	16 Dec 2005 12:17:52 -0000	1.1
+++ ctgc.m	16 Jan 2006 10:38:41 -0000
@@ -16,6 +16,10 @@
 
 :- interface.
 
+:- import_module parse_tree.
+
 :- include_module structure_sharing.
+:- include_module datastruct.
+:- include_module selector.
 
 :- end_module transform_hlds.ctgc.
Index: ctgc.selector.m
===================================================================
RCS file: ctgc.selector.m
diff -N ctgc.selector.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ ctgc.selector.m	16 Jan 2006 10:38:42 -0000
@@ -0,0 +1,392 @@
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: ctgc.selector.m
+% Main authors: nancy
+%
+% Definition of predicates and functions for the manipulation of 
+% selectors. 
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.selector.
+
+:- interface.
+
+:- import_module hlds.hlds_module.
+:- import_module parse_tree__prog_data.
+
+:- import_module std_util.
+:- import_module list.
+
+	% Create a selector as either the top selector, a term selector, 
+	% or a type selector.
+:- func top_selector = selector. 
+:- func init(cons_id, int) = selector.
+:- func init(list(mer_type)) = selector.
+
+	% Rename the type variables within the types occurring in the selector.
+:- pred rename_types(maybe(tsubst)::in, selector::in, selector::out) is det.
+
+	% Perform a termshift operation.
+:- pred termshift(selector::in, selector::in, selector::out) is det.
+
+	% subsumed_by(ModuleInfo, Selector0, Selector1, Type, Extension). 
+	% Returns true if Selector0 is subsumed by Selector1. This 
+    % means that Selector1 is more general than Selector0, hence, there
+    % exists an extension Ext, such that Selector1.Extension = 
+    % Selector0. 
+	% Note that the type specifies the type of the term to which the 
+	% selectors refer. 
+:- pred subsumed_by(module_info::in, selector::in, selector::in, 
+	mer_type::in, selector::out) is semidet.
+
+	% Using the type information of the variable to which the given 
+	% selector belongs, normalize that selector. 
+	% S2 is the normalized form of S1 iff: 
+	% 	* type of the node selected by S2 = type of the node
+	% 	selected by S1. 
+	% 	* a path of selectors can be constructed which leads from S2
+	% 	to S1. 
+:- pred normalize_with_type_information(module_info::in, mer_type::in, 
+	selector::in, selector::out) is det.
+
+    % SubType = type_of_node(ModuleInfo, StartType, Selector).
+	% Determines the type SubType of the node obtained by traversing
+	% the type tree of StartType using the path Selector. 
+:- func type_of_node(module_info, mer_type, selector) = mer_type.
+
+	% Abbreviate a selector to the type of the node it selects. 
+:- pred apply_widening(module_info::in, mer_type::in,
+		selector::in, selector::out) is det.
+
+:- implementation.
+
+:- import_module check_hlds.type_util.
+:- import_module libs.compiler_util.
+:- import_module parse_tree.prog_type.
+:- import_module parse_tree.prog_type_subst.
+
+:- import_module assoc_list.
+:- import_module map.
+
+top_selector = [].
+init(Cons, Index) = [termsel(Cons, Index)].
+init(Types) = 
+	list__map(func(T) = US :- US = typesel(T), Types).
+
+rename_types(no, S, S).
+rename_types(yes(Subst), S0, S) :-
+	list__map(unit_selector_rename_types(Subst), S0, S).
+
+:- pred unit_selector_rename_types(tsubst::in,
+		unit_selector::in, unit_selector::out) is det.
+
+unit_selector_rename_types(Subst, US0, US) :- 
+	(
+		US0 = termsel(_,_),
+		US = US0
+	;
+		US0 = typesel(Type0), 
+		prog_type_subst.apply_subst_to_type(Subst, Type0, Type), 
+		US = typesel(Type)
+	).
+	
+termshift(S1, S2, S) :- list__append(S1, S2, S).
+
+subsumed_by(ModuleInfo, S1, S2, MainType, Extension):- 
+    % first make sure that both selectors are in a normalized form.
+    normalize_with_type_information(ModuleInfo, MainType, S1, NormS1), 
+    normalize_with_type_information(ModuleInfo, MainType, S2, NormS2), 
+    subsumed_by_2(ModuleInfo, NormS1, NormS2, MainType, Extension). 
+
+:- pred subsumed_by_2(module_info::in, selector::in, selector::in,
+    mer_type::in, selector::out) is semidet.
+
+subsumed_by_2(ModuleInfo, S1, S2, MainType, Extension):- 
+	(
+		split_upto_type_selector(S2, S2_part1, TS, S2_part2),
+		TS = typesel(SubType)
+	->
+        % step 1: S2_part1.Rest = S1, hence S2_part1 should be more general
+        % than S1. 
+		subsumed_by_2(ModuleInfo, S1, S2_part1, MainType, Rest),
+
+        % step 2: S2_part1.TS.Remainder = S1, hence S2_part1.TS should be more
+        % general than S1. 
+        % i.e.
+        % Check the type-selector part: starting from the type selected by
+        % S2_part1, does the remainder of Rest (the extension of S2_part1 
+        % such that S2_part1.Rest = S1) lead through a node with type
+        % "SubType".
+        %
+		type_on_path(ModuleInfo, type_of_node(ModuleInfo, MainType, S2_part1),
+            SubType, Rest, Remainder),
+
+        % step 3: % S2_part1.TS.S1_part2 should be more general than S1.
+		subsumed_by_2(ModuleInfo, Remainder, S2_part2, SubType, Extension)
+	; 	
+		% If the second selector S2 has no type-
+		% selectors, we have the simple case where S1 can be more
+        % general than S2 if there exists a path "Extension" such that
+        % S1.Extension = S2
+		subsumed_by(S1, S2, Extension)
+	). 
+
+:- pred subsumed_by(selector::in, selector::in, selector::out) is semidet.
+subsumed_by(S1, S2, Extension):-
+	list__append(S2, Extension, S1). 
+
+
+
+type_of_node(ModuleInfo, StartType, Selector) = SubType :-
+	(
+		Selector = [ UnitSelector | RestSelector ]
+	->
+		(
+			UnitSelector = termsel(ConsId, Index),
+			SubType0 = select_subtype(ModuleInfo, StartType, ConsId, Index) 
+		; 
+			UnitSelector = typesel(SubType0)
+		),
+		SubType = type_of_node(ModuleInfo, SubType0, RestSelector)
+	;
+		SubType = StartType
+	).
+
+	% SubType = select_subtype(ModuleInfo, Type, ConsID, Position, SubType).
+	% Determine the type of the type node selected from the type tree Type,
+    % selecting the specific constructor (ConsId), at position Position. 
+	% Position counts starting from 1.
+:- func select_subtype(module_info, mer_type, cons_id, int) = mer_type. 
+select_subtype(ModuleInfo, Type, ConsID, Choice) = SubType :- 
+	(
+		type_util__get_cons_id_non_existential_arg_types(ModuleInfo, 
+			Type, ConsID, ArgTypes)
+	->
+		(
+			list__index1(ArgTypes, Choice, SubType0)
+		->
+			SubType = SubType0
+		;
+			unexpected(this_file, "get_type_of_node: selection failed.")
+		)
+	;
+		unexpected(this_file, "get_type_of_node: existential type.")
+	).
+
+
+
+	% split_upto_type_selector(Sin, S1, TS, S2): 
+	%	This predicate succeeds if there exists a typeselector
+	% 	TS, such that Sin is equivalent to append(S1, [TS | S2])
+	% 	and S1 contains no other type selector. It fails otherwise. 
+:- pred split_upto_type_selector(selector::in, selector::out, 
+		unit_selector::out, selector::out) is semidet.
+
+split_upto_type_selector(Sin, S1, TS, S2):-
+    list__takewhile(
+        pred(UnitSelector::in) is semidet :- 
+            ( UnitSelector = termsel(_, _) ), 
+        Sin, 
+        S1, 
+        Remainder), 
+    Remainder = [TS | S2 ].
+                
+	% type_on_path(ModuleInfo, FromType, ToType, Path, Remainder):
+	% This predicate verifies that the path Path starting from 
+	% FromType encounters at least one type node with the type ToType. 
+    % Remainder is the remainder of the Path after stripping it to the last
+    % encounter of a node with "ToType". 
+    % XXX Changed w.r.t. original implementation!
+	% 
+:- pred type_on_path(module_info::in, mer_type::in, mer_type::in, 
+		selector::in, selector::out) is semidet.
+
+type_on_path(ModuleInfo, FromType, ToType, Path, RemainderPath) :-
+    % In checking this, at least one step of the Path must be done. Indeed, if
+    % FromType = ToType, than RemainderPath would be equal to Path, which would
+    % contradict the actual meaning of a type selector: A type-selector is a
+    % shortcut notation for any non-zero (!) selector that selects a node of
+    % the type described by the type-selector. 
+	type_on_path_2(first, ModuleInfo, FromType, 
+			ToType, Path, RemainderPath).
+
+:- type step ---> first ; subsequent. 
+:- pred type_on_path_2(step::in, module_info::in, mer_type::in, mer_type::in, 
+		selector::in, selector::out) is semidet.
+
+type_on_path_2(Step, ModuleInfo, FromType, ToType, Path, RemainderPath) :- 
+	(
+		FromType = ToType, 
+		Step = subsequent	
+	->
+		RemainderPath = Path
+	; 
+		Path = [ UnitSelector | Rest ],
+		(
+			UnitSelector = typesel(SubType),
+			(
+				SubType = ToType
+			->
+                (
+                    % Check if the same type occurs anywhere further on the
+                    % path. 
+                    type_on_path_2(first, ModuleInfo, ToType, ToType, 
+                        Rest, RemainderPath0)
+                -> 
+                    RemainderPath = RemainderPath0
+                ; 
+				    RemainderPath = Rest
+                )
+			;
+				type_on_path_2(subsequent, ModuleInfo, SubType, ToType, 
+					Rest, RemainderPath)
+			)
+		;
+			UnitSelector = termsel(ConsId, Index), 
+			SubType = select_subtype(ModuleInfo, FromType, ConsId, Index),
+			(
+				SubType = ToType
+			->
+                (
+                    % Check if the same type occurs anywhere further on the
+                    % path. 
+                    type_on_path_2(first, ModuleInfo, ToType, ToType, 
+                        Rest, RemainderPath0)
+                -> 
+                    RemainderPath = RemainderPath0
+                ; 
+				    RemainderPath = Rest
+                )
+			;
+				type_on_path_2(subsequent, ModuleInfo, SubType, ToType, 
+					Rest, RemainderPath)
+			)
+		)
+	).
+
+normalize_with_type_information(ModuleInfo, Type, Sel0, Sel) :- 
+	(
+		prog_type.is_introduced_type_info_type(Type)
+	->
+		Sel = Sel0
+	; 
+		branch_map_init(B0), 
+		branch_map_insert(Type, top_selector, B0, B1),
+		normalize_wti(ModuleInfo, Type, B1, top_selector, Sel0, Sel)
+	).
+
+	
+:- pred normalize_wti(module_info::in, mer_type::in, branch_map::in, 
+	selector::in, selector::in, selector::out) is det.
+
+
+normalize_wti(ModuleInfo, VarType, B0, Acc0, Sel0, Sel):-
+	(
+		Sel0 = [ UnitSelector | SelRest ]
+	->
+		Class = type_util.classify_type(ModuleInfo, VarType),
+		(
+			Class = type_cat_user_ctor
+		->
+            % If it is either a term-selector of a non existentially typed
+            % functor or a type-selector, construct the branch map and proceed
+            % with normalization. If it is a term-selector of an existentially
+            % typed functor, than normalization stops. 
+			(
+			    (
+                    UnitSelector = termsel(ConsId, Index),
+				    type_util.get_cons_id_non_existential_arg_types(ModuleInfo, 
+				        VarType, ConsId, ArgTypes),
+				    (
+					    list__index1(ArgTypes, Index, SubType)
+				    ->
+					    CType = SubType
+				    ;
+                        Msg = "normalize_wti: accessing non-existing index.",
+					    unexpected(this_file, Msg)
+				    )
+			    ;
+				    UnitSelector = typesel(CType)
+			    )
+			->
+				(
+					branch_map_search(B0, CType,
+						BSel)
+				->
+					normalize_wti(ModuleInfo, CType, 
+						B0, BSel, SelRest, Sel)
+				;
+					termshift(Acc0, [UnitSelector], 
+						Acc1),
+					branch_map_insert(CType, 
+						Acc1, B0, B1),
+					normalize_wti(ModuleInfo, CType, 
+						B1, Acc1, SelRest, Sel)
+				)
+			;
+				% existentially typed functor.
+				append(Acc0, Sel0, Sel)
+			)
+		;
+            % if it is not a user type, SelRest is empty anyhow, and
+            % normalization stops.
+			% Resulting selector = accumulator.sel0
+			append(Acc0, Sel0, Sel)
+
+		)
+	;
+		% SEL0 = []		
+		Sel = Acc0
+	).
+
+apply_widening(ModuleInfo, MainType, Selector0, Selector) :-
+	(
+		Selector0 = []
+	-> 
+		Selector = Selector0
+	; 
+		Selector = [ typesel(type_of_node(ModuleInfo, MainType, Selector0)) ]
+	).
+
+
+%-----------------------------------------------------------------------------%
+% BRANCH_MAP : copy/pasted from wimvh/bta_reduce.m
+%-----------------------------------------------------------------------------%
+
+:- type branch_map == assoc_list(mer_type, selector).
+
+:- pred branch_map_init(branch_map::out) is det.
+
+:- pred branch_map_insert(mer_type::in, selector::in, branch_map::in, 
+	branch_map::out) is det.
+        
+:- pred branch_map_search(branch_map::in, mer_type::in, 
+	selector::out) is semidet.
+
+branch_map_init([]).
+
+branch_map_insert(Type, SelPart, Map1, [(Type - SelPart) | Map1]).
+
+branch_map_search([ (T1 - S1) | Ms ], T2, S):-
+        map__init(Empty),
+		% The two types are considered equal if they unify under an
+		% empty substitution
+        (
+		prog_type.type_unify(T1, T2, [], Empty, Subst), 
+		map__is_empty(Subst)
+	->
+                S = S1
+	;
+	        branch_map_search(Ms, T2, S)
+	).
+
+
+%-----------------------------------------------------------------------------%
+
+:- func this_file = string. 
+this_file = "ctgc.selector.m".
Index: prog_data.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/prog_data.m,v
retrieving revision 1.151
diff -u -d -r1.151 prog_data.m
--- prog_data.m	16 Jan 2006 03:08:14 -0000	1.151
+++ prog_data.m	16 Jan 2006 10:38:44 -0000
@@ -320,6 +320,46 @@
 
 %-----------------------------------------------------------------------------%
 %
+% Stuff for the `structure_sharing_info' pragma.
+%
+
+        % Elements of the structure sharing domain lattice are either bottom
+        % (no structure sharing), top (any kind of structure sharing), or
+        % a list of structure sharing pairs. 
+:- type structure_sharing_domain
+    --->    bottom
+    ;       real(structure_sharing)
+    ;       top(list(string)). 
+
+        % The public representation of structure sharing is simply set to be a
+        % list of structure sharing pairs.
+:- type structure_sharing == list(structure_sharing_pair).
+
+        % A structure sharing pair represents the fact that two datastructures
+        % might be represented by the same memoryspace.
+:- type structure_sharing_pair == pair(datastruct).
+
+        % A datastructure is a concept that designates a particular subterm 
+        % of the term to which a particalar variable may be bound. 
+:- type datastruct 
+    --->    selected_cel(
+                sc_var ::   prog_var,
+                sc_selector ::  selector
+            ).
+
+        % A selector describes a path in a type-tree.
+:- type selector == list(unit_selector).
+
+        % Unit-selectors are either term selectors or type selectors. 
+        % A term selector selects a subterm f/n of a term, where f is a
+        % functor (identified by the cons_id), and n an integer. 
+        % A type selector designates any subterm that has that specific type.
+:- type unit_selector 
+    --->    termsel(cons_id, int)    % term selector
+    ;       typesel(mer_type).           % type selector
+
+%-----------------------------------------------------------------------------%
+%
 % Stuff for the `unused_args' pragma
 %
 
Index: structure_sharing.domain.m
===================================================================
RCS file: structure_sharing.domain.m
diff -N structure_sharing.domain.m
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ structure_sharing.domain.m	16 Jan 2006 10:38:51 -0000
@@ -0,0 +1,1518 @@
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU General
+% Public License - see the file COPYING in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% File: ctgc.structure_sharing.domain.m
+% Main authors: nancy
+%
+% Definition of the abstract domain for representing structure sharing between 
+% data structures. 
+% This domain forms a complete lattice. It has a bottom element (representing 
+% the definite absence of any possible structure sharing), and a top element
+% (that represents any possible structure sharing), a least upper bound 
+% operation, and a comparison predicate (is_subsumed_by). 
+%
+% The auxiliary functions needed for using the domain within the abstract
+% semantics on which the implementation of the analysis is based are: 
+% 	* project: limit the abstract information to include only the 
+% 		information regarding some given set of variables.
+% 	* rename: given a mapping of variables, this operation renames every
+% 		occurrence of a variable to its mapping.
+%   * init: create an initial empty sharing set that represents the absence
+%     of any possible sharing. 
+%   * comb: combine new sharing information (that usually stems from a
+%     procedure call) with existing sharing such that the result correctly 
+%     approximates the real sharing that would exist when new concrete
+%     sharing is added to existing sharing. 
+%   * add: add the sharing created by a primitive operation (unification)
+%     to any existing sharing. 
+% 	
+% Additional operations are: 
+%   * extend_datastruct: compute the set of datastructures referring to the
+%     same memory space as a given datastructure, using sharing information.
+%   * conversion operations between the public and private representation
+%     for sharing sets. 
+%
+%-----------------------------------------------------------------------------%
+
+:- module transform_hlds.ctgc.structure_sharing.domain.
+
+:- interface.
+
+:- import_module hlds.hlds_goal.
+:- import_module hlds.hlds_module.
+:- import_module hlds.hlds_pred.
+:- import_module parse_tree.prog_data.
+
+:- import_module list.
+:- import_module map. 
+:- import_module set.
+:- import_module std_util.
+:- import_module string.
+
+:- type sharing_as.
+
+	% Operations w.r.t. the "bottom" element of the lattice. 
+:- func init = sharing_as. 
+:- pred is_bottom(sharing_as::in) is semidet.
+	
+	% Operations w.r.t. the "top" element of the lattice. When sharing 
+	% becomes top, it is useful to know why it has become top. This can 
+	% be recorded and passed to the top-value as a string.
+:- func top_sharing(string) = sharing_as is det.
+:- func top_sharing(string, sharing_as) = sharing_as is det.
+:- pred is_top(sharing_as::in) is semidet.
+
+	% Returns the size of the sharing set. Fails when sharing is top.
+:- pred size(sharing_as::in, int::out) is semidet.
+
+	% Projection operation. 
+	% This operation reduces the sharing information to information 
+	% regarding a given set of variables only. 
+	% Some properties of a call `project(Vars, SharingIn, SharingOut)':
+	% 	* vars(SharingOut) is a subset of Vars.
+	% 	* vars(SharingIn minus SharingOut) union Vars = emptyset.
+:- pred project(list(prog_var)::in, sharing_as::in, sharing_as::out) is det.
+:- pred project_set(set(prog_var)::in, sharing_as::in, 
+	sharing_as::out) is det.
+
+	% Renaming operation.
+	% This operation renames the variables and type variables occurring
+	% in the sharing information according to a variable and type variable
+	% mapping. 
+:- pred rename(map(prog_var, prog_var)::in, maybe(tsubst)::in,
+	sharing_as::in, sharing_as::out) is det.
+
+    % Renaming of the formal description of data structure sharing to the
+    % actual description of the sharing. The formal information is given 
+    % using the module information. A list of variables and types is used as
+    % the actual variables and types. 
+    % recorded in the module info. 
+    % rename_using_module_info(ModuleInfo, PredProcId, ActualVars, ActualTypes,
+    %   FormalSharing, ActualSharing). 
+:- pred rename_using_module_info(module_info::in, pred_proc_id::in, 
+    list(prog_var)::in, list(mer_type)::in, 
+    sharing_as::in, sharing_as::out) is det.
+
+    % One of the cornerstone operations of using the program analysis system 
+    % is to provide a "comb" (combination) operation that combines new 
+    % information with old information to obtain a new description. Within the
+    % analysis system, the "comb" operation is used to combine the information
+    % of a predicate call (the new information) to the information that is 
+    % already available before the predicate call (the old information). The
+    % result must be a correct description of the execution state that would
+    % be obtained if the predicate call is executed in the circumstances 
+    % described by the old information. 
+    %
+    % comb is not commutative! 
+    % The correct call is: 
+    % Result = comb(ModuleInfo, ProcInfo, NewSharing, OldSharing).
+:- func comb(module_info, proc_info, sharing_as, sharing_as) = sharing_as.
+
+    % Yet another basic function used within the analysis framework: add. 
+    % This operation adds the sharing created by a unification to the already
+    % existing sharing information.
+:- func add(module_info, proc_info, unification, 
+    hlds_goal_info, sharing_as) = sharing_as.
+
+    % Compare two sharing sets. A sharing set Set1 is subsumed by a sharing set
+    % Set2 iff the total set of sharing represented by Set1 is a subset of the
+    % total set of sharing represented by Set2. This means that for every
+    % structure sharing pair in Set1, there exists a structure sharing pair P2
+    % in Set2, such that P1 is subsumed by P2 (i.e. P2 at least describes the
+    % same sharing as P1). 
+:- pred is_subsumed_by(module_info::in, proc_info::in, sharing_as::in, 
+    sharing_as::in) is semidet.
+ 
+    % Compute the least upper bound. 
+:- func least_upper_bound(module_info, proc_info, sharing_as, 
+    sharing_as) = sharing_as. 
+:- func least_upper_bound(module_info, proc_info, list(sharing_as)) = 
+    sharing_as. 
+
+    % Compute the set of data structures whose memory representation coincide
+    % with the memory representation of the given datastructure. 
+	% This corresponds to the "extend" operation used in Nancy's Phd. 
+	% The operation produces a software error when called with
+	% a top alias description. 
+:- pred extend_datastruct(module_info::in, proc_info::in, datastruct::in,
+    sharing_as::in, list(datastruct)::out) is det.
+
+    % Conversion between the public and the private representation for
+    % structure sharing sets. 
+:- func from_structure_sharing_domain(structure_sharing_domain) = sharing_as. 
+:- func to_structure_sharing_domain(sharing_as) = structure_sharing_domain.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+:- implementation. 
+
+:- import_module check_hlds.type_util.
+:- import_module libs.compiler_util.
+:- import_module parse_tree.prog_type.
+:- import_module hlds.hlds_llds.
+
+:- import_module int.
+:- import_module require.
+
+:- type sharing_as 
+	---> 	real_as(sharing_set)
+	;	bottom
+	;	top(list(string)).
+
+init = bottom.
+is_bottom(bottom). 
+top_sharing(Msg) = top([Msg]).
+top_sharing(Msg, SharingAs) = TopSharing :- 
+	(
+		SharingAs = real_as(_),
+		Msgs = [Msg]
+	; 	
+		SharingAs = bottom,
+		Msgs = [Msg]
+	; 
+		SharingAs = top(Msgs0),
+		list__cons(Msg, Msgs0, Msgs)
+	), 
+	TopSharing = top(Msgs).
+is_top(top(_)).
+
+size(bottom, 0).
+size(real_as(SharingSet), sharing_set_size(SharingSet)).
+
+    % inproject = projection such that result contains information about
+    %   selection of variables only. 
+    % outproject = projection such that result contains information about
+    %   all variables _except_ the selection of variables.
+:- type projection_type ---> inproject; outproject. 
+
+project(ListVars, SharingAs0, SharingAs):- 
+    project(inproject, ListVars, SharingAs0, SharingAs). 
+
+:- pred project(projection_type::in, list(prog_var)::in, sharing_as::in, 
+    sharing_as::out) is det.
+project(ProjectionType, ListVars, SharingAs0, SharingAs) :- 
+	(
+		SharingAs0 = bottom, 
+		SharingAs = SharingAs0
+	;
+		SharingAs0 = real_as(SharingSet0),
+		sharing_set_project(ProjectionType, ListVars, SharingSet0, 
+            SharingSet),
+		wrap(SharingSet, SharingAs)
+	;
+		SharingAs0 = top(_),
+		SharingAs = SharingAs0
+	).
+
+project_set(SetVars, !SharingAs) :- 
+	project(set__to_sorted_list(SetVars), !SharingAs).
+
+rename(MapVar, MaybeTypeSubst, SharingAs0, SharingAs) :- 
+	(
+		SharingAs0 = real_as(SharingSet0),
+		sharing_set_rename(MapVar, MaybeTypeSubst, SharingSet0, 
+			SharingSet),
+		SharingAs = real_as(SharingSet)
+	;
+		SharingAs0 = bottom,
+		SharingAs = bottom
+	;
+		SharingAs0 = top(_), 
+		SharingAs = SharingAs0
+	).
+
+rename_using_module_info(ModuleInfo, PredProcId, ActualVars, ActualTypes,
+		FormalSharing, ActualSharing):- 
+	module_info_pred_proc_info(ModuleInfo, PredProcId, PredInfo,
+			ProcInfo),
+	pred_info_arg_types(PredInfo, FormalTypes), 
+	proc_info_headvars(ProcInfo, FormalVars),
+	map__from_corresponding_lists(FormalVars, ActualVars, Dict), 
+        % XXX Check the direction here. Different imlementation. 
+    (
+        prog_type.type_unify_list(FormalTypes, ActualTypes, [], map__init, 
+            TypeSubstitution)
+    -> 
+	    rename(Dict, yes(TypeSubstitution), FormalSharing, ActualSharing)
+    ; 
+        unexpected(this_file, "Types are supposed to be unifiable.")
+    ).
+
+comb(ModuleInfo, ProcInfo, NewSharing, OldSharing) = ResultSharing :- 
+    (
+        NewSharing = real_as(NewSharingSet),
+        (
+            OldSharing = real_as(OldSharingSet),
+            ResultSharing = wrap(sharing_set_comb(ModuleInfo, ProcInfo, 
+                NewSharingSet, OldSharingSet))
+        ; 
+            OldSharing = bottom,
+            ResultSharing = NewSharing
+        ; 
+            OldSharing = top(_), 
+            ResultSharing = OldSharing
+        )
+    ; 
+        NewSharing = bottom,
+        ResultSharing = OldSharing
+    ; 
+        NewSharing = top(MsgNew),
+        (
+            OldSharing = top(MsgOld)
+        -> 
+            ResultSharing = top(list.append(MsgNew, MsgOld))
+        ;
+            ResultSharing = NewSharing
+        )
+    ).
+
+add(ModuleInfo, ProcInfo, Unification, GoalInfo, 
+    OldSharing) = NewSharing :- 
+    UnifSharing = sharing_from_unification(ModuleInfo, 
+        ProcInfo, Unification, GoalInfo),
+    ResultSharing = comb(ModuleInfo, ProcInfo, UnifSharing, OldSharing),
+    % When the unification is a construction unification, some local variables
+    % may become totally useless for the rest of the code (deaths), and so 
+    % any structure sharing involving these variables may safely be removed. 
+    %
+    % Note that this "useless" sharing information can not be removed earlier
+    % as it can contribute to new sharing with the comb operation. 
+    (
+		Unification = construct(_, _, _, _, _, _, _)
+	-> 
+		NewSharing = optimization_remove_deaths(ProcInfo, 
+            GoalInfo, ResultSharing)
+	;
+		NewSharing = ResultSharing
+	).
+
+    % Describe the sharing that is created between the variables involved in 
+    % unification. 
+:- func sharing_from_unification(module_info, proc_info, unification,
+    hlds_goal_info) = sharing_as.
+
+sharing_from_unification(ModuleInfo, ProcInfo, Unification, 
+    GoalInfo) = Sharing :- 
+    (
+        Unification = construct(Var, ConsId, Args0, _, _, _, _),
+        list__takewhile(is_introduced_typeinfo_arg(ProcInfo), Args0, 
+            _TypeInfoArgs, Args), 
+        number_args(Args, NumberedArgs),
+        list__foldl(
+            add_var_arg_sharing(ModuleInfo, ProcInfo, Var, ConsId),
+            NumberedArgs,
+            sharing_set_init, 
+            SharingSet0),
+        create_internal_sharing(ModuleInfo, ProcInfo, Var, ConsId, 
+            NumberedArgs, SharingSet0, SharingSet), 
+        Sharing = wrap(SharingSet)
+    ; 
+        Unification = deconstruct(Var, ConsId, Args0, _, _, _),
+        list__takewhile(is_introduced_typeinfo_arg(ProcInfo), Args0, 
+            _TypeInfoArgs, Args), 
+        number_args(Args, NumberedArgs),
+        optimize_for_deconstruct(GoalInfo, NumberedArgs, ReducedNumberedArgs),
+        list__foldl(
+            add_var_arg_sharing(ModuleInfo, ProcInfo, Var, ConsId),
+            ReducedNumberedArgs,
+            sharing_set_init, 
+            SharingSet),
+        Sharing = wrap(SharingSet)
+    ; 
+        Unification = assign(X, Y),
+        (
+            arg_has_primitive_type(ModuleInfo, ProcInfo, X)
+        -> 
+            Sharing = init
+        ; 
+            new_entry(ModuleInfo, ProcInfo, 
+                datastruct.init(X) - datastruct.init(Y), 
+                sharing_set_init, SharingSet), 
+            Sharing = wrap(SharingSet)
+        )
+    ; 
+        Unification = simple_test(_, _),
+        Sharing = init
+    ;
+        Unification = complicated_unify(_, _, _),
+        % XXX needs to be studied again. For the moment generate top. 
+        Sharing = top_sharing("Encountered complicated unify") 
+    ). 
+
+:- pred is_introduced_typeinfo_arg(proc_info::in, prog_var::in) is semidet.
+is_introduced_typeinfo_arg(ProcInfo, Var) :- 
+    proc_info_vartypes(ProcInfo, VarTypes), 
+    map__lookup(VarTypes, Var, Type), 
+    prog_type.is_introduced_type_info_type(Type).
+    
+:- pred number_args(list(prog_var)::in, list(pair(int, prog_var))::out) is det.
+number_args(Args, NumberedArgs) :- 
+	list__map_foldl(
+		pred(A::in, AP::out, Nin::in, Nout::out) is det:- 
+		(
+			AP = Nin - A,
+			Nout = Nin + 1
+		),
+		Args,
+		NumberedArgs,
+		1, _).
+
+:- pred add_var_arg_sharing(module_info::in, proc_info::in, prog_var::in,
+    cons_id::in, pair(int, prog_var)::in, sharing_set::in, 
+    sharing_set::out) is det.
+add_var_arg_sharing(ModuleInfo, ProcInfo, Var, ConsId, N - Arg, 
+    Sharing0, Sharing) :- 
+    (
+        arg_has_primitive_type(ModuleInfo, ProcInfo, Arg)
+    -> 
+        Sharing = Sharing0
+    ; 
+        Data1 = datastruct.init(Var, ConsId, N),
+        Data2 = datastruct.init(Arg), 
+        new_entry(ModuleInfo, ProcInfo, Data1 - Data2, Sharing0, Sharing)
+    ).
+
+:- pred arg_has_primitive_type(module_info::in, proc_info::in, 
+    prog_var::in) is semidet.
+arg_has_primitive_type(ModuleInfo, ProcInfo, Var):- 
+    proc_info_vartypes(ProcInfo, VarTypes), 
+    map__lookup(VarTypes, Var, Type), 
+    type_util.type_is_atomic(Type, ModuleInfo).
+
+    % When two positions within the constructed term refer to the same variable,
+    % this must be recorded as an extra sharing pair. 
+    % E.g.: X = f(Y,Y), then the sharing between f/1 and f/2 must be recorded.
+    % XXX Different implementation!
+:- pred create_internal_sharing(module_info::in, proc_info::in, 
+    prog_var::in, cons_id::in, list(pair(int, prog_var))::in, 
+    sharing_set::in, sharing_set::out) is det.
+create_internal_sharing(ModuleInfo, ProcInfo, Var, ConsId, NumberedArgs, 
+    !Sharing) :- 
+    % For every argument and the occurrence of the variable of that argument
+    % in the rest of the arguments, add the appropriate sharing pair. 
+    (
+        NumberedArgs = [First | Remainder],
+        First = Pos1 - Var1,
+        list__foldl(
+            pred(OtherNumberedArg::in, S0::in, S::out) is det :- 
+            (
+                OtherNumberedArg = Pos2 - Var1
+            -> 
+                % Create sharing between Pos1 and Pos2
+                Data1 = datastruct.init(Var, ConsId, Pos1), 
+                Data2 = datastruct.init(Var, ConsId, Pos2), 
+                new_entry(ModuleInfo, ProcInfo, Data1 - Data2, S0, S)
+
+            ;
+                S = S0
+            ),
+            Remainder, !Sharing),
+        create_internal_sharing(ModuleInfo, ProcInfo, 
+            Var, ConsId, Remainder, !Sharing)
+    ;
+        NumberedArgs = []
+    ).
+
+	% For deconstructions, a huge optimization can be made by
+	% avoiding the construction of sharing between variables that are not
+    % used in the remainder of the code anyway. The set of used args is
+    % known as the pre-birth set as computed by the liveness-pass (liveness.m).
+:- pred optimize_for_deconstruct(hlds_goal_info::in, 
+    list(pair(int, prog_var))::in, 
+    list(pair(int, prog_var))::out) is det.
+optimize_for_deconstruct(GoalInfo, NumberedArgs0, NumberedArgs) :- 
+    hlds_llds.goal_info_get_pre_births(GoalInfo, PreBirthSet),
+    list__filter(
+        pred(NumberedArg::in) is semidet :- 
+        (
+            NumberedArg = _N - Var, 
+            set__member(Var, PreBirthSet)
+        ),
+        NumberedArgs0, 
+        NumberedArgs).
+
+
+:- func optimization_remove_deaths(proc_info, hlds_goal_info,
+    sharing_as) = sharing_as.
+optimization_remove_deaths(ProcInfo, GoalInfo, Sharing0) = Sharing :- 
+    proc_info_headvars(ProcInfo, HeadVars), 
+    set__list_to_set(HeadVars, HeadVarsSet), 
+    hlds_llds.goal_info_get_post_deaths(GoalInfo, Deaths0), 
+        % Make sure to keep all the information about the headvars, 
+        % even if they are in the post deaths set. 
+    set__difference(Deaths0, HeadVarsSet, Deaths), 
+    set__to_sorted_list(Deaths, DeathsList), 
+    project(outproject, DeathsList, Sharing0, Sharing).
+
+is_subsumed_by(ModuleInfo, ProcInfo, Sharing1, Sharing2):-
+    (
+        Sharing2 = top(_)
+    ; 
+        Sharing1 = bottom
+    ;
+        Sharing1 = real_as(SharingSet1), 
+        Sharing2 = real_as(SharingSet2), 
+        sharing_set_is_subsumed_by(ModuleInfo, ProcInfo, SharingSet1, 
+            SharingSet2)
+    ).
+
+least_upper_bound(ModuleInfo, ProcInfo, Sharing1, Sharing2) = Sharing :- 
+    (
+        Sharing1 = bottom,
+        Sharing = Sharing2
+    ;
+        Sharing1 = top(Msg1),
+        (
+            Sharing2 = top(Msg2)
+        -> 
+            Sharing = top(list__append(Msg1, Msg2))
+        ;
+            Sharing = Sharing1
+        )
+    ;
+        Sharing1 = real_as(SharingSet1),
+        (
+            Sharing2 = bottom, 
+            Sharing = Sharing1
+        ;
+            Sharing2 = top(_), 
+            Sharing = Sharing2
+        ; 
+            Sharing2 = real_as(SharingSet2), 
+            Sharing = real_as(sharing_set_least_upper_bound(ModuleInfo, 
+                ProcInfo, SharingSet1, SharingSet2))
+
+        )
+    ).
+
+least_upper_bound(ModuleInfo, ProcInfo, SharingList) = 
+    list__foldl(least_upper_bound(ModuleInfo, ProcInfo), SharingList, 
+        init). 
+
+extend_datastruct(ModuleInfo, ProcInfo, Datastruct, SharingAs, Datastructs):- 
+    (
+        SharingAs = bottom,
+        Datastructs = []
+    ;
+        SharingAs = real_as(SharingSet), 
+        sharing_set_extend_datastruct(ModuleInfo, ProcInfo, Datastruct,
+            SharingSet, Datastructs)
+    ;
+        SharingAs = top(_),
+        unexpected(this_file, "extend_datastruct with top sharing set.")
+    ).
+
+from_structure_sharing_domain(SharingDomain) = SharingAs :- 
+	(
+		SharingDomain = bottom,
+		SharingAs = bottom
+	;
+		SharingDomain = real(StructureSharing),
+		SharingSet = from_sharing_pair_list(StructureSharing),
+		wrap(SharingSet, SharingAs)
+	; 
+		SharingDomain = top(Msgs), 
+		SharingAs = top(Msgs)
+	).
+
+
+to_structure_sharing_domain(SharingAs) = SharingDomain :- 
+    (
+        SharingAs = bottom, 
+        SharingDomain = bottom
+    ;
+        SharingAs = real_as(SharingSet), 
+        SharingDomain = real(to_sharing_pair_list(SharingSet))
+    ;
+        SharingAs = top(Msgs), 
+        SharingDomain = top(Msgs)
+    ).
+
+%-----------------------------------------------------------------------------%
+% Type: sharing_set. 
+% Definition of the (hidden) representation for lists of sharing data
+% structures. 
+% XXX The definition and implementation of sharing_set should be in a separate
+% (sub)module. Yet this gave compilation errors. To do. 
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+% Type definition. 
+% 
+% Theoretically, a structure sharing set is a set of structure sharing
+% pairs, i.e., pairs of data structures reflecting the possible sharing between
+% them. However, lookup operations occur often, and have a dramatic performance
+% using this simple representation. We therefore use a hierarchy of different
+% map-types to represent a structure sharing set. 
+%
+% Hence: In the sharing_set we map a prog_var to a description of the
+% structure sharing pairs it is involved in. These structure sharing pairs
+% are represented as a map mapping selectors on data structure sets.
+% Suppose (Sel-Data) is in the map to which prog_var V relates to, then this 
+% means that the memory space for V^Sel might share with the memory spaces
+% used for each of the data structures in Data. 
+% Note that in the sharing_set type we explicitly keep track of the number of 
+% structure sharing pairs at each level of the map. 
+%
+% Example: 
+% A set of one sharing pair expressing that the memory space
+% for the term of a variable X might be the same as the memory space used
+% to store the term of a variable Y: 
+% * Plain representation would be: { (X^\epsilon - Y^\epsilon) } 
+% * Optimised representation: 
+% 	sharing_set(
+% 		2, 		% number of structure sharing pairs in the
+% 				% sharing set. If X-Y is sharing, then also 
+% 				% Y-X, hence in this case "2". 
+% 	    	{ 
+%			X -> selector_sharing_set(
+%				1,  	% number of data structures with
+%					% which terms of X share in this set.
+%				{  \epsilon -> Y^\epsilon }
+%			)
+%			Y -> selector_sharing_set(
+%				1, 
+%				{ \epsilon -> X^\epsilon }
+%			)
+% 	    	}
+%	)
+%-----------------------------------------------------------------------------%
+%
+:- import_module transform_hlds.ctgc.datastruct.
+:- import_module transform_hlds.ctgc.selector.
+
+
+:- type sharing_set 
+	---> sharing_set(
+		int,	% number of structure sharing pairs represented
+			% by the set.
+		map(prog_var, selector_sharing_set)
+	).
+:- type selector_sharing_set 
+	---> selector_sharing_set(
+		int, 	% number of data structures represented by this
+			% set. 
+		map(selector, data_set)
+	).
+
+:- type data_set 
+	---> datastructures(
+		int, 	% size of the set of data structures.
+		set(datastruct)
+	). 
+
+%-----------------------------------------------------------------------------%
+% sharing_set predicates/functions.
+%
+	
+:- func sharing_set_init = sharing_set is det.
+:- pred sharing_set_is_empty(sharing_set::in) is semidet.
+:- func sharing_set_size(sharing_set) = int.
+
+:- pred wrap(sharing_set::in, sharing_as::out) is det.
+:- func wrap(sharing_set) = sharing_as.
+
+:- pred sharing_set_project(projection_type::in, 
+    list(prog_var)::in, sharing_set::in, 
+	sharing_set::out) is det.
+:- pred sharing_set_rename(map(prog_var, prog_var)::in, 
+	maybe(tsubst)::in, sharing_set::in, 
+	sharing_set::out) is det.
+
+:- func sharing_set_comb(module_info, proc_info, sharing_set, sharing_set) =
+    sharing_set.
+
+:- pred sharing_set_is_subsumed_by(module_info::in, proc_info::in, 
+    sharing_set::in, sharing_set::in) is semidet.
+
+:- func sharing_set_least_upper_bound(module_info, proc_info, sharing_set,
+    sharing_set) = sharing_set. 
+
+:- pred sharing_set_extend_datastruct(module_info::in, proc_info::in,
+    datastruct::in, sharing_set::in, list(datastruct)::out) is det.
+
+	% Conversion between list of sharing data structures to 
+	% sharing_set's and vice versa.
+    %
+    % Note: from_sharing_pair_list assumes that the sharing set is minimal, ie,
+    % there are no two sharing pairs in that set such that one sharing pair
+    % subsumes the other pair.
+:- func from_sharing_pair_list(list(structure_sharing_pair)) = sharing_set.
+:- func to_sharing_pair_list(sharing_set) = list(structure_sharing_pair).
+
+
+%-----------------------------------------------------------------------------%
+
+sharing_set_init = sharing_set(0, map__init).
+sharing_set_is_empty(sharing_set(0, _Map)).
+sharing_set_size(sharing_set(Size, _)) = Size.
+
+wrap(SharingSet, SharingAs) :- 
+	( 
+		sharing_set_is_empty(SharingSet)
+	-> 
+		SharingAs = bottom
+	; 
+		SharingAs = real_as(SharingSet)
+	).
+wrap(SharingSet) = SharingAs :- 
+    wrap(SharingSet, SharingAs).
+
+sharing_set_project(ProjectionType, Vars, SharingSet0, SharingSet) :- 
+	SharingSet0 = sharing_set(_, Map0), 
+    ( 
+        ProjectionType = inproject, 
+	    map__select(Map0, set__list_to_set(Vars), Map1)
+    ; 
+        ProjectionType = outproject, 
+        map__keys(Map0, AllVars), 
+        set__difference(set__list_to_set(AllVars), 
+                        set__list_to_set(Vars), Remainder),
+        map__select(Map0, Remainder, Map1)
+    ),
+	map__foldl(
+		pred(Var::in, SelSet0::in, S0::in, S::out) is det :- 
+		    (
+			selector_sharing_set_project(ProjectionType, 
+                Vars, SelSet0, SelSet), 
+			(
+				selector_sharing_set_is_empty(SelSet)
+			->
+				S = S0
+			;
+		    	S0 = sharing_set(Size0, M0), 	
+				map__det_insert(M0, Var, SelSet, M),
+				Size = Size0 +
+					selector_sharing_set_size(SelSet),
+				S = sharing_set(Size, M)
+			)
+		   ), 
+		Map1, 
+		sharing_set_init, 
+		SharingSet).
+
+sharing_set_rename(Dict, MaybeTypeSubst, SharingSet0, SharingSet) :- 
+	SharingSet0 = sharing_set(Size, Map0), 
+	map__foldl(
+		pred(Var0::in, SelectorSet0::in, M0::in, M::out) is det:- 
+		    (
+			selector_sharing_set_rename(Dict, MaybeTypeSubst, 
+				SelectorSet0, SelectorSet),
+			map__lookup(Dict, Var0, Var), 
+
+			% XXX old code pretends that 2 vars can be renamed to 
+			% To check. 
+			% (
+			%	map__search(M0, Var, SelectorSet2)
+			%-> 
+			%	% can occur when 2 vars are renamed to 
+			%	% the same var (call: append(X,X,Y))
+			%	selector_sharing_set_add(SelectorSet1, 
+			%		SelectorSet2, SelectorSet), 
+			%	map__det_update(M0, Var, SelectorSet, M)
+			%; 
+			%	map__det_insert(M0, Var, SelectorSet1, M)
+			%)
+			map__det_insert(M0, Var, SelectorSet, M)
+		   ),
+		Map0, 
+		map__init, 
+		Map),
+	SharingSet  = sharing_set(Size, Map). 
+
+    % The implementation for combining sharing sets is to compute the 
+    % alternating closure of those sets. 
+    % Adapted copy/paste of the definition as given in Phd Nancy
+    % (definition 6.31): 
+    % Let X, Y be sets of pairs of elements of any kind, then 
+    % altclos(X, Y) = { (a_0, a_n) | 
+    %   a sequence (a_0, a_1).(a_1, a_2). ... .(a_(n_1),a_n) can be constructed
+    %   where adjoining pairs stem from either X or Y, i.e., if (a_i, a_(i+1))
+    %   \in X, then (a_(i+1), a_(i+2)) \from Y. 
+    %
+    % Although the theoretic definition is commutative, the implementation uses
+    % some of the known properties of existings sharing and additional sharing,
+    % which simplifies the implementation, yet makes it non-commutative. 
+    % Instead of computing needless chains of sharing pairs, the alternating 
+    % closure of a NewSharingSet, and an OldSharingSet, is equivalent to the
+    % least upper bound of the sets (Corollary 10.1): 
+    %   * NewSharingSet
+    %   * OldSharingSet
+    %   * sharing pairs formed using paths of length two (direction irrelevant)
+    %   * sharing pairs formed using paths of length three N - O - N, where
+    %   N are sharing pairs from NewSharingSet, and O is a sharing pair from
+    %   OldSharingSet. 
+sharing_set_comb(ModuleInfo, ProcInfo, NewSharingSet, OldSharingSet) = 
+    ResultSharingSet :- 
+
+    % paths of length 2: 
+    OldNewSharingSet = sharing_set_altclos_2(ModuleInfo, ProcInfo,    
+        NewSharingSet, OldSharingSet),
+
+    % paths of length 3: 
+    NewOldNewSharingSet = sharing_set_altclos_3_directed(ModuleInfo, ProcInfo,
+        NewSharingSet, OldSharingSet),
+
+    % combine it all: 
+    ResultSharingSet = sharing_set_least_upper_bound(ModuleInfo, ProcInfo, 
+        [NewSharingSet, OldSharingSet, OldNewSharingSet, NewOldNewSharingSet]).
+
+
+% XXX new implementation.
+:- func sharing_set_altclos_2(module_info, proc_info, sharing_set, 
+    sharing_set) = sharing_set.
+
+sharing_set_altclos_2(ModuleInfo, ProcInfo, NewSharingSet, 
+    OldSharingSet) = ResultSharingSet :- 
+
+    NewSharingSet = sharing_set(_, NewMap), 
+    OldSharingSet = sharing_set(_, OldMap), 
+
+    % compute common vars: 
+    map__keys(NewMap, NewVars), 
+    map__keys(OldMap, OldVars), 
+    set__list_to_set(NewVars, NewVarsSet), 
+    set__list_to_set(OldVars, OldVarsSet), 
+    set__intersect(NewVarsSet, OldVarsSet, CommonVarsSet),
+    set__to_sorted_list(CommonVarsSet, CommonVars), 
+
+    % downsize the maps to contain only the keys regarding the common vars: 
+    map__select(NewMap, CommonVarsSet, NewMap1), 
+    map__select(OldMap, CommonVarsSet, OldMap1), 
+
+	proc_info_vartypes(ProcInfo, VarTypes), 
+
+    % for each common var V, compute the sharing pairs A-B, such that
+    % \exists X where var(X) = V, and X-A \in NewSharingSet, and X-B \in 
+    % OldSharingSet.
+    list__foldl(
+        pred(Var::in, SS0::in, SS::out) is det :- 
+        (  
+            map__lookup(VarTypes, Var, Type), 
+            map__lookup(NewMap1, Var, NewSelSet), 
+            map__lookup(OldMap1, Var, OldSelSet), 
+            SharingPairs = selector_sharing_set_altclos(ModuleInfo, ProcInfo, 
+                Type, NewSelSet, OldSelSet), 
+            new_entries(ModuleInfo, ProcInfo, SharingPairs, SS0, SS)
+        ), 
+        CommonVars,
+        sharing_set_init, 
+        ResultSharingSet).
+
+
+% sharing_set_altclos_3_directed(ModuleInfo, ProcInfo, NewSharingSet, 
+%   OldSharingSet) =
+% Compute the sharing pairs A-B such that exists X-Y \in OldSharingSet and
+%   A - X \subsumed by NewSharingSet,
+%   Y - B \subsumed by NewSharingSet.
+% XXX New implementation. 
+:- func sharing_set_altclos_3_directed(module_info, proc_info, sharing_set,
+    sharing_set) = sharing_set.
+
+sharing_set_altclos_3_directed(ModuleInfo, ProcInfo, NewSharingSet, 
+    OldSharingSet) = ResultSharingSet :- 
+
+    NewSharingSet = sharing_set(_, NewMap), 
+    OldSharingSet = sharing_set(_, OldMap), 
+
+    % compute common vars: 
+    map__keys(NewMap, NewVars), 
+    map__keys(OldMap, OldVars), 
+    set__list_to_set(NewVars, NewVarsSet), 
+    set__list_to_set(OldVars, OldVarsSet), 
+    set__intersect(NewVarsSet, OldVarsSet, CommonVarsSet),
+    set__to_sorted_list(CommonVarsSet, CommonVars), 
+
+    % downsize OldSharingSet to contain only information regarding the 
+    % common vars, hence a full projection...
+    sharing_set_project(inproject, CommonVars, 
+        OldSharingSet, OldSharingSetProjected),
+    % As each and every pair within OldMapProjected needs to be looked at, 
+    % we might as well use the full list representation: 
+    OldSharingPairs = to_sharing_pair_list(OldSharingSetProjected),
+
+    % Now for each sharing pair X-Y represented by OldMapProjected, find
+    % all the datastructures in NewSharingMap that cover X, find
+    % all the datastructures in NewSharingMap that cover Y, and compute
+    % the crossproduct of both sets returning the set of new sharing pairs.
+
+    list__foldl(
+        pred(X - Y::in, SS0::in, SS::out) is det :- 
+        (
+            sharing_set_extend_datastruct(ModuleInfo, ProcInfo, X, 
+                NewSharingSet, ExtendedX),
+            sharing_set_extend_datastruct(ModuleInfo, ProcInfo, Y, 
+                NewSharingSet, ExtendedY), 
+            set_cross_product(set.from_list(ExtendedX), 
+                set.from_list(ExtendedY), SetPairs),
+            new_entries(ModuleInfo, ProcInfo, 
+                set.to_sorted_list(SetPairs), SS0, SS)
+        ),
+        OldSharingPairs,
+        sharing_set_init,
+        ResultSharingSet).
+    
+    % SharingSet1 is subsumed by SharingSet2 iff every sharing pair
+    % represented by SharingSet1 is subsumed by any of the sharing pairs
+    % represented by SharingSet2. 
+    % XXX For the moment SharingSet1 is converted to a list of sharing pairs, 
+    % and each of the sharing pairs is checked for subsumption. This should be
+    % optimised to follow the inner structure of sharing_set instead. 
+sharing_set_is_subsumed_by(ModuleInfo, ProcInfo, SharingSet1, SharingSet2):-
+    list__all_true(sharing_set_subsumes_sharing_pair(ModuleInfo, ProcInfo,
+        SharingSet2), to_sharing_pair_list(SharingSet1)).
+
+sharing_set_least_upper_bound(ModuleInfo, ProcInfo, Set1, Set2) = Union :- 
+    % Foldling over the map could be done, but the union is easier to describe
+    % by picking each of the sharing pairs represented by the smallest sharing
+    % set, and adding them to the other sharing set. 
+    Set1 = sharing_set(Size1, _), 
+    Set2 = sharing_set(Size2, _), 
+    (
+        Size1 < Size2
+    -> 
+        Pairs = to_sharing_pair_list(Set1),
+        Set = Set2
+    ; 
+        Pairs = to_sharing_pair_list(Set2), 
+        Set = Set1
+    ), 
+    new_entries(ModuleInfo, ProcInfo, Pairs, Set, Union).
+
+:- func sharing_set_least_upper_bound(module_info, proc_info,
+    list(sharing_set)) = sharing_set.
+
+sharing_set_least_upper_bound(ModuleInfo, ProcInfo, ListSharingSet) = 
+    list.foldl(sharing_set_least_upper_bound(ModuleInfo, ProcInfo),
+        ListSharingSet, sharing_set_init).
+        
+
+sharing_set_extend_datastruct(ModuleInfo, ProcInfo, Datastruct, SharingSet,
+    Datastructs) :- 
+    SharingSet = sharing_set(_, SharingMap),
+    Var = Datastruct^sc_var,
+    Selector = Datastruct^sc_selector,
+    (
+        map__search(SharingMap, Var, SelectorSet)
+    ->
+            % The type of the variable is needed to be able to compare
+            % datastructures.
+        proc_info_vartypes(ProcInfo, VarTypes),
+        map__lookup(VarTypes, Var, VarType), 
+        selector_sharing_set_extend_datastruct(ModuleInfo, VarType, 
+            Selector, SelectorSet, Datastructs)
+    ;
+        Datastructs = []
+    ).
+
+from_sharing_pair_list(SharingPairs) = SharingSet :-
+    list__foldl(new_entry_no_controls, SharingPairs, sharing_set_init,
+        SharingSet).
+
+	% Add a new sharing pair into the existing sharing set. This operation
+    % takes into account subsumption:
+    % * if the new sharing pair is subsumed by any of the sharing already
+    % present in the set, then this operation is a null operation. 
+    % * if the new sharing pair subsumes any of the existing sharing, then
+    % all the subsumed sharing pairs must be removed. 
+    %
+    % XXX
+    % Due to the above checks, this operation may become quite costly. To
+    % verify!
+:- pred new_entry(module_info::in, proc_info::in, 
+    structure_sharing_pair::in, sharing_set::in, sharing_set::out) is det.
+new_entry(ModuleInfo, ProcInfo, SharingPair, !SharingSet) :- 
+    (
+        sharing_set_subsumes_sharing_pair(ModuleInfo, ProcInfo, 
+            !.SharingSet, SharingPair)
+    -> 
+        true
+    ; 
+        sharing_set_subsumed_subset(ModuleInfo, ProcInfo, 
+            !.SharingSet, SharingPair, SubsumedPairs), 
+        remove_entries(SubsumedPairs, !SharingSet),
+        new_entry_no_controls(SharingPair, !SharingSet)
+    ).
+
+:- pred new_entry_no_controls(structure_sharing_pair::in, sharing_set::in,
+    sharing_set::out) is det.
+new_entry_no_controls(SharingPair, !SS) :-
+    SharingPair = Data1 - Data2, 
+    new_directed_entry(Data1, Data2, !SS),
+    (
+        ctgc.datastruct.equal(Data1, Data2)
+    ->
+        true
+    ;
+        new_directed_entry(Data2, Data1, !SS)
+    ).
+
+:- pred remove_entries(list(structure_sharing_pair)::in, sharing_set::in,
+    sharing_set::out) is det.
+remove_entries(SharingPairs, !SS):- 
+    list__foldl(remove_entry, SharingPairs, !SS).
+
+    % Remove a structure sharing pair that is known to be explicitly 
+    % represented in the sharing set. 
+    % Software error if the sharing pair is not part of the set.
+:- pred remove_entry(structure_sharing_pair::in, sharing_set::in, 
+    sharing_set::out) is det.
+remove_entry(SharingPair, !SharingSet) :- 
+    SharingPair = Data1 - Data2, 
+    remove_directed_entry(Data1, Data2, !SharingSet), 
+    (
+        ctgc.datastruct.equal(Data1, Data2)
+    -> 
+        true
+    ; 
+        remove_directed_entry(Data2, Data1, !SharingSet)
+    ).
+
+:- pred remove_directed_entry(datastruct::in, datastruct::in, sharing_set::in,
+    sharing_set::out) is det.
+remove_directed_entry(FromData, ToData, SharingSet0, SharingSet) :- 
+    FromVar = FromData ^ sc_var, 
+    FromSel = FromData ^ sc_selector, 
+
+    SharingSet0 = sharing_set(Size0, SharingMap0), 
+    map__lookup(SharingMap0, FromVar, SelSharingSet0), 
+    SelSharingSet0 = selector_sharing_set(SelSize0, SelSharingMap0),
+    map__lookup(SelSharingMap0, FromSel, DataSet0), 
+    DataSet0 = datastructures(DataSize0, Data0), 
+    (
+        set__remove(Data0, ToData, Data)
+    ->
+        DataSize = DataSize0 - 1, 
+        SelSize = SelSize0 - 1, 
+        Size = Size0 - 1, 
+
+        ( 
+            Size = 0
+        -> 
+            SharingSet = sharing_set(Size, map__init)
+        ; 
+            SelSize = 0
+        -> 
+            map__delete(SharingMap0, FromVar, SharingMap),
+            SharingSet = sharing_set(Size, SharingMap)
+        ;
+            DataSize = 0
+        ->
+            map__delete(SelSharingMap0, FromSel, SelSharingMap),
+            SelSharingSet = selector_sharing_set(SelSize, SelSharingMap),
+            map__det_update(SharingMap0, FromVar, SelSharingSet, SharingMap),
+            SharingSet = sharing_set(Size, SharingMap)
+        ; 
+            DataSet = datastructures(DataSize, Data),
+            map__det_update(SelSharingMap0, FromSel, DataSet, SelSharingMap), 
+            SelSharingSet = selector_sharing_set(SelSize, SelSharingMap),
+            map__det_update(SharingMap0, FromVar, SelSharingSet, SharingMap),
+            SharingSet = sharing_set(Size, SharingMap)
+        )
+    ;
+        unexpected(this_file, "Removing non-existant sharing pair.")
+    ).
+
+
+    % Determine if the sharing set subsumes the sharing information
+    % represented by the structure sharing pair. 
+    % This means: \exists A-B \in SharingSet, such that A-B is more general
+    % than the given structure sharing pair. 
+:- pred sharing_set_subsumes_sharing_pair(module_info::in, proc_info::in,
+    sharing_set::in, structure_sharing_pair::in) is semidet.
+sharing_set_subsumes_sharing_pair(ModuleInfo, ProcInfo, SharingSet, 
+        SharingPair):- 
+    SharingSet = sharing_set(_, SharingMap), 
+
+    SharingPair = Data1 - Data2, 
+    Var1 = Data1 ^ sc_var, 
+    Sel1 = Data1 ^ sc_selector, 
+    Var2 = Data2 ^ sc_var, 
+    Sel2 = Data2 ^ sc_selector, 
+
+    proc_info_vartypes(ProcInfo, VarTypes), 
+    map__lookup(VarTypes, Var1, Type1), 
+    map__lookup(VarTypes, Var2, Type2), 
+
+    map__lookup(SharingMap, Var1, SelSharingSet), 
+    SelSharingSet = selector_sharing_set(_, SelSharingMap), 
+    map__keys(SelSharingMap, SelectorList), 
+        
+        % Find at least one selector in SelectorList that is more general 
+        % than Sel1 (with a specific extension), and whose associated dataset
+        % contains at least one datastructure that is more general than Data2
+        % (with that same extension). 
+    list__find_first_map(
+        pred(Sel::in, Data::out) is semidet :- 
+        (
+            selector.subsumed_by(ModuleInfo, Sel1, Sel, Type1, Extension), 
+            map__lookup(SelSharingMap, Sel, DataSet), 
+            DataSet = datastructures(_, DatastructureSet), 
+            MatchedDatastructs = list__filter(
+                pred(Datastructure::in) is semidet :-
+                (
+                    Var2 = Datastructure^sc_var, 
+                    selector.subsumed_by(ModuleInfo, Sel2, 
+                        Datastructure^sc_selector, Type2, Extension)
+                ), 
+                to_sorted_list(DatastructureSet)),
+            % The list of matched datastructures contains at least one element.
+            MatchedDatastructs = [Data| _]
+        ), 
+        SelectorList, 
+        _).
+
+
+    % Return the list of sharing pairs included in the sharing set that are 
+    % less or equal to the given sharing pair. 
+:- pred sharing_set_subsumed_subset(module_info::in, proc_info::in, 
+    sharing_set::in, structure_sharing_pair::in, 
+    list(structure_sharing_pair)::out) is det.
+sharing_set_subsumed_subset(ModuleInfo, ProcInfo, SharingSet, SharingPair, 
+    SubsumedPairs) :- 
+    SharingSet = sharing_set(_, SharingMap), 
+
+    SharingPair = Data1 - Data2, 
+    Var1 = Data1 ^ sc_var, 
+    Sel1 = Data1 ^ sc_selector, 
+    Var2 = Data2 ^ sc_var, 
+    Sel2 = Data2 ^ sc_selector, 
+
+    proc_info_vartypes(ProcInfo, VarTypes), 
+    map__lookup(VarTypes, Var1, Type1), 
+    map__lookup(VarTypes, Var2, Type2), 
+
+    map__lookup(SharingMap, Var1, SelSharingSet), 
+    SelSharingSet = selector_sharing_set(_, SelSharingMap), 
+
+        % Determine all Selector-Dataset pairs where
+        %   * Selector is less or equal to Sel1 wrt some extension E,
+        %   * Dataset is a set of datastructures less or equal to Data2 
+        %   (wrt the same extension E). 
+
+    map__keys(SelSharingMap, SelectorList), 
+    list__filter_map(
+        pred(Selector::in, SPairs::out) is semidet :- 
+        (   
+            selector.subsumed_by(ModuleInfo, Selector, Sel1, 
+                Type1, Extension), 
+            map__lookup(SelSharingMap, Selector, Dataset),
+            Dataset = datastructures(_, Datastructs), 
+            list__filter_map(
+                pred(D::in, Pair::out) is semidet :- 
+                (
+                    Var2 = D^sc_var, 
+                    selector.subsumed_by(ModuleInfo, D^sc_selector, Sel2, 
+                        Type2, Extension),
+                    Pair = datastruct.init(Var1, Selector) - D
+                ), 
+                to_sorted_list(Datastructs), 
+                SPairs),
+            SPairs = [_|_]
+        ), 
+        SelectorList, 
+        ListSubsumedPairs), 
+    list__condense(ListSubsumedPairs, SubsumedPairs).
+
+:- pred new_entries(module_info::in, proc_info::in, 
+    list(structure_sharing_pair)::in, sharing_set::in, 
+    sharing_set::out) is det.
+new_entries(ModuleInfo, ProcInfo, SharingPairs, !SS) :- 
+    list__foldl(new_entry(ModuleInfo, ProcInfo), SharingPairs, !SS).
+
+:- pred new_directed_entry(datastruct::in, datastruct::in, 
+				sharing_set::in, sharing_set::out) is det.
+new_directed_entry(FromData, ToData, SharingSet0, SharingSet):- 
+	SharingSet0 = sharing_set(Size0, Map0), 
+	Var = FromData^sc_var, 
+	Selector = FromData^sc_selector, 
+	(
+		map__search(Map0, Var, Selectors0)
+	->
+		(	selector_sharing_set_new_entry(Selector, ToData, 
+				Selectors0, Selectors)
+		-> 
+			map__det_update(Map0, Var, Selectors, Map),
+			Size = Size0 + 1
+		; 
+			Map = Map0, 
+			Size = Size0
+		)
+	;
+		(
+			selector_sharing_set_new_entry(Selector, ToData, 
+				selector_sharing_set_init, 
+				Selectors)
+		-> 
+			map__det_insert(Map0, Var, Selectors, Map), 
+			Size = Size0 + 1
+		;
+			unexpected(this_file, "new_directed_entry: Impossible option.")
+		)
+	), 
+	SharingSet = sharing_set(Size, Map). 
+
+
+to_sharing_pair_list(SharingSet0) = SharingPairs :- 
+    SharingSet = without_doubles(SharingSet0),
+    SharingSet = sharing_set(_, SharingMap),
+    map__foldl(
+        pred(ProgVar::in, SelSharingSet::in, P0::in, P::out) is det :-
+            ( 
+                SelSharingSet = selector_sharing_set(_, SelectorMap),
+                map__foldl(
+                    pred(Selector::in, Dataset::in, Pa::in, Pb::out) is det :-
+                    ( 
+                        Dataset = datastructures(_, Datastructs), 
+                        set__fold(
+                            pred(Datastruct::in, Px::in, Py::out) is det :- 
+                            (
+                                SharingPair = Datastruct -
+                                        datastruct.init(ProgVar, Selector),
+                                Py = [ SharingPair | Px ]
+                            ),
+                            Datastructs,
+                            Pa, Pb)
+                    ),
+                    SelectorMap, 
+                    P0, 
+                    P
+                    )
+            ), 
+            SharingMap, 
+            [], 
+            SharingPairs).
+
+
+:- func without_doubles(sharing_set) = sharing_set. 
+
+without_doubles(SharingSet0) = SharingSet :- 
+	SharingSet0 = sharing_set(_, Map0), 
+	map__foldl(
+		pred(ProgVar::in, SelSharingSet::in, SS0::in, SS::out) is det :-
+			( SelSharingSet = selector_sharing_set(_, SelMap), 
+			  map__foldl(
+			  	pred(Selector::in, DataSet::in, SSa::in, SSb::out) is det :- 
+					(
+					DataSet = datastructures(_, DS),
+					set__fold(
+						pred(Datastruct::in, 
+							SSx::in, SSy::out) 
+								is det :- 
+							( (
+						        directed_entry_is_member(
+                                    datastruct.init(ProgVar, Selector),
+                                    Datastruct, SSx)
+                            ->
+                                SSy = SSx
+                            ; 
+                                new_directed_entry(Datastruct, 
+                                    datastruct.init(ProgVar, Selector),
+                                    SSx, SSy)
+							) ), 
+						 	DS, 
+							SSa, 
+							SSb
+						)
+					),
+                SelMap,
+				SS0, 
+				SS
+			  )), 
+		Map0, 
+		sharing_set_init, 
+		SharingSet).
+
+:- pred directed_entry_is_member(datastruct::in, datastruct::in, 
+    sharing_set::in) is semidet.
+
+directed_entry_is_member(FromData, ToData, SharingSet) :- 
+    SharingSet = sharing_set(_, Map), 
+    Var = FromData^sc_var, 
+    Selector = FromData^sc_selector, 
+    map__search(Map, Var, SelSharingSet), 
+    SelSharingSet = selector_sharing_set(_, SelectorMap), 
+    map__search(SelectorMap, Selector, Dataset),
+    Dataset = datastructures(_, Datastructures),
+    set__member(ToData, Datastructures).
+
+        
+%-----------------------------------------------------------------------------%
+% selector_sharing_set predicates/functions.
+%-----------------------------------------------------------------------------%
+:- func selector_sharing_set_init = selector_sharing_set.
+:- pred selector_sharing_set_is_empty(selector_sharing_set::in) is semidet.
+:- func selector_sharing_set_size(selector_sharing_set) = int. 
+
+:- pred selector_sharing_set_project(projection_type::in, list(prog_var)::in, 
+	selector_sharing_set::in, selector_sharing_set::out) is det.
+:- pred selector_sharing_set_rename(map(prog_var, prog_var)::in, 
+	maybe(tsubst)::in, selector_sharing_set::in, 
+	selector_sharing_set::out) is det.
+
+	% selector_sharing_set_new_entry(Selector, Datastruct, SS0, SS):
+	% Adds Datastruct into SS0 using Selector as a key. Fails if that 
+	% Datastructs is already present with that selector. 
+:- pred selector_sharing_set_new_entry(selector::in, datastruct::in, 
+	selector_sharing_set::in, selector_sharing_set::out) is semidet.
+
+:- func selector_sharing_set_altclos(module_info, proc_info, mer_type, 
+    selector_sharing_set, selector_sharing_set) = 
+    list(structure_sharing_pair). 
+
+:- pred selector_sharing_set_extend_datastruct(module_info::in, 
+    mer_type::in, selector::in, selector_sharing_set::in, 
+    list(datastruct)::out) is det.
+
+selector_sharing_set_init = selector_sharing_set(0, map__init).
+selector_sharing_set_is_empty(selector_sharing_set(0, _Map)).
+selector_sharing_set_size(selector_sharing_set(Size,_)) = Size.
+
+selector_sharing_set_project(ProjectionType, Vars, SelSharingSet0, 
+    SelSharingSet):- 
+	SelSharingSet0 = selector_sharing_set(_, Map0), 
+	map__foldl(
+		pred(Sel0::in, DataSet0::in, SS0::in, SS::out) is det:-
+		(
+			data_set_project(ProjectionType, Vars, DataSet0, DataSet),
+		    (
+				data_set_is_empty(DataSet)
+			->
+				SS0 = SS
+			;
+				SS0 = selector_sharing_set(Size0, M0),
+				map__det_insert(M0, Sel0, DataSet, M),
+				Size = Size0 + data_set_size(DataSet),
+				SS = selector_sharing_set(Size, M)
+			)
+		), 
+		Map0, 
+		selector_sharing_set_init, 
+		SelSharingSet).
+
+selector_sharing_set_rename(Dict, MaybeSubst, SelSharingSet0, SelSharingSet):- 
+	SelSharingSet0 = selector_sharing_set(Size, Map0),
+	map__foldl(
+		pred(Sel0::in, DataSet0::in, M0::in, M::out) is det :-
+		(
+			ctgc.selector.rename_types(MaybeSubst, Sel0, Sel), 
+			data_set_rename(Dict, MaybeSubst, DataSet0, DataSet), 
+			map__det_insert(M0, Sel, DataSet, M)
+		), 
+		Map0,
+		map__init, 
+		Map),
+	SelSharingSet = selector_sharing_set(Size, Map). 
+
+selector_sharing_set_new_entry(Selector, Datastruct, SelSharingSet0, 
+		SelSharingSet) :- 
+	SelSharingSet0 = selector_sharing_set(Size0, Map0), 
+	(
+		map__search(Map0, Selector, DataSet0)
+	->
+		data_set_new_entry(Datastruct, DataSet0, DataSet), 
+		Size = Size0 + 1,
+		map__det_update(Map0, Selector, DataSet, Map)
+	;
+		data_set_new_entry(Datastruct, data_set_init, DataSet), 
+		Size = Size0 + 1, 
+		map__det_insert(Map0, Selector, DataSet, Map)
+	), 
+	SelSharingSet = selector_sharing_set(Size, Map). 
+
+selector_sharing_set_altclos(ModuleInfo, ProcInfo, Type, NewSelSet, 
+    OldSelSet) = NewSharingPairs :- 
+
+    NewSelSet = selector_sharing_set(_, NewMap), 
+    OldSelSet = selector_sharing_set(_, OldMap), 
+
+    % get the selectors
+    map__keys(NewMap, NewSelectors), 
+    map__keys(OldMap, OldSelectors),
+
+    % for each selector in NewSelectors, verify each selector in OldSelector,
+    % if either one is less or equal to the other, then generate the structure
+    % sharing pair as appropriate. 
+    list__foldl(
+        pred(NewSel::in, L0::in, L::out) is det :- 
+            ( 
+                map__lookup(NewMap, NewSel, NewSelDataSet),
+                list__foldl(
+                    pred(OldSel::in, La::in, Lb::out) is det :-
+                        (
+                            map__lookup(OldMap, OldSel, OldSelDataSet), 
+                            NewPairs = 
+                                basic_closure(ModuleInfo, ProcInfo, Type, 
+                                NewSelDataSet, OldSelDataSet, 
+                                NewSel, OldSel), 
+                            list__append(NewPairs, La, Lb)
+                        ),
+                    OldSelectors, L0, L)
+            ),
+            NewSelectors,
+            [], 
+            NewSharingPairs).
+          
+:- func basic_closure(module_info, proc_info, mer_type, 
+    data_set, data_set, selector, selector) = list(structure_sharing_pair). 
+
+basic_closure(ModuleInfo, _ProcInfo, Type, NewDataSet, OldDataSet, 
+    NewSel, OldSel) = SharingPairs :- 
+    % three cases: 
+    % 1. NewSel <= OldSel then generate sharing pairs.
+    % 2. OldSel <= NewSel then generate sharing pairs.
+    % 3. NewSel and OldSet not comparable then no new sharing pairs. 
+    
+    (
+        % NewSel <= OldSel ie, \exists Extension: OldSel.Extension = NewSel.
+        selector.subsumed_by(ModuleInfo, NewSel, OldSel, Type, Extension)
+    -> 
+        data_set_termshift(OldDataSet, Extension, TermShiftedOldDataSet), 
+        SharingPairs = data_set_directed_closure(TermShiftedOldDataSet, 
+            NewDataSet)
+
+    ;
+        % OldSel <= NewSel ie, \exists Extension: NewSel.Extension = OldSel.
+        selector.subsumed_by(ModuleInfo, OldSel, NewSel, Type, Extension)
+    -> 
+        data_set_termshift(NewDataSet, Extension, TermShiftedNewDataSet),
+        SharingPairs = data_set_directed_closure(TermShiftedNewDataSet, 
+            OldDataSet)
+    ;
+        % uncomparable
+        SharingPairs = []
+    ).
+
+selector_sharing_set_extend_datastruct(ModuleInfo, VarType, Selector, 
+    SelectorSharingSet, Datastructs) :-
+    SelectorSharingSet = selector_sharing_set(_, SelectorMap),
+    map__foldl(
+        pred(Sel::in, Dataset0::in, D0::in, D::out) is det :- 
+        (
+			% if Sel is more general than Selector, i.e.
+			% Selector = Sel.Extension, apply this extension
+			% to all the datastructs associated with Sel, and add them
+            % to the set of datastructs collected. 
+            (
+                selector.subsumed_by(ModuleInfo, Selector, 
+                    Sel, VarType, Extension)
+            -> 
+                data_set_termshift(Dataset0, Extension, Dataset), 
+                Dataset = datastructures(_, Data),
+                list__append(set__to_sorted_list(Data), D0, D)
+            ;
+                D = D0
+            )
+       ),
+       SelectorMap, 
+       [],
+       Datastructs).
+                
+
+%-----------------------------------------------------------------------------%
+% data_set predicates/functions.
+%-----------------------------------------------------------------------------%
+
+:- func data_set_init = data_set.
+:- pred data_set_is_empty(data_set::in) is semidet.
+:- func data_set_size(data_set) = int.
+
+:- pred data_set_project(projection_type::in, list(prog_var)::in, data_set::in, 
+	data_set::out) is det.
+:- pred data_set_rename(map(prog_var, prog_var)::in, 
+	maybe(tsubst)::in, 
+	data_set::in, data_set::out) is det.
+:- pred data_set_termshift(data_set::in, selector::in, data_set::out) is det.
+
+:- pred data_set_new_entry(datastruct::in, data_set::in, data_set::out) 
+		is semidet.
+
+:- func data_set_directed_closure(data_set, data_set) = 
+    list(structure_sharing_pair).
+
+data_set_init = datastructures(0, set__init).
+data_set_is_empty(datastructures(0, _Set)).
+data_set_size(datastructures(Size, _)) = Size.
+data_set_project(ProjectionType, Vars, DataSet0, DataSet) :- 
+	data_set_filter(
+		pred(Data::in) is semidet :- 
+		(
+			Var = Data^sc_var,
+            ( 
+                ProjectionType = inproject, 
+			    list__member(Var, Vars)
+            ; 
+                ProjectionType = outproject, 
+			    \+ list__member(Var, Vars)
+            )
+		),
+		DataSet0, 
+		DataSet). 
+
+data_set_rename(Dict, MaybeSubst, DataSet0, DataSet) :- 
+	data_set_map(ctgc.datastruct.rename(Dict, MaybeSubst), 
+			DataSet0, DataSet).
+
+data_set_termshift(DataSet0, Selector, DataSet) :- 
+    DataSet0 = datastructures(Size, Set0), 
+    Set = set__map(datastruct.termshift(Selector), Set0),
+    DataSet = datastructures(Size, Set).
+
+data_set_new_entry(Datastruct,  DataSet0, DataSet) :- 
+	DataSet0 = datastructures(Size0, Datastructs0), 
+	\+ set__member(Datastruct, Datastructs0),
+	set__insert(Datastructs0, Datastruct, Datastructs), 
+	Size = Size0 + 1, 
+	DataSet = datastructures(Size, Datastructs).
+
+data_set_directed_closure(FromData, ToData) = SharingPairs :- 
+    FromData = datastructures(_, DataSet1), 
+    ToData = datastructures(_, DataSet2), 
+    set_cross_product(DataSet1, DataSet2, SetOfPairs), 
+    set__to_sorted_list(SetOfPairs, SharingPairs).
+
+:- pred set_cross_product(set(T1)::in, set(T2)::in, 
+				set(pair(T1, T2))::out) is det.
+
+set_cross_product(Set0, Set1, CrossProduct):-
+	solutions_set(
+		pred(Pair::out) is nondet :- 
+		(
+			set__member(Elem0, Set0), 
+			set__member(Elem1, Set1), 
+			Pair = Elem0 - Elem1
+		), 
+		CrossProduct).
+
+:- pred data_set_filter(pred(datastruct), data_set, data_set).
+:- mode data_set_filter(pred(in) is semidet, in, out) is det.
+data_set_filter(Pred, DataSet0, DataSet):- 
+	DataSet0 = datastructures(_, Datastructs0), 
+	Datastructs = set__filter(Pred, Datastructs0),
+	DataSet = datastructures(set__count(Datastructs), Datastructs).
+%
+:- pred data_set_map(pred(datastruct, datastruct), data_set, data_set).
+:- mode data_set_map(pred(in, out) is det, in, out) is det.
+data_set_map(Pred, DataSet0, DataSet):-
+	DataSet0 = datastructures(_Size, Datastructs0), 
+	Datastructs = set__map(tofunc(Pred), Datastructs0),
+	DataSet = datastructures(set__count(Datastructs), Datastructs). 
+
+:- func tofunc(pred(X,Y), X) = Y.
+:- mode tofunc(pred(in,out) is det, in) = out is det.
+
+tofunc(Pred, X) = Y :- Pred(X, Y).
+
+%-----------------------------------------------------------------------------%
+
+:- func this_file = string.
+
+this_file = "structure_sharing.domain.m".
+%-----------------------------------------------------------------------------%
+:- end_module transform_hlds.ctgc.structure_sharing.domain.
Index: structure_sharing.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/structure_sharing.m,v
retrieving revision 1.1
diff -u -d -r1.1 structure_sharing.m
--- structure_sharing.m	16 Dec 2005 12:17:55 -0000	1.1
+++ structure_sharing.m	16 Jan 2006 10:38:51 -0000
@@ -17,6 +17,7 @@
 :- interface.
 
 :- include_module analysis. 
+:- include_module domain.
 
 :- import_module hlds.
 

