Description
prob1: mymake This problem involves writing a C program that implements part the core functionality of the make utility. This assignment involves reading in a file specifying dependencies and rules as in make (though with a different and more explicit syntax); constructing a dependency tree; and then traversing the tree starting with some specified target. The extension to actually check timestamps and execute the associated commands where necessary will be part of a future assignment. Invocation: Your program will be compiled to an executable named mymake . It will be invoked as follows: mymake aMakeFile aTarget aMakeFile is is a file specifying dependencies and rules according to the format given below; and aTarget is the name of a target appearing in aMakeFile. Behavior: An invocation “mymake aMakeFile aTarget” of your program should behave as follows: (i) read in the targets and dependencies specified in aMakeFile and construct the corresponding data dependency graph; (ii) traverse this graph using a postorder traversal, starting at the node corresponding to the target aTarget. (The Wikipedia discusses the general notion of tree traversals, including postorder traversals, in more detail.) Files: You should structure your program so that conceptually distinct pieces of the program reside in distinct files. For instance, the code for reading the makefile specifications might be in a different file from the fuctions dealing with graphs. (for example, finding a node, adding a node, traversing the graph, etc.) You should include at least 2 different files of source code and one header file. You can include more if you feel so inclined. Output: The output produced by your program is a sequence of node names obtained from the postorder traversal of the dependency graph (see below) followed by all the commands for those nodes with the commands indented two spaces. To guarantee your output matches the example code, visit the children of a node in the order they are listed in the make file. Errors: Error messages should be sensible and informative (use perror where necessary) and should be sent to stderr. The following are all fatal errors and should cause the program to exit immediately with exit status 1. o An input file or a target is not specified. o Too many arguments are specified. o The input file cannot be opened for reading. o The input file is in an illegal format. o The specified target is not defined in the input file. Assumptions and Restrictions Assumptions: You may assume that a word in the input mymake file has length at most 64. Restrictions: The point of this exercise is to work with pointers and dynamic data structures. Programs that use statically preallocated memory will not get credit. You will also not get credit for solutions that use realloc or which simulate realloc by making repeated calls to malloc or calloc. (In other words, use linked lists as in prior programs.) mymake makefile specifications Terminology A whitespace character is any character for which the function isspace() returns a nonzero value, e.g., blanks, tabs, newlines. Note that since rules are on lines that you should read with getline(), we can essentially ignore the possibibilty of newlines in what follows. A word is a nonempty sequence of characters that are not whitespace and not :. File Structure A “mymake file” consists of a sequence of rules. These have the structure specified below. 1. Rules A rule consists of a single target specification followed by a list of zero or more commands. The commands are listed on separate lines. These have the structure specified below. 1.1. Target Specification A target specification is of the form target : str1 str2 … strn There can be any number of dependencies (strings separated by whitespace after the “:”, including none). There can be any amount of whitespace before and after the “:”, including none. Important: A word cannot appear as the target for more than one rule. 1.2. Commands A command is of the form \t cmd where cmd is a bash command. The tab character, \t, must be exactly the first character on the line. The space after the \t is just for illustration purposes. You can choose to support leading spaces before cmd, but we will not test that. 2. Examples The following are examples of mymake files. (Note that in these examples by “\t” I mean a tab character, not the two chars ‘\’ and ‘t’): Example 1: The following is legal: spellcheck.o : utils.h spellcheck.h spellcheck.c \t gcc -Wall -c spellcheck.c hash.o :hash.c utils.h hash.h \t gcc -Wall hash.c spellcheck : hash.o spellcheck.o \t gcc *.o -o spellcheck testStuff: \t spellcheck out1 \t spellcheck out2 \t spellcheck out3 Example 2: The following is illegal. Because spellcheck appears as a target more than once. spellcheck : hash.c spellcheck.c \t gcc hash.c spellcheck.c -o spellcheck spellcheck.o : utils.h spellcheck.h spellcheck.c \t gcc -Wall -c spellcheck.c hash.o : hash.c utils.h hash.h \t gcc -Wall hash.c spellcheck : hash.o spellcheck.o \t gcc *.o -o spellcheck Dependency Graphs A dependency graph is a data structure that captures the dependencies between different files as specified in a make file. To keep this discussion specific, we will focus here on rules in mymake format; however, the concepts are not specific to this assignment and generalize readily to the full make utility. 1. Structure A dependency graph is a directed graph satisfying the following: Each node represents a target or something a target depends on as given in the input mymake file. Thus, for each rule of the form A : … B … \t cmd1 \t cmd2 there is a node named A and a node named B in the dependency graph and there is edge from node A to node B if A “depends on” B. The sequence of commands (cmd1 and cmd2 in the above example) is associated with the dependency graph node for the target for the rule. The following example illustrates the notion of dependency graphs. Concider the following mymake file: spellcheck.o : utils.h spellcheck.h spellcheck.c \t gcc -Wall -c spellcheck.c hash.o : hash.c utils.h hash.h \t gcc -Wall hash.c spellcheck : hash.o spellcheck.o \t gcc *.o -o spellcheck The corresponding dependency graph is as follows: The ordering on the children of each node in a dependency graph is significant: it reflects the left-to-right ordering on the dependencies specified as part of a rule. For example, the first rule in the example above gives the dependencies of the target “spellcheck.o” in the following left-toright order: utils.h spellcheck.h spellcheck.c The children of the node corresponding to this target in the dependency graph shown above reflect this ordering. 2. Post-order Traversal Let the sequence of children of the node aTarget be <aChild1, aChild2, …, aChildn>, where the ordering on the nodes aChildi reflects as the ordering specified in the target specification for the rule for aTarget, as discussed above. The postorder traversal of the graph starting at node aTarget is carried out as follows: PostOrder (aTarget) If aTarget visited return mark aTarget as visited for i = 1 to n (in that order) PostOrder(aChildi); Process aTarget For the purposes of this assignment, “processing a node” simply means printing out its name, without any extraneous whitespace, followed by a newline, and then each command (if any) associated with that target. Each command should be on its own line and should be indented two spaces. This is essentially a depth first search Example: A post-order traversal of the dependency graph shown above, starting at the root node spellcheck, produces the following: hash.c utils.h hash.h hash.o gcc -Wall hash.c spellcheck.h spellcheck.c spellcheck.o gcc -Wall -c spellcheck.c spellcheck gcc *.o -o spellcheck
