Sqp 2005 L8a Re Engineering

2162ICT Software Quality Principles

Reengineering Software

R.G. Dromey

© R.G.Dromey, Griffith University, 2005

What We Will Focus On Low-level re-engineering at the code level, -- loops, -- branches, ----------sequences.

QUESTION Why re-engineer software

while ((Op= getopt(arge, argv, Vop)) != ERROR) { if ((char) Op == Opq) { QFlag = TRUE; if (LFlag) { Error = TRUE; break; } if (SFlag) { Error = TRUE; break; } } else { if ((char) Op == Opl) { LFlag = TRUE; if (QFlag) { Error = TRUE; break; } LevelStr = optarg; } else {if ((char) Op == Ops) { SFlag = TRUE; Subsystem = optarg; if (QFlag) { Error = TRUE; break; } } else { Error = TRUE; break; } } } }  

Justification for Re-engineering To meet other needs or improve its quality To understand what a piece of code does To discover problems with a piece of code To improve the efficiency and/or understandability of a piece of code.

Problems With Branched Structures •

  Branched  structures  either  in  loops  or  elsewhere  are a major cause of  quality defects in software.

     Problems with branched structures include: – – – –

­  some branches are unreachable ­  logic in branched structures may be incorrect ­    branched  structures  in  loops  can  cause  termination     ­­­­­ problems ­  complex  branched  structures  are  hard  to  understand  ­­­­­­and modify 

Branch Statement Rules

Absorption Into Branch Structure Promotes statement into branch.  

Statement  must  be  absorbed  into  all branches The  expression’s  value  must  be  factored  into  the  guards  for  the  if  statement. 

Assignment Absorption Into Branch

Before x:=E; if C →S1 [] ¬C → S2 fi   After Transformation  

if C[E/x] → x:=E; S1 [] ¬C[E/x] → x:=E; S2 fi

Assignment Absorption - Example Before x:=a+b; if x < N → S1 [] x ≥ N → S2 fi   After Transformation  

if a+b
Read, Write, Absorption Before write(E); if C → S1 [] ¬C → S2 fi   After Transformation  

if C → write(E); S1 [] ¬C → write(E); S2 fi NOTE: Cannot absorb read(x) if x is in guard C

Post-absorption Into Branch Structure Before if C → S1 [] ¬C → S2 fi; S  After Transformation  

if C → S1; S [] ¬C → S2; S fi Such transformations used to remove redundancies

Loop Statement Rules

Problems With Loops   

In imperative programs loops are usually regarded  as  the  most  difficult  structures  to  implement,  analyse, reuse, modify and prove correct.

     The use of multiple exits and flags exacerbates the  difficulties of dealing with loops.             Such  features  significantly  detract  from  the  structural  integrity,  simplicity,  reliability  and  the  ultimate quality of programs.

Equivalence Transformations      It is possible to make a number of transformations  on  loops  that  allow  us  to  remove  unnecessary  structure involving multiple exits while preserving  correctness with respect to the original program.   

        The program before and  after transformation  will  always  produce  the  same  results  for  the  same  inputs.  

          The  restructuring  structuring  technique  that  may  be  used  employs  a  number  of  equivalence  transformations.

Branch Removal From a Loop Before do G → if Ce → Se [] C¬e → S¬e fi od  After Transformation  

do G∧C¬e → S¬e od; if G → Se fi where Se causes an exit from the loop

Reengineering A Loop Structure 

  

We  now  want  to  examine  how  the  various transformations we have defined  may  be  combined  to  reengineer  a  complex loop structure These  tranformations  allow  us  to  create  intermediate  forms  that  expose  logical  flaws in the structure of a loop

Reengineering A Loop Structure 

We  are  able  to  graphically  represent  the  execution  behaviour of a complex  loop and  decide  how  its  structure  should  be transformed to make it simpler  and more efficient  

while ((Op= getopt(arge, argv, Vop)) != ERROR) { if ((char) Op == Opq) { QFlag = TRUE; if (LFlag) { Error = TRUE; break; } if (SFlag) { Error = TRUE; break; } } else { if ((char) Op == Opl) { LFlag = TRUE; if (QFlag) { Error = TRUE; break; } LevelStr = optarg; } else {if ((char) Op == Ops) { SFlag = TRUE; Subsystem = optarg; if (QFlag) { Error = TRUE; break; } } else { Error = TRUE; break; } } } }  

Collapsing a Loop Structure 

The first major step in the process of  loop  reengineering  is  to  carry  out  a  transformation  that,  in  operational  terms,  effectively  delays  as  far  as  possible  the  execution  of  all  assignments. 

        That  is,  if  it  is  possible  to  delay  an  assignment  until  some  additional  condition  has  been  established  then  this should always be done. 

Collapsing a Loop Structure   This  transformation  uncovers  the  strongest  precondition  under  which  each assignment may execute.                   Imposing  this  requirement  also  effectively  collapses  complex  branch  structures  within  a  loop  to  a  simple  uniform form. 

MBS Form for Loop Structures W     We  call  this  required  intermediate 

structure  the  Multiply­Branched  Statement  (MBS) form, i.e: do G → if C1 → S1 [] C2 → S2 .... [] Cn → Sn fi od

Part of Poor Loop Structure  while

((Op= getopt(arge, argv, Vop)) != ERROR) { if ((char) Op == Opq) { QFlag = TRUE; The first step is to if (LFlag) { move the assignment Error = TRUE; QFLAG = TRUE break; } if (SFlag) { Error = TRUE; break; } }

Does This Complete the Absorption?   while ((Op= getopt(arge, argv, Vop)) != ERROR) { if ((char) Op == Opq) { if (LFlag) { QFlag = TRUE; Error = TRUE; break; } if (SFlag) { QFlag = TRUE; Error = TRUE; break; } }

Need to Account for Negated Case Original while((Op= getopt(arge, argv, Vop)) != ERROR) { if ((char) Op == Opq) { if (LFlag) { QFlag = TRUE; Error = TRUE; break; } if (SFlag) { QFlag = TRUE; Error = TRUE; break; } }  

 

We need to properly account for the case where both  guards are false.  

Assignment Absorption Into Branch             

After while ((Op= getopt(arge, argv, Vop)) != ERROR) { if ((char) Op == Opq) { if (LFlag) { QFlag = TRUE; Error = TRUE; break; } if (SFlag) { QFlag = TRUE; Error = TRUE; break; } if (¬LFlag ∧ ¬SFlag){ QFlag = TRUE;} }

Get Resolved Guards For Branches 

We  may  also  combine  guards  to  get  the  resolved  guards  for  each  of  the  resulting  three  branches.  This gives:



 



while ((Op= getopt(arge, argv, Vop)) != ERROR) { {B1}if (Op == Opq)∧LFlag → QFlag = TRUE; Error = TRUE; break {B2}[] (Op==Opq) ∧ ¬LFlag ∧ SFlag → QFlag = TRUE; Error=TRUE; break {B3}[] (Op == Opq) ∧ ¬LFlag ∧ ¬SFlag → QFlag = TRUE •••





 





 

Get Resolved Guards For Branches         

do (Op= getopt(arge, argv, Vop)) != ERROR → {B1}if (Op == Opq)∧LFlag → QFlag = TRUE; Error = TRUE; break {B2}[] (Op == Opq) ∧¬LFlag SFlag → QFlag = TRUE; Error = TRUE; break {B3}[] (Op == Opq) ∧ ¬LFlag ∧ ¬SFlag → QFlag = TRUE {B4}[] (Op == Opl) ∧ QFlag ∅LFlag = TRUE; Error = TRUE; break {B5}[] (Op == Opl) ∧ ¬QFlag → LFlag = TRUE; LevelStr = optarg {B6}[] (Op == Ops) ∧ QFlag → SFlag = TRUE; Subsystem = optarg; Error = TRUE; break {B7}[] (Op == Ops) → SFlag = TRUE; Subsystem See∧ ¬QFlag has eight (8) branches = optarg Most are terminating {B8}[] (Op != Opq)∧(Op != Opl)∧(Op != Ops)∧(Op != Ops) → Error = TRUE; break

Identify Non-Terminating Branches         

do (Op= getopt(arge, argv, Vop)) != ERROR → {B1}if (Op == Opq)∧LFlag → QFlag = TRUE; Error = TRUE; break {B2}[] (Op == Opq) ∧¬LFlag∧SFlag → QFlag = TRUE; Error = TRUE; break {B3}[] (Op == Opq) ∧ ¬LFlag ∧ ¬SFlag → QFlag = TRUE {B4}[] (Op == Opl) ∧ QFlag ∅LFlag = TRUE; Error = TRUE; break {B5}[] (Op == Opl) ∧ ¬QFlag → LFlag = TRUE; LevelStr = optarg {B6}[] (Op == Ops)∧QFlag→ SFlag=TRUE;Subsystem=optarg; Error = TRUE; break {B7}[] (Op == Ops) → SFlag = TRUE; Subsystem See∧ ¬QFlag has eight (8) branches = optarg Most are terminating {B8}[] (Op != Opq)∧(Op != Opl)∧(Op != Ops)∧(Op != Ops) → Error = TRUE; break

Branch Successor Graph   One Iteration

Next Iteration (if loop guard holds)

Branch Successor Graph B4 B2

B1

B6 B3 B7 B5

Reachability = 13  64            

B8

Exiting nodes (leaf                nodes)  Non­exiting nodes

Ideally branch­successor­graphs should be strongly connected ­  i.e. each branch connected to every other branch

Loop Normalization In graph theoretic terms loop rationalization involves removing  all the leaf nodes from the branch­successor graph.

B4(Exit)

B3

B2 (Exit) B1 (Exit)

B7 B5

B6 (Exit) Loop  Rationalization

B8 (Exit)

B3 B7 B5

Re-engineered Loop Structure 





   



do (Op = getopt(arge, argv, Vop) == Opq) ∧ ¬LFlag ∧ ¬SFlag → QFlag = TRUE [] (Op = getopt(…) == Opl) ∧ ¬QFlag → LFlag = TRUE; LevelStr = optarg [] (Op = getopt(…) == Ops) ∧ ¬QFlag → SFlag = TRUE; Subsystem = optarg od; if (Op == Opq) ∧(LFlag SFlag) → QFlag = TRUE; Error = TRUE [] (Op == Opl) ∧ QFlag → LFlag = TRUE; Error = TRUE [] (Op == Ops) ∧QFlag → SFlag = TRUE; Subsystem = optarg; Error = TRUE [] (Op != ERROR) ∧(Op != Opq) ∧(Op != Opl) (Op != Ops) → Error = TRUE