AM - 30 Jan 2007

This is small example that I worked up showing one of the more unusual operations in [TclRAL], transitive
closure. This is useful for dealing with hierarchical or graph structured data. In this small example, we
deal with file include dependencies in "C" source.
----
 # One common activity in building software is determining the include
 # dependencies of files. Because one file can include another which can itself
 # include other files, in general the dependencies form a graph. So one
 # question that often needs to be answered is for a given file, what is the set
 # of files that needs to be checked in order to determine if the given file is
 # out of date with respect to its dependencies.
 #
 # This example shows a method of computing the dependencies of a "C" file using
 # TclRAL. The strategy is to examine each file to determine just which other
 # files it is dependent upon and add these binary dependencies into a relvar.
 # Then computing the transitive close of the relation value will give us the
 # list of dependencies.

 package require ral
 namespace import ::ral::*

 # We need a relvar to hold the dependency information. Each tuple of the
 # relvar value represents an edge in an implied graph of dependencies.  The
 # edge is denoted by the file names showing the "includes" dependency.  N.B.
 # that both attributes are used to form the single identifier of the relation.
 # Also, "relation tclose" insists that the relation be binary (i.e. have only
 # two attributes, which can always be achieved by projection, if necessary).

 relvar create FileDep {
     Relation
     {FileName string DepFile string}
     {{FileName DepFile}}
 }

 # Now we must populate the relvar. This proc is overly simplistic for
 # "real world" use, but serves as a simple example. In practice we would
 # probably need to worry about include paths, system includes, etc. etc.
 # For this example, we will scan every line of the file looking for
 # "# include" constructs.
 package require fileutil
 proc scanFile {filename} {
     # Creating a relvar, creates an ordinary Tcl variable by the same name.
     global FileDep
     fileutil::foreachLine line $filename {
        if {[regexp {#include\s+[<"](.*)[>"]} $line match inclFile]} {
            # The "relvar insert" command throws an error when attempting to
            # insert a duplicate. We catch this and go on since a duplicate
            # here implies we are revisiting some previous dependency.
            catch {relvar insert FileDep [list\
                    FileName [file tail $filename]\
                    DepFile $inclFile]} result
            # Look to see if the file exists in the current directory and that
            # we have not already scanned it. If all that is true, then we
            # recursively look at what files it includes.  We can tell if we
            # have scanned the file by determining if there are any tuples in
            # the "FileDep" relvar that have the FileName attribute set to the
            # name of file that is included.
            if {[file exists $inclFile] &&
                    [relation isempty [relation restrictwith $FileDep\
                        {$FileName eq $inclFile}]]} {
                scanFile $inclFile
            }
        }
     }
 }

 # Okay, pull a file name off the command line and scan it
 set f [lindex $argv 0]
 cd [file dirname $f]
 set f [file tail $f]
 scanFile $f

 # The dependency graph has edges described by the tuples of the relvar.
 puts [relformat $FileDep "File Dependencies"]

 # The transitive closure algorithm, which came from Aho, Hopcroft and Ullman,
 # has memory requirements that are O(N^2) and computation times O(N^3) where
 # N is the number of nodes in the implied dependency graph. So large graphs
 # can take some time. Here we time it just for fun.
 puts [time {set closure [relation tclose $FileDep]} 1]

 # The transitive close contains a tuple for every pair of file names where
 # there is some path from the file to its included file. Thus if a --> b and
 # b --> c and c --> d, then the transitive closure will contain a tuple for
 # a --> d (among others). This implies the original relation value is a subset
 # of the transitive closure.
 puts [relformat $closure "Transitive Closure"]

 # So a list of the ultimate dependencies of the file is a simple expression
 # finding those tuples where the FileName attribute matches, projecting out
 # the DepFile attribute and converting the result into a Tcl list.
 set depList [relation list [relation project\
     [relation restrictwith $closure {$FileName eq $f}] DepFile]]

 # We could choose to put this out in "make" syntax, but a simple listing
 # will do.
 puts "$f depends upon:"
 foreach depFile [lsort $depList] {
     puts "\t$depFile"
 }
----
So if we run this on one of the source files to TclRAL, ral.c, we get:
----
 +=====================+=====================+
 |FileName             |DepFile              |
 |string               |string               |
 +=====================+=====================+
 |ral.c                |stdio.h              |
 |ral.c                |string.h             |
 |ral.c                |tcl.h                |
 |ral.c                |ral_tuplecmd.h       |
 |ral_tuplecmd.h       |tcl.h                |
 |ral_tuplecmd.h       |ral_tupleobj.h       |
 |ral_tupleobj.h       |tcl.h                |
 |ral_tupleobj.h       |ral_utils.h          |
 |ral_utils.h          |tcl.h                |
 |ral_tupleobj.h       |ral_tupleheading.h   |
 |ral_tupleheading.h   |ral_attribute.h      |
 |ral_attribute.h      |tcl.h                |
 |ral_attribute.h      |ral_utils.h          |
 |ral_tupleheading.h   |ral_joinmap.h        |
 |ral_joinmap.h        |ral_vector.h         |
 |ral_vector.h         |stdio.h              |
 |ral_tupleheading.h   |ral_vector.h         |
 |ral_tupleheading.h   |stdio.h              |
 |ral_tupleobj.h       |ral_tuple.h          |
 |ral_tuple.h          |tcl.h                |
 |ral_tuple.h          |ral_utils.h          |
 |ral_tuple.h          |ral_attribute.h      |
 |ral_tuple.h          |ral_tupleheading.h   |
 |ral_tuple.h          |stdio.h              |
 |ral_tupleobj.h       |ral_vector.h         |
 |ral.c                |ral_relationcmd.h    |
 |ral_relationcmd.h    |tcl.h                |
 |ral.c                |ral_relationobj.h    |
 |ral_relationobj.h    |tcl.h                |
 |ral_relationobj.h    |ral_utils.h          |
 |ral_relationobj.h    |ral_relationheading.h|
 |ral_relationheading.h|ral_utils.h          |
 |ral_relationheading.h|ral_tupleheading.h   |
 |ral_relationheading.h|ral_vector.h         |
 |ral_relationheading.h|ral_joinmap.h        |
 |ral_relationheading.h|stdio.h              |
 |ral_relationobj.h    |ral_relation.h       |
 |ral_relation.h       |ral_utils.h          |
 |ral_relation.h       |ral_relationheading.h|
 |ral_relation.h       |ral_tuple.h          |
 |ral_relation.h       |ral_attribute.h      |
 |ral_relation.h       |ral_vector.h         |
 |ral_relation.h       |ral_joinmap.h        |
 |ral_relation.h       |stdio.h              |
 |ral_relationobj.h    |stdio.h              |
 |ral.c                |ral_relvar.h         |
 |ral_relvar.h         |tcl.h                |
 |ral_relvar.h         |ral_vector.h         |
 |ral_relvar.h         |ral_relation.h       |
 |ral_relvar.h         |ral_joinmap.h        |
 |ral.c                |ral_relvarobj.h      |
 |ral_relvarobj.h      |tcl.h                |
 |ral_relvarobj.h      |ral_relvar.h         |
 |ral_relvarobj.h      |ral_relationheading.h|
 |ral.c                |ral_relvarcmd.h      |
 |ral_relvarcmd.h      |tcl.h                |
 +=====================+=====================+
 File Dependencies
 -----------------
 593 microseconds per iteration
 +=====================+=====================+
 |FileName             |DepFile              |
 |string               |string               |
 +=====================+=====================+
 |ral.c                |stdio.h              |
 |ral.c                |string.h             |
 |ral.c                |tcl.h                |
 |ral.c                |ral_tuplecmd.h       |
 |ral.c                |ral_tupleobj.h       |
 |ral.c                |ral_utils.h          |
 |ral.c                |ral_tupleheading.h   |
 |ral.c                |ral_attribute.h      |
 |ral.c                |ral_joinmap.h        |
 |ral.c                |ral_vector.h         |
 |ral.c                |ral_tuple.h          |
 |ral.c                |ral_relationcmd.h    |
 |ral.c                |ral_relationobj.h    |
 |ral.c                |ral_relationheading.h|
 |ral.c                |ral_relation.h       |
 |ral.c                |ral_relvar.h         |
 |ral.c                |ral_relvarobj.h      |
 |ral.c                |ral_relvarcmd.h      |
 |ral_tuplecmd.h       |stdio.h              |
 |ral_tuplecmd.h       |tcl.h                |
 |ral_tuplecmd.h       |ral_tupleobj.h       |
 |ral_tuplecmd.h       |ral_utils.h          |
 |ral_tuplecmd.h       |ral_tupleheading.h   |
 |ral_tuplecmd.h       |ral_attribute.h      |
 |ral_tuplecmd.h       |ral_joinmap.h        |
 |ral_tuplecmd.h       |ral_vector.h         |
 |ral_tuplecmd.h       |ral_tuple.h          |
 |ral_tupleobj.h       |stdio.h              |
 |ral_tupleobj.h       |tcl.h                |
 |ral_tupleobj.h       |ral_utils.h          |
 |ral_tupleobj.h       |ral_tupleheading.h   |
 |ral_tupleobj.h       |ral_attribute.h      |
 |ral_tupleobj.h       |ral_joinmap.h        |
 |ral_tupleobj.h       |ral_vector.h         |
 |ral_tupleobj.h       |ral_tuple.h          |
 |ral_utils.h          |tcl.h                |
 |ral_tupleheading.h   |stdio.h              |
 |ral_tupleheading.h   |tcl.h                |
 |ral_tupleheading.h   |ral_utils.h          |
 |ral_tupleheading.h   |ral_attribute.h      |
 |ral_tupleheading.h   |ral_joinmap.h        |
 |ral_tupleheading.h   |ral_vector.h         |
 |ral_attribute.h      |tcl.h                |
 |ral_attribute.h      |ral_utils.h          |
 |ral_joinmap.h        |stdio.h              |
 |ral_joinmap.h        |ral_vector.h         |
 |ral_vector.h         |stdio.h              |
 |ral_tuple.h          |stdio.h              |
 |ral_tuple.h          |tcl.h                |
 |ral_tuple.h          |ral_utils.h          |
 |ral_tuple.h          |ral_tupleheading.h   |
 |ral_tuple.h          |ral_attribute.h      |
 |ral_tuple.h          |ral_joinmap.h        |
 |ral_tuple.h          |ral_vector.h         |
 |ral_relationcmd.h    |tcl.h                |
 |ral_relationobj.h    |stdio.h              |
 |ral_relationobj.h    |tcl.h                |
 |ral_relationobj.h    |ral_utils.h          |
 |ral_relationobj.h    |ral_tupleheading.h   |
 |ral_relationobj.h    |ral_attribute.h      |
 |ral_relationobj.h    |ral_joinmap.h        |
 |ral_relationobj.h    |ral_vector.h         |
 |ral_relationobj.h    |ral_tuple.h          |
 |ral_relationobj.h    |ral_relationheading.h|
 |ral_relationobj.h    |ral_relation.h       |
 |ral_relationheading.h|stdio.h              |
 |ral_relationheading.h|tcl.h                |
 |ral_relationheading.h|ral_utils.h          |
 |ral_relationheading.h|ral_tupleheading.h   |
 |ral_relationheading.h|ral_attribute.h      |
 |ral_relationheading.h|ral_joinmap.h        |
 |ral_relationheading.h|ral_vector.h         |
 |ral_relation.h       |stdio.h              |
 |ral_relation.h       |tcl.h                |
 |ral_relation.h       |ral_utils.h          |
 |ral_relation.h       |ral_tupleheading.h   |
 |ral_relation.h       |ral_attribute.h      |
 |ral_relation.h       |ral_joinmap.h        |
 |ral_relation.h       |ral_vector.h         |
 |ral_relation.h       |ral_tuple.h          |
 |ral_relation.h       |ral_relationheading.h|
 |ral_relvar.h         |stdio.h              |
 |ral_relvar.h         |tcl.h                |
 |ral_relvar.h         |ral_utils.h          |
 |ral_relvar.h         |ral_tupleheading.h   |
 |ral_relvar.h         |ral_attribute.h      |
 |ral_relvar.h         |ral_joinmap.h        |
 |ral_relvar.h         |ral_vector.h         |
 |ral_relvar.h         |ral_tuple.h          |
 |ral_relvar.h         |ral_relationheading.h|
 |ral_relvar.h         |ral_relation.h       |
 |ral_relvarobj.h      |stdio.h              |
 |ral_relvarobj.h      |tcl.h                |
 |ral_relvarobj.h      |ral_utils.h          |
 |ral_relvarobj.h      |ral_tupleheading.h   |
 |ral_relvarobj.h      |ral_attribute.h      |
 |ral_relvarobj.h      |ral_joinmap.h        |
 |ral_relvarobj.h      |ral_vector.h         |
 |ral_relvarobj.h      |ral_tuple.h          |
 |ral_relvarobj.h      |ral_relationheading.h|
 |ral_relvarobj.h      |ral_relation.h       |
 |ral_relvarobj.h      |ral_relvar.h         |
 |ral_relvarcmd.h      |tcl.h                |
 +=====================+=====================+
 Transitive Closure
 ------------------
 ral.c depends upon:
        ral_attribute.h
        ral_joinmap.h
        ral_relation.h
        ral_relationcmd.h
        ral_relationheading.h
        ral_relationobj.h
        ral_relvar.h
        ral_relvarcmd.h
        ral_relvarobj.h
        ral_tuple.h
        ral_tuplecmd.h
        ral_tupleheading.h
        ral_tupleobj.h
        ral_utils.h
        ral_vector.h
        stdio.h
        string.h
        tcl.h

----
[Category Example]