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 dhis is TclRAL a relational algebra library extention for Tcl.
INSTALLATION ============
Installation follows the typical TEA scheme. On most UNIX or Linux systems it should be sufficient to unwrap the source and:
% ./configure % make % make install
Configure typically needs to know where Tcl is installed on your system via the "--with-tcl=...." argument.
This also works more or less on Windows system using MSys or Cygwin. I build the Windows binary distributes using MSys.
BINARY DISTRIBUTION ===================
If you have selected to use one of the binary distributions, then it is only necessary to un-tar or un-zip the file into a directory that is along your Tcl library path. This could be in the "lib" directory of your Tcl installation (a common practice under Windows) or in any directory that is mentioned in the TCLLIBPATH environment variable. Binary distributions come with documentation and test cases located in directories below the package files.
CONTACT =======
TclRAL is a hosted at SourceForge and bug reportss and requests can be posted there:
http://sourceforge.net/projects/tclral
ependencies. 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