[m-rev.] for review: detect cycles in typeclass hierarchy

[Ralph Becket]

Mark Brown, Wednesday, 19 January 2005:
> Index: compiler/check_typeclass.m
> +
> +:- pred check_for_cyclic_classes(class_table::in, bool::out, io::di, io::uo)
> +	is det.
> +
> +check_for_cyclic_classes(ClassTable, Errors, !IO) :-
> +	ClassIds = map__keys(ClassTable),
> +	foldl2(find_cycles(ClassTable, []), ClassIds, set.init, _, [], Cycles),

You might want to consider using map__foldl2 to avoid constructing the
list of keys.

> +	(
> +		Cycles = [],
> +		Errors = no
> +	;
> +		Cycles = [_ | _],
> +		Errors = yes,
> +		foldl(report_cyclic_classes(ClassTable), Cycles, !IO)
> +	).
> +
> +:- type class_path == list(class_id).
> +
> +	% find_cycles(ClassTable, Path, ClassId, !Visited, !Cycles)
> +	%
> +	% Perform a depth first traversal of the class hierarchy, starting
> +	% from ClassId.  Path contains a list of nodes joining the current
> +	% node to the root.  When we reach a node that has already been
> +	% visited, check whether there is a cycle in the Path.
> +	%
> +:- pred find_cycles(class_table::in, class_path::in, class_id::in,
> +	set(class_id)::in, set(class_id)::out,
> +	list(class_path)::in, list(class_path)::out) is det.
> +
> +find_cycles(ClassTable, Path, ClassId, !Visited, !Cycles) :-
> +	(
> +		set.member(ClassId, !.Visited)
> +	->
> +		(
> +			find_cycle(ClassId, Path, [ClassId], Cycle)
> +		->
> +			!:Cycles = [Cycle | !.Cycles]
> +		;
> +			true
> +		)
> +	;
> +		svset.insert(ClassId, !Visited),
> +		ClassIds = get_superclass_ids(ClassTable, ClassId),
> +		foldl2(find_cycles(ClassTable, [ClassId | Path]), ClassIds,
> +			!Visited, !Cycles)
> +	).

When there are so few "state" changes, I usually prefer to just number
states explicitly rather than use state variable notation.

Otherwise, that looks fine.

-- Ralph
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------