dgsh – Directed Graph Shell

Downloading and installation The dgsh suite has been tested under Debian and Ubuntu Linux, FreeBSD, and Mac OS X. A Cygwin port is underway. An installation of GraphViz will allow you to visualize the dgsh graphs that you specify in your programs. By default, the program and its documentation are installed under /usr/local . You can modify this by setting the PREFIX variable in the `config` step, for example: To test dgsh you will need to have the following ports installed on your system: To compile and run dgsh you will need to have the following packages installed in your system: By default, the program and its documentation are installed under /usr/local . You can modify this by setting the PREFIX variable in the `config` step, for example: To test dgsh you will need to have the following commands installed in your system: To compile and run dgsh you will need to have the following commands installed on your system: These are the manual pages for dgsh, the associated helper programs and the API in formats suitable for browsing and printing. The commands are listed in the order of usefulness in everyday scenarios. Examples Compression benchmark Report file type, length, and compression performance for data received from the standard input. The data never touches the disk. Demonstrates the use of an output multipipe to source many commands from one followed by an input multipipe to sink to one command the output of many and the use of dgsh-tee that is used both to propagate the same input to many commands and collect output from many commands orderly in a way that is transparent to users. #!/usr/bin/env dgsh tee | {{ printf 'File type:\t' file - printf 'Original size:\t' wc -c printf 'xz:\t\t' xz -c | wc -c printf 'bzip2:\t\t' bzip2 -c | wc -c printf 'gzip:\t\t' gzip -c | wc -c }} | cat Git commit statistics Process the Git history, and list the authors and days of the week ordered by the number of their commits. Demonstrates streams and piping through a function. #!/usr/bin/env dgsh forder() { sort | uniq -c | sort -rn } git log --format="%an:%ad" --date=default "$@" | tee | {{ echo "Authors ordered by number of commits" # Order by frequency awk -F: '{print $1}' | forder echo "Days ordered by number of commits" # Order by frequency awk -F: '{print substr($2, 1, 3)}' | forder }} | cat C code metrics Process a directory containing C source code, and produce a summary of various metrics. Demonstrates nesting, commands without input. #!/usr/bin/env dgsh {{ # C and header code find "$@" \( -name \*.c -or -name \*.h \) -type f -print0 | tee | {{ # Average file name length # Convert to newline separation for counting echo -n 'FNAMELEN: ' tr \\0 \ | # Remove path sed 's|^.*/||' | # Maintain average awk '{s += length($1); n++} END { if (n>0) print s / n; else print 0; }' xargs -0 /bin/cat | tee | {{ # Remove strings and comments sed 's/#/@/g;s/\\[\\"'\'']/@/g;s/"[^"]*"/""/g;'"s/'[^']*'/''/g" | cpp -P | tee | {{ # Structure definitions echo -n 'NSTRUCT: ' egrep -c 'struct[ ]*{|struct[ ]*[a-zA-Z_][a-zA-Z0-9_]*[ ]*{' #}} (match preceding openings) # Type definitions echo -n 'NTYPEDEF: ' grep -cw typedef # Use of void echo -n 'NVOID: ' grep -cw void # Use of gets echo -n 'NGETS: ' grep -cw gets # Average identifier length echo -n 'IDLEN: ' tr -cs 'A-Za-z0-9_' ' ' | sort -u | awk '/^[A-Za-z]/ { len += length($1); n++ } END { if (n>0) print len / n; else print 0; }' }} # Lines and characters echo -n 'CHLINESCHAR: ' wc -lc | awk '{OFS=":"; print $1, $2}' # Non-comment characters (rounded thousands) # -traditional avoids expansion of tabs # We round it to avoid failing due to minor # differences between preprocessors in regression # testing echo -n 'NCCHAR: ' sed 's/#/@/g' | cpp -traditional -P | wc -c | awk '{OFMT = "%.0f"; print $1/1000}' # Number of comments echo -n 'NCOMMENT: ' egrep -c '/\*|//' # Occurences of the word Copyright echo -n 'NCOPYRIGHT: ' grep -ci copyright }} }} # C files find "$@" -name \*.c -type f -print0 | tee | {{ # Convert to newline separation for counting tr \\0 \ | tee | {{ # Number of C files echo -n 'NCFILE: ' wc -l # Number of directories containing C files echo -n 'NCDIR: ' sed 's,/[^/]*$,,;s,^.*/,,' | sort -u | wc -l }} # C code xargs -0 /bin/cat | tee | {{ # Lines and characters echo -n 'CLINESCHAR: ' wc -lc | awk '{OFS=":"; print $1, $2}' # C code without comments and strings sed 's/#/@/g;s/\\[\\"'\'']/@/g;s/"[^"]*"/""/g;'"s/'[^']*'/''/g" | cpp -P | tee | {{ # Number of functions echo -n 'NFUNCTION: ' grep -c '^{' # Number of gotos echo -n 'NGOTO: ' grep -cw goto # Occurrences of the register keyword echo -n 'NREGISTER: ' grep -cw register # Number of macro definitions echo -n 'NMACRO: ' grep -c '@[ ]*define[ ][ ]*[a-zA-Z_][a-zA-Z0-9_]*(' # Number of include directives echo -n 'NINCLUDE: ' grep -c '@[ ]*include' # Number of constants echo -n 'NCONST: ' grep -ohw '[0-9][x0-9][0-9a-f]*' | wc -l }} }} }} # Header files echo -n 'NHFILE: ' find "$@" -name \*.h -type f | wc -l }} | # Gather and print the results cat Find duplicate files List the names of duplicate files in the specified directory. Demonstrates the combination of streams with a relational join. #!/usr/bin/env dgsh # Create list of files find "$@" -type f | # Produce lines of the form # MD5(filename)= 811bfd4b5974f39e986ddc037e1899e7 xargs openssl md5 | # Convert each line into a "filename md5sum" pair sed 's/^MD5(//;s/)= / /' | # Sort by MD5 sum sort -k2 | tee | {{ # Print an MD5 sum for each file that appears more than once awk '{print $2}' | uniq -d # Promote the stream to gather it cat }} | # Join the repeated MD5 sums with the corresponding file names # Join expects two inputs, second will come from scatter # XXX make streaming input identifiers transparent to users join -2 2 | # Output same files on a single line awk ' BEGIN {ORS=""} $1 != prev && prev {print " "} END {if (prev) print " "} {if (prev) print " "; prev = $1; print $2}' Highlight misspelled words Highlight the words that are misspelled in the command's first argument. Demonstrates stream processing with multipipes and the avoidance of pass-through constructs to avoid deadlocks. #!/usr/bin/env dgsh export LC_ALL=C tee | {{ # Find errors {{ # Obtain list of words in text tr -cs A-Za-z \ | tr A-Z a-z | sort -u # Ensure dictionary is compatibly sorted sort /usr/share/dict/words }} | # List errors as a set difference comm -23 # Pass through text cat }} | grep --fixed-strings --file=- --ignore-case --color --word-regex --context=2 Word properties Read text from the standard input and list words containing a two-letter palindrome, words containing four consonants, and words longer than 12 characters. #!/usr/bin/env dgsh # Consistent sorting across machines export LC_ALL=C # Stream input from file cat $1 | # Split input one word per line tr -cs a-zA-Z \ | # Create list of unique words sort -u | tee | {{ # Pass through the original words cat # List two-letter palindromes sed 's/.*\(.\)\(.\)\2\1.*/p: \1\2-\2\1/;t g' # List four consecutive consonants sed -E 's/.*([^aeiouyAEIOUY]{4}).*/c: \1/;t g' # List length of words longer than 12 characters awk '{if (length($1) > 12) print "l:", length($1); else print ""}' }} | # Paste the four streams side-by-side paste | # List only words satisfying one or more properties fgrep : Web log reporting Creates a report for a fixed-size web log file read from the standard input. Demonstrates the combined use of multipipe blocks, writeval and readval to store and retrieve values, and functions in the scatter block. Used to measure throughput increase achieved through parallelism. #!/usr/bin/env dgsh # Output the top X elements of the input by the number of their occurrences # X is the first argument toplist() { uniq -c | sort -rn | head -$1 echo } # Output the argument as a section header header() { echo echo "$1" echo "$1" | sed 's/./-/g' } # Consistent sorting export LC_ALL=C export -f toplist export -f header if [ -z "${DGSH_DRAW_EXIT}" ] then cat </dev/null || gdate -f - +%a)' | sort | uniq -c | sort -rn }} }} # Hour {{ call 'header "Accesses by Local Hour"' awk -F: '{print $2}' | sort | uniq -c }} }} dgsh-readval -q -s nAccess }} | cat Text properties Read text from the standard input and create files containing word, character, digram, and trigram frequencies. #!/usr/bin/env dgsh # Consistent sorting across machines export LC_ALL=C # Convert input into a ranked frequency list ranked_frequency() { awk '{count[$1]++} END {for (i in count) print count[i], i}' | # We want the standard sort here sort -rn } # Convert standard input to a ranked frequency list of specified n-grams ngram() { local N=$1 perl -ne 'for ($i = 0; $i < length($_) - '$N'; $i++) { print substr($_, $i, '$N'), " "; }' | ranked_frequency } export -f ranked_frequency export -f ngram tee | {{ # Split input one word per line tr -cs a-zA-Z \ | tee | {{ # Digram frequency call 'ngram 2 >digram.txt' # Trigram frequency call 'ngram 3 >trigram.txt' # Word frequency call 'ranked_frequency >words.txt' }} # Store number of characters to use in awk below wc -c | dgsh-writeval -s nchars # Character frequency sed 's/./&\ /g' | # Print absolute call 'ranked_frequency' | awk 'BEGIN { "dgsh-readval -l -x -q -s nchars" | getline NCHARS OFMT = "%.2g%%"} {print $1, $2, $1 / NCHARS * 100}' > character.txt }} C/C++ symbols that should be static Given as an argument a directory containing object files, show which symbols are declared with global visibility, but should have been declared with file-local (static) visibility instead. Demonstrates the use of dgsh-capable comm (1) to combine data from two sources. #!/usr/bin/env dgsh # Find object files find "$1" -name \*.o | # Print defined symbols xargs nm | tee | {{ # List all defined (exported) symbols awk 'NF == 3 && $2 ~ /[A-Z]/ {print $3}' | sort # List all undefined (imported) symbols awk '$1 == "U" {print $2}' | sort }} | # Print exports that are not imported comm -23 Hierarchy map Given two directory hierarchies A and B passed as input arguments (where these represent a project at different parts of its lifetime) copy the files of hierarchy A to a new directory, passed as a third argument, corresponding to the structure of directories in B. Demonstrates the use of join to process results from two inputs and the use of gather to order asynchronously produced results. #!/usr/bin/env dgsh if [ -z "${DGSH_DRAW_EXIT}" -a \( ! -d "$1" -o ! -d "$2" -o -z "$3" \) ] then echo "Usage: $0 dir-1 dir-2 new-dir-name" 1>&2 exit 1 fi NEWDIR="$3" export LC_ALL=C line_signatures() { find $1 -type f -name '*.[chly]' -print | # Split path name into directory and file sed 's|\(.*\)/\([^/]*\)|\1 \2|' | while read dir file do # Print "directory filename content" of lines with # at least one alphabetic character # The fields are separated by and sed -n "/[a-z]/s|^|$dir$file|p" "$dir/$file" done | # Error: multi-character tab '\001\001' sort -T `pwd` -t -k 2 } export -f line_signatures {{ # Generate the signatures for the two hierarchies call 'line_signatures "$1"' -- "$1" call 'line_signatures "$1"' -- "$2" }} | # Join signatures on file name and content join -t -1 2 -2 2 | # Print filename dir1 dir2 sed 's///g' | awk -F 'BEGIN{OFS=" "}{print $1, $3, $4}' | # Unique occurrences sort -u | tee | {{ # Commands to copy awk '{print "mkdir -p '$NEWDIR'/" $3 ""}' | sort -u awk '{print "cp " $2 "/" $1 " '$NEWDIR'/" $3 "/" $1 ""}' }} | # Order: first make directories, then copy files # TODO: dgsh-tee does not pass along first incoming stream cat | sh Plot Git committer activity over time Process the Git history, and create two PNG diagrams depicting committer activity over time. The most active committers appear at the center vertical of the diagram. Demonstrates image processing, mixining of synchronous and asynchronous processing in a scatter block, and the use of an dgsh-compliant join command. #!/usr/bin/env dgsh # Commit history in the form of ascending Unix timestamps, emails git log --pretty=tformat:'%at %ae' | # Filter records according to timestamp: keep (100000, now) seconds awk 'NF == 2& $1 > 100000& $1 < '`date +%s` | sort -n | tee | {{ {{ # Calculate number of committers awk '{print $2}' | sort -u | wc -l | tee | {{ dgsh-writeval -s committers1 dgsh-writeval -s committers2 dgsh-writeval -s committers3 }} # Calculate last commit timestamp in seconds tail -1 | awk '{print $1}' # Calculate first commit timestamp in seconds head -1 | awk '{print $1}' }} | # Gather last and first commit timestamp cat | # Make one space-delimeted record tr ' ' ' ' | # Compute the difference in days awk '{print int(($1 - $2) / 60 / 60 / 24)}' | # Store number of days dgsh-writeval -s days sort -k2 # # Place committers left/right of the median # according to the number of their commits awk '{print $2}' | sort | uniq -c | sort -n | awk ' BEGIN { "dgsh-readval -l -x -q -s committers1" | getline NCOMMITTERS l = 0; r = NCOMMITTERS;} {print NR % 2 ? l++ : --r, $2}' | sort -k2 # }} | # Join committer positions with commit time stamps # based on committer email join -j 2 | # # Order by timestamp sort -k 2n | tee | {{ # Create portable bitmap echo 'P1' {{ dgsh-readval -l -q -s committers2 dgsh-readval -l -q -s days }} | cat | tr ' ' ' ' | awk '{print $1, $2}' perl -na -e ' BEGIN { open(my $ncf, "-|", "dgsh-readval -l -x -q -s committers3"); $ncommitters = <$ncf>; @empty[$ncommitters - 1] = 0; @committers = @empty; } sub out { print join("", map($_ ? "1" : "0", @committers)), " "; } $day = int($F[1] / 60 / 60 / 24); $pday = $day if (!defined($pday)); while ($day != $pday) { out(); @committers = @empty; $pday++; } $committers[$F[2]] = 1; END { out(); } ' }} | cat | # Enlarge points into discs through morphological convolution pgmmorphconv -erode <( cat <large.png # A smaller image pamscale -width 640 | pnmtopng >small.png }} Parallel word count Count number of times each word appears in the specified input file(s) Demonstrates parallel execution mirroring the Hadoop WordCount example via the dgsh-parallel command. In contrast to GNU parallel, the block generated by dgsh-parallel has N input and output streams, which can be combined by any dgsh-compatible tool, such as dgsh-merge-sum or sort -m. #!/usr/bin/env dgsh # Number of processes N=8 # Collation order for sorting export LC_ALL=C # Scatter input dgsh-tee -s | # Emulate Java's default StringTokenizer, sort, count dgsh-parallel -n $N "tr -s ' \t \r\f' ' ' | sort -S 512M | uniq -c" | # Merge sorted counts by providing N input channels dgsh-merge-sum $(for i in $(seq $N) ; do printf '<| ' ; done) Venue author compare Given the specification of two publication venues, read a compressed DBLP computer science bibliography from the standard input (e.g. piped from curl -s http://dblp.uni-trier.de/xml/dblp.xml.gz or from a locally cached copy) and output the number of papers published in each of the two venues as well as the number of authors who have published only in the first venue, the number who have published only in the second one, and authors who have published in both. The venues are specified through the script's first two command-line arguments as a DBLP key prefix, e.g. journals/acta/, conf/icse/, journals/software/, conf/iwpc/, or conf/msr/. Demonstrates the use of dgsh-wrap -e to have sed(1) create two output streams and the use of tee to copy a pair of streams into four ones. #!/usr/bin/env dgsh # Extract and sort author names sorted_authors() { sed -n 's/\([^<]*\)<\/author>/\1/p' | sort } # Escape a string to make it a valid sed(1) pattern escape() { echo "$1" | sed 's/\([/\\]\)/\\\1/g' } export -f sorted_authors if [ ! "$2" -a ! "$DGSH_DOT_DRAW"] ; then echo "Usage: $0 key1 key2" 1>&2 echo "Example: $0 conf/icse/ journals/software/" 1>&2 exit 1 fi gzip -dc | # Output the two venue authors as two output streams dgsh-wrap -e sed -n " /^<.*key=\"$(escape $1)/,/