path: root/test/xref.original

XREF(AWK)                   Philip L. Bewig                   XREF(AWK)

NAME

        xref(awk) - produce a cross reference listing of an awk program

SYNOPSIS

        awk -f xref.awk [ file ... ]

DESCRIPTION

        XREF(AWK) takes as input a valid awk program and produces as out-
        put a cross-reference listing of all variables and function calls
        which appear in the program.

        For ordinary variables and array variables, a line of the form

                count var(func) lines ...

        is produced, where "count" is the number of times the variable is
        used, "var" is the name of the variable, "func" is the function
        name to which the variable is local (a null "func" indicates that
        the variable is global), and "lines" is the number of each line
        where the variable appears.  Appearances of the variable in a
        function's parameter list are ignored.  The number of lines shown
        may differ from "count" if the variable appears more than once on
        the same line.

        For functions, a line of the form

                count func(define) lines ...

        is produced, where "count" is the number of times the function is
        called, "func" is the name of the function, "define" is the lime
        number where the function is defined, and "lines" is the number of
        each line where the function is called.  As for variables, the
        number of lines shown may differ from "count."

        Output lines for variables and functions are intermixed and are
        sorted by name.  Though terse, the output is informative, easy to
        read, and amenable to further processing.

EXAMPLE

        The cross-reference listing produced by running xref.awk against
        itself is shown below:

                5 NR() 39 45 50 53 68
                8 RLENGTH() 119 120 123 124 127 128 132 133
                10 act() 31 34 36 40 51 54 56 63 65 67
                1 arr(asplit) 90
                2 arr(inarray) 93 94
                1 asplit(89) 6
                3 braces() 55 57 58
                2 flines() 53 79
                1 fs(asplit) 89
                3 funcname() 42 52 61
                16 i() 76 77 78 79 81 82 83 84 90
                3 inarray(92) 37 43 48
                6 j() 82 83 84
                3 j(inarray) 93 94
                3 keywords() 10 125 129
                1 lex(97) 29
                31 line() 103 104 107 108 109 110 112 113 114 115 116 117 118
                        119 120 122 123 124 126 127 128 131 132 133
                6 lines() 39 45 50 83 84
                4 local() 41 59 60 64
                3 machine() 17 30 31
                2 n(asplit) 89 90
                15 names() 37 38 43 44 48 49 77 78 79 81 82 83 84
                3 nextstate() 30 62 73
                4 nnames() 38 44 49 76
                4 state() 23 30 31 73
                1 str(asplit) 89
                3 symb() 29 30 31
                2 temp() 59 60
                2 temp_asplit() 89 90
                31 tok() 37 38 39 41 42 43 44 45 47 48 49 50 52 53 64 101 105
                        113 115 117 119 123 125 127 129 132
                1 val(inarray) 94
                5 xnames() 39 45 50 77 82

        For readability, some lines have been folded.

SOURCE CODE

        # xref.awk - cross reference an awk program

        BEGIN {

                # create array of keywords to be ignored by lexer
                asplit("BEGIN:END:atan2:break:close:continue:cos:delete:" \
                        "do:else:exit:exp:for:getline:gsub:if:in:index:int:"  \
                        "length:log:match:next:print:printf:rand:return:sin:" \
                        "split:sprintf:sqrt:srand:sub:substr:system:while",
                        keywords,":")

                # build the symbol-state table
                split("00:00:00:00:00:00:00:00:00:00:" \
                          "20:10:10:12:12:11:07:00:00:00:" \
                          "08:08:08:08:08:33:08:00:00:00:" \
                          "08:44:08:36:08:08:08:00:00:00:" \
                          "08:44:45:42:42:41:08",machine,":")

                # parse the input and store an intermediate representation
                # of the cross-reference information

                # set up the machine
                state = 1

                # run the machine
                for (;;) {

                        # get next symbol
                        symb = lex()
                        nextstate = substr(machine[state symb],1,1)
                        act = substr(machine[state symb],2,1)

                        # perform required action
                        if ( act == "0" )
                                ; # do nothing
                        else if ( act == "1" ) {
                                if ( ! inarray(tok,names) )
                                        names[++nnames] = tok
                                lines[tok,++xnames[tok]] = NR }
                        else if ( act == "2" ) {
                                if ( tok in local ) {
                                        tok = tok "(" funcname ")"
                                        if ( ! inarray(tok,names) )
                                                names[++nnames] = tok
                                        lines[tok,++xnames[tok]] = NR }
                                else {
                                        tok = tok "()"
                                        if ( ! inarray(tok,names) )
                                                names[++nnames] = tok
                                        lines[tok,++xnames[tok]] = NR } }
                        else if ( act == "3" ) {
                                funcname = tok
                                flines[tok] = NR }
                        else if ( act == "4" )
                                braces++
                        else if ( act == "5" ) {
                                braces--
                                if ( braces == 0 ) {
                                        for ( temp in local )
                                                delete local[temp]
                                        funcname = ""
                                        nextstate = 1 } }
                        else if ( act == "6" ) {
                                local[tok] = 1 }
                        else if ( act == "7" )
                                break
                        else if ( act == "8" ) {
                                print "error: xref.awk: line " NR ": aborting" \
                                        > "/dev/con"
                                exit 1 }

                        # finished with current token
                        state = nextstate }

                # finished parsing, now ready to print output
                for ( i = 1; i <= nnames; i++ ) {
                        printf "%d ", xnames[names[i]] |"sort +1"
                        if ( index(names[i],"(") == 0 )
                                printf "%s(%d)", names[i], flines[names[i]] |"sort +1"
                        else
                                printf "%s", names[i] |"sort +1"
                        for ( j = 1; j <= xnames[names[i]]; j++ )
                                if ( lines[names[i],j] != lines[names[i],j-1] )
                                        printf " %d", lines[names[i],j] |"sort +1"
                        printf "\n" |"sort +1" }

                } # END OF PROGRAM

        function asplit(str,arr,fs,  n) { n = split(str,temp_asplit,fs)
                for ( i = 1; i <= n; i++ ) arr[temp_asplit[i]]++ }

        function inarray(val,arr,  j) {
            for ( j in arr )
                if ( arr[j] == val ) return j
            return "" }

        function lex() {

                for (;;) {

                        if ( tok == "(eof)" ) return 7

                        while ( length(line) == 0 )
                                if ( getline line == 0 ) {
                                        tok = "(eof)"; return 7 }

                        sub(/^[ \t]+/,"",line)                                # remove white space,
                        sub(/^"([^"]|\\")*"/,"",line)             # quoted strings,
                        sub(/^\/([^\/]|\\\/)+\//,"",line)     # regular expressions,
                        sub(/^#.*/,"",line)                                   # and comments

                        if ( line ~ /^function/ ) {
                                tok = "function"; line = substr(line,9); return 1 }
                        else if ( line ~ /^{/ ) {
                                tok = "{"; line = substr(line,2); return 2 }
                        else if ( line ~ /^}/ ) {
                                tok = "}"; line = substr(line,2); return 3 }
                        else if ( match(line,/^[A-Za-z_][A-Za-z_0-9]*\[/) ) {
                                tok = substr(line,1,RLENGTH-1)
                                line = substr(line,RLENGTH+1)
                                return 5 }
                        else if ( match(line,/^[A-Za-z_][A-Za-z_0-9]*\(/) ) {
                                tok = substr(line,1,RLENGTH-1)
                                line = substr(line,RLENGTH+1)
                                if ( ! ( tok in keywords ) ) return 6 }
                        else if ( match(line,/^[A-Za-z_][A-Za-z_0-9]*/) ) {
                                tok = substr(line,1,RLENGTH)
                                line = substr(line,RLENGTH+1)
                                if ( ! ( tok in keywords ) ) return 4 }
                        else {
                                match(line,/^[^A-Za-z_{}]/)
                                tok = substr(line,1,RLENGTH)
                                line = substr(line,RLENGTH+1) } } }

TECHNICAL DISCUSSION

        Broadly, XREF(AWK) parses an awk program using a symbol-state
        table, in much the same way as a yacc-generated parser.  The
        lexical analyzer recognizes seven distinct symbols:  the word
        "function", the left brace, the right brace, identifiers used
        as variables, identifiers used as arrays, identifiers used as
        functions, and end of file.  The type of symbol is returned to
        the parser as the value of the "lex" function, and the global
        variable "tok" is set to the text of the current token.

        The symbol-state table is stored in the "machine" array.  The
        table can be represented as follows:

                       symbol |     1       2  3   4     5     6     7
                              |
        state                 | "function"  {  }  var  array  func  eof
        -- -- -- -- -- -- -- -+- -- -- -- -- -- -- -- -- -- -- -- -- --
        1 any                 |     20     10  10  12    12    11   07
        2 "function"          |     08     08  08  08    08    33   08
        3 "function" name     |     08     44  08  36    08    08   08
        4 "function" name "{" |     08     44  45  42    42    41   08

        where the first digit is the state to be entered after process-
        ing the current token and the second digit is an action to be
        performed.  The actions are listed below:

                1       found a function call
                2       found a variable or array
                3       found a function definition
                4       found a left brace
                5       found a right brace
                6       found a local variable declaration
                7       found end of file
                8       found an error

        Each of the first six actions causes some information about the
        target program to be stored for later processing; the structures
        used will be discussed below.  The seventh action causes the
        parser to exit.  The eighth action causes errors to be reported
        to standard error and the program to abort.

        Before describing the intermediate data structures, we will
        discuss some of the more interesting points in the action calls.
        The "braces" variable keeps track of whether we are currently
        within a functions; it is positive within a function and zero
        without.  When the right brace which causes the value of "braces"
        to go from one to zero is found, the value of "nextstate" is
        changed from four (scanning a function) to one (any) and the
        names of local variables are forgotten.  The "local" array is
        accumulated from the variables found after the function name but
        before the opening left brace of the function; action two care-
        fully checks whether a variable is global or local before writing
        to the intermediate data structure.  The variable "funcname" is
        the name of the current function when within a function and null
        without.

        The following arrays store an intermediate representation of the
        variable and function identifiers of the target program:

                names[1..nnames] = list of all identifiers, both variable and
                        function names; for variables, the name has the form
                        var(func), but for functions, there are no parentheses

                xnames[names[i]] = number of times names[i] is used

                lines[names[i],1..xnames[names[i]]] = list of line numbers
                        where names[i] is used

                flines[names[i]] = line number where function names[i] is
                        defined

        These arrays are created as the parser reads the input; when the
        parser is finished, the arrays are output in user-readable form.

PORTABILITY

        XREF(AWK) will work with any implementation of nawk.  The MKS
        ToolKit implementation requires the large-model version of awk.

HISTORY

        Written by Phil Bewig on February 10, 1990.  Inspired by
        Exercise 3-16 of the book "The Awk Programming Language" by
        Alfred V. Aho, Brian W. Kernighan and Peter J. Weinberger
        (Addison-Wesley:  1988).

COPYRIGHT

        This program is placed in the public domain.  However, the
        author requests credit when distributed.