How to find all mutual friendships in large C++ source tree?

In a large C++ source tree, with about 600 or so classes 开发者_JAVA技巧defined, I want to find all pairs of classes where each declares the other a friend.

There are many cases of one class being a friend of another, too many to make it worth wading through a simple grep result.

---

You could implement a kind of triple loop here; the algorithm could be as follows:

1. First loop: find all classes who have friends, and remember the name of the friend and the name of the actual class;
2. Then run inner loop for all the classes and find a class with the name of the friend from step 1.
3. Then run another inner loop through all the friends of the class found at step 2. If you have found class with name from step 1 - voila - they're mutual friends.

I believe Perl and regexes are the best tools for such things.

P.S. sure this approach has its limits, because not everything in C++ could be parsed with regex (using namespace stuff is the first thing came into my mind). But, to some extent, this is working approach, and if you don't have alternatives, you could give it a try.

EDIT: An idea came to my mind today in the morning, while I still was lying in my bed. :) The idea is quite simple and clear (like all morning ideas): use SQL! Naturally, imagine you have a table of classes with 2 columns, where first column is class name, and second column is it's friend`s name. Say, something like this:

ClassName FriendName
C1        C2
C1        C3
C1        C4
C2        C1
C2        C8
C3        C1
C3        C2
...       ...

Then you can run a simple query against it. Say, something like this (sorry, I don't have any SQL DB handy, so have not checked the query, but I hope you'll got the idea and implement it as needed:

SELECT ClassName as c, FriendName as f FROM T
WHERE c in 
  (SELECT FriendName FROM T
     WHERE FriendName = c AND ClassName = f)

The idea behind this variant is that we should employ those tolls which exactly fit the task. What can compare to SQL when you need to crunch some sets of data?

---

I) Some elegant ways:

1) Doxygen ( http://www.doxygen.nl/ ) might be able to give you what you need. (If it doesn't already give this information, you could hack Doxygen's C++ parser a bit to get what you need).

2) There are also existing ANTLR grammar files for C++ as well.

II) Quicker way (perhaps the right approach here):

Regex should just be fine for your purpose as others suggest. Consider the following pseudo code:

rm -f result_file;
foreach source_file
do
  sed 's/[ \t\n]\+/ /g' $source_file >  temp_file;  ## remove newlines, etc
  grep -o -P -i "friend [^;]*;"  >> result_file; ## you can improve this regex for eliminating some possible unwanted matches or post-process result_file later
done

Now you have all friend relations in result_file. You can remove "friend functions" using another simple regex and/or process the result_file further as per needs.

---

This answer is similar to @user534498's, but I'm going to go into a bit more detail, as the suggestion "parse C++ with regex" is so insane, I don't think it bears consideration.

I also don't think you're going to find an automated tool which can already do this for you. If this were managed code land, I'd be suggesting something like Nitriq, but I don't think anything like that works for C++.

If you're not worried about nested classes, I think you can construct parings of classes to friends without too much difficulty. You can find instances of the keyword class, followed by curly braces, and within the curly braces look for friend statements. That should, without too much difficulty, give you a listing of which classes have which friends.

Once you've done that, you can check for duplicate references easily. (Depends on the language you're using... if you're in C++ then you'd put your results in a std::multimap with the keys being class name and values being the friends)

I suppose this is similar to what @Haspemulator is suggesting ... but my point is that it will probably be easier to split out the parsing, then implement the circular ref checking in terms of sets or maps, then it will be to try to intertwine these operations.

---

Use perl or python or c++ regex to parse all files, record all class-friends pairs. The matching should be trivial for these kind of 600 pairs