GAM 2007-01-30:
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.
#! /bin/env tclsh
# 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 {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