/*  LIB.PL  */


:- op( 253, fx, [module, public, dynamic, load_with, needs]).
/*  See below for purpose of these.  */


/*
This just makes sure that the directives succeed when called. Under
Poplog v13, failing directives cause an error message to be printed,
which I don't want. In Poplog, when compiling Prolog, this has to come
before the first use of any of these directives.
*/
;;; module X.
;;; public X.
;;; dynamic X.
;;; load_with X.
;;; needs X.
;;; endmodule.

/*
:- module lib.


:- public lib/1,
          lib/2,
          lib_clearloads/0,
          add_linking_clause/3,
          del_linking_clause/3,
          load/1,
          load_scan/1,
          load_clearscan/0,
          load_writescan/1,
          load_readscan/1.
*/


/*
SPECIFICATION
-------------

This module exports lib/1 and lib/2, for loading library files, and two
predicates for adding and deleting such things as portray or
term_expansion clauses. For more advanced library management, loading
the files necessary to implement given predicates, it exports load/1. It
also defines some operators (see start of module), partly for
compatibility with other module systems, and partly for use by load. See
the documentation file MODULES. for a description of their purpose.


PUBLIC lib( File+, Pred+ ):
---------------------------

File must be an atom naming a Prolog file. If this name doesn't include
a directory, lib will search for the file in the list of library
directories defined by library_directories/1, below; if the name does
include a directory, lib will look for the file there. If the name has
no extension, it will be assumed to be ".PL".

If lib finds the file, it will generate the full file name, including
disk, directory, extension, and version, and load it by calling
Pred(File). However, it will not load files it has already loaded.

The Pred argument is useful when loading files whose contents must be
translated, such as SDO rules (see SDO.PL).


PUBLIC lib( FileList+, Pred+ ):
-------------------------------

Loads each file in the list. If the file takes the form Name-P, then
P will be used as the loading predicate instead of Pred. Thus,
    lib( [ 'fred.sdo', fred-reconsult, 'bert.sdo' ], sdo_reconsult )
will load the first and third files with sdo_reconsult, but the
second one with reconsult.


PUBLIC lib( (File-Pred)+ ):
PUBLIC lib( (FileList-Pred)+ ):
-------------------------------

As the two argument form, but allows Pred to be specified as part of the
first argument.


PUBLIC lib( X+ ):
-----------------

Equivalent to lib(X,reconsult).


NOTE: this module relies on modules 'bug' and 'files'. Hence these, and
'lib' itself, are pre-loaded, and 'lib' will not re-load them.


PUBLIC lib_clearloads:
----------------------

Unsets the "file loaded" flags for all files loaded by lib (except for
lib itself, bug, and files).


PUBLIC lib_clearload( File ):
-----------------------------

Unsets the "file loaded" flags for File.


PUBLIC add_linking_clause( Link+, Pred+, Arity+ ):
PUBLIC del_linking_clause( Link+, Pred+, Arity+ ):
--------------------------------------------------

add_linking_clause ensures that there is a clause
    Pred( <ARGS> ) :- Link( <ARGS> )
in your database. Here, <ARGS> denotes a sequence of Arity variables.

del_linking_clause ensures that there is _no_ such clause.

For example,
    ?- add_linking_clause( term_expansion, expand, 2 ).
will ensure that the clause
    term_expansion(X,Y) :- expand(X,Y)
has been asserted.

    ?- del_linking_clause( portray, show, 1 ).
will ensure that there are no clauses for
    portray(X) :- show(X).

The use of these is that you can add new clauses for such predicates as
term_expansion and portray. It isn't enough for a module to contain
clauses like
    portray( Record ) :-
        is_record(Record), !, output_record(Record).
because when these are reconsulted, any other clauses for portray will
be wiped out. As Richard O'Keefe suggests, you can instead write
    my_portray( Record ) :-
        is_record(Record), !, output_record(Record).
    ... any other clauses for my_portray ...
and then (if there isn't one already), assert the "linking clause"
    portray( Thing ) :- my_portray( Thing ).

add/del_linking_clause automate the business of constructing and
asserting these link definitions. See Chapter 9 of "The Craft of Prolog"
for discussion.


Notes on use.
-------------

I find two reasons for wanting lib.

Firstly, my files do not all live in the same directory. I might have
one directory for trees, arrays and other structures; one for games to
be used by the students; one for sample databases; and so on. It is
convenient to be able to load files without worrying about where they
live. Full VMS filenames are not in any case very elegant things to
type. 'lib' takes care of this by having an internal list of
directories, and running along each directory in turn until it finds the
library file it has been asked to load. This requires testing for file
existence, and so lib depends on the predicates in FILES.PL.

Secondly, I like to avoid the ``steering file'' approach to programs.
For many programs, the first file to be loaded is a steering file that
looks like this
    :- consult( 'useful.pl' ).
    :- consult( 'sets.pl' ).
    :- consult( 'lists.pl' ).
    :- consult( 'datetime.pl' ).
    ...
Such an approach is unmodular. If module A needs predicates from
module B, this is A's business and no-one else's. The loading
command for B should be placed inside A. A reader who is concerned
with how A works can then see that it depends on B: no-one else
needs to know. (Having said this, you will see that MASTER.PL
actually is a steering file. This should make things easier for
you, since it shows you immediately all the files you'll need.)

The trouble with doing consult(B) inside A is that if C also needs B,
then the code for B will get loaded twice. If Prolog were a purely
logical language this would not matter, since the logical reading is
unimpaired by duplicating clauses. But of course Prolog isn't, and
loading a predicate twice may have very odd effects. If A and C were
both to reconsult(B), only one copy of the code would be loaded, (Well,
this should be true: under Poplog, you still get two copies. Don't ask
why.) but time would still be wasted in doing the extra reconsult.

lib has an anti-duplication flag which avoids this. Before lib loads
a file, it checks a flag to see whether the file has already been
loaded, and if so, does nothing.

The anti-duplication flag can come in useful when teaching students. If
you set an exercise, you may want the student to load some supplementary
predicates to use with it. It is nice not to worry about whether they
have already been loaded by the Tutor. By telling students to use lib,
you can ignore this worry; and you also save the student from having to
type directory names and file extensions.

This version of lib is adapted from Peter Ross' code in ``Advanced
Prolog''. There is a similar predicate in LIB and LIB2 from the Dec-10
library.


More advanced predicates
------------------------


PUBLIC load( Thing+ ):
PUBLIC load( ThingList+ ):
--------------------------

Here, Thing (or each element of ThingList) is either
    file(File)  -   File must be a filename suitable for 'lib'.
    Pred        -   assumed if an atom.
    Pred/Arity  -   Pred must be an atom.

'load' uses the public, needs, and load_with directives in your library
files to work out which other files are necessary to support the
predicates and files you have asked it to load, and then calls 'lib' to
load each one. It works as follows
1) For each Pred/Arity in the list, replace it by the name of its
   exporting file. Report a bug if more than one file exports the same
   predicate and arity.
2) For each Pred in the list, replace by the name of a file that exports
   that predicate with any arity. Report a bug if the same predicate
   (regardless of arity) is exported by more than one file.
3) Eliminate duplicate filenames and files that have already been loaded
   by lib.
4) Repeat the same process on the needs-lists of each of these files to
   build up the complete list of child files.
5) Perform a topological sort on the resulting list to sort it into
   ascending order. This is necessary because some files may rely on
   operators declared by earlier files. If there is a dependency loop,
   report it and leave the rest of the list unsorted.

For load to work, you must first have called load_scan as described
below.


PUBLIC load_scan( FileList ):
-----------------------------

Scans each file in the list and stores the information in its public,
needs, and load_with directives. These are operators declared at the
start of this module, and have the following syntax:
    public Pred/Arity, Pred/Arity, ...
    needs Pred/Arity, Pred/Arity, ...
    load_with Pred.

From these, load_scan can work out which predicate (second argument to
'lib') is needed to load each file, and which files are called by the
predicates defined in other files.

Note: already-loaded files are not included in the needs information.
If you are building up scans to be saved by load_writescan, you
should therefore call lib_clearloads first.


PUBLIC load_clearscan:
----------------------

Removes the information gathered by load_scan.


PUBLIC lib_writescan( File+ ):
------------------------------

Write the result of a load_scan to File.


PUBLIC lib_readscan( File+ ):
-----------------------------

Read the result of a load_scan to File, overwriting any previous scan
information.


The Tutor does not use these more advanced predicates, and they
are still experimental. You may or may not find them useful.
*/


/*
IMPLEMENTATION
--------------

See under specific sections below.
*/




/*
Dynamics.
*/

/*
:- dynamic
   '$already_read' / 1,
   '$export_from' / 2,
   '$file_is_loaded' / 1,
   '$needs_files'/2,
   '$needs_list'/2,
   '$load_with'/2.
 */

/*
Define 'pop_compile' for loading files of Pop-11 code. Remove this if
not using Poplog.
*/
pop_compile(F) :-
    prolog_eval(compile(><('logic$src:',><(F,'')))).

/*
:- needs
   bug / 2,
   find_file / 5,
   open_and_reconsult / 2,
   open_input / 2,
   open_output / 2.
*/

:- reconsult( 'logic$src:bug.pl' ).
:- reconsult( 'logic$src:files.pl' ).


/*
lib.
----

lib uses find_file from module FILES to search for its file amongst a
list of directories. If the file is found, it calls load_library_file.
This checks whether there's already an assertion stating that the file
has been loaded: if not, load_library_file reconsults the file.

The library directories are defined by library_directories below, in the
form used by find_file/5. The list must contain at least one element
(which will usually be either the notation for the current directory, []
at Oxford, or some standard library directory, logic$src etc at Oxford).

Note: you must change the two reconsults above, since they have to have
directories wired in.
*/


library_directories( [ 'logic$src:',
                       '[]'
                     ]
                   ).



/*  find_library_file( File+, FullName?, Status? ):
        Look for library file File in the directories above. If found,
        Status = ok, FullName = its full name (complete with version
        number on VMS); otherwise FullName is undefined and Status
        indicates the error.
*/
find_library_file( File, FullName, Status ) :-
    library_directories( LibraryDirectories ),
    find_file( File, LibraryDirectories, '.pl', FullName, Status ).


lib( [], _ ) :- !.

lib( [File|Files], Pred ) :-
    !,
    lib( File, Pred ),
    lib( Files, Pred ).

lib( File-Pred, _ ) :-
    !,
    lib( File, Pred ).
    /*  This one ensures that File-Pred elements in lists over-ride the
        outer Pred.
    */

lib( File, ReconsultPred ) :-
    find_library_file( File, FullName, Status ),
    (
        Status \= ok
    ->
        bug( 'lib: file not found', Status )
    ;
        load_library_file( File, FullName, ReconsultPred )
    ).


lib( X-Pred ) :-
    !,
    lib( X, Pred ).

lib( File ) :-
    lib( File, reconsult ).


lib_clearloads :-
    retractall( '$file_is_loaded'(_) ),
    assert_loaded( bug ),
    assert_loaded( files ),
    assert_loaded( lib ).


lib_clearload( File ) :-
    retractall( '$file_is_loaded'(File) ),
    assert_loaded( bug ),
    assert_loaded( files ),
    assert_loaded( lib ).


assert_loaded( File ) :-
    not( '$file_is_loaded'(File) ),
    asserta( '$file_is_loaded'( File ) ).


:- lib_clearloads.
/*  Calling this now will ensure that bug, files, and lib are marked as
    loaded.
*/


/*  load_library_file( File+, FullName+, ReconsultPred+ ):
        If File not already loaded, try to do so, and if successful,
        mark it as loaded via '$file_is_loaded'(File). We record
        the short (user-supplied) filenames rather than the file's
        full name; this makes it easier for 'load' to check whether
        its files have been loaded using the same assertions.
*/
load_library_file( File, FullName, ReconsultPred ) :-
    telling( COS ),
    tell( user ),
    seeing( CIS ),
    (
        '$file_is_loaded'( File )
    ->
        write( File ), write( ' already loaded.' ), nl
    ;
        open_library_file( FullName, ReconsultPred, Status ),
        (
            Status \= ok
        ->
            bug( 'lib: file not readable', Status )
        ;
            read_library_file( FullName, ReconsultPred ),
            see( FullName ), seen, see( CIS ),
            /* ... close file.  */
            asserta( '$file_is_loaded'( File ) ),
            write( 'File ' ), write( File ), write( ' reconsulted.' ), nl
        )
    ),
    tell( COS ).


open_library_file( File, ReconsultPred, Status ) :-
    open_input( File, Status ),
    seeing( CIS ), see( File ), seen, see( CIS ).
    /*  Open the file to find out whether it can be opened, then close
        again ready for ReconsultPred.
    */


read_library_file( File, ReconsultPred ) :-
    Goal =.. [ ReconsultPred, File ],
    call( Goal ).


/*
Linking clauses.
----------------

The definitions of add/del_linking_clause are taken from "The Craft of
Prolog" by Richard O'Keefe.
*/


add_linking_clause( Link, Pred, Arity ) :-
    '$make_goal'( Link, Arity, Head ),
    '$make_goal'( Pred, Arity, Body ),
    Head =.. [ _ | Args ],
    Body =.. [ _ | Args ],
    /*  to ensure that they share their variables  */
    (
        clause( Head, Body )
    ->
        true
    ;
        assert(( Head:-Body ))
    ).


del_linking_clause( Link, Pred, Arity ) :-
    '$make_goal'( Link, Arity, Head ),
    '$make_goal'( Pred, Arity, Body ),
    (
        retract(( Head:-Body )),
        fail
    ;
        true
    ).


'$make_goal'( Pred, Arity, Head ) :-
    functor( Head, Pred, Arity ).


/*
Scanning the files.
-------------------

Meaning of assertions:

    '$already_read'(F)      - F has been scanned.
    '$export_from'(F,P/A)   - F exports P/A.
    '$load_with'(F,P)       - F should be loaded by calling P(F).
    '$needs_list'(F,L)      - F's needs-list is L.
    '$needs_files'(F,Files) - F needs Files.

The final two will not exist at the same time.

Scanning operates in two phases. The first, tabulate_files_transports,
reads the exports and needs-lists. The second, convert_needs_lists,
converts the needs-lists as described above under "load", by calling
needs_list_to_needs_files. This can't be done until the exports are all
recorded, since we have to go from predicates to their home files.
*/


load_scan( Files ) :-
    tabulate_files_transports( Files ),
    convert_needs_lists.


load_clearscan :-
    retractall( '$already_read'(_) ),
    retractall( '$export_from'(_,_) ),
    retractall( '$load_with'(_,_) ),
    retractall( '$needs_list'(_,_) ),
    retractall( '$needs_files'(_,_) ).


load_writescan( F ) :-
    open_output( F, Status ),
    (
        Status = ok
    ->
        '$save_facts'( '$export_from'(_,_) ),
        '$save_facts'( '$load_with'(_,_) ),
        '$save_facts'( '$needs_files'(_,_) )
    ;
        bug( 'load_writescan: file not writeable', [F] )
    ).


load_readscan( F ) :-
    open_and_reconsult( F, Status ),
    (
        Status = ok
    ->
        true
    ;
        bug( 'load_readscan: file not readable', [F] )
    ).


/*  '$save_facts'( Head ):
        Head must be a structure whose arguments are all uninstantiated,
        and represents the head of a procedure. Save all clauses to COS,
        one per line, in reconsultable form. Assumes they are all
        unconditional facts.
*/
'$save_facts'( Head ) :-
    call( Head ),
    writeq( Head ), write('.'), nl,
    fail.

'$save_facts'( _ ).


/*
Reading public, load_with, and needs directives.
------------------------------------------------

This is the guts of load_scan.
*/


/*  tabulate_files_transports( Files+ ):
        Read and record the directives for a list of files.
*/
tabulate_files_transports( [] ) :- !.

tabulate_files_transports( [File|Files] ) :-
    tabulate_file_transports( File ),
    tabulate_files_transports( Files ).


/*  tabulate_file_transports( File+ ):
        Read and record the directives for one file.
*/
tabulate_file_transports( File ) :-
    telling( COS ),
    tell( user ), write( 'Scanning exports and imports for ' ), write( File ), nl,
    find_library_file( File, FullName, Status ),
    (
        Status = ok
    ->
        read_file_transports( File, FullName )
    ;
        bug( 'load_scan: file not found', Status )
    ),
    write( 'Finished scanning ' ), write( File ), nl,
    tell( COS ).


/*  read_file_transports( File+, Fullname+ ):
        Read and record the directives for one file, if it has not
        already been scanned.
*/
read_file_transports( ShortName, FullName ) :-
    (
        '$already_read'( ShortName )
    ->
        true
    ;
        open_input( FullName, Status ),
        (
            Status = ok
        ->
            asserta( '$already_read'( ShortName ) ),
            read_file_transports_1( ShortName ),
            seeing( CIS ), see( FullName ), seen, see( CIS )
        ;
            bug( 'load_scan: file not reconsultable', Status )
        )
    ).


read_file_transports_1( File ) :-
    read( X ),
    do_putative_transports( File, X ).


/*  do_putative_transports( File+, X+ ):
        Process term X from File. File is the file's original
        (user-supplied) name, used when creating the assertions.
*/
do_putative_transports( File, end_of_file ) :-
    (
        not( '$needs_list'(File,_) )
    ->
        asserta( '$needs_list'( File, [] ) )
    ;
        true
    ).

do_putative_transports( File, (:-(public(Preds))) ) :-
    !,
    do_exports( File, Preds ),
    read_file_transports_1( File ).

do_putative_transports( File, (:-(load_with(Pred))) ) :-
    !,
    asserta( '$reconsult_with'( File, Pred ) ),
    read_file_transports_1( File ).

do_putative_transports( File, (:-(needs(Things))) ) :-
    !,
    '$comma_list_to_list'( Things, Things_ ),
    asserta( '$needs_list'( File, Things_ ) ),
    read_file_transports_1( File ).

do_putative_transports( File, _ ) :-
    read_file_transports_1( File ).


/*  do_exports( File+, X+ ):
        X+ is either a single P/A structure, or a comma-list (
        part or all of the 'public' directive's argument).
*/
do_exports( File, (E1,E2) ) :-
    !,
    do_exports( File, E1 ),
    do_exports( File, E2 ).

do_exports( File, Pred ) :-
    asserta( '$export_from'(File,Pred) ).


/*  convert_needs_lists:
        Replace all '$needs_list' assertions by equivalent
        '$needs_files' ones.
*/
convert_needs_lists :-
    retract( '$needs_list'( File, Things ) ),
    !,
    needs_list_to_needs_files( Things, [], Files ),
    asserta( '$needs_files'( File, Files ) ),
    convert_needs_lists.

convert_needs_lists.


/*
load.
-----

The method behind load was described in the specification part above. In
terms of predicates, it first calls
    needs_list_to_needs_files( ThingList, [], Files )
to convert the list of things into a list of filenames. The mapping is
    file(File)  -> File
    Pred/Arity  -> the exporting file
    Pred        -> the exporting file

The latter two are obtained from the '$export_from' assertions created by
load_scan. Duplicate filenames are removed; there may be a lot of these,
since several predicates might come from the same file.

It then does
    non_loaded_files_for( Files, Children )
to get, in Children, a list of all the files needed by Files
(technically speaking, the transitive closure of the relation defined by
the needs-lists of Files and their sons). This is done by breadth-first
search. The reason for using breadth-first is that, originally, I
obtained the needs-lists by reading them from the files in the "find
children" stage of search, rather than relying on the results of
load_scan. Doing a depth-first, which is easier, entailed having several
files open simultaneously ( F, and one of the files mentioned in its
needs-list, and one of the files mentioned in that one's needs-list...)
and this caused Poplog to run out of memory. Probably a system bug, but
I had to alter it so that only one file was open at any time. I have
kept the same structure, even though no longer necessary.

Having got these files, non_loaded_files_for then does a topological
sort, trying to order them so that if F1 needs F2, F2 appears earlier in
Children than F1. This may fail if the dependency graph contains a loop:
in that case, non_loaded_files_for gives a warning and leaves the order
of the looped part of the network, and the files above it, unchanged.

None of these algorithms are efficient. To make them so would require
more auxiliary predicates - perhaps the DEC10 graphs module - than I
want to include in a module this basic.
*/


load( Thing ) :-
    Thing \= [], Thing \= [_|_],
    !,
    load( [Thing] ).
    /*  This clause if Thing is not a list.  */

load( ThingList ) :-
    needs_list_to_needs_files( ThingList, [], Files ),
    non_loaded_files_for( Files, Children ),
    lib( Children ).


/*  needs_list_to_needs_files( List+, SoFar+, Files- ):
        The result of converting needs-list List to a list of
        files and appending to SoFar is Files.
*/
needs_list_to_needs_files( [], Files0, Files0 ) :- !.

needs_list_to_needs_files( [X|T], Files0, Files ) :-
    needs_thing_to_needs_file( X, File ),
    add_file( File, Files0, Files1 ),
    needs_list_to_needs_files( T, Files1, Files ).


/*  needs_thing_to_needs_file( Thing+, File- ):
        Thing is a predicate name, P/A, or file(File), as described
        above.
        File is the corresponding file.
*/
needs_thing_to_needs_file( P/A, File ) :-
    !,
    needs_pa_to_needs_file( P, A, File ).

needs_thing_to_needs_file( file(File), File ) :-
    !.

needs_thing_to_needs_file( P, File ) :-
    atom( P ),
    !,
    needs_p_to_needs_file( P, File ).


needs_pa_to_needs_file( P, A, File ) :-
    '$export_from'( File1, P/A ),
    '$export_from'( File2, P/A ),
    File1 \= File2,
    !,
    bug( 'load_scan: predicate exported from more than one file',
         [ P/A-File1, P/A-File2 ]
    ).

needs_pa_to_needs_file( P, A, File ) :-
    '$export_from'( File, P/A ),
    !.

needs_pa_to_needs_file( P, A, _ ) :-
    bug( 'load_scan: predicate not in export list', [P/A] ).


needs_p_to_needs_file( P, File ) :-
    '$export_from'( File1, P/A1 ),
    '$export_from'( File2, P/A2 ),
    File1 \= File2 ,
    !,
    bug( 'load_scan: predicate exported from more than one file',
         [P/A1-File1, P/A2-File2]
    ).

needs_p_to_needs_file( P, File ) :-
    '$export_from'( File, P/A ),
    !.

needs_p_to_needs_file( P, _ ) :-
    bug( 'load_scan: predicate not in export list', [P] ).


/*  add_file( File+, SoFar+, Files- ):
        If File hasn't been loaded by lib, and is not already in SoFar,
        add it.
*/
add_file( File, Files0, [File|Files0] ) :-
    not( '$file_is_loaded'( File ) ),
    not( '$memberchk'(File,Files0) ),
    !.

add_file( File, Files0, Files0 ) :- !.


/*
Finding all the files.
----------------------

This entails a breadth-first search through all the needs-lists,
starting from the files passed as argument to load.
*/


/*  non_loaded_files_for( Files+, Children- ):
        Children are all the non-loaded files needed by Files,
        sorted in ascending order if there are no dependency loops.
*/
non_loaded_files_for( Files, Children ) :-
    '$bfs'( Files, Arcs, Children0 ),
    tsort( Children0, Arcs, Children ).


/*  '$bfs'( Files+, Arcs-, Children- ):
        Children is the list of all files needed by Files. Arcs is the
        needs relation, as a list of pairs (Parent,Child).
*/
'$bfs'( Files, Arcs, Children ) :-
    '$bfs'( Files, [], Arcs, Children ).


/*  '$bfs'( Files+, Visited+, Arcs-, Children- ):
        As above, but Visited is a list of all files whose needs-lists
        have already been examined.
*/
'$bfs'( [], _, [], [] ) :- !.

'$bfs'( [File|Rest], Visited, Arcs, Children ) :-
    '$memberchk'( File, Visited ),
    !,
    '$bfs'( Rest, Visited, Arcs, Children ).

'$bfs'( [File|Rest], Visited, Arcs, Children ) :-
    '$file_is_loaded'( File ),
    !,
    '$bfs'( Rest, Visited, Arcs, Children ).

'$bfs'( [File|Rest], Visited, Arcs1, [File|RestChildren] ) :-
    file_to_needs_files( File, Needs ),
    add_needs( File,Needs, Arcs, Arcs1 ),
    '$unite'( Rest, Needs, New ),
    '$bfs'( New, [File|Visited], Arcs, RestChildren ).


/*  add_needs( File+, Needs+, ArcsSoFar+, Arcs- ):
        Needs is the files needed by File.
        Add this relation to ArcsSoFar giving Arcs.
*/
add_needs( _, [], L, L ) :- !.

add_needs( F, [Need|Needs], L, T ) :-
    add_needs( F, Needs, [(F,Need)|L], T ).


file_to_needs_files( File, Files ) :-
    '$needs_files'( File, Files ),
    !.

file_to_needs_files( File, Files ) :-
    bug( 'load: no needs list for file', [File] ).


/*
Sorting file dependencies.
--------------------------

This uses a topological sort:
    tsort( Nodes+, Arcs+, TotalOrder? ):
TotalOrder is an ordering for the Nodes (a list), consistent with the
partial order given in Arcs. Arcs is a list of pairs (Parent,Child).

If Arcs contains a loop, tsort reports it and leaves the rest of the list
unsorted.

Example:
    ?- tsort( [c,b,a], [(a,b)], X ).
    X = [a,b,c].

The method is based on the fact that any acyclic graph must have at
least one node without children. At any iteration, select this node,
pump it to the output list and discard all related arcs from the graph,
then repeat with the remaining graph.

Credits:
Code posted to comp.lang.prolog in June 1992 by
Carlos Lang, M.Sc.,
Maestria en CC Cognocitivas,
Universidad de Costa Rica.

``Main strategy suggested in an exercise from Aho et al,
"The Design and Complexity of Computer Algorithms".

This code was developed using SWI-Prolog, ported by someone else
to 386.

Disclaimer: we have made no attempt whatsoever to provide an
efficient implementation.''
*/


tsort( [], _, [] ) :- !.

tsort( Nodes, Arcs, [N|R] ) :-
    no_child( N, Nodes, Arcs ),
    !,
    '$delete'( Nodes, N, Nodes1 ),
    '$delete'( Arcs, (_,N), Arcs1 ),
    '$delete'( Arcs1, (N,_), Arcs2 ),
    tsort( Nodes1, Arcs2, R ).

tsort( Nodes, Arcs, Nodes ) :-
    warning( 'load_scan: loop', [ Nodes, Arcs ] ).


/*  no_child( N-, Nodes+, Arcs+ ):
        N (in Nodes) has, according to Arcs, no children.
*/
no_child( N, Nodes, Arcs ) :-
    '$member'( N, Nodes ),
    not( '$memberchk'( (N,_), Arcs ) ).


/*
Auxiliary predicates.
---------------------

The problem with writing the file-dependency analyser is that it needs
several list-handling and other auxiliary predicates. But we don't want
to define stuff that might clash with what the user uses 'load' to load.
Hence give the utilities funny names.
*/


/*  '$member'( Element+, List+ ):
        What's usually called member.
*/
'$member'(X, [X|_]).
'$member'(X, [_|Y]) :-
    '$member'(X, Y).


/*  '$memberchk'( Element+, List+ ):
        Deterministic version of '$member'.
*/
'$memberchk'( X, L ) :-
    '$member'( X, L ),
    !.


/*  '$delete'( List+, Element+, List1- ):
        Deletes all matches of Element from List, producing List1.

        Free variables in Element are not bound after the first
        deletion, so
            delete( L, (_,X), L1 )
        (where X is bound) will delete all pairs (_,X) from L.
*/
'$delete'( [], _, [] ) :- !.

'$delete'( [H1|T], H2, L ) :-
    not(not(H1=H2)),
    !,
    '$delete'( T, H2, L ).

'$delete'( [X|T], H, [X|L] ) :-
    '$delete'( T, H, L ).


/*  '$unite'( L1+, L2+, L- ):
        L is the union of L1 and L2.
*/
'$unite'( [], L, L ).
'$unite'( [H|R], S, [H|T] ) :-
    not( '$memberchk'(H,S) ),
    !,
    '$unite'( R, S, T ).
'$unite'( [H|R], S, T ) :-
    '$unite'( R, S, T ).


/*  Usual append. */
'$append'( [], L, L ).
'$append'( [H|R], S, [H|T] ) :-
    '$append'( R, S, T ).


/*  '$comma_list_to_list'( CommaList+, List- ):
        Converts a "comma list" of the form (a,b,c) into
        a list [a,b,c]. Used when converting needs-lists read
        from file, which are comma-lists.
*/
'$comma_list_to_list'( CommaList, List ) :-
    '$comma_list_to_list'( CommaList, [], List ).


'$comma_list_to_list'( (A,B), SoFar, Result ) :-
    !,
    '$comma_list_to_list'( B, SoFar, L1 ),
    '$comma_list_to_list'( A, L1, Result ).

'$comma_list_to_list'( X, SoFar, [X|SoFar] ).

/*
:- endmodule.
*/
