Learning goals

You will learn or practice how to:

1. Practice writing programs with linked lists.
2. Write programs using more complex data structures (beyond the cannonical linked list and BST).
3. Use union and enum types.
4. Write programs that use dynamic memory (malloc(…))
5. Debug code that uses dynamic memory (malloc(…))
6. Parse strings
7. Apply test-driven development (TDD).

Overview

This is part 2 of a 2-part sequence in which you will create a decoder for the JSON data format.

JSON is a file format for exchanging hierarchical data between programs, often written in different programming languages and/or on different computers. In web programming, this allows a server application written in any language (e.g., Python or even C) to pass complex structures of information to the user's browser, which then renders it.

A JSON string may represent a number, a string, or a list. (In this context, when we say “list”, we mean a linked list.) Here are some examples:

type	json	data
number	10	10
string	"ten"	"ten"
list	[2, 6, 4]

Linked lists

As in C, whitespace is ignored (except within a string). Thus, the following are all equivalent.

type	json	data
list	[2, 6, 4]
list	[2, 6, "four"]
list	[2, [3, "+", 3], "four"]

Getting Started on HW12

1. Implement print_element(…) just enough to support integers.
2. Test print_element(…). (This should be easy to test.)
3. Submit.
4. Implement parse_element(…) just enough to support integers.
5. Test parse_element(…). (This should be trivial.)
6. Submit.
7. Extend print_element(…) so that it supports strings, too.
8. Test print_element(…). (Again, this should be easy.)
9. Submit.
10. Extend parse_element(…) to support strings.
11. Test parse_element(…). (Again, easy, but make sure it's perfect.)
12. Submit.
13. Implement parse_list(…).
    1. Create a trivial test (e.g., []).
    2. Implement just enough of parse_list(…) so that it passes your trivial test (functionality only). It should fail all other tests with linked lists.
    3. Extend free_element(…) so that your parse_list(…) tests work without any memory leaks (e.g., passes Valgrind).
    4. Add another simple test (e.g., [0]).
    5. Implement just enough to pass your two list tests so far.
    6. Add another simple test (e.g., ["a"]).
    7. Implement just enough to pass your three list tests so far.
    8. Add a test with multiple integers as list items (e.g., [1, 2]).
    9. Implement just enough to pass your tests so far.
    10. Add a test with multiple strings as list items (e.g., ["A", "B"]).
    11. You shouldn't need to add any code for this, but make sure it works 100% before you proceed.
    12. Add a test with an empty list as a list item (e.g., [[]]).
    13. Implement just enough to pass your tests so far.
    14. Add a test with a non-empty list as a list item (e.g., [[1]]).
    15. Implement just enough to pass your tests so far.
    16. Add a few more tests with gradually increasing complexity (e.g., [[1, 2]], [1, [2, 3], 4], [[1, 2], [3, 4], []]).
    17. Test as needed. Get things perfect—including memory (Valgrind) and test coverage (gcov)—and submit at every stage.
14. Test error cases. Make sure parse_element(…), parse_int(…), parse_string(…), and parse_list(…) return false for incorrect input.
15. Test that there are no memory leaks, even for incorrect input.

How much work is this?

This assignment will only feasible if you are disciplined in the way you build it. If you try to build it all at once, success is extremely unlikely.

Instructor's solution json.c is 69 sloc for HW12 and 127 sloc for the two halves together. That code is tight, but defensible (meets code quality standards, and uses no methods or language features we haven't covered).

Requirements

Submit

To submit HW12 from within your hw12 directory, type 264submit HW12 json.c json.h test_json.c expected.txt miniunit.h clog.h Makefile

If your code does not depend on miniunit.h or clog.h, those may be omitted. Your json.h will most likely be identical to the starter. Makefile will not be checked, but including it may help in case we need to do any troubleshooting.

Pre-tester ●

The pre-tester for HW12 has been released and is ready to use.

Q&A

1. How can I structure my tests?

   Here's a start. (We may add to this at some point.)

   // OK TO COPY / ADAPT this snippet---but ONLY if you understand it completely.
   // ⚠ Do not copy blindly.
   // 
   // This test is nowhere near adequate on its own.  It is provided to illustrate how to
   // use helper functions to streamline your test code.
   
   #include <stdio.h>
   #include <stdlib.h>
   #include "json.h"
   #include "miniunit.h"
   
   int _test_parse_int_valid() {
     mu_start();
     //──────────────────────────────────────────────────────
     int   result;  // will be initialized in parse_int(…)
     char* input = "0";
     char* pos = input;
     bool is_success = parse_int(&result, &pos);
     mu_check(is_success);   // because the input is valid
     mu_check(pos == input + 1);
     mu_check(result == 0);
     //──────────────────────────────────────────────────────
     mu_end();
   }
   
   int _test_parse_int_invalid() {
     mu_start();
     //──────────────────────────────────────────────────────
     int   result;  // will be initialized in parse_int(…)
     char* input = "A";
     char* pos = input;
     bool is_success = parse_int(&result, &pos);
     mu_check(!is_success);  // because the input is valid
     mu_check(pos == input); // failure should be at the first character in the input
     //──────────────────────────────────────────────────────
     mu_end();
   }
   
   int main(int argc, char* argv[]) {
     mu_run(_test_parse_int_valid);
     mu_run(_test_parse_int_invalid);
     return EXIT_SUCCESS;
   }
   

2. That's a lot of duplication! Can we make our tests more concise?

   You could use a helper function and a struct type just for testing. You may copy/adapt this code—but only if you understand it completely. ⚠ Do not copy blindly.

   // FANCY way of testing, using a helper function and struct type just for testing.
   //
   // Okay to copy/adapt, but ONLY IF YOU UNDERSTAND THIS CODE COMPLETELY.
   // ⚠ Do not copy blindly.
   
   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   #include "json.h"
   #include "miniunit.h"
   
   typedef struct {
       bool is_success;
       union {  // anonymous union (C11)
           Element element;
           long int error_idx;
       };
   } ParseResult;
   
   ParseResult _parse_json(char* s) {
       Element element;  // Not initialized because parse_element(…) *must* do so.
       char* pos = s;
       bool is_success = parse_element(&element, &pos);
       if(is_success) {
           return (ParseResult) { .is_success = is_success, .element = element };
       }
       else {
           return (ParseResult) { .is_success = is_success, .error_idx = pos - s };
       }
   }
   
   int _test_int() {
       mu_start();
       //────────────────────
       ParseResult result = _parse_json("0");
       mu_check(result.is_success);
       if(result.is_success) {
           mu_check(result.element.type == ELEMENT_INT);
           mu_check(result.element.as_int == 0);
           free_element(result.element);  // should do nothing
       }
       //────────────────────
       mu_end();
   }
   
   
   int _test_string() {
       mu_start();
       //────────────────────
       result = _parse_json("\"abc\"");
       mu_check(result.is_success);
       if(result.is_success) {
           mu_check(result.element.type == ELEMENT_STRING);
           mu_check(strcmp(result.element.as_string, "abc") == 0);
           mu_check(strlen(result.element.as_string) == 3);
           free_element(result.element);
       }
       //────────────────────
       mu_end();
   }
   
   int _test_list_of_ints() {
       mu_start();
       //────────────────────
       ParseResult result = _parse_json("[1, 2]");
       mu_check(result.is_success);
       if(result.is_success) {
           mu_check(result.element.type == ELEMENT_LIST);
           mu_check(result.element.as_list != NULL);
           mu_check(result.element.as_list -> element.as_int == 1);
           mu_check(result.element.as_list -> element.type == ELEMENT_INT);
           mu_check(result.element.as_list -> next != NULL);
           mu_check(result.element.as_list -> next -> element.type == ELEMENT_INT);
           mu_check(result.element.as_list -> next -> element.as_int == 2);
           free_element(result.element);
       }
       //────────────────────
       mu_end();
   }
   
   int main(int argc, char* argv[]) {
       mu_run(_test_int);
       mu_run(_test_string);
       mu_run(_test_list_of_ints);
       return EXIT_SUCCESS;
   }
   

   ⚠ If you do not understand this code, do not use it.

3. What should be the value of *a_pos after parse_▒▒▒(…) returns?

   _____________________________________________
   # EXAMPLE #1
   
   INPUT:
   
       123
   
   BEFORE we call parse_int(…):
   
       123
       ↑
       *a_pos
   
   RETURN value from parse_int(…):
   
       true
   
   After parse_int(…) returns:
   
       123
          ↑
          *a_pos refers to null terminator just
           after the integer literal.
   
       element.type   == ELEMENT_INT
       element.as_int == 123
   
   _____________________________________________
   # EXAMPLE #2
   
   INPUT:
   
       123ABC
   
   BEFORE we call parse_int(…):
   
       123ABC
       ↑
       *a_pos
   
   RETURN value from parse_int(…):
   
       true
   
   After parse_int(…) returns:
   
       123ABC
          ↑
          *a_pos refers to the non-digit character
           after the integer literal.
   
       element.type   == ELEMENT_INT
       element.as_int == 123
   
   _____________________________________________
   # EXAMPLE #3
   
   INPUT:
   
       -A1
   
   BEFORE we call parse_int(…):
   
       -A1
       ↑
       *a_pos
   
   RETURN value from parse_int(…):
   
       false
   
   After parse_int(…) returns:
   
       -A1
        ↑
        *a_pos refers first character that informed
         us this cannot be an integer literal.
   
       element.type   == (don't care)
       element.as_int == (don't care)

4. What does the output of print_element(…) look like?

   It's just the inverse operation to parse_element(…).
   parse_element(…) takes JSON as input.
   print_element(…) prints JSON as output.
   If you were to parse the output of print_element(…) with parse_element(…) you should get an equivalent object.
   If you parse a JSON string and then print it again, you should get an equivalent string.
   If you're looking for concrete examples, just look at any example of input to parse_element(…) (except for the trailing characters). There are several at the top of this assignment description page.

5. The specification says we don't have to handle escape sequences, but then it mentions escape sequences. Do we parse escape sequences or don't we? How do we handle backslash?

   We use C escape codes to make C string literals containing certain characters (e.g., double-quote, newline, etc.) in our C code.
   You don't have to parse JSON escape codes. Unless you are doing the escape sequence bonus, just treat a backslash like any other character.
   Here's an example to illustrate the distinction:

   #include <stdlib.h>
   #include <assert.h>
   #include <string.h>
   #include <stdio.h>
   #include "json.h"
   
   int main(int argc, char* argv[]) {
       Element element;   // 'element' will be initialized inside parse_element(…)
   
       // C escape codes used to create a C string literal containing double quotes
       char* json_input = "\"A\""; // same as: {'\"', 'A', '\"'}
       char* pos = json_input;
       assert(strlen(json_input) == 3);
       parse_element(&element, &pos);
       printf(">>>|%s|<<<\n", element.as_string);
       // Output:
       // >>>|A|<<<
   
       // JSON escape codes
       json_input = "\"A\\nB\"";  // same as: {'\"', 'A', '\\', 'n', 'B', '\"'}
       assert(strlen(json_input) == 5);
       pos  = json_input;
       parse_element(&element, &pos);
       printf(">>>|%s|<<<\n", element.as_string);
       // Output:
       // >>>|A\nB|<<<
   
       // Output: (with escape code bonus)
       // >>>|A
       // B|<<<
   
       // Note: strlen(…) does not count the null terminator
   
       return EXIT_SUCCESS;
   }
   

6. Should the double quotes be stored in memory?

   No. The double quotes are part of the JSON syntax.
   This is just like how in C, when you define a string like this:

   char s[] = "abc";
   

   … the double quotes are not stored in memory.

7. How much code should I end up with?

   Here's a screenshot of the instructor's solution. The parts that had to be added to support lists (i.e., HW12) are highlighted in yellow.
   

Updates