Bracket matching gives up after 4000 characters

[jameshfisher]

Steps to reproduce

1. Paste the following into a new buffer:

   (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa)
   

2. Place cursor at start of buffer.

Expected behavior

Start and end parens are highlighted.

Actual behavior

Neither paren is highlighted, as if they do not match.

Notice that deletion of any of the a characters will cause ST to behave correctly.

Since there are 4000 as in the failing test case, infer that ST "gives up" searching for a matching bracket after 4000 characters.

Suggested fix

Remove this arbitrary restriction. Use a sensible data structure to keep track of brackets if it is inefficient.

This is a real-world problem: the situations where I require bracket matching are exactly those situations where there is a lot of stuff between the brackets. Having the feature enabled only for less useful situations is stupid.

Comments

In cases where ST gives up, it is worse than simply not having the feature. It causes me to infer that my brackets are non-matching and go hunting for a non-existent error in my code, rather than causing me to think "oh well, there must be more than 4000 characters between those brackets".

The same behavior is observed with matching pairs of brackets, e.g.

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

[jbrooksuk]

I'd hardly call this arbitrary. You have to set boundaries on this kind of thing.

Why would you need to highlight 4000 different parenthesis in one line?

[jameshfisher]

@jbrooksuk

• 4000 certainly is arbitrary, in the sense that the number 4000 does not appear anywhere in the problem statement (i.e. "highlight matching brackets")
• Re "You have to set boundaries" -- why? Every buffer is always of a finite size and so it will always terminate in linear time, even with the current implementation. And if this is too slow, as I suggested, it should be easy enough to use a sensible data structure to bring the complexity down to log(N).
• Re "Why would you need to highlight 4000 different parenthesis in one line?" -- it's not just in one line. The STR I posted is the simplest case I could find, but the buggy behavior applies generally in any buffer, with any characters between the brackets, including newlines. It's very common to have more than 4000 characters between matching brackets in a file; I can provide examples if you wish. And, as I said, the usefulness of the bracket-highlighting feature increases with the number of characters between brackets -- it's precisely these cases where I need help from my editor.

[iamntz]

Actually this was discussed in forum back in the day and it's more like a feature, not a bug. It's done this way for perfomance reasons and common sense: it's pretty useless to do bracket highlight if you don't have both brackets on screen.

As a workaround, you could use BracketHighlighter plugin and adjust "search_threshold": 5000 to whatever suits you (but again, you may encounter some performance penalties)

As a side note, if you have 4000 characters between brackets, you most likely do something wrong.

[jameshfisher]

@iamntz

it's more like a feature, not a bug

What is the feature? I can see no way in which the current behavior could be called a "feature". My understanding of the word "feature" is "something the application provides in order to help the user solve some problem". What is the problem that the "giving up after 4000 characters" is attempting to solve?

it's pretty useless to do bracket highlight if you don't have both brackets on screen.

What makes you say that? I have used bracket highlighting on many occasions for work that spans one screenful. For example, to select one large block of text in order to move or remove it, I will place the cursor on one bracket, scroll to the matching bracket, and shift-click there.

"Performance", as I keep saying, isn't the issue here. A sensible data structure can be used to make the search time sublinear in order to give acceptable performance for virtually any size buffer.

if you have 4000 characters between brackets, you most likely do something wrong.

What a man does with his own buffer is his own business. I also don't know what you're trying to get at -- most files have a bracket pair of this size. For instance, you are saying that everyone that is viewing Java files is doing it wrong.

[iamntz]

@jameshfisher i feel you are a bit of harsh (to hostile).

I can't find the discussion on forums, but i'm like 99% sure that the feature is called speed. It's a little internal compromise on speed vs highlighting things that are way out of screen.

Please notice the difference between bracket matching (ctrl+m / ctrl+shift+m and which is a functionality) and bracket highlight (which is just a visual thing). First keeps working on huge files (i tested on 12k lines of legacy code and works great), second is close to useless on large distances.

If you really, really, really want the brackets to be highlighted, you can install the plugin i mentioned above and increase the treshold to a higher value. Then you can start complain about how slow sublime is.

[jbrooksuk]

I think this should be closed as it's not a bug,

[FichteFoll]

I agree this is not a bug, but I marked it as enhancement for the purpose to make it configurable, so imo it should not be closed. I can also see that making it configurable at least has advantages with little effort.

I can not comment on the usage of your "sensible data structures" because I'd have to see how it should work, how it currently works and then some benchmarks - which is also rather in scope of the developer because I can't judge on that either.

[jbrooksuk]

Still, you have to put a cap on it somewhere. There needs to be a trade off between speed and usability, and I feel 4k is a fair limit.

[jameshfisher]

@iamntz if I was too hostile, it's only because I felt I was receiving strangely hostile responses after I was good enough to submit a valid bug report. Here's the polite response I expected to receive and which I would have received on most other projects:

Thanks. The current behavior is a deliberate cut-off. While this limitation is a usability issue, the decision to have a cut-off was made to avoid cases where our linear search algorithm was unacceptably slow. If you would like to suggest or contribute a fix, please do.

It's a mistake to call "speed" a feature -- it's not. Say I were to write a program which claims to print out all the prime numbers, but stops after 7. Imagine if I were to claim that "this is a feature, not a bug -- sure it doesn't print them all, but look how fast it prints them!" An algorithm's correctness and an algorithm's performance are orthogonal characteristics.

Re bracket matching vs bracket highlighting -- cool, I didn't realize the former existed! Thanks for pointing that out. But if this exists, and it's efficient, I don't understand why bracket highlighting apparently isn't efficient -- isn't the algorithmic problem the same in both cases?

@FichteFoll re data structures, I think it should be possible to avoid the current linear search implementation (assuming this is how it is currently implemented) by maintaining a tree of all the brackets in a buffer such that we can efficiently answer the questions:

• given an index into the buffer, what is the preceding bracket?
• given an index into the buffer, what is the following bracket?
• given an index i into the buffer b where b[i] is a bracket, what is the index j of the matching bracket, if there is one?

(I think this roughly characterizes the interface that is required for bracket highlighting.)

Modifications to the buffer -- i.e. insertions and deletions of characters -- result in corresponding changes to the bracket tree.

I would be happy to expand on this and perhaps even implement it, if I were confident that it wouldn't be rejected on the grounds that "it's a feature, not a bug".

[FichteFoll]

Yeah, I can see how that could work, but I'm not to implement this sort of thing. You have to realize that this issue tracker is community-driven and neither of us is affiliated with Sublime HQ (which you seem to not know). The source code is closed and the developer doesn't talk too much - we don't even know if he actually looked at this list a single time. We're just hoping that he'll do it eventually and then magically fix everything by willpower.

Anyway, reopening since I think this is a valid issue - just not a "bug".

[titoBouzout]

While I understand @jameshfisher issue, I consider with @jbrooksuk and @iamntz that this is not a bug, nor an issue, as there is already the Package BracketHighlighter which addresses the thing discussed here with its "search_threshold" setting.

This is work for plugins/packages, I think we cannot complain ST is not open source and then open this type of issue to get already open solved problems fixed in the closed form. So I'm closing. The issue here is that ST tries to do too many things, and does not do all of these things in the best possible way, raising an incredible amount of bugs that packages already solved. We should try to push Jon to give us a Rich extensible API system instead of distracting him with this type of things. Hope you can understand.

[FichteFoll]

Afaik we are not in the position to decide what Jon should do and what not, which is why I generally keep all issues opened that contain some sort of feedback/bug report/feature request, including this one. It already has the lowest severity. If Jon decides that we don't need this one here, sure, I'm fine with closing it, but we don't know that - or did you ask him?

This definitely looks like a valid issue, it raises the concern about not being able to configure the maximum length of characters to scan and suggests a different way to allow "more dynamic" bracket matching, if that's not how it's done already. I know that there is a package that does this too, but it's likely less efficient and afaik you can't disable sublime's behaviour. Furthermore, the feature itself exists already so it would be just some tweaking instead of an entirely new thing (in which case I'd agree that just having a plugin would be enough).

[titoBouzout]

I generally agree with your comments FichteFoll, but ST does too many things, and a lot of these looks unfinished, or behave incorrectly, we don't need more of that.

We need strong and rich APIs, working correctly. Not that we decide ST future. But at least we manage this effort, and I believe the general consensus of this thread is it to believe this problem, is not important to get from the main developer's time. I must recognize there are some other issues open in the lines of this one.. and you expend a lot of time and effort already in this repository.. so well, your decision.. :)

Maybe.. another idea, is to request open issues asking for the removal of things that are not working correctly. As for example this "feature". Why on earth the editor adds thing that are not working correctly, instead of adding APIs to let the community work in the rest..

[FichteFoll]

(The general consens is that if you add a lot of APIs and remove a lot of features it will ultimately result in the actual editor pretty much only cosisting of Plugins, in a plugin language. Yes, Python is awesome and stuff, but there are things that C just handles more efficiently. Furthermore, less closed-source core code means it is easier to copy/reproduce.
This is an extrem case and will not be pursued further.)

Anyway, I also agree that we need a larger API. It's also the reason why C: API is the second most used tag, besides "syntaxes" which includes a whole lot of various small things, and most of the feature requests are actually API-related.

Sure, we can have that too - assuming it's getting in the way, distracting, misleading or raising false hopes (like here) and there is a replacement. However, in this case there is a setting for this already, so it seems rather redundant to remove it completely because it is still useful in cases. (match_brackets)

(I actually wrote this comment over 5 hours.)

[pensnarik]

I face this issue quite often. Especially while observing javascript files.

[keith-hall]

the comment I made on a different issue also seems relevant here :)
It would even be possible to use the scopes assigned to the brackets to fix this problem without needing to worry too much about size/time constraints because the API is efficient.