Performance idea: Partition before executing current uniform indentation search

schneems/partition ブランチの失敗しているテストから始め、現在の検索アルゴリズムによる Ripper.parse の呼び出しを追跡してください。インデントと kw/end のペアがどのように処理されているかを読み、その後、パーティショニングまたはより大きな展開ステップを既存の動作と比較してください。九千行のケースで timeout を回避しながら、構文エラー結果の品質を維持できれば完了です。

This is a failing test: https://github.com/zombocom/dead_end/tree/schneems/partition. The file is nine thousand lines and it takes a tad over 1 second to parse which means it hits the timeout.

We are already fairly well optimized for the current algorithm so to be able to handle arbitrarily large-sized files we will need a different strategy.

The current algorithm takes relatively small steps in the interest in producing a good end result. That takes a long time.

Here's my general idea: We can split up the file into multiple large chunks before running the current fine-grained algorithm. At a high level: split up the file into 2 parts and see which holds the syntax error. If we can isolate the problem to only half the file then we've dropped processing time in half (relatively). We can run this partition step a few times.

The catch is that some files (such as the one in the failing test cannot be split without introducing a syntax error (since it starts with a class declaration and ends with an end). To account for this we will need to split in a way that's lexically aware.

For example on that file, I think the algorithm would determine that it can't do much with indentation 0 so it would have to go to the next indentation, there it could see there are N chunks of kw/end pairs, it could divide into N/2 and see if one of those sections holds all of the syntax errors. We could perform this division several times to arrive at a subset of the larger problem, then run the original search array on it.

The challenge is, that we will essentially need to build an inverse of the existing algorithm. Instead of starting with a single line and expanding towards indentation zero, we'll start with all the lines and reduce towards indentation max.

The expensive part is checking code is valid via Ripper.parse, sub dividing large files into smaller files can help us isolate problems sections with fewer parse calls, but we've got to make sure the results are as good.

An alternative idea would be to use the existing search/expansion logic to perform more expansions until a set of N blocks are generated then check all of them at once. Then once the document problem is isolated, go back and re-parse only the N blocks with the existing. Algorithm. (Basically the same idea as partitioning, but we're working from the same direction as the current algorithm, just taking larger steps (which means fewer Ripper.parse) calls. However we would still need a way to sub-divide the blocks with this process in the terminal case that the syntax error is on indentation zero and the document is massive and all within one kw/end pair.