10 ms·

Design and Implementation of a Win32 Text Editor (2005)

173 points by setra 10y ago

bluedino 10y ago
Great article. Would be an interesting discussion to have with a developer canididate during an interview.
hugozap 10y ago
Mirror?
- wolfgang42 10y ago
  http://webcache.googleusercontent.com/search?q=cache:http://www.catch22.net/tuts/neatpad http://webcache.googleusercontent.com/search?q=cache:http://...
- softblush 10y ago
  https://web.archive.org/web/20161129233642/http://www.catch22.net/tuts/neatpad https://web.archive.org/web/20161129233642/http://www.catch2...
dewiz 10y ago
Perhaps add "2005" to the title?
- nacs 10y ago
  Has the cutting edge techniques for implementing Notepad changed that much since 2005?
  - maxerickson 10y ago
    It's the house style to add the year to titles from previous years.
  - imron 10y ago
    Actually yes! The Unicode text handling in Windows has been significantly revamped from the APIs listed in these articles, as has the text rendering APIs which now go through DirectX.
    - batina 10y ago
      You can still use Uniscribe in Windows 10 but as you said it has been superseded by DirectWrite (used in Microsoft Word, WPF, etc).
      - imron 10y ago
        Yep, you can definitely still use it all, just like you can continue to use the even older APIs too - hooray for backwards compatibility. Just pointing out that the technology for Notepad has actually changed and improved since 2005.
wyager 10y ago
I don't see it mentioned in the text, but essentially the best-known data structure for representing large amounts of random-location-editable text is called the Rope. It's based on my favorite data structure, the Finger Tree, which has very impressive asymptotic performance characteristics over a huge range of intuitively (but not actually) expensive operations. It doesn't require you to break the text up into lines and hope for short lines or anything; you can insert, split, cut, paste, delete, whatever, with at worst O(log(n)) for "expensive" operations (like beginning to edit at a random point in the text, or cutting/pasting a huge chunk of text) and O(1) for "cheap" operations (like insertion/deletion of a character after you've started editing). It's based on a finger tree containing densely packed byte or UTF arrays (strictly speaking, this isn't necessary, but gives an appreciable constant time/memory speedup), and tree nodes are tagged with the length of all text underneath them. Here's an implementation specialized to byte arrays (not UTF-8). https://hackage.haskell.org/package/rope https://hackage.haskell.org/package/rope
- greglindahl 10y ago
  Given the desire for syntax highlighting and other demanding features in modern editors, it would be fun to see a comparison of "piece chains" or "the rope" with a gap buffer, which is the data structure historically used by Emacs. Sure, it's easy to see how different editing itself fares with these various data structures, but what about syntax highlighting?
  - codygman 10y ago
    There exists a phenomenal paper comparing ropes, gap buffers, and piece chains I cannot recall. There is a lua editor called Vis that uses piece chains which the paper suggests is best.
    - taeric 10y ago
      I would be very interested in if you could find that paper. Briefly reading on piece chains, I can't see how they would be the preferred way, sadly. (I'm assuming the failing is on me, hence the sadly.) Even gap buffers seem somewhat odd to me. I'm assuming the gap is only created/inserted when text is typed. Not just on moving of the point/cursor. That, or thinking longer, I suppose that the contents of the file can be out of sync while the buffer is not saved. So, probably possible to easily insert and shift a gap periodically into the text, as needed. (I'm envisioning the rotate memory code from Programming Pearls to keep the gap where you want it.) Similarly, the piece chain (which, I should add that googling that was a piece of hilarity), if it is possible to "snapshot" the base of the piece chain every so often to what is on disk, it would just mean inverting some of the change pieces. Which doesn't sound too hard.
dingdingdang 10y ago
Honestly very good article - are anyone aware of a similar type of tutorial for OSX that covers small to huge text file editing?
- valleyer 10y ago
  TextEdit, the actual editor that ships on macOS, is open source. https://developer.apple.com/library/content/samplecode/TextEdit/Introduction/Intro.html https://developer.apple.com/library/content/samplecode/TextE... Nearly all of the load is shouldered by the Cocoa text system.
  - imron 10y ago
    And it's not very good with huge text files and long lines.
    - dingdingdang 10y ago
      Yep, this is the problem, just because its bare metal sys-call wise does not mean it does partial/incremental loading correctly! :/
      - imron 10y ago
        Incremental loading is one of the things I dislike about the native cocoa text/document components - especially if you have a large file and want to scroll to the end. Scroll and wait. Scroll and wait. Scroll and wait. You can use the same basic techniques presented in the original article for loading large files instantly on macOS (I did), and then use Core Text APIs for rendering the actual text instead of the Win32 API calls. You need to use Core Text APIs over the NS equivalent, or at least you do if you want to handle text with long lines, because all the NS* eventually gets down to Core Text and one of the functions (I forget which one, but likely CTTypesetterCreateWithAttributedString) becomes noticeably sluggish when processing long lines (think > 10k characters per line), especially if most of that text might not even be appearing on the screen. At least it does for Chinese, not sure about other scripts. However if you break that same 10k chunk up in to a bunch of smaller text chunks first, and stop once you get off the visible screen, the combined time of processing each chunk is significantly less than processing them as a single piece of text. Checking my source code, I've currently got the maximum length to split on set at 1,024 and that works quite well.
maxxxxx 10y ago
I once wrote an HTML WYSIWYG editor for Windows 3.1. I had bid for a project but didn't check that the library I wanted to use would actually work with 16 bit Windows. So I had to do it myself. It took me several all-nighters to make it work. The hardest part was rendering in a performant way. One page was fine but with several pages it got horribly slow. I had to invent some caching to avoid recalculating the layout all the time. Definitely one of the most educational things I have ever done.
iask 10y ago
I always enjoy reading articles like this. I am a .Net developer and recently did an application for parsing some of our B2B PDF documents (different vendors, different document structures) and loading the data into a backend db. It was an interesting project. Text parsing becomes so simple once you have a logic. And there are so many things to watch out for e.g. Different versions of PDF are structured differently, some vendors had HTML documents, flat text, some totally not in any structure. Thanks for sharing!
- bbernoulli 10y ago
  What did you use for parsing PDFs?
  - iask 10y ago
    I used itextsharp library to convert the PDF files to text and then go from there. Once you have the file in text format you can then determine how to parse - that would be the structure you will see all the time for that document. In my case, each document differ by vendors, hence different parsers. That's the gist of it.
imron 10y ago
This is a really great series of articles, and I used a number of the techniques mentioned in them for a program I made - https://www.chinesetextanalyser.com/ https://www.chinesetextanalyser.com/ The files opened by the program are read-only, so I didn't need to look in to or worry about piece-chains, but it's nice to be able to open multi-gigabyte files, with highlighting, and scroll around instantly to anywhere in the file, and have very low CPU and memory usage.

173 points by setra 10y ago

bluedino 10y ago

Great article. Would be an interesting discussion to have with a developer canididate during an interview.

hugozap 10y ago

Mirror?

wolfgang42 10y ago
http://webcache.googleusercontent.com/search?q=cache:http://www.catch22.net/tuts/neatpad http://webcache.googleusercontent.com/search?q=cache:http://...
softblush 10y ago
https://web.archive.org/web/20161129233642/http://www.catch22.net/tuts/neatpad https://web.archive.org/web/20161129233642/http://www.catch2...

dewiz 10y ago

Perhaps add "2005" to the title?

nacs 10y ago
Has the cutting edge techniques for implementing Notepad changed that much since 2005?
- maxerickson 10y ago
  It's the house style to add the year to titles from previous years.
- imron 10y ago
  Actually yes! The Unicode text handling in Windows has been significantly revamped from the APIs listed in these articles, as has the text rendering APIs which now go through DirectX.
  - batina 10y ago
    You can still use Uniscribe in Windows 10 but as you said it has been superseded by DirectWrite (used in Microsoft Word, WPF, etc).
    - imron 10y ago
      Yep, you can definitely still use it all, just like you can continue to use the even older APIs too - hooray for backwards compatibility. Just pointing out that the technology for Notepad has actually changed and improved since 2005.

wyager 10y ago

I don't see it mentioned in the text, but essentially the best-known data structure for representing large amounts of random-location-editable text is called the Rope. It's based on my favorite data structure, the Finger Tree, which has very impressive asymptotic performance characteristics over a huge range of intuitively (but not actually) expensive operations. It doesn't require you to break the text up into lines and hope for short lines or anything; you can insert, split, cut, paste, delete, whatever, with at worst O(log(n)) for "expensive" operations (like beginning to edit at a random point in the text, or cutting/pasting a huge chunk of text) and O(1) for "cheap" operations (like insertion/deletion of a character after you've started editing). It's based on a finger tree containing densely packed byte or UTF arrays (strictly speaking, this isn't necessary, but gives an appreciable constant time/memory speedup), and tree nodes are tagged with the length of all text underneath them. Here's an implementation specialized to byte arrays (not UTF-8). https://hackage.haskell.org/package/rope https://hackage.haskell.org/package/rope

greglindahl 10y ago
Given the desire for syntax highlighting and other demanding features in modern editors, it would be fun to see a comparison of "piece chains" or "the rope" with a gap buffer, which is the data structure historically used by Emacs. Sure, it's easy to see how different editing itself fares with these various data structures, but what about syntax highlighting?
- codygman 10y ago
  There exists a phenomenal paper comparing ropes, gap buffers, and piece chains I cannot recall. There is a lua editor called Vis that uses piece chains which the paper suggests is best.
  - taeric 10y ago
    I would be very interested in if you could find that paper. Briefly reading on piece chains, I can't see how they would be the preferred way, sadly. (I'm assuming the failing is on me, hence the sadly.) Even gap buffers seem somewhat odd to me. I'm assuming the gap is only created/inserted when text is typed. Not just on moving of the point/cursor. That, or thinking longer, I suppose that the contents of the file can be out of sync while the buffer is not saved. So, probably possible to easily insert and shift a gap periodically into the text, as needed. (I'm envisioning the rotate memory code from Programming Pearls to keep the gap where you want it.) Similarly, the piece chain (which, I should add that googling that was a piece of hilarity), if it is possible to "snapshot" the base of the piece chain every so often to what is on disk, it would just mean inverting some of the change pieces. Which doesn't sound too hard.

dingdingdang 10y ago

Honestly very good article - are anyone aware of a similar type of tutorial for OSX that covers small to huge text file editing?

valleyer 10y ago
TextEdit, the actual editor that ships on macOS, is open source. https://developer.apple.com/library/content/samplecode/TextEdit/Introduction/Intro.html https://developer.apple.com/library/content/samplecode/TextE... Nearly all of the load is shouldered by the Cocoa text system.
- imron 10y ago
  And it's not very good with huge text files and long lines.
  - dingdingdang 10y ago
    Yep, this is the problem, just because its bare metal sys-call wise does not mean it does partial/incremental loading correctly! :/
    - imron 10y ago
      Incremental loading is one of the things I dislike about the native cocoa text/document components - especially if you have a large file and want to scroll to the end. Scroll and wait. Scroll and wait. Scroll and wait. You can use the same basic techniques presented in the original article for loading large files instantly on macOS (I did), and then use Core Text APIs for rendering the actual text instead of the Win32 API calls. You need to use Core Text APIs over the NS equivalent, or at least you do if you want to handle text with long lines, because all the NS* eventually gets down to Core Text and one of the functions (I forget which one, but likely CTTypesetterCreateWithAttributedString) becomes noticeably sluggish when processing long lines (think > 10k characters per line), especially if most of that text might not even be appearing on the screen. At least it does for Chinese, not sure about other scripts. However if you break that same 10k chunk up in to a bunch of smaller text chunks first, and stop once you get off the visible screen, the combined time of processing each chunk is significantly less than processing them as a single piece of text. Checking my source code, I've currently got the maximum length to split on set at 1,024 and that works quite well.

maxxxxx 10y ago

I once wrote an HTML WYSIWYG editor for Windows 3.1. I had bid for a project but didn't check that the library I wanted to use would actually work with 16 bit Windows. So I had to do it myself. It took me several all-nighters to make it work. The hardest part was rendering in a performant way. One page was fine but with several pages it got horribly slow. I had to invent some caching to avoid recalculating the layout all the time. Definitely one of the most educational things I have ever done.

iask 10y ago

I always enjoy reading articles like this. I am a .Net developer and recently did an application for parsing some of our B2B PDF documents (different vendors, different document structures) and loading the data into a backend db. It was an interesting project. Text parsing becomes so simple once you have a logic. And there are so many things to watch out for e.g. Different versions of PDF are structured differently, some vendors had HTML documents, flat text, some totally not in any structure. Thanks for sharing!

bbernoulli 10y ago
What did you use for parsing PDFs?
- iask 10y ago
  I used itextsharp library to convert the PDF files to text and then go from there. Once you have the file in text format you can then determine how to parse - that would be the structure you will see all the time for that document. In my case, each document differ by vendors, hence different parsers. That's the gist of it.

imron 10y ago

This is a really great series of articles, and I used a number of the techniques mentioned in them for a program I made - https://www.chinesetextanalyser.com/ https://www.chinesetextanalyser.com/ The files opened by the program are read-only, so I didn't need to look in to or worry about piece-chains, but it's nice to be able to open multi-gigabyte files, with highlighting, and scroll around instantly to anywhere in the file, and have very low CPU and memory usage.