Add antlr4-c3 to ydb sync to github

Add antlr4-c3 to ydb sync to github
commit_hash:f53b6baf79027bbab0ada47fd33db3ca054fe8df

10 files changed, 1765 insertions, 0 deletions

diff --git a/contrib/libs/antlr4-c3/.yandex_meta/build.ym b/contrib/libs/antlr4-c3/.yandex_meta/build.ym
new file mode 100644
index 0000000000..7207a79cc6
--- /dev/null
+++ b/contrib/libs/antlr4-c3/.yandex_meta/build.ym
@@ -0,0 +1,46 @@
+{% extends '//builtin/bag.ym' %}
+
+{% block current_version %}2.0.0{% endblock %}
+
+{% block current_url %}
+https://github.com/mike-lischke/antlr4-c3/archive/refs/tags/cpp-{{self.version().strip()}}.tar.gz
+{% endblock %}
+
+{% block patch_source %}
+# remove root src
+rm -Rf src
+
+# make new src from cpp port
+mv ports/cpp/source/antlr4-c3 src
+
+# remove files from root except license and readme
+find . -maxdepth 1 ! -name 'License.txt' ! -name 'readme.md' -type f -exec rm -f {} +
+
+# add cpp readme
+mv ports/cpp/README.md README-cpp.md
+
+# remove all directories except src
+find . ! -name 'src' ! -name . ! -name .yandex_meta -type d  -exec rm -rf {} +
+
+{% endblock %}
+
+{% block ya_make %}
+SUBSCRIBER(
+    g:cpp-contrib
+)
+
+PEERDIR(
+    contrib/libs/antlr4_cpp_runtime
+)
+
+SRC(
+    src/CodeCompletionCore.cpp
+)
+
+{% endblock %}
+
+{% block move_to_output %}
+{{super()}}
+cp -R src ${OUTPUT}/
+{% endblock %}
+
diff --git a/contrib/libs/antlr4-c3/.yandex_meta/devtools.copyrights.report b/contrib/libs/antlr4-c3/.yandex_meta/devtools.copyrights.report
new file mode 100644
index 0000000000..22ac12e6b7
--- /dev/null
+++ b/contrib/libs/antlr4-c3/.yandex_meta/devtools.copyrights.report
@@ -0,0 +1,45 @@
+# File format ($ symbol means the beginning of a line):
+#
+# $ # this message
+# $ # =======================
+# $     # comments (all commentaries should starts with some number of spaces and # symbol)
+# $ IGNORE_FILES {file1.ext1} {file2.ext2} - (optional) ignore listed files when generating license macro and credits
+# $ RENAME {original license id} TO {new license id} # user comments - (optional) use {new license id} instead {original license id} in ya.make files
+# $ # user comments
+# $
+# ${action} {license id} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/1/ya.make ./ya/make/2/ya.make
+# ${all_file_action} filename
+# $ # user commentaries (many lines)
+# $ generated description - files with this license, license text... (some number of lines that starts with some number of spaces, do not modify)
+# ${action} {license spdx} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/3/ya.make
+# ${all_file_action} filename
+# $    #    user commentaries
+# $ generated description
+# $ ...
+#
+# You can modify action, all_file_action and add commentaries
+# Available actions:
+# keep - keep license in contrib and use in credits
+# skip - skip license
+# remove - remove all files with this license
+# rename - save license text/links into licenses texts file, but not store SPDX into LINCENSE macro. You should store correct license id into devtools.license.spdx.txt file
+#
+# {all file action} records will be generated when license text contains filename that exists on filesystem (in contrib directory)
+# We suppose that that files can contain some license info
+# Available all file actions:
+# FILE_IGNORE - ignore file (do nothing)
+# FILE_INCLUDE - include all file data into licenses text file
+# =======================
+
+KEEP     COPYRIGHT_SERVICE_LABEL 7f21db3991f0ec39d24cc1ee5479550d
+BELONGS ya.make
+    License text:
+        Copyright (c) 2016 - present Mike Lischke
+    Scancode info:
+        Original SPDX id: COPYRIGHT_SERVICE_LABEL
+        Score           : 100.00
+        Match type      : COPYRIGHT
+    Files with this license:
+        License.txt [3:3]
diff --git a/contrib/libs/antlr4-c3/.yandex_meta/devtools.licenses.report b/contrib/libs/antlr4-c3/.yandex_meta/devtools.licenses.report
new file mode 100644
index 0000000000..f29000dd07
--- /dev/null
+++ b/contrib/libs/antlr4-c3/.yandex_meta/devtools.licenses.report
@@ -0,0 +1,70 @@
+# File format ($ symbol means the beginning of a line):
+#
+# $ # this message
+# $ # =======================
+# $     # comments (all commentaries should starts with some number of spaces and # symbol)
+# $ IGNORE_FILES {file1.ext1} {file2.ext2} - (optional) ignore listed files when generating license macro and credits
+# $ RENAME {original license id} TO {new license id} # user comments - (optional) use {new license id} instead {original license id} in ya.make files
+# $ # user comments
+# $
+# ${action} {license id} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/1/ya.make ./ya/make/2/ya.make
+# ${all_file_action} filename
+# $ # user commentaries (many lines)
+# $ generated description - files with this license, license text... (some number of lines that starts with some number of spaces, do not modify)
+# ${action} {license spdx} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/3/ya.make
+# ${all_file_action} filename
+# $    #    user commentaries
+# $ generated description
+# $ ...
+#
+# You can modify action, all_file_action and add commentaries
+# Available actions:
+# keep - keep license in contrib and use in credits
+# skip - skip license
+# remove - remove all files with this license
+# rename - save license text/links into licenses texts file, but not store SPDX into LINCENSE macro. You should store correct license id into devtools.license.spdx.txt file
+#
+# {all file action} records will be generated when license text contains filename that exists on filesystem (in contrib directory)
+# We suppose that that files can contain some license info
+# Available all file actions:
+# FILE_IGNORE - ignore file (do nothing)
+# FILE_INCLUDE - include all file data into licenses text file
+# =======================
+
+KEEP     MIT                  399584035c417b91040964779555dfac
+BELONGS ya.make
+    License text:
+        MIT License
+    Scancode info:
+        Original SPDX id: MIT
+        Score           : 100.00
+        Match type      : REFERENCE
+        Links           : http://opensource.org/licenses/mit-license.php, https://spdx.org/licenses/MIT
+    Files with this license:
+        License.txt [1:1]
+
+KEEP     MIT                  54575e81a786e9aa7d98337ec2e1ebb0
+BELONGS ya.make
+    Note: matched license text is too long. Read it in the source files.
+    Scancode info:
+        Original SPDX id: MIT
+        Score           : 100.00
+        Match type      : TEXT
+        Links           : http://opensource.org/licenses/mit-license.php, https://spdx.org/licenses/MIT
+    Files with this license:
+        License.txt [5:21]
+
+KEEP     MIT                  e05ba18ab449e96e18c1d72863031ecf
+BELONGS ya.make
+    License text:
+        //  Licensed under the MIT License.
+    Scancode info:
+        Original SPDX id: MIT
+        Score           : 100.00
+        Match type      : NOTICE
+        Links           : http://opensource.org/licenses/mit-license.php, https://spdx.org/licenses/MIT
+    Files with this license:
+        src/CodeCompletionCore.cpp [5:5]
+        src/CodeCompletionCore.hpp [5:5]
diff --git a/contrib/libs/antlr4-c3/.yandex_meta/licenses.list.txt b/contrib/libs/antlr4-c3/.yandex_meta/licenses.list.txt
new file mode 100644
index 0000000000..8996671fdc
--- /dev/null
+++ b/contrib/libs/antlr4-c3/.yandex_meta/licenses.list.txt
@@ -0,0 +1,30 @@
+====================COPYRIGHT====================
+Copyright (c) 2016 - present Mike Lischke
+
+
+====================MIT====================
+//  Licensed under the MIT License.
+
+
+====================MIT====================
+MIT License
+
+
+====================MIT====================
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
\ No newline at end of file
diff --git a/contrib/libs/antlr4-c3/License.txt b/contrib/libs/antlr4-c3/License.txt
new file mode 100644
index 0000000000..c7069cc6db
--- /dev/null
+++ b/contrib/libs/antlr4-c3/License.txt
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2016 - present Mike Lischke
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/contrib/libs/antlr4-c3/README-cpp.md b/contrib/libs/antlr4-c3/README-cpp.md
new file mode 100644
index 0000000000..6614ca64e1
--- /dev/null
+++ b/contrib/libs/antlr4-c3/README-cpp.md
@@ -0,0 +1,59 @@
+# ANTLRv4 C3 C++ Port
+
+## About
+
+This is a port of the `antlr4-c3` library to `C++`.
+
+Please see the parent [README.md](../../readme.md) for an explanation of the library and for examples.
+
+## Port features
+
+1. Only `CodeCompletionCore` was ported.
+
+2. Supports cancellation for `collectCandidates` method via timeout or flag.
+
+## Requirements
+
+- [C++ 20 standard](https://en.cppreference.com/w/cpp/20) to compile sources.
+
+- [ANTLRv4 C++ Runtime](https://github.com/antlr/antlr4/tree/4.13.1/runtime/Cpp) to compile sources.
+
+- [CMake 3.7](https://cmake.org/cmake/help/latest/release/3.7.html) to build project.
+
+- [ANTLRv4 Tool](https://www.antlr.org/download.html) to build tests.
+
+- [Google Test](https://github.com/google/googletest) to build tests.
+
+## Usage
+
+Currently, there are no other ways to adding C++ port as a dependency other than by copying and pasting the [directory with project's source code](./source/antlr4-c3) into your own project.
+
+## Build & Run
+
+Actual build steps are available at [CMake GitHub Workflow](../../.github/workflows/cmake.yml). 
+
+`ANTLRv4` Runtime and Tool as well as other dependecnies will be downloaded during `CMake` configiration stage.
+
+```bash
+# Clone antlr4-c3 repository and enter C++ port directory
+git clone git@github.com:mike-lischke/antlr4-c3.git
+cd antlr4-c3/ports/cpp # Also a workspace directory for VSCode
+
+# Create and enter the build directory
+mkdir build && cd build
+
+# Configure CMake build
+# - ANTLR4C3_DEVELOPER should be enabled if you are going to run tests
+# - CMAKE_BUILD_TYPE Asan and Tsan are supported too
+cmake -DANTLR4C3_DEVELOPER=ON -DCMAKE_BUILD_TYPE=Release ..
+
+# Build everything
+make
+
+# Running tests being at build directory
+(make && cd test && ctest)
+```
+
+## Contributing
+
+We recommend using [VSCode](https://code.visualstudio.com/) with [clangd extension](https://marketplace.visualstudio.com/items?itemName=llvm-vs-code-extensions.vscode-clangd) as an IDE. There are some configuration files for launching tests in debug mode, `clangd` configuration and more.
diff --git a/contrib/libs/antlr4-c3/readme.md b/contrib/libs/antlr4-c3/readme.md
new file mode 100644
index 0000000000..65c1ba25ba
--- /dev/null
+++ b/contrib/libs/antlr4-c3/readme.md
@@ -0,0 +1,342 @@
+[![GitHub Workflow Status (with event)](https://img.shields.io/github/actions/workflow/status/mike-lischke/antlr4-c3/nodejs.yml?style=for-the-badge&color=green&logo=github)](https://github.com/mike-lischke/antlr4-c3/actions/workflows/nodejs.yml)
+![License](https://img.shields.io/github/license/mike-lischke/antlr4-c3?style=for-the-badge&color=lightgreen)
+[![Weekly Downloads](https://img.shields.io/npm/dw/antlr4-c3?style=for-the-badge&color=blue)](https://www.npmjs.com/package/antlr4-c3)
+[![npm version](https://img.shields.io/npm/v/antlr4-c3?style=for-the-badge&color=yellow)](https://www.npmjs.com/package/antlr4-c3)
+
+# antlr4-c3 The ANTLR4 Code Completion Core
+
+This project contains a grammar agnostic code completion engine for ANTLR4 based parsers. The c3 engine is able to provide code completion candidates useful for editors with ANTLR generated parsers, independent of the actual language/grammar used for the generation.
+
+The original implementation is provided as a node module (works in both, Node.js and browsers), and is written in TypeScript. Ports to Java, C#, C++ are available in the `ports` folder. These ports might not be up to date compared to the TypeScript version.
+
+# Abstract
+
+This library provides a common infrastructure for code completion implementations. The c3 engine implementation is based on an idea presented a while ago under [Universal Code Completion using ANTLR3](https://soft-gems.net/universal-code-completion-using-antlr3/). There a grammar was loaded into a memory structure so that it can be walked through with the current input to find a specific location (usually the caret position) and then collect all possible tokens and special rules, which then describe the possible set of code completion candidates for that position. With ANTLR4 we no longer need to load a grammar, because the grammar structure is now available as part of a parser (via the ATN - [Augmented Transition Network](https://en.wikipedia.org/wiki/Augmented_transition_network)). The ANTLR4 runtime even provides the [LL1Analyzer](https://github.com/antlr/antlr4/blob/master/runtime/Java/src/org/antlr/v4/runtime/atn/LL1Analyzer.java) class, which helps with retrieving follow sets for a given ATN state, but has a few shortcomings and is in general not easy to use.
+
+With the Code Completion Core implementation things become a lot easier. In the simplest setup you only give it a parser instance and a caret position and it will return the candidates for it. Still, a full code completion implementation requires some support code that we need to discuss first before we can come to the actual usage of the c3 engine.
+
+# A Code Completion Breakdown
+
+For showing possible symbols in source code you obviously need a source for all available symbols at the given position. Providing them is usually the task of a symbol table. Its content can be derived from your current source code (with the help of a parser + a parse listener). More static parts (like runtime functions) can be loaded from disk or provided by a hard coded list etc. The symbol table can then answer your question about all symbols of a given type that are visible from a given position. The position usually corresponds to a specific symbol in the symbol table and the structure then allows to easily get visible symbols. The c3 engine comes with a small symbol table implementation, which is however not mandatory to use the library, but instead provides an easy start, if you don't have an own symbol table class already.
+
+While the symbol table provides symbols of a given type, we need to find out which type is actually required. This is the task of the c3 engine. In its simplest setup it will return only keywords (and other lexer symbols) that are allowed by the grammar for a given position (which is of course the same position used to find the context for a symbol lookup in your symbol table). Keywords are a fixed set of words (or word sequences) that usually don't live in a symbol table. You can get the actual text strings directly from the parser vocabulary. The c3 engine only returns the lexer tokens for them.
+
+In order to also get other types like variables or class names you have to do 2 steps:
+
+* Identify entities in your grammar which you are interested in and put them into own rules. More about this below.
+* Tell the engine in which parser rules you are particularly interested. It will then return those to you instead of the lexer tokens they are made of.
+
+Let's consider a grammar which can parse simple expressions like:
+
+```typescript
+var a = b + c()
+```
+
+Such a grammar could look like:
+
+```antlr
+grammar Expr;
+expression: assignment | simpleExpression;
+
+assignment: (VAR | LET) ID EQUAL simpleExpression;
+
+simpleExpression
+    : simpleExpression (PLUS | MINUS) simpleExpression
+    | simpleExpression (MULTIPLY | DIVIDE) simpleExpression
+    | variableRef
+    | functionRef
+;
+
+variableRef: ID;
+functionRef: ID OPEN_PAR CLOSE_PAR;
+
+VAR: [vV] [aA] [rR];
+LET: [lL] [eE] [tT];
+
+PLUS: '+';
+MINUS: '-';
+MULTIPLY: '*';
+DIVIDE: '/';
+EQUAL: '=';
+OPEN_PAR: '(';
+CLOSE_PAR: ')';
+ID: [a-zA-Z] [a-zA-Z0-9_]*;
+WS: [ \n\r\t] -> channel(HIDDEN);
+```
+
+You can see the 2 special rules `variableRef` and `functionRef`, which mostly consist of the `ID` lexer rule. We could have instead used a single `ID` reference in the `simpleExpression` rule. However, this is where your domain knowledge about the language comes in. By making the two use cases explicit you can now exactly tell what to query from your symbol table. As you see we are using parser rules to denote entity types, which is half of the magic here.
+
+The code completion core can return parser rule indexes (as created by ANTLR4 when it generated your files). With a returned candidate `ExprParser.RULE_variableRef` you know that you have to ask your symbol for all visible variables (or functions if you get back `ExprParser.RULE_functionRef`). It's easy to see how this applies to much more complex grammars. The principle is always the same: create an own parser rule for your entity references. If you have an SQL grammar where you drop a table write your rules so:
+
+```mysql
+dropTable: DROP TABLE tableRef;
+tableRef: ID;
+```
+
+instead of:
+
+```mysql
+dropTable: DROP TABLE ID;
+```
+
+Then tell the c3 engine that you want to get back `tableRef` if it is a valid candidate at a given position.
+
+# Getting Started
+
+With this knowledge we can now look at a simple code example that shows how to use the engine. For further details check the unit tests for this node module (under the test/ folder).
+
+> Since this library is made for ANTLR4 based parser, it requires a [JavaScript/TypeScript runtime](https://github.com/mike-lischke/antlr4ng), just like your parser (namely antlr4ng).
+
+```typescript
+let inputStream = new ANTLRInputStream("var c = a + b()");
+let lexer = new ExprLexer(inputStream);
+let tokenStream = new CommonTokenStream(lexer);
+
+let parser = new ExprParser(tokenStream);
+let errorListener = new ErrorListener();
+parser.addErrorListener(errorListener);
+let tree = parser.expression();
+
+let core = new c3.CodeCompletionCore(parser);
+let candidates = core.collectCandidates(0);
+```
+
+This is a pretty standard parser setup here. It's not even necessary to actually parse the input. But the c3 engine needs a few things for its work:
+
+* the ATN of your parser class
+* the tokens from your input stream
+* vocabulary and rule names for debug output
+
+All these could be passed in individually, but since your parser contains all of that anyway and we need a parser for predicate execution, the API has been designed to take a parser instead (predicates work however only if written for the Javascript/Typescript target). In real world applications you will have a parser anyway (e.g. for error checking), which is perfect as ATN and input provider for the code completion core. But keep in mind: whatever parser you pass in it must have a fully set up token stream. It's not required that it parsed anything before calling the code completion engine and the current stream positions don't matter either.
+
+The returned candidate collection contains fields for lexer tokens (mostly keywords, but also other tokens if they are not on the ignore list) and parser rule indexes. This collection is defined as:
+
+```typescript
+class CandidatesCollection {
+    public tokens: Map<number, TokenList>;
+    public rules: Map<number, CandidateRule>;
+};
+```
+
+where the map keys are the lexer tokens and the rule indices, respectively. Both can come with additional values, which you may or may not use for your implementation.
+
+For parser rules the value includes a `startTokenIndex`, which reflects the index of the starting token within the evaluated rule. This allows consumers to determine the range of tokens that should be replaced or matched against when resolving symbols for your rule. The value also contains a rule list which represents the call stack at which the given rule was found during evaluation. This allows consumers to determine a context for rules that are used in different places.
+
+For the lexer tokens the list consists of further token ids which directly follow the given token in the grammar (if any). This allows you to show **token sequences** if they are always used together. For example consider this SQL rule:
+
+```antlr
+createTable: CREATE TABLE (IF NOT EXISTS)? ...;
+```
+
+Here, if a possible candidate is the `IF` keyword, you can also show the entire `IF NOT EXISTS` sequence to the user (and let him complete all 3 words in one go in the source code). The engine will return a candidate entry for `IF` with a token list containing `NOT` and `EXISTS`. This list will of course update properly when the user comes to `NOT`. Then you will get a candidate entry for `NOT` and an additional list consisting of just `EXISTS`.
+
+Essential for getting any rule index, which you can use to query your symbol table, is that you specify those you want in the `CodeCompletionCore.preferredRules` field before running `CodeCompletionCore.collectCandidates()`.
+
+The final step to get your completion strings is usually something like this:
+
+```typescript
+let keywords: string[] = [];
+for (let candidate of candidates.tokens) {
+    keywords.push(parser.vocabulary.getDisplayName(candidate[0]));
+}
+
+let symbol = ...; // Find the symbol that covers your caret position.
+let functionNames: string[] = [];
+let variableNames: string[] = [];
+for (let candidate of candidates.rules) {
+  switch (candidate[0]) {
+    case ExprParser.RULE_functionRef: {
+      let functions = symbol.getSymbolsOfType(c3.FunctionSymbol);
+      for (function of functions)
+        functionNames.push(function.name);
+      break;
+    }
+
+    case ExprParser.RULE_variableRef: {
+      let variables = symbol.getSymbolsOfType(c3.VariableSymbol);
+      for (variable of variables)
+        functionNames.push(variable.name);
+      break;
+    }
+  }
+}
+
+// Finally combine all found lists into one for the UI.
+// We do that in separate steps so that you can apply some ordering to each of your sub lists.
+// Then you also can order symbols groups as a whole depending their importance.
+let candidates: string[] = [];
+candidates.push(...keywords);
+candidates.push(...functionNames);
+candidates.push(...variableNames);
+```
+
+# Fine Tuning
+
+## Ignored Tokens
+
+As mentioned above in the base setup the engine will only return lexer tokens. This will include your keywords, but also many other tokens like operators, which you usually don't want in your completion list. In order to ease usage you can tell the engine which lexer tokens you are not interested in and which therefor should not appear in the result. This can easily be done by assigning a list of token ids to the `ignoredTokens` field before you invoke `collectCandidates()`:
+
+```typescript
+core.ignoredTokens = new Set([
+  ExprLexer.ID,
+  ExprLexer.PLUS, ExprLexer.MINUS,
+  ExprLexer.MULTIPLY, ExprLexer.DIVIDE,
+  ExprLexer.EQUAL,
+  ExprLexer.OPEN_PAR, ExprLexer.CLOSE_PAR,
+]);
+```
+
+## Preferred Rules
+
+As mentioned already the `preferredRules` field is an essential part for getting more than just keywords. It lets you specify the parser rules that are interesting for you and should include the rule indexes for the entities we talked about in the code completion breakdown paragraph above. Whenever the c3 engine hits a lexer token when collecting candidates from a specific ATN state it will check the call stack for it and, if that contains any of the preferred rules, will select that instead of the lexer token. This transformation ensures that the engine returns contextual information which can actually be used to look up symbols.
+
+## Constraining the Search Space
+
+Walking the ATN can at times be quite expensive, especially for complex grammars with many rules and perhaps (left) recursive expression rules. I have seen millions of visited ATN states for complex input, which will take very long to finish. In such cases it pays off to limit the engine to just a specific rule (and those called by it). For that there is an optional parser rule context parameter in the `collectCandidates()` method. If a context is given the engine will never look outside of this rule. It is necessary that the specified caret position lies within that rule (or any of those called by it) to properly finish the ATN walk.
+
+You can determine a parser rule context from your symbol table if it stores the context together with its symbols. Another way would be to use the parse tree and do a search to find the most deeply nested context which contains the caret position. While it will make the c3 engine ultra fast when you pick the context that most closely covers the caret position it might have also a negative side effect: candidates located outside of this context (or those called by it) will not appear in the returned candidates list. So, this is a tradeoff between speed and precision here. You can select any parse rule context you wish between the top rule (or null) and the most deeply nested one. with increasing execution time (but more complete results) the higher in the stack your given rule is.
+
+In any case, when you want to limit the search space you have to parse your input first to get a parse tree.
+
+## Selecting the Right Caret Position
+
+It might sound weird to talk about such a trivial thing like the caret position but there's one thing to consider, which makes this something you have to think about. The issue is the pure token index returned by the token stream and the visual appearance on screen. This image shows a typical scenario:
+
+![token position](images/token-position.png)
+
+Each vertical line corresponds to a possible caret position. The first 3 lines clearly belong to token index 0, but the next line is no longer that clear. At that position we already are on token index 1 while visually the caret still belongs to index 0, because it could be that we are just at the end of a word and want to add more letters to it and hence have to provide candidates for that word. However, for token position 5 the situation is different. After the equal sign there are no possible further characters that could belong to it, so in this case position 5 really means 5. Similarly, token position 7 visually belongs to 6, while 8 is really 8. That means in order to find the correct candidates you have to change the token index based on the type of the token that immediately precedes the caret token.
+
+Things get really tricky however, when your grammar never stores whitespaces (i.e. when using the `skip` lexer action). In that case you won't get token indexes for whitespaces, as demonstrated in the second index line in the image. In such a scenario you cannot even tell (e.g. for token position 1) whether you still have to complete the `var` keyword or want candidates for the `a`. Also the position between the two whitespaces is unclear, since you have no token index for that and have to use other indicators to decide if that position should go to index 3 (`b`) or 4 (`+`). Given these problems it is probably better not to use the `skip` action for your whitespace rule, but simply put whitespaces on a hidden channel instead.
+
+# Debugging
+
+Sometimes you are not getting what you actually expect and you need take a closer look at what the c3 engine is doing. For this situation a few fields have been added which control some debug output dumped to the console:
+
+* `showResult`: Set this field to true to print a summary of what has been processed and collected. It will print the number of visited ATN states as well as all collected tokens and rules (along with their additional info).
+* `showDebugOutput`: This setting enables output of states and symbols (labels) seen for transitions as they are processed by the engine. There will also be lines showing when input is consumed and candidates are added to the result.
+* `debugOutputWithTransitions`: This setting only has an effect if `showDebugOutput` is enabled. It adds all transitions to the output which the engine encountered (not all of them are actually followed, however).
+* `showRuleStack`: Also this setting only has an effect if `showDebugOutput` is enabled. It will make the engine print the current rule stack whenever it enters a new rule during the walk.
+
+The last two options potentially create a lot of output which can significantly slow down the collection process.
+
+## Release Notes
+
+### 3.4.0
+
+- Switched to a new major version of the antlr4ng runtime (3.0.0).
+- Fixed issue #96 Add .cjs output to package
+
+### 3.3.7
+
+- Stop bundling 3rd party libraries in the own lib bundle. This is not only unnecessary (these deps are installed with all the other dependencies in a target project), but can cause trouble if a dependent project uses 2 different versions of such a bundled 3rd party lib.
+
+### 3.3.6
+
+- Fixed bug #93 Add command to esbuild (stop including 3rd party libs in bundle).
+- Updated dependencies.
+
+### 3.3.5
+
+Updated dependencies.
+
+### 3.3.1 - 3.3.4
+
+Updated dependencies.
+
+### 3.3.0
+
+Now using esbuild for building the package.
+
+### 3.2.4 - 3.2.5
+- Last changes for the dependency switch (antlr-ts -> antlr4ng).
+- Updated Jest settings to run ESM + TS tests.
+
+### 3.2.3
+- Completed switch away from antlr4ts.
+
+### 3.2.0
+
+- A new [TypeScript runtime](https://github.com/mike-lischke/antlr4ng) powers this package now (antlr4ng).
+- The package is now published as ES module, which is supported by all modern browsers and Node.js.
+- The contributors list has been moved to a separate file, because now contributions are tracked via git's signed-off commits.
+
+### 3.1.1
+
+- Renamed a few interfaces to follow the interface naming rules (a leading I).
+- Merged PR #81 from Aaron Braunstein.
+- Upgraded all dependencies to their latest version.
+-
+### 3.0.0
+
+BREAKING CHANGES: With this major version release the API has been changed to make it more consistent and easier to use. The most important changes are:
+
+- All the classes in the SymbolTable.ts file have been split into separate files.
+- The main Symbol class has been renamed to `BaseSymbol` to avoid confusion and trouble with the Javascript `Symbol` class.
+- The package works now with Typescript 5.0 and above.
+- The tests have been organized into a separate sub project, which is no longer built with the main project. Instead tests files are transpiled on-the-fly (using `ts-jest`) when running the tests. These transpiled files are never written to disk.
+- Symbol creation functions (like `SymbolTable.addNewSymbolOfType`) now allow Typescript to check the given parameters for the class type. You will now have to provide the correct parameter list for the symbol type you want to create. This is a breaking change, because the old version allowed you to pass any parameter list to any symbol creation function.
+
+### 2.2.3
+
+Upgraded dependencies, which includes a new major version of Typescript (5.0). With this version the `main` field in `package.json` apparently became necessary, because of the package organization, and has been set in this release.
+
+### 2.2.2
+- Some improvements in the symbol table implementation.
+- Updated dependencies.
+- PR #76 (fixes bug #23) Account for empty and fully-optional-body rules when collecting tokens, thanks to Aaron Braunstein.
+
+### 2.2.1
+Reverted changes from `any` to `unknown` for `SymbolTable.addNewSymbolOfType`. It works in the tests, but is not accepted by consumers of the node module.
+
+### 2.2.0
+- Added `InterfaceSymbol` to SymbolTable and enhanced `ClassSymbol` for interface implementations.
+- Added a modifier and a visibility field to Symbol, so that's available for all symbols now. Removed the obsolete visibility field from method and field symbols.
+
+### 2.1.0
+- It turned out that synchronous symbol retrieval methods have their value, so I brought them back by adding `...Sync()` variants of all methods with an async behavior.
+- Brought back and extended project tests on Github.
+- Upgraded module dependencies.
+- Cleaned up the code again, now with latest eslint settings.
+
+### 2.0.2
+- `getAllSymbols<T>` now returns symbols of type T (instead of `Symbol`), like all other enumeration methods.
+
+### 2.0.1
+- Breaking change: some of the methods in the symbol table implementation, which may require extra work return now promises (symbol collections and resolver methods). This allows also to override them and return asynchronous results which are constructed from external resources (like database symbols).
+
+### 1.1.16
+- Fixed an issue where wrong tokens were collected for code completion.
+
+### 1.1.15
+- Fixed a problem with seen states in the follow set determination.
+
+### 1.1.13
+- Added a C# port of the library (thanks to Jonathan Philipps)
+- Optionally allow to walk the rule stack on matching a preferred rule either top-down or bottom-up (which changes how preference is given to multiple preferred rules in a single stack).
+- Rule candidates now include the start token index of where they matched.
+
+### 1.1.12
+- Updated modules with known vulnerabilities.
+- Better handling of recursive rules in code completion (via precedence).
+- Updated to latest antlr4ts.
+
+### 1.1.8
+- Renamed a number of methods for improved consistency (`next` -> `nextSibling` etc.) and updated some tests.
+- Also simple symbols can be used to resolve other symbols (by delegating this call to their parents, if there's one).
+- Added a method to find a symbol by it's associated context + added a test for that.
+
+### 1.1.6
+- Added Java port from Nick Stephen.
+- Added contributors.txt file.
+- A symbol can now store a `ParseTree` reference (which allows for terminal symbols in addition to parser rules).
+- Added navigation functions to `Symbol` and `ScopedSymbol` (first/last child, next/previous sibling) and added tests for that.
+- Fixed formatting and spelling in tests + `SymbolTable`.
+- Updated readme.
+
+### 1.1.1
+- Travis-CI integration
+- Implemented completion optimizations
+
+### 1.0.4
+- First public release
+- Added initial tests, `SymbolTable` and `CodeCompletionCore` classes
diff --git a/contrib/libs/antlr4-c3/src/CodeCompletionCore.cpp b/contrib/libs/antlr4-c3/src/CodeCompletionCore.cpp
new file mode 100644
index 0000000000..30fc3d1050
--- /dev/null
+++ b/contrib/libs/antlr4-c3/src/CodeCompletionCore.cpp
@@ -0,0 +1,864 @@
+//
+//  CodeCompletionCore.cpp
+//
+//  C++ port of antlr4-c3 (TypeScript) by Mike Lischke
+//  Licensed under the MIT License.
+//
+
+#include "CodeCompletionCore.hpp"
+
+#include <Parser.h>
+#include <ParserRuleContext.h>
+#include <Token.h>
+#include <Vocabulary.h>
+#include <atn/ATN.h>
+#include <atn/ATNState.h>
+#include <atn/ATNStateType.h>
+#include <atn/PrecedencePredicateTransition.h>
+#include <atn/PredicateTransition.h>
+#include <atn/RuleStartState.h>
+#include <atn/RuleStopState.h>
+#include <atn/RuleTransition.h>
+#include <atn/Transition.h>
+#include <atn/TransitionType.h>
+
+#include <algorithm>
+#include <atomic>
+#include <chrono>
+#include <cmath>
+#include <cstddef>
+#include <iostream>
+#include <iterator>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+namespace c3 {
+
+namespace {
+
+std::vector<size_t> longestCommonPrefix(
+    std::vector<size_t> const& lhs, std::vector<size_t> const& rhs
+) {
+  size_t index = 0;
+  for (; index < std::min(lhs.size(), rhs.size()); index++) {
+    if (lhs[index] != rhs[index]) {
+      break;
+    }
+  }
+  return {
+      lhs.begin(),
+      std::next(lhs.begin(), static_cast<std::ptrdiff_t>(index)),
+  };
+}
+
+}  // namespace
+
+thread_local std::unordered_map<std::type_index, CodeCompletionCore::FollowSetsPerState>  // NOLINT
+    CodeCompletionCore::followSetsByATN = {};
+
+// Matches ATNStateType enum
+std::vector<std::string> CodeCompletionCore::atnStateTypeMap  // NOLINT
+    {
+        "invalid",
+        "basic",
+        "rule start",
+        "block start",
+        "plus block start",
+        "star block start",
+        "token start",
+        "rule stop",
+        "block end",
+        "star loop back",
+        "star loop entry",
+        "plus loop back",
+        "loop end",
+    };
+
+CodeCompletionCore::CodeCompletionCore(antlr4::Parser* parser)
+    : parser(parser)
+    , atn(&parser->getATN())
+    , vocabulary(&parser->getVocabulary())
+    , ruleNames(&parser->getRuleNames())
+    , timeout(0)
+    , cancel(nullptr) {
+}
+
+CandidatesCollection CodeCompletionCore::collectCandidates(
+    size_t caretTokenIndex, Parameters parameters
+) {
+  const auto* context = parameters.context;
+
+  timeout = parameters.timeout;
+  cancel = parameters.isCancelled;
+  timeoutStart = std::chrono::steady_clock::now();
+
+  shortcutMap.clear();
+  candidates.rules.clear();
+  candidates.tokens.clear();
+  candidates.isCancelled = false;
+  statesProcessed = 0;
+  precedenceStack = {};
+
+  tokenStartIndex = (context != nullptr) ? context->start->getTokenIndex() : 0;
+  auto* const tokenStream = parser->getTokenStream();
+
+  tokens = {};
+  size_t offset = tokenStartIndex;
+  while (true) {
+    const antlr4::Token* token = tokenStream->get(offset++);
+    if (token->getChannel() == antlr4::Token::DEFAULT_CHANNEL) {
+      tokens.push_back(token);
+
+      if (token->getTokenIndex() >= caretTokenIndex) {
+        break;
+      }
+    }
+
+    // Do not check for the token index here, as we want to end with the first
+    // unhidden token on or after the caret.
+    if (token->getType() == antlr4::Token::EOF) {
+      break;
+    }
+  }
+
+  RuleWithStartTokenList callStack = {};
+  const size_t startRule = (context != nullptr) ? context->getRuleIndex() : 0;
+
+  processRule(atn->ruleToStartState[startRule], 0, callStack, 0, 0, candidates.isCancelled);
+
+  for (auto& [_, following] : candidates.tokens) {
+    auto removed = std::ranges::remove_if(following, [&](size_t token) {
+      return ignoredTokens.contains(token);
+    });
+    following.erase(std::begin(removed), std::end(removed));
+  }
+
+  printOverallResults();
+
+  return candidates;
+}
+
+/**
+ * Checks if the predicate associated with the given transition evaluates to
+ * true.
+ *
+ * @param transition The transition to check.
+ * @returns the evaluation result of the predicate.
+ */
+bool CodeCompletionCore::checkPredicate(const antlr4::atn::PredicateTransition* transition) {
+  return transition->getPredicate()->eval(parser, &antlr4::ParserRuleContext::EMPTY);
+}
+
+/**
+ * Walks the rule chain upwards or downwards (depending on
+ * translateRulesTopDown) to see if that matches any of the preferred rules. If
+ * found, that rule is added to the collection candidates and true is returned.
+ *
+ * @param ruleWithStartTokenList The list to convert.
+ * @returns true if any of the stack entries was converted.
+ */
+bool CodeCompletionCore::translateStackToRuleIndex(
+    RuleWithStartTokenList const& ruleWithStartTokenList
+) {
+  if (preferredRules.empty()) {
+    return false;
+  }
+
+  // Change the direction we iterate over the rule stack
+  auto forward = std::views::iota(0U, ruleWithStartTokenList.size());
+  auto backward = forward | std::views::reverse;
+
+  if (translateRulesTopDown) {
+    // Loop over the rule stack from lowest to highest rule level. This will
+    // prioritize a lower preferred rule if it is a child of a higher one that
+    // is also a preferred rule.
+    return std::ranges::any_of(backward, [&](auto index) {
+      return translateToRuleIndex(index, ruleWithStartTokenList);
+    });
+  }
+
+  // Loop over the rule stack from highest to lowest rule level. This will
+  // prioritize a higher preferred rule if it contains a lower one that is
+  // also a preferred rule.
+  return std::ranges::any_of(forward, [&](auto index) {
+    return translateToRuleIndex(index, ruleWithStartTokenList);
+  });
+}
+
+/**
+ * Given the index of a rule from a rule chain, check if that matches any of the
+ * preferred rules. If it matches, that rule is added to the collection
+ * candidates and true is returned.
+ *
+ * @param i The rule index.
+ * @param ruleWithStartTokenList The list to check.
+ * @returns true if the specified rule is in the list of preferred rules.
+ */
+bool CodeCompletionCore::translateToRuleIndex(
+    size_t index, RuleWithStartTokenList const& ruleWithStartTokenList
+) {
+  const auto& rwst = ruleWithStartTokenList[index];
+
+  if (preferredRules.contains(rwst.ruleIndex)) {
+    // Add the rule to our candidates list along with the current rule path,
+    // but only if there isn't already an entry like that.
+    std::vector<size_t> path;
+    path.reserve(index);
+    for (size_t i = 0; i < index; i++) {
+      path.push_back(ruleWithStartTokenList[i].ruleIndex);
+    }
+
+    bool addNew = true;
+    for (auto const& [cRuleEntryRuleIndex, cRuleEntryCandidateRule] : candidates.rules) {
+      if (cRuleEntryRuleIndex != rwst.ruleIndex ||
+          cRuleEntryCandidateRule.ruleList.size() != path.size()) {
+        continue;
+      }
+
+      // Found an entry for this rule. Same path?
+      bool samePath = true;
+      for (size_t i = 0; i < path.size(); i++) {
+        if (path[i] == cRuleEntryCandidateRule.ruleList[i]) {
+          samePath = false;
+          break;
+        }
+      }
+
+      // If same path, then don't add a new (duplicate) entry.
+      if (samePath) {
+        addNew = false;
+        break;
+      }
+    }
+
+    if (addNew) {
+      candidates.rules[rwst.ruleIndex] = {
+          .startTokenIndex = rwst.startTokenIndex,
+          .ruleList = path,
+      };
+      if (debugOptions.showDebugOutput) {
+        std::cout << "=====> collected: " << ruleNames->at(rwst.ruleIndex) << "\n";
+      }
+    }
+
+    return true;
+  }
+
+  return false;
+}
+
+/**
+ * This method follows the given transition and collects all symbols within the
+ * same rule that directly follow it without intermediate transitions to other
+ * rules and only if there is a single symbol for a transition.
+ *
+ * @param transition The transition from which to start.
+ * @returns A list of toke types.
+ */
+std::vector<size_t> CodeCompletionCore::getFollowingTokens(const antlr4::atn::Transition* transition
+) {
+  std::vector<size_t> result;
+  std::vector<antlr4::atn::ATNState*> pipeline = {transition->target};
+
+  while (!pipeline.empty()) {
+    antlr4::atn::ATNState* state = pipeline.back();
+    pipeline.pop_back();
+
+    if (state == nullptr) {
+      continue;
+    }
+
+    for (const antlr4::atn::ConstTransitionPtr& outgoing : state->transitions) {
+      if (outgoing->getTransitionType() == antlr4::atn::TransitionType::ATOM) {
+        if (!outgoing->isEpsilon()) {
+          const auto list = outgoing->label();
+          if (list.size() == 1) {
+            result.push_back(list.get(0));
+            pipeline.push_back(outgoing->target);
+          }
+        } else {
+          pipeline.push_back(outgoing->target);
+        }
+      }
+    }
+  }
+
+  return result;
+}
+
+/**
+ * Entry point for the recursive follow set collection function.
+ *
+ * @param start Start state.
+ * @param stop Stop state.
+ * @returns Follow sets.
+ */
+CodeCompletionCore::FollowSetsHolder CodeCompletionCore::determineFollowSets(
+    antlr4::atn::ATNState* start, antlr4::atn::ATNState* stop
+) {
+  std::vector<FollowSetWithPath> sets = {};
+  std::vector<antlr4::atn::ATNState*> stateStack = {};
+  std::vector<size_t> ruleStack = {};
+  const bool isExhaustive = collectFollowSets(start, stop, sets, stateStack, ruleStack);
+
+  // Sets are split by path to allow translating them to preferred rules. But
+  // for quick hit tests it is also useful to have a set with all symbols
+  // combined.
+  antlr4::misc::IntervalSet combined;
+  for (const auto& set : sets) {
+    combined.addAll(set.intervals);
+  }
+
+  return {
+      .sets = sets,
+      .combined = combined,
+      .isExhaustive = isExhaustive,
+  };
+}
+
+/**
+ * Collects possible tokens which could be matched following the given ATN
+ * state. This is essentially the same algorithm as used in the LL1Analyzer
+ * class, but here we consider predicates also and use no parser rule context.
+ *
+ * @param s The state to continue from.
+ * @param stopState The state which ends the collection routine.
+ * @param followSets A pass through parameter to add found sets to.
+ * @param stateStack A stack to avoid endless recursions.
+ * @param ruleStack The current rule stack.
+ * @returns true if the follow sets is exhaustive, i.e. we terminated before the
+ * rule end was reached, so no subsequent rules could add tokens
+ */
+bool CodeCompletionCore::collectFollowSets(  // NOLINT
+    antlr4::atn::ATNState* state,
+    antlr4::atn::ATNState* stopState,
+    std::vector<FollowSetWithPath>& followSets,
+    std::vector<antlr4::atn::ATNState*>& stateStack,
+    std::vector<size_t>& ruleStack
+) {
+  if (std::ranges::find(stateStack, state) != stateStack.end()) {
+    return true;
+  }
+  stateStack.push_back(state);
+
+  if (state == stopState || state->getStateType() == antlr4::atn::ATNStateType::RULE_STOP) {
+    stateStack.pop_back();
+    return false;
+  }
+
+  bool isExhaustive = true;
+  for (const antlr4::atn::ConstTransitionPtr& transitionPtr : state->transitions) {
+    const antlr4::atn::Transition* transition = transitionPtr.get();
+
+    if (transition->getTransitionType() == antlr4::atn::TransitionType::RULE) {
+      const auto* ruleTransition = dynamic_cast<const antlr4::atn::RuleTransition*>(transition);
+
+      if (std::ranges::find(ruleStack, ruleTransition->target->ruleIndex) != ruleStack.end()) {
+        continue;
+      }
+
+      ruleStack.push_back(ruleTransition->target->ruleIndex);
+      const bool ruleFollowSetsIsExhaustive =
+          collectFollowSets(transition->target, stopState, followSets, stateStack, ruleStack);
+      ruleStack.pop_back();
+
+      // If the subrule had an epsilon transition to the rule end, the tokens
+      // added to the follow set are non-exhaustive and we should continue
+      // processing subsequent transitions post-rule
+      if (!ruleFollowSetsIsExhaustive) {
+        const bool nextStateFollowSetsIsExhaustive = collectFollowSets(
+            ruleTransition->followState, stopState, followSets, stateStack, ruleStack
+        );
+        isExhaustive = isExhaustive && nextStateFollowSetsIsExhaustive;
+      }
+
+    } else if (transition->getTransitionType() == antlr4::atn::TransitionType::PREDICATE) {
+      if (checkPredicate(dynamic_cast<const antlr4::atn::PredicateTransition*>(transition))) {
+        const bool nextStateFollowSetsIsExhaustive =
+            collectFollowSets(transition->target, stopState, followSets, stateStack, ruleStack);
+        isExhaustive = isExhaustive && nextStateFollowSetsIsExhaustive;
+      }
+    } else if (transition->isEpsilon()) {
+      const bool nextStateFollowSetsIsExhaustive =
+          collectFollowSets(transition->target, stopState, followSets, stateStack, ruleStack);
+      isExhaustive = isExhaustive && nextStateFollowSetsIsExhaustive;
+    } else if (transition->getTransitionType() == antlr4::atn::TransitionType::WILDCARD) {
+      followSets.push_back({
+          .intervals = allUserTokens(),
+          .path = ruleStack,
+          .following = {},
+      });
+    } else {
+      antlr4::misc::IntervalSet label = transition->label();
+      if (!label.isEmpty()) {
+        if (transition->getTransitionType() == antlr4::atn::TransitionType::NOT_SET) {
+          label = label.complement(allUserTokens());
+        }
+        followSets.push_back({
+            .intervals = label,
+            .path = ruleStack,
+            .following = getFollowingTokens(transition),
+        });
+      }
+    }
+  }
+  stateStack.pop_back();
+
+  return isExhaustive;
+}
+
+/**
+ * Walks the ATN for a single rule only. It returns the token stream position
+ * for each path that could be matched in this rule. The result can be empty in
+ * case we hit only non-epsilon transitions that didn't match the current input
+ * or if we hit the caret position.
+ *
+ * @param startState The start state.
+ * @param tokenListIndex The token index we are currently at.
+ * @param callStack The stack that indicates where in the ATN we are currently.
+ * @param precedence The current precedence level.
+ * @param indentation A value to determine the current indentation when doing
+ * debug prints.
+ * @returns the set of token stream indexes (which depend on the ways that had
+ * to be taken).
+ */
+CodeCompletionCore::RuleEndStatus CodeCompletionCore::processRule(  // NOLINT
+    antlr4::atn::RuleStartState* startState,
+    size_t tokenListIndex,
+    RuleWithStartTokenList& callStack,
+    int precedence,      // NOLINT
+    size_t indentation,  // NOLINT
+    bool& timedOut
+) {
+  // Cancelled by external caller?
+  if (cancel != nullptr && cancel->load()) {
+    timedOut = true;
+    return {};
+  }
+
+  // Check for timeout
+  timedOut = false;
+  if (timeout.has_value() && std::chrono::steady_clock::now() - timeoutStart > timeout) {
+    timedOut = true;
+    return {};
+  }
+
+  // Start with rule specific handling before going into the ATN walk.
+
+  // Check first if we've taken this path with the same input before.
+  std::unordered_map<size_t, RuleEndStatus>& positionMap = shortcutMap[startState->ruleIndex];
+  if (positionMap.contains(tokenListIndex)) {
+    if (debugOptions.showDebugOutput) {
+      std::cout << "=====> shortcut" << "\n";
+    }
+    return positionMap[tokenListIndex];
+  }
+
+  RuleEndStatus result;
+
+  // For rule start states we determine and cache the follow set, which gives us
+  // 3 advantages: 1) We can quickly check if a symbol would be matched when we
+  // follow that rule. We can so check in advance
+  //    and can save us all the intermediate steps if there is no match.
+  // 2) We'll have all symbols that are collectable already together when we are
+  // at the caret on rule enter. 3) We get this lookup for free with any 2nd or
+  // further visit of the same rule, which often happens
+  //    in non trivial grammars, especially with (recursive) expressions and of
+  //    course when invoking code completion multiple times.
+  FollowSetsPerState& setsPerState = followSetsByATN[typeid(parser)];
+
+  if (!setsPerState.contains(startState->stateNumber)) {
+    antlr4::atn::RuleStopState* stop = atn->ruleToStopState[startState->ruleIndex];
+    setsPerState[startState->stateNumber] = determineFollowSets(startState, stop);
+  }
+
+  const FollowSetsHolder& followSets = setsPerState[startState->stateNumber];
+
+  // Get the token index where our rule starts from our (possibly filtered)
+  // token list
+  const size_t startTokenIndex = tokens[tokenListIndex]->getTokenIndex();
+
+  callStack.push_back({
+      .startTokenIndex = startTokenIndex,
+      .ruleIndex = startState->ruleIndex,
+  });
+
+  if (tokenListIndex >= tokens.size() - 1) {  // At caret?
+    if (preferredRules.contains(startState->ruleIndex)) {
+      // No need to go deeper when collecting entries and we reach a rule that
+      // we want to collect anyway.
+      translateStackToRuleIndex(callStack);
+    } else {
+      // Convert all follow sets to either single symbols or their associated
+      // preferred rule and add the result to our candidates list.
+      for (const FollowSetWithPath& set : followSets.sets) {
+        RuleWithStartTokenList fullPath = callStack;
+
+        // Rules derived from our followSet will always start at the same token
+        // as our current rule.
+        for (const size_t rule : set.path) {
+          fullPath.push_back({
+              .startTokenIndex = startTokenIndex,
+              .ruleIndex = rule,
+          });
+        }
+
+        if (!translateStackToRuleIndex(fullPath)) {
+          for (const size_t symbol : set.intervals.toList()) {
+            if (!ignoredTokens.contains(symbol)) {
+              if (debugOptions.showDebugOutput) {
+                std::cout << "=====> collected: " << vocabulary->getDisplayName(symbol) << "\n";
+              }
+              if (!candidates.tokens.contains(symbol)) {
+                // Following is empty if there is more than one entry in the
+                // set.
+                candidates.tokens[symbol] = set.following;
+              } else if (candidates.tokens[symbol] != set.following) {
+                // More than one following list for the same symbol.
+                candidates.tokens[symbol] = {};
+              }
+            }
+          }
+        }
+      }
+    }
+
+    if (!followSets.isExhaustive) {
+      // If we're at the caret but the follow sets is non-exhaustive (empty or
+      // all tokens are optional), we should continue to collect tokens
+      // following this rule
+      result.insert(tokenListIndex);
+    }
+
+    callStack.pop_back();
+
+    return result;
+  }
+
+  // Process the rule if we either could pass it without consuming anything
+  // (epsilon transition) or if the current input symbol will be matched
+  // somewhere after this entry point. Otherwise stop here.
+  const size_t currentSymbol = tokens[tokenListIndex]->getType();
+  if (followSets.isExhaustive && !followSets.combined.contains(currentSymbol)) {
+    callStack.pop_back();
+
+    return result;
+  }
+
+  if (startState->isLeftRecursiveRule) {
+    precedenceStack.push_back(precedence);
+  }
+
+  // The current state execution pipeline contains all yet-to-be-processed ATN
+  // states in this rule. For each such state we store the token index + a list
+  // of rules that lead to it.
+  std::vector<PipelineEntry> statePipeline;
+
+  // Bootstrap the pipeline.
+  statePipeline.push_back({.state = startState, .tokenListIndex = tokenListIndex});
+
+  while (!statePipeline.empty()) {
+    if (cancel != nullptr && cancel->load()) {
+      timedOut = true;
+      return {};
+    }
+
+    const PipelineEntry currentEntry = statePipeline.back();
+    statePipeline.pop_back();
+    ++statesProcessed;
+
+    const size_t currentSymbol = tokens[currentEntry.tokenListIndex]->getType();
+
+    const bool atCaret = currentEntry.tokenListIndex >= tokens.size() - 1;
+    if (debugOptions.showDebugOutput) {
+      printDescription(
+          indentation,
+          currentEntry.state,
+          generateBaseDescription(currentEntry.state),
+          currentEntry.tokenListIndex
+      );
+      if (debugOptions.showRuleStack) {
+        printRuleState(callStack);
+      }
+    }
+
+    if (currentEntry.state->getStateType() == antlr4::atn::ATNStateType::RULE_STOP) {
+      // Record the token index we are at, to report it to the caller.
+      result.insert(currentEntry.tokenListIndex);
+      continue;
+    }
+
+    // We simulate here the same precedence handling as the parser does, which
+    // uses hard coded values. For rules that are not left recursive this value
+    // is ignored (since there is no precedence transition).
+    for (const antlr4::atn::ConstTransitionPtr& transition : currentEntry.state->transitions) {
+      switch (transition->getTransitionType()) {
+        case antlr4::atn::TransitionType::RULE: {
+          const auto* ruleTransition =
+              dynamic_cast<const antlr4::atn::RuleTransition*>(transition.get());
+          auto* ruleStartState = dynamic_cast<antlr4::atn::RuleStartState*>(ruleTransition->target);
+          bool innerCancelled = false;
+          const RuleEndStatus endStatus = processRule(
+              ruleStartState,
+              currentEntry.tokenListIndex,
+              callStack,
+              ruleTransition->precedence,
+              indentation + 1,
+              innerCancelled
+          );
+
+          if (innerCancelled) {
+            timedOut = true;
+            return {};
+          }
+
+          for (const size_t position : endStatus) {
+            statePipeline.push_back({
+                .state = ruleTransition->followState,
+                .tokenListIndex = position,
+            });
+          }
+
+        } break;
+
+        case antlr4::atn::TransitionType::PREDICATE: {
+          const auto* predTransition =
+              dynamic_cast<const antlr4::atn::PredicateTransition*>(transition.get());
+          if (checkPredicate(predTransition)) {
+            statePipeline.push_back({
+                .state = transition->target,
+                .tokenListIndex = currentEntry.tokenListIndex,
+            });
+          }
+
+        } break;
+
+        case antlr4::atn::TransitionType::PRECEDENCE: {
+          const auto* predTransition =
+              dynamic_cast<const antlr4::atn::PrecedencePredicateTransition*>(transition.get());
+          if (predTransition->getPrecedence() >= precedenceStack[precedenceStack.size() - 1]) {
+            statePipeline.push_back({
+                .state = transition->target,
+                .tokenListIndex = currentEntry.tokenListIndex,
+            });
+          }
+
+        } break;
+
+        case antlr4::atn::TransitionType::WILDCARD: {
+          if (atCaret) {
+            if (!translateStackToRuleIndex(callStack)) {
+              for (const auto token :
+                   std::views::iota(antlr4::Token::MIN_USER_TOKEN_TYPE, atn->maxTokenType + 1)) {
+                if (!ignoredTokens.contains(token)) {
+                  candidates.tokens[token] = {};
+                }
+              }
+            }
+          } else {
+            statePipeline.push_back({
+                .state = transition->target,
+                .tokenListIndex = currentEntry.tokenListIndex + 1,
+            });
+          }
+
+        } break;
+
+        default: {
+          if (transition->isEpsilon()) {
+            // Jump over simple states with a single outgoing epsilon
+            // transition.
+            statePipeline.push_back({
+                .state = transition->target,
+                .tokenListIndex = currentEntry.tokenListIndex,
+            });
+            continue;
+          }
+
+          antlr4::misc::IntervalSet set = transition->label();
+          if (!set.isEmpty()) {
+            if (transition->getTransitionType() == antlr4::atn::TransitionType::NOT_SET) {
+              set = set.complement(allUserTokens());
+            }
+            if (atCaret) {
+              if (!translateStackToRuleIndex(callStack)) {
+                const std::vector<ptrdiff_t> list = set.toList();
+                const bool hasTokenSequence = list.size() == 1;
+                for (const size_t symbol : list) {
+                  if (!ignoredTokens.contains(symbol)) {
+                    if (debugOptions.showDebugOutput) {
+                      std::cout << "=====> collected: " << vocabulary->getDisplayName(symbol)
+                                << "\n";
+                    }
+
+                    std::vector<size_t> followingTokens;
+                    if (hasTokenSequence) {
+                      followingTokens = getFollowingTokens(transition.get());
+                    }
+
+                    if (!candidates.tokens.contains(symbol)) {
+                      candidates.tokens[symbol] = followingTokens;
+                    } else {
+                      candidates.tokens[symbol] =
+                          longestCommonPrefix(followingTokens, candidates.tokens[symbol]);
+                    }
+                  }
+                }
+              }
+            } else {
+              if (set.contains(currentSymbol)) {
+                if (debugOptions.showDebugOutput) {
+                  std::cout << "=====> consumed: " << vocabulary->getDisplayName(currentSymbol)
+                            << "\n";
+                }
+                statePipeline.push_back({
+                    .state = transition->target,
+                    .tokenListIndex = currentEntry.tokenListIndex + 1,
+                });
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+
+  callStack.pop_back();
+  if (startState->isLeftRecursiveRule) {
+    precedenceStack.pop_back();
+  }
+
+  // Cache the result, for later lookup to avoid duplicate walks.
+  positionMap[tokenListIndex] = result;
+
+  return result;
+}
+
+antlr4::misc::IntervalSet CodeCompletionCore::allUserTokens() const {
+  const auto min = antlr4::Token::MIN_USER_TOKEN_TYPE;
+  const auto max = static_cast<ptrdiff_t>(atn->maxTokenType);
+  return antlr4::misc::IntervalSet::of(min, max);
+}
+
+std::string CodeCompletionCore::generateBaseDescription(antlr4::atn::ATNState* state) {
+  const std::string stateValue = (state->stateNumber == antlr4::atn::ATNState::INVALID_STATE_NUMBER)
+                                     ? "Invalid"
+                                     : std::to_string(state->stateNumber);
+  std::stringstream output;
+
+  output << "[" << stateValue << " " << atnStateTypeMap[static_cast<size_t>(state->getStateType())]
+         << "]";
+  output << " in ";
+  output << ruleNames->at(state->ruleIndex);
+  return output.str();
+}
+
+void CodeCompletionCore::printDescription(
+    size_t indentation,
+    antlr4::atn::ATNState* state,
+    std::string const& baseDescription,
+    size_t tokenIndex
+) {
+  const auto indent = std::string(indentation * 2, ' ');
+
+  std::string transitionDescription;
+  if (debugOptions.showTransitions) {
+    for (const antlr4::atn::ConstTransitionPtr& transition : state->transitions) {
+      std::string labels;
+      std::vector<ptrdiff_t> symbols = transition->label().toList();
+
+      if (symbols.size() > 2) {
+        // Only print start and end symbols to avoid large lists in debug output.
+        labels = vocabulary->getDisplayName(static_cast<size_t>(symbols[0])) + " .. " +
+                 vocabulary->getDisplayName(static_cast<size_t>(symbols[symbols.size() - 1]));
+      } else {
+        for (const size_t symbol : symbols) {
+          if (!labels.empty()) {
+            labels += ", ";
+          }
+          labels += vocabulary->getDisplayName(symbol);
+        }
+      }
+      if (labels.empty()) {
+        labels = "ε";
+      }
+
+      transitionDescription += "\n";
+      transitionDescription += indent;
+      transitionDescription += "\t(";
+      transitionDescription += labels;
+      transitionDescription += ") [";
+      transitionDescription += std::to_string(transition->target->stateNumber);
+      transitionDescription += " ";
+      transitionDescription +=
+          atnStateTypeMap[static_cast<size_t>(transition->target->getStateType())];
+      transitionDescription += "] in ";
+      transitionDescription += ruleNames->at(transition->target->ruleIndex);
+    }
+  }
+
+  std::string output;
+  if (tokenIndex >= tokens.size() - 1) {
+    output = "<<" + std::to_string(tokenStartIndex + tokenIndex) + ">> ";
+  } else {
+    output = "<" + std::to_string(tokenStartIndex + tokenIndex) + "> ";
+  }
+
+  std::cout << indent + output + "Current state: " + baseDescription + transitionDescription
+            << "\n";
+}
+
+void CodeCompletionCore::printRuleState(RuleWithStartTokenList const& stack) {
+  if (stack.empty()) {
+    std::cout << "<empty stack>\n";
+    return;
+  }
+
+  for (const RuleWithStartToken& rule : stack) {
+    std::cout << ruleNames->at(rule.ruleIndex);
+  }
+  std::cout << "\n";
+}
+
+void CodeCompletionCore::printOverallResults() {
+  if (debugOptions.showResult) {
+    if (candidates.isCancelled) {
+      std::cout << "*** TIMED OUT ***\n";
+    }
+
+    std::cout << "States processed: " << statesProcessed << "\n\n";
+
+    std::cout << "Collected rules:\n";
+    for (const auto& [tokenIndex, rule] : candidates.rules) {
+      std::cout << ruleNames->at(tokenIndex);
+      std::cout << ", path: ";
+
+      for (const size_t token : rule.ruleList) {
+        std::cout << ruleNames->at(token) << " ";
+      }
+    }
+    std::cout << "\n\n";
+
+    std::set<std::string> sortedTokens;
+    for (const auto& [token, tokenList] : candidates.tokens) {
+      std::string value = vocabulary->getDisplayName(token);
+      for (const size_t following : tokenList) {
+        value += " " + vocabulary->getDisplayName(following);
+      }
+      sortedTokens.emplace(value);
+    }
+
+    std::cout << "Collected tokens:\n";
+    for (const std::string& symbol : sortedTokens) {
+      std::cout << symbol;
+    }
+    std::cout << "\n\n";
+  }
+}
+
+}  // namespace c3
diff --git a/contrib/libs/antlr4-c3/src/CodeCompletionCore.hpp b/contrib/libs/antlr4-c3/src/CodeCompletionCore.hpp
new file mode 100644
index 0000000000..de90341594
--- /dev/null
+++ b/contrib/libs/antlr4-c3/src/CodeCompletionCore.hpp
@@ -0,0 +1,265 @@
+//
+//  CodeCompletionCore.hpp
+//
+//  C++ port of antlr4-c3 (TypeScript) by Mike Lischke
+//  Licensed under the MIT License.
+//
+
+#pragma once
+
+#include <Parser.h>
+#include <ParserRuleContext.h>
+#include <Token.h>
+#include <Vocabulary.h>
+#include <atn/ATNState.h>
+#include <atn/PredicateTransition.h>
+#include <atn/RuleStartState.h>
+#include <atn/Transition.h>
+#include <misc/IntervalSet.h>
+
+#include <atomic>
+#include <chrono>
+#include <cstddef>
+#include <map>
+#include <optional>
+#include <string>
+#include <typeindex>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+namespace c3 {
+
+using TokenList = std::vector<size_t>;
+
+using RuleList = std::vector<size_t>;
+
+struct CandidateRule {
+  size_t startTokenIndex;
+  RuleList ruleList;
+
+  friend bool operator==(const CandidateRule& lhs, const CandidateRule& rhs) = default;
+};
+
+/**
+ * All the candidates which have been found. Tokens and rules are separated.
+ * – Token entries include a list of tokens that directly follow them (see also
+ * the "following" member in the FollowSetWithPath class). – Rule entries
+ * include the index of the starting token within the evaluated rule, along with
+ * a call stack of rules found during evaluation. – cancelled will be true if
+ * the collectCandidates() was cancelled or timed out.
+ */
+struct CandidatesCollection {
+  std::map<size_t, TokenList> tokens;
+  std::map<size_t, CandidateRule> rules;
+  bool isCancelled;
+
+  friend bool operator==(const CandidatesCollection& lhs, const CandidatesCollection& rhs) =
+      default;
+};
+
+/**
+ * Optional parameters for `CodeCompletionCore`.
+ */
+struct Parameters {
+  /** An option parser rule context to limit the search space. */
+  const antlr4::ParserRuleContext* context = nullptr;
+
+  /** If non-zero, the number of milliseconds until collecting times out. */
+  std::optional<std::chrono::milliseconds> timeout = std::nullopt;
+
+  /**
+   * If set to a non-`NULL` atomic boolean, and that boolean value is set to
+   * true while the function is executing, then collecting candidates will abort
+   * as soon as possible.
+   */
+  std::atomic<bool>* isCancelled = nullptr;
+};
+
+struct DebugOptions {
+  /**
+   * Not dependent on showDebugOutput.
+   * Prints the collected rules + tokens to terminal.
+   */
+  bool showResult = false;
+
+  /**
+   * Enables printing ATN state info to terminal.
+   */
+  bool showDebugOutput = false;
+
+  /**
+   * Only relevant when showDebugOutput is true.
+   * Enables transition printing for a state.
+   */
+  bool showTransitions = false;
+
+  /**
+   * Only relevant when showDebugOutput is true.
+   * Enables call stack printing for each rule recursion.
+   */
+  bool showRuleStack = false;
+};
+
+class CodeCompletionCore {
+private:
+  struct PipelineEntry {
+    antlr4::atn::ATNState* state;
+    size_t tokenListIndex;
+  };
+
+  struct RuleWithStartToken {
+    size_t startTokenIndex;
+    size_t ruleIndex;
+  };
+
+  using RuleWithStartTokenList = std::vector<RuleWithStartToken>;
+
+  /**
+   * A record for a follow set along with the path at which this set was found.
+   * If there is only a single symbol in the interval set then we also collect and
+   * store tokens which follow this symbol directly in its rule (i.e. there is no
+   * intermediate rule transition). Only single label transitions are considered.
+   * This is useful if you have a chain of tokens which can be suggested as a
+   * whole, because there is a fixed sequence in the grammar.
+   */
+  struct FollowSetWithPath {
+    antlr4::misc::IntervalSet intervals;
+    RuleList path;
+    TokenList following;
+  };
+
+  /**
+   * A list of follow sets (for a given state number) + all of them combined for
+   * quick hit tests + whether they are exhaustive (false if subsequent
+   * yet-unprocessed rules could add further tokens to the follow set, true
+   * otherwise). This data is static in nature (because the used ATN states are
+   * part of a static struct: the ATN). Hence it can be shared between all C3
+   * instances, however it depends on the actual parser class (type).
+   */
+  struct FollowSetsHolder {
+    std::vector<FollowSetWithPath> sets;
+    antlr4::misc::IntervalSet combined;
+    bool isExhaustive;
+  };
+
+  using FollowSetsPerState = std::unordered_map<size_t, FollowSetsHolder>;
+
+  /** Token stream position info after a rule was processed. */
+  using RuleEndStatus = std::unordered_set<size_t>;
+
+public:
+  explicit CodeCompletionCore(antlr4::Parser* parser);
+
+  /**
+   * Tailoring of the result:
+   * Tokens which should not appear in the candidates set.
+   */
+  std::unordered_set<size_t> ignoredTokens;  // NOLINT: public field
+
+  /**
+   * Rules which replace any candidate token they contain.
+   * This allows to return descriptive rules (e.g. className, instead of
+   * ID/identifier).
+   */
+  std::unordered_set<size_t> preferredRules;  // NOLINT: public field
+
+  /**
+   * Specify if preferred rules should translated top-down (higher index rule
+   * returns first) or bottom-up (lower index rule returns first).
+   */
+  bool translateRulesTopDown = false;  // NOLINT: public field
+
+  /**
+   * Print human readable ATN state and other info.
+   */
+  DebugOptions debugOptions;  // NOLINT: public field
+
+  /**
+   * This is the main entry point. The caret token index specifies the token
+   * stream index for the token which currently covers the caret (or any other
+   * position you want to get code completion candidates for). Optionally you
+   * can pass in a parser rule context which limits the ATN walk to only that or
+   * called rules. This can significantly speed up the retrieval process but
+   * might miss some candidates (if they are outside of the given context).
+   *
+   * @param caretTokenIndex The index of the token at the caret position.
+   * @param parameters Optional parameters.
+   * @returns The collection of completion candidates. If cancelled or timed
+   * out, the returned collection will have its 'cancelled' value set to true
+   * and the collected candidates may be incomplete.
+   */
+  CandidatesCollection collectCandidates(size_t caretTokenIndex, Parameters parameters = {});
+
+private:
+  static thread_local std::unordered_map<std::type_index, FollowSetsPerState> followSetsByATN;
+  static std::vector<std::string> atnStateTypeMap;
+
+  antlr4::Parser* parser;
+  const antlr4::atn::ATN* atn;
+  const antlr4::dfa::Vocabulary* vocabulary;
+  const std::vector<std::string>* ruleNames;
+  std::vector<const antlr4::Token*> tokens;
+  std::vector<int> precedenceStack;
+
+  size_t tokenStartIndex = 0;
+  size_t statesProcessed = 0;
+
+  /**
+   * A mapping of rule index + token stream position to end token positions.
+   * A rule which has been visited before with the same input position will
+   * always produce the same output positions.
+   */
+  std::unordered_map<size_t, std::unordered_map<size_t, RuleEndStatus>> shortcutMap;
+
+  /** The collected candidates (rules and tokens). */
+  c3::CandidatesCollection candidates;
+
+  std::optional<std::chrono::milliseconds> timeout;
+  std::atomic<bool>* cancel;
+  std::chrono::steady_clock::time_point timeoutStart;
+
+  bool checkPredicate(const antlr4::atn::PredicateTransition* transition);
+
+  bool translateStackToRuleIndex(RuleWithStartTokenList const& ruleWithStartTokenList);
+
+  bool translateToRuleIndex(size_t index, RuleWithStartTokenList const& ruleWithStartTokenList);
+
+  static std::vector<size_t> getFollowingTokens(const antlr4::atn::Transition* transition);
+
+  FollowSetsHolder determineFollowSets(antlr4::atn::ATNState* start, antlr4::atn::ATNState* stop);
+
+  bool collectFollowSets(
+      antlr4::atn::ATNState* state,
+      antlr4::atn::ATNState* stopState,
+      std::vector<FollowSetWithPath>& followSets,
+      std::vector<antlr4::atn::ATNState*>& stateStack,
+      std::vector<size_t>& ruleStack
+  );
+
+  RuleEndStatus processRule(
+      antlr4::atn::RuleStartState* startState,
+      size_t tokenListIndex,
+      RuleWithStartTokenList& callStack,
+      int precedence,
+      size_t indentation,
+      bool& timedOut
+  );
+
+  antlr4::misc::IntervalSet allUserTokens() const;
+
+  std::string generateBaseDescription(antlr4::atn::ATNState* state);
+
+  void printDescription(
+      size_t indentation,
+      antlr4::atn::ATNState* state,
+      std::string const& baseDescription,
+      size_t tokenIndex
+  );
+
+  void printRuleState(RuleWithStartTokenList const& stack);
+
+  void printOverallResults();
+};
+
+}  // namespace c3
diff --git a/contrib/libs/antlr4-c3/ya.make b/contrib/libs/antlr4-c3/ya.make
new file mode 100644
index 0000000000..abffa08b29
--- /dev/null
+++ b/contrib/libs/antlr4-c3/ya.make
@@ -0,0 +1,23 @@
+# Generated by devtools/yamaker/ym2
+
+LIBRARY()
+
+LICENSE(MIT)
+
+LICENSE_TEXTS(.yandex_meta/licenses.list.txt)
+
+VERSION(2.0.0)
+
+ORIGINAL_SOURCE(https://github.com/mike-lischke/antlr4-c3/archive/refs/tags/cpp-2.0.0.tar.gz)
+
+NO_COMPILER_WARNINGS()
+
+SUBSCRIBER(g:cpp-contrib)
+
+PEERDIR(
+    contrib/libs/antlr4_cpp_runtime
+)
+
+SRC(src/CodeCompletionCore.cpp)
+
+END()