Merciless Refactoring Demo Part Notes

add this to the end of TEST(1)

  result = cmp.compare();
  utassert(Comparer::DONE, result);

Refactor steps:

look for easy methods to extract
look for encapsulation opportunities
look for code you understand

1) enscapsulate associated code together:

const values (CHG, etc.) go together with compareInit and compare()
put them into a class called Comparer

create an empty class; compile
move the enum into the class; comment out the consts; compile; get errors
put Comparer:: in front of all the references; compile & run UTs?
put CompareInit?() and compare() in the class, put leftDiff & rightDiff into the class
in the Test Case, create an instance of Comparer called cmp
put "cmp." in front of CompareInit?, etc. compile and run
move lindex, rindex, x and y into Comparer; get rid of the "=0"

2) rename some variables

there are variables 'x' and 'y'
look in CompareInit?(), they are assigned to leftstr and rightstr respectively
look to rename primitive types the vector<string> is in a lot of places

rename 'x' to mLeftList and 'y' to mRightList
create a new typedef StringList?; put it in Comparer (public)

   typedef vector<string> StringList; compile & run

rename lindex to mLeftIndex, rindex to mRightIndex
rename leftDiff to LeftDiff? and rightDiff to RightDiff?

3) look for encapsulation opportunities

make things private; can make mLeftIndex, mRightIndex, mLeftList and mRightList private.

4) look for methods to extract

first bit of code: //skip over common values in both lists

extract it; call it SkipCommonItems?()
refactor SkipCommonItems?();

notice that mLeftIndex < mLeftList.size() is checking if the left list is done

extract it as IsLeftDone? ; compile and run
extract same for IsRightDone?; compile and run

look for duplicate code to be replaced by IsLeftDone? and IsRightDone?

replace three if's with IsLeftDone? and IsRightDone?; compile and run
replace the inverse and replace with !IsLeftDone? and !IsRightDone?

5) look to simplify nested if's

- look at first if. move things around a little a) change if into two separate clauses both at the same level

- What does this do?

    while(!IsRightDone())
      RightDiff.push_back(mRightList[mRightIndex++]);

- it copies the remainder of the right list into the RightDiff?

b) Too scary! add a couple of new test cases

TEST(empty_left)
  {
  Comparer::StringList leftlist;
  Comparer::StringList rightlist;
  int result;
  
  leftlist.clear();
  rightlist.clear();
  
  rightlist.push_back("item1");
  rightlist.push_back("item2");
  
  Comparer cmp;
  cmp.compareInit(leftlist, rightlist);
  
  result = cmp.compare();
  utassert(Comparer::INS, result);
  utassert(0, cmp.LeftDiff.size());
  utassert(2, cmp.RightDiff.size());
  utassert("item1", cmp.RightDiff[0]);
  utassert("item2", cmp.RightDiff[1]);

  result = cmp.compare();
  utassert(Comparer::DONE, result);
  }

TEST(empty_right)
  {
  Comparer::StringList leftlist;
  Comparer::StringList rightlist;
  int result;
  
  leftlist.clear();
  rightlist.clear();
  
  leftlist.push_back("item1");
  leftlist.push_back("item2");
  
  Comparer cmp;
  cmp.compareInit(leftlist, rightlist);
  
  result = cmp.compare();
  utassert(Comparer::DEL, result);
  utassert(2, cmp.LeftDiff.size());
  utassert(0, cmp.RightDiff.size());
  utassert("item1", cmp.LeftDiff[0]);
  utassert("item2", cmp.LeftDiff[1]);

  result = cmp.compare();
  utassert(Comparer::DONE, result);
  }

c) extract method; call it CopyRemainderOfRightList?()

- look for similar code - find this:

    while(!IsLeftDone())
      LeftDiff.push_back(mLeftList[mLeftIndex++]);

- it copies the remainder of the left list into the LeftDiff?

d) extract method; call it CopyRemainderOfLeftList?()

6) look for methods to extract - look at first bit of code: it searches through the right list looking for a given item

a) extract method:

int Comparer::FindInRightList(const string& item)

- look at bit of code right underneath it - it copies from i to the end of the list

b) extract method:

void Comparer::CopyFromRightListUntil(int i);

- look for other common code - find this:

   while (mLeftIndex != tmp)
          LeftDiff.push_back(mLeftList[mLeftIndex++])

c) extract method:

void Comparer::CopyFromLeftListUntil(int i);

- look at this:

      bool done = false;
      for(int tmp = mLeftIndex + 1; tmp < mLeftList.size(); tmp++)
        {
        if (mLeftList[tmp] != mRightList[mRightIndex])
          continue;
     
        CopyFromLeftListUntil(tmp);
        done = true;
        result = Comparer::DEL;
        }

- it looks like a bug! it seems that the for loop should end when done == true.

d) add a break at the end of the for(). rerun, passes the UTs?!?

hmmm. we need to add a unit test for the this situation.

7) add unit tests:

a) remove the "break" at the end of the for loop b) add this test case

TEST(TwoSameItemsInLeftList)
  {
  Comparer::StringList leftlist;
  Comparer::StringList rightlist;
  
  leftlist.clear();
  rightlist.clear();
  int result;
  
  leftlist.push_back("item1");
  leftlist.push_back("item2");
  leftlist.push_back("item3");
  leftlist.push_back("item4");
  leftlist.push_back("item3");
  rightlist.push_back("item1");
  rightlist.push_back("item3");
  rightlist.push_back("item3");
  
  Comparer cmp;
  cmp.compareInit(leftlist, rightlist);
  
  result = cmp.compare();
  utassert(Comparer::DEL, result);
  utassert(1, cmp.LeftDiff.size());
  utassert("item2", cmp.LeftDiff[0]);

  result = cmp.compare();
  utassert(Comparer::DEL, result);
  utassert(1, cmp.LeftDiff.size());
  utassert("item4", cmp.LeftDiff[0]);

  result = cmp.compare();
  utassert(Comparer::DONE, result);
  }

c) compile & run; there should be 4 assertions d) uncomment the "break"; compile & run; there should be no errors!

- look at cleaning up the code in the for loop! make it look like FindInRightList?

e) rearrange the for-loop to:

      for(int i = mLeftIndex + 1; i < mLeftList.size(); i++)
        {
        if (mLeftList[i] == mRightList[mRightIndex])
          break;
        }
      if (i < mLeftList.size())
        {
        CopyFromLeftListUntil(i);
        result = Comparer::DEL;
        done = true;
        }

compile & run. No errors!

- the variable done is now redundant!?

f) remove done.

g) extract new method

int Comparer::FindInLeftList(const string& item)

8) clean up nested ifs - allow multiple exit points...

a) replace lines like:

result = Comparer::DONE;

with

return Comparer::DONE;

- huh? MATCH can never be returned???

  int result = Comparer::MATCH;

b) add a unit test!

TEST(ListsAreTheSame)
  {
  Comparer::StringList leftlist;
  Comparer::StringList rightlist;
  
  leftlist.clear();
  rightlist.clear();
  int result;
  
  leftlist.push_back("item1");
  leftlist.push_back("item2");
  rightlist.push_back("item1");
  rightlist.push_back("item2");
  
  Comparer cmp;
  cmp.compareInit(leftlist, rightlist);
  
  result = cmp.compare();
  utassert(Comparer::DONE, result);
  utassert(0, cmp.LeftDiff.size());
  utassert(0, cmp.RightDiff.size());
  }

compile and run.; everything passes; what???

c) add another unit test for empty lists?

TEST(EmptyLists)
  {
  Comparer::StringList leftlist;
  Comparer::StringList rightlist;
  
  leftlist.clear();
  rightlist.clear();
  int result;
  
  Comparer cmp;
  cmp.compareInit(leftlist, rightlist);
  
  result = cmp.compare();
  utassert(Comparer::DONE, result);
  utassert(0, cmp.LeftDiff.size());
  utassert(0, cmp.RightDiff.size());
  }

compile and run.; everything passes;

looks like Comparer::MATCH is a bug. It never gets returned!

d) delete MATCH from the enum

9) remove dead code

- look at:

    int l = mLeftIndex;
    int r = mRightIndex;
    
    if (l >= mLeftList.size())
      break;
    
    if (r >= mRightList.size())
      break;
    
    if (mLeftList[l] == mRightList[r])
      break;
    
    for (int j = mLeftIndex + 1; !done && j < mLeftList.size(); j++)
      done = mLeftList[j] == mRightList[r];
    
    for(int k = mRightIndex + 1; !done && k < mRightList.size(); k++)
      done = mRightList[k] == mLeftList[l];

This code does not modify mLeftIndex or mRightIndex. It doesn't modify mLeftDiff or mRightDiff.

It has no effect???

a) temporarily comment out the code. compile and run; boom! get a GPF.

look at again at the loop:

  bool done = false;
  do
    {
    LeftDiff.push_back(mLeftList[mLeftIndex++]);
    RightDiff.push_back(mRightList[mRightIndex++]);
    <snip>
    } while(!done);

It's an infinite loop

b) temporarily comment out the loop and the done variable; compile and run; it passes!

- check the code again; explain the CHG happens for one and only one item...

c) delete all the comment out code

- look at all of compare(). The code now makes sense.

- The LeftDiff?.clear(); look a little out of place.

d) put the xx.clear() in CompareInit?(); compile & run. fails!

- looks like the clear() have to be done each time compare() is run

e) put them back in compare()

f) rename CompareInit?() to Init().

10) Look for duplication:

- here's the current list of methods:

    bool IsLeftDone();
    bool IsRightDone();
    void CopyRemainderOfRightList();
    void CopyRemainderOfLeftList();
    int FindInRightList(const string& item);
    int FindInLeftList(const string& item);
    void CopyFromRightListUntil(int i);
    void CopyFromLeftListUntil(int i);

there's duplication in the names of the methods. The only difference in the method names is "Left" vs "Right"

- also look at the member variables

    StringList mLeftList;
    int mLeftIndex;
    StringList mRightList;
    int mRightIndex;

there's duplication there too. The only difference in the method names is "Left" vs "Right"

This suggests that there are two instances (a "left" and a "right") of the same class. That class encapsulates an index and a StringList?.

a) create an empty class called

class CompareList
  {
  public:
  } ;

b) copy the member variables to the class; remove the "Left" or "Right"; they are now mList and mIndex; add the typedef for the compile error

typedef vector<string> StringList;

c) in Comparer add an instance of CompareList?:

CompareList mLeft;

i) lots of compiler errors; change all mLeftList to mLeft.mList ii) more compiler errors; change all mLeftIndex to mLeft.mIndex iii) compiles clean iv) do mRightList and mRightIndex v) compiles clean

- now look for methods that use only mLeft variables or only mRight variables - find FindInRightList? and FindInLeftList?

d) move them into CompareList? i) change the Comparer:: into CompareList?:: ii) remove references to "Right" in the method name and in the class declaration iii) remove the mRight references iv) compile v) fix all calls to it

vi) ditto for FindInLeftList?

11) Look for more duplication/extract methods

- look at other similar methods bool Comparer::IsLeftDone?() and IsRightDone?

a) extract IsDone?() to CompareList?

- look for more! find:

void Comparer::CopyRemainderOfLeftList()
  {
  while(!mLeft.IsDone())
    LeftDiff.push_back(mLeft.mList[mLeft.mIndex++]);
  }

The problem here is the LeftDiff?. We need to pass it into the method as a parameter.

b) change CopyRemainderOfLeftList?() to use a parameter

compile & run; looks good

c) extract CopyRemainderOfList? to CompareList?

void CopyRemainderOfListTo?(StringList?& difflist);

d) repeat for CopyFromLeftListUntil? and CopyFromRightListUntil?

12) look for encapsulation opportunites

- look at

  int i;
  i = mRight.FindInList(mLeft.mList[mLeft.mIndex]);
  if (i < mRight.mList.size())
    {
    mRight.CopyFromListUntil(RightDiff, i);
    return Comparer::INS;
    }

It uses almost all mRight variables or methods. Can this be extracted out?

a) Yes. create this:

bool CompareList::CopyChangesUntil(StringList& difflist, const string& item)
  {
  int i = FindInList(item);
  if (i < mList.size())
    {
    CopyFromListUntil(difflist, i);
    return true;
    }
  return false;
  }

- see if CopyFromListUntil? can be made private?

b) Yes, make it private

- these are still public in CompareList?:

    StringList mList;
    int mIndex;

can they be made private?

c) yes, create a const string& GetCurrent?() for mXX.mList[mXX.mIndex]

For these two:

  LeftDiff.push_back(mLeft.mList[mLeft.mIndex++]);
  RightDiff.push_back(mRight.mList[mRight.mIndex++]);

convert to:

  LeftDiff.push_back(mLeft.mList[mLeft.mIndex]);
  mLeft.mIndex++;
  RightDiff.push_back(mRight.mList[mRight.mIndex]);
  mRight.mIndex++;

d) create a CompareList?::Next() and convert all the mXX.mIndex to Next()

e) try moving the CompareList? variables into private section

- Comparer::Init() complains about accesses to private variables.

f) create

void CompareList::Init(const StringList& slist)

13) Polish

- find private functions in CompareList? and Comparer

a) end up with these two

  private:
    int FindInList(const string& item);
    void CopyFromListUntil(StringList& difflist, int i);

b) extract a BothNext?():

void Comparer::BothNext()
  {
  mLeft.Next();
  mRight.Next();
  }

c) add more unit tests:

TEST(LeftLonger)
  {
  Comparer::StringList leftlist;
  Comparer::StringList rightlist;
  int result;
  
  leftlist.clear();
  rightlist.clear();
  
  leftlist.push_back("item1");
  leftlist.push_back("item2");
  rightlist.push_back("item1");
  
  Comparer cmp;
  cmp.Init(leftlist, rightlist);
  
  result = cmp.compare();
  utassert(Comparer::DEL, result);
  utassert(1, cmp.LeftDiff.size());
  utassert(0, cmp.RightDiff.size());
  utassert("item2", cmp.LeftDiff[0]);
  
  result = cmp.compare();
  utassert(Comparer::DONE, result);
  }

TEST(RightLonger)
  {
  Comparer::StringList leftlist;
  Comparer::StringList rightlist;
  int result;
  
  leftlist.clear();
  rightlist.clear();
  
  leftlist.push_back("item1");
  rightlist.push_back("item1");
  rightlist.push_back("item2");
  
  Comparer cmp;
  cmp.Init(leftlist, rightlist);
  
  result = cmp.compare();
  utassert(Comparer::INS, result);
  utassert(0, cmp.LeftDiff.size());
  utassert(1, cmp.RightDiff.size());
  utassert("item2", cmp.RightDiff[0]);
  
  result = cmp.compare();
  utassert(Comparer::DONE, result);
  }

d) extract IsMatch?()

mLeft.GetCurrent() != mRight.GetCurrent()  //don't forget to change the != to an ==

convert the forloop to:

  while( !mLeft.IsDone() && !mRight.IsDone() && IsMatch() )
    BothNext();

14) Look for similar signatures

- note for these two:

mLeft.CopyRemainderOfListTo(LeftDiff);
mLeft.CopyChangesUntil(LeftDiff, mRight.GetCurrent()))

That LeftDiff? is always passed in and mLeft & LeftDiff? have similar names. The right versions are the same:

mRight.CopyRemainderOfListTo(RightDiff);
mRight.CopyChangesUntil(RightDiff, mLeft.GetCurrent()))

This seems to suggest that there is another class in compare():

It contains a CompareList? and a StringList? and has method names:

    CopyRemainderOfList()
    CopyChangesUntil()

plus a few pass-through methods.

//--------------------------------------------------------------
class ComparePair
  {
  public:
    void Init(const StringList& slist)
      {
      mList.Init(slist);
      }
    bool IsDone()
      {
      return mList.IsDone();
      }
    void CopyRemainderOfList()
      {
      mList.CopyRemainderOfListTo(mDiff);
      }
    bool CopyChangesUntil(const string& item)
      {
      return mList.CopyChangesUntil(mDiff, item);
      }
    const string& GetCurrent()
      {
      return mList.GetCurrent();
      }
    void PushCurrent()
      {
      mDiff.push_back(mList.GetCurrent());
      }
    void Next()
      {
      mList.Next();
      }
    
    CompareList mList;
    StringList mDiff;
  } ;