Data structures for 'structure editor'

1

  1. I admit this is more of a data structure question than a Rust question, but I hope the community will allow it.

  2. In traditional dev, we edit code in a buffer, save, then the compiler/interpreter slurps the file, parses it, type checks it, and compiles/runs it. For a moment -- please forget Vim / Emacs / IntelliJ. In an alternative world, we could imagine specialized editors that operate directly on the Abstract-Syntax-Tree level. In such a case, we would need a specialized editor for every file format, and the editor should ensure that the "code" was (nearly) always a valid AST (a few nodes may be invalid and highlighted in red).

  3. Consider the problem of building a 'structure editor' for a scheme/lisp. It might operate somewhat like ParEdit: The Animated Guide to Paredit . ParEdit, however, still operates on emacs buffers.

  4. What would be the right data structure for a paredit-like "structure editor" ?

  5. Three options seems to be:

(1) flat-flie/buffer ==> no real benefit, seems like we are just doing parsing all the time

(2)

pub struct Sexp {
  Cons(Rc<Sexp>, Rc<Sexp>),
  Number(..), String(..)
}

(basically use the "in memory structure" as the representation); this has the problem that it is non-trivial to "point" to part of the code. In (1), it is easy to say "runtime error caused by line 2, column 5". In this case, we just have a Rc to some Sexp in memory.

(3) A third option is to "flatten" the "sexp tree" into a table of nodes, this would be something like:

pub struct FlatNode {
  Cons(u32, u32), Number(..), String(..)
}
code = Vec<FlatNode>

===

Question: has anyone here built an "abstract syntax tree structure editor" ? If so, what internal data structure did you use? (Suggestions of books / articles / ... very welcome).

Thanks!

2

I can't say I've ever built an AST structure editor, but if you squint a bit, this is quite similar to other applications where the state of the world contains lots of different types of objects which can be modified over time.

If you want to take a different approach you may want to see how this is handled in the game industry (ECS, etc.). It may also be useful to check out other IDE-related projects like .Net's Roslyn or rust-analyzer to see how they handle the AST.

2 Likes
3

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.