metrixpp/old/dupindex/dupindex.cpp

/*
 *  Software Index, Copyright 2010, Software Index Project Team
 *  Link: http://swi.sourceforge.net
 *
 *  This file is part of Software Index Tool.
 *
 *  Software Index is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, version 3 of the License.
 *
 *  Software Index is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Software Index.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <algorithm>
#include <string>
#include <vector>

static const char SWI_EOF = '\x7'; // ASCII code 7 is used as EOF marker
static const int  SWI_MAX_TEXT_LENGTH = 10000;

/**
 * Container for sortable stuff
 * Strings are not moved, just bookmarks are sorted
 */
struct SwiBookmark
{
	int         m_possition;
	const char* m_text;

	// sort algorithm requires to define this operator
	bool operator<(const SwiBookmark& another) const
	{
		return strcmp(another.m_text, m_text) < 0;
	}
};

/**
 * Container for the file/function record
 */
struct SwiRecord
{
	const char* functionName;
	const char* fileName;
	int         end;
};

/**
 * Returns line number in intial record
 * from the begging till the symbol by offset
 */
static int swiLineNumberGet(const char* text,
							int         offset,
							SwiRecord   files[],
							int         fileIndex)
{
	const int start = (fileIndex == 0) ? 0 : files[fileIndex - 1].end;

	int line = 1;
	for (int i = start; i < offset; ++i)
	{
		if (text[i] == '\n')
		{
			++line;
		}
	}

	return line;
}

/**
 * Adds a character to the processed string,
 * initializes new bookmark, and returns it
 */
static SwiBookmark swiProcessedCharacterAdd(char c, int originalPossition, char* processedText)
{
	static int processedPossition;
	SwiBookmark bookmark;
	bookmark.m_possition  = originalPossition;
	bookmark.m_text = processedText + processedPossition;
	processedText[processedPossition++] = c;
	return bookmark;
}

/**
 * Prints to stdout the found items
 * The format of stdout is strictly defined by the caller: SWI/PROCESSOR
 * Change it synchroniously with SWI/PROCESSOR code
 */
static void swiResultPrint(SwiBookmark bookmark,
						   SwiRecord   files[],
						   const char* originalText,
						   int         numOfDuplicatedSymbols)
{
	int recordIndex = 0;
	while (files[recordIndex].end <= bookmark.m_possition)
	{
		++recordIndex;
	}

	printf("duplication: file: '%s' function: '%s' possition: '%d' size: '%d' \n",
		files[recordIndex].fileName,
		files[recordIndex].functionName,
		swiLineNumberGet(originalText, bookmark.m_possition, files, recordIndex),
		numOfDuplicatedSymbols);
}

/**
* Returns number of symbols which are equal from the beggining
*/
static int swiStringsCompare(SwiBookmark bookmarkFirst,
							 SwiBookmark bookmarkSecond)
{
	int pos = 0;
	for (; bookmarkFirst.m_text[pos] == bookmarkSecond.m_text[pos]; ++pos)
	{
		if (bookmarkFirst.m_text[pos] == SWI_EOF)
		{
			break;
		}
	}
	return pos;
}

/**
 * Checks if two strings are equal in the defined range of symbol's indexes:
 * from the first symbol till upperLimit
 */
static bool swiStringsEqualCheck(SwiBookmark bookmarkFirst,
								 SwiBookmark bookmarkSecond,
								 int upperLimit,
								 const char* endPos)
{
	if (bookmarkFirst.m_text + upperLimit >= endPos ||
		bookmarkSecond.m_text + upperLimit >= endPos)
	{
		return false;
	}

	for (int i = upperLimit; i >= 0; --i)
	{
		if (bookmarkFirst.m_text[i] != bookmarkSecond.m_text[i])
		{
			return false;
		}
	}
	return true;
}

/**
 * Scans the original text into a processed text, which is returned.
 * The processed string does not include the ignorable symbols
 * The list of ignorable symbols is configured (usualy spaces)
 * Bookmarks are installed for every newline
 * if it begins from the 'regular' symbol
 * The list of non-regular symbols is configred
 */
static const char* swiOriginalStringProcess(std::string               originalText,
											std::vector<SwiBookmark>& bookmarks,
											const char * ignorableSymbols,
											const char * nonregularSymbols)
{
	char* const processedText = new char[originalText.length()];
	bool  isNewlineDetected = true;

	for (unsigned int i = 0; i < originalText.length(); ++i)
	{
		const char c = originalText[i];
		bool isIgnorable  = false;
		bool isRegular    = true;


		// Processed text should not include the end-null symbol
		if (c == '\0')
		{
			continue;
		}

		if (c == SWI_EOF)
		{
			swiProcessedCharacterAdd(c, i, processedText);
			continue;
		}

		for (int j = 0; ignorableSymbols[j] != '\0'; ++j)
		{
			if (ignorableSymbols[j] == c)
			{
				isIgnorable = true;
			}
		}

		for (int j = 0; nonregularSymbols[j] != '\0'; ++j)
		{
			if (nonregularSymbols[j] == c)
			{
				isRegular = false;
			}
		}

		if (!isIgnorable)
		{
			if (isNewlineDetected && isRegular)
			{
				bookmarks.push_back(swiProcessedCharacterAdd(c, i, processedText));
			}
			else
			{
				swiProcessedCharacterAdd(c, i, processedText);
			}

			isNewlineDetected = false;
		}

		if (c == '\n')
		{
			isNewlineDetected = true;
		}
	}
	swiProcessedCharacterAdd('\0', originalText.length(), processedText);

	return processedText;
}

/**
* Removes bookmarks which are in reported area already
* It helps to prevent the unexpected reporting of the duplicatedSymbolsCount markers more than once
*/
static void swiBookmarksShift(std::vector<SwiBookmark>& bookmarks)
{
	unsigned int indexFrom = 0;
	for (unsigned int indexTo = 0; indexTo < bookmarks.size() - 1; ++indexTo)
	{
		if (bookmarks[indexTo].m_text == 0)
		{
			if (indexFrom <= indexTo)
			{
				indexFrom = indexTo + 1;
			}
			while (indexFrom < bookmarks.size() &&
				bookmarks[indexFrom].m_text == 0)
			{
				++indexFrom;
			}

			if (indexFrom == bookmarks.size())
			{
				break;
			}

			bookmarks[indexTo]= bookmarks[indexFrom];
			bookmarks[indexFrom].m_text = 0;
		}
	}
}

/**
 * Programm entry point
 */
int main(int argc, char* argv[])
{
	std::vector<SwiRecord>  files(0);
	std::string commonString      = "";
	int minLength         = 100;
	int proximityFactor   = 100;
	char * ignorabaleSymbols = new char[SWI_MAX_TEXT_LENGTH];
	char * nonRegularSymbols = new char[SWI_MAX_TEXT_LENGTH];

	strcpy(ignorabaleSymbols, " \t\n");
	strcpy(nonRegularSymbols, "}");

	while (1)
	{
		char * command = new char[SWI_MAX_TEXT_LENGTH];
		scanf("%s", command);

		if (strcmp(command, "start") == 0)
		{
			// Continue search algorithm
			break;
		}

		if (strcmp(command, "exit") == 0)
		{
			// Breaking the search
			exit(EXIT_SUCCESS);
		}

		if (strcmp(command, "init_length") == 0)
		{
			scanf("%d", &minLength);
		}

		if (strcmp(command, "init_proximity") == 0)
		{
			scanf("%d", &proximityFactor);

			if (proximityFactor < 1 || proximityFactor > 100)
			{
				fprintf(stderr, "error: Proximity factor must be between 1 and 100 (inclusive)\n");
				exit(EXIT_FAILURE);
			}
		}

		if (strcmp(command, "init_ignorable") == 0)
		{
			// TODO: no ways to configure newline symbol
			scanf("%s", ignorabaleSymbols);
		}

		if (strcmp(command, "init_nonregular") == 0)
		{
			// TODO: no ways to configure hewline symbol
			scanf("%s", nonRegularSymbols);
		}

		if (strcmp(command, "init_file") == 0)
		{
			unsigned int fileLength = 0;
			unsigned int functionLength = 0;
			unsigned int textLength = 0;

			scanf("%d", &fileLength);
			scanf("%d", &functionLength);
			scanf("%d", &textLength);

			char * file     = new char[fileLength + 1];
			char * function = new char[functionLength + 1];
			char * text     = new char[textLength + 1 + 1]; // +1 for null pointer, +1 for EOF symbol

			file[fileLength] = '\0';
			function[functionLength] = '\0';
			text[textLength] = SWI_EOF;
			text[textLength + 1] = '\0';

			fread(file, 1, 1, stdin); // Consume one empty symbol
			fread(file, fileLength, 1, stdin);
			fread(function, functionLength, 1, stdin);
			fread(text, textLength, 1, stdin);

			commonString += std::string(text);
			SwiRecord record;
			record.end        = commonString.length();
			record.functionName = function;
			record.fileName = file;
			files.push_back(record);

			delete text;
		}

		delete command;
	}

	if (commonString.length() == 0)
	{
		fprintf(stderr, "error: No files defined or they are empty\n");
		exit(EXIT_FAILURE);
	}

	std::vector<SwiBookmark> bookmarks;
	const char* processedText =
		swiOriginalStringProcess(commonString, bookmarks, ignorabaleSymbols, nonRegularSymbols);
	const char* processedEnd  = processedText + strlen(processedText);

	std::sort(bookmarks.begin(), bookmarks.end());

	while(1)
	{
		int longestDuplication = 0;
		int firstInstanceIndex = 0;

		// Find the two bookmarks that have the longest common substring.
		for (unsigned int bookmarkIndex = 0; bookmarkIndex < bookmarks.size() - 1; ++bookmarkIndex)
		{
			if (bookmarks[bookmarkIndex + 1].m_text == 0)
			{
				break;
			}

			if (swiStringsEqualCheck(bookmarks[bookmarkIndex], bookmarks[bookmarkIndex + 1],
				longestDuplication, processedEnd))
			{
				const int duplicatedSymbolsCount = swiStringsCompare(bookmarks[bookmarkIndex],
					bookmarks[bookmarkIndex + 1]);
				if (duplicatedSymbolsCount > longestDuplication)
				{
					firstInstanceIndex = bookmarkIndex;
					longestDuplication = duplicatedSymbolsCount;
				}
			}
		}

		if (longestDuplication < minLength)
		{
			// Do not process too short strings
			// This is the exit from the while loop
			break;
		}

		int numberOfInstances        = 2;
		int almostLongestDuplication = (longestDuplication * proximityFactor) / 100;
		int initialIndexForScan = firstInstanceIndex;

		// // Search for duplicated strings before the current pair.
		for (int i = initialIndexForScan - 1; i >= 0; --i)
		{
			const int duplicatedSymbolsCount =
				swiStringsCompare(bookmarks[initialIndexForScan], bookmarks[i]);

			if (duplicatedSymbolsCount < almostLongestDuplication)
			{
				break;
			}
			numberOfInstances++;
			if (longestDuplication > duplicatedSymbolsCount)
			{
				longestDuplication = duplicatedSymbolsCount;
			}
			firstInstanceIndex = i;
		}

		// Search for duplicated strings after the current pair.
		for (unsigned int i = initialIndexForScan + 2; i < bookmarks.size(); ++i)
		{
			if (bookmarks[i].m_text == 0)
			{
				break;
			}

			const int duplicatedSymbolsCount = swiStringsCompare(bookmarks[initialIndexForScan],
				bookmarks[i]);
			if (duplicatedSymbolsCount < almostLongestDuplication)
			{
				break;
			}
			numberOfInstances++;
			if (longestDuplication > duplicatedSymbolsCount)
			{
				longestDuplication = duplicatedSymbolsCount;
			}
		}

		printf("info: group_start\n");
		for (int i = 0; i < numberOfInstances; ++i)
		{
			swiResultPrint(bookmarks[firstInstanceIndex + i], &files[0],
				commonString.c_str(), longestDuplication);

			// Clear bookmarks that point out to the reported area.
			const char* reportStart =
				bookmarks[firstInstanceIndex + i].m_text;

			for (unsigned int j = 0; j < bookmarks.size() - 1; ++j)
			{
				if (bookmarks[j].m_text >= reportStart &&
					bookmarks[j].m_text < reportStart + longestDuplication)
				{
					bookmarks[j].m_text = 0;
				}
			}
		}
		printf("\n");

		swiBookmarksShift(bookmarks);
	}

	delete [] processedText;
	return 0;
}