Rex Liu

Forty-three courses

uwscrape, a degree planner for Waterloo, and the bug that looked exactly like caution.

On the second day of uwscrape I had a demo I was pretty happy with. It scraped the course catalog, parsed prerequisites into trees, evaluated them against a fake student's transcript, and drew the whole thing as a 3D graph you could fly around in. It covered forty-three courses.

The Faculty of Math has a few hundred. That evening I corrected my roadmap: the demo proved a lot of plumbing and none of the product yet.

The product, once I wrote it down properly, was smaller and harder than the demo. You drag the courses you've taken and the ones you plan to take onto a board. For any course or credential, the tool tells you what you're missing, which alternatives would cover it, and what a course unlocks. Every answer has to come from the calendar, with a link back to the sentence it came from. I kept the 3D graph, demoted to a view of the same data.

The hard part had been sitting under the demo the whole time. Waterloo publishes its calendar through Kuali, and Kuali hands back requirements as rendered HTML: nested lists, each headed by an English sentence. "Complete all of the following." "Complete 1 of the following." "Earned a minimum grade of 60% in each of the following:". The nesting is the structure and the sentences are the logic. Turning that into something a program can evaluate means writing a parser for a language whose grammar is "whatever the person editing the calendar typed that day".

The parser does what you'd expect. Groups become all_of, any_of and choose_k nodes, and leaves become facts a student has or lacks: a course, a course with a minimum grade, a level like 2A, a program. Most sentences fall into a handful of patterns. Some don't. Some program restrictions come in phrasings I'd never seen. Some sentences appear on exactly one course page.

I'd made one decision about those on the very first day, before there was any code, and it shaped everything after it. A sentence the parser can't read is a real record. It goes into the index with its original text and a link, and when the evaluator reaches it, the answer is unknown. The tempting alternatives all resolve the doubt in the tool's favour. Call it satisfied, and a student finds out on enrollment day that they can't take the course. Call it unsatisfied, and the tool quietly hides courses they could take. Drop it, and nobody ever learns the condition existed. I didn't want a planner that guesses on someone else's behalf.

Once a leaf can be unknown, groups have to combine three values instead of two. An all_of with a failed child has failed, whatever else it contains. With no failures but an unknown child, it's unknown. An any_of is the mirror image, and that's where the decision pays for itself: one satisfied alternative settles the group, even with an unreadable sentence sitting right next to it. choose_k gets bounds. Count the children you know are satisfied, then count them again with every unknown assumed satisfied. If the pessimistic count already reaches k, yes. If the optimistic count can't, no. Anything in between, unknown. The all_of and any_of rules are the conjunction and disjunction of Kleene's strong three-valued logic. I got to them from the problem and found out afterwards that Kleene had written them down long before, in Introduction to Metamathematics (1952, §64). The choose_k bounds are the same idea stretched to counting.

On top of the truth values I added a status the student actually sees, because "not satisfied" covers both "you've done two of the three" and "you've done none of it". The evaluator reports satisfied, not_satisfied, partial, unknown, conflict (an antirequisite you've already taken) and not_applicable. partial turned out to be the most useful word in the whole vocabulary. It also turned out to be the best hiding place I could have built for a bug.

CS 246#

After that I pointed the parser at the live catalog and fitted it to what Kuali actually serves, which differs from my demo snapshot in all the small ways you'd expect. A couple of days after that, CS 246 showed partial for a transcript that had met its prerequisites.

The heart of CS 246's rule is a choice between three routes, and that transcript covered one of them. partial is a completely normal answer. A half-finished prerequisite looks exactly like that, and nothing on the screen was malformed. You had to already know CS 246's rule to see that the answer was wrong. When I opened the tree my parser had handed the evaluator, the choice was gone. The three routes sat side by side under an all_of, all three mandatory, and partial was the evaluator's correct answer to the wrong question.

I'd written the parser with two paths. The structural one walks the HTML as a tree, so a <ul> becomes a group and its label decides what kind. The text path is a fallback that flattens the fragment into a string and works from sentences. I'd only let the structural path run when the fragment was exactly one list. Kuali wraps its lists in <div>s:

<div><div><ul><li><span>Complete 1 of the following</span><ul><li>CS 136</li><li>CS 138</li><li>CS 146</li></ul></li></ul></div></div>

So I was sending that to the text path, where my clause filter threw away "Complete 1 of the following" as a sentence with no course codes in it. Dropping "Complete all of the following" is harmless on that path, since all_of is the default container anyway. Dropping "Complete 1 of" removes the only thing that made those courses alternatives. I lost the grade wrapper the same way, so "a minimum grade of 60%" vanished and any completed course counted. One bug made the tool too strict and the other made it too lenient, which is two of my three tempting wrong answers, implemented by accident.

When I sampled courses across CS, MATH, CO, STAT, AMATH and ACTSC, about half had the collapsed choice: CS 240, CS 245, MATH 135, MATH 235. Every one of those had been evaluating the wrong tree, and from the outside caution and wrongness looked identical. The three-valued logic I was proud of had made the failure look like honesty.

I stopped flattening. Wrapper elements are presentation, so I made the parser descend through them until it finds the real list:

func findRootRequirementList(nodes []*html.Node) *html.Node {
	for _, node := range nodes {
		if isListNode(node) {
			return node
		}
		if isTransparentContainer(node) {
			children := filterMeaningfulNodes(elementChildren(node))
			if nested := findRootRequirementList(children); nested != nil {
				return nested
			}
		}
	}
	return nil
}

I gave the grade wrapper its own branch that pushes the threshold down onto every course under it, through nested choices. On the text path, I made a choice sentence merge into the clause that follows it, and if nothing follows, it becomes its own clause and usually lands as an unknown. A visible unknown beats a silent drop, which was my first-day rule all along. I bumped the parser version so the index would rebuild every condition from scratch, and got CS 246 back with its any_of and its 60% thresholds.

The checks I wrote for it assert that CS 246 comes back satisfied for a student whose board says honours mathematics, because the rule has one more condition after the choice. For many of the other courses the checks can't trust the root at all. Next to the choice sits a program-enrollment clause that the parser leaves unread, because of how Kuali serves it, and that honest unknown keeps the root at partial. It looks exactly like the broken ones did, so for those courses the checks assert the status of the choice itself.

That honours-mathematics condition gave CS 246 a second partial the same evening, an honest one this time. My parser reads the condition fine, and a student who hadn't put a program on the board got partial for it even with a whole route covered. So I made the course view stop counting program enrollment at all. A student in another program now sees CS 246 as satisfied and finds out at registration, which is exactly what I'd ruled out on the first day for sentences the parser can't read. Here I chose it on purpose. A course's status is meant to say whether you're ready for it academically, program enrollment is an administrative check that Quest makes at registration anyway, and the view of your progress toward a degree still checks it strictly.

The site is up at uwwoe.fyi.