cs50/spl

CS50's fork of Eric Roberts' Stanford Portable Library.

spl's Issues

determine how to re-generate docs

Using cppdoc maybe, based on presence of cppdoc.css in existing docs? Ideally we should re-create Eric's template, though. And re-use original images.

scanNumber: xch set but not used

I'm not 100% sure what xch is supposed to represent in this function (tokencanner.c:449) but it is assigned to and then never read from, indicating a possible bug in this function.

Make install bugs

Hey David,
When ran on Ubuntu, there are two bugs with your Makefile, when make install is run.

cp build/lib/{libcs.a,spl.jar} /usr/local/lib/
chmod -R a+r /usr/local/lib/{libcs.a,spl.jar}

Neither of these commands run properly with the {} method of cp/chmod on multiple files. Easy to fix as the user, but I thought I would let you know!

Cheers,
Bill Long

P.S. I am loving my time in the edX cs50!

waitForClick bug

---------- Forwarded message ----------

Looks like this is indeed a bug in SPL.

With GDB I can see that waitForClick() is always reached, but if the mouse was moving at the time waitForClick gets called, a click is processed even with no click.

---------- Forwarded message ----------

After I noticed a bug in a student's program where if they moved the mouse as the ball was hitting the bottom edge, the game wouldn't wait for a click (event though he requested it to) and the ball would reset its location and keep moving (the amount of lives was still correct).

I tried this using the staff's implementation, and the bug was there was well.

Undefined behavior invoked in unittest framework

This is #24 at work. The trace macro uses try/catch and potentially clobbers the variables that it is testing. GCC actually warns about this if you compile with warnings at a higher optimization level than -O0. This occurs 33 times across the library. It was fairly trivial to mark the variables declared in unit tests within the library as volatile (see db1aa2b), but this framework is public (though undocumented), so if a user wanted to write unit tests using it, they would run into this same issue. This also means that removing exceptions from the library would also mean removing the unit tests.

Undefined symbols

One of the changes in the port will be that the library will be dynamically linked rather than statically linked to ensure __attribute__((constructor)) works as intended. Because dynamic linking brings over all the symbols the library exports (while static linking only links symbols that are actually used), this change caught a couple of bugs in the library wherein functions were called, but were never defined. (Enabling warnings also would have caught this though compiling SPL with warnings produces quite a lot of output which may be worth investigating in the future).

In any case, the undefined functions are:

• mapSymbolTable called in newCommandIterator in cmdscan.c on line 167
• freeSymbolTable called in freeCommandScanner in cmdscan.c on line 84
• ignoreSpaces called in newCommandScanner in cmdscan.c on line 77

ensure no memory leaks, bad memory accesses in SDL port

Catching SPL exceptions potentially invokes undefined behavior

Source

Stack unwinding is simulated in exception.{h,c} by utilizing the setjmp and longjmp functions from the C standard library. These functions dynamically create for non-local gotos, allowing control flow to be transferred from one function to an arbitrary location in another.

There functions, while useful, carry a subtle "gotcha". When control flow is transferred, whether or not registers are restored is unspecified (it is undefined in GCC, not sure about clang), meaning the values of non-volatile variables with automatic storage duration that have changed between the setjmp and longjmp calls are unspecified.

Example of the UB:

int foo(int);
void bar(int, int);

int main(void)
{
    int x = 10, y = 5;
   // Do stuff with x and y
    try { // setjmp is called in the expansion of `try`
        x = foo(y); // x is modified
        bar(x,y); // Throws an exception, which calls longjmp
    } catch (ANY) {
         // x might have been in a register but it's value has (maybe) been clobbered
         fprintf(stderr, "The value of x is %d", x); 
    }
}

Recommendation

I don't think that leaving potentially UB-causing constructs in a library designed for students. I would propose removing this feature and refactoring the library to function without it.

update README with Fedora/Ubuntu requirements

Should suffice to install a minimal ISO of each into a Docker image, then try to build SPL with make, see what fails, determine what packages to install via yum or apt-get, then update README.

GWindow can't currently be freed

It seems a GWindow can't currently be freed:

There does seem to be a generic remove function, defined in StanfordCSLib/src/generic.c, right after the generic add function. However, it looks to me like the handling of GWindow by remove is buggy. The relevant branch of remove reads:

   if (endsWith(type, "GWindow")) {
      va_start(args, arg);
      gobj = va_arg(args, GObject);
      va_end(args);
      removeGWindow((GWindow) arg, key);
   }

At this point in the code, key is uninitialized. I believe the intent was to pass gobj to removeGWindow, not key.

tidy Makefile to be consistent with conventions

I reorganized the repo to essentially put everything in c/ and java/ subdirectories, with a top-level Makefilethat builds everything into build/. That way, all a user needs to do is install whatever is inbuild/and can ignore everything else. It remains a to-do to auto-generatebuild/docs`, so for now its in the top-level too.

Would be ideal not to hard-code so much in the Makefile, though?

https://github.com/cs50/spl/blob/master/Makefile

• tidy Makefile
• determine when best to remove build/obj/ (so that once make is done, everything is staged in build/, for make install); right now, make install depends on libcs.a, which is thus depending on obj/ not yet being deleted

refTypeCheck invokes undefined behavior

refTypeCheck in src/ref.c:257 invokes undefined behavior. It declares but does not initialize a pointer and then immediately checks whether it is NULL. Based on the resulting error message, this is likely a typo and the check should instead check the function's first argument for NULL.

Tracking issue for SDL port

Todo:

• GArc (Easy)
• GInteractor (Hard)
• GImage (Easy)
• GRoundRect (Very Easy)
• G3DRect (Unsure, I have some questions about this)
• Key, action and timer events (Medium)
• GTimer (Easy)
• GSound (Easy)
• install target in Makefile (Easy)
• Decide what format the library should take (LLVM bytecode, JS, etc.)
• Graceful error handling on SDL failure (Easy)
• Removing buggy/misleading features (creation of "bst of doubles", exceptions) (Medium, depending on how much of the code relies on these features)
• Decide on which fonts to support

Float comparisons

cmpfn.{c,h} define comparison functions for many types, including floats and doubles. It defines them like so:

int doubleCmpFn(const void *p1, const void *p2) {
   double v1, v2;
   v1 = *((double *) p1);
   v2 = *((double *) p2);
   if (v1 == v2) return 0;
   return (v1 < v2) ? -1 : +1;
}

IEEE floating point numbers should not be compared for equality. (Source). As it currently stands, structures that uses a CompareFn (BST and HashMap for example) are inherently implementation defined. This does not seem suitable for a library with "portable" in its name.

A simple fix would be to change v1==v2 to something like abs(v1 - v2) < DBL_EPSILON, however, this creates a scenario in which one double is, conceptually, both equal to and less/greater than another -- in other words, a partial ordering.

The description and implementation of these functions imply that a CompareFn will produce a total ordering; this is fundamentally incompatible with IEEE floating point numbers, as they are only partially orderable. Consequently, any structures which assume a total ordering (e.g. BST) could still exhibit strange behavior with the epsilon solution.

I would propose two ways of dealing with this. One would be to remove doubleCmpFn and floatCmpFn, and have types that use CompareFns throw an error if they are given floating point numbers. The other would be somewhat more complicated as it would involve creating an additional PartialCompareFn interface and implementing it for types which are partially orderable (a superset of types that are totally orderable). Incidentally this is how ordering is done in the Rust standard library, which exports two traits (somewhat analogous to Java interfaces): Ord and PartialOrd.