Week 3 — Unit Testing
Based on Graphs

3.1Graph Coverage Criteria Applied to Test Code

Control Flow Graph (CFG) kya hai?

CFG ek method ke saare possible executions ko model karta hai. Nodes = statements ya statements ke sequences (basic blocks), edges = ek statement se doosre mein transfer of control. CFG code ka coarse abstraction hai — variables/exact statements ki info drop, sirf control flow retain.

CFG patterns — statement by statement

Running example: Statistics program

// computeStats(int[] numbers)
int length = numbers.length;  sum = 0.0;
for(int i=0; i<length; i++) { sum += numbers[i]; }
med = numbers[length/2];  mean = sum/(double)length;  varsum = 0.0;
for(int i=0; i<length; i++) { varsum += (numbers[i]-mean)*(numbers[i]-mean); }
var = varsum/(length-1);  sd = Math.sqrt(var);
// 4 print statements

3.2Data Flow in Graphs

Ab CFG mein data ki info add karte hain — kahan variable ko value milti hai (def) aur kahan value access hoti hai (use).

• Har node n ke liye def(n), use(n); har edge e ke liye def(e), use(e).
• Programs ke graphs mein edges pe defs typically nahi hote (FSM designs mein edge actions ho sakte hain). Decision predicates ke uses edges pe aate hain — dono outgoing edges (true/false) pe same use set.
• du-pair = pair (l_i, l_j): v defined at l_i, used at l_j.

Notation (assignment mein direct pucha jaata hai)

c-use vs p-use

Pattern Matching example (data flow graph)

Subject string mein pattern dhundhne wala program. CFG ~11 nodes; usse defs/uses se augment kiya:

3.3Data Flow Graph Coverage Criteria

du-paths bahut saare ho sakte hain, isliye unhe group karke criteria banate hain — def-path sets aur def-pair sets ke through.

Teen criteria — ek nazar mein

Worked example — du(10, iSub) in Pattern Matching

Def-path set: du(10, iSub) = {[10,3,4], [10,3,4,5], [10,3,4,5,6,7,8], [10,3,4,5,6,7,9], [10,3,4,5,6,10], [10,3,4,5,6,7,8,10], [10,3,4,10]}

Def-pair sets mein todo: du(10,4,iSub)={[10,3,4]} · du(10,5,iSub)={[10,3,4,5]} · du(10,8,iSub)={[10,3,4,5,6,7,8]} · du(10,9,iSub)={[10,3,4,5,6,7,9]} · du(10,10,iSub)={[10,3,4,5,6,10],[10,3,4,5,6,7,8,10],[10,3,4,10]}

Subsumption — 3 assumptions pe based

1. Har use se pehle kahin ek def hota hai.
2. Har def kam se kam ek use tak pahunchta hai.
3. Multiple out-edges wale har node pe: har out-edge pe at least one variable use hota hai, aur same variables har out-edge pe.

Data flow testing: process

3.4Data Flow Testing Example — Statistics

Statistics ke CFG ko defs/uses se augment kiya (nodes 3, 6 dummy — predicates edges pe). Phir har variable ke du-pairs nikale:

• mean: def at 5, used at 7 & 8 → pairs (5,7),(5,8) → du-paths [5,6,7], [5,6,8]
• varsum: pairs (5,7),(7,7),(7,8) → [5,6,7], [7,6,7], [7,6,8]
• i: bahut saare pairs (loop variable)

Test cases

3.5Summary — Master Subsumption Diagram 🏆

Ye diagram exam ki jaan hai — Prof. ne bola "this is the summary slide I want you all to remember."

• Prime path ⇒ all-du-paths kyun? Prime paths har branch/decision ko lene AUR skip karne dono account karte hain — toh har def-to-use path bhi cover.
• All-uses ⇒ edge kyun? (Assumption #3 ke under) har edge pe at least ek use hota hai → saare uses = saare edges.
• IDE (Eclipse/IntelliJ/VS) se CFG generate kar sakte ho; course mein hand se. Next week: call graphs.

PAWeek 3 Practice Assignment — Q&A

Common data Q7–9: findMin()

public int findMin(){
  int min = 0;                      // ← BUG yahan chhupa hai!
  for(int i = 0; i < iarr.length; i++){
    if(min > iarr[i]) min = iarr[i];
  }
  return min;
}

GAWeek 3 Graded Assignment — Q&A

Common data Q3–5

x=0; y=1;
while(x<y){ y = x+y; x = x+1; }

Common data Q6–10: getAvgWordLen()

public double getAvgWordLen() {
  double avg = 0.0;  int totalLen = 0;
  int n = words.length;
  if(n == 1) { avg = words[0].length(); }
  else {
    for(int i = 0; i < n; i++) { totalLen += words[i].length(); }
    avg = (double)totalLen / n;   // BUG: n==0 → division by zero!
  }
  return avg;
}

⚡Rapid Revision — quiz se pehle 5 minute

1. du-path = simple + def-clear (def → use). Intervening uses OK, re-defs NOT OK.
2. Subsumption chain: All-du-Paths ⇒ All-Uses ⇒ All-Defs.
3. Cross arrows: Prime Path ⇒ All-du-Paths aur All-Uses ⇒ Edge — master diagram ki jaan.
4. Data flow mein side trips def-clear hone chahiye.
5. Loop-check node = dummy node; bina branching wale consecutive statements = ek basic block / ek node.
6. x++ type statements: use pehle, def baad mein.
7. Switch-case bina break = fall-through edge agle case tak; har return ka alag node.
8. Infeasible du-pairs identify karna usually undecidable hai; du-pairs bahut zyada ho sakte hain.
9. Boundary test cases (empty array, single element, all-positive) hi classic bugs pakadte hain — min=0 bug, division-by-zero bug.
10. Process: program → data flow analysis → du-pairs → test data generation → coverage check → test cases.