Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Background

In a recent school software engineering module, I needed to developed a static program analyzer. Given a ficticious programming language source code, I need to analyze it, then the user can query about the program, eg. what statements uses this variable, which modifies, statements affected by another etc.

Possible link with IDEs

At first, it sounded very useless... it was a software engineering module but in reality more like some theoretical programming language module instead. However, some of these functionality could be what goes into the IDE's we use. So I was wondering how might some common IDE functionality be implemented.

Static Program Analyzer (how to make it dynamic/realtime)

In the project, we designed the analyzer for a static program ... but who needs that? In the IDEs we use, everything is near realtime, as we type, syntax highlighting is done, the IDE's analyzes the code for errors, variables that are not used, etc. How is it done so efficiently?

In the static analyzer, there is a parser that parses the source, builds AST & CFG. This can then be used to see if a variable is used by some statement etc. In reality what can be cached are cached. There are many areas that can be optimized, but I am not sure any (I can think of) can make it realtime.

Some problems I can see are:

  • As we type, things are incomplete, this will lead to a parsing error, but a real IDE somehow is smart enough to know where to continue parsing.
  • As we type, things change very rapidly, we cannot parse the entire program. Even if I make the parser smart enough and parse only the changed line, I need to update my AST/CFG/expire relevant cache etc.

In a real IDE, I don't see that CPU usage spikes as we type etc. How is it done?

Some might suggest looking at the source of some open source IDE eg. Eclipse or Netbeans. But I expect it to be really hard to understand such a big app by just reading code. What I hope to get is a high level idea of how might a simple IDE (and some of the commonly used features) be implemented, a simple paragraph or some pseudocode etc. Some common features I can think of now are

  • Refactoring (something like a contextual find and replace)
  • Find usages
  • Go to definition
  • Auto complete (find all possible classes, variables, methods in context)
  • Syntax highlighting

For static code, some might be trivial to implement, but an IDE is (near) realtime

share|improve this question

closed as not a real question by Jimmy Hoffa, MichaelT, gnat, GlenH7, Bart van Ingen Schenau Apr 18 '13 at 15:23

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
I believe that Xcode uses the real clang fronted to parse the code and form an AST. I think that at some time there was a plan to have VC++ do the same thing (use the real compiler's frontend that is, not use clang :-p). –  Will Apr 18 '13 at 14:15
1  
Take a look at this section of the clang webpage. I believe it hints that the terms "Incremental Compilation" and "fuzzy parsing" are something you could look at. –  Will Apr 18 '13 at 14:16
    
possible duplicate of What are the most impressive tricks an IDE could pull off with the code? –  gnat Apr 18 '13 at 14:29
5  
Do you think you could narrow the scope of this question? The "how might something work" question is very broad and can have dozens of right answers. As such, this doesn't fit into the Q&A format that is designed to handle questions that have one right answer. If you can identify a specific problem that you are having designing, that could help narrow the scope. There is nothing wrong with asking several distinct questions on different problems for the same project (compared to one question that tries to get them all). Consider also asking in chat for the more nebulous aspects. –  MichaelT Apr 18 '13 at 14:31

2 Answers 2

I think you are overestimating the difficulty of source code validation. Parsing a single source file that is already loaded into memory takes a tiny fraction of a second, unless it is huge. Parsing the entire file works fine (and is what most IDEs do, I would guess). Only a single file is being edited at a time, so only that file needs to be parsed.

Source code validating IDEs wait until you are idle for a specified length of time before analyzing the source, so you don't see errors or experience slowness while you type.

Parsing only the current line simply would not work, because the contents of the current line cannot be interpreted without the context of the entire file (the last line might have the closing brace of a function that started at the beginning of the file, for example).

Important information from all the files in your project (variables, subs, methods, etc.) is stored, and the entries relating to the current file are updated whenever the source code is parsed.

As for the other issues you mentioned:

  • Refactoring would necessarily involve the syntax tree rather than a mere find and replace. Because a given piece of code can't be understood without all the other code.

  • "Find usages" need not be more than a glorified search function.

  • "Go to definition" and auto-complete are simple if you maintain project-wide information on variables, subs, etc., as I mentioned above.

  • Syntax highlighting is done in different ways. If you are already validating the source, it is a simple matter to use that information to also do the highlighting, because you know what everything is. But other tools that are not that sophisticated use simplified rules for the highlighting, which get it right most of the time.
share|improve this answer

The IDE's user can only do so much. They can only edit the current file, most IDEs only have one cursor etc. A source code file is usually measured in kilo bytes, not that big a deal to process in real time. The cursor is only in one function, class, whatever definition at a time, so you can scope its impact on the program fairly easily. Also since you know what was after the cursor before the user started typing assume its AST is unchanged until the user has made a complete valid change.

For instance if you were going to make go to definition \ find usages functionality, how would you do it? It would be easy, build a table that links definitions and usages. When the user updates a line to define something new, create a new entry in the symbol table and check the usages of unknown symbols for the newly defined symbol. If the user modifies a line to use a symbol update the table with a new entry representing that usage.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.