code call-graphs for warzone

[kage]

to help me figure out the warzone code, as well as other large codebases, in less time, i've looked into call-graph related utilities. thus far, the best one i was able to find that actually worked is egypt (there was one called codeviz which i couldn't get any other alternatives to build on modern linux system, and most other alternatives have no remaining mirrors). anyways, egypt was exceptionally good for making callgraphs, and could handle an arbitrary number of input files, but was primarily intended for just one or a few input files at a time, and sorting out a codebase as large as warzone's produced unreadable graphs.

good news: i've been modifying warzone to be able to split up and organize call graphs in a number of different ways, with the intent that egypt be able to usably handle arbitrarily large code bases (which means that it'll, in theory, help me, and anyone who's interested, in learning the warzone source more quickly). here's some of what my modified version was able to do a couple of subversions ago:

http://www.last-ditch.net/egypt-warzone ... tfiles.png

this one used egypt with an output mode that is a variation off of the original and only output mode: in this one, 3 input files were passed to egypt, and it seperately displays all defined functions within those files, as well as, in this case, any calls that go to any other function defined within the input files. this is obviously a bit unwieldly, as the calls are already getting ambiguous (many lines clumped together) with only 3 input files, and warzone has 185 *.c (as of the last time i checked out svn).

so, a variation on this output mode that i'm in the process of coding will allow for the creation of one graph per input file, but with some of the benefits of the multiple-input-file graphs (such as showing which file each called function resides within).

http://www.last-ditch.net/egypt-warzone-perfunction.png

this output shows one graph per each function defined within the specified codebase. any dotted lines you see represent "indirect" calls as defined by gcc: they're functions that aren't called by a symbol reference (such as calling the function explicitly), but are executed by address, such as in the case of a callback. any functions that have a dashed ellipse around their name is supposed to be a function that is not defined within the specified codebase (malloc, as you might know, isn't defined in any part of the warzone source code). there appears to be a bug, since many functions are "dashed" that appear as though they're warzone-related (such as "mapHeight" and "mapWidth"), but i think that bug is fixed by now.

i'm planning on making a way to output hot-linking svg, or, more probably, html files with corresponding png's and image maps, which would allow you to click on a function and see that function's own graph (which would allow you to navigate the whole codebase with much greater ease). there's also the possibility of integration with doxygen comments and integration with gprof, but i'm not going to think about those right now.

if anyone really cares, i'll, of course, be making my modified version of egypt freely available under the same license as egypt (which is itself under the same license as perl), but at the moment, it's too unstable and otherwise unusable -- if you really want it in its present state, you may have it, but don't expect me to respond very quickly to the couple hundred questions you email me.

[Rman Virgil]

* I certainly don"t have the proficiency of any of the coders on this project, nonetheless, with my modest knowledge I percieve what your doing as a breakthrough modus operandi. Just seeing these 2 mappings has dispelled some of the fog in identifying relationships that underlie in-game behaviours I've observed (for lack of a better way of phrasing it) and wondered about their place in the overall structure or as I have thought of it - the WZ archetechtonic.

* Simply, a sweet code forensic.

[DevUrandom]

You know "dot"?

If you are allready into modifying that tool: What about displaying the file with the function in the 2nd diagram?
The 1st wouldn't be that bad if the diagram would also be going "down" instead of just "right". Would make much more space available.
Problem with those graphs is mostly that the tool wants to put too many functions into too little space, which clutters the diagram and makes it unreadable.

[Rman Virgil]

.........

Problem with those graphs is mostly that the tool wants to put too many functions into too little space, which clutters the diagram and makes it unreadable.

* A variant of HyperText perhaps ?

* Not so original a thought - the "Principia Cybernetica Project" made use of it a decade ago.

* System Dynamics Modeling simulations that model economies, ecologies, etc. comprehensively (& dealing with the positive & negative feedback loops in an open dynamic system) manage to display relationships with a crystaline elegance.

* Makes me wonder what the "Humane Genome Project" uses for graphing-mapping a humane genome...... certainly astronomically more complex than the WZ source.

[kage]

yes, i know dot.

If you are allready into modifying that tool: What about displaying the file with the function in the 2nd diagram?

actually, this makes me realize how old that second graph is... displaying the filename of the source file in which the function was defined, as well as the name of the function which the graph is displaying (to prevent any confusion, since that particular output mode can display the callers of that function, or the "ancestors", so to speak) has been a part of the output for weeks. that part of the egypt code isn't usable right now (under reconstruction), so i'm not going to have any good examples of this for at least a little while.

The 1st wouldn't be that bad if the diagram would also be going "down" instead of just "right". Would make much more space available.

agreed. if not only because people are more used to scrolling down instead of to the right, here's a more vertical version, which, in all ways, seems better. you'll still notice that, like the previous version, it flows in a semi-diagonal layout, but there's no easy hack to get past this that i know of, but then i've never really cared enough to look. in either case, i'll say once again, that this isn't at all representative of the final version.

Problem with those graphs is mostly that the tool wants to put too many functions into too little space, which clutters the diagram and makes it unreadable.

yep. big issue with the graphviz algorithm. the dot language specifies a whole lot of ultra-reliable ways to unclutter nodes, but as of yet, the algorithm doesn't do much in the way of uncluttering edges (the lines between nodes), either because of lack of effort, or because of the inevitable fact that it'd transform an exceptionally fast algorithm into a really damned slow one (several dozen orders of magnitude slower). in the above graph, i created the graph with the concentrate attribute set to true -- that alone did remove almost all problems with edges becoming ambiguous, but there are still a few problem areas. since the output methods i intend to use will result in signifigantly simpler graphs, it should be even less of an issue once i'm done.

as an example of my mods vs the original egypt -- for the hell of it, i had the original egypt process the entire warzone codebase and pipe it to fdp (the only one of the graphviz utils that could handle a graph of this complexity from a memory-usage standpoint), and after 55 minutes of processing on a 2 ghz athlon 64 proc, it spit out a 17 mb png in which no edge, node, or character of text could be made out (pretty much 90% of the image was black) -- that's all 68,910 function calls in one 37,000x28,000 image. i could have messed around and made it so that the nodes didn't overlap, but it'd have taken days of processing, and definitely wouldn't have been only 17mb, nor would it have been usable in any way.

on the added-in graph-per-function output mode, the entire warzone codebase is represented with about 4500 very easy to understand graphs (4475 functions defined in the warzone source, at least according to gcc, as bizarre as that sounds). in the graph-per-source-file mode, there'll be 185 graphs, though not containing as much detail per graph. both types of graphs used in conjunction should give a relatively quick overview of warzone -- the per-file graphs could be used to figure out where you need to start if you want to change something specific, and the per-function graphs could be used to figure out how the chunk of warzone you're interested in really works.

* Makes me wonder what the "Humane Genome Project" uses for graphing-mapping a humane genome...... certainly astronomically more complex than the WZ source.

your genome perhaps... i'm not a very complex life form -- as i remember, the university of california, berkeley, wrote a book on me entitled "behavioral modification: reprogramming kage in 23 easy steps" (it was #1 on the childrens' best seller list for 8 consecutive weeks).

[Rman Virgil]

Kage wrote:....


your genome perhaps... i'm not a very complex life form -- as i remember, the university of california, berkeley, wrote a book on me entitled "behavioral modification:
reprogramming kage in 23 easy steps" (it was #1 on the childrens' best seller list for 8 consecutive weeks).

............

* Actually, according to my research, that was the Readers Digest single volume edition which followed the layout of the ever popular "Idiot & Dummy" self-help books (making use of some sort of reverse fractal filter algorithm per urban legend) but has been out-of-print for some years  and trying to get a dog-eared used copy has been well nigh impossible even through Amazon's vast partner network across the planet..

* Instead I've had to resort to reading the only slightly expurgated 16-volume edition put out by Brittanica Press in partnership with UC Berkley Press which has been over-stocked since publication & can be had in bargain-bins along Telegraph Hill books stores (like Moe's) for a buck a volume.

* It's been slow-going I must confess and daresay it is doubtfull I'll finish before years end.

* I can only wonder wistfully, much like a sad clown, the pleasures of reading instead the Caldecott Award winning zippy-paced, prose poetry of the single volume fully illustrated "Kage".

* Well then, hope tends to spring eternal in warzones throughout history (new roadmaps to progress, & the like)..... much as the Resurrection to this day abides through difficult passages frought with inherent uncertainty. That said, we'll leave gospel truth in any secular realm to the cruel shoes of humorless pundits.

- rv 

[Rman Virgil]

* On a more practical arc....

* Obviously this proposition has captivated me and perhaps my previous correlation were a bit too far afield and abstract.

* Ergo what follows -

* "Flight Gear" is one of my favorite Open Source Games - it is a pretty awesome flight simulator even at this formative stage.

* There is a utility for FG called "Atlas" that is essentially a world map of all the airports on the planet with flight paths between them plus longitude and latitude headings, and more.... in other words, a dense clustering of information that rendered can be an unreadable blob.

* If you dl the "Atlas" HERE you can see for yourself how this issue is dealt with dynamically so that it is all useable information graphically rendered.

[cybersphinx]

I don't know what can be installed on this server, but having a tool like gonzui or something similar would be quite nice to navigate the code online.

[DevUrandom]

It would be cool to get this server to weekly generate DoxyGen docs from the sourcecode... (DoxyGen has also a searchengine integrated, which can optionaly be enabled.)

[cybersphinx]

Gonzui is not just a search engine, though the website might make you believe that. You can also browse source code with it. Here's a short article about it, and here is an example (unfortunately there's mostly small ruby packages, but it should be sufficient to see how it works). Go to line 41 and click on "set_item", then you see where this function is called. Gonzui has native SVN support, so with a suitable post-commit hook we'd always have a browsable, up-to-date online code repository. There's also lxr, though that seems abandoned and more difficult to set up.

[kage]

you have to wonder why more ide's don't do that kind of stuff really well -- even eclipse isn't great when it comes to quickly seeing the definition of a referenced function -- it makes you open that file to see it. odd thing i noticed about the ruby example: why is it that when you hold your mouse over any identifier, a tooltip comes up that displays that line? the searching and navigating stuff are great, but the tooltip bit seems exceptionally worthless to me.

[DevUrandom]

AFAIK DoxyGen does the same thing, but with additional call-graphs and documentation support... Or did I miss something about Gonzui & Co.?

[Rman Virgil]

Gonzui is not just a search engine, though the website might make you believe that. You can also browse source code with it. Here's a short article about it, and here is an example (unfortunately there's mostly small ruby packages, but it should be sufficient to see how it works). Go to line 41 and click on "set_item", then you see where this function is called. Gonzui has native SVN support, so with a suitable post-commit hook we'd always have a browsable, up-to-date online code repository. There's also lxr, though that seems abandoned and more difficult to set up.

* Inspired by your "gonzui" suggestion to a crash course on these source code nav tools (inc Web based services like Codase, Krugle, Koders, etal) ..... I can now see that my instinctive, but uninformed, initial suggestions were actually tracking with what is out there.... nice to have that feedback and not think I was totally off base.

* But more to the point - as far OSS freebies "gonzui" seems to touch all the prerequisites of the project quite effectively.

* As far as proprietary tools - Western Wares "CC-Ryder" is pretty awesome... I'm using the fully functional demo (only time constrained) and it has quite an impressive feature set. But of course I am not gonna spring 5 Benjys for a licence as sweet as it is. Still interesting to see the full scope of what can be done to nav and doc the source - very inspireing, personally.

AFAIK DoxyGen does the same thing, but with additional call-graphs and documentation support... Or did I miss something about Gonzui & Co.?

* Far as I can tell Doxygen does not support importing the SVN repositiory like Gonzui.... Gonzui can dynamically search the code base as a whole or in sub-assemblies and generate corresponding real time docs, inc hierarchical trees, (w/refrsh)..... Doxygen can be set to process the original source to the end of extracting docs (there or not), inc graphs, (with some limitations stated in the To-Do and Trouble-shooting sections) which can then be studied afterward - not quite the same, as I can see.

* To my pea-brain, "CC-Ryder" can do what both do, and then some. 

* BTW... I found the following archived article at Slashdot quite instructive and well worth a few minutes of time to check-out: Reverse Engineering Large Software Projects ...seeing the refs to "BlackIce" and "Rational Purify" brought back mems... and of course Doxygen and Gonzui are also mentioned. Come to think of it, Doxygen (instead of PERCEPS) was recommended in the same breathe as Subversion (instead of CVS) within weeks of the source release, how many years ago now at RTS.net. Why Subversion was followed through on (& Berlioz instead of SF or a private server) and Doxygen passed-over in favor of nothing, I cannot say - one of those cyber mysteries, perhaps, but interesting how it has come full circle nonetheless.

[DevUrandom]

I don't see where DoxyGen fails... You can easily setup a Cronjob which downloads the sourcecode from SVN and creates the docs afterwards.
And generating the docs on every commit would be total overkill, as the code doesn't progress fast enough to justify such a load for the server. And several commits are just very small fixups which wouldn't change the structure at all.
And in the end the tool, whatever it is, has to be used by those who do the actual coding...

[Rman Virgil]

And in the end the tool, whatever it is, has to be used by those who do the actual coding...

* Just a salon-like conversation, bro. (Salon as in 19th century occassions to enjoy well-rounded wit, intelligence & eloquence.... not to be confused with saloons were much jabber goes on of a different sort )

* I didn't say Doxygen "fails", it's just different functionalities. I actually recommended the use of Doxygen almost 3 years ago (thread still there at RTS.net **) when the source was released... so it aint new to me nor does it really matter what is decided on as long as those who use it are happy with its functionality.... certainly better than nothing, I would hazard to say.

** To be precise October 26, 2004.... before source release, actually - HERE  ... 2-3 years ahead of the curve seems to be the norm.