Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Explore using stack graphs for better code search / navigation / context / repo map / etc #742

Closed
0xdevalias opened this issue Apr 5, 2024 · 12 comments
Labels
agent framework Strategies for prompting, agent, etc architecture Related to architecture, including frontend and backend enhancement New feature or request severity:low Minor issues, affecting single user Stale Inactive for 30 days

Comments

@0xdevalias
Copy link

Not really a feature request per se, but just wanted to share some info/references/libs that I've been collating recently RE: stack graphs, and how they can be used for better 'code navigation awareness'/etc; may be useful/interesting for this project:

Stack Graphs (an evolution of Scope Graphs) sound like they could be really interesting/useful with regards to code navigation, symbol mapping, etc. Perhaps we could use them for module identification, or variable/function identifier naming stabilisation or similar?

  • https://github.blog/changelog/2024-03-14-precise-code-navigation-for-typescript-projects/
    • Precise code navigation is now available for all TypeScript repositories.
      Precise code navigation gives more accurate results by only considering the set of classes, functions, and imported definitions that are visible at a given point in your code.

      Precise code navigation is powered by the stack graphs framework.
      You can read about how we use stack graphs for code navigation and visit the stack graphs definition for TypeScript to learn more.

      • https://github.blog/2021-12-09-introducing-stack-graphs/
        • Introducing stack graphs

        • Precise code navigation is powered by stack graphs, a new open source framework we’ve created that lets you define the name binding rules for a programming language using a declarative, domain-specific language (DSL). With stack graphs, we can generate code navigation data for a repository without requiring any configuration from the repository owner, and without tapping into a build process or other CI job.

        • LOTS of interesting stuff in this post..
        • As part of developing stack graphs, we’ve added a new graph construction language to Tree-sitter, which lets you construct arbitrary graph structures (including but not limited to stack graphs) from parsed CSTs. You use stanzas to define the gadget of graph nodes and edges that should be created for each occurrence of a Tree-sitter query, and how the newly created nodes and edges should connect to graph content that you’ve already created elsewhere.

        • Why aren’t we using the Language Server Protocol (LSP) or Language Server Index Format (LSIF)?

          To dig even deeper and learn more, I encourage you to check out my Strange Loop talk and the stack-graphs crate: our open source Rust implementation of these ideas.

  • https://docs.github.com/en/repositories/working-with-files/using-files/navigating-code-on-github
    • GitHub has developed two code navigation approaches based on the open source tree-sitter and stack-graphs library:

      • Search-based - searches all definitions and references across a repository to find entities with a given name
      • Precise - resolves definitions and references based on the set of classes, functions, and imported definitions at a given point in your code

      To learn more about these approaches, see "Precise and search-based navigation."

      • https://docs.github.com/en/repositories/working-with-files/using-files/navigating-code-on-github#precise-and-search-based-navigation
        • Precise and search-based navigation
          Certain languages supported by GitHub have access to precise code navigation, which uses an algorithm (based on the open source stack-graphs library) that resolves definitions and references based on the set of classes, functions, and imported definitions that are visible at any given point in your code. Other languages use search-based code navigation, which searches all definitions and references across a repository to find entities with a given name. Both strategies are effective at finding results and both make sure to avoid inappropriate results such as comments, but precise code navigation can give more accurate results, especially when a repository contains multiple methods or functions with the same name.

  • https://pl.ewi.tudelft.nl/research/projects/scope-graphs/
    • Scope Graphs | A Theory of Name Resolution

    • Scope graphs provide a new approach to defining the name binding rules of programming languages. A scope graph represents the name binding facts of a program using the basic concepts of declarations and reference associated with scopes that are connected by edges. Name resolution is defined by searching for paths from references to declarations in a scope graph. Scope graph diagrams provide an illuminating visual notation for explaining the bindings in programs.

Originally posted by @0xdevalias in 0xdevalias/chatgpt-source-watch#11

@foragerr
Copy link
Collaborator

foragerr commented Apr 5, 2024

Would you know how Stack Graphs compare to Lossless Semantic Trees ?

@0xdevalias
Copy link
Author

0xdevalias commented Apr 5, 2024

Would you know how Stack Graphs compare to Lossless Semantic Trees ?

@foragerr Not deeply/immediately.. but from skimming that page, some things that popped up in my mind while reading it:


It talks about LSTs being 'format-preserving' compared to ASTs (eg. not losing whitespace/etc). The stack-graphs lib above is implemented on top of tree-sitter, which creates Concrete Syntax Trees (CSTs) rather than ASTs, which also capture the full data in a 'lossless' way like these LSTs seem to:

That said, I don't believe the stack-graphs themselves are aiming to be CSTs, I think they are more just the higher level 'map' between the files/dependencies/symbols/etc.


Where it talks about 'type-attributed', it seems to basically be saying that instead of just a symbol name, there is a way to know where that symbol comes from/etc; that is something stack graphs inherently handle as well.


OpenRewrite's LST lifecycle suggests that a new LST will be created for each run, as nothing is stored between recipe runs. For a small repo, it may be quick enough to do this, but for a larger repo this may introduce a time penalty. One aspect that the stack-graphs implementation specifically had a goal of was to avoid needing to re-parse the entire repo whenever any file changed; and is designed in a way that only the relevant parts need to be re-parsed/etc.


Hopefully that's helpful. I haven't dug super deep into stack-graphs myself yet in a 'practically using them' sense, but so far they have seemed like they will be a super interesting/useful tool; and the fact that these underlying libs are backed by GitHub and used for their code search/etc feels like they should be pretty 'battle tested' at scale/across a large number of languages/etc.

@rbren rbren added architecture Related to architecture, including frontend and backend agent framework Strategies for prompting, agent, etc severity:low Minor issues, affecting single user labels Apr 7, 2024
@rbren rbren mentioned this issue Apr 10, 2024
Copy link
Contributor

github-actions bot commented May 8, 2024

This issue is stale because it has been open for 30 days with no activity. Remove stale label or comment or this will be closed in 7 days.

@github-actions github-actions bot added the Stale Inactive for 30 days label May 8, 2024
@0xdevalias
Copy link
Author

Not sure stale is relevant to this?

@github-actions github-actions bot removed the Stale Inactive for 30 days label May 12, 2024
@0xdevalias
Copy link
Author

0xdevalias commented May 30, 2024

This seems to be aligned to how some other agents have chosen to go, eg.

Where they saw it as an improvement on their older method:

I understand it not being a current priority; but to discount the concept entirely (particularly without reasoning beyond seemingly personal opinion) seems counterintuitive to getting the best agent/outcome here.

Further to this, aider just set a new SOTA and topped the SWE-bench lite leaderboard with 26.3%. While all of that performance gain can't be attributed to just their smart code search/repo map'; I would happily bet that it helped it achieve it:

It will be interesting to see if they end up exploring stack graphs directly, and if that improves their performance further again:

Originally posted by @0xdevalias in princeton-nlp/SWE-agent#38 (comment)

See also:

Copy link
Contributor

This issue is stale because it has been open for 30 days with no activity. Remove stale label or comment or this will be closed in 7 days.

@github-actions github-actions bot added the Stale Inactive for 30 days label Jun 30, 2024
@0xdevalias
Copy link
Author

0xdevalias commented Jun 30, 2024

Personally I still think this would be relevant to explore; unless the thought it just to continue to leverage code context via '3rd party' integrations (eg. aider)

See also:

@github-actions github-actions bot removed the Stale Inactive for 30 days label Jul 1, 2024
@0xdevalias 0xdevalias changed the title Explore whether stack graphs may be useful in this tool Explore using stack graphs for better code search / context / repo map / etc Jul 1, 2024
@0xdevalias 0xdevalias changed the title Explore using stack graphs for better code search / context / repo map / etc Explore using stack graphs for better code search / navigation / context / repo map / etc Jul 1, 2024
@enyst
Copy link
Collaborator

enyst commented Jul 1, 2024

Personally I still think this would be relevant to explore; unless the thought it just to continue to leverage code context via '3rd party' integrations (eg. aider)

I agree, and I believe we're working on different approaches to improve this both with and without additional tools.

That said, it's not fully clear to me how actionable is this issue because it seems very generic, wouldn't it be better as one issue per proposed approach?

@0xdevalias
Copy link
Author

it's not fully clear to me how actionable is this issue because it seems very generic, wouldn't it be better as one issue per proposed approach?

@enyst I guess the perspective I opened it for is to highlight a single tool/library (stack graphs) that gives that sort of code context/navigation/etc aspect of things:

I don't know the OpenDevin project enough to know exactly where it would fit in/how to do so/etc. I was hoping to generate some discussion that might then lead to someone with more of that 'other side' of the knowledge figuring how it might better fit in; particularly given that I keep seeing places where it seems like the same sorts of tools are being re-created/etc.

In my original post I included a bunch of other relevant context/links that explain it a bit more/how it works/is used by GitHub's code navigation/etc.

Copy link
Contributor

github-actions bot commented Aug 2, 2024

This issue is stale because it has been open for 30 days with no activity. Remove stale label or comment or this will be closed in 7 days.

@github-actions github-actions bot added the Stale Inactive for 30 days label Aug 2, 2024
@mamoodi mamoodi removed the Stale Inactive for 30 days label Aug 14, 2024
Copy link
Contributor

This issue is stale because it has been open for 30 days with no activity. Remove stale label or comment or this will be closed in 7 days.

@github-actions github-actions bot added the Stale Inactive for 30 days label Sep 20, 2024
Copy link
Contributor

This issue was closed because it has been stalled for over 30 days with no activity.

@github-actions github-actions bot closed this as not planned Won't fix, can't repro, duplicate, stale Sep 27, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
agent framework Strategies for prompting, agent, etc architecture Related to architecture, including frontend and backend enhancement New feature or request severity:low Minor issues, affecting single user Stale Inactive for 30 days
Projects
None yet
Development

No branches or pull requests

5 participants