CMSC216 Project 4: Make me a Bake

 1: # SampleBakefile: a sample Bakefile. Run this with
 2: # >> bake -f SampleBakefile
 3: 
 4: # lead target is 'demo' which will be used if
 5: # no target is specified on the command line.
 6: # Some of the commands have @ as their prefix which
 7: # silences the command.
 8: demo : hello bye
 9: 	@ echo Running programs
10: 	./hello
11: 	./bye
12: 	@ echo Done running programs
13: 
14: all : hello bye
15: 
16: # this is program 1 / 2
17: hello : hello.o
18: 	gcc -o hello hello.o
19: 
20: hello.o : hello.c
21: 	gcc -c hello.c
22: 
23: # this is program 2 / 2
24: bye : bye.o
25: 	gcc -o bye bye.o
26: 
27: bye.o : bye.c
28: 	gcc -c bye.c
29: 
30: # this target removes built files
31: clean :
32: 	rm -f hello.o bye.o hello bye
33: 
34: # END of SampleBakefile

// bake_funcs.c: required service functions for handling of Bakefiles

#include "bake.h"

////////////////////////////////////////////////////////////////////////////////
// PROBLEM 1
////////////////////////////////////////////////////////////////////////////////

char *slurp_file_efficient(char *fname);
// PROBLEM 1: Uses combination of stat() and read() to efficiently
// read in the entire contents of a file into a malloc()'d block of
// memory, null terminates it (\0). Returns a pointer to the file data
// or NULL if the file could not be opened. If the file can't be
// opened, use perror() to print "Couldn't open file" and why.

rule_t *bake_target_rule(bake_t *bake, char *targname);
// PROBLEM 1: Searches bake for a rule with a target that equals
// `targname`. If found, returns a pointer to that rule. Otherwise
// returns NULL if no rule with target `targname` exists.
//
// DESIGN NOTE: The curent design makes use of linear search for
// target location, O(rule_count) for each lookup. Maintainting a hash
// table of target->rule key/vals would allow O(1) lookup for rules
// with given target names.

void bake_print_cmd(cmd_t *cmd);
// PROBLEM 1: If the SILENCE_BIT is set, does nothing and immediately
// returns. Otherwise, prints the given command token by token. If I/O
// redirects are indicated by the fields of the command, prints the
// after all tokens with "< infile" for input followed by "> outfile"
// if present. This function is used to print out commands in
// bake_execute_cmd().

////////////////////////////////////////////////////////////////////////////////
// PROBLEM 2
////////////////////////////////////////////////////////////////////////////////

int bake_execute_cmd(cmd_t *cmd);
// PROBLEM 2: Called during bake_do_update(). Prints the command using
// bake_print_cmd() unless its SILENCE bit is set. fork()'s a child
// process which exec's the command specified in cmd->tokens.  Sets up
// I/O redirection in child process if indicated by cmd flags and
// fields. Uses a wait() call to wait until the child process is
// done. If the child completes normally, its exit code is passed up,
// 0 or non-zero. If the child process fails to complete normally or
// prints an error message with line number of command
// CMD_NONSTAND_EXIT. Non-zero returns from this function will usually
// be handled in a build by cancelling the build whil 0 return will
// cause the build to prceed and execute subsequent commands.
//
// During Input and Output redirection, if the requrested files cannot
// be opened, the child process exits with code CMD_FAIL_INPREDI or
// CMD_FAIL_OUTREDI. Additionally, if the child fails to exec() a
// command, CMD_FAIL_EXEC is used as its return code. All of these are
// non-zero and trigger builds to fail. In the above failure cases,
// prints one of the below error messages appropriate to the error.
// 
// perror("ERROR: can't open file for output")
// perror("ERROR: can't open file for output")
// perror("ERROR: job failed to exec");
//
// CLARIFICATION: When open()'ing files for output redirection,
// certain options should be passed to ensure that the created file
// adheres to conventions
// - For the second argument to open(), pass options
//     O_WRONLY|O_CREAT|O_TRUNC
//   which will open the file for writing, create it if not present,
//   and truncate the file if it already exists
// - For the third argument to open(), pass the arguments
//     S_IRUSR|S_IWUSR
//   which will set the "rw" permissions on the created file for the
//   owner (user) of the file

////////////////////////////////////////////////////////////////////////////////
// PROBLEM 3
////////////////////////////////////////////////////////////////////////////////

int bake_set_updates(bake_t *bake, char *targname);
// PROBLEM 3: Starting at `targname`, recurses down the
// target/dependency DAG setting the UPDATE bit in rule_flags to
// indicate whether a target requires updates. Makes use of the
// CLEAR_BIT(), CHECK_BIT(), and SET_BIT() macros when dealing with
// bit-manipulations. For a given rule, first visits all its
// dependencies to check if they require updates via recursion. Then
// determines if `targname` requires an update. The conditions that
// require an update are described in detail in the program
// specification and shoudl be consulted while implementing this
// function. Returns 1 if target needs to be updated so associated
// rule commands should be run later. Returns 0 if the named target
// does not need to be updated. Prints an error if targname is not
// found and returns -1. If any dependency returns -1, an error
// ocurred lower down the DAG. In case, nothing is printed nothing and
// -1 is returned up the nested recursion.

int bake_do_updates(bake_t *bake, char *targname);
// PROBLEM 3: Starting at `targname`, run commands if the UPDATE bit
// is set. Before running commands associated with `targname`,
// recursively visit dependencies and if their UPDATE bit is set, run
// their commands first. Returns number of rules that were updated or
// -1 to indicate an error ocurred while running commands.

////////////////////////////////////////////////////////////////////////////////
// PROBLEM 4
////////////////////////////////////////////////////////////////////////////////

int bake_cmd_postprocess(bake_t *bake, cmd_t *cmd);
// PROBLEM 4: Examines cmd->tokens to set cmd->flags and a few other
// fields. Used to post-process the raw tokens of a command. Likely
// uses the utility function array_shift() to ease the re-arrangment
// of arrays.
// 
// 1. If tokens[0] = "@", eliminates this token by shifting all tokens
// over and sets the SILENCED bit
// 
// 2. If tokens[i] = "<", input redirection is desired; if tokens[i+1]
// is not NULL, returns -1. Otherwise sets the INPREDI bit and
// input_redirect field to tokens[i+1]. Then shifts all tokens over to
// eliminate tokens[i] and tokens[i+1].
// 
// 3. If tokens[i] = ">", output redirection is desired and performs
// similar operations to #2 with the OUTREDI flag and output_redirect
// fields.
//
// Correctly handles any order of "< input" / "> output" and other
// tokens (ex: output redirection may appear first followed by normal
// tokens followed by input redirection)
// 
// If multiple "<" or ">" tokens appear, the behavior of this function
// is unspecified: it may return an error, segfault, or behave randomly.
// 
// Returns 0 on succesful completion.
//
// DESIGN NOTE: This function must be called prior to any commands
// being run. The ideal location is during parsing to modify commands
// as a bake_t structure is built. However, this functionality is
// separated out to enable future functionality such as variable
// substitution to be added to commands and tested separately from
// parsing. Any additional context needed for such things will be part
// of the 'bake' parameter (e.g. may contain a map of variable
// names/values for substitutions).

void bake_post_process(bake_t *bake);
// PROBLEM 4: Applies postprocessing operations to the bake after
// loading it from a file. Currently only iterates over all rules and
// applies bake_cmd_postprocess() to each of their commands.
//
// DESIGN NOTE: This function is where additional operations could be
// used to further modify the bakefile such as performing variable
// substitutions on rules / targets, including other bakefiles. etc.

////////////////////////////////////////////////////////////////////////////////
// PROBLEM 5 MAKEUP CREDIT (OPTIONAL)
////////////////////////////////////////////////////////////////////////////////

int bake_check_cycles(bake_t *bake, char *targname, int do_print);
// PROBLEM 5 MAKEUP: Analyzes `bake` starting at targname to
// deteremine if any cycles are present which would create problems
// completing a build: if targA depends on targB depends an targA, a
// cyclcil dependency exists and could not be fulfilled.  Returns 1 if
// a cycle is present, 0 if no cycle is present, and -1 if an error
// occurs such as not finding a needed target.
//
// If do_print is non-zero, prints out a message like:
// 
//   ERROR Cyclic Dependency detected:
//   fileA.txt -> fileB.txt -> fileC.txt -> fileA.txt
// 
// where the first line is always identical and the second line shows
// the path from the initial target through a cycle. Implementations
// assume that these messages will fit in a 2048-byte array and have
// undefined behavior if the message is larger.
//
// NOTES: This function needs to initiate a recursive descent into
// `bake` via a helper function which does the brunt of the work.
// This helper function may be defined in whatever way with whatever
// prototype is convenient. Global variables may be used to help
// generate cycle message BUT implementations with pride will find
// ways to avoid the use of global variables.

// bake_util.c: provided functions for the bake program

#include "bake.h"

////////////////////////////////////////////////////////////////////////////////
// string processing
////////////////////////////////////////////////////////////////////////////////

void split_into_lines(char *text, char ***lines, int *nlines);
// Modifies `text` so that each line ends with a \0 (rather than
// \n). Sets lines to point to a malloc()'d array of the start of each
// line. Sets nlines to be the number of lines.
//
// EXAMPLE:
// char text[32] = "every good\nboy does fine\nFACEG\n\0";
// char **lines; int nlines;
// split_into_lines(text, &lines, &nlines);
// - text[] is now "every good\0boy does fine\0FACEG\0\0"
// - nlines is now 4
// - lines is now {"every good","boy does fine","FACEG",""}
// - lines[i] points into text[]

void split_into_tokens(char *line, char ***tokens, int *ntokens);
// Modifies line so that whitespace-separate characters are replaced
// with \0's to denote 'tokens'. Sets parameter `tokens` to be a
// malloc()'d array with pointers to each of the tokens. Sets ntokens
// to be the nubmer of tokens in the line.
//
// EXAMPLE:
// char line[32] = "hello  :  friendly world\0";
// char **tokens; int notkens;
// split_into_tokens(line, &tokens, &ntokens);
// - line[] is now "hello\0\0:\0\0friendly\0world\0"
// - ntokens is now 4
// - tokens is now {"hello",":","friendly","world"}
// - tokens[i] points into line[]

////////////////////////////////////////////////////////////////////////////////
// general utilities
////////////////////////////////////////////////////////////////////////////////

void array_shift(char *strs[], int delpos, int maxlen);
// shift the array of strings left by 1 starting at delpos; eliminates
// delpos from the array.

long diff_timespec(struct timespec a, struct timespec b);
// returns difference in times between a-b; positive return means a is
// newer than b; negative indicates b is newer than a

void Dprintf(const char* format, ...);
// Prints out a message if the environment variable DEBUG is set;
// Try running as `DEBUG=1 ./some_program`

void ind_printf(int ind, const char* format, ...);
// Like printf but indents 'ind' spaces; used for printing recursive
// data structures

////////////////////////////////////////////////////////////////////////////////
// bake-specific provided functions
////////////////////////////////////////////////////////////////////////////////

rule_t *bake_add_empty_rule(bake_t *bake);
// Modifies `bake` to add a new, empty rule to it and returns a
// pointer to that rule. If bake->rules[] is full (rule_capacity and
// rule_count are equal) doubles the size of rules[] via realloc() in
// order create room at its end for the new empty rule. Returns a
// pointer to the new empty rule.
//
// This function intitalizes all the data in the returned rule to NULL
// or 0 including the nested arrays. It uses of the memset() to
// quickly initialize the entire rule_t struct to 0's. This is
// possible due to the nested arrays being within the rule_t rather
// than pointers to other blocks of memory which means a single
// memset() call will suffice.
// 
// CAUTION: Calling this function MAY invalidate any pointers to
// existing rules as the array that houses the rules may move.
// This sequence is dangerous:
//   rule_t *rule  = bake_target_rule(bake, "sometarget");
//   rule_t *empty = bake_add_empty_rule(bake);
//   rule may now point to de-allocated memory

int bake_add_implicit_rules(bake_t *bake);
// Iterate over all rules appending implicit rules for any dependency
// that is not an explicit target. New rules added in this way are
// marked with the RULE_IMPLICIT_BIT. The number of new rules added is
// returned.  
//
// Situations where a program artifact has a source file dependency
// often occur such as in:
// ------------------------------------------------------------
// progA : src1.o src2.o           # EXPLICIT RULE 1
//         gcc src1.o src2.o
//
// src1.o : src1.c                 # EXPLICIT RULE 2
//         gcc -c src1.c
//
// src2.o : src2.c                 # EXPLICIT RULE 3
//         gcc -c src2.c
// ------------------------------------------------------------
// This would create an irregular rules array which would complicate
// the recursive traversal of the DAG data structure. Instead,
// implicit rules are added for the .c files here which need to exist
// to make the overall data structure look like this:
// ------------------------------------------------------------
// progA : src1.o src2.o           # EXPLICIT RULE 1
//         gcc src1.o src2.o
//
// src1.o : src1.c                 # EXPLICIT RULE 2
//         gcc -c src1.c
//
// src2.o : src2.c                 # EXPLICIT RULE 3
//         gcc -c src2.c
//
// src1.c :                        # IMPLICIT RULE 4
//
// src2.c :                        # IMPLICIT RULE 5
// ------------------------------------------------------------
// The Implicit rules are added at the end and are automatically
// satisfied so long as the Target files exist.
//
// CAUTION: Since bake->rules[] may expand, care must be taken when
// referencing rules in this function to avoid inadvertently derefing
// a pointer to free()'d memory.

bake_t *bake_create_from_file(char *fname);
// parse file and create a bakefile from it

void bake_free(bake_t *bake);
// De-allocates memory associated with a bake_t

void bake_show_cmd(cmd_t *cmd, int ind);
// print a formatted version of cmd_t for testing / debugging

void bake_show_rule(rule_t *rule, int ind);
// print a formatted version of a rule_t for testing / debugging

void bake_show_bake(bake_t *bake, int ind);
// print a formatted version of a bake_t for testing / debugging

  1: # Demonstration of bake 
  2: >> cd p4-code
  3: 
  4: >> make bake
  5: gcc -Wall -Wno-comment -Werror -g -Wno-format-security -c bake_funcs.c
  6: gcc -Wall -Wno-comment -Werror -g -Wno-format-security -c bake_main.c
  7: gcc -Wall -Wno-comment -Werror -g -Wno-format-security -c bake_util.c
  8: gcc -Wall -Wno-comment -Werror -g -Wno-format-security -o bake bake_funcs.o bake_main.o bake_util.o
  9: 
 10: >> cd test_data12
 11: 
 12: >> cat Bakefile1                          # show a sample Bakefile
 13: # this is a comment
 14: 
 15: hello : hello.c
 16:       gcc -o hello hello.c
 17: 
 18: # this is the end of the Bakefile
 19: 
 20: >> ../bake -f Bakefile1                   # use bake to build the targets
 21: bake: updating 'hello' via 1 command(s)
 22: gcc -o hello hello.c 
 23: bake complete, 1 update(s) performed
 24: 
 25: >> ./hello                                # run the built program
 26: Hello world!
 27: 
 28: >> ../bake -f Bakefile1                   # build again but there's no action needed
 29: bake: file 'hello' is up to date
 30: 
 31: >> rm hello                               # delete hello program
 32: 
 33: >> cp Bakefile1 Bakefile                  # copy to the default name 'Bakefile'
 34: 
 35: >> ../bake                                # build using default 'Bakefile'
 36: bake: updating 'hello' via 1 command(s)
 37: gcc -o hello hello.c 
 38: bake complete, 1 update(s) performed
 39: 
 40: >> ../bake                                # again, rebuilding need take no action
 41: bake: file 'hello' is up to date
 42: 
 43: >> cat Bakefile3                          # show a more complex Bakefile
 44: # this is a leading comment
 45: 
 46: # this target uses the program that is built
 47: # and runs it printing messages around it
 48: demo : hello bye
 49: 	@ echo Running programs
 50: 	./hello
 51: 	./bye
 52: 	@ echo Done running programs
 53: 
 54: all : hello bye
 55: 
 56: # this is program 1 / 2
 57: hello : hello.o
 58: 	gcc -o hello hello.o
 59: 
 60: hello.o : hello.c
 61: 	gcc -c hello.c
 62: 
 63: # this is program 2 / 2
 64: bye : bye.o
 65: 	gcc -o bye bye.o
 66: 
 67: bye.o : bye.c
 68: 	gcc -c bye.c
 69: 
 70: # this target removes built files
 71: clean :
 72: 	rm -f hello.o bye.o hello bye
 73: 
 74: # END OF THE Bakefile3
 75: 
 76: >> ../bake -f Bakefile3 clean             # clean up any targets that exist
 77: bake: updating 'clean' via 1 command(s)
 78: rm -f hello.o bye.o hello bye 
 79: bake complete, 1 update(s) performed
 80: 
 81: >> ../bake -f Bakefile3 all               # build with a named target 'all'
 82: bake: updating 'hello.o' via 1 command(s)
 83: gcc -c hello.c 
 84: bake: updating 'hello' via 1 command(s)
 85: gcc -o hello hello.o 
 86: bake: updating 'bye.o' via 1 command(s)
 87: gcc -c bye.c 
 88: bake: updating 'bye' via 1 command(s)
 89: gcc -o bye bye.o 
 90: bake: updating 'all' via 0 command(s)
 91: bake complete, 5 update(s) performed
 92: 
 93: >> ../bake -f Bakefile3                   # build with the default 1st target 'demo'
 94: bake: updating 'demo' via 4 command(s)
 95: Running programs
 96: ./hello 
 97: Hello world!
 98: ./bye 
 99: See you, space cowboy
100: Done running programs
101: bake complete, 1 update(s) performed
102: 
103: >> ../bake -f Bakefile3 clean             # clean up the build
104: bake: updating 'clean' via 1 command(s)
105: rm -f hello.o bye.o hello bye 
106: bake complete, 1 update(s) performed
107: 
108: >> ../bake -f Bakefile3 bye               # build the target 'bye'
109: bake: updating 'bye.o' via 1 command(s)
110: gcc -c bye.c 
111: bake: updating 'bye' via 1 command(s)
112: gcc -o bye bye.o 
113: bake complete, 2 update(s) performed
114: 
115: >> ./bye                                  # run bye program
116: See you, space cowboy
117: 
118: >> ../bake -f Bakefile3 no-target         # show the behavior on a missing target
119: No rule to create target 'no-target'
120: bake failed
121: 
122: >> ../bake -f Bakefile3 all               # build everything
123: bake: updating 'hello.o' via 1 command(s)
124: gcc -c hello.c 
125: bake: updating 'hello' via 1 command(s)
126: gcc -o hello hello.o 
127: bake: updating 'all' via 0 command(s)
128: bake complete, 3 update(s) performed
129: 
130: >> ../bake -f Bakefile3 all               # verify no updates are needed
131: bake: nothing to be done for target 'all'
132: 
133: >> touch -d '-1min' hello hello.o         # change timestamp on program / .o
134: >> touch hello.c                          # to be older than the source file
135: 
136: >> ../bake -f Bakefile3 all               # bake deteces the need to update hello but not bye
137: bake: updating 'hello.o' via 1 command(s)
138: gcc -c hello.c 
139: bake: updating 'hello' via 1 command(s)
140: gcc -o hello hello.o 
141: bake: updating 'all' via 0 command(s)
142: bake complete, 3 update(s) performed

char *slurp_file_efficient(char *fname);
// PROBLEM 1: Uses combination of stat() and read() to efficiently
// read in the entire contents of a file into a malloc()'d block of
// memory, null terminates it (\0). Returns a pointer to the file data
// or NULL if the file could not be opened.

rule_t *bake_target_rule(bake_t *bake, char *targname);
// PROBLEM 1: Searches bake for a rule with a target that equals
// `targname`. If found, returns a pointer to that rule. Otherwise
// returns NULL if no rule with target `targname` exists.
//
// DESIGN NOTE: The curent design makes use of linear search for
// target location, O(rule_count) for each lookup. Maintainting a hash
// table of target->rule key/vals would allow O(1) lookup for rules
// with given target names.

// Macros to deal with bits in flags
#define SET_BIT(flag,   bitmask) (flag |=  bitmask)
#define CLEAR_BIT(flag, bitmask) (flag &= ~bitmask)
#define CHECK_BIT(flag, bitmask) (flag &   bitmask)

if( CHECK_BIT(cmd->cmd_flags, CMD_SILENCE_BIT) ){
  // code for True / is silenced
}
else{
  // code for False / is not silenced
}

void bake_print_cmd(cmd_t *cmd);
// PROBLEM 1: If the SILENCE_BIT is set, does nothing and immediately
// returns. Otherwise, prints the given command token by token. If I/O
// redirects are indicated by the fields of the command, prints the
// after all tokens with "< infile" for input followed by "> outfile"
// if present. This function is used to print out commands in
// bake_execute_cmd().

bake_recursive_func(bake, target):
  check that target is in the rules[] array of bake
  if not, return print "No rule to create target XXX" and return -1 for an error

  Perform some initial checks / actions on the current rule

  Loop over all dependencies calling bake_recursive_func() on them
  Capture the return values of recursive call on each dependency
  Use those returns to potentially take further action on the current target

  return whether or not action was taken on the current target

// PROBLEM 3: Starting at `targname`, recurses down the
// target/dependency DAG setting the UPDATE bit in rule_flags to
// indicate whether a target requires updates. Makes use of the
// CLEAR_BIT(), CHECK_BIT(), and SET_BIT() macros when dealing with
// bit-manipulations. For a given rule, first visits all its
// dependencies to check if they require updates via recursion. Then
// determines if `targname` requires an update. The conditions that
// require an update are described in detail in the program
// specification and shoudl be consulted while implementing this
// function. Returns 1 if target needs to be updated so associated
// rule commands should be run later. Returns 0 if the named target
// does not need to be updated. Prints an error if targname is not
// found and returns -1. If any dependency returns -1, an error
// ocurred lower down the DAG. In case, nothing is printed nothing and
// -1 is returned up the nested recursion.
int bake_set_updates(bake_t *bake, char *targname){
  rule_t *targ_rule = ???;
  if(targ_rule == NULL){
    printf("No rule to create target '%s'\n", targname);
    return -1;
  }

  // clears the update bit to default to false
  CLEAR_BIT(???);

  // special case for implicit targets: enure that they have a file
  // present that is accessible
  if(CHECK_BIT(???)){
    if( access(???)==0 ){                        // use the access() system call to check file exists
      return 0;
    }
    else{                                        // does not exist
      printf("Implicit rule cannot find file '%s'\n", targname);
      return -1;
    }
  }

  // visit each dependency of the target; run ALL iterations for this
  // loop unless a dependency returns an error. ALL depencies should
  // be checked even if one indicates tha the current target needs an
  // update, other depencies may also need updates and should be visited.
  for(int i=0; targ_rule->deps[i]!=NULL; i++){
    int dep_update = ???;            // recursive call to set updates on deeper rules
    if(dep_update == -1){            // dep check failed
      return -1;                     // note: traditional make checks this case to include target/dep in error message but we won't bother here
    }
    else if(dep_update == 1){        // dep needs update so this target also needs an update
      SET_BIT(???);
    }
    else if( ??? ){                  // check both target and dependency file exist, are normal files
      // both target and dep are files that exist, compare timestamps
      // for them as if the dependency file is newer than the target
      // file, an update is required

      // Use stat() to compare timestamps of target file and
      // dependency file; if the dependency is newer than the target,
      // set the update bit for this rule; about 10 lines of code
      ???;
    }
  }

  // special case for rules like 'clean : (nothing)'
  if(access(targname,F_OK)!=0 &&     // no file exists
     targ_rule->cmd_count>0)         // there are commands to run
  {
    SET_BIT(targ_rule->rule_flags, RULE_UPDATE_BIT); // update target
  }

  // return 1 if the UPDATE bit is set and 0 otherwie
  return ???;
}

program : prog.o
	gcc -o program prog.o

prog.o : prog.c
	gcc -c prog.c

all : prog1 prog2


prog1 : x.o y.o
	gcc -o prog1 x.o y.o

prog2 : x.o z.o
	gcc -o prog2 x.o z.o

x.o : x.c
	gcc -c x.c

y.o : y.c
	gcc -c y.c

z.o : z.c
	gcc -c z.c

>> ../bake
bake: updating 'x.o' via 1 command(s)
gcc -c x.c 
bake: updating 'y.o' via 1 command(s)
gcc -c y.c 
bake: updating 'prog1' via 1 command(s)
gcc -o prog1 x.o y.o 
bake: updating 'z.o' via 1 command(s)
gcc -c z.c 
bake: updating 'prog2' via 1 command(s)
gcc -o prog2 x.o z.o 
bake: updating 'all' via 0 command(s)
bake complete, 6 update(s) performed

int bake_cmd_postprocess(bake_t *bake, cmd_t *cmd);
// PROBLEM 4: Examines cmd->tokens to set cmd->flags and a few other
// fields. Used to post-process the raw tokens of a command. Likely
// uses the utility function array_shift() to ease the re-arrangment
// of arrays.
// 
// 1. If tokens[0] = "@", eliminates this token by shifting all tokens
// over and sets the SILENCED bit
// 
// 2. If tokens[i] = "<", input redirection is desired; if tokens[i+1]
// is not NULL, returns -1. Otherwise sets the INPREDI bit and
// input_redirect field to tokens[i+1]. Then shifts all tokens over to
// eliminate tokens[i] and tokens[i+1].
// 
// 3. If tokens[i] = ">", output redirection is desired and performs
// similar operations to #2 with the OUTREDI flag and output_redirect
// fields.
//
// Correctly handles any order of "< input" / "> output" and other
// tokens (ex: output redirection may appear first followed by normal
// tokens followed by input redirection)
// 
// If multiple "<" or ">" tokens appear, the behavior of this function
// is unspecified: it may return an error, segfault, or behave randomly.
// 
// Returns 0 on succesful completion.
//
// DESIGN NOTE: This function must be called prior to any commands
// being run. The ideal location is during parsing to modify commands
// as a bake_t structure is built. However, this functionality is
// separated out to enable future functionality such as variable
// substitution to be added to commands and tested separately from
// parsing. Any additional context needed for such things will be part
// of the 'bake' parameter (e.g. may contain a map of variable
// names/values for substitutions).

prog : dep1.c dep2.c
	cat dep1.c dep2.c > deps.c        # cmd0
	@ echo Counting lines in deps.c   # cmd1
	wc -l < deps.c                    # cmd2
	gcc -o prog deps.c                # cmd3

int bake_check_cycles(bake_t *bake, char *targname, int do_print);
// PROBLEM 5 MAKEUP: Analyzes `bake` starting at targname to
// deteremine if any cycles are present which would create problems
// completing a build: if targA depends on targB depends an targA, a
// cyclcil dependency exists and could not be fulfilled.  Returns 1 if
// a cycle is present, 0 if no cycle is present, and -1 if an error
// occurs such as not finding a needed target.
//
// If do_print is non-zero, prints out a message like:
// 
//   ERROR Cyclic Dependency detected:
//   fileA.txt -> fileB.txt -> fileC.txt -> fileA.txt
// 
// where the first line is always identical and the second line shows
// the path from the initial target through a cycle. Implementations
// assume that these messages will fit in a 2048-byte array and have
// undefined behavior if the message is larger.
//
// NOTES: This function needs to initiate a recursive descent into
// `bake` via a helper function which does the brunt of the work.
// This helper function may be defined in whatever way with whatever
// prototype is convenient. Global variables may be used to help
// generate cycle message BUT implementations with pride will find
// ways to avoid the use of global variables.