ooad1-8  Exercise 2: Finding the Holes in a State Table
===========================================================

ex2.py (Python 3.14):

  """Exercise 2: find the holes in a state table by analysis, not by reading it.

  The table is the life of a physical COPY of a book. It contains two mistakes (both are missing rows).
  Two different checks are needed, because they are different kinds of mistake.
  """
  from collections import deque

  TABLE = [
      ("Available", "lend", "OnLoan"),
      ("OnLoan", "return_ok", "Available"),
      ("OnLoan", "return_for_hold", "Held"),
      ("Available", "withdraw", "Withdrawn"),
      ("OnLoan", "report_lost", "Lost"),
      ("Held", "collect", "OnLoan"),
      ("Available", "send_for_repair", "Repair"),
  ]
  INITIAL = "Available"
  EXPECTED_FINAL = {"Withdrawn", "Lost"}
  WAITING_FOR_A_PERSON = {"Held"}              # domain knowledge: the library waits here until a member turns up
  TIMEOUT_EVENTS = {"hold_expired"}


  def reachable(table, start):
      seen, queue = {start}, deque([start])
      while queue:
          s = queue.popleft()
          for src, _, dst in table:
              if src == s and dst not in seen:
                  seen.add(dst)
                  queue.append(dst)
      return seen


  def analyse(table):
      states = {s for s, _, _ in table} | {d for _, _, d in table}
      print("states:", sorted(states))
      print("check 1, unreachable from", INITIAL + ":", sorted(states - reachable(table, INITIAL)) or "none")
      traps = [s for s in sorted(states) if s != INITIAL and s not in EXPECTED_FINAL and INITIAL not in reachable(table, s)]
      print("check 1, trap states (can never get back to Available, and not an intended end):", traps or "none")
      missing_timeout = [s for s in sorted(WAITING_FOR_A_PERSON)
                         if not any(src == s and ev in TIMEOUT_EVENTS for src, ev, _ in table)]
      print("check 2, states that wait for a person but have no timeout transition:", missing_timeout or "none")


  print("== table as given")
  analyse(TABLE)
  fixed = TABLE + [("Held", "hold_expired", "Available"), ("Repair", "repaired", "Available")]
  print()
  print("== with the two missing rows added")
  analyse(fixed)

Run with:  py ex2.py

Output:

  == table as given
  states: ['Available', 'Held', 'Lost', 'OnLoan', 'Repair', 'Withdrawn']
  check 1, unreachable from Available: none
  check 1, trap states (can never get back to Available, and not an intended end): ['Repair']
  check 2, states that wait for a person but have no timeout transition: ['Held']

  == with the two missing rows added
  states: ['Available', 'Held', 'Lost', 'OnLoan', 'Repair', 'Withdrawn']
  check 1, unreachable from Available: none
  check 1, trap states (can never get back to Available, and not an intended end): none
  check 2, states that wait for a person but have no timeout transition: none

THE TWO MISTAKES, AND WHY ONE CHECK CANNOT FIND BOTH
  Missing row 1: Repair has no way out. Check 1 finds it: from Repair, no path leads back to Available, and Repair is not an intended final state. This is a structural problem in the graph.
  Missing row 2: Held has no timeout. Check 1 does NOT find it, because a Held copy can still leave by being collected (Held, collect, OnLoan) and then returned, so Available is reachable from Held. What is missing is behaviour for the case where nobody comes. That needs domain knowledge: "a state where the library waits for a person must have a timeout". Check 2 encodes that rule (it needs the list of waiting states and the names of the timeout events).
So reachability is necessary but not sufficient. Graph checks find structure; rules from the domain find missing behaviour.

WHY THIS WORKS AS AN ANSWER
---------------------------
After adding the two rows (Held, hold_expired, Available) and (Repair, repaired, Available), both checks are clean. The point to take away is that the analysis found one of two problems on its own, and that a check you have never seen fail on a known hole is not a check you can rely on. (My first draft of this exercise claimed check 1 would find both. Running it showed otherwise.)