Info Schedule Assignments A4 Policies Canvas Ed ☰

Assignment 4: Directory and File Tree Abstract Objects

Purpose

The purpose of this assignment is to increase your experience with the following important software engineering fundamentals:

It also will give you the opportunity to gain more experience with the Linux operating system and the GNU programming tools, especially bash, gdb, and make.

Part 1 consists of no code writing, but will have lots of code reading. Part 2 consists of some additional reading, (hopefully) some deep thinking about invariants, and some code writing. Part 3 consists of (hopefully) some practical thinking about design decisions and (potentially, but not necessarily) lots of code writing.

As fair warning, we expect it may be more challenging to get started on this assignment than your assignments thus far because of the learning curve to understand the inner workings of an initially unfamiliar codebase.

This is only the third term the assignment is being offered, so it is changing term-to-term more than other assignments do. Thus, while we can offer the reported average times taken on the assignment for the two inaugural offerings (22 and 26 hours, respectively), these may not be as reflective as they are for other assignments.

Rules

You may work with one partner on this assignment. You are not required to work with a partner, but we strongly prefer and suggest that you do. Your preceptor will help you with your partner search if you so desire.

There is no "challenge" portion for this assignment.

There are two small extra credit items in Part 1. These are completely optional, so if you don't attempt them you can still earn 100% on the assignment.

Background

As you learned in COS 126, a tree is a linked data structure that represents a hierarchical organization of data. There is exactly one node with no incoming links, which we call the root of the tree. There is a unique path from the root to every other node in the tree. Every other node in the tree has exactly one incoming link (from its parent). A node with no outgoing links (and thus no children) is called a leaf of the tree.

As you learned earlier in this course, the Linux file system is structured as a tree. There is one root directory, technically with no name but colloquially called / , that serves as the ancestor of all other directories in the directory hierarchy. Both directories and files may be leaves of the tree, and nodes that are not leaves may have either or both of directories and files as children. Each node in the hierarchy has a canonical name (absolute path or full path) derived from an enumeration of the nodes visited traveling from the root directory to that node, delimited by slashes. As an example, /usr/bin/ls describes all four nodes visited in reaching the ls binary executable: the unnamed directory that is the tree's root, the usr directory that is a child of the root, the bin directory that is a child of usr, and the ls file leaf that is a child of bin.

In this assignment you will be working with three different tree data structures, each of which represents an increasingly complicated file system hierarchy, eventually achieving the full description from the first paragraph above:

As a simplification, in all three implementations, neither the root nor any other directory will be unnamed. This avoids complications with empty strings within paths. Thus no absolute path may have multiple slash delimiters in a row (i.e., a/b/c would be a valid full path and /a//b/c would not be for two different reasons, unlike in Linux).

Your Task

There are three parts to this assignment, corresponding to the three tree data structures listed above.

In Part 1, you are given object files for a series of faulty Binary Directory Tree implementations, as well as for a correct implementation. You are also given the source for a minimalist BDT client that exhibits errors when run after building with any of the faulty implementations. You will locate the bugs in several faulty implementation by debugging the client program using gdb. You also have the extra credit opportunity to reason about the debugging process of two more faulty implementations, without actually having to debug them.

In Part 2, you are given object files for a series of faulty Directory Tree implementations, as well as the source for a correct implementation and a minimalist DT client. This time the client (a) does not necessarily exhibit errors when built with the faulty implementations, and (b) the object files were not configured to facilitate stepping through the code in those files while debugging in gdb. So instead of the approach from Part 1, here you will write an internal validation module that will verify the validity of the data structure such that it correctly identifies the invalid state of the data structure and terminates the program when checked at the leading and trailing edges of each API function.

In Part 3, you are given an expanded API that is appropriate for hierarchies that contain both directories and files. You will implement the File Tree interface, using the Directory Tree implementation from Part 2 as a jumping off point. But the given Part 2 code may not have made the best design choices! Thus, along the way, you may need to reassess the program design and modularity for your expanded version.

The Given Files

Part 1

Part 2

Part 3

The Procedure

As you have been doing thus far in the course, you may write code in whatever development environment and on whatever computer you see fit.

In this assignment, we provide pre-built .o files that contain various correct and buggy solutions. These were built using gcc217 on armlab, so you will have to do the testing and debugging there.

We continue to encourage you to use the model of committing frequently in GitHub, pushing to the cloud, then pulling down the updates into a repository on armlab for testing, debugging, critiquing. When you are finished, pull down your final version to armlab to issue the appropriate submit command(s).

Step 0.1: Preliminaries

As with the other assignments, you will create your own repository, separate from ours, that has the same contents as ours. As a reminder, you can follow these procedures to import your own version of our contents into your GitHub account, or follow the Setup Step 5 from the Git and GitHub Primer document from the first precept.

Note, though, that only one partner should do this. After having done so, that partner should continue with Setup Step 6. Only after that will the other partner obtain a working copy, by executing a (regular, non-bare) clone of the first partner's repository.

The COS 217 assignment repository for this assignment is:
https://github.com/COS217/DirectoryFileTrees

Step 1.1: Examine the BDT Interface and Client

Study the two given source files, bdt.h and bdt_client.c, to learn about what operations a BDT supports and how they might be called by a client of the BDT module. The client program is not a true external client of the module, but instead a test client that validates (some of) the expected behavior of the module.

The BDT internal implementation is not revealed to the interface or the client -- this is good data structure design! However, to get you started, we will tell you that the BDT is implemented as an Abstract Object with the following static state variables: 

      /* a flag for if it is in an initialized state (TRUE) or not (FALSE) */
      static boolean isInitialized;

      /* a pointer to the root node in the hierarchy */
      static Node_T root;

      /* a counter of the number of nodes in the hierarchy */
      static size_t count;
where Node_T is a pointer to one of these structures: 
      struct node {
         /* the absolute path of the directory */
         char* path;
      
         /* links to child directories, each NULL if there is no such child.
         invariant: if child1 == NULL, then child2 == NULL as well. */
         Node_T child1, child2;
      
         /* link to this directory's parent directory, or NULL if the root */
         Node_T parent;
      };

Step 1.2: Build the Buggy BDTs

Using the Makefile you can issue all these commands to build the programs from the client's C source, a library's C source, and the good and bad implementations' object code: 

      $ make
      gcc217 -g -c dynarray.c
      gcc217 -g -c bdt_client.c
      gcc217 -g dynarray.o bdtGood.o bdt_client.o -o bdtGood
      gcc217 -g dynarray.o bdtBad1.o bdt_client.o -o bdtBad1
      gcc217 -g dynarray.o bdtBad2.o bdt_client.o -o bdtBad2
      gcc217 -g dynarray.o bdtBad3.o bdt_client.o -o bdtBad3
      gcc217 -g dynarray.o bdtBad4.o bdt_client.o -o bdtBad4
      gcc217 -g dynarray.o bdtBad5.o bdt_client.o -o bdtBad5

Step 1.3: Run the Buggy BDTs

Each of the buggy implementations has a simple-but-serious bug that will manifest itself in either a failed assert in the client, a crash or other serious problem, or output that diverges from that of bdtGood. Run each of the programs to observe the behavior: 

      $ ./bdtGood
      $ ./bdtBad1
      ...

Step 1.4: Learn How to Log gdb Sessions (optional)

As you perform deeper dives into debugging in gdb, you may find it useful to keep track of previous forays into the code for what examinations of the runtime state you've made, what commands you experimented with and eventually mastered, etc. gdb provides a reasonable way to keep a record of your debugging session using automatic transcript logging.

To almost fully automate the process of recording your gdb sessions, we will rely on gdb's ability to load a configuration file that contains many commands (much like the .bashrc file that bash loads each time we start a new shell). We will use these configuration files to batch issue a series of commands that turn on logging so that every gdb command you type and the output from that command will be saved in a sensibly named log file.

In the repository, there are configuration files to use when debugging each of the buggy Part 1 implementations (each separately, so that the transcripts from debugging on different implementations are not intermingled). In order to use them, you must issue this as the first command after launching gdb (whether from the command line or from within emacs), where N is the buggy implementation number from 1-5: 

      (gdb) source .gdbinitN
This setup will create and append to ./badN.log (where N is again 1-5) as the log files. You may choose to keep these to remind you of what you've already tried in tracking down the bug, but you are not required to do so — though we do think it can be edifying. If you are curious about further gdb logging options, you can refer to the documentation here.

Step 1.5: Debug the Buggy BDTs

One at a time, conduct one or more gdb sessions to step through the operations that eventually result in an error and explore to home in on the point at which it all goes wrong.

Refer to the gdb guide for tips on how to debug efficiently.

Write the identified bug locations (simply the function is fine, no need to be more granular) in the designated section of the readme.

Once you have identified the bug in each of the required buggy implementations, and perhaps answered the two optional extra credit items, you are done with Part 1.

Step 2.1: Examine the DT Interface, Client, and Given Implementations

Study the given source files, dt.h, dt_client.c. The interface is extremely similar to the BDT interface from part 1 of the assignment, but the client exhibits some of the different behavior of the new data structure (e.g., that a parent can now have more than two children).

Also study the given implementation dtGood.c and nodeGood.c. This implementation is sometimes cryptic and under-documented, making it imperative that you really study it to tease out the design, algorithms, and invariants of Node_T and DT. But you will need to do so in order to construct your internal testing, because the buggy versions share the same internal representation and overall structure. You will also need to have a strong grasp of this implementation to complete the required critique of its design.

Step 2.2: Build the Buggy DTs

Using the Makefile you can issue all these commands to build the programs from the client's C source, a library's C source, and the good and bad implementations' object code: 

      $ make
      gcc217 -g -c dynarray.c
      gcc217 -g -c nodeGood.c
      gcc217 -g -c checkerDT.c
      gcc217 -g -c dtGood.c
      gcc217 -g -c dt_client.c
      gcc217 -g dynarray.o nodeGood.o checkerDT.o dtGood.o dt_client.o -o dtGood
      gcc217 -g dynarray.o nodeBad1a.o checkerDT.o dtBad1a.o dt_client.o -o dtBad1a
      gcc217 -g dynarray.o nodeBad1b.o checkerDT.o dtBad1b.o dt_client.o -o dtBad1b
      gcc217 -g dynarray.o nodeBad2.o checkerDT.o dtBad2.o dt_client.o -o dtBad2
      gcc217 -g dynarray.o nodeBad3.o checkerDT.o dtBad3.o dt_client.o -o dtBad3
      gcc217 -g dynarray.o nodeBad4.o checkerDT.o dtBad4.o dt_client.o -o dtBad4
      gcc217 -g dynarray.o nodeBad5.o checkerDT.o dtBad5.o dt_client.o -o dtBad5
Notice that the Makefile automatically recognizes which files do and do not need to be rebuilt after any changes. This was also the case with the BDTs, however as we accumulate more source files, the partial-build capabilities become more important.

Step 2.3: Run the Buggy DTs

In Step 1.3, each of the buggy implementations had a bug that was client-observable. That isn't the case in this step: while dtBad2 crashes, dtBad3 produces different output, and dtBad5 fails an assert, dtBad4 yields the same behavior from the client as the correct version. Furthermore, trying to debug these with gdb runs into a problem: they were not compiled with -g, so there is no source code associated with the memory locations in the executable. This is a good indication that a developer will be well served taking a different approach to debugging.

Step 2.4: Develop Your Own DT Validation Module

While one option in this situation would be to expand the client to span a broader and more systematic testing suite than its current scattershot series of calls, instead you will approach the problem at a lower level by beefing up the internal testing used in the DT modules.

Each function listed in DT's interface has a call to CheckerDT_isValid at the beginning of its function body and just before each possible return point. Similarly, each function listed in the given node interface that produces a new Node_T for the client or mutates an existing one for the client has a call to CheckerDT_Node_isValid at the function's leading and trailing edges. The implementation of these checker functions should thoroughly exercise checks of every invariant of the data structures' internal representations and their interfaces' stated restrictions.

(What's a data structure invariant? These involve a constrained set of values of individual state variables within the data structure's implementation or well-defined relationships between several state variables' values. For example, in your Assignment 3 SymTable list implementation, if oSymTable->firstNode is NULL, then oSymTable->uCount must be 0; and in your hash table implementation, if the binding for a particular key is found in bucket i, the hash value of that key must be i!)

The provided checkerDT.h gives a specification for the two isValid functions. To get you started, you are also given a few supplied sample tests in checkerDT.c. (This is why dtBad1a and dtBad1b already abort with a correct description of the bug.) In particular, as some of the tests for DT validity require a proper method of traversing the tree, we have provided working scaffolding for this algorithm in checkerDT.c

Our advice is that your checkerDT.c implementation should identify all or nearly all of the buggy DTs' issues before you proceed to the next step. (This isn't a hard prerequisite, it's just that writing more checker tests will further familiarize you with the implementation upon which we assume you will be basing Part 3.)

Step 2.5: Critique Our DT Implementations

In the code given for Part 2, there exist functions that are not used or not used to the best of their abilities, module bloat, questionable naming conventions, etc. Some things were improved between Part 1 and Part 2 (Node_T is implemented with a fully fledged module, not an overgrown struct within another object's module, among other things), but real code you sit down in front of does not typically have the polish of perfect academic examples, and we've represented that here. Give one last look back at the code and offer a critique of how a refactorer could/should clean up the interfaces and implementations to better meet the goals from the Modularity lecture and accord to what we know about good program design and style. You will enter this in the appropriate place in the readme — either paragraph or bulleted list form will be fine.

Step 3.1: Examine the FT Interface and Client

Study the two given source files, ft.h and ft_client.c, to learn about what additional operations an FT supports beyond those from the DT interface, and how they might be called by a client of the FT module. Again, the client program is not a true external client of the module, but instead a test client that validates (some of) the expected behavior of the module.

Step 3.2: Design Modules, Interfaces to Support FT

In Part 3, you will implement the FT interface to further expand the capabilities of a DT to include representing files: the leaves in the tree that have contents associated with them. Your first inclination for doing so might be to rush out and start "hacking" by adding new fields to the Node_T implementation to fit the first idea that comes to mind, making slapdash changes to the DT code where its invariants no longer hold for the new expansion, etc.

While this could end up working -- and indeed, your eventual product will likely end up making some of these changes -- a better software engineering approach is to reconsider the overall design of your program. Modularity is the manifestation of abstraction: a strong program designer understands how to find abstractions in a large program and convey them via a cogent set of modules, each with a sensible interface.

Before you begin coding, consider the answers to these design decision questions (there may be no right answers):

As you answer the questions, you should, for your own benefit, compose a diagram (e.g. a flowchart or a mind map) of the interactions between the modules that you intend to write and/or the internal representations you intend to change for existing modules. Aim for strong cohesion and weak coupling, and ensure that there are no violations of encapsulation built in to the design.

(Aside: this assignment's author was recently on the receiving end of the lamentations of an engineer from a major tech company, who indicated that candidates -- including Princetonians, alack! -- often fail her modularity-focused interview question because they charge into coding instead of drawing out a coherent diagram of the architecture of modules they will be building.)

Your design choices will inform how easy or difficult it will be to complete subsequent steps in Part 3. So do not become wedded to your choices to the point of becoming susceptible to the sunk-cost fallacy: you may have to iterate on your design decisions as you delve into the next steps of actually implementing the FT. The perfect, however, is the enemy of the good -- encouraging deep thoughts about design doesn't mean we want you to never start coding!

Step 3.3: Compose a Makefile

Create a first version of a Makefile that corresponds to the files you have chosen in the previous step. You may have to refine this Makefile as you refine your program design.

Your Makefile must:

Step 3.4: Compose and Test Your New and/or Improved Supporting Modules

Having settled on a set of modules and their interfaces in Step 3.2, you will now implement these modules. As you write the implementation(s), you may find that you are never using some functions from the API, yet you feel as though other useful ones are missing — use this insight to iterate back to Step 3.2 and refine your design choices. (If these are leftover elements from DT, consider also whether this observation applies to the given code from Part 2 as well, and if so whether you should augment your answer from Step 2.5.)

You will want to test each new module, perhaps with a simple test client for your own benefit (that is, you need not submit such a client), before relying on the module as a dependency of a larger build. If you completed an organizational diagram in Step 3.2, it can provide the appropriate order for composing and testing your new modules that minimizes the entanglement of multiple untested modules with each other.

Step 3.5: Implement the FT Interface

The final module that you will implement is the only one with its interface specified for you: the core FT abstract object. The FT interface is very similar to the DT interface, except almost every function is now split out into a directory version and a file version. In addition, there are functions to manipulate a file's contents, and a new FT_stat function that will allow a client to access metadata about a node in the File Tree.

Note: your implementation of the FT_toString function must maintain the same format from the corresponding BDT_toString and DT_toString functions. In dealing with the new features, it adds the ordering requirement specified in the comment in the client that a directory's children should be printed depth first in lexicographic order but with file children listed before directory children.

After you have composed your FT implementation, you can test using the provided reference implementation. You can build the given sampleft.o with the provided test client ft_client.c using the provided Makefile.sampleft, which is named in such a way as not to conflict with your own Makefile. Use the -f Makefile.sampleft option to make in order to specify this file instead of your own Makefile. We encourage you to expand ft_client.c with your own tests, or even to write a FT validation checker module if we have sufficiently convinced you that these are valuable. (If you do the latter, you'll need to name it differently than the module from Part 2 in order to submit it without a naming conflict. CheckerFT would be a natural choice.)

Step 3.6: Critique Your FT Implementation

Critique the code for your new modules using critTer. Each time critTer generates a warning on your code, you must either (1) edit your code to eliminate the warning, or (2) explain your disagreement with the warning in your readme file.

Critique the program consisting of the new modules and the client using splint. Each time splint generates a warning on your code, you must either (1) edit your code to eliminate the warning, or (2) explain your disagreement with the warning in your readme file.

You do not have to explicitly explain away warnings that result solely from your repurposing of the DT code we gave you, but you might consider if those warnings are additional fodder for your comments in Step 2.5.

Step 4.1: Complete the readme File

Edit your copy of the given readme file by answering each question that is expressed therein.

In step 1.5, you should have entered the bug locations from Part 1. If you didn't, do it now.

Also in step 1.5, you were given the opportunity to offer a response to the two optional extra credit items in the readme. We hope you put some thought into them!

In step 2.5, you should have entered your critique and refactoring suggestions from Part 2. If you didn't, do it now.

Step 4.2: Provide Feedback

Provide the instructors with your feedback on the assignment. To do that, issue this command on armlab: 

      FeedbackCOS217.py 4
and answer the questions that it asks. (If you worked with a partner, then when answering the numeric questions, please enter the average of the responses that you and your partner would provide individually.) That command stores its questions and your answers in a file named feedback in your working directory. You need not store it in your repository, though you can.

Note: this portion is particularly helpful for this assignment, given that this is still a "young" assignment relative to the others in this course that have developed and evolved over the course of decades.

Step 4.3: Submit

Submit your work electronically on armlab. If you worked with a partner, then one of the partners must submit all of your team's files, and the other partner must submit none of your team's files.

Your readme file and your source code must contain both your name and your partner's name.

For Part 1 there is no file to submit other than the readme.

For Part 2 you must submit checkerDT.c .

For Part 3 you must submit the .c and .h files for all the modules used to implement the FT interface and build your ft executable, with the exception of the ft.h interface file itself and the ft_client.c client file itself. (Be sure you get them all! Seriously. Go triple-check.)

For Part 3 you also must submit the Makefile that uses all these files to build the ft executable out of ft_client.c.

You must submit the completed readme file and the feedback transcript.

Finally, if you have worked with a partner, you must submit the appropriate .partner file as described on the Policies page: 

      touch netid.partner
      submit 4 netid.partner
where netid is the non-submitting partner's NetID.

Program Style

In part, good program style is defined by the splint and critTer tools, and by the rules given in The Practice of Programming (Kernighan and Pike) as summarized by the Rules of Programming Style document.

The more course-specific style rules listed in the previous assignment specifications also apply, as do these:

This assignment was created by Christopher Moretti and Vikash Modi '23, with input from Xiaoyan Li and Donna Gabai.