Practice question · Put in order
Order the steps of debugging a data structure with an invariant checker.
- Fix that operation, which is the one that corrupted the structure
- Write a function that walks the structure and verifies that property
- Call the checker after every operation while reproducing the bug
- Note the first operation after which the checker fails
- Write down, in words, the property the structure must always satisfy
Hints
- A property has to be stated before it can be turned into code.
- The fix belongs to the operation the checker caught, not to whatever read the structure later.
Show the answer
- Write down, in words, the property the structure must always satisfy
- Write a function that walks the structure and verifies that property
- Call the checker after every operation while reproducing the bug
- Note the first operation after which the checker fails
- Fix that operation, which is the one that corrupted the structure
Why
Stating the invariant, coding it, running it after every operation, and stopping at the first failure localises the bug to one operation. Without the checker you would find the damage far downstream, where the visible symptom has nothing to do with the code that caused it.
Practise Debugging Structural Invariants
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Debugging Structural Invariants
- An invariant checker is written, run during development, and deleted before release. What was gained, and…
- Sort each statement about a binary search tree by whether it is an invariant of the structure.
- Select every benefit the lesson attributes to writing an invariant checker.
- An invariant checker is code that verifies a structure's rules and is never called in production. Why is…