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.

This is only the second term the assignment is being offered, so the only empirical data of how long students took to complete the assignment is from the inaugural offering: approximately 20 hours. Our intent is that it will be no more intensive in terms of code writing than Assignment 3, but we expect it may be more challenging to get started on Parts 2 and 3 because of the learning curve to understand the inner workings of an initially unfamiliar code base.

Rules

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

There is no "challenge" portion for this 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 above:

In all three implementations, neither the root nor any other directory will be unnamed, in order to avoid 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 each faulty implementation by debugging the client program using gdb, and will also report a transcript of a gdb session that appropriately shows how the debugger can identify the location of the bug.

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 will 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, child2 == NULL. */
         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

Because you will submit not only a diagnosis of the bug's location, but also a transcript of a reasonable gdb session demonstrating the discovery, you will need to record your debugging session.

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. We will expect you to submit a curated-but-representative version of the contents of each of these files for Part 1. If you are curious about gdb logging options 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 and ensure you have a gdb session transcript that is representative of the exploratory-but-structured nature of tracking down the bug.

Once you have identified and logged all the given buggy implementations, 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 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. See the provided checkerDT.h for the specification.

To get you started, you are 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, 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, implementation, etc. to better meet the goals from the Modularity lecture. You will enter this in the appropriate place in the readme.

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 DT 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, changing DT code where the invariants no longer work for the new expansion, etc.

While this could end up working, 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:

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. Aim for strong cohesion and weak coupling, and ensure that there are no violations of encapsulation assumed.

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.

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 will refine this Makefile as you refine your program design.

Your Makefile must:

Step 3.4: Compose and Test Your New 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 method is now split out into a directory version and a file version. In addition, there are methods to manipulate a file's contents, and a new FT_stat method that will allow a client to access metadata about a node in the File Tree.

Note: your implementation of the FT_toString method must maintain the same format from the corresponding BDT_toString and DT_toString methods. In dealing with the new features, it adds the 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 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. 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.

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.

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 you must submit your gdb transcripts.

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 (Be sure you get them all!) and the Makefile that uses them to build the ft executable out of ft_client.c. There is no need to submit ft.h, nor any provided or expanded client code.

You must submit the 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.