Cyclomatic Complexity Viewer

/*  ====================================================================
*  Copyright (c) 2005 Franz Klein, franzaklein@yahoo.co.uk
*  All rights reserved.
*
*  Redistribution and use in source and binary forms, with or without
*  modification, are permitted provided that the following conditions
*  are met:
*
*  1. Redistributions of source code must retain the above copyright
*     notice, this list of conditions and the following disclaimer.
*
*  2. Redistributions in binary form must reproduce the above copyright
*     notice, this list of conditions and the following disclaimer in the
*     documentation and/or other materials provided with the distribution.
*
*  3. The name of the author may not be used to endorse or promote products
*     derived from this software without specific prior written permission.
*
*  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
*  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
*  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
*  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
*  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
*  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
*  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
*  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
*  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
*  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*  ====================================================================
*/

// GraphBuilder.cpp: implementation of the CGraphBuilder class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "CycloComplexViewer.h"
#include "GraphBuilder.h"
#include <assert.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CGraphBuilder::CGraphBuilder()
{
	graphdata = CSingleton<Data>::Instance();
	currentnode = graphdata->begin();
	ifword = "if";
	elseword = "else";
	doword = "do";
	whileword = "while";
	caseword = "case";
	switchword = "switch";
	inifelse = false;
	inelse = false;
	switchlevel = 0;
}

CGraphBuilder::~CGraphBuilder()
{

}

//Generates directional graph
bool CGraphBuilder::BuildGraph()
{
	NumberNodes();
	while (currentnode != graphdata->end())
	{
		node_ptr returnnode = ConditionalSwitcher(currentnode);
		if (currentnode == returnnode)
			currentnode++;
		else
			currentnode = returnnode;
	}
	return true;
}

//Switches to the different parsers depending on the conditional statement
node_ptr CGraphBuilder::ConditionalSwitcher(node_ptr parent)
{
	string searchline = parent->label;
	if (parent->indo)
		return BuildDoGraph(parent);
	if (parent->ifelse)
	{
		inifelse = true;
		node_ptr result = BuildIfElseGraph(parent);
		inifelse = false;
		return result;
	}
	else
	{
		if (m_dictionary.Search(searchline, "if"))
			return BuildIfGraph(parent, NULL);
	}
	if (m_dictionary.Search(searchline, "while"))
		return BuildWhileGraph(parent);
	if (m_dictionary.Search(searchline, "switch"))
		return BuildSwitchGraph(parent);
	return parent;
}

//Constructs a sub-graph for an 'if' compound statement
node_ptr CGraphBuilder::BuildIfGraph(node_ptr parent, node_ptr elsenode)
{
	//parent must contain the 'if' statement
	assert(m_dictionary.Search(parent->label, "if"));
	node_ptr child = parent;
	child++;
	//let the 'if' statement point to the statement that
	//will be executed if the 'if' statement is true
	AddChild(parent, child);

	node_ptr next;
	if (elsenode == NULL)
	{
		while ((parent->level < child->level))
			child = ParseSubgraphs(child);
		//find false route
		next = child;
		//skip nested statements within compound 'if' statement
		while (next->level > parent->level)
			next++;
	}
	else //the 'if' statement is part of an 'if/else'
	{
		while (child != elsenode)
			child = ParseSubgraphs(child);
		next = child;
		//skip the statements of the 'else' compound statement
		if (parent->inelse == 0)
		{
			while (next->inelse > 0)
				next++;
		}
	}

	child--;
	//if the 'if' statements are contained within 'case' statements then
	//skip other compound 'case' statements
	while ((next->level >= child->level) || (next->casenum != child->casenum) && (next->casenum > 0))
		next++;
	//check to see if nested within an 'if/else' statement
	//if so skip the 'else' part
	while (next->iselse)
		next++;
	if (next != graphdata->end())
	{
		//continuation route
		AddChild(child, next);
		//false route
		if (!parent->ifelse)
			AddChild(parent, next);
	}
	//if contained within a 'while' statement
	if (parent->inwhile)
	{
		node_ptr whilepos = parent;
		whilepos--;
		AddChild(child, whilepos);
	}

	return child;
}

//Constructs a sub-graph for a 'while' compound statement
node_ptr CGraphBuilder::BuildWhileGraph(node_ptr parent)
{
	//parent should contain the 'while' statement
	assert(m_dictionary.Search(parent->label, "while"));
	node_ptr child = parent;
	child++;
	AddChild(parent, child);
	//last child needs to point back to parent as well
	//as the next statement.
	while ((child->level > parent->level) && (child != graphdata->end()))
		child = ParseSubgraphs(child);
	node_ptr next = child;
	child--;
	if (parent->inelse == 0)
	{
		while (next->inelse > 0)
			next++;
	}
	//if inside a compound 'case' statement
	while ((next->level >= child->level) || (next->casenum != child->casenum) && (next->casenum > 0))
		next++;
	//generate edges
	if (child != graphdata->end())
	{
		AddChild(child, parent);
		AddChild(child, next);
		AddChild(parent, next);
	}

	return child;
}

//Constructs a sub-graph for an 'do' compound statement
node_ptr CGraphBuilder::BuildDoGraph(node_ptr parent)
{
	//the 'do' statement is left out
	node_ptr child = parent;
	child++;
	AddChild(parent, child);
	node_ptr whileofdo = parent;
	//find the corresponding 'while' of the 'do'
	bool whilefound = false;
	bool semicolonfound = false;
	do
	{
		whileofdo++;
		//the 'while' part of a 'do' statement end in ';'
		whilefound = m_dictionary.Search((whileofdo->label), "while");
		semicolonfound = m_dictionary.Search((whileofdo->label), ";");
	} while (!whilefound && !semicolonfound);
	//child should now point to the 'while'
	assert(m_dictionary.Search(whileofdo->label, "while"));
	//last child needs to point to parent as well
	//as the next statement
	AddChild(whileofdo, parent);
	//now process all nested conditions within 'do' statement
	node_ptr current_child = parent;
	while (current_child != whileofdo)
	{
		current_child->indo = 0;
		current_child++;
	}
	while (parent != whileofdo)
		parent = ParseSubgraphs(parent);
	node_ptr next = whileofdo;
	while ((next->level >= child->level) || (next->casenum != child->casenum) && (next->casenum > 0))
		next++;
	AddChild(whileofdo, next);

	return ++parent;
}

//Constructs a sub-graph for a 'switch' compound statement
node_ptr CGraphBuilder::BuildSwitchGraph(node_ptr parent)
{
	//parent should contain the 'switch' statement
	assert(m_dictionary.Search(parent->label, "switch"));
	node_ptr child = parent;
	child++;
	node_ptr afterswitch = child;
	while (afterswitch->level > parent->level)
		afterswitch++;
	if ((afterswitch->ifelse || afterswitch->inelse) && (parent->inif))
	{
		while (afterswitch->ifelse || afterswitch->inelse)
			afterswitch++;
	}
	while (child->level > parent->level)
	{
		AddChild(parent, child);
		node_ptr result = BuildCaseGraph(child, afterswitch);
		child = result;
	}

	return child;
}

//Labels nodes of graph
void CGraphBuilder::NumberNodes()
{
	node_ptr node = graphdata->begin();
	int i = 0;
	while (node != graphdata->end())
	{
		node->num = i++;
		node++;
	}
}

//Check whether the parent has the specified child
//returns true if the child already exists
//        false if not
bool CGraphBuilder::HasEdge(node_ptr parent, node_ptr child)
{
	node_ptr* children = parent->children.begin();
	if (child == parent)
		return true;
	while (children != parent->children.end())
	{
		if (*children == child)
			return true;
		else
			children++;
	}
	return false;
}

node_ptr CGraphBuilder::BuildElseGraph(node_ptr parent)
{
	inelse = true;
	node_ptr child = parent;
	do
	{
		child = ParseSubgraphs(child);
	} while (child->level > parent->level);
	node_ptr next = child;
	child--;
	if (!inifelse)
		while (next->level > parent->level)
			next++;
	while ((next->level >= child->level) || (next->casenum != child->casenum) && (next->casenum > 0))
		next++;
	if (next != graphdata->end())
	{
		//continuation route
		AddChild(child, next);
	}
	inelse = false;
	return ++child;
}

node_ptr CGraphBuilder::BuildIfElseGraph(node_ptr parent)
{
	//parent should contain the 'if' statement
	assert(m_dictionary.Search(parent->label, "if"));
	node_ptr elselocation = parent;
	//first find an 'else'
	do
	{
		elselocation++;
	} while (!elselocation->iselse);
	//now check if it is the right 'else'
	while (elselocation->level != (parent->level + 1))
	{
		if ((elselocation->indo) && (elselocation->level == (parent->level + 2)))
			break;
		else
			elselocation++;
	}
	node_ptr output = BuildIfGraph(parent, elselocation);
	output++;
	AddChild(parent, output);
	node_ptr result = BuildElseGraph(output);

	return result;
}

//
node_ptr CGraphBuilder::BuildCaseGraph(node_ptr parent, node_ptr post_switch)
{
	//parent should contain the 'switch' statement
	assert(parent->incase);
	node_ptr nextcase = parent;
	//first find the statement following the whole compound 'case'
	//statement
	do
	{
		nextcase++;
	} while (!nextcase->incase && nextcase->level >= parent->level);
	node_ptr last = parent;
	while (last != nextcase)
	{
		last = ParseSubgraphs(last);
	}
	last--;
	AddChild(last, post_switch);

	return ++last;
}

//Calculates the actual metric value from the graph
//generated
int CGraphBuilder::CalculateMetric()
{
	//Cyclomatic Complexity Metric = Edges - Nodes + 2
	//count nodes by looking at size of vector
	int nodes = 0;
	node_ptr start_node = graphdata->begin();
	while (start_node != graphdata->end())
	{
		nodes++;
		start_node++;
	}
	//count edges by looking at how many children each node_ptr has
	int edges = 0;
	start_node = graphdata->begin();
	while(start_node != graphdata->end())
	{
		edges += start_node->children.size();
		start_node++;
	}
	int ccm = 0;
	//perform calculation
	if (edges != 0 || nodes != 0)
		ccm = edges - nodes + 2;
	graphdata->erase(graphdata->begin(), graphdata->end());
	return ccm;
}

//Used to parse subgraphs that contain conditionals
node_ptr CGraphBuilder::ParseSubgraphs(node_ptr first_statement)
{
	assert(first_statement != NULL);
	node_ptr result = ConditionalSwitcher(first_statement);
	if (result == first_statement)
		result++;

	return result;
}

//Gets rid of data
void CGraphBuilder::Cleanup()
{
	CSingleton<Data>::Destroy();
}

//Add a child to the list of a parent's children
//returns true if child is added
//        false if not
bool CGraphBuilder::AddChild(node_ptr parent, node_ptr child)
{
	if (!HasEdge(parent, child))
	{
		parent->children.push_back(child);
		return true;
	}
	else
		return false;
}